2020/02/05 by Jesús Arroyo, Carey E. Priebe, Arroyo, Jesús +3 · 1 citation
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Graph Theory and Algorithms #Complex Network Analysis Techniques
paper · pdf · doi:10.48550/arxiv.2002.01648
Graph matching consists of aligning the vertices of two unlabeled graphs in\norder to maximize the shared structure across networks; when the graphs are\nunipartite, this is commonly formulated as minimizing their edge disagreements.\nIn this paper, we address the common setting in which one of the graphs to\nmatch is a bipartite network and one is unipartite. Commonly, the bipartite\nnetworks are collapsed or projected into a unipartite graph, and graph matching\nproceeds as in the classical setting. This potentially leads to noisy edge\nestimates and loss of information. We formulate the graph matching problem\nbetween a bipartite and a unipartite graph using an undirected graphical model,\nand introduce methods to find the alignment with this model without collapsing.\nWe theoretically demonstrate that our methodology is consistent, and provide\nnon-asymptotic conditions that ensure exact recovery of the matching solution.\nIn simulations and real data examples, we show how our methods can result in a\nmore accurate matching than the naive approach of transforming the bipartite\nnetworks into unipartite, and we demonstrate the performance gains achieved by\nour method in simulated and real data networks, including a\nco-authorship-citation network pair, and brain structural and functional data.\n