GraphUniverse: Enabling Systematic Evaluation of Inductive Generalization

• URL: http://arxiv.org/abs/2509.21097v1
• Date: Thu, 25 Sep 2025 12:46:01 GMT
• Title: GraphUniverse: Enabling Systematic Evaluation of Inductive Generalization
• Authors: Louis Van Langendonck, Guillermo Bernárdez, Nina Miolane, Pere Barlet-Ros,
• Abstract summary: GraphUniverse is a framework for generating entire families of graphs.<n>It enables the first systematic evaluation of inductive generalization at scale.<n>Our core innovation is the generation of graphs with persistent semantic communities.
• Score: 8.95975918626961
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A fundamental challenge in graph learning is understanding how models generalize to new, unseen graphs. While synthetic benchmarks offer controlled settings for analysis, existing approaches are confined to single-graph, transductive settings where models train and test on the same graph structure. Addressing this gap, we introduce GraphUniverse, a framework for generating entire families of graphs to enable the first systematic evaluation of inductive generalization at scale. Our core innovation is the generation of graphs with persistent semantic communities, ensuring conceptual consistency while allowing fine-grained control over structural properties like homophily and degree distributions. This enables crucial but underexplored robustness tests, such as performance under controlled distribution shifts. Benchmarking a wide range of architectures -- from GNNs to graph transformers and topological architectures -- reveals that strong transductive performance is a poor predictor of inductive generalization. Furthermore, we find that robustness to distribution shift is highly sensitive not only to model architecture choice but also to the initial graph regime (e.g., high vs. low homophily). Beyond benchmarking, GraphUniverse's flexibility and scalability can facilitate the development of robust and truly generalizable architectures -- including next-generation graph foundation models. An interactive demo is available at https://graphuniverse.streamlit.app.

Related papers

• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• G-reasoner: Foundation Models for Unified Reasoning over Graph-structured Knowledge [88.82814893945077]
  Large language models (LLMs) excel at complex reasoning but remain limited by static and incomplete parametric knowledge.<n>Recent graph-enhanced RAG (GraphRAG) attempts to bridge this gap by constructing tailored graphs and enabling LLMs to reason on them.<n>G-reasoner is a unified framework that integrates graph and language foundation models for reasoning over diverse graph-structured knowledge.
  arXiv  Detail & Related papers  (2025-09-29T04:38:12Z)
• Generating Directed Graphs with Dual Attention and Asymmetric Encoding [41.979242767509064]
  We propose Directo, the first generative model for directed graphs built upon the discrete flow matching framework.<n>Our approach combines principled positional encodings tailored to asymmetric pairwise relations, (ii) a dual-attention mechanism capturing both incoming and outgoing dependencies, and (iii) a robust, discrete generative framework.<n>Our results highlight the effectiveness and generality of our approach, establishing a solid foundation for future research in directed graph generation.
  arXiv  Detail & Related papers  (2025-06-19T15:35:20Z)
• Scalable Graph Generative Modeling via Substructure Sequences [50.32639806800683]
  We introduce Generative Graph Pattern Machine (G$2$PM), a generative Transformer pre-training framework for graphs.<n>G$2$PM represents graph instances (nodes, edges, or entire graphs) as sequences of substructures.<n>It employs generative pre-training over the sequences to learn generalizable and transferable representations.
  arXiv  Detail & Related papers  (2025-05-22T02:16:34Z)
• It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph [19.222317334613162]
  Graph Neural Networks (GNNs) excel at analyzing graph-structured data but struggle on heterophilic graphs, where connected nodes often belong to different classes.<n>We provide theoretical foundations linking edge homophily, GNN embedding smoothness, and node classification performance.<n>We introduce a rewiring framework that increases graph homophily using a reference graph, with theoretical guarantees on the homophily of the rewired graph.
  arXiv  Detail & Related papers  (2025-05-18T13:28:56Z)
• Towards A Universal Graph Structural Encoder [18.609281566514017]
  GFSE is a universal graph structural encoder designed to capture transferable structural patterns across diverse domains.<n>Built on a Graph Transformer, GFSE incorporates attention mechanisms informed by graph inductive bias, enabling it to encode intricate multi-level and fine-grained topological features.<n>GFSE achieves state-of-the-art performance in 81.6% evaluated cases, spanning diverse graph models and datasets.
  arXiv  Detail & Related papers  (2025-04-15T06:57:26Z)
• Revisiting Graph Neural Networks on Graph-level Tasks: Comprehensive Experiments, Analysis, and Improvements [54.006506479865344]
  We propose a unified evaluation framework for graph-level Graph Neural Networks (GNNs)<n>This framework provides a standardized setting to evaluate GNNs across diverse datasets.<n>We also propose a novel GNN model with enhanced expressivity and generalization capabilities.
  arXiv  Detail & Related papers  (2025-01-01T08:48:53Z)
• What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding [67.59552859593985]
  Graph Transformers, which incorporate self-attention and positional encoding, have emerged as a powerful architecture for various graph learning tasks. This paper introduces first theoretical investigation of a shallow Graph Transformer for semi-supervised classification.
  arXiv  Detail & Related papers  (2024-06-04T05:30:16Z)
• Fine-tuning Graph Neural Networks by Preserving Graph Generative Patterns [13.378277755978258]
  We show that the structural divergence between pre-training and downstream graphs significantly limits the transferability when using the vanilla fine-tuning strategy. We propose G-Tuning to preserve the generative patterns of downstream graphs. G-Tuning demonstrates an average improvement of 0.5% and 2.6% on in-domain and out-of-domain transfer learning experiments.
  arXiv  Detail & Related papers  (2023-12-21T05:17:10Z)
• Supercharging Graph Transformers with Advective Diffusion [28.40109111316014]
  This paper proposes Advective Diffusion Transformer (AdvDIFFormer), a physics-inspired graph Transformer model designed to address this challenge.<n>We show that AdvDIFFormer has provable capability for controlling generalization error with topological shifts.<n> Empirically, the model demonstrates superiority in various predictive tasks across information networks, molecular screening and protein interactions.
  arXiv  Detail & Related papers  (2023-10-10T08:40:47Z)
• GraphGLOW: Universal and Generalizable Structure Learning for Graph Neural Networks [72.01829954658889]
  This paper introduces the mathematical definition of this novel problem setting. We devise a general framework that coordinates a single graph-shared structure learner and multiple graph-specific GNNs. The well-trained structure learner can directly produce adaptive structures for unseen target graphs without any fine-tuning.
  arXiv  Detail & Related papers  (2023-06-20T03:33:22Z)
• Spectral Augmentations for Graph Contrastive Learning [50.149996923976836]
  Contrastive learning has emerged as a premier method for learning representations with or without supervision. Recent studies have shown its utility in graph representation learning for pre-training. We propose a set of well-motivated graph transformation operations to provide a bank of candidates when constructing augmentations for a graph contrastive objective.
  arXiv  Detail & Related papers  (2023-02-06T16:26:29Z)
• EGRC-Net: Embedding-induced Graph Refinement Clustering Network [66.44293190793294]
  We propose a novel graph clustering network called Embedding-Induced Graph Refinement Clustering Network (EGRC-Net) EGRC-Net effectively utilizes the learned embedding to adaptively refine the initial graph and enhance the clustering performance. Our proposed methods consistently outperform several state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-19T09:08:43Z)

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.