Aligning Spatially Constrained Graphs
Pages 7712 - 7723
Abstract
We focus on the problem of aligning graphs that have a spatial basis. In such graphs, which we refer to as <italic>rigid graphs</italic>, nodes have preferred positions relative to their graph neighbors. Rigid graphs can be used to abstract objects in diverse applications such as large biomolecules, where edges corresponding to chemical bonds have preferred lengths, functional connectomes of the human brain, where edges corresponding to co-firing regions of the brain have preferred anatomical distances, and mobile device/ sensor communication logs, where edges corresponding to point-to-point communications across devices have distance constraints. Effective analysis of such graphs must account for edge lengths in addition to topological features. For instance, when identifying conserved patterns through graph alignment, it is important for matched edges to have correlated lengths, in addition to topological similarity. In this paper, we formulate the problem of <italic>rigid graph alignment</italic> and present a method for solving it. Our formulation of rigid graph alignment simultaneously aligns the topology of the input graphs, as well as the geometric structure represented by the edge lengths, which is solved using a block coordinate descent technique. Using detailed experiments on real and synthetic datasets, we demonstrate a number of important desirable features of our method: (i) it significantly outperforms topological and structural aligners on a wide range of problems; (ii) it scales to problems in important real-world applications; and (iii) it has excellent stability properties, in view of noise and missing data in typical applications.
References
[1]
M. E. J. Newman, “Modularity and community structure in networks,” Proc. Nat. Acad. Sci., vol. 103, no. 23, 2006, Art. no. [Online]. Available: http://www.pnas.org/content/103/23/8577.abstract
[2]
D. Godwin, R. L. Barry, and R. Marois, “Breakdown of the brain's functional network modularity with awareness,” Proc. Nat. Acad. Sci., vol. 112, no. 12, 2015, Art. no. [Online]. Available: http://www.pnas.org/content/112/12/3799.abstract
[3]
S. P. Borgatti, “Centrality and network flow,” Soc. Netw., vol. 27, no. 1, pp. 55–71, 2005.
[4]
C. F. Negre et al., “Eigenvector centrality for characterization of protein allosteric pathways,” Proc. Nat. Acad. Sci., vol. 115, no. 52, pp. E12201–E12208, 2018.
[5]
R. Singh, J. Xu, and B. Berger, “Pairwise global alignment of protein interaction networks by matching neighborhood topology,” in Proc. 11th Annu. Int. Conf. Res. Comput. Mol. Biol., 2007, pp. 16–31.
[6]
H. Yin, A. R. Benson, J. Leskovec, and D. F. Gleich, “Local higher-order graph clustering,” in Proc. 23rd ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2017, pp. 555–564.
[7]
S. Aibar et al., “Scenic: Single-cell regulatory network inference and clustering,” Nature Methods, vol. 14, no. 11, pp. 1083–1086, 2017.
[8]
E. S. Finn et al., “Functional connectome fingerprinting: Identifying individuals using patterns of brain connectivity,” Nature Neurosci., vol. 18, no. 11, pp. 1664–1671, 2015.
[9]
V. Ravindra, H. Nassar, D. F. Gleich, and A. Grama, “Rigid graph alignment,” in Proc. 8th Int. Conf. Complex Netw. Appl. VIII, 2020, pp. 621–632.
[10]
E. H. Sussenguth, “A graph-theoretic algorithm for matching chemical structures,” J. Chem. Documentation, vol. 5, no. 1, pp. 36–43, Feb. 1965.
[11]
B. Zelinka, “On a certain distance between isomorphism classes of graphs,” Časopis Pro Pěstování Matematiky, vol. 100, no. 4, pp. 371–373, 1975.
[12]
B. Zelinka, “Distances between graphs (extended abstract),” in Proc. 4th Czechoslovakian Symp. Combinatorics, Graphs Complexity, 1992, pp. 355–361.
[13]
S. Umeyama, “An eigendecomposition approach to weighted graph matching problems,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 10, no. 5, pp. 695–703, Sep. 1988.
[14]
R. Singh, J. Xu, and B. Berger, “Pairwise global alignment of protein interaction networks by matching neighborhood topology,” in Proc. Annu. Int. Conf. Res. Comput. Mol. Biol., 2007, pp. 16–31.
[15]
G. Kollias, S. Mohammadi, and A. Grama, “Network similarity decomposition (NSD): A fast and scalable approach to network alignment,” IEEE Trans. Knowl. Data Eng., vol. 24, no. 12, pp. 2232–2243, Dec. 2012.
[16]
C.-S. Liao, K. Lu, M. Baym, R. Singh, and B. Berger, “Isorankn: Spectral methods for global alignment of multiple protein networks,” Bioinformatics, vol. 25, no. 12, pp. i253–i258, 2009.
[17]
G. W. Klau, “A new graph-based method for pairwise global network alignment,” BMC Bioinf., vol. 10, no. 1, Jan. 2009, Art. no.
[18]
G. Ciriello, M. Mina, P. H. Guzzi, M. Cannataro, and C. Guerra, “AlignNemo: A local network alignment method to integrate homology and topology,” PLoS One, vol. 7, no. 6, pp. 1–14, 06 2012.
[19]
J. Berg and M. Lässig, “Local graph alignment and motif search in biological networks,” Proc. Nat. Acad. Sci., vol. 101, no. 41, pp. 14689–14694, 2004. [Online]. Available: https://www.pnas.org/content/101/41/14689
[20]
W. HeimannLee, S. Pan, K.-Y. Chen, and D. Koutra, “HashAlign: Hash-based alignment of multiple graphs,” in Proc. Adv. Knowl. Discov. Data Mining, 2018, pp. 726–739.
[21]
V. Vijayan and T. Milenkovic, “Multiple network alignment via multimagna,” IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 15, no. 5, pp. 1669–1682, Sep./Oct. 2018.
[22]
H. Nassar, G. Kollias, A. Grama, and D. F. Gleich, “Low rank methods for multiple network alignment,” 2018, arXiv:1809.08198.
[23]
O. Kuchaiev, T. Milenković, V. Memišević, W. Hayes, and N. Pržulj, “Topological network alignment uncovers biological function and phylogeny,” J. Roy. Soc. Interface, vol. 7, no. 50, pp. 1341–1354, Sep. 2010. [Online]. Available: http://rsif.royalsocietypublishing.org/content/early/2010/03/24/rsif.2010.0063
[24]
R. Patro and C. Kingsford, “Global network alignment using multiscale spectral signatures,” Bioinformatics, vol. 28, no. 23, pp. 3105–3114, 2012.
[25]
S. Mohammadi, D. F. Gleich, T. G. Kolda, and A. Grama, “Triangular alignment (TAME): A tensor-based approach for higher-order network alignment,” IEEE/ACM Trans. Comput. Biol. Bioinf., vol. 14, no. 6, pp. 1446–1458, Nov./Dec. 2017.
[26]
S. Feizi, G. Quon, M. Recamonde-Mendoza, M. Medard, M. Kellis, and A. Jadbabaie, “Spectral alignment of graphs,” IEEE Trans. Netw. Sci. Eng., vol. 7, no. 3, pp. 1182–1197, Apr. 2019.
[27]
M. Bayati, D. F. Gleich, A. Saberi, and Y. Wang, “Message-passing algorithms for sparse network alignment,” ACM Trans. Knowl. Discov. Data, vol. 7, no. 1, pp. 3:1–3:31, Mar. 2013.
[28]
M. Heimann, H. Shen, T. Safavi, and D. Koutra, “Regal,” Proc. 27th ACM Int. Conf. Inf. Knowl. Manage., 2018, pp. 117–126.
[29]
X. Chen, M. Heimann, F. Vahedian, and D. Koutra, “Cone-Align: Consistent network alignment with proximity-preserving node embedding,” in Proc. 29th ACM Int. Conf. Inf. Knowl. Manage., 2020, pp. 1985–1988.
[30]
C. Riederer, Y. Kim, A. Chaintreau, N. Korula, and S. Lattanzi, “Linking users across domains with location data: Theory and validation,” in Proc. 25th Int. Conf. World Wide Web, 2016, pp. 707–719.
[31]
S. Melnik, H. Garcia-Molina, and E. Rahm, “Similarity flooding: A versatile graph matching algorithm and its application to schema matching,” in Proc. 18th Int. Conf. Data Eng., 2002, pp. 117–128.
[32]
P. Buneman and S. Staworko, “Rdf graph alignment with bisimulation,” in Proc. Int. Conf. Very Large Databases, 2016, pp. 1149–1160.
[33]
S. Zhang and H. Tong, “Final: Fast attributed network alignment,” in Proc. 22nd ACM SIGKDD Int. Conf. Knowl. Discov. Data Mining, 2016, pp. 1345–1354.
[34]
L. Wiskott, N. Krüger, N. Kuiger, and C. Von DerMalsburg, “Face recognition by elastic bunch graph matching,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 19, no. 7, pp. 775–779, Jul. 1997.
[35]
F. Zhou, J. Brandt, and Z. Lin, “Exemplar-based graph matching for robust facial landmark localization,” in Proc. IEEE Int. Conf. Comput. Vis., 2013, pp. 1025–1032.
[36]
B. R. Conroy and P. J. Ramadge, “The grouped two-sided orthogonal procrustes problem,” in Proc. IEEE Int. Conf. Acoust., Speech Signal Process., 2011, pp. 3688–3691.
[37]
P. Besl and H. McKay, “A method for registration of 3-D shapes,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 14, no. 2, pp. 239–256, Feb. 1992.
[38]
P. H. Schönemann, “A generalized solution of the orthogonal procrustes problem,” Psychometrika, vol. 31, no. 1, pp. 1–10, Mar. 1966.
[39]
W. Kabsch, “A solution for the best rotation to relate two sets of vectors,” Acta Crystallographica Sect. A, vol. 32, no. 5, pp. 922–923, Sep. 1976.
[40]
B. Sabata and J. Aggarwal, “Estimation of motion from a pair of range images: A review,” CVGIP: Image Understanding, vol. 54, no. 3, pp. 309–324, 1991. [Online]. Available: http://www.sciencedirect.com/science/article/pii/104996609190032K
[41]
D. Eggert, A. Lorusso, and R. Fisher, “Estimating 3-D rigid body transformations: A comparison of four major algorithms,” Mach. Vis. Appl., vol. 9, no. 5, pp. 272–290, Mar. 1997.
[42]
A.-L. Barabási and R. Albert, “Emergence of scaling in random networks,” Science, vol. 286, no. 5439, pp. 509–512, 1999. [Online]. Available: http://science.sciencemag.org/content/286/5439/509
[43]
E. N. Gilbert, “Random graphs,” Ann. Math. Statist., vol. 30, no. 4, pp. 1141–1144, Dec. 1959.
[44]
J. Dall and M. Christensen, “Random geometric graphs,” Phys. Rev. E, vol. 66, Jul 2002, Art. no.
[45]
R. B. Ellis, J. L. Martin, and C. Yan, “Random geometric graph diameter in the unit ball,” Algorithmica, vol. 47, no. 4, pp. 421–438, 2007.
[46]
D. Funke et al., “Communication-free massively distributed graph generation,” J. Parallel Distrib. Comput., vol. 131, pp. 200–217, 2019.
[47]
A. M. Khan, D. F. Gleich, A. Pothen, and M. Halappanavar, “A multithreaded algorithm for network alignment via approximate matching,” in Proc. Int. Conf. High Perform. Comput., Netw., Storage Anal., 2012, pp. 64:1–64:11.
[48]
D. C. V. Essen, S. M. Smith, D. M. Barch, T. E. Behrens, E. Yacoub, and K. Ugurbil, “The WU-minn human connectome project: An overview,” NeuroImage, vol. 80, pp. 62–79, 2013.
[49]
S. M. Smith et al., “Resting-state fMRI in the human connectome project,” NeuroImage, vol. 80, pp. 144–168, 2013.
[50]
M. Jenkinson, P. Bannister, M. Brady, and S. Smith, “Improved optimization for the robust and accurate linear registration and motion correction of brain images,” NeuroImage, vol. 17, no. 2, pp. 825–841, 2002.
[51]
S. M. Smith, “Fast robust automated brain extraction,” Hum. Brain Mapping, vol. 17, no. 3, pp. 143–155, Nov. 2002.
[52]
R. Lissitz, P. Schönemann, and J. Lingoes, “A solution to the weighted procrustes problem in which the transformation is in agreement with the loss function,” Psychometrika, vol. 41, no. 4, pp. 547–550, 1976.
[53]
A. Mooijaart and J. Commandeur, “A general solution of the weighted orthonormal procrustes problem,” Psychometrika, vol. 55, no. 4, pp. 657–663, 1990.
Recommendations
Comparability Graphs Among Cover-Incomparability Graphs
Algorithms and Discrete Applied MathematicsAbstractComparability graphs and cover-incomparability graphs (C-I graphs) are two interesting classes of graphs from posets. Comparability graph of a poset is a graph with vertex set V and two vertices u and v are adjacent in V if u and v are ...
Collapsible graphs and Hamiltonian connectedness of line graphs
Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics-an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, ...
Equimatchable Graphs on Surfaces
A graph G is equimatchable if each matching in G is a subset of a maximum-size matching and it is factor critical if G-v has a perfect matching for each vertex v of G. It is known that any 2-connected equimatchable graph is either bipartite or factor ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
1041-4347 © 2022 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See https://www.ieee.org/publications/rights/index.html for more information.
Publisher
IEEE Educational Activities Department
United States
Publication History
Published: 01 August 2023
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 02 Mar 2025