Graph Matching Between Bipartite and Unipartite Networks: To Collapse or Not to Collapse, That Is the Question

• Activity Number: 210 - SLDS CSpeed 3
• Type: Contributed
• Date/Time: Tuesday, August 10, 2021 : 1:30 PM to 3:20 PM
• Sponsor: Section on Statistical Learning and Data Science
• Author(s): Jesus Arroyo Relión* and Carey E Priebe and Vince Lyzinski
• Companies: Texas A&M University, Department of Statitics and Johns Hopkins University and University of Maryland
• Keywords: graphical models; graphical lasso; bipartite network; graph matching

Abstract

Graph matching consists of aligning the vertices of two unlabeled graphs in order to maximize the shared structure across networks; when the graphs are unipartite, this is commonly formulated as minimizing their edge disagreements. In this paper we address the common setting in which one of the graphs to match is a bipartite network and one is unipartite. Commonly, the bipartite networks are collapsed or projected into a unipartite graph, and graph matching proceeds as in the classical setting. This potentially leads to noisy edge estimates and loss of information. We formulate the graph matching problem between a bipartite and a unipartite graph using an undirected graphical model, and introduce methods to find the alignment with this model without collapsing. We theoretically demonstrate that our methodology is consistent, and provide non-asymptotic conditions that ensure exact recovery of the matching solution. In simulations and real data examples, we show how our methods can result in a more accurate matching than the naive approach of transforming the bipartite networks into unipartite.