Partial Gromov-Wasserstein Learning for Partial Graph Matching

Weijie Liu, Chao Zhang, Jiahao Xie, Zebang Shen, Hui Qian, 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, or network alignment, is the fundamental task of identifying corresponding nodes across different graphs. This process is critical for applications such as merging databases, deanonymizing social networks, and identifying protein interactions across species. Despite its importance, real-world graph matching faces two significant hurdles: heterogeneity and partial overlap.

Heterogeneity refers to nodes having distinct types (e.g., actors vs. directors), where standard algorithms often fail by matching incompatible types. Partial overlap occurs when graphs are not perfect subsets of each other, causing "full matching" algorithms to force incorrect correspondences. This paper introduces FOTA (From One To All), the first practical unsupervised framework designed to address these challenges simultaneously without requiring ground-truth labels.

Methodology

FOTA employs a hybrid strategy that combines a "divide-and-conquer" type-matching approach with partial Optimal Transport (OT). The framework is built on four key pillars:

  1. Partial Optimal Transport: Unlike standard OT, which forces a 1-to-1 mapping for all nodes, the partial OT formulation allows the model to transport only a fraction of the mass. This effectively ignores nodes that lack a counterpart in the target graph.
  2. Model Decomposition (One-to-All Strategy): To manage complexity, FOTA decomposes the matching problem by node type. It aligns one type first, using those matches as "seeds" to recursively align subsequent types. This drastically reduces the search space and prevents type-mismatch errors.
  3. Joint Learning: The algorithm simultaneously learns node embeddings (global topological representations) and the transport plan (the matching matrix). This mutual reinforcement increases robustness against structural noise.
  4. Recursive Line Search: To handle unknown overlap ratios, FOTA utilizes a line-search mechanism to estimate the "transport mass." It identifies the "elbow point" where matching costs spike, indicating that non-overlapping nodes are being forced into matches.
Illustration of the partial graph matching process between source and target graphs, highlighting the underlying heterogeneous structure and the 'One-to-All' decomposition strategy.

Experimental Setup

The authors evaluated FOTA on both homogeneous and heterogeneous benchmarks. Homogeneous datasets included Arenas Email, PPI Yeast, and Arxiv. Heterogeneous datasets included Movie (actors, directors, etc.), PubMed (genes, diseases), and DBLP (authors, papers). To simulate real-world conditions, subgraphs were extracted with varying overlap ratios ($\rho = 1.0, 0.8, 0.6$).

Statistics for the homogeneous datasets used in the study, showing node and edge counts across different overlap ratios ($\rho$).

Key Results

FOTA demonstrated significant improvements over state-of-the-art baselines:

  • Accuracy: On partially overlapped graphs ($\rho=0.6$), FOTA improved the F1 score by 7.7% to 12.5% over the best baselines on homogeneous data.
  • Type Integrity: On heterogeneous datasets like Movie and PubMed, FOTA achieved a 0% type mismatch rate. In contrast, competing methods like SANA or GWL often mismatched between 5% and 60% of nodes.
  • Efficiency: With a complexity of $O(V^2)$, FOTA is significantly more scalable than previous heterogeneous matchers that often reached $O(V^5)$, allowing for the alignment of much larger networks.

Conclusion

FOTA represents a major step forward in unsupervised graph matching by successfully integrating type constraints and partial overlap handling. While the current work focuses on topological structure, future research could integrate node attributes (e.g., text or images) via Graph Neural Networks and explore the impact of type-ordering in the decomposition process to further enhance performance on massive, million-node networks.

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{liu2022partial,
  author = {Weijie Liu and Chao Zhang and Jiahao Xie and Zebang Shen and Hui Qian and Nenggan Zheng},
  title = {{Partial Gromov-Wasserstein Learning for Partial Graph Matching}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.1609/aaai.v36i4.20329},
}
Figure