Edge-Girth as a Structural Edge Feature for Graph Neural Networks

Graph neural networks (GNNs) are fundamentally limited by the 1-WL Weisfeiler-Leman test, meaning they cannot distinguish between certain non-isomorphic graphs regardless of their depth or width. To overcome this, researchers often augment node or edge features with structural descriptors like subgraph counts. However, these methods typically require choosing a fixed motif size in advance, which is often done blindly and can lead to suboptimal performance if the chosen size does not match the data's informative structures. The authors propose a new, unbounded structural descriptor: the edge-girth (the length of the shortest cycle containing an edge) and its multiplicity (the number of such shortest cycles). This pair is computed via a single breadth-first search per edge, providing a per-edge invariant that captures cycle information without a predefined size limit.

The authors introduce EGAGNN, a gated message-passing architecture that incorporates these edge-girth features. On the ZINC-12k molecular regression benchmark, EGAGNN significantly outperforms gated comparators, achieving a test mean absolute error (MAE) three times lower than the closest baseline at a matched parameter budget. In a controlled study, the authors demonstrate that while bounded cycle-counting dictionaries can eventually match this performance, they require a specific, large-enough motif size to be effective; dictionaries capped at length four provide no improvement over baseline, whereas the unbounded edge-girth descriptor succeeds without such tuning.

This work highlights the limitations of "blind" structural augmentation in GNNs. By using a descriptor that naturally adapts to the graph's cycle structure rather than relying on a fixed motif budget, the authors provide a more flexible and robust way to enhance GNN expressivity. While the authors prove that their method remains limited on specific "edge-girth-regular" graph families, the approach offers a practical, computationally efficient, and task-agnostic way to improve performance on molecular datasets where cycle structure is a key determinant of properties.