PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Lilian Marey, Charlotte Laclau

arXiv:2609.01441v1cs.LG

TL;DR

Message-passing GNNs are limited by 1-WL, while common structural descriptors require choosing a substructure size in advance. The paper introduces per-edge shortest-cycle length and multiplicity, computes them exactly by breadth-first search, and injects them into EGAGNN. EGAGNN reaches 0.0932 ± 0.0035 test MAE on Zinc-12k at approximately 100k parameters, but its descriptor collapses to the 1-WL bound on edge-girth-regular graphs.

  • Problem

    MPNNs are bounded by 1-WL, and fixed-size subgraph descriptors require committing to a motif-size limit before observing the data.

  • Method

    The paper uses per-edge shortest-cycle length and shortest-cycle multiplicity, computed exactly by one breadth-first search per edge and consumed by the gated EGAGNN architecture.

  • Results

    0.0932 ± 0.0035 test MAE is achieved on Zinc-12k at approximately 100k parameters, a factor three below the closest gated comparator; the descriptor also matches only a length-eight cycle dictionary under controlled comparison.

  • Takeaways & Limitations

    Edge-girth provides useful unbounded cycle information for the reported molecular regression task without selecting a maximum cycle length in advance.

  • Takeaways & Limitations

    The descriptor is constant on edge-girth-regular graphs, so models built on it revert to the 1-WL bound; supervised evidence comes from one regression target on one dataset, and transfer remains untested.

Abstract

from arXiv · show

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.

1 Introduction

The paper introduces edge-girth and shortest-cycle multiplicity as an unbounded, exactly computable per-edge descriptor, then injects it into gated message passing. EGAGNN improves Zinc-12k regression while retaining a provable 1-WL limitation on edge-girth-regular graphs.

  • Motivation: MPNNs are bounded by 1-WL, while fixed-size subgraph descriptors require choosing a motif-size limit in advance.The paper motivates a descriptor that avoids this data-independent size choice.
  • Contribution: The pair (g_e, λ_e) records each edge’s shortest-cycle length and the number of shortest cycles through it, without a cycle-length ceiling.It is attached per edge and can represent cycles of arbitrary length.
  • Contribution: EGAGNN gates messages using edge features and lets edge states absorb endpoint context, diffusing edge-girth information beyond immediate neighborhoods.The architecture consumes the descriptor locally rather than treating it as a graph-level signature.
  • Results: 0.0932 ± 0.0035 test MAE is achieved by EGAGNN on Zinc-12k at approximately 100k parameters, with a factor-three improvement over the closest gated comparator.The comparison is reported at matched capacity, and a depth-matched comparator addresses nonlinear depth as an alternative explanation.
  • Results: A six-channel dictionary counting cycles through length eight matches the three-channel edge-girth descriptor, whereas dictionaries capped at length four are worthless on this data.The descriptor-versus-descriptor comparison holds architecture and chemical inputs fixed.
  • Limitations: On edge-girth-regular graphs, the descriptor is constant and models built on it revert to the 1-WL bound; none of 90 such BREC pairs is resolved.The result covers 90 edge-girth-regular pairs among the 400 BREC pairs.

2 Edge-Girth as a Structural Edge Invariant

Edge-girth and multiplicity form an isomorphism-invariant per-edge descriptor computed exactly by one breadth-first search per edge. Its local use avoids the weaknesses of a graph-level edge-girth sequence, while computation trades speed for exactness and no size ceiling.

  • Definition: For each edge, edge-girth is the shortest cycle length containing it, while multiplicity counts distinct cycles of that shortest length; bridges have infinite edge-girth.The pair is invariant under graph isomorphism and has no prescribed substructure-size bound.
  • Definition: The example distinguishes bridges, triangle edges, and square edges, while multiplicity counts shortest cycles rather than all cycles.An edge lying on both a triangle and a square receives edge-girth three, not four.
  • Limitations: The edge-girth sequence is a weak graph signature because vertex identification preserves it and identical sequences can occur on graphs with different numbers of vertices.Nine edge-girth values equal to three occur for both a five-vertex and a seven-vertex graph.
  • Use in message passing: The descriptor is therefore attached to edges and injected into message passing rather than used as a graph-level sequence.This local treatment supports regression while avoiding reliance on the sequence as a complete graph signature.
  • Computation: A breadth-first search from one endpoint with the edge removed returns the shortest replacement path and its multiplicity, yielding edge-girth and λ_e exactly.Unreachable endpoints give infinite edge-girth, and no approximation or truncation is involved.
  • Computation: O(|E|(|V| + |E|)) per graph is the descriptor’s traversal cost, with the ranking against bounded motif counting depending on graph family.Molecular graphs favor the traversal in the reported measurements, while sparse low-degree graphs with long cycles can favor bounded enumeration.

3 EGAGNN

EGAGNN encodes normalized edge-girth, shortest-cycle multiplicity, and a bridge indicator, then uses these features to gate message passing. Edge states incorporate endpoint context across layers while raw structural features remain available.

  • 3.1 Edge Feature Initialization: Bridges receive a placeholder pair plus an explicit indicator, while non-bridge edge-girth and multiplicity values are normalized using training-split statistics.The structural triple is combined with any dataset edge attributes, such as molecular bond types.
  • 3.1 Edge Feature Initialization: Both edge-girth entries are computed by one breadth-first search per edge, stopping at shortest cycles rather than counting cycles to a prescribed length.Counting cycles up to a fixed length is tractable but corresponds to a bounded cycle dictionary; unrestricted prescribed-length counting is harder.
  • 3.2 Gated Message Passing: Structural edge information enters multiplicatively through learned per-channel gates, allowing edges on different cycle-length regimes to open different message channels.The sigmoid gate is formed from edge and node states and uses a Hadamard product.
  • 3.2 Gated Message Passing: Residual aggregation updates node states from gated messages, while edge states are updated by an MLP using endpoint representations.The edge update makes the architecture more than static feature augmentation.
  • 3.2 Gated Message Passing: After ℓ layers, a gate can depend on edge-girth values within ℓ hops, while reinjecting the initial edge descriptor prevents its diffusion from washing it out.Without discriminative edge input, the model cannot exceed its message-passing backbone.
  • 3.3 Readout: A permutation-invariant readout produces graph representations, which feed a regression head on Zinc and are directly compared on the isomorphism benchmark.The architecture remains a message-passing scheme and therefore inherits the 1-WL bound absent useful edge information.

4 Expressivity: What Edge-Girth Cannot Do

Edge-girth features cannot distinguish graphs when every edge has the same shortest-cycle length and multiplicity, because the structural input is constant. EGAGNN and any architecture using only this per-edge descriptor then retain the 1-WL limitation, although multiplicity keeps the blind spot smaller than girth alone.

  • 4.1 Edge-Girth-Regular Graphs: Edge-girth is informative only when it varies across a graph’s edges; a constant descriptor provides no advantage over the message-passing backbone.This limitation concerns the descriptor’s discriminative signal rather than a particular consumption mechanism.
  • 4.1 Edge-Girth-Regular Graphs: In an edge-girth-regular graph, every edge has the same girth g and shortest-cycle multiplicity λ, so the descriptor is constant by construction.Such graphs are k-regular on n vertices, have girth g, and place exactly λ shortest cycles through every edge.
  • 4.2 Proof of the Limitation: EGAGNN assigns two edge-girth-regular graphs with matching parameters distinct representations only if 1-WL distinguishes them.The proof propagates the constant edge input through node and edge updates and reduces the final readout to 1-WL colour multisets.
  • 4.2 Proof of the Limitation: The limitation applies even though gates can vary across layers, because those gates absorb only information already available through message passing and constant initial edge features.The proof does not require gates themselves to remain constant.
  • 4.3 Graph Families Covered: Strongly regular graphs with λ > 0 and distance-regular graphs are edge-girth-regular, so matching-parameter pairs from these families fall under the limitation.For strongly regular graphs, every edge lies on λ triangles; distance-regular parameters determine the relevant quantities.
  • 4.4 Why Multiplicity Matters: Using only edge-girth would enlarge the BREC family from 90 to 103 pairs, but EGAGNN resolves 12 of the 13 additional pairs because their multiplicities vary.The full pair (g_e, λ_e) therefore keeps the blind spot minimal.
  • 4.5 Generality: The result is architecture-independent for models whose sole structural input is a per-edge function of (g_e, λ_e), and escaping it requires information such as cycle counts beyond the girth.That additional information reintroduces the choice of bounded cycle lengths.
  • 4.6 Benchmark Prediction: The prediction is testable before training: every matching-parameter edge-girth-regular BREC pair should remain unresolved, and Section 5.4 evaluates all 400 pairs.The benchmark test is framed as a pair-by-pair falsifiable prediction.

5 Experiments

Experiments evaluate EGAGNN on molecular regression and graph discrimination under matched conditions. EGAGNN improves Zinc performance, while BREC results expose a sharply defined limitation for edge-girth-regular pairs.

  • Graph Regression on Zinc: EGAGNN reaches 0.0932 ± 0.0035 test MAE on Zinc-12k at approximately 100,000 parameters, 3.0 times below GatedGCN.The comparison varies architecture, descriptor, and edge-attribute access jointly; GSN is an external baseline rather than a controlled comparison.
  • Graph Regression on Zinc: Replacing GatedGCN’s linear transforms with EGAGNN’s two-layer MLPs changes MAE by 0.005 within the combined standard deviation.The gating mechanism, aggregation, skip connection, and matched parameter setting were retained, ruling out nonlinear depth as the explanation reported here.
  • Descriptor Comparison: A length-four cycle dictionary reaches 0.2021, indistinguishable from no structural descriptor, whereas length-six and length-eight dictionaries reach 0.1150 and 0.1005.The controlled comparison holds architecture and bond attributes fixed while varying only structural edge descriptors.
  • Descriptor Comparison: Edge-girth reaches 0.0932 with three structural channels, while the length-eight dictionary uses six channels and requires choosing a dataset-specific ceiling.The paper presents k = 8 as close on molecular graphs, but notes that k = 4 is worthless and k = 6 leaves part of the gain unrealized.
  • Isomorphism Discrimination on BREC: On BREC, edge-girth separates every Basic pair and 82% of Extension, exceeding GSN’s 0.71 on Extension under matched structural-descriptor conditions.All methods receive no edge attributes and attain 100% reliability under the official protocol.
  • Isomorphism Discrimination on BREC: Not one of the 90 edge-girth-regular BREC pairs is resolved by either method, exactly matching the predicted blind spot.The result holds pair by pair across all 400 benchmark pairs; however, 116 other pairs remain unresolved even though the descriptor varies.

6 Discussion and Limitations

The discussion identifies where edge-girth methods succeed, where their evidence is limited, and which comparisons remain unresolved or confounded.

  • Scope of the graph-discrimination result: Edge-girth methods resolve 49 of 50 non-egr Regular pairs but none of the 50 egr pairs, matching exact 2-FWL except for pair #71.The CFI pairs fall outside the proposition’s scope; edge-girth methods resolve 3% of them versus 60% for exact 2-FWL.
  • Value of the unbounded descriptor: A cycle dictionary reaching length eight comes within 8% of (ge, λe) on Zinc, with nearly overlapping standard deviations.The experiments do not settle whether any affordable fixed ceiling is insufficient.
  • Limits of supervised evidence: Supervised evidence comes from one regression target on one dataset, so transfer to graph classification and other molecular targets remains untested.The study reports matched baselines, official splits, no test-set model selection, and a four-seed descriptor study.
  • Comparison caveats: GSN differs from EGAGNN in both backbone and descriptor, while several baselines do not consume bond types, so these are not controlled descriptor comparisons.Section 5.3 provides the controlled comparison.

A Experimental Details

The experimental appendix records shared training configuration and implementation choices for preprocessing and edge-feature handling.

  • Training configuration: Training values are shared across methods unless Section A.5 specifies otherwise.This is the scope stated for Table 5’s configuration.
  • Edge-feature preprocessing: Bridges use (ge, λe) = (∞, 0) internally but are injected as (0, 0, 1), avoiding a numerical stand-in for infinity.Finite descriptor values are standardised using training-split statistics, with the normaliser fitted on all CSL graphs.
  • Edge representation: The two directed copies of each undirected edge receive identical descriptor values through an unordered lookup.Under sum aggregation, each undirected edge consequently contributes twice to neighbourhood aggregation.

A.3 Parameter-budget matching

Parameter matching targets approximately 100,000 parameters while compensating for descriptor-dependent edge-processing costs; one cycle-dictionary comparison remains mildly under budget.

  • Budget matching: Target 100,000 parameters with ±10% tolerance is enforced by independently searching hidden width for each method and descriptor variant.Adding structural channels enlarges edge components and is compensated by reducing hidden width.
  • Budget exception: The cycles-3–8 variant uses 90,351 parameters, 9.6% below target and 13% below the edge-girth variant.Its MAE of 0.1005 is therefore an upper bound on the full-budget performance of a length-eight dictionary.
  • BREC evaluation: The BREC benchmark contains 400 pairs partitioned into Basic, Regular, Extension, CFI, 4-Vertex-Condition, and Distance-Regular categories.The last two categories partition the official 140-pair Regular bucket, preserving the total while changing reporting granularity.
  • Non-learned baselines: Exact 2-FWL and the edge-girth multiset baseline are not learned and bypass the training loop.Both are passed through the same T^2 test at the same threshold as learned methods.

A.5 Asymmetries between methods

The appendix records method-specific departures from shared experimental settings, including bond-type access, BREC architecture changes, and computational resources.

  • Method asymmetries: On Zinc, GCN, GIN, GatedGCN, and GatedGCN-MLP omit bond types, whereas EGAGNN and GSN consume them.On BREC, PPGN uses half the hidden width and two layers, while the triangle-count baseline uses one structural channel.
  • Compute: The full BREC campaign runs on CPU and takes 6.5 hours across nine methods.The ablation takes 67 minutes and the descriptor study 57 minutes, each over four seeds.

B Full Result Tables

The reported tables cover BREC reliability, Zinc test MAE, descriptor ablations, and the distinction between edge-girth-regularity criteria.

  • BREC reliability: 100% reliability is reported for every evaluated method across all 400 BREC pairs.The table records zero control-group failures out of 400.
  • Zinc results: Zinc results are reported as test MAE per seed, with bond-aware GSN used in the main text.GSN rows without bond types are included only for reference.
  • Descriptor study: The descriptor study keeps architecture and bond attributes identical throughout the Zinc comparison.This table isolates descriptor and ablation effects under a fixed setup.
  • Edge-girth criterion: The weaker edge-girth-only criterion admits 103 pairs instead of 90, and 12 of its 13 additional pairs are resolved.This is why the paper rejects a girth-only version of the proposition.

C CSL

The CSL evaluation reports deterministic fold behavior but flags specific methods as unreliable, limiting how their apparent accuracies should be interpreted.

  • Evaluation scope: CSL is reported for completeness, but excluded from the main text because two reference implementations proved unreliable.The exclusion is an evaluation-quality decision rather than a reported performance result.
  • Unreliable methods: PPGN never reaches chance-level cross-entropy despite training loss falling from 1962 to 2.73.Its minimum loss is 2.462 versus chance ln 10 ≈2.303, and its accuracy is exactly 0.100.
  • Unreliable methods: The exact 2-FWL CSL result uses a lossy histogram summary followed by logistic regression, so its 0.200 reflects that pipeline rather than 3-WL separation.The paper therefore does not report it as a 3-WL baseline.
  • Fold behavior: Every CSL method returns the same accuracy on all five folds, producing zero standard deviations.The paper attributes this uniformity to deterministic separation of skip-length classes and identical class composition across stratified folds.
  • CSL setup: CSL uses 150 graphs, 10 classes, five-fold cross-validation, and 100 epochs, with chance accuracy 0.100.Starred rows are marked unreliable and should not be read as results.
Loading 2609.01441v1…