Edge-Girth as a Structural Edge Feature for Graph Neural Networks
Lilian Marey, Charlotte Laclau
cs.LG
Quick verdict
门控 GNN 中的每边围长描述子（Per-edge girth descriptor）：在 ZINC 上表现强劲，且在 BREC 上得到了成对验证的盲点证明；但有监督证据仅基于单一数据集。
Summary
本文提出了用于消息传递 GNN 的每边对（边围长、多重性）——即通过每边的最短回路的长度和数量，可通过每边进行一次广度优先搜索精确计算——作为一种结构描述子，与有界回路计数词典不同，它不需要预先选择主题大小上限。通过乘法方式注入门控架构（EGAGNN）中，它在约 104k 参数下于 ZINC-12k 上达到了 0.0932±0.0035 的测试 MAE，而 GatedGCN 为 0.2778，GSN 为 0.1725，不过作者指出了表 1 中的那些对比因键类型访问权限而存在混淆。受控的表 2 研究表明，cycles-3–4 词典毫无价值（0.2021 对比无描述子的 0.2044），cycles-3–8 相差 8%（0.1005），而 edge-girth 以三个通道获胜。理论上，命题 1 证明在边围长正则图（edge-girth-regular graphs）上，描述子是常数，构建于其上的任何模型都会退化为 1-WL 边界；在所有 400 个 BREC 对中，受影响的 90 个对均未得到解决，完全符合预测，且注 3 表明多重性通道是必要的。主要局限性：有监督证据来自单一回归数据集和四个随机种子；CFI 失败（3% 对比 2-FWL 的 60%）无法解释；且与最佳有界词典的差距处于重叠的标准差范围内。代码已公开。
Review complete
Assessment at a glance
4
risk flags identified
● high 0
● medium 2
● low 2
4 strengths · 4 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- The per-edge pair (edge-girth, multiplicity of shortest cycles) is an isomorphism-invariant structural descriptor computable exactly by one BFS per edge, with no motif-size ceiling chosen in advance.
- EGAGNN with this descriptor reaches 0.0932±0.0035 test MAE on ZINC-12k at ~104k parameters, roughly a factor three below GatedGCN and 1.9x below GSN (comparisons the authors themselves flag as confounded).
- Any model whose sole structural input is a per-edge function of (ge, λe) provably collapses to its 1-WL backbone on edge-girth-regular graphs with matching (g, λ), and a girth-only version of the statement would be false.
- On BREC, none of the 90 edge-girth-regular pairs (out of 400) is resolved, matching the prediction without exception, while supervised gains over bounded cycle dictionaries hold only at near-parity with a length-8 dictionary.
Strengths
Controlled descriptor comparison
Table 2 (§5.3) holds architecture and bond attributes fixed and varies only the structural channels: cycles-3–4 at 0.2021 is indistinguishable from no descriptor (0.2044), cycles-3–8 reaches 0.1005 with 6 channels at a disclosed 90,351-parameter handicap, and (ge,λe)+bridge wins at 0.0932 with 3 channels — cleanly isolating the ceiling-choice problem the paper is about.
Falsifiable theory verified at pair granularity
Proposition 1 (§4) predicts collapse on edge-girth-regular graphs; Table 4 shows 0 of the 90 such BREC pairs resolved by both methods, and Remark 3 sharpens it by showing a girth-only criterion would fail (12 of 13 additional pairs resolved), proving the multiplicity channel is load-bearing rather than decorative.
Calibration against published numbers
Unusual transparency about adverse facts
Weaknesses
Single-dataset supervised evidence
Confounded headline comparison
Margin over the best bounded dictionary is within noise
Unexplained CFI collapse
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper (arXiv 2609.01441, cs.LG) introduces a per-edge structural descriptor for message-passing GNNs: the edge-girth g_e (length of the shortest cycle through an edge, ∞ for bridges) together with λ_e, the number of such shortest cycles. Unlike bounded subgraph-count dictionaries (GSN-style), it reports cycles of arbitrary length with no size ceiling chosen in advance, at O(|E|(|V|+|E|)) preprocessing via one BFS per edge (§2.3). The pair is injected multiplicatively into a gated MPNN, EGAGNN (§3). Three claims: (1) the descriptor carries task-agnostic structural signal; (2) on ZINC-12k it reaches 0.0932±0.0035 test MAE at ~104k parameters, beating bounded dictionaries under a fixed architecture; (3) Proposition 1 proves any model whose sole structural input is a function of (g_e, λ_e) collapses to the 1-WL bound on edge-girth-regular graphs — verified pair-by-pair on BREC (0/90 such pairs resolved).
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 4 strengths & 4 weaknesses, analyzed in detail
- 4 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is the edge-girth of an edge in a graph?
It is the length of the shortest cycle passing through that edge (∞ if the edge is a bridge, i.e., lies on no cycle). The companion quantity, multiplicity, counts how many distinct shortest cycles of that length pass through the edge. Both are computable exactly with one breadth-first search per edge that avoids the edge itself, with no limit on cycle length.
How much does EGAGNN improve results on ZINC-12k?
At a matched ~100k-parameter budget it reports 0.0932±0.0035 test MAE versus 0.2778 for GatedGCN and 0.1725 for GSN (k=6). The paper notes some baseline comparisons are confounded by bond-feature access; in the controlled descriptor study its 3-channel descriptor beats cycle-count dictionaries, with a dictionary counting cycles up to length 8 closest at 0.1005 — a gap within overlapping standard deviations.
What are the known limitations of edge-girth features for GNNs?
On edge-girth-regular graphs — where every edge lies on the same number of shortest cycles of the same length — the descriptor is constant, so any model built on it falls back to the 1-Weisfeiler-Leman expressive power limit; on the BREC benchmark none of the 90 such pairs was distinguished. Supervised evidence is also limited to ZINC-12k regression, and the method resolves only 3% of CFI pairs versus 60% for 2-FWL, which the paper leaves unexplained.
Is code available for the EGAGNN paper?
Yes. The paper links an anonymous repository (anonymous.4open.science/r/GDDL_EGAGNN-5154) and provides full hyperparameters, per-seed result tables, descriptor-normalization details, and parameter-matching logs in its appendices; all experiments run on CPU.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Extraction appears complete: the text runs through Appendix C and Table 12 with the full abstract, all references and appendices present (the metadata feed's mid-sentence abstract cut is an artifact of the metadata, not the full text).
- The linked anonymous code repository was not inspected; reproducibility readiness is judged from the paper's stated protocols, hyperparameters and appendices only.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.