mlsanityData to 14 Oct 2026

Towards Effective and Efficient Graph Alignment without Supervision

arXiv 2603.08526 ↗First posted 9 Mar 2026cs.LG cs.AIcited by 0

Not on the map. Why?

Abstract (arXiv)

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 underlineGlobal representation and underlineoptimal transport-underlinebased underlineAlignment (textttGlobAlign), and its variant, textttGlobAlign-E, for better underlineEfficiency. 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, textttGlobAlign-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, textttGlobAlign-E achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Builds on 24 of its 60 references that are in the map. First posted on arXiv 9 Mar 2026.

Builds on

24 of 60 references.

References · 24

  1. 2017Attention Is All You Needcited by 60,361
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2013Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distancescited by 2,316
  5. 2018Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learningcited by 1,102
  6. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  7. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  8. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  9. 2018Optimal Transport for structured data with application on graphscited by 172
  10. 2023SGFormer: Simplifying and Empowering Transformers for Large-Graph Representationscited by 133
  11. 2019Gromov-Wasserstein Learning for Graph Matching and Node Embeddingcited by 126
  12. 2019Scalable Gromov-Wasserstein Learning for Graph Partitioning and Matchingcited by 103
12 more
  1. 2023DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusioncited by 87
  2. 2018REGAL: Representation Learning-based Graph Alignmentcited by 40
  3. 2022SelfKG: Self-Supervised Entity Alignment in Knowledge Graphscited by 32
  4. 2021From Alignment to Assignment: Frustratingly Simple Unsupervised Entity Alignmentcited by 26
  5. 2021Unsupervised Knowledge Graph Alignment by Probabilistic Reasoning and Semantic Embeddingcited by 18
  6. 2022LightEA: A Scalable, Robust, and Interpretable Entity Alignment Framework via Three-view Label Propagationcited by 18
  7. 2023A Fused Gromov-Wasserstein Framework for Unsupervised Knowledge Graph Entity Alignmentcited by 16
  8. 2023Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transportcited by 15
  9. 2016Spectral Alignment of Graphscited by 12
  10. 2022Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsificationcited by 11
  11. 2022Interactive Contrastive Learning for Self-supervised Entity Alignmentcited by 7
  12. 2024CombAlign: Enhancing Model Expressiveness in Unsupervised Graph Alignmentcited by 2

Built on by

Not cited yet.