Abstract. -We introduce a new distributed algorithm for aligning graphs or finding substructures within a given graph. It is based on the cavity method and is used to study the maximum-clique and the graph-alignment problems in random graphs. The algorithm allows to analyze large graphs and may find applications in fields such as computational biology. As a proof of concept we use our algorithm to align the similarity graphs of two interacting protein families involved in bacterial signal transduction, and to predict actually interacting protein partners between these families. Over the last decade, the use of graphs for the description of relations between components of complex systems has become increasingly popular [1] . However, most part of the current literature concentrates on (computationally accessible) local characteristics like node degrees, whereas the full exploitation of more global properties of large networks remains frequently elusive due to their inherent algorithmic complexity. Most often studying global properties requires solving NP-hard problems or even harder problems if some form of uncertainty or lack of information is included in the definition of the problem. In both cases heuristic algorithms need to be developed. Specific examples, covered by this article, include the comparison of two different networks, the so-called graph-alignment problem (GA) [2] [3] [4] , and the sub-graph isomorphism (SGI), as a particular case of which we consider the widely studied maximum-clique problem [5] [6] [7] . Recently, there has been a lot of interest in distributed algorithms to deal with optimization problems over networks. In the context of statistical physics a new generation of algorithms has been developed (e.g. [8, 9] ) that have shown promising performance on several applications (for a review, see [10] ). These techniques are based on the so called cavity method and are known as message-passing (MP) algorithms. They are fully distributed and easy to run on parallel machines. A recent result in this framework is an algorithm for finding a connected sub-graph of a given graph which optimizes a given factorized cost function [11]. Here we aim at making a step forward by introducing new techniques for SGI and GA. We develop two alternative MP strategies and test their performance on three sample problems. The first two are well-defined theoretical benchmarks, where our results can be compared to rigorous bounds: (i) the maximum-clique problem in random graphs for the SGI problem; and (ii) the alignment of two random graphs of controlled similarity. The third sample problem is thought as a proof-of-concept application in computational biology: We study (iii) the alignment of the similarity networks of two interacting protein-domain families involved in bacterial signal transduction, to identify actual signaling pathways. This case, involving large networks of >2500 nodes, exploits co-evolutionary processes between interacting proteins to identify interaction partners [12] . The model -Both problems, SGI and GA, can be put into the common framework of matching two graphs of possibly different size. Let G = (V, E, w) and G ′ = (V ′ , E ′ , w ′ ) be two weighted graphs with nodes V, V ′ , edges E, E ′ and edge weights w, w ′ . In the applications shown in this letter, weights are non-negative, but this is not a necessary condition for the applicability of the message-passing algorithms. In the case of unweighted graphs, we assume w and w ′ to describe the adjacency matrices, i.e. weights are one if an edge is present between two vertices, and zero else. Further more we denote the node number by N = |V | (N ′ = |V ′ |), and the edge number by M = |E| (M ′ = |E ′ |). Neighbors of a node i are assembled in ∂i. To facilitate notation, primed quantities (in particular node indices) will always refer to G
Although both REF and this work share the use of a BP approach, the factor graph and the algorithms are different.
Aligning graphs and finding substructures by a cavity approach
2010 Europhys. Lett. 89 37009
Physics Biology Computer Science