Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study

• URL: http://arxiv.org/abs/2603.00044v1
• Date: Mon, 09 Feb 2026 07:19:25 GMT
• Title: Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study
• Abstract summary: Graph Neural Networks (GNNs) have achieved remarkable success in processing graph-structured data.<n>We develop a property-driven evaluation methodology grounded in formal specification, systematic evaluation, and empirical study.<n>We conduct the first comprehensive study on global pooling methods' impact on GNN expressiveness.
• Score: 4.596496450055493
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Advancing trustworthy AI requires principled software engineering approaches to model evaluation. Graph Neural Networks (GNNs) have achieved remarkable success in processing graph-structured data, however, their expressiveness in capturing fundamental graph properties remains an open challenge. We address this by developing a property-driven evaluation methodology grounded in formal specification, systematic evaluation, and empirical study. Leveraging Alloy, a software specification language and analyzer, we introduce a configurable graph dataset generator that produces two dataset families: GraphRandom, containing diverse graphs that either satisfy or violate specific properties, and GraphPerturb, introducing controlled structural variations. Together, these benchmarks encompass 336 new datasets, each with at least 10,000 labeled graphs, covering 16 fundamental graph properties critical to distributed systems, knowledge graphs, and biological networks. We propose a general evaluation framework that assesses three key aspects of GNN expressiveness: generalizability, sensitivity, and robustness, with two novel quantitative metrics. Using this framework, we conduct the first comprehensive study on global pooling methods' impact on GNN expressiveness. Our findings reveal distinct trade-offs: attention-based pooling excels in generalization and robustness, while second-order pooling provides superior sensitivity, but no single approach consistently performs well across all properties. These insights highlight fundamental limitations and open research directions including adaptive property-aware pooling, scale-sensitive architectures, and robustness-oriented training. By embedding software engineering rigor into AI evaluation, this work establishes a principled foundation for developing expressive and reliable GNN architectures.

Related papers

• On the Potential of Graph Neural Networks as Metamodels for Supply Chain Optimization: Dataset, Architectures, and Directions [0.0]
  Graph Neural Networks (GNNs) have emerged as a powerful, differentiable class of learning models forstructured systems.<n>This paper lays the foundation, presents initial steps, and discusses key research directions.
  arXiv  Detail & Related papers  (2026-07-18T11:06:22Z)
• A Unified Benchmark for Evaluating Knowledge Graph Construction Methods and Graph Neural Networks [1.9307742024764771]
  We introduce a dual-purpose benchmark designed to jointly evaluate the performance of Graph Neural Networks (GNNs) on noisy, text-derived graphs.<n>The benchmark is built in the biomedical domain from a single textual corpus.
  arXiv  Detail & Related papers  (2026-05-06T21:53:49Z)
• GNNs for Time Series Anomaly Detection: An Open-Source Framework and a Critical Evaluation [0.0]
  We present an open-source framework for graph-based Time Series Anomaly Detection (TSAD) using Graph Neural Networks (GNNs)<n>This work contributes both practical tools and critical insights to advance the development and evaluation of graph-based TSAD systems.
  arXiv  Detail & Related papers  (2026-03-10T13:45:34Z)
• The Underappreciated Power of Vision Models for Graph Structural Understanding [28.781392309798672]
  Graph Neural Networks operate through bottom-up message-passing, fundamentally differing from human visual perception.<n>We investigate the underappreciated potential of vision models for graph understanding, finding they achieve performance comparable to GNNs on established benchmarks.
  arXiv  Detail & Related papers  (2025-10-27T05:11:44Z)
• GraphUniverse: Enabling Systematic Evaluation of Inductive Generalization [8.95975918626961]
  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.
  arXiv  Detail & Related papers  (2025-09-25T12:46:01Z)
• Graph Foundation Models: A Comprehensive Survey [66.74249119139661]
  Graph Foundation Models (GFMs) aim to bring scalable, general-purpose intelligence to structured data.<n>This survey provides a comprehensive overview of GFMs, unifying diverse efforts under a modular framework.<n>GFMs are poised to become foundational infrastructure for open-ended reasoning over structured data.
  arXiv  Detail & Related papers  (2025-05-21T05:08:00Z)
• G-OSR: A Comprehensive Benchmark for Graph Open-Set Recognition [54.45837774534411]
  We introduce textbfG-OSR, a benchmark for evaluating Graph Open-Set Recognition (GOSR) methods at both the node and graph levels.<n>Results offer critical insights into the generalizability and limitations of current GOSR methods.
  arXiv  Detail & Related papers  (2025-03-01T13:02:47Z)
• 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)
• Learning to Model Graph Structural Information on MLPs via Graph Structure Self-Contrasting [50.181824673039436]
  We propose a Graph Structure Self-Contrasting (GSSC) framework that learns graph structural information without message passing. The proposed framework is based purely on Multi-Layer Perceptrons (MLPs), where the structural information is only implicitly incorporated as prior knowledge. It first applies structural sparsification to remove potentially uninformative or noisy edges in the neighborhood, and then performs structural self-contrasting in the sparsified neighborhood to learn robust node representations.
  arXiv  Detail & Related papers  (2024-09-09T12:56:02Z)
• Massive Activations in Graph Neural Networks: Decoding Attention for Domain-Dependent Interpretability [0.9499648210774584]
  We show the emergence of Massive Activations (MAs) within attention layers in edge-featured Graph Neural Networks (GNNs)<n>Our study assesses various edge-featured attention-based GNN models using benchmark datasets, including ZINC, TOX21, and PROTEINS.
  arXiv  Detail & Related papers  (2024-09-05T12:19:07Z)
• 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)
• Graph Information Bottleneck [77.21967740646784]
  Graph Neural Networks (GNNs) provide an expressive way to fuse information from network structure and node features. Inheriting from the general Information Bottleneck (IB), GIB aims to learn the minimal sufficient representation for a given task. We show that our proposed models are more robust than state-of-the-art graph defense models.
  arXiv  Detail & Related papers  (2020-10-24T07:13:00Z)

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.