Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question

• URL: http://arxiv.org/abs/2002.01648v3
• Date: Mon, 12 Apr 2021 17:35:52 GMT
• Title: Graph matching between bipartite and unipartite networks: to collapse, or not to collapse, that is the question
• Authors: Jes\'us Arroyo, Carey E. Priebe, Vince Lyzinski
• Abstract summary: We address the common setting in which one of the graphs to match is a bipartite network and one is unipartite. We formulate the graph matching problem between a bipartite and a unipartite graph using an undirected graphical model. We show how our methods can result in a more accurate matching than the naive approach of transforming the bipartite networks into unipartite.
• Score: 13.625395368083641
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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, 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.

Related papers

• You Only Transfer What You Share: Intersection-Induced Graph Transfer Learning for Link Prediction [79.15394378571132]
  We investigate a previously overlooked phenomenon: in many cases, a densely connected, complementary graph can be found for the original graph. The denser graph may share nodes with the original graph, which offers a natural bridge for transferring selective, meaningful knowledge. We identify this setting as Graph Intersection-induced Transfer Learning (GITL), which is motivated by practical applications in e-commerce or academic co-authorship predictions.
  arXiv  Detail & Related papers  (2023-02-27T22:56:06Z)
• SynGraphy: Succinct Summarisation of Large Networks via Small Synthetic Representative Graphs [4.550112751061436]
  We describe SynGraphy, a method for visually summarising the structure of large network datasets. It works by drawing smaller graphs generated to have similar structural properties to the input graphs.
  arXiv  Detail & Related papers  (2023-02-15T16:00:15Z)
• GrannGAN: Graph annotation generative adversarial networks [72.66289932625742]
  We consider the problem of modelling high-dimensional distributions and generating new examples of data with complex relational feature structure coherent with a graph skeleton. The model we propose tackles the problem of generating the data features constrained by the specific graph structure of each data point by splitting the task into two phases. In the first it models the distribution of features associated with the nodes of the given graph, in the second it complements the edge features conditionally on the node features.
  arXiv  Detail & Related papers  (2022-12-01T11:49:07Z)
• Learning Universe Model for Partial Matching Networks over Multiple Graphs [78.85255014094223]
  We develop a universe matching scheme for partial matching of two or multiple graphs. The subtle logic for inlier matching and outlier detection can be clearly modeled. This is the first deep learning network that can cope with two-graph matching, multiple-graph matching, online matching, and mixture graph matching simultaneously.
  arXiv  Detail & Related papers  (2022-10-19T08:34:00Z)
• CGMN: A Contrastive Graph Matching Network for Self-Supervised Graph Similarity Learning [65.1042892570989]
  We propose a contrastive graph matching network (CGMN) for self-supervised graph similarity learning. We employ two strategies, namely cross-view interaction and cross-graph interaction, for effective node representation learning. We transform node representations into graph-level representations via pooling operations for graph similarity computation.
  arXiv  Detail & Related papers  (2022-05-30T13:20:26Z)
• Sparse Partial Least Squares for Coarse Noisy Graph Alignment [10.172041234280865]
  Graph signal processing (GSP) provides a powerful framework for analyzing signals arising in a variety of domains. We propose a novel regularized partial least squares method which both incorporates the observed graph structures and imposes sparsity in order to reflect the underlying block community structure.
  arXiv  Detail & Related papers  (2021-04-06T21:52:15Z)
• Spectral Embedding of Graph Networks [76.27138343125985]
  We introduce an unsupervised graph embedding that trades off local node similarity and connectivity, and global structure. The embedding is based on a generalized graph Laplacian, whose eigenvectors compactly capture both network structure and neighborhood proximity in a single representation.
  arXiv  Detail & Related papers  (2020-09-30T04:59:10Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.