Edge-Girth for Graph Neural Networks
Edge-Girth as a Structural Edge Feature for Graph Neural Networks
EGAGNN outperforms cycle-counting methods using fewer parameters, offering a more efficient approach for graph regression tasks.
The EGAGNN model uses edge-girth as a structural descriptor for graph neural networks.
It achieves a test MAE three times lower than the closest gated comparator on the ZINC-12k regression benchmark at 104k parameters.
The edge-girth descriptor reports cycles of arbitrary length through a single breadth-first search per edge.On the BREC benchmark, the model cannot distinguish any of the 90 pairs where edges see identical cycle counts.
Edge-Girth as a Structural Edge Feature for Graph Neural Networks
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.
This report is categorized under AITOP's "Papers" desk. Key entities and technical topics under continuous tracking include graph neural networks, 1-WL, ZINC-12k.
Source attribution: curated from arXiv cs.LG (@Lilian Marey, Charlotte Laclau).