From One to All: Learning to Match Heterogeneous and Partially Overlapped Graphs

Weijie Liu, Hui Qian, Chao Zhang, Jiahao Xie, Zebang Shen, Nenggan Zheng

Abstract

Recent years have witnessed a flurry of research activity in graph matching, which aims at finding the correspondence of nodes across two graphs and lies at the heart of many artificial intelligence applications. However, matching heterogeneous graphs with partial overlap remains a challenging problem in real-world applications. This paper proposes the first practical learning-to-match method to meet this challenge. The proposed unsupervised method adopts a novel partial OT paradigm to learn a transport plan and node embeddings simultaneously. In a from-one-to-all manner, the entire learning procedure is decomposed into a series of easy-to-solve sub-procedures, each of which only handles the alignment of a single type of nodes. A mechanism for searching the transport mass is also proposed. Experimental results demonstrate that the proposed method outperforms state-of-the-art graph matching methods.

Introduction

Graph matching—finding the correspondence between nodes in two different graphs—is essential for tasks such as social network alignment, knowledge graph integration, and biological network analysis. Despite its importance, most existing algorithms struggle with two common real-world characteristics: heterogeneity and partial overlap.

Heterogeneity refers to graphs containing multiple types of nodes (e.g., actors, directors, and films in a movie database). Standard methods often fail by matching nodes of different types. Partial overlap occurs when Graph A is not a perfect mirror of Graph B, meaning some nodes lack a counterpart. Existing solutions are often computationally expensive or require extensive manual feature engineering. This paper introduces FOTA (From One To All), the first practical unsupervised method designed to address both challenges simultaneously.

Methods

FOTA employs a "seed-and-extend" logic combined with global searching via Optimal Transport (OT). Its core innovation lies in decomposing the complex matching task into a sequence of simpler sub-problems based on node types.

Overview of the FOTA matching paradigm

The methodology consists of several key components:

  • Model Decomposition: Instead of matching the entire graph at once, FOTA matches one node type at a time. The results from one type serve as "seeds" to facilitate the matching of subsequent types.
  • Partial Optimal Transport: The model simultaneously learns a transport plan and node embeddings. It utilizes a Partial Gromov-Wasserstein (GW) discrepancy to align the internal structures of the graphs, even when they reside in different mathematical spaces.
  • Recursive Line Search: To handle partial overlap, FOTA includes a novel mechanism that automatically estimates the overlap ratio. By finding the "turning point" where matching costs increase sharply, it identifies the optimal transport mass.
  • Global Topology: High-order proximity (multi-hop connections) is incorporated into node embeddings to ensure local matches remain consistent with the global network structure.

Datasets

The performance of FOTA was evaluated using both homogeneous and heterogeneous benchmarks. Homogeneous datasets included Arenas Email, PPI Yeast, and Arxiv co-author networks. Heterogeneous datasets included Movie (actors, directors, etc.), PubMed (genes, diseases, etc.), and DBLP (authors, papers, etc.).

Statistics of homogeneous datasets

Experiments were conducted across various overlap ratios ($\rho = 1.0, 0.8, 0.6$) to simulate different levels of real-world complexity.

Key Results and Insights

FOTA demonstrates significant improvements over state-of-the-art baselines like REGAL, GWL, and SANA. On graphs with only 60% overlap ($\rho=0.6$), FOTA improved F1 scores by at least 7.7% and precision by 12.5% compared to the next best method.

A critical advantage of FOTA is its zero type mismatch rate. While baseline methods often matched different node types (up to 60% mismatch in some cases), FOTA’s design inherently prevents such errors. Furthermore, the simultaneous learning of embeddings and matching plans creates a virtuous cycle where improvements in one lead to refinements in the other. Computationally, FOTA achieves a complexity of approximately $O(V^2)$, making it far more scalable than previous $O(V^5)$ approaches for heterogeneous matching.

Conclusion

FOTA provides a robust, unsupervised framework for matching complex, partially overlapped heterogeneous graphs. By treating type constraints as a feature rather than a limitation, it significantly reduces the search space and improves accuracy. Future research may extend this work to attributed graphs using Graph Neural Networks (GNNs) and explore the impact of node-type sequencing on matching performance.

Summary updated

Abstract

Recent years have witnessed a flurry of research activity in graph matching, which aims at finding the correspondence of nodes across two graphs and lies at the heart of many artificial intelligence applications. However, matching heterogeneous graphs with partial overlap remains a challenging problem in real-world applications. This paper proposes the first practical learning-to-match method to meet this challenge. The proposed unsupervised method adopts a novel partial OT paradigm to learn a transport plan and node embeddings simultaneously. In a from-one-to-all manner, the entire learning procedure is decomposed into a series of easy-to-solve sub-procedures, each of which only handles the alignment of a single type of nodes. A mechanism for searching the transport mass is also proposed. Experimental results demonstrate that the proposed method outperforms state-of-the-art graph matching methods.
BibTeX
@inproceedings{liu2022from,
  author = {Weijie Liu and Hui Qian and Chao Zhang and Jiahao Xie and Zebang Shen and Nenggan Zheng},
  title = {{From One to All: Learning to Match Heterogeneous and Partially Overlapped Graphs}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20329},
}
Figure