论文标题
两分和单分部网络之间的图形匹配：要崩溃或不崩溃，这就是问题
Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question
论文作者
论文摘要
图形匹配包括对齐两个未标记图的顶点，以最大程度地跨网络共享结构；当图形是单分数时，通常将其表达为最小化其边缘分歧。在本文中，我们介绍了一个共同的设置，其中一个图形匹配的是二分网络，一个是单分明确的。通常，双方网络被折叠或投影到一个单面图中，并且图形匹配的过程如经典设置一样。这可能导致嘈杂的边缘估计和信息丢失。我们使用非方向的图形模型在两部分和单分部分图之间制定图形匹配问题，并介绍方法以在不崩溃的情况下找到与此模型对齐的方法。从理论上讲，我们证明了我们的方法是一致的，并提供了非肌电条件，以确保匹配解决方案的精确恢复。在模拟和真实的数据示例中，我们展示了与将双分部分网络转换为单一方面的天真方法相比，我们的方法如何导致更准确的匹配，并且我们证明了我们的方法在模拟和真实数据网络中获得的性能提高，包括共同创作引文网络对以及大脑结构和功能数据。
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, and we demonstrate the performance gains achieved by our method in simulated and real data networks, including a co-authorship-citation network pair, and brain structural and functional data.
