Towards Effective and Efficient Graph Alignment without Supervision

• URL: http://arxiv.org/abs/2603.08526v1
• Date: Mon, 09 Mar 2026 16:00:08 GMT
• Title: Towards Effective and Efficient Graph Alignment without Supervision
• Abstract summary: Unsupervised graph alignment aims to find the node correspondence across different graphs without any anchor node pairs.<n>By focusing on the exploitation of local and global graph information, we formalize them as the local representation, global alignment'' paradigm.<n>We present a new global representation and alignment'' paradigm to resolve the mismatch between the two phases in the alignment process.
• Score: 28.31247120989485
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 \underline{Gl}obal representation and \underline{o}ptimal transport-\underline{b}ased \underline{Align}ment (\texttt{GlobAlign}), and its variant, \texttt{GlobAlign-E}, for better \underline{E}fficiency. 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, \texttt{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, \texttt{GlobAlign-E} achieves the best efficiency, with an order of magnitude speedup against existing OT-based methods.

Related papers

• CoRe-GNN: Multilevel Message passing on Coarsened graphs [13.325673513204377]
  Training Graph Neural Networks on large graphs is challenged by the memory cost of node representations across layers.<n>We show that several existing scalable approaches can be written as structured modifications of the GNN propagation matrix.<n>In particular, graph coarsening replaces it by a lowrank approximation that enables spectral guarantees but assigns uniform representations to nodes.
  arXiv  Detail & Related papers  (2026-08-03T12:18:58Z)
• Towards Pre-trained Graph Condensation via Optimal Transport [52.6504753271008]
  Graph condensation aims to distill the original graph into a small-scale graph, mitigating redundancy and accelerating GNN training.<n> conventional GC approaches heavily rely on rigid GNNs and task-specific supervision.<n>Pre-trained Graph Condensation (PreGC) via optimal transport is proposed to transcend the limitations of task- and architecture-dependent GC methods.
  arXiv  Detail & Related papers  (2025-09-18T08:13:24Z)
• LOBSTUR: A Local Bootstrap Framework for Tuning Unsupervised Representations in Graph Neural Networks [0.9208007322096533]
  Graph Neural Networks (GNNs) are increasingly used in conjunction with unsupervised learning techniques to learn powerful node representations.<n>We propose a novel framework designed to adapt bootstrapping techniques for unsupervised graph representation learning.
  arXiv  Detail & Related papers  (2025-05-20T19:59:35Z)
• Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics [59.07903030446756]
  Graph neural networks are highly vulnerable to distribution shifts on graphs.<n>We present Gadget, the first framework for non-IID graph data.<n> Gadget can be seamlessly integrated with existing graph DA methods to handle large shifts on graphs.
  arXiv  Detail & Related papers  (2025-05-19T05:03:58Z)
• Joint Optimal Transport and Embedding for Network Alignment [66.49765320358361]
  We propose a joint optimal transport and embedding framework for network alignment named JOENA.<n>With a unified objective, the mutual benefits of both methods can be achieved by an alternating optimization schema with guaranteed convergence.<n>Experiments on real-world networks validate the effectiveness and scalability of JOENA, achieving up to 16% improvement in MRR and 20x speedup.
  arXiv  Detail & Related papers  (2025-02-26T17:28:08Z)
• Decentralized Federated Learning with Gradient Tracking over Time-Varying Directed Networks [42.92231921732718]
  We propose a consensus-based algorithm called DSGTm-TV. It incorporates gradient tracking and heavy-ball momentum to optimize a global objective function. Under DSGTm-TV, agents will update local model parameters and gradient estimates using information exchange with neighboring agents.
  arXiv  Detail & Related papers  (2024-09-25T06:23:16Z)
• Efficient and Scalable Graph Generation through Iterative Local Expansion [26.843529744867222]
  We introduce a method that generates a graph by progressively expanding a single node to a target graph. In each step, nodes and edges are added in a localized manner through denoising diffusion, building first the global structure, and then refining the local details. Our model achieves state-of-the-art performance on well-established benchmark datasets while successfully scaling to graphs with at least 5000 nodes.
  arXiv  Detail & Related papers  (2023-12-14T10:42:42Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Robust Attributed Graph Alignment via Joint Structure Learning and Optimal Transport [26.58964162799207]
  We propose SLOTAlign, an unsupervised graph alignment framework that jointly performs Structure Learning and Optimal Transport Alignment. We incorporate multi-view structure learning to enhance graph representation power and reduce the effect of structure and feature inconsistency inherited across graphs. The proposed SLOTAlign shows superior performance and strongest robustness over seven unsupervised graph alignment methods and five specialized KG alignment methods.
  arXiv  Detail & Related papers  (2023-01-30T08:41:36Z)
• Mixed Graph Contrastive Network for Semi-Supervised Node Classification [63.924129159538076]
  We propose a novel graph contrastive learning method, termed Mixed Graph Contrastive Network (MGCN)<n>In our method, we improve the discriminative capability of the latent embeddings by an unperturbed augmentation strategy and a correlation reduction mechanism.<n>By combining the two settings, we extract rich supervision information from both the abundant nodes and the rare yet valuable labeled nodes for discriminative representation learning.
  arXiv  Detail & Related papers  (2022-06-06T14:26:34Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• A Regularized Wasserstein Framework for Graph Kernels [32.558913310384476]
  We propose a learning framework for graph kernels grounded on regularizing optimal transport. This framework provides a novel optimal transport distance metric, namely Regularized Wasserstein (RW) discrepancy. We have empirically validated our method using 12 datasets against 16 state-of-the-art baselines.
  arXiv  Detail & Related papers  (2021-10-06T07:54:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.