Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2026; Woodstock, NY ISBN: 978-1-4503-XXXX-X/18/06
Sicong Che, Jiayi Yang, Sarfraz Khurshid, Wenxi Wang · 2026
Read Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2026; Woodstock, NY ISBN: 978-1-4503-XXXX-X/18/06 by Sicong Che, Jiayi Yang, Sarfraz Khurshid, Wenxi Wang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-00044.txt.
Introduction
Che's team builds a property-driven test method for graph neural networks, whose power on basic graph traits stays open. Using the Alloy spec language, they build two dataset groups. GraphRandom holds graphs that meet or break chosen traits. GraphPerturb adds set shape changes. Together they total hundreds of sets, each with at least ten thousand tagged graphs, across sixteen traits. Their pooling study finds attention-based pooling best for breadth and robustness, second-order pooling best for sensitivity, and no single approach best across all traits.
Catalog record
| CREATOR | Sicong Che, Jiayi Yang, Sarfraz Khurshid, Wenxi Wang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 45906 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.00044
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Property-Driven Evaluation of GNN Expressiveness at Scale: Datasets, Framework, and Study DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2026; Woodstock, NY ISBN: 978-1-4503-XXXX-X/18/06 Sicong Che, Jiayi Yang, Sarfraz Khurshid, Wenxi Wang Abstract . Advancing trustworthy AI requires principled approaches to model evaluation. Graph Neural Networks (GNNs) excel at processing graph-structured data; however, their expressiveness, particularly in capturing fundamental graph properties, remains an open challenge. We address this by developing a property-driven evaluation methodology grounded in rigorous benchmarking using formal specification, systematic evaluation, and empirical study. Leveraging Alloy, a widely used 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 graph structural variations to stress-test models. Together, these benchmarks encompass 352 datasets, each with at least 10,000 labeled graphs, covering 16 fundamental graph properties critical to both theoretical and real-world domains such as distributed systems, knowledge graphs, and biological networks. Building on these datasets, we propose a general evaluation framework that assesses three key aspects (generalizability, sensitivity, and robustness) and introduces two new quantitative metrics. Leveraging this framework, we conduct the first study on the impact of global pooling methods on GNN expressiveness. Our findings provide critical insights into how pooling strategies influence graph-level representation learning, highlighting fundamental limitations of existing pooling strategies and opening several research directions. By embedding formal specification rigor into AI evaluation, this work establishes a principled foundation for developing GNN architectures that combine expressive power with reliability across a wide range of real-world applications. 1. Introduction Graph Neural Networks (GNNs) ( 42 ; 51 ) excel at processing graph-structured data, driving advancements in diverse applications such as social network analysis ( 18 ; 36 ) , molecular chemistry ( 47 ; 14 ) , recommendation systems ( 11 ; 41 ) , and knowledge graphs ( 10 ) . The expressiveness of GNNs has been extensively studied ( 33 ; 27 ; 38 ) , with the Weisfeiler-Lehman (WL) test ( 40 ) commonly used to assess a model’s ability to distinguish graph structures. More recently, Zhang et al. ( 48 ) proposed a new perspective by systematically evaluating GNN expressiveness through the lens of a specific graph property, biconnectivity , and introduced evaluation metrics beyond the WL hierarchy to quantify expressive power. While their work provides a valuable framework, it is limited in scope: it focuses solely on a single property and lacks generality for evaluating expressiveness across a broader range of graph properties. To address the limitation, we evaluate GNN expressiveness across 16 fundamental graph properties, as shown in Table 1 . We classified the 16 properties into three groups: basic properties, function-related properties, and combined properties, defined as follows. • Basic properties : define fundamental constraints on directed relationships within graphs, governing self-loops, mutual edges, and pairwise connectivity. They include antisymmetry , connex , reflexivity , irreflexivity , and transitivity . • Function-related properties : describe how graph nodes map to one another, analogous to mathematical functions. They include function , functionality , injectivity , surjectivity , and bijectivity . • Combined properties : emerge from combining basic properties, forming well-known structures such as equivalence and orders. They include equivalence , partial order , preorder , strict order , non-strict order , and total order . Table 1 . Definitions of 16 graph properties. Property Conceptual Definition Base Size Antisymmetry No two distinct nodes in the graph have edges in both directions between them. 5 Connex For any two different nodes u and v , either there is an edge from u to v or an edge from v to u (or both). 6 Reflexivity Every node in the graph has a self-loop. 5 Irreflexivity No node in the graph has a self-loop. 5 Transitivity If for all nodes u , v , w , whenever there are edges u \rightarrow v and v \rightarrow w , there is an edge u \rightarrow w . 6 Function Each node has exactly one outgoing edge. 8 Functionality Each node has at most one outgoing edge. 8 Injectivity No two distinct nodes have edges directed to the same node. 8 Surjectivity Each node has at least one incoming edge. 14 Bijectivity Each node has exactly one incoming and one outgoing edge. 14 Equivalence The graph is reflexive, symmetric, and transitive. 20 Partial order The graph is reflexive, antisymmetric, and transitive. 6 Preorder The graph is reflexive and transitive. 7 Strict order The graph is irreflexive and transitive. 7 Non-strict order The graph is reflexive, antisymmetric, and transitive. 7 Total order The graph is reflexive, antisymmetric, transitive, and connex. 13 Beyond the theoretical significance of these 16 properties, they play a crucial role in real-world applications across various domains. For instance, total order ensures consistency and coordination in distributed systems ( 19 ) , while antisymmetry is fundamental in knowledge bases ( 13 ; 24 ) . Reflexivity models self-regulating genes in gene regulatory networks, playing a key role in homeostasis and environmental response ( 34 ) . Similarly, transitivity helps analyze group interactions in real-world hypergraphs, providing insights into social network dynamics ( 17 ) . Moreover, a tournament graph, in which every pair of distinct nodes is connected by exactly one directed edge, inherently satisfies the connex property ( 26 ) . Given the foundational importance of these properties and their widespread real-world applications, it is crucial for GNNs to exhibit strong expressive power in capturing them. To evaluate GNN expressiveness in this context, we first aim to construct comprehensive datasets covering these 16 fundamental graph properties . The goal is to efficiently generate class-balanced graphs that either satisfy (positive samples) or violate (negative samples) a given property. A straightforward approach is to randomly generate graphs and filter them using a property checker. However, this method is highly inefficient, as positive samples often represent a tiny portion of the graph space (e.g., for the total order property with graph size 13, the proportion of positive graph samples is only 2.07\times 10^{-47} ). To address this challenge, we leverage Alloy ( 15 ) , which serves as both a lightweight software specification language and an Analyzer. Based on relational logic, Alloy specification language maps naturally to graph structures, enabling concise encoding of diverse graph properties. The Alloy Analyzer supports bounded, exhaustive enumeration of graphs that either satisfy or violate the specified property, eliminating the need for post-generation filtering or checking. Building on these capabilities, we transform Alloy into a flexible, reproducible graph dataset generator tailored for evaluating GNN expressiveness. As a result, we apply our Alloy-based graph generator to produce two dataset families, GraphRandom and GraphPerturb . GraphRandom comprises 176 datasets across 16 graph properties. Each dataset includes positive samples (graphs satisfying the property) and an equal number of randomly generated negative samples (graphs that do not), spanning 11 different graph sizes per property. GraphPerturb builds on GraphRandom by introducing datasets in which each positive sample is paired with a structurally similar negative counterpart that differs by only one or two edges. As a result, GraphPerturb contains 176 datasets ,