cs.LGJun 19, 2024

CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment

Authors: Songyang Chen, Yu Liu, Lei Zou, Zexuan Wang, Youfang Lin

Organizations: School of Computer and Information Technology, Beijing Jiaotong University, Beijing 100044, China · Beijing Key Laboratory of Traffic Data Analysis and Mining, Beijing 100044, China · Peking University, Beijing 100871, China

Abstract

Unsupervised graph alignment finds the node correspondence between a pair of attributed graphs by only exploiting graph structure and node features. One category of recent studies first computes the node representation and then matches nodes with the largest embedding-based similarity, while the other category reduces the problem to optimal transport (OT) via Gromov-Wasserstein learning. However, it remains largely unexplored in the model expressiveness, as well as how theoretical expressivity impacts prediction accuracy. We investigate the model expressiveness from two aspects. First, we characterize the model's discriminative power in distinguishing matched and unmatched node pairs across two graphs. Second, we study the model's capability of guaranteeing node matching properties such as one-to-one matching and mutual alignment. Motivated by our theoretical analysis, we put forward a hybrid approach named CombAlign with stronger expressive power. Specifically, we enable cross-dimensional feature interaction for OT-based learning and propose an embedding-based method inspired by the Weisfeiler-Lehman test. We also apply non-uniform marginals obtained from the embedding-based modules to OT as priors for more expressiveness. Based on that, we propose a traditional algorithm-based refinement, which combines our OT and embedding-based predictions using the ensemble learning strategy and reduces the problem to maximum weight matching. With carefully designed edge weights, we ensure these matching properties and further enhance prediction accuracy. By extensive experiments, we demonstrate a significant improvement of 14.5% in alignment accuracy compared to state-of-the-art approaches and confirm the soundness of our theoretical analysis.

Figures & tables

Explore similar work

CardsList
  1. Towards Effective and Efficient Graph Alignment without Supervision

    Mar 9, 2026Songyang Chen, Youfang Lin, Yu Liu +2Graph MatchingGraph Representation Learning

  2. Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

    Aug 30, 2026Lutz Oettershagen, Honglian Wang, Aristides GionisGraph MatchingHypergraph Learning

  3. Chaining 2-FWL GNNs for Combinatorial Graph Alignment

    Oct 3, 2025Marc LelargeGraph MatchingHigher-Order GNNs