CS Paper Radar

Revisiting the Generalization of Neural Graph Edit Distance Models

Zhouyang Liu, Ning Liu, Yixin Chen, Jiezhong He, Dongsheng Li

cs.LG ·submitted 2026-10-03 16:35 UTC · v1

Abstract

Neural approaches to Graph Edit Distance (GED) have achieved strong results under standard within-dataset evaluation, but much less is known about how well these models transfer across graph collections. We conduct a systematic study of this problem using exact GED supervision across diverse graph datasets and a broad set of representative learning-based methods. Our results reveal a pronounced gap between within-collection performance and cross-collection transfer. Models that perform well on their training collections often lose this advantage when evaluated on structurally different data. Training on multiple source collections substantially improves zero-shot transfer and provides a better starting point when limited supervision is available for a new target collection. Further analysis shows that transfer behavior varies with the source--target direction and the structural characteristics of the collections involved. These findings suggest that conventional within-collection evaluation provides only a partial view of the generalization behavior of neural GED models and motivate broader evaluation across heterogeneous graph collections.

Closest papers

Nearest neighbours by meaning across the whole index.

ReCoG: Relative Node Contexts for Multi-Domain Graph Pre-training

cs.LG ·2026-11-01 ·Yupeng Tong, Lianze Shan, Jitao Zhao, Dongxiao He
similarity 0.64
Abstract · 13 pages, 7 figures, 8 tables

The success of foundation models in language and vision has motivated Graph Foundation Models (GFMs), which learn transferable knowledge through multi-domain graph pre-training. Existing methods advance GFMs through feature unification and structural learning, and in doing so they rely on the raw graph structure to organize node contexts. However, we observe that removing a large proportion of edges from source graphs during pre-training improves cross-domain transfer accuracy across four representative methods. Our theoretical analysis identifies the raw graph structure as a source of conflict in cross-graph model sharing. We therefore advocate defining node contexts using criteria consistent across graphs. Achieving this requires (1) constructing node contexts consistently across graphs without a shared positional structure, such as the token order of text or the pixel grid of images, and (2) retaining the structural and neighborhood information of the original graphs. To this end, we introduce Relative Contexts for Graphs (ReCoG) for multi-domain graph pre-training. Specifically, we first construct attribute contexts to provide a comparison rule independent of the raw graph structure. Furthermore, we construct structural contexts based on common neighbors and semantic contexts based on neighborhood attribute summaries to retain the topological and neighborhood information of the original graphs. Since all graphs share these construction rules, we pre-train a single graph encoder by reconstructing node attributes over these contexts, without domain-specific modules. We conduct extensive experiments on 18 target datasets, which demonstrate the effectiveness of ReCoG. In particular, ReCoG exceeds the strongest baseline by 7.61 percentage points in mean 1-shot cross-domain node classification accuracy and by 4.47 points in cross-type transfer to heterophilous graphs.

0.13

Hierarchical Response Preservation for Continual Adaptation of Zero-Shot Graph-Text Models

cs.LG ·2026-09-27 ·Haopeng Zhang, Yuhan Wang, Yubing Su, Yingxin Chen, Xiao Wang +2 more
similarity 0.63
Abstract · Preprint

Pretrained graph-text models align graph representations with textual semantics, enabling recognition of unseen classes and transfer across graph domains. However, as graph data and classes continually arrive, models should learn from new supervision while retaining their zero-shot transfer capabilities and historical task knowledge. Two challenges arise: (i) new classes can overturn historical predictions despite preserved distinctions among historical classes, and (ii) overly strict response preservation can stall learning of new classes. To address these challenges, we propose Hierarchical Response Preservation (HiRP). HiRP represents this competition through a hierarchical response that keeps each historical-class probability and sums new-class probabilities, preserving historical distinctions and aggregate competition while allowing distinctions within the new class group to adapt. It further uses the geometry induced by this response to guide constrained updates, retaining useful adaptation directions while controlling response drift. Across three class-incremental settings, HiRP achieves absolute gains of 1.84-7.95 percentage points in average accuracy over the strongest compared baseline in each setting, while mitigating zero-shot transfer degradation.

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.63
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

Graph Domain Adaptation Does Not End with Representation Learning

cs.LG ·2026-09-22 ·Ziqian Liu, Yongxue Xu, Enze Zhang, Jiaqi Zhang, Hao Wang +1 more
similarity 0.62
Abstract

Graph domain adaptation (GDA) transfers knowledge from a labeled source graph to an unlabeled target graph under shifts in both node attributes and graph structure. Existing methods primarily adapt graph representations through propagation redesign, distribution alignment, or source-to-target transition modeling, but still rely on a single graph-propagating path for target prediction. This leaves open whether an adapted graph representation exhausts the predictive evidence available in the target domain, since the graph-aware expert and graph-free local expert may exhibit different failure modes under topological shifts. To address this limitation, we propose EviGDA, an Evidence-Augmented Graph Domain Adaptation framework that complements graph representation adaptation with a graph-free local expert. The graph-aware expert performs message passing and entropy-aware marginal alignment, while the graph-free local expert learns solely from source node features and labels without graph propagation or target alignment. The two experts are optimized independently and combined only at inference through a task-level constant probability mixture, preserving complementary evidence without joint training, learned routing, or target pseudo-labels. Extensive experiments on ten datasets and 16 transfer tasks show that EviGDA outperforms state-of-the-art baselines. Complementary prediction paths add value beyond graph representation alignment.

0.14

Scaling Graph Similarity Learning with Graph Neural Networks

cs.LG cs.AI ·2026-11-06 ·Ahmet Tüzen, Helge Langseth, Kjetil Nørvåg
benchmark similarity 0.60
Abstract

Graph similarity computation is an important task in graph mining with many real-world applications, such as chemical compound analysis, program dependence comparison, and social network analysis. The problem is computationally challenging: Graph Edit Distance (GED) and Maximum Common Subgraph (MCS), which quantify the distance between graphs and identify their largest shared subgraph, respectively, are NP-hard to compute exactly. To address these computational challenges, Graph Neural Networks (GNNs) have been applied to this problem. However, existing GNN-based approaches have primarily focused on small-scale graph datasets, while scalability to larger scales remains underexplored. In this work, we propose FiLSim, a scalable GNN-based framework, and investigate whether a simplified GNN pipeline can maintain competitive performance on standard benchmarks while scaling to large graphs. We additionally propose a sequential graph-editing strategy to construct large-scale graph datasets with reliable GED labels to evaluate scalability. The proposed framework is evaluated on four benchmark datasets and four newly created large-scale datasets, demonstrating its effectiveness and scalability. FiLSim remains accurate on graphs with more than 150{,}000 nodes, where the baseline methods run out of memory or fail to learn, and scores all test pairs within seconds on a single GPU.

0.25

Learning a Prior-Data Fitted Network for Graph Foundation Models via Structural Causal Model Priors

cs.LG ·2026-10-28 ·Ziwei Zhang, Tianyin Liao, Chunyu Hu, Ge Lan, Nuo Xu +5 more
similarity 0.59
Abstract

Graph Foundation Models (GFMs) have recently emerged as a promising paradigm for learning transferable representations across different graphs and domains. However, existing GFMs face notable limitations, including limited pre-training scale or reliance on aligning with textual information in Large Language Models (LLMs). To overcome these limitations, recent studies have drawn inspiration from prior-data fitted networks (PFNs), which learn from large synthetic datasets and support multi-domain prediction backed by causal learning. However, existing graph PFNs encounter severe difficulties in modeling causal relationships within and across node and edge sets, generating diverse graph structures, and designing suitable architectures that can learn from complex synthetic datasets. To address these challenges, we propose **GSCM-PFN** (Graph SCM-based Prior-Data Fitted Network), a graph PFN pre-trained on synthetic data generated from an SCM-based prior that jointly models nodes and graph topology. Specifically, we (1) design a joint feature-edge-label structural causal model (SCM) to guide synthetic graph generation and capture causal relationships within and across node and edge sets; (2) introduce prior-guided node-edge dependency modeling to instantiate diverse graph generation strategies, and prove that our SCM-based generation prior is more expressive than existing priors; and (3) propose a feature-permutation-invariant dual-path graph network with theoretical guarantees for learning from diverse synthetic graphs. Experiments on 23 real-world benchmarks show that GSCM-PFN outperforms both conventional GFMs and PFN-based GFMs, without utilizing real-world graph data for pre-training. Code: https://anonymous.4open.science/r/GSCM-PFN-A3A3/

0.19

The Universal Classifier for Graph Learning

cs.LG ·2026-09-28 ·Ben Finkelshtein, André Linhares, Petar Veličković, Bryan Perozzi, Mikhail Galkin
similarity 0.59
Abstract

While foundation models have revolutionized natural language processing and computer vision by leveraging universal vocabularies, Graph Machine Learning (GML) remains fractured due to the absence of a unified feature and structural representation across diverse domains. Existing works claiming to be Graph Foundation Models (GFMs) are typically restricted to node-level predictions or require fixed feature dimensions, failing to provide a truly task-agnostic backbone for the full spectrum of graph learning applications. In this paper, we introduce the Universal Classifier (UC), which supports arbitrary feature and class cardinalities, unifying node-, edge-, and graph-level objectives under a single similarity-based classification objective. The UC reformulates all node-, edge-, and graph-level prediction tasks as maximizing similarity in the latent space: by lifting heterogeneous features and labels into 3D latent tensors, the model learns transferable features independent of specific input schemas. This architecture allows a single pre-trained model to generalize to node classification, node regression, and link prediction across unseen graphs with varying feature semantics. Experiments show strong zero-shot transfer performance across node-, link-, and graph-level tasks.

0.31

MAGE: Meta-path Adaptive Graph Evidence for Transferable Multimodal Graph Learning

cs.IR ·2026-11-16 ·Haiyang Jiang, Tong Chen, Xinyi Gao, Hao Wang, Hongzhi Yin
similarity 0.59
Abstract

Multimodal graphs integrate textual and visual attributes with relational structures, providing a rich representation of complex real-world data. To enable the broad applicability and reuse of graph models, it is crucial for models trained on source graphs to generalize to unseen graph domains. However, this is challenging because cross-modal interactions among neighbors and the neighboring information needed for prediction can vary across target nodes and graph domains. This gives rise to two key challenges: adaptive cross-modal neighborhood fusion, which captures and integrates cross-modal interactions among neighbors to accommodate variations across nodes and domains; and target-specific evidence selection, which identifies the neighboring textual and visual information needed for each target node to support LLM-based prediction. In light of these challenges, we propose MAGE (Meta-path Adaptive Graph Evidence Prompting), a framework for transferable multimodal graph learning. MAGE represents textual and visual node views separately in a heterogeneous graph and introduces two complementary components. Meta-path Adaptive Multimodal Propagation (MAMP) adaptively aggregates neighborhood information along heterogeneous meta-paths and compresses it into graph-aware soft tokens. Evidence-Guided Instruction Tuning (EGIT) selects relevant neighboring evidence for each query and incorporates its graph-aware representations into instructions for a frozen multimodal LLM. Together, these components support transfer from multiple source graphs to unseen target graphs without target-domain parameter updates. Experiments with three source graphs and four unseen target graphs demonstrate strong cross-domain transfer performance on node classification and link prediction, without requiring parameter updates on the target domains.

0.06