CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignment
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
| Notation | Description |
|---|---|
| The source and target graphs | |
| The sizes of the nodes and edges | |
| Adjacency matrix, node feature matrix ( ) | |
| Nodes with and | |
| Embeddings computed by GNN, GNN w/o training, and feature propagation, respectively ( ) | |
| Intra-graph and inter-graph costs for GW learning |
| Dataset | Features | Anchors | ||
|---|---|---|---|---|
| Douban [ 25 ] | ||||
| ACM-DBLP [ 69 ] | ||||
| Allmovie-Imdb [ 14 ] | ||||
| 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 |
| 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 |
| 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 |
| 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 |
| 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% |
| dataset | S3GA-RCF | CombAlign |
|---|---|---|
| EN-FR | 71.77 (879 secs) | 72.98 (903 secs) |
| EN-DE | 71.93 (412 secs) | 73.51 (427 secs) |
Graph Matching
Graph matching finds correspondences between nodes and edges to compare, align, or locate related structures in graphs.
See all 40 papers