aiqbench analysis
This research introduces the edge-girth descriptor, a structural invariant for graph neural networks that dynamically captures cycles of arbitrary length without predefining subgraph sizes. By integrating this feature into a gated message-passing architecture, the proposed EGAGNN model significantly outperforms standard cycle-counting baselines on molecular property regression benchmarks while maintaining theoretical bounds consistent with the Weisfeiler-Leman test. The work advances GNN expressivity by offering a data-adaptive method to encode topological complexity more efficiently than fixed-window counting approaches.
Edge-Girth as a Structural Edge Feature for Graph Neural Networks
arXiv:2609.01441v1 Announce Type: new Abstract: Graph neural networks (GNN) based on message passing are provably no more powerful than the one-dimensional Weisfeiler--Leman colour-refinement test (1-WL): two graphs it cannot tell apart receive identical representations, however deep or wide the network. A common remedy augments node or edge features with precomputed structural descriptors, most often counts of a fixed small subgraph such as triangles or longer cycles, but such counts require committing in advance to the size of the substructure counted, a choice usually made blind to the data. We study a descriptor that avoids this choice. The edge-girth of an edge is the length of a shortest cycle through it, and its multiplicity is the number of such shortest cycles; together they form a per-edge invariant that reports cycles of arbitrary length, computable exactly by a single breadth-first search per edge. Injected into a gated message-passing architecture, EGAGNN, it reaches a test MAE a factor three below the closest gated comparator on the ZINC-12k regression benchmark at 104k parameters; against bounded cycle-counting descriptors under the same architecture, it matches only a dictionary counting cycles up to length eight, using twice as many channels, while a dictionary capped at length four performs no better than no structural information at all. On graph discrimination we prove a matching limitation: on graphs where every edge sees the same number of shortest cycles of the same length, the descriptor becomes constant and any model built on it collapses back to the 1-WL bound. This holds without exception across all 400 pairs of the BREC benchmark: not one of the 90 such pairs is distinguished.
Abstract:Graph neural networks (GNN) based on message passing are provably no more powerful than the one-dimensional Weisfeiler--Leman colour-refinement test (1-WL): two graphs it cannot tell apart receive identical representations, however deep or wide the network. A common remedy augments node or edge features with precomputed structural descriptors, most often counts of a fixed small subgraph such as triangles or longer cycles, but such counts require committing in advance to the size of the substructure counted, a choice usually made blind to the data. We study a descriptor that avoids this choice. The edge-girth of an edge is the length of a shortest cycle through it, and its multiplicity is the number of such shortest cycles; together they form a per-edge invariant that reports cycles of arbitrary length, computable exactly by a single breadth-first search per edge. Injected into a gated message-passing architecture, EGAGNN, it reaches a test MAE a factor three below the closest gated comparator on the ZINC-12k regression benchmark at 104k parameters; against bounded cycle-counting descriptors under the same architecture, it matches only a dictionary counting cycles up to length eight, using twice as many channels, while a dictionary capped at length four performs no better than no structural information at all. On graph discrimination we prove a matching limitation: on graphs where every edge sees the same number of shortest cycles of the same length, the descriptor becomes constant and any model built on it collapses back to the 1-WL bound. This holds without exception across all 400 pairs of the BREC benchmark: not one of the 90 such pairs is distinguished.
Machine Learning (cs.LG)
arXiv:2609.01441 [cs.LG]
(or arXiv:2609.01441v1 [cs.LG] for this version)
https://doi.org/10.48550/arXiv.2609.01441 Focus to learn more arXiv-issued DOI via DataCite (pending registration)
arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.
Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.
Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.
Full text under the publisher's open licence · 359 words
Related coverage
Topology-Aware Gaussian Graph Repair for Robust Graph Neural Networks
arXiv · Jun 3, 2026
Reachability-Based Formal Verification of Graph Neural Networks with Node and Edge Features
arXiv · Sep 26, 2026
Subgraph Filtering for Fair Graph Neural Networks
arXiv · Aug 28, 2026
Mesh Graph Neural Network Framework for Accelerating Finite Element Simulation for Arbitrary Geometries
arXiv · Jun 9, 2026