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

Edge-Girth as a Structural Edge Feature for Graph Neural Networks Lilian Marey∗

Charlotte Laclau†

arXiv:2609.01441v1 [cs.LG] 1 Sep 2026

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): starting from a uniform colouring, each node is repeatedly recoloured as a function of its own colour and the multiset of its neighbours’ colours, and two graphs the process 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 being 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 and is computable exactly by a single breadth-first search per edge. Like other structural encodings, it is computed once from the graph alone, before and independently of any supervision, and is therefore not specific to a downstream objective. We evaluate it on two tasks of different kinds. 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; compared against bounded cycle-counting descriptors under the same architecture, it matches only a dictionary that explicitly counts cycles up to length eight, which requires 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 prediction holds without exception across all 400 pairs of the BREC graph-isomorphism benchmark: not one of the 90 such pairs is distinguished.

Code and datasets are available at https://anonymous.4open.science/r/GDDL_EGAGNN-5154

1

Introduction

Message-passing neural networks (MPNNs) are limited in expressive power by the one-dimensional WeisfeilerLeman test (1-WL): two graphs that 1-WL fails to separate receive identical representations, no matter how many layers or parameters are used [18, 13]. A standard remedy is to enrich node or edge inputs with precomputed structural descriptors, most commonly counts of small subgraphs [3] or random-walk and spectral encodings [6]. Higher-order approaches such as cellular complexes [2] make cycle structure explicit at the message-passing level, while recent work on the cycle counting expressiveness of MPNNs [9] has quantified the limits of cycle-based augmentation. Subgraph counting carries an assumption that is rarely made explicit: the informative substructure must be bounded in size and fixed in advance. The limitation is one of coverage rather than of budget. A dictionary of motifs of size at most k cannot report a cycle of length k + 1, however much computation is spent on it; enlarging k trades one ceiling for a higher one but never removes it. The choice is consequential and is made blind: on a molecular dataset such as Zinc, a per-edge cycle dictionary capped at k = 4 leaves the model no better than one given no structural descriptor at all, while the same dictionary at k = 8 recovers almost all of the available gain. In this article, we study a descriptor that does not require this choice. The edge-girth ge of an edge e is the length of a shortest cycle containing e, with ge = ∞ when no such cycle exists; alongside it, we carry λe , the ∗ LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France (lilian.marey@telecom-paris.fr).

† LTCI, Télécom Paris, Institut Polytechnique de Paris, Palaiseau, France (charlotte.laclau@telecom-paris.fr).

1

number of cycles of that length through e. The pair is attached to each edge, is invariant under isomorphism, and reports a cycle of unbounded length: an edge lying only on a 20-cycle is described as faithfully as one lying on a triangle, with no dictionary to enlarge. It is also exactly computable, by a single breadth-first search per edge: the quantity equals one plus the length of a shortest path between the endpoints of e that avoids e, the object of the replacement path problem [1]. It carries meaning in applications, governing transition rates in active flow networks [16], and short cycles through an edge – exactly the small edge-girth values – are a dominant cause of decoding failure in the Tanner graphs of LDPC codes [17]. The collection of these values over all edges, the edge-girth sequence, has recently been characterised up to realizability [11]. That characterisation also indicates how the descriptor should not be used: the sequence is additive under vertex identification and does not determine the number of vertices of the graph, so it is a poor graph signature. We therefore propose to treat edge-girth locally, injecting the per-edge pair into message passing so that it modulates the flow of node information rather than summarising the graph on its own. The resulting model, EGAGNN (Edge-Gated Aligned GNN), gates each message by a learned function of the edge it travels along, and lets edge states absorb the context of their endpoints so that edge-girth information diffuses beyond immediate neighbourhoods. The descriptor is effective on molecular property prediction and provably powerless on a precisely identifiable family of graphs. On Zinc-12k at a matched parameter budget, EGAGNN reaches a test MAE of 0.0932 ± 0.0035, a factor three below the closest gated comparator. Holding the architecture and the chemical inputs fixed and varying only the structural descriptor, we compare (ge , λe ) (together with a bridge indicator, three channels per edge in total) against bounded cycle-count dictionaries of increasing length. The three-channel descriptor is matched only by a six-channel dictionary reaching length eight, and dictionaries capped at four are worthless on this data: the advantage lies less in what edge-girth sees than in not having to guess where to stop looking. In the opposite direction, on edge-girth-regular graphs (those in which every edge lies on the same number of shortest cycles, all of the same length, [10]) the descriptor is constant by definition, and any model built on it computes what it would compute from a constant edge input: its expressive power falls back to the 1-WL bound. The prediction holds without a single exception on the BREC benchmark [15], a purpose-built collection of graph pairs designed to be hard for the Weisfeiler–Leman hierarchy. It does not, however, account for every hard case in that benchmark, as we discuss in Section 6. Contributions. • We propose the per-edge pair (ge , λe ) as a structural descriptor requiring no motif-size budget and computable exactly by one breadth-first search per edge, and EGAGNN, a gated message-passing architecture that consumes it (Sections 2–3). • On Zinc-12k with all architectures matched to ≈100k parameters, EGAGNN reaches 0.0932 ± 0.0035 test MAE, and a depth-matched comparator rules out nonlinear depth as the explanation. A descriptorversus-descriptor study, holding architecture and chemical inputs fixed, quantifies what a bounded cycle dictionary must reach to match an unbounded one (Sections 5.2–5.3). • We prove that edge-girth-based models degenerate onto their backbone on edge-girth-regular graphs, and verify the prediction pair by pair: of the 400 BREC pairs, 90 are edge-girth-regular and not one is resolved. We further show that the multiplicity λe is necessary for the statement – an edge-girth-only version of it would be false (Section 4).

2

Edge-Girth as a Structural Edge Invariant

2.1

Edge-Girth and Multiplicity, by Example

Let G = (V, E) be a simple connected graph. The edge-girth of an edge e ∈ E, denoted ge , is the minimum number of edges of a simple cycle of G containing e, and ge = ∞ when e lies on no cycle, i.e. when e is a bridge. Edge-girth values range over {3, 4, 5, . . . } ∪ {∞}, and mine∈E ge recovers the usual girth of G. We write λe for the multiplicity of e, the number of distinct cycles of length ge through e. The pair (ge , λe ) is the elementary object this work builds on: it is defined per edge, invariant under graph isomorphism, and, unlike a subgraph count, carries no bound on the size of the structure it reports. 2

a

b d

c a: ge = ∞

b: ge = 3, λe = 1

c: ge = 3, λe = 2

e

d: ge = 3, λe = 1

e: ge = 4, λe = 1

Figure 1: The descriptor on a small graph, illustrated on five edges. Edge a is a bridge: it lies on no cycle, so its edge-girth is infinite. Edge b lies on a single triangle, and edge c on two, which is what its multiplicity of two records, the multiplicity counts how many shortest cycles an edge belongs to, not how many cycles in total. Edge d is the instructive case: it lies on a triangle and also on the square formed with edges e and its neighbours, and only the shorter of the two is reported, so its edge-girth is three rather than four. Edge e belongs to no triangle at all, and its shortest cycle is that square, giving edge-girth four. Figure 1 works through both quantities on a small graph. Collecting the edge-girth values over all edges yields the edge-girth sequence σ(G). Which sequences arise as σ(G) for some simple connected G has recently been settled: a sequence is realizable if and only if it satisfies a recursive criterion on the number of edges attaining its largest value, controlled by the maximum diameter attainable by graphs realizing the sequence with that largest value removed [11]. We use that characterisation only as background; the two properties we need are stated next. A related but distinct notion is that of edge-girth-regular graphs [10]: regular graphs where every edge lies on exactly λ shortest cycles, all of length g, so that (ge , λe ) is constant across edges. The formal definition is given in Section 4, which shows what this family delimits.

2.2

The Edge-Girth Sequence Is a Weak Global Invariant

Two properties show that σ is poorly suited to acting as a graph signature on its own. First, σ is additive under vertex identification: gluing two graphs G1 and G2 at a single vertex (denoted as G1 ⊕ G2 ) creates no new cycle, so the edge-girth values of G1 ⊕ G2 are exactly those of G1 together with those of G2 [11]. The sequence is blind to how components are attached to one another, and any two assemblies of the same building blocks are indistinguishable by σ. Second, σ does not determine the order of the graph: the sequence consisting of nine edge-girth values all equal to 3 is realized both by a graph on five vertices and by a graph on seven vertices [11]. A quantity that fails to recover |V (G)| cannot be expected to separate non-isomorphic graphs in general. We therefore attach (ge , λe ) to each edge and inject it into message passing rather than using σ as a graph-level descriptor. This buys nothing on the isomorphism benchmark of Section 5.4, where propagating the descriptor through a network matches a direct hash of the per-edge multiset to within one pair out of four hundred; it pays off on graph-level regression (Section 5.2), and Section 4 explains why no architecture built on this descriptor could have done better on the former.

2.3

Computing (ge , λe ) by Breadth-First Search

Both quantities come from a single traversal per edge. For e = {u, v}, a breadth-first search from u in G \ {e} returns d(u, v), the shortest path distance between u and v in G \ {e}, and by the standard shortest-path counting recursion, the number of shortest u–v paths. Since such a path is simple and avoids e, closing it with e gives ge = d(u, v) + 1 and λe exactly, with ge = ∞ when v is unreachable. No approximation and no truncation is involved. The traversal is paid once per edge, so the descriptor costs O(|E|(|V | + |E|)) per graph. This is a real cost, and we make no claim that it is smaller than that of bounded motif counting: in our measurements the ranking between the two reverses with the graph family. On molecular graphs, which are small and comparatively dense, the per-edge traversal is the cheaper of the two; on sparse, low-degree graphs whose edges lie on long cycles, a bounded cycle enumeration has few cycles to find and wins comfortably. What the traversal buys

3

is exactness and the absence of a size ceiling, not speed. Unlike higher-order GNNs that elevate cycles to the message-passing level [2], edge-girth keeps the backbone standard while enriching edge features, trading expressivity for computational simplicity. This complements recent analyses of cycle-counting expressiveness [9]. Computing ge is an instance of the replacement path problem, for which sharper bounds are available [1]; the linear-time procedure of [8] applies when the girth is globally constant, which is not the regime considered here. The computation is a one-off preprocessing step, cached and amortised over training in the same way as random-walk and Laplacian encodings [6]. At molecular scale it costs a fraction of a single training run and is reused across every seed and every hyperparameter setting, so it does not enter the comparison between methods.

3

EGAGNN

3.1

Edge Feature Initialization

Each edge e = {u, v} is endowed with the pair introduced in Section 2. Two adjustments make it usable as a network input. Bridges, for which ge = ∞, cannot be handed to a network as a finite number, so we replace the pair by a fixed placeholder value together with an explicit binary indicator: the network is told directly that the edge lies on no cycle, rather than being given an arbitrarily large finite substitute that it might mistake for a very long cycle. Concretely, both quantities are normalised using training-split statistics only, and a bridge is represented by the placeholder value (g̃uv , λ̃uv ) = (0, 0) together with the indicator set to 1. The initial edge representation is h i e(0) g̃uv , λ̃uv , 1{guv = ∞} auv , (1) uv = where g̃ and λ̃ are the normalised edge-girth and multiplicity, and auv denotes any edge attributes supplied by the dataset, such as bond types on molecular graphs. On the isomorphism benchmark auv is empty and the structural triple is the only edge input; on Zinc it is not, which is why Section 5.3 holds the architecture and auv fixed and varies only the structural part. Both entries g̃ and λ̃ come from the single breadth-first search of Section 2.3. We deliberately stop at the shortest cycle. Going further means one of two things. Counting simple cycles of unbounded prescribed length through an edge is #W[1]-hard [7], whereas counting shortest ones is a linear-time recursion. Counting them up to a fixed length k is tractable, it is exactly what a bounded cycle dictionary does. Section 5.3 measures what that choice costs relative to the unbounded descriptor.

3.2

Gated Message Passing

Structural edge information is injected multiplicatively rather than by concatenation to node features, so that an edge modulates what passes through it. At layer ℓ, the message sent from v to u is 

(ℓ) (ℓ−1) (ℓ−1) m(ℓ) = sigm ϕ e ⊙ ϕ(ℓ) , (2) uv e uv n hv (ℓ)

(ℓ)

where ϕe and ϕn are MLPs acting on the edge and node states respectively, sigm is the sigmoid and ⊙ the Hadamard product. The sigmoid output acts as a learned per-channel gate: an edge on a short cycle and an edge on a long one open different channels, and the model learns which edge-girth regimes are worth propagating for the task at hand. Node and edge states are then updated by   (ℓ−1) h(ℓ) + AGG m(ℓ) , (3) u = hu uv v ∈ N (u)   (ℓ) e(ℓ) e(0) e(ℓ−1) h(ℓ) h(ℓ) , (4) uv = ψ uv uv u v with ψ (ℓ) an MLP and ∥ concatenation. Equation (3) is a residual aggregation of the gated messages. Equation (4) is what makes the scheme more than a static feature augmentation. Because an edge state 4

absorbs the representations of its two endpoints at every layer, and those endpoints have themselves aggregated their neighbourhoods, after ℓ layers the gate on {u, v} depends on the edge-girth values of every edge within (0) ℓ hops, not only on guv . Re-injecting euv at each layer keeps the raw descriptor available and prevents it from being washed out by this diffusion. Two consequences matter for Section 4. First, the architecture is a message-passing scheme: absent any edge input it inherits the 1-WL bound. Second, the only information it receives beyond the adjacency (0) structure is euv . Whenever that input carries no discriminative signal, the model can do no better than its backbone.

3.3

Graph-Level Readout (L)

A permutation-invariant pooling of the final node states yields the graph representation g = READOUT {hu |
u ∈ V } , passed to a regression head on Zinc; on the isomorphism benchmark the graph embeddings themselves are compared under the protocol of Section 5.4.

4

Expressivity: What Edge-Girth Cannot Do

The descriptor of Section 2 is informative only inasmuch as it varies across the edges of a graph. There is a family on which it does not vary at all, and on which the model retains no advantage over its backbone. Recall from [10] that a graph is egr(n, k, g, λ), or edge-girth-regular, if it is k-regular on n vertices, has girth g, and every edge lies on exactly λ cycles of length g. In such a graph the descriptor is constant by construction, and this is enough to erase it. Proposition 1. Let G1 and G2 be edge-girth-regular graphs with the same parameters (g, λ) and no dataset edge attributes. Then EGAGNN assigns them distinct graph representations only if the 1-WL test distinguishes them. Proof. Every edge of an edge-girth-regular graph satisfies ge = g and λe = λ, and no edge is a bridge, so (0) Equation (1) gives euv = c for every edge of either graph, with the same constant c in both. We show by (ℓ) (ℓ) induction on ℓ that hu is a function of the 1-WL colour cℓ (u) and that euv is a function of {{cℓ (u), cℓ (v)}}. (0) This holds at ℓ = 0, node states being initialised identically
and e being constant. Assuming it at ℓ − 1, the message (2) is a function of {{cℓ−1 (u), cℓ−1 (v)}}, cℓ−1 (v) ; aggregating over N (u) in (3) yields a function of cℓ−1 (u) and of the multiset {{cℓ−1 (v)}}v∈N (u) , which is exactly the refinement defining cℓ (u); the edge update (4) then depends only on c and on the colours of its endpoints. As READOUT is a function of the multiset of final node states, two graphs with identical 1-WL colour multisets receive identical representations. The gates do not stay constant across layers: from the first layer on, they absorb node states through (4). What the proof shows is simpler. The model computes exactly the function it would compute with any constant edge input, so its expressive power is that of its message-passing backbone, and the 1-WL bound applies unchanged. Corollary 2. Strongly regular graphs with λ > 0, and among them those satisfying the four-vertex condition, are edge-girth-regular: such a graph has girth 3 with exactly λ triangles through every edge. Distance-regular graphs are likewise edge-girth-regular, the girth and the number of shortest cycles through an edge being determined by the intersection array [4, 14]. Pairs drawn from either family with matching parameters therefore fall under Proposition 1. Remark 3 (the multiplicity is necessary). Proposition 1 requires the full pair (ge , λe ) to be constant, and this is not a technical convenience. Requiring only ge to be constant yields a strictly larger family (on BREC, 103 pairs instead of 90), over which the proposition would be false: of the 13 additional pairs, 12 are resolved by EGAGNN, precisely because λe varies on them while ge does not. Carrying the multiplicity keeps the blind spot minimal. Remark 4 (generality). Nothing in the proof is specific to EGAGNN. The argument applies to any architecture whose sole structural input is a per-edge function of (ge , λe ), and in particular to a plain MPNN augmented 5

with these values as edge features. The limitation is a property of the descriptor, not of the way it is consumed. Escaping it requires strictly more information, cycle counts at lengths beyond the girth, for instance, which reintroduces the trade-off of Section 3.1. Proposition 1 is a prediction that can be read off a benchmark before any model is trained, and it is falsifiable pair by pair: every pair whose two graphs are edge-girth-regular with matching parameters must go unresolved. Section 5.4 tests it on all 400 pairs of BREC, and Section 6 discusses how much of the benchmark’s difficulty it accounts for.

5

Experiments

5.1

Setup

The descriptor is computed from the graph alone, once, before any training, and does not depend on the downstream objective, it is a property of the representation rather than of the task. We therefore evaluate it on two tasks of different kinds, which probe it in complementary ways. Zinc-12k [5] measures whether the descriptor carries signal a supervised model can exploit, and lets us compare it against alternative structural descriptors under a fixed architecture. BREC [15], a benchmark of graph pairs constructed to be indistinguishable by 1-WL and difficult for higher levels of the Weisfeiler–Leman hierarchy, measures separating power directly, with no objective to fit, and is where the limitation of Section 4 can be tested pair by pair. Results on CSL are relegated to Appendix C, where two of the reference implementations proved unreliable. On Zinc we use the official splits (10,000/1,000/1,000), train for 200 epochs and report test MAE averaged over four seeds, with no early stopping and no test-set model selection. All architectures are matched to a budget of 100,000 parameters within ±10% by adjusting the hidden width, so that comparisons are not confounded by capacity. On BREC we use the official reliable-paired-comparison protocol with 32 relabelings, on all 400 pairs; every method attains a 100% reliability rate, i.e. no method is credited with distinguishing a pair it cannot reliably separate under permutation. All experiments run on CPU. Full hyperparameters are given in Appendix A. Calibration. Three independent checks place our pipeline against published numbers. The 2-dimensional Folklore Weisfeiler–Leman colour refinement (Exact 2-FWL), provably equivalent in distinguishing power to 3-WL, reaches 0.675 overall on BREC, matching the published figure for 3-WL on this benchmark; our implementation of PPGN [12], a message-passing architecture proven to match 2-FWL’s power, resolves 50 of the 140 pairs that [15] report as a single aggregated Regular bucket, i.e. 35.7%, exactly the published value once the same aggregation is applied; and on Zinc our GatedGCN baseline reaches 0.278 against a published 0.375 ± 0.003 at a comparable budget [5]. The baselines we compare against are at least as strong as their reference implementations, not weaker. CW Networks [2] and I2 -GNN [9] were left out of Table 1 for implementation cost rather than principle; GSN remains the closest descriptor-augmented comparator we report.

5.2

Graph Regression on Zinc

Table 1 reports Zinc results at matched capacity. GCN, GIN, GatedGCN and GatedGCN-MLP do not consume bond types in our implementation, whereas EGAGNN and GSN do (Appendix A.5). The comparison to those four methods therefore reflects architecture, descriptor, and edge-attribute access jointly, and Section 5.3 is the controlled comparison. EGAGNN reaches 0.0932 ± 0.0035, a factor 3.0 below GatedGCN, the closest architectural comparator, and a factor 1.9 below GSN with a cycle dictionary sized for molecular rings. For reference, the published GSN figures are 0.115 ± 0.012 at a comparable budget and 0.101 ± 0.010 with roughly five times more parameters [3]. EGAGNN’s per-layer transforms are two-layer MLPs whereas GatedGCN’s are single linear maps, so matched parameter counts do not by themselves match nonlinear depth. We therefore built GatedGCN-MLP, identical to GatedGCN except that each of its four linear transforms is replaced by the same two-layer MLP used in EGAGNN, holding the gating mechanism, aggregation and skip connection fixed. It moves the MAE by 0.005, within the combined standard deviation: nonlinear depth is not the explanation. 6

Table 1: Zinc-12k test MAE (lower is better), mean ± std over four seeds, all architectures matched to ≈ 100k parameters. GatedGCN-MLP replaces each linear transform of GatedGCN by the same two-layer MLP EGAGNN uses, matching nonlinear depth per layer. GSN here is a GIN backbone with per-node orbit counts up to length six and bond-type edge features; it differs from EGAGNN in architecture as well as descriptor and is reported as an external baseline, not as a controlled comparison. Section 5.3 provides the latter. Method EGAGNN GSN (k = 6) GatedGCN-MLP GatedGCN GIN GCN

Hidden dim.

Params

Test MAE

54 98 54 74 98 130

104,113 102,313 102,601 102,121 99,961 106,081

0.0932 ± 0.0035 0.1725 ± 0.0129 0.2726 ± 0.0151 0.2778 ± 0.0072 0.3152 ± 0.0108 0.4372 ± 0.0096

Table 2: Zinc, architecture and bond attributes held fixed, only the structural edge descriptor varied. “Dim” is the number of structural channels supplied per edge. Mean ± std over four seeds at a matched parameter budget. Structural descriptor none (constant) triangle count cycle counts, lengths 3–4 cycle counts, lengths 3–6 cycle counts, lengths 3–8 (ge , λe ) + bridge

5.3

Dim

Test MAE

0 1 2 4 6 3

0.2044 ± 0.0030 0.2154 ± 0.0150 0.2021 ± 0.0117 0.1150 ± 0.0124 0.1005 ± 0.0090 0.0932 ± 0.0035

Which Structural Descriptor?

Table 1 varies architecture and descriptor together, so it cannot attribute the improvement to either. We therefore hold the architecture and the bond attributes fixed – every variant below is EGAGNN with the (0) same capacity and the same chemistry – and vary only the structural entries of euv . Alongside (ge , λe ) we consider per-edge counts of simple cycles of each length up to a ceiling k, the natural bounded-dictionary counterpart to an unbounded descriptor. These counts are computed per edge and injected identically; they are not GSN, whose per-node orbit counts and backbone differ, though the bounded enumeration mechanism is the same idea [3]. Table 2 makes the cost of the ceiling explicit. A dictionary capped at length four is worth nothing on this data: at 0.2021 it is indistinguishable from supplying no structural descriptor at all, and counting triangles alone is no better. The picture changes once the ceiling clears the ring sizes that occur in drug-like molecules, with length six reaching 0.1150 and length eight 0.1005. Edge-girth reaches 0.0932 with three channels rather than six, and without the ceiling ever being chosen. The gap between the best bounded dictionary and edge-girth is small, and we claim no more from it than it supports: on molecular graphs, a cycle dictionary sized to k = 8 comes close. What the comparison shows is the shape of the trade-off. The useful ceiling is not knowable in advance, as k = 4 is worthless here and k = 6 leaves a fifth of the gain on the table, and it is dataset-specific, whereas the unbounded descriptor requires no such choice and reports the informative cycle whatever its length.

5.4

Isomorphism Discrimination on BREC

On BREC no method receives edge attributes, so Table 3 compares structural descriptors on equal terms. Edge-girth separates every Basic pair and 82% of Extension, placing EGAGNN ahead of GSN and of triangle counting overall, though below exact 2-FWL and PPGN. The margin over GSN is clearest on Extension, 0.82 against 0.71. One observation runs against the design of the model. EGAGNN and a direct hash of the per-edge 7

Table 3: BREC, all 400 pairs, official RPC protocol. Fraction of pairs distinguished; all methods attain 100% reliability. No method receives edge attributes here, so this is a comparison of structural descriptors under matched conditions. † marks methods whose only structural input is a per-edge function of (ge , λe ), and which Proposition 1 therefore constrains. Method

Overall (400)

Basic (60)

Regular (100)

Extension (100)

CFI (100)

4-Vert. (20)

Dist.-Reg. (20)

Exact 2-FWL PPGN EGAGNN† Edge-girth multiset† GSN Triangle counts GCN / GIN / GatedGCN

0.675 0.518 0.485 0.483 0.443 0.398 0.000

1.000 1.000 1.000 1.000 0.950 0.983 0.000

0.500 0.500 0.490 0.490 0.490 0.480 0.000

1.000 0.970 0.820 0.810 0.710 0.520 0.000

0.600 0.000 0.030 0.030 0.000 0.000 0.000

0.000 0.000 0.000 0.000 0.000 0.000 0.000

0.000 0.000 0.000 0.000 0.000 0.000 0.000

Table 4: Pairs resolved versus edge-girth-regularity, all 400 BREC pairs. The upper-left cell is the one Proposition 1 constrains; it is empty for both methods.

resolved not resolved

EGAGNN

Edge-girth multiset

egr

not egr

egr

not egr

0 90

194 116

0 90

193 117

multiset {{(ge , λe )}} differ by a single pair out of four hundred. Propagating the descriptor through a network buys nothing on this task: the feature, not the architecture, does all the work. This contrasts with Zinc, where the architecture accounts for a substantial share of the improvement, and Section 4 explains why no architecture built on this descriptor could have done better here. The predicted blind spot, pair by pair. Aggregate rates understate the point, since Proposition 1 constrains individual pairs. Of the 400 BREC pairs, 90 have both graphs edge-girth-regular with matching parameters (k, g, λ); these include the whole of the distance-regular and four-vertex-condition categories, all 40 of whose graphs we verify to be edge-girth-regular. Table 4 crosses this against the outcome. Not one edge-girth-regular pair is resolved, by either method, anywhere in the benchmark. The prediction holds without exception at the level of individual pairs, not merely in aggregate. The converse cell is populated as expected (116 pairs go unresolved although the descriptor does vary on them), since the proposition is a one-directional guarantee and not a characterisation of success. We return to what it does and does not explain in Section 6.

6

Discussion and Limitations

What Proposition 1 does and does not explain. Two qualifications keep the BREC result from being over-read. Within the Regular category, the 50 edge-girth-regular pairs coincide exactly with the strongly regular ones, no pair separates the two properties (Table 11). Edge-girth-based methods resolve 49 of the 50 non-egr pairs and none of the 50 egr ones, while exact 2-FWL resolves all 50 non-egr pairs and likewise none of the egr ones: the two coincide except for a single pair, which is neither edge-girth-regular nor strongly regular and is resolved by 2-FWL alone. That pair, #71, is the only instance in the entire category where our prediction and generic 3-WL hardness come apart. Second, the CFI pairs fall outside the proposition’s scope entirely: not one of the 100 has both graphs edge-girth-regular with matching parameters, so the descriptor does vary on them, and yet the edge-girth methods resolve 3% of them against 60% for exact 2-FWL (Table 3). Why an informative descriptor fails so completely there is an empirical finding our analysis does not account for, and we report it as such rather than stretch the theory to cover it. The proposition is a one-directional guarantee, edge-girth-regularity implies failure and not a characterisation of success. 8

How much the unbounded descriptor is worth. The margin between edge-girth and the best bounded dictionary we tried is small. A per-edge cycle count reaching length eight is within 8% of (ge , λe ) on Zinc, and the two standard deviations nearly overlap. On this dataset the practical benefit of removing the ceiling is modest once it is set correctly, the harder problem is that it cannot be set correctly in advance (Section 5.3). Whether a family of graphs exists on which no affordable ceiling suffices is not settled by our experiments, and constructing a benchmark that isolates it proved hard. How far the supervised evidence reaches. The descriptor is computed independently of the objective, so nothing in its construction is specific to regression; but our supervised evidence comes from a single regression target on a single dataset, and we do not claim more. Whether the gains reported here transfer to graph classification, or to molecular targets whose dependence on cycle structure differs from Zinc’s, is untested. We have made that single point of evidence as solid as we could: baselines matched in parameter count and in nonlinear depth, calibrated against published numbers, official splits, no test-set model selection, and a descriptor study at full scale over four seeds. We also ruled out the most natural shortcut explanation, that the cyclic term of Zinc’s target is being read off the descriptor, by regressing the target on the edge-girth histogram alone, which explains only R2 ≈ 0.26 of its variance, far too little to account for the gap. What remains is a mechanism we can bound but not identify: the gated architecture alone reaches 0.204 (Table 2), the descriptor contributes the rest, and why the interaction of per-edge cycle structure with message passing is worth that much is open. Two comparisons in Table 1 remain confounded and should not be read as descriptor comparisons. GSN differs from EGAGNN in backbone as well as in descriptor, so its gap cannot be attributed to either; Section 5.3 is the controlled version of that comparison. And GCN, GIN and GatedGCN do not consume Zinc’s bond types in our implementation, so they stand as architecture baselines rather than as chemistry-aware ones. Directions. The most immediate follow-up is to widen the range of downstream tasks. Since the descriptor is task-agnostic by construction, graph classification with a matched architecture, and molecular targets whose dependence on cycle structure differs from Zinc’s, would establish whether the gains observed here are a property of the representation or of this particular objective. Second, the regime the descriptor is designed for (graphs whose informative cycles are long) remains untested; Tanner graphs of LDPC codes are a natural candidate, since decoding performance degrades with short cycles through an edge [17], which is exactly what ge reports. Third, combining edge-based constraints with vertex-based ones such as the degree sequence would tighten the prescribed local structure and may leave the edge-girth-regular regime altogether. We note finally that building a synthetic probe to isolate cycle scale is harder than it appears: in our attempts, a target simple enough to control was either predictable from adjacency alone, without any cycle-length information, or an invertible function of the descriptor.

References [1] Aaron Bernstein. “A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs”. In: Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms. SIAM. 2010, pp. 742–755. [2] Cristian Bodnar et al. “Weisfeiler and lehman go cellular: Cw networks”. In: Advances in neural information processing systems 34 (2021), pp. 2625–2640. [3] Giorgos Bouritsas et al. “Improving graph neural network expressivity via subgraph isomorphism counting”. In: IEEE Transactions on Pattern Analysis and Machine Intelligence 45.1 (2022), pp. 657– 668. [4] Andries E Brouwer and Willem H Haemers. “Distance-regular graphs”. In: Spectra of graphs. Springer, 2011, pp. 177–185. [5] Vijay Prakash Dwivedi et al. “Benchmarking graph neural networks”. In: Journal of Machine Learning Research 24.43 (2023), pp. 1–48.

9

[6] Vijay Prakash Dwivedi et al. “Graph neural networks with learnable structural and positional representations”. In: arXiv preprint arXiv:2110.07875 (2021). [7] Jörg Flum and Martin Grohe. “The parameterized complexity of counting problems”. In: SIAM Journal on Computing 33.4 (2004), pp. 892–922. [8] Jan Goedgebeur and Jorik Jooken. “Exhaustive generation of edge-girth-regular graphs”. In: Experimental Mathematics (2025), pp. 1–13. [9] Yinan Huang et al. “Boosting the cycle counting power of graph neural networks with I2-GNNs”. In: arXiv preprint arXiv:2210.13978 (2022). [10] R. Jajcay, G. Kiss, and S Miklavic. “Edge-girth-regular graphs”. In: European Journal of Combinatorics 72 (2018), pp. 70–82. [11] Lilian Marey, Paul Hilaire, and Charlotte Laclau. “On the Realizability of Edge-Girth Sequences”. In: arXiv preprint arXiv:2607.25629 (2026). [12] Haggai Maron et al. “Provably powerful graph networks”. In: Advances in neural information processing systems 32 (2019). [13] Christopher Morris et al. “Weisfeiler and leman go neural: Higher-order graph neural networks”. In: Proceedings of the AAAI conference on artificial intelligence. Vol. 33. 2019, pp. 4602–4609. [14] Edwin R Van Dam, Jack H Koolen, and Hajime Tanaka. “Distance-regular graphs”. In: arXiv preprint arXiv:1410.6294 (2014). [15] Yanbo Wang and Muhan Zhang. “An empirical study of realized gnn expressiveness”. In: arXiv preprint arXiv:2304.07702 (2023). [16] Francis G Woodhouse et al. “Stochastic cycle selection in active flow networks”. In: Proceedings of the national academy of sciences 113.29 (2016), pp. 8200–8205. [17] Hengzhou Xu et al. “LDPC Codes on Balanced Incomplete Block Designs: Construction, Girth, and Cycle Structure Analysis”. In: Entropy 27.5 (2025), p. 476. [18] Keyulu Xu et al. “How powerful are graph neural networks?” In: arXiv preprint arXiv:1810.00826 (2018).

A

Experimental Details

A.1

Hyperparameters

Table 5: Training configuration. Values are shared across methods unless stated otherwise in Section A.5. Optimizer Learning rate Weight decay Batch size (train) Batch size (eval) Scheduler Propagation layers Hidden dim. Output dim. Aggregation Readout Loss Epochs Seeds

Zinc

Descriptor study

BREC

Adam 10−3 0 32 64 none 4 matched = hidden sum sum L1 200 13–16

Adam 10−3 0 32 64 none 4 matched = hidden sum sum L1 200 13–16

Adam 10−4 10−4 16 — ReduceLROnPlateau 3 32 16 sum sum cosine embedding 20 per pair 13

10

The BREC scheduler is ReduceLROnPlateau in its default PyTorch configuration (mode = min, factor 0.1, patience 10), and the cosine embedding loss uses margin 0. BREC is run at a single seed; the 32 relabelings of the RPC protocol supply the stochasticity the test requires, so per-seed variance is not the quantity of interest there. On BREC and CSL, where the graphs carry no attributes, node features are initialised to a constant vector of ones.

A.2

Descriptor construction

Bridges are represented internally as (ge , λe ) = (∞, 0) and injected as the triple (0, 0, 1): the two structural channels are zeroed and the indicator is set, so the network never receives a numerical stand-in for infinity. Finite values are standardised (mean and standard deviation, the latter floored to 1 when degenerate) over the first 300 graphs of the training split, pooled over all their edges. On CSL, which has only 150 graphs in total, the normaliser is fitted on the whole dataset. BREC has no train/test split, so the 300 graphs used there are the first entries of whichever subset a given invocation preprocessed; since the normalisation is applied identically to both graphs of every pair and the RPC test is scale-free within a pair, this does not affect the reported outcomes. edge_index stores both directions of every undirected edge. The descriptor is looked up by an unordered key, so the two directed copies carry identical values by construction; each undirected edge consequently contributes twice to the neighbourhood aggregation of Equation (3), which is a constant factor under sum aggregation.

A.3

Parameter-budget matching

All Zinc architectures are matched to 100,000 parameters within ±10% by binary search on the hidden width over [4, 1024], the parameter count being monotone in that width for every architecture used. The search is run independently for each method and each descriptor variant, so a variant supplying more structural channels, which enlarges the edge embedding and the edge-update MLP, is compensated by a smaller hidden width. Table 6: Effective hidden width and parameter count. Target 100,000, tolerance ±10%. Method EGAGNN GCN GIN GatedGCN GatedGCN-MLP GSN (k = 6)

Hidden

Params

Descriptor variant

Hidden

Params

54 130 98 74 54 98

104,113 106,081 99,961 102,121 102,601 102,313

none (constant) triangle count cycles 3–4 cycles 3–6 cycles 3–8 (ge , λe )

54 54 54 54 50 54

104,113 103,573 103,843 104,383 90,351 104,113

One entry deserves comment. The cycles-3–8 variant lands at 90,351 parameters, 9.6% below target and 13% below the edge-girth variant it is compared against: the binary search overshot downwards when compensating for its six structural channels. That variant is therefore the one comparison in Table 2 run at a mild disadvantage, and its reported MAE of 0.1005 should be read as an upper bound on what a length-eight dictionary achieves at full budget. This does not affect the conclusions drawn in Section 5.3, which concern the dictionaries capped at four and six.

A.4

BREC protocol

We use 32 relabelings per graph, 20 training epochs per pair, an embedding dimension of 16, a Hotelling T 2 threshold of 72.34 and a loss-based early stop at 0.2, following the reference implementation. The reliability control group uses the same number of relabelings and the same threshold as the main test; a pair is credited only when the main statistic exceeds the threshold and the control statistic does not. The benchmark’s 400 pairs are partitioned into Basic (60), Regular (100), Extension (100), CFI (100), 4-Vertex-Condition (20) and Distance-Regular (20). The official release reports a single Regular

11

bucket of 140 pairs; our last two categories (4-Vertex-Condition and Distance-Regular) partition exactly that bucket, so the totals agree and only the reporting granularity differs. Two of the evaluated methods are not learned. Exact 2-FWL compares the two graphs’ stable paircolourings directly. The edge-girth multiset baseline maps each distinct (ge , λe ) value to a fixed pseudo-random vector and sums over edges, giving one deterministic embedding per graph and no parameters. Both skip the training loop entirely and are then passed through the same T 2 test at the same threshold as the learned methods, so no separate similarity proxy is used anywhere in Table 3.

A.5

Asymmetries between methods

Three departures from the shared configuration should be recorded. On Zinc, GCN, GIN, GatedGCN and GatedGCN-MLP do not consume bond types in our implementation, whereas EGAGNN and GSN do; this is discussed in Section 6. On BREC, PPGN is built with half the hidden width (16) and two layers instead of three, following its reference configuration for memory reasons. Also on BREC, the triangle-count baseline supplies a single structural channel rather than the shared edge-input dimension.

A.6

Hardware and software

All experiments run on CPU: an 11-core Apple M3 Pro with 18 GB of RAM, with ten worker processes. Total wall-clock time was 6.5 h for the full BREC campaign across nine methods, 67 min for the ablation and 57 min for the descriptor study, each over four seeds.

B

Full Result Tables

Table 7: BREC, all 400 pairs, all evaluated methods. Every method attains a 100% reliability rate (0 control-group failures out of 400). Method

Basic (60)

Regular (100)

Extension (100)

CFI (100)

4-Vert. (20)

Dist.-Reg. (20)

Overall (400)

Exact 2-FWL PPGN EGAGNN Edge-girth multiset GSN Triangle counts GCN GIN GatedGCN

1.000 1.000 1.000 1.000 0.950 0.983 0.000 0.000 0.000

0.500 0.500 0.490 0.490 0.490 0.480 0.000 0.000 0.000

1.000 0.970 0.820 0.810 0.710 0.520 0.000 0.000 0.000

0.600 0.000 0.030 0.030 0.000 0.000 0.000 0.000 0.000

0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000

0.675 0.518 0.485 0.483 0.443 0.398 0.000 0.000 0.000

Table 8: Zinc test MAE per seed. GSN rows without bond types are reported for reference; the main text uses the bond-aware version. Method

Seed 13

Seed 14

Seed 15

Seed 16

EGAGNN GSN (k = 6, bond types) GSN (k = 4, bond types) GSN (k = 6, no bonds) GSN (k = 4, no bonds) GatedGCN-MLP GatedGCN GIN GCN

0.0958 0.1702 0.2651 0.2222 0.3390 0.2726 0.2730 0.3078 0.4329

0.0879 0.1926 0.2366 0.2073 0.3162 0.2748 0.2859 0.3200 0.4537

0.0923 0.1706 0.2477 0.2257 0.3019 0.2926 0.2838 0.3027 0.4303

0.0969 0.1566 0.2393 0.2119 0.3224 0.2501 0.2687 0.3305 0.4319

12

Table 9: Descriptor study and ablation, Zinc test MAE per seed. Architecture and bond attributes identical throughout. Structural descriptor

Seed 13

Seed 14

Seed 15

Seed 16

none (constant) Gaussian noise triangle count cycles 3–4 cycles 3–6 cycles 3–8 λe only ge only (ge , λe ) + bridge

0.2002 0.2182 0.2164 0.2085 0.1307 0.1146 0.1813 0.0890 0.0958

0.2066 0.2393 0.2320 0.1974 0.1209 0.0904 0.1328 0.0973 0.0879

0.2031 0.2541 0.2218 0.2167 0.0971 0.0959 0.1289 0.0882 0.0923

0.2077 0.2447 0.1913 0.1857 0.1113 0.1010 0.1769 0.0908 0.0969

Table 10: Contingency under the criterion actually used (both ge and λe constant) and under the weaker criterion that constrains ge alone. The weaker criterion admits 103 pairs instead of 90, and 12 of the additional 13 are resolved, which is why Remark 3 states that a girth-only version of Proposition 1 would be false.

C

res. ∧ egr

res. ∧ ¬egr

¬res. ∧ egr

¬res. ∧ ¬egr

EGAGNN Edge-girth multiset

0 0

194 193

90 90

116 117

EGAGNN Edge-girth multiset

12 12

182 181

91 91

115 116

Criterion

Method

(ge , λe ) (ge , λe ) ge only ge only

CSL

We report CSL for completeness, but exclude it from the main text because two reference implementations proved unreliable on it. Training uses Adam with learning rate 10−3 and weight decay 10−5 , cross-entropy loss, batch size 16, three propagation layers of width 32, and constant node features. Folds are stratified with seed 13. Why PPGN is unreliable here. Its training loss moves (from 1962 at the first epoch to 2.73 at the hundredth) but never falls below the chance-level cross-entropy ln 10 ≈ 2.303; the minimum reached over 100 epochs is 2.462, at epoch 87. The model trains without learning a discriminative representation, and its accuracy of exactly 0.100 carries no information either way. Why exact 2-FWL is unreliable here. On BREC, our 2-FWL implementation compares two graphs’ jointly canonicalised stable pair-colourings for exact multiset equality: a direct, exact, unlearned pairwise decision. CSL is a classification task and requires a per-graph vector, so the colouring is reduced to the sorted histogram of stable-colour class sizes and passed to a logistic regression. That histogram is a lossy summary (two 2-FWL-inequivalent graphs can in principle share one) and the prediction depends on a classifier trained on other graphs. The resulting 0.200 therefore measures the summary and the classifier, not the separating power of 3-WL, and we do not report it as a 3-WL baseline. The uniform absence of fold-to-fold variance in Table 12 is consistent with the tasks these methods solve on CSL being deterministic: each method either separates a given skip-length class or does not, and the stratified folds contain the same classes.

13

Table 11: The Regular category, stratified by strong regularity. Edge-girth-regularity and strong regularity coincide on all 100 pairs: every edge-girth-regular pair is strongly regular and conversely, so no pair of this category separates the two properties. Subset (n = 50 each) Plain regular (not strongly regular) Strongly regular

res. ∧ egr

res. ∧ ¬egr

¬res. ∧ egr

¬res. ∧ ¬egr

0 0

49 0

0 50

1 0

Table 12: CSL, 150 graphs, 10 classes, five-fold cross-validation, 100 epochs. Chance level is 0.100. Every method returns the same accuracy on all five folds, so all standard deviations are zero. Starred rows are unreliable and should not be read as results. Method

Test accuracy

EGAGNN GSN Edge-girth multiset Exact 2-FWL⋆ GCN GIN GatedGCN PPGN⋆

14

0.300 0.300 0.300 0.200 0.100 0.100 0.100 0.100

Related documents

• Edge Sparsification via Temporal Forman-Ricci Curvature for Dynamic Graph Learning#440388
• Graph Neural Networks Applications Across Domains: All Insights You Need#310818
• Relevant Walk Search for Explaining Graph Neural Networks#222597
• EssentialGIN: a new approach for gene essentiality prediction based on graph isomorphism neural networks#1014735
• New structure for old graphs: Twin-width through the lens of classical parameters / Simon Vincent Raßmann ; Gutachter: Pascal Schweitzer, Kord Eickmeyer#1065184