CS Paper Radar

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

Federico Méndez, Paul Krzakala, Gabriel Melo, Charlotte Laclau, Rémi Flamary, Florence d'Alché-Buc

cs.LG stat.ML ·submitted 2026-09-14 12:00 UTC · v2

Abstract

End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings. Such losses typically involve a costly graph-matching problem. We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP. Then, to avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem. For each training sample, the loss function leverages a transport plan provided by a parametric matcher based on the differentiable Sinkhorn algorithm applied on empirical node distributions. The graph prediction module and the matcher are jointly learned. We showcase the efficiency of this approach on toy and real world SGP problems of increasing complexity including a novel Mass-spectra to Scaffold task that we introduce.

Closest papers

Nearest neighbours by meaning across the whole index.

Optimal Transport for Network Comparison: A Unified Review with New Spectral Bounds and Machine Learning Applications

cs.LG stat.MLcs.SI ·2026-08-27 ·James Hyun, François G. Meyer
theory similarity 0.66
Abstract

Network comparison using optimal transport is a growing area of research in network science. Unlike standard graph metrics, optimal transport computes both network dissimilarity and a transport plan that explains how one graph morphs into another. In this paper, we review how optimal transport compares undirected, unweighted simple graphs using three primary distances: the Wasserstein, Gromov-Wasserstein, and Bures-Wasserstein distances. We examine the closed form of the Wasserstein distance in one dimension via node feature probability distributions, and show how the transport plans of the Wasserstein and Gromov-Wasserstein distances visualize how mass is shifted to transform one network into another. Beyond reviewing existing transport-based approaches, we establish new spectral lower and upper bounds for the Bures-Wasserstein distance and characterize the tightness of the lower bound under eigenbasis perturbations. Finally, we evaluate these distances using a synthetic network dataset for clustering and a real-world temporal network.

0.17

Alignment Matters Inside and Out in Equivariant Graph Flow Matching

cs.LG math.OCstat.ML ·2026-08-27 ·Moritz Piening, Christian Wald
similarity 0.65
Abstract · Gromov-Wasserstein, Optimal Transport, Flow Matching, Graph Generation, Equivariant Networks

Graphs are invariant under node permutations, motivating permutation-equivariant architectures in generative models. In flow matching, however, symmetry also affects the source-target coupling: one must choose both which graphs to pair and which node representatives to align. We study these two forms of alignment, termed outer and inner alignment, and their effect on equivariant graph flow matching. We connect inner alignment to transport on the graph quotient space, whose Euclidean quotient metric coincides with Gromov-Monge distance, and show that quotient couplings admit aligned representative lifts while symmetrization yields equivariant flow-matching minimizers, including for categorical endpoints. In practice, we compare random augmentation, permutation-blind minibatch optimal transport, approximate Gromov-Wasserstein alignment, and combinations of inner and outer alignment. Across continuous graph and molecular generation, alignment can substantially simplify trajectories and improve few-step generation, while its benefits depend on the alignment and computational budget. Our results highlight that effective graph flow matching benefits from alignment both inside and across graph pairs.

0.37

Unsupervised Multi-Scale Gromov-Wasserstein Hypergraph Alignment

cs.LG cs.SI ·2026-08-30 ·Lutz Oettershagen, Honglian Wang, Aristides Gionis
top venue similarity 0.65
Abstract · Accepted at ICDM 2026

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.

0.43

Efficient Graph Generation via Direct Prediction and Flow Matching

cs.LG ·2026-10-04 ·Susie Lu
published similarity 0.65
Abstract · NeurIPS 2026 Workshop on Geometric Distributional Deep Learning (Oral)

Generative modeling of graph-structured data is crucial for tasks ranging from drug discovery to social network simulation. Among these models, denoising diffusion models have achieved great success in graph generation by learning to progressively reverse a process that adds noise to the original graph. However, the standard noise-prediction approach of diffusion models is suboptimal for graph data. The goal for a graph generative model is to learn the clean graphs' topological properties, such as connectivity and degree distribution. Because a diffusion model that predicts noise does not explicitly learn these topological properties, it is challenging for the model to output graphs with the desired structural statistics. To address this challenge, we introduce Direct Graph Flow Matching (DiGFM), a novel graph transformer model guided by two goals: predict clean graphs and improve sampling efficiency. Distinct from the prevailing diffusion approach, DiGFM employs a continuous flow-matching paradigm and integrates direct graph prediction. Specifically, DiGFM maps the prior noise distribution to the clean graph distribution via a multi-step process: the model repeatedly predicts the underlying clean graph, and a transformation is employed to convert the model output to the velocity vector that points in the direction toward the clean graph distribution. This design enables DiGFM to generate high-quality samples using only 2.5% to 15.6% of the steps required by diffusion-based models, which leads to a 5.3x to 257x speedup in wall-clock inference time. Experiments demonstrate that DiGFM outperforms or matches prior state-of-the-art models across general graph benchmarks and molecular datasets, generating graphs with strong adherence to ground-truth structural statistics at significantly faster inference speeds.

0.34

More Is Better? Exploring Latent Correspondence in Federated Hypergraph Learning

cs.LG cs.DC ·2026-10-29 ·Bo Yan, Siming Zhang, Siqi Li, Hang Yu
similarity 0.65
Abstract

Federated hypergraph learning with latent cross-client hyperedge correspondence poses fundamental identifiability and computational challenges, as the same local release can correspond to multiple global hypergraph structures. We characterize the tractability of recovering these latent correspondences, showing tractable pairwise assignment but generally intractable multi-client hyperedge matching. Building on this characterization, we derive a cross-entropy decomposition that reveals when local prediction can outperform predictors fitted with additional cross-client information. Motivated by this principle, we introduce Federated Adaptive Spectral Training with Representation Alignment (FedASTRA), which learns correspondence-invariant diffusion representations through adaptive heat diffusion and masked latent prediction while communicating model parameters only. We establish its asymptotic optimality with respect to the permitted local information and prove global population-risk convergence under explicit conditions on recovery, representation, and update alignment. Experiments on eight real-world datasets demonstrate the effectiveness of FedASTRA against identifier-free federated graph and hypergraph methods. On ogbn-papers100M, FedASTRA reaches the performance-communication Pareto frontier, achieving 50.07 Accuracy and 29.73 Macro-F1 while communicating only 59.60 MiB per round.

0.15

Equivariant Neural Primal-Dual Assignment for Maximum Common Edge Subgraphs

cs.LG ·2026-09-26 ·Jiaqing Xie, Yanchao Li, Zhuo Yang, Yuxin Wang, Tianfan Fu +1 more
theoryhot direction similarity 0.63
Abstract · 35 pages, 11 figures

Maximum common edge subgraph (MCES) matching finds a partial vertex correspondence between two labeled graphs that preserves as many labeled edges as possible. Molecular similarity search requires matching many graph pairs, making the cost of repeated queries important. The strongest baseline attains accurate MCES solutions but trains a separate network for each pair. We introduce Equivariant Neural Primal-Dual Assignment (ENPDA), which learns a shared matching policy and applies it to new pairs without further training, answering queries roughly three orders of magnitude faster and recovering its training cost after a few dozen queries. The policy recomputes exact objective marginals for candidate matches and learns corrections and step sizes that update their scores. Target prices respond to competition when several source vertices favor the same target. Four update rounds and a Hungarian projection produce a partial one-to-one matching. We prove per-pair guarantees that hold for any network parameters. In exact arithmetic, reordering either graph permutes the assignment and price states, the projected matching is one-to-one, and repaired prices give a valid MCES upper bound. Subtracting the preserved-edge count bounds the optimality gap; combined with structural caps, these certificates prove global optimality for 60 of 291 native test pairs. On three molecular benchmarks with disjoint train/validation/test splits, ENPDA improves over an analytic counterpart with the same update and projection budget by 7.4-8.6 accuracy points; after one second of refinement search, 2.5-3 points of the gain remain. Transferred without fine-tuning to edge-deletion tasks from social and protein graphs, the policy gains 9.1-17.6 points over the analytic counterpart. When output matchings must keep aromatic rings intact, ENPDA recovers more reference bonds than the baselines on all three datasets.

0.38

Distilling Graph Geometry: Knowledge Gap from GNNs to MLPs

cs.LG ·2026-10-07 ·Zhewei Chen, Hao Zhu, Jiaojiao Jiang, Ahad N. Zehmakan
similarity 0.62
Abstract

GNN-to-MLP distillation aims to retain the predictive accuracy of a message-passing teacher while deploying a graph-free MLP at inference. Existing methods mainly transfer node-wise predictions or use confidence-based reweighting, but they do not specify where the student should preserve the teacher's graph-induced geometry. We show that this omission leads to two spectral failure modes in the student's representation space. On sparse graphs, the student suffers from spectral underfit, missing high-energy teacher directions induced by aggregation. On dense graphs, it suffers from spectral overfit, retaining spurious directions that the teacher has collapsed through aggregation. Motivated by an energy-weighted teacher-student alignment objective, we propose Graph Geometry-aware MLP (G^2MLP), a training-time distillation framework guided by Ollivier-Ricci curvature. Curvature acts as a local proxy for allocating supervision between prediction-level and representation-level alignment. The deployed model is a standard MLP with no graph access at inference. Across node-classification benchmarks, G^2MLP improves over graph-free distillation baselines in most settings, reduces the teacher-student rank gap in both regimes, and transfers to Graph Transformer teachers and link prediction.

0.25

SUCRe: Selective Uncertainty-Aware Contrastive Representation for Graph Transfer Learning

cs.GR ·2026-09-25 ·Mingcan Wang, Junchang Xin, Zhongming Yao, Bing Tian Dai, Kaifu Long +1 more
similarity 0.61
Abstract

Graph transfer learning (GTL) provides a promising paradigm for adapting knowledge from source graphs with sufficient labels to label-scarce target graphs. However, existing approaches often assume that transferred knowledge is uniformly reliable, ignoring the different transferability of samples caused by structural and distribution shifts across graphs. This limitation leads to negative transfer and unnecessary computational overhead. In this work, we propose SUCRe, a selective uncertainty-aware contrastive representation method for GTL. The key idea is to selectively adapt and transfer graph knowledge according to its estimated reliability. Specifically, we introduce structure-aware entropy-based matching discrepancy, which jointly models feature uncertainty and structural coherence to ensure accurate feature adaptation between graphs. Moreover, we develop a domain-aware semi-hard negative sampling strategy that constructs informative contrastive sets by filtering unreliable cross-domain relationships, reducing computational redundancy while enhancing representation discrimination. Extensive experiments on graph transfer benchmarks demonstrate that SUCRe achieves competitive performance with improved efficiency.

0.10