We present a new algorithm, global positioning graph matching (GPGM), to perform global network alignments between pairs of undirected graphs by minimizing a dissimilarity score over matched vertices. We define structural dissimilarities based on a random walk over each graph to provide a robust measure of the global graph topology using a nonlinear manifold learning algorithm known as diffusion maps. Measures of vertex-vertex dissimilarity are straightforwardly incorporated in a convex combination. We have tested our approach in pairwise alignments of protein-protein interaction networks of Xenopus laevis (frog), Rattus norvegicus (rat), Caenorhabditis elegans (worm), Mus musculus (mouse), and Drosophila melanogaster (fly). When vertex-vertex dissimilarities are incorporated using homology scores between protein sequences, the performance of GPGM is comparable to that of the IsoRank algorithm (Singh et al. Proc. Natl. Acad. Sci. USA 105 35 12763 (2008)). When homology information is not included, GPGM discovers superior alignments, making it well suited to graph matching applications where vertex labels are unknown or undefined.
BandyopadhyayS., SharanR. and IdekerT., Systematic identification of functional orthologs based on protein network comparison, Genome Research16(3) (2006), 428-435.
2.
BechtoldT., RudnyiE.B. and KorvinkJ.G., Fast Simulation of Electro-Thermal MEMS: Efficient Dynamic Compact Models, Springer-Verlag, Berlin Heidelberg, 2007.
3.
BelkinM. and NiyogiP., Laplacian eigenmaps for dimensionality reduction and data representation, Neural Computation15(6) (2003), 1373-1396.
4.
ChoM., LeeJ. and LeeK., Reweighted random walks for graph matching, in: Computer Vision - ECCV 2010 (Lecture Notes in Computer Science)6315, DaniilidisK., MaragosP. and ParagiosN., eds, Springer-Verlag, Berlin Heidelberg, 2010, pp. 492-505.
5.
CoifmanR.R. and LafonS., Diffusion maps, Applied and Computational Harmonic Analysis21(1) (2006), 5-30.
6.
CoifmanR.R., ShkolniskyY., SigworthF.J. and SingerA., Graph laplacian tomography from unknown random projections, IEEE Transactions on Image Processing17(10) (2008), 1891-1899.
7.
ConteD., FoggiaP., SansoneC. and VentoM., Thirty years of graph matching in pattern recognition, International Journal of Pattern Recognition and Artificial Intelligence18(3) (2004), 265-298.
8.
CourT., SrinivasanP. and ShiJ., Balanced graph matching, in: Advances in Neural Information Processing Systems 19, SchölkopfB., PlattJ. and HoffmanT., eds, MIT Press, Cambridge, 2007, pp. 313-320.
9.
DimitrovP., PhillipsC. and SiddiqiK., Robust and efficient skeletal graphs, Proceedings of the IEEE Conference of Computer Vision and Pattern Recognition1 (2000), 417-423.
10.
DuchenneO., BachF., KweonI.-S. and PonceJ., A tensor-based algorithm for high-order graph matching, IEEE Transactions on Pattern Analysis and Machine Intelligence33(12) (2011), 2383-2395.
11.
FergusonA.L., PanagiotopoulosA.Z., DebenedettiP.G. and KevrekidisI.G., Systematic determination of order parameters for chain dynamics using diffusion maps, Proceedings of the National Academy of Sciences of the USA107(31) (2010), 13597-13602.
12.
FergusonA.L., PanagiotopoulosA.Z., KevrekidisI.G. and DebenedettiP.G., Nonlinear dimensionality reduction in molecular simulation: The diffusion map approach, Chemical Physics Letters509(1) (2011), 1-11.
13.
FergusonA.L., ZhangS., DikiyI., PanagiotopoulosA.Z., DebenedettiP.G. and LinkA.J., An experimental and computational investigation of spontaneous lasso formation in microcin J25, Biophysical Journal99(9) (2010), 3056-3065.
14.
GolubG.H. and Van LoanC.F., Matrix computations (4th ed.), JHU Press, Baltimore, 2012.
15.
GopalanP.K. and BleiD.M., Efficient discovery of overlapping communities in massive networks, Proceedings of the National Academy of Sciences of the USA110(36) (2013), 14534-14539.
16.
HardyG.H., LittlewoodJ.E. and PolyaG., Inequalities (2nd ed.), Cambridge University Press, Cambridge, 1952.
17.
HenikoffS. and HenikoffJ.G., Amino acid substitution matrices from protein blocks, Proceedings of the National Academy of Sciences of the USA89(22) (1992), 10915-10919.
18.
KelleyB.P., SharanR., KarpR.M., SittlerT., RootD.E., StockwellB.R. and IdekerT., Conserved pathways within bacteria and yeast as revealed by global protein network alignment, Proceedings of the National Academy of Sciences of the USA100(20) (2003), 11394-11399.
19.
KlauG.W., A new graph-based method for pairwise global network alignment, BMC Bioinformatics10(Suppl. I) (2009), S59.
20.
KuhnH.W., The hungarian method for the assignment problem, Naval Research Logistics Quarterly2(1-2) (1955) 83-97.
21.
LarsenR.M., Lanczos bidiagonalization with partial reorthogonalization, DAIMI PB-357 Technical Report, Aarhus University, 1998.
22.
LeordeanuM. and HebertM., A spectral technique for correspondence problems using pairwise constraints, Tenth IEEE International Conference on Computer Vision2 (2005), 1482-1489.
23.
LiaoC.-S., LuK., BaymM., SinghR. and BergerB., IsoRankN: Spectral methods for global alignment of multiple protein networks, Bioinformatics25(12) (2009), i253-i258.
24.
LongA.W. and FergusonA.L., Nonlinear machine learning of patchy particle assembly pathways and mechanisms, The Journal of Physical Chemistry B118(15) (2014), 4228-4244.
25.
MitraK., CarvunisA.-R., RameshS.K. and IdekerT., Integrative approaches for finding modular structure in biological networks, Nature Reviews Genetics14(10) (2013), 719-732.
26.
NadlerB., LafonS., CoifmanR.R. and KevrekidisI., Diffusion maps, spectral clustering and eigenfunctions of fokker-planck operators, in: Advances in Neural Information Processing Systems, WeissY., SchölkopfB. and PlattJ., eds, Vol. 18, MIT Press, Cambridge, 2006, pp. 955-962.
27.
NewmanM.E.J. and GirvanM., Finding and evaluating community structure in networks, Physical Review E69(2) (2004), 026113.
28.
PearsonW.R. and LipmanD.J., Improved tools for biological sequence comparison, Proceedings of the National Academy of Sciences of the USA85(8) (1988), 2444-2448.
29.
PearsonW.R., WoodT., ZhangZ. and MillerW., Comparison of DNA sequences with protein sequences, Genomics46(1) (1997), 24-36.
30.
SingerA., A remark on global positioning from local distances, Proceedings of the National Academy of Sciences of the USA105(28) (2008), 9507-9511.
31.
SinghR., XuJ. and BergerB., Global alignment of multiple protein interaction networks with application to functional orthology detection, Proceedings of the National Academy of Sciences of the USA105(35) (2008), 12763-12768.
32.
StarkC., BreitkreutzB.-J., RegulyT., BoucherL., BreitkreutzA. and TyersM., BioGRID: A general repository for interaction datasets, Nucleic Acids Research34(Suppl. I) (2006), D535-D539.
33.
ZaslavskiyM., BachF. and VertJ.-P., Global alignment of protein-protein interaction networks by graph matching methods, Bioinformatics25(12) (2009), 1259-1267.
34.
FanW., Graph pattern matching revised for social network analysis, in: Proceedings of the 15th International Conference on Database Theory, MarklV., ManolescuI., Amer-YahiaS., NaumannF. and AriI., eds, Association for Computing Machinery, New York, 2012, pp. 8-21.
35.
Olfati-SaberR., FaxJ.A. and MurrayR.M., Consensus and cooperation in networked multi-agent systems, Proceedings of the IEEE95(1) (2007), 215-233.
