A0741
Title: Graph matching between bipartite and unipartite networks
Authors: Jesus Arroyo - Texas A&M University (United States) [presenting]
Carey Priebe - Johns Hopkins University (United States)
Vince Lyzinski - University of Maryland, College Park (United States)
Abstract: Graph matching is the problem of aligning the vertices of two unlabeled graphs in order to maximize the shared structure across the networks; when the graphs are unipartite, this is commonly formulated as minimizing their edge disagreements. The common setting in which one of the graphs matches is a bipartite network and one is unipartite is addressed. Commonly, the bipartite networks are collapsed or projected into a unipartite graph, which potentially leads to noisy edge estimates and loss of information. A novel formulation of the graph matching problem between a bipartite and a unipartite graph is introduced, as well as methods to find the alignment. Theoretical performance is studied, providing non-asymptotic conditions that ensure the exact recovery of the matching solution. The method is illustrated in simulations and real networks, including a co-authorship-citation network pair, and brain structural and functional data.
