Writing study: Which Algorithms Can Graph Neural Networks Learn?

ICML overviewCorpus atlasBy contribution typeVisual galleryRules & templateWriting patternsPaper studies

← ICML 2026 oral writing corpus

Solveig Wittig, Antonis Vasileiou, Robert R Nerem, Timo Stoll, Floris Geerts, Yusu Wang, Christopher Morris · Official ICML 2026 oral record

Observed writing choices, not acceptance rules. This study examines the inspected manuscript version. It does not establish why the paper was accepted or that its presentation choices should be copied unchanged.

Figure, table and section ledger

Editorial contribution type: Theory & formal analysis (primary).

Layout extraction, not a required paper template. Counts are distinct caption labels; a multi-panel figure counts once. Section spans are estimated from heading positions, including floats and whitespace. Method and limitations.

Canonical PDF

76 physical pages

Before references / appendix

≈ 9.18 page-equivalents

Main figures / tables

2 / 2

Attached appendix figures / tables

5 / 8

Attached appendix span

≈ 61.91 page-equivalents

Before references / appendix: ≈ 12.08%References / intervening material: ≈ 6.46%Attached appendix: ≈ 81.46%Estimated layout envelopes, not text/artwork area. Unresolved appendix boundaries remain within the undivided post-body material.

Section-by-section lengths and source pages

The title/abstract/front matter precede the first numbered heading. A span ends at the next detected top-level heading, not at the last sentence; end-page whitespace is included. References and statements are listed separately. These are not measurements of text-only or artwork area.

Top-level heading	Starts on PDF page	Estimated span	Share of entire PDF
1. Background	2	≈ 1.16 pp.	1.53%
2. What and how can GNNs learn	3	≈ 3.77 pp.	4.96%
3. What GNNs cannot learn	7	≈ 0.85 pp.	1.12%
4. Limitations and future directions	8	≈ 0.34 pp.	0.45%
5. Experimental study	8	≈ 0.99 pp.	1.3%
6. Conclusion	9	≈ 0.3 pp.	0.39%
Acknowledgement	10	≈ 0.08 pp.	0.11%
Impact statement	10	≈ 0.05 pp.	0.07%
References	10	≈ 4.91 pp.	6.46%
A. Related work	15	≈ 1.47 pp.	1.93%
B. Extended background	16	≈ 4.16 pp.	5.47%
C. Proof of Theorem 2	20	≈ 1.86 pp.	2.45%
D. Learning non-realizable functions	22	≈ 1.5 pp.	1.97%
E. Improved learning guarantees for SSSPs algorithms	24	≈ 4 pp.	5.26%
F. Proof of Theorem 16	28	≈ 23.24 pp.	30.58%
G. What MPNN cannot learn	51	≈ 2.29 pp.	3.01%
H. Expressivity limitations	53	≈ 3.86 pp.	5.08%
I. MPNN classes satisfying finite Lipschitzness	57	≈ 2.03 pp.	2.67%
J. Topological, measure-theoretic, and geometric background	59	≈ 3.29 pp.	4.33%
K. Proof of Theorem 3 for sum/mean-aggregation	62	≈ 4.7 pp.	6.18%
L. Proof of Theorem 3 for max/min-aggregation	67	≈ 2.9 pp.	3.82%
M. Iterated degree measures as computation trees	70	≈ 0.35 pp.	0.46%
N. Experimental study	70	≈ 6.24 pp.	8.21%

All detected figure and table locations

Main text

• Figure 1 · p. 5
• Figure 2 · p. 9
• Table 1 · p. 9
• Table 2 · p. 9

Attached appendix

• Figure 3 · p. 27
• Figure 4 · p. 33
• Figure 5 · p. 57
• Table 3 · p. 71
• Table 4 · p. 72
• Table 5 · p. 72
• Table 6 · p. 73
• Table 7 · p. 73
• Table 8 · p. 73
• Figure 6 · p. 74
• Table 9 · p. 74
• Table 10 · p. 74
• Figure 7 · p. 75

Argument and organization

1. Introduction; 1 Background; 2 What and how can GNNs learn?

   Separates representation from learnability and builds a certificate-controlled extrapolation framework.

2. 3 What GNNs cannot learn; 4 Limitations and future directions

   Distinguishes expressivity obstructions from failure of sufficient covering conditions and optimization guarantees.

3. 5 Experimental study; 6 Conclusion

   Organizes size generalization, architecture and regularization tests as three explicit questions.

Problem, claim and contribution

The central distinction is whether a representable algorithm can be learned from finite examples with worst-case extrapolation, rather than whether a GNN merely expresses its computation.

Introduction, pp.1-2 · Main paper

Argument and section order

A general covering argument precedes aggregation-specific results and a constructive Bellman-Ford case, followed by negative examples and limitations before experiments.

Sections 2-5, pp.4-8 · Main paper

Figures, captions and visual explanation

The conceptual diagram links a graph-to-tree representation with the covering argument; the results page separates a training-threshold plot from architecture and regularizer tables with three-seed variability.

Figure 1, p.5; Figure 2 and Tables 1-2, p.9 · Main paper

Tables, comparisons and evidence

The empirical questions test whether optimization and regularization behave as hoped, while the theorem itself is conditional on sufficiently small regularized loss and does not guarantee optimizer convergence.

Limitations and Q1-Q3, p.8; results, p.9 · Main paper

Appendix and reproducibility

The constructive path training set is diagrammed beside the formal theorem, which exposes exponential depth-dependent scales and a scalar aggregation restriction; later setup records actual dimensions and Adam settings.

Appendix E.3-E.4, pp.26-27; Appendix N, pp.70-71 · Main paper

Clarity and writing conventions

The negative section carefully says possibly not learnable where its sufficient conditions fail, avoiding a universal impossibility claim from a missing covering property.

Section 3.2, p.8 · Main paper

What to reuse—and what not to infer

Transferable lesson: Separate expressivity, conditional learnability, dataset construction and optimization success, and carry the same distinctions through the negative results and experimental questions.

Boundary: Arbitrary graph size does not mean arbitrary algorithm depth: the Bellman-Ford result learns fixed K steps under stated architecture, certificate and loss conditions, with potentially prohibitive depth-dependent scales.

Apply this lesson using the argument and evidence worksheet.

Inspection record and sources

Checked

2026-10-07

Reading status

Writing-focused manuscript scan + selected visuals inspected

Main text

Writing-oriented scan of the main argument through physical p.9, with focused physical-page text inspection on 1, 2, 3, 4, 5, 6, 7, 8, 9. Framing, section progression, mechanism/proof explanation, displays, comparison conditions and conclusions were inspected. This is not exhaustive technical reading, proof verification or reproduction.

Appendix / supplement

Appendix organization and main-text pointers were checked; focused text inspection of physical pages 13, 20, 26, 27, 30, 70, 71. Remaining appendix proofs and details were not exhaustively read. No separately linked supplement inspected.

Visually inspected PDF pages

5, 9

This is a writing-focused scan of the manuscript and the stated supplementary scope: framing, organization, visual explanation, evidence presentation and wording. It is not a line-by-line proof audit, reproduction of results or exhaustive scientific review.

• Published proceedings PDF, PMLR volume 306, retrieved 2026-10-07 · 76 pages