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
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
Fig. 1 : Illustration of model expressiveness for graph alignment, where (a) denotes the model’s capability of separating matched and unmatched node pairs, while (b) & (c) showcase two disadvantages of pure learning-based approaches, i.e., one-to-many prediction regardless of the one-to-one matching constraint, and the inconsistency between row and column-wise alignment.
Notation
Description
Gs,Gt
The source and target graphs
n,m
The sizes of the nodes and edges
Ap,Xp
Adjacency matrix, node feature matrix ( p=s,t )
ui,uj,vk,vl
Nodes with ui,uj∈Gs and vk,vl∈Gt
Zp,Hp,Rp
Embeddings computed by GNN, GNN w/o training, and feature propagation, respectively ( p=s,t )
Cs,Ct,Cgwd
Intra-graph and inter-graph costs for GW learning
TABLE I : Table of notations.
Fig. 2 : The overall framework of CombAlign . Modules in orange, green, and purple belong to the embedding-based, OT-based, and traditional algorithm-based approaches, respectively.
Fig. 3 : Illustration of the necessity of non-uniform marginals.
Fig. 4 : Percentage of one-to-many predictions and inconsistencies in terms of mutual alignment for representative baselines.
Dataset
n1,n2
m1,m2
Features
Anchors
Douban [ 25 ]
1,118
3,022
538
1,118
3,906
16,328
ACM-DBLP [ 69 ]
9,872
39,561
17
6,325
9,916
44,808
Allmovie-Imdb [ 14 ]
6,011
124,709
14
5,174
5,713
119,073
TABLE III : Datasets and their statistics.
Datasets
Metrics
KNN
GAlign
WAlign
GTCAlign
GWL
SLOTAlign
UHOT-GM
HLOT
CombAlign w/o C
Douban
Hits@1
27.82
45.26
39.45
61.79
3.29
51.43
60.23
57.26
68.52
Hits@5
45.53
67.71
62.35
76.83
8.32
73.43
71.36
79.77
87.84
Hits@10
52.68
78.00
71.47
82.29
9.93
77.73
76.91
84.09
91.41
MAP
36.08
56.32
46.22
69.77
5.79
61.29
67.35
63.45
77.08
ACM-DBLP
Hits@1
36.35
70.20
63.43
60.92
56.36
66.04
69.89
65.86
72.18
Hits@5
66.83
87.23
83.18
75.60
77.09
85.84
87.12
84.74
88.98
TABLE IV : Comparison of model performance on six datasets.
Datasets
Douban
ACM-DBLP
Allmovie-Imdb
KNN
23.88
31.11
28.79
MJV
31.03
56.89
35.14
GAlign
20.84
66.18
80.28
WAlign
15.56
60.33
51.29
GTCAlign
57.15
56.96
83.91
GWL
3.22
52.09
87.22
TABLE V : Comparison of Hits@1 with one-to-one matching constraint.
Hits@1
Douban
ACM-DBLP
Allmovie-Imdb
w/ LGCN
57.07
68.87
93.39
w/ GCN
61.45
69.68
94.57
w/ GIN
63.15
71.64
95.61
w/ SGFormer
65.38
72.73
96.02
TABLE VI : The performance (Hits@1) of GRAFT with different GNNs.
Fig. 5 : Ablation study on three real-world datasets.
Fig. 6 : Running time vs. Hits@1 of different methods.
Methods
Douban
ACM-DBLP
Allmovie-Imdb
GWL
3.29
56.36
87.82
GWL+C
5.81
63.46
90.07
SLOTAlign
51.43
66.04
90.60
SLOTAlign+C
60.01
69.20
91.03
UHOT-GM
60.23
69.89
91.73
UHOT-GM+C
63.17
71.32
92.45
TABLE VII : Improving other OT-based models w/ Combine (Hits@1).
CombAlign
Douban
ACM-DBLP
Allmovie-Imdb
- w/ C
100%
100%
100%
- w/o C
94.36%
88.36%
98.54%
- w/o C+NUM
94.18%
86.50%
97.60%
- w/o C+NUM+FT
91.32%
83.27%
96.25%
TABLE VIII : The ratio of the remaining set over ground truth after eliminating one-to-many predictions.
Fig. 7 : Further Evaluation. (a) Convergence. (b) Runtime of CombAlign (Opt) vs. graph size. (c) and (d) represent the sensitivity analysis.
dataset
S3GA-RCF
CombAlign
EN-FR
71.77 (879 secs)
72.98 (903 secs)
EN-DE
71.93 (412 secs)
73.51 (427 secs)
TABLE IX: Comparison of Hits@1 on the datasets with 1 million nodes.
Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs. Despite the recent efforts utilizing deep learning-based techniques, such as the embedding and optimal transport (OT)-based approaches, we observe their limitations in terms of model accuracy-efficiency tradeoff. By focusing on the exploitation of local and global graph information, we formalize them as the local representation, global alignment'' paradigm, and present a new global representation and alignment'' paradigm to resolve the mismatch between the two phases in the alignment process. We then propose Global representation and optimal transport-based Alignment (GlobAlign), and its variant, GlobAlign-E, for better Efficiency. Our methods are equipped with the global attention mechanism and a hierarchical cross-graph transport cost, able to capture long-range and implicit node dependencies beyond the local graph structure. Furthermore, GlobAlign-E successfully closes the time complexity gap between representative embedding and OT-based methods, reducing OT's cubic complexity to quadratic terms. Through extensive experiments, our methods demonstrate superior performance, with up to a 20% accuracy improvement over the best competitor. Meanwhile, GlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.
We study unsupervised hypergraph alignment, where the goal is to infer node correspondences between two hypergraphs using only structural information, without node features, labels, seed matches, or side information. Direct higher-order formulations can represent hyperedge interactions faithfully, but they can be computationally demanding and cumbersome for non-uniform hypergraphs. Graph-reduction approaches introduce a different challenge: clique expansions keep the alignment problem on the original node set but collapse all hyperedge evidence into one pairwise graph, whereas bipartite expansions preserve incidence structure but enlarge the problem from nodes to nodes plus hyperedges. We introduce FALCON (Filtration-based hypergrAph aLignment via Cross-scale Optimal traNsport), an unsupervised optimal-transport framework for hypergraph alignment. Instead of representing each hypergraph by a single collapsed clique graph, FALCON constructs a filtration-induced sequence of clique-based co-occurrence dissimilarity matrices and jointly aligns all levels through one shared multi-scale Gromov--Wasserstein (GW) objective. The shared transport plan enforces a globally consistent node correspondence across filtration levels while avoiding the auxiliary hyperedge nodes introduced by bipartite expansion. Experiments on perturbation benchmarks derived from real-world hypergraphs show that FALCON is robust to structural noise and in almost all cases outperforms strong graph- and hypergraph-alignment baselines.
For the combinatorial graph alignment problem (GAP), finding the node correspondence that maximizes the number of common edges (nce) between two unlabeled graphs, the classical Frank-Wolfe heuristic FAQ remains a strong baseline once it is properly initialized, while existing GNN approaches struggle in the purely structural setting. We introduce a chaining procedure: a sequence of Folklore-type (2-FWL) GNNs in which each network is trained with cross-entropy after decoding the previous network's similarity matrix and ranking nodes by their current alignment quality. This non-differentiable ranking step injects discrete combinatorial feedback at every stage; at inference, we iterate the final network and keep the candidate with highest observed nce. On sparse Erdos-Renyi graphs at noise level 0.25, chained FGNNs used to initialize FAQ reach 85% accuracy versus 13% for FAQ initialized from the convex relaxation, and essentially 0% for prior GNN methods. On correlated regular graphs, where MPNNs with constant features produce identical node embeddings (1-WL fails to refine) and FAQ's convex initialization is degenerate, chaining is the only method among those we evaluate, including Gromov-Wasserstein solvers, that recovers a non-trivial alignment. On three real-world benchmarks (yeast PPI, coauthorship, and road networks), recent comparisons underestimate FAQ by initializing it from a uniform doubly stochastic matrix; initialized from the convex relaxation it already surpasses prior reported numbers, and dataset-specific chained FGNNs further improve on this strengthened baseline. Code and pretrained chains available at: https://github.com/mlelarge/chaining-gnn-graph-alignment.
Marc Lelarge
INRIA - Ecole Normale Supérieure PSL Research University