A · Foundations

Message passing, WL expressivity, over-smoothing, transformers

B · Beyond pairs

Hypergraphs, sheaves, temporal graphs, generation

C · Learning regimes

Embeddings, self-supervision, communities, reduction, federation

D · Generality

Foundation models, LLMs, knowledge graphs, databases

E · Trust

Attacks, privacy, explanations, uncertainty, anomalies

F · Social systems

Opinion dynamics, influence, LLM societies, the X API

G · Algorithms & science

Neural CO, algorithmic reasoning, molecules, brains, weather

H · Logic

GNNs as logics, rule learning, neuro-symbolic

I · Threads

Evaluation crisis, homophily, quantitative theory, (I+L)⁻¹

J · Getting involved

Reading path, thesis openings, exercises

How to read it

Each part: intuition → math → history → what 2025–26 audited → open problems. Dark tiles are closest to your research.

01

Theory became quantitative

It now measures how hard a task is, not only whether two graphs can be told apart.

Message Passing Complexity (NeurIPS 2025 spotlight) · Which Algorithms Can GNNs Learn? (ICML 2026 oral)

02

Generality comes from priors

Transfer works when models share a prior or an invariance — not from scale alone.

GraphPFN (ICML 2026) · Relational Transformer, zero-shot (ICLR 2026)

03

LLMs act on graphs

Letting the LLM write code over the graph beats describing the graph in a prompt.

Actions Speak Louder than Prompts (ICLR 2026 oral) · agentic Graph-R1 (ICML 2026)

1736

Euler’s Königsberg bridges: the first graph theorem

1934

Moreno’s sociograms: friendship drawn as a network

1946

Heider’s balance theory; formalised by Cartwright–Harary 1956

1959

Erdős–Rényi random graphs: the first null model

1968

Weisfeiler–Leman colour refinement — later the yardstick for GNNs

1973–74

Granovetter’s weak ties; DeGroot’s opinion averaging

1990–92

Friedkin–Johnsen stubborn opinions; Cai–Fürer–Immerman limits of WL

1998–99

Small worlds, PageRank, scale-free networks

2002–03

Girvan–Newman communities; Kempe–Kleinberg–Tardos influence

2006–11

Markov logic; modularity; WL kernel; SBM detectability threshold

2009

Scarselli et al.’s fixed-point GNN

2013–14

TransE; spectral CNNs on graphs; DeepWalk

2016–17

ChebNet, node2vec; GCN, MPNN, GraphSAGE

2018

GAT, Nettack, GraphRNN, relational inductive biases

2019–20

GIN = 1-WL; GNNs = graded modal logic; TGN; DGI

2021–22

Over-squashing; Graphormer, GraphGPS; sheaf diffusion

2023

Graph prompting, TGB; heterophily benchmark leakage found

2024

GraphRAG, ULTRA, OFA; RelBench; “GFMs are already here”

2025

GNN+ matches transformers; LLMs trained with RL on graphs

2026

Audits everywhere; GraphPFN; provable size generalisation

Spectral line — signal processing

2014 · Bruna et al. Convolution in the Laplacian eigenbasis. Not local, O(n²), tied to one graph.

g ⋆ x = U diag(θ) Uᵀ x, L = UΛUᵀ

2016 · ChebNet. A degree-K Chebyshev polynomial: exactly K-hop local, O(K|E|), no eigendecomposition.

2017 · GCN. Set K = 1 and simplify.

Spatial line — recursion

2009 · Scarselli et al. Iterate node states to a fixed point.

2017 · Gilmer et al., MPNN. Everything is message → aggregate → update:

mᵥ = Σ_{u∈N(v)} M(hᵥ, hᵤ, e_uv) hᵥ′ = U(hᵥ, mᵥ)

GraphSAGE, GAT and GIN are settings of this one template.

What it really is

A first-order low-pass filter. Depth stands in for polynomial order.

SGC (2019) removed the nonlinearities — Âᴷ X W — and often matched GCN.

So: GCN ≈ smoothing + linear classifier. Over-smoothing is already visible here.

COMBINATORICS

MPNN = 1-WL

Message passing is at most as discriminating as colour refinement, and reaches it with injective updates.

Xu et al.; Morris et al. 2019

LOGIC

= graded modal logic

GNN node classifiers capture exactly formulas built from ◇≥k φ: “at least k neighbours satisfy φ”.

Barceló et al. ICLR 2020

ALGEBRA

= tree homomorphisms

Two graphs are 1-WL-equivalent iff they have equal homomorphism counts from every tree.

Dell, Grohe, Rattan 2018

ICML 2024 · position

Morris, Frasca, Dym, Maron, Grohe, Jegelka et al.: theory is too focused on “coarse-grained expressive power”; balance it with generalisation and optimisation.

Davidson & Dym · venue unconfirmed

Graphs that 1-WL separates in three rounds can be practically inseparable at finite precision. Separation quality matters.

NeurIPS 2025 · spotlight

Message Passing Complexity: real tasks “rarely require expressivity beyond the basic WL test”. A continuous difficulty measure that also captures over-squashing.

ICML 2026 · oral

Which algorithms can GNNs learn? Conditions under which training on small graphs provably generalises to any size — shortest paths, MST, knapsack — and proofs that some tasks are unlearnable.

Over-smoothing

Âᴸ collapses toward rank one: every node ends up with the same state. Dirichlet energy tr(Xᵀ L̃ X) decays exponentially.

Named by Li, Han & Wu 2018 · proved by Oono & Suzuki · attention does not stop it

Over-squashing

(Âᴸ)ᵥᵤ is tiny across bottlenecks: an exponentially growing receptive field is squeezed into one fixed-width vector.

Alon & Yahav 2021 · curvature (Topping 2022) · effective resistance (Di Giovanni 2023)

The gold bridge: negative curvature, high resistance

A GCN averages neighbours. That helps when neighbours share labels (homophily) and hurts when they differ (heterophily): fraudsters linking to victims, dunk quote-tweets, dating graphs.

THE AUDIT · ICLR 2023

Platonov et al.: Squirrel and Chameleon contain duplicate nodes leaking between train and test.

On cleaned data and five new heterophilous datasets, plain GNNs with residual connections match or beat specialised heterophily models.

ICLR 2023

Heterophily benchmarks leak; simple GNNs win on clean data (Platonov et al.)

2023

Basic tuning closes most of the Long Range Graph Benchmark gap (Tönshoff et al.)

ICLR 2026

“Universal statements … not always true”: refuted by simple formal counterexamples (Arnaiz-Rodriguez & Errica)

Jan 2026

Over-smoothing “mostly uncorrelated” with accuracy; useful information is usually local (Kormann et al., venue unconfirmed)

NeurIPS 2026

GRIP: four axioms for a truly long-range task; a popular curvature notion is uncorrelated with performance

2020

Neighbour-restricted attention + Laplacian encodings (Dwivedi & Bresson)

2021

Graphormer: full attention with shortest-path biases; wins OGB-LSC

2022

GraphGPS: local MPNN ∥ global attention ∥ encodings

2024

Graph Mamba: needs a node order, breaks permutation invariance

The symmetry problem

Eigenvectors are defined only up to sign — and up to rotation for repeated eigenvalues. SignNet: ρ([φ(vᵢ)+φ(−vᵢ)]ᵢ) is universal for sign-invariant functions; BasisNet handles multiplicity.

The key insight

A transformer is a GNN on the complete graph. The input graph enters only through encodings and biases — so its power is theirs.

8 / 14

graph-level datasets where “GNN+” ranked first; top three on all 14

Luo, Shi & Wu gave GCN, GIN and GatedGCN six standard techniques:

…and they ran several times faster. Companion position (ICML 2025): “Graph learning will lose relevance due to poor benchmarks.”

The learnability triangle

Which inductive biases make a WL-separable target learnable by SGD from few samples?

Task-side theory

Dataset statistics that say where label-relevant information sits and how far it travels.

When attention earns its cost

No verified 2026 paper settles “transformer vs GNN”; large heterogeneous graphs are the open case.

Precision and uniformity

What one fixed network computes on graphs of every size, at float precision (see Part H).

Hodge Laplacians

Lₖ = Bₖᵀ Bₖ + Bₖ₊₁ Bₖ₊₁ᵀ

Edge signals split into gradient + curl + harmonic parts. ker Lₖ ≅ Hₖ: harmonic flows detect holes.

Hypergraph convolution

X′ = σ(Dᵥ^−½ H W Dₑ⁻¹ Hᵀ Dᵥ^−½ X Θ)

HGNN (2019). AllSet recasts layers as two multiset functions: node → hyperedge → node.

History

2021 MPSN: a simplicial WL strictly stronger than 1-WL; CW networks attach 2-cells to rings.

2022–24 Combinatorial complexes unify all of these; ICML 2024 position: “TDL is the new frontier”.

Attach a vector space (a stalk) to each node and edge, and a restriction map from node to edge. Two neighbours “agree” when their restricted states match on the edge.

(δx)ₑ = F_{v◁e} xᵥ − F_{u◁e} xᵤ L_F = δᵀδ, ker L_F = H⁰(G; F)

Hansen & Ghrist 2019 · Neural Sheaf Diffusion, NeurIPS 2022

FOR SOCIAL SYSTEMS

Social interaction is often group interaction: threads, co-hashtags, collective adoption.

Battiston et al. (2020) document dynamics pairwise projections cannot produce — explosive and bistable contagion.

On X: user ⊂ thread ⊂ community is a combinatorial complex. TopoBench and DHG-Bench (ICLR 2026) make “does higher-order help?” cheap to test.

DISCRETE-TIME (DTDG)

Snapshots G₁ … G_T. EvolveGCN evolves the weights with an RNN.

CONTINUOUS-TIME (CTDG)

Events (u, v, t, e). The natural form for replies, retweets, quotes.

EDGEBANK · NeurIPS 2022

“Seen before ⇒ positive.”

A training-free lookup that is embarrassingly competitive, because random negative sampling made dynamic link prediction too easy.

TGB (2023): time-split, per-query ranking — model rankings reshuffle across datasets.

T-GRAB (2025): 11 methods fail on periodic, delayed and long-range patterns; EdgeBank wins a counting task.

TGM, ICLR 2026: one library for snapshots and streams; 7.8× faster than DyGLib on average.

MiNT, NeurIPS 2025*: pre-train on many transaction networks, beat per-network models zero-shot on 20 unseen ones.

CRAFT, NeurIPS 2025: no memory, no aggregation — learnable node identities plus cross-attention.

2018

GraphVAE; GraphRNN (BFS order)

2019–22

GRAN; score-based EDP-GNN, GDSS

ICLR 2023

DiGress: discrete diffusion

ICML 2025

DeFoG: discrete flow matching

2025–26

AutoGraph, Graph-GRPO: LLM-ification

The 2025–26 trend

AutoGraph (NeurIPS 2025) flattens graphs into token sequences for a decoder-only transformer — no O(n²) adjacency.

Graph-GRPO (ICML 2026): RL with verifiable rewards on flow models; 95.0% valid-unique-novel on planar graphs in 50 steps.

Evaluation is its own front

MMD rankings flip with the kernel choice (O’Bray et al. ICLR 2022).

PolyGraph Discrepancy (ICLR 2026): train real-vs-fake classifiers; a bounded lower bound on Jensen–Shannon distance.

ACT 1 · GEOMETRY · 2003

Laplacian eigenmaps

min Σ Wᵢⱼ ‖yᵢ − yⱼ‖² s.t. YᵀDY = I

Neighbours should sit close: the bottom eigenvectors of L.

ACT 2 · SAMPLING · 2014–16

DeepWalk, LINE, node2vec

Random walks become “sentences” for word2vec’s skip-gram.

node2vec’s p and q tune walks between BFS (structural roles) and DFS (homophily).

ACT 3 · ALGEBRA · 2018

NetMF

DeepWalk implicitly factorises a log-transformed sum of random-walk matrix powers, roughly log(Σᵣ (D⁻¹A)ʳ D⁻¹). LINE is the one-step case.

Check the exact constants in Qiu et al.’s theorem before reuse.

1 · Mutual information

DGI (2019): make local patches agree with a global summary, against a corrupted graph.

2 · Two-view contrast

GRACE, MVGRL, GraphCL (2020): two augmented views should agree; the best augmentation depends on the domain. BGRL drops negatives.

3 · Masked reconstruction

GraphMAE (KDD 2022): hide node features and reconstruct them — generative SSL returns.

Objective-based

Q = (1/2m) Σᵢⱼ [Aᵢⱼ − kᵢkⱼ/2m] δ(cᵢ, cⱼ)

Modularity (Newman): edges inside communities minus what a degree-preserving random graph would give.

Resolution limit: it cannot see communities with fewer than about √(2m) internal edges; exponentially many near-optima.

Louvain → Leiden: Leiden guarantees connected communities.

Inference-based

Fit a generative model — the stochastic block model — and read communities off its parameters.

Only this view can say when communities cannot be found at all, by any algorithm.

It also tells you how confident to be, and supports model selection for the number of groups.

Sparse symmetric SBM with k groups, average degree c̄, in- and out-group degrees c_in, c_out. Decelle, Krzakala, Moore & Zdeborová (2011):

| c_in − c_out | > k · √c̄

Above this Kesten–Stigum bound, detection beats chance. Below it — for k = 2 — no algorithm does better than guessing.

Exact recovery needs √a − √b > √2 in the log-degree regime; for k ≥ 5 an information–computation gap opens (Abbe 2017).

NeurIPS 2025 D&B

DGCBench

First unified deep-graph-clustering benchmark, motivated by missing ground truth and inconsistent protocols.

ICLR 2026 oral*

CoCo

Low-rank compactness plus cross-view consistency, to capture global relations.

NeurIPS 2025 spotlight

Hedonic games

Communities as stable coalitions in friend/enemy graphs, with new stability notions and complexity results.

THE UNIFYING OBJECT

Effective resistance drives sparsification, bounds over-squashing, and now feeds community detection.

OPEN PROBLEM

Condensed graphs transfer poorly across architectures (GC-Bench). Extend sparsifier-style bounds to learned synthetic graphs.

FedAvg assumes independent samples. A graph split across silos loses the cross-client edges no one can see.

POLITICAL ECONOMY

Federated graph learning is the technical form of data localisation.

Platform data held under national sovereignty regimes is exactly the subgraph setting: the cross-border edges are invisible.

Open problem: formal structural differential privacy is still thin.

FAIR EVALUATION · ICML 2026 GFM WORKSHOP

3 of 9

foundation models beat well-tuned GNNs on ten GraphLand datasets — all three prior-fitted (G2T-FM, TAG, GraphPFN), at much higher inference cost.

The rest “consistently underperform tuned GNNs, often by a wide margin.” Same group built GraphPFN: independent replication needed.

2023 · graph as prose

Serialise the graph into text. NLGraph: reasoning “preliminary” and brittle. Talk like a Graph: accuracy swings with the serialisation.

TAPE, GLEM: LLMs as feature enhancers on text-attributed graphs.

2024 · graph as tokens

Project neighbourhoods into the LLM’s token space with a graph encoder. GraphGPT, LLaGA.

Taxonomies: LLM as enhancer, predictor or aligned partner.

2025–26 · graph as environment

Train with RL on verifiable graph problems (G1), or let the LLM write and run code over the graph.

The neural model plans; the program does the exact combinatorics.

Where the gain is largest

Long-text or high-degree graphs, where prompts run out of tokens.

The surprise

“All interaction strategies remain effective on heterophilic graphs” — against a common assumption.

The philosophical reading

The symbolic–connectionist divide, resolved by delegation: the network writes the program, the program reasons exactly.

INDUCTIVE · NBFNET 2021

Link prediction as a generalised path sum, computed by a learned Bellman–Ford:

h(u,v) = ⊕_P ⊗_{e∈P} w(e)

Covers Katz, PageRank and distance heuristics. ULTRA builds on it to generalise to unseen relations.

1 · Extract

An LLM pulls entities and relations from documents

2 · Cluster

Leiden communities over the entity graph

3 · Summarise

One summary per community

4 · Answer

Map-reduce over summaries for global questions

Accuracy (GraphRAG-Bench, novels)

Blue = graph-based, grey = plain retrieval

Average prompt tokens per query

* The paper’s prose gives a smaller figure than its table: treat the magnitude as uncertain.

Fey et al. (ICML 2024 position) treat a relational database as a heterogeneous temporal graph. RelBench makes it measurable on Amazon, Stack, H&M, F1 and clinical-trial data.

KumoRFM-2 (April 2026) claims ~5% over supervised RelGNN — a vendor claim, not yet replicated.

THE NEURO-SYMBOLIC THROUGH-LINE

Markov logic (2006): the schema is a template for a graphical model.

P(x) = (1/Z) exp(Σᵢ wᵢ nᵢ(x))

RDL (2024): the schema is a template for a computation graph.

Relational transformers (2026): the schema is part of the input — so models transfer across schemas.

ATTACKS

Nettack (KDD 2018 best paper): perturb edges and features against a linearised GCN, keeping the degree distribution “unnoticeable”.

Metattack (ICLR 2019): treat the adjacency as a hyperparameter and differentiate through training.

DEFENCES

Pro-GNN, GNNGuard assume attacks connect dissimilar nodes — a homophily prior.

Mujkanovic et al. (NeurIPS 2022): most defences give little or no robustness once attacks adapt.

Certified: randomised smoothing — honest, but covers only a few edges.

WHERE IT MOVED BY 2026

Graph transformers can be more fragile than MPNNs.

Unlearning APIs become attack vectors.

GNN bot detectors are attacked by node injection and optimal-transport perturbations.

DP-SGD assumes each example is independent. In a GNN one node appears in many neighbourhoods. Fixes: degree-bounded sampling; GAP’s noisy aggregation.

Link stealing: black-box outputs leak edges, because connected nodes predict alike.

UNLEARNING REPEATS THE ROBUSTNESS STORY

POST-HOC

GNNExplainer (2019): learn an edge mask that preserves the prediction. PGExplainer, SubgraphX (Shapley values), counterfactuals.

SELF-EXPLAINING

ProtGNN (prototypes), GSAT (stochastic attention): the explanation is part of the model.

THE CRISES

Masked subgraphs are out of distribution for the model. ICLR 2026: self-explaining GNNs can explain something unrelated to how they decide.

Uncertainty

GNNs tend to be under-confident — the opposite of CNNs (CaGCN, GATS).

Conformal prediction works transductively: a random calibration/test split is exchangeable. It breaks under growth, time and community splits — the normal case for social data.

Fairness

On homophilous social graphs, message passing leaks a sensitive attribute into embeddings even after it is removed.

FairGNN (adversarial), NIFTY (counterfactual stability), EDITS (data debiasing).

Shift

GOOD (2022) made shift measurable. DIR, CIGA search for invariant causal subgraphs; GNNSafe propagates OOD scores.

For social networks, temporal shift dominates — the least mature subarea.

OddBall 2010

Egonet power laws

DOMINANT 2019

Reconstruction error

CoLA 2021

Node–subgraph contrast

BWGNN, ICML 2022

Spectral “right-shift” → band-pass filters

ARC 2024 → 2026

Generalist, zero-shot detectors

One fact, three faces

Spectral right-shift = anomalies are heterophilous = fraudsters camouflage by linking to benign nodes (CARE-GNN).

The audit

GADBench (2023): tree ensembles with simple neighbour aggregation beat most specialised GNNs (supervised). 2026 generalist papers: no confirmed venue, not checked against trees.

Features

Botometer’s account-feature ensembles

Graphs

BotRGCN; TwiBot-22 (~1M users): graph methods lead

LLM bots

ACL 2024: LLM-guided manipulation evades detectors

2026

Coordination and relational traces carry the signal

The arms race continues

Graph-augmented LLM botnets now mimic human network structure too, and graph detectors are attacked by node injection.

A conceptual warning

Bots (automation), coordination (organisation) and misinformation (falsity) are different targets. Conflating them is a common error.

Balance · Heider 1946

Cartwright–Harary (1956): a signed graph is balanced iff every cycle has positive sign product iff it splits into two camps — the ancestor of “polarisation as two-clustering”.

Weak ties · Granovetter 1973

Bridges carry novel information. LinkedIn experiments on ~20M users (Science 2022): an inverted U — moderately weak ties help job mobility most.

Homophily · McPherson et al. 2001

“Birds of a feather”: ties form between similar people. The empirical root of the GNN low-pass prior.

Centrality · Freeman 1977, PageRank 1998

π = α Pᵀπ + (1 − α) 𝟙/n

Physics added null models: small worlds (1998), scale-free (1999).

DEGROOT 1974

x(t+1) = W x(t)

Everyone averages neighbours. Converges to consensus πᵀx(0), weighted by centrality.

FRIEDKIN–JOHNSEN 1990

x(t+1) = ΛWx(t) + (I−Λ)s z* = (I + L)⁻¹ s

Add stubbornness toward an innate opinion s. Disagreement never vanishes.

BOUNDED CONFIDENCE

Deffuant (2000), Hegselmann–Krause (2002): listen only to those within distance ε.

As ε shrinks, opinions fragment into clusters.

Musco, Musco & Tsourakakis (WWW 2018) define, for opinions z with mean z̄:

At the Friedkin–Johnsen equilibrium:

P + D = s̄ᵀ (I + L)⁻¹ s̄

Convex in L — so finding the least polarising network is a convex programme.

THE RECOMMENDER TWIST

Chitra & Musco (2020): a recommender that slightly reweights edges to reduce users’ disagreement sharply increases polarisation.

A filter bubble, derived from first principles: an adversary rewiring L.

NeurIPS 2025 · oral

Opinion intervals from conflicts in signed graphs

Blohm, Chen, Gionis, Neumann. Infer latent opinion intervals consistent with edge signs. Hardness + a PTAS via interval graphs and correlation clustering; recovers German party leanings from co-voting.

ICLR 2026

Online polarisation minimisation via low-rank bandits

Cinus, Kuroki, Miyauchi, Bonchi. Innate opinions unknown; only a scalar P + D per intervention is observed. Regret Õ(max(1/κ, √|V|) √(|V|T)).

NeurIPS 2025

Fast Friedkin–Johnsen computation

Entries of (I + L)⁻¹ count rooted spanning forests. Sampling partial forests gives sublinear-time opinion and P + D optimisation.

Signed networks

Balance theory meets data. Leskovec et al. (CHI 2010): in directed signed data, status theory (“I rate up those above me”) explains more than balance.

SGCN (2018) propagates “friend” and “enemy” embeddings by sign products: the enemy of my enemy…

Misinformation

Vosoughi, Roy & Aral (Science 2018), ~126,000 Twitter cascades: falsehood reached 1,500 people about six times faster and was ~70% more likely to be retweeted — driven by humans, not bots.

Detection moved from content to propagation structure: tree-recursive nets, Bi-GCN, UPFD; coordination networks catch human-run campaigns.

SIMULATION

Generative Agents (2023): a 25-agent Smallville.

OASIS (2024): up to a million agents on simulated X and Reddit, with recommenders and follow graphs. Reproduces herd effects and group polarisation.

ICLR 2026 ORAL · STEERING THE HERD

An LLM planner sits between agents in a Bayesian social-learning chain (Bikhchandani–Hirshleifer–Welch).

Biased planners sometimes deliberately obscure signals; even with no lying and no cherry-picking, mediation shifts welfare substantially.

THE VALIDITY BACKLASH

Micro-to-macro gap: fluent individuals do not imply correct collective dynamics.

Homogeneity: all agents share one pretrained prior. Persona construction alone can drive polarisation.

HUSZÁR ET AL. · PNAS 2022

Twitter’s long-running 1% holdout (~2M accounts on chronological feeds): the mainstream political right was amplified more than the left in 6 of 7 countries.

META 2020 ELECTION STUDIES

Three months of chronological feed did not significantly change polarisation (Science 2023). Cutting like-minded sources by a third did not reduce affective polarisation (Nature 2023).

INFLUENCE RUNS BOTH WAYS

SNA theory analyses agent networks.

Agent networks are controllable — but validity-limited — laboratories for SNA.

33,306

studies across 8,914 venues and 16 disciplines built on Twitter data (“RIP Twitter API”)

2023: free research access ended; Enterprise access priced around $42,000 a month. Output fell about 13% after the change, with more decline expected.

2015

Pointer networks

2017–19

RL constructive heuristics: S2V-DQN, attention model, POMO; NeuroSAT

2019

Learning inside exact solvers: imitate strong branching in SCIP

2023

Diffusion heatmaps: DIFUSCO

The critiques

A GCN-guided MIS search worked as well with random network outputs (ICLR 2022). Greedy beats “physics-inspired” GNNs on MIS. 2026: “classical algorithms still outperform GNNs” on hard random CSPs.

The benchmarks

ML4CO-Bench-101 (NeurIPS 2025): 7 problems, 65 datasets. FrontierCO (venue unconfirmed): real instances to ~10M nodes; best neural TSP solver ~10% off where LKH-3 is near-optimal.

2026 · THEOREMS

Wittig et al. (ICML 2026 oral): sufficient conditions for provable size generalisation — shortest paths, MST, knapsack — and impossibility results.

Learning to execute exactly (Jan 2026, preprint): with bounded degree and finite precision, BFS, DFS and Bellman–Ford run without error w.h.p.

Caveat: reasoners that fit every hint can still “flood prematurely” on longer runs.

Molecules: a symmetry ladder

Permutation (MPNN) → E(3)-invariant (SchNet, DimeNet) → E(3)-equivariant (EGNN, NequIP) → higher body order (MACE) → “foundation” potentials.

2025–26: low test error no longer predicts simulation behaviour; datasets highly redundant.

Brains

BrainGNN, BrainGB. BRep (ICML 2026): correlation-built connectomes are a hand-crafted relic; learn the correlations instead, with a universal-approximation guarantee.

Weather: neural wins

GraphCast (Science 2023): 10-day forecasts in under a minute, beating ECMWF HRES on ~90% of 1,380 targets. GenCast beats the ensemble.

Dense, honest, physical evaluation made the difference.

RULE LEARNING · 1990–91

FOIL’s greedy Horn clauses; Muggleton’s inductive logic programming:

B ∧ H ⊨ E⁺, B ∧ H ⊭ E⁻

STATISTICAL RELATIONAL · 2006–07

Markov logic networks: weighted first-order formulas ground into a graphical model. ProbLog: probabilistic logic programs via weighted model counting.

THE OBJECTION · 1988

Fodor & Pylyshyn: anyone who can think “John loves Mary” can think “Mary loves John”. Networks either fail at this systematicity or merely implement a classical system.

2018

Battaglia et al.: relational inductive biases for “combinatorial generalization”

2020

Kautz’s six neuro-symbolic patterns, from Symbolic[Neuro] to Neuro[Symbolic]

2020–23

Garcez & Lamb: neurosymbolic AI as the “third wave”

RULE

r(x,y) ← r₁(x,z₁) ∧ … ∧ r_T(z_{T−1},y)

MATRIX PRODUCT

M_{r₁} ⋯ M_{r_T} vₓ

Neural LP (2017), with attention over relations

SEMIRING DP

⊕_P ⊗_{e∈P} w(e)

NBFNet’s learned Bellman–Ford

LOGIC

Conditional MPNNs capture a relational graded modal logic over pairs (NeurIPS 2023)

Neural predicates inside logic

DeepProbLog: neural predicates under exact (#P-hard) weighted model counting. Logic Tensor Networks ground first-order logic in t-norms.

Query embedding

GQE, Query2Box, BetaE, CQD trade exact semantics for robustness to missing facts. CQD composes a pretrained link predictor with t-norms and wins with far less data.

Still live

Whether trained weights actually instantiate that fragment — Fodor & Pylyshyn’s “mere implementation” horn, back as explanatory faithfulness.

Explanations as formulas

If a model class equals a logic, every trained model is some formula. Sound Datalog-rule extraction and compiled-GNN benchmarks follow.

LLM reasoning as graphs

CRV (ICLR 2026 oral) classifies chain-of-thought errors from attribution-graph structure; editing single features fixes faulty reasoning.

Graph transformers

Beat GNNs → tuned GNN+ matches them

Heterophily

Needs special models → benchmark leakage

Long range

Needs attention → gap vanishes with tuning

Temporal graphs

Complex models win → EdgeBank, protocol artefacts

Self-supervision

Augmentations help → random GNNs are strong

Foundation models

They transfer → non-PFN models lose

GraphRAG

Graphs help → hurt on simple facts, huge cost

Robustness

Defences work → not under adaptive attack

Unlearning

Methods forget → not practical at scale

Explanations

Self-explanations explain → can be unrelated

Anomaly detection

Specialised GNNs → tree ensembles win

Neural CO

Learned solvers → classical still ahead

Force fields

Low error → does not predict simulation

Graph generation

MMD ranks models → rankings unstable

The rule

Run GNN+, EdgeBank or trees before believing any gain

GCN low-pass propagation

Contrastive smoothness objectives

Pro-GNN, GNNGuard defences

DAPS conformal diffusion

GNNSafe OOD propagation

Fairness leakage

Neighbour-consistency anomaly scores

Friedkin–Johnsen opinion smoothing

THREE ROLES AT ONCE

A modelling prior in GNNs.

An empirical regularity of social graphs (McPherson et al.).

A confound that makes influence unidentifiable (Shalizi–Thomas).

On X data with bots, campaigns and dunk quote-tweets, heterophily is the attack surface — not an edge case.

1

Each agent balances its innate view against neighbours (normalised Laplacian L̃ = I − Â, weight γ):

min ‖z − s‖² + γ zᵀ L̃ z

2

Set the gradient to zero:

z* = (I + γ L̃)⁻¹ s

3

Factor the matrix:

I + γ(I − Â) = (1+γ)(I − γ/(1+γ) · Â)

4

With α = 1/(1+γ):

z* = α (I − (1 − α) Â)⁻¹ s

Low-pass filter

Spectrally FJ applies 1/(1 + γλ): it carries exactly GCN’s homophily bias.

Over-smoothing = consensus

As γ → ∞ (no stubbornness), z* collapses to DeGroot consensus.

Polarisation metric

P + D = s̄ᵀ(I + L)⁻¹s̄ is a quadratic form in the same operator.

Forests

Entries count rooted spanning forests — the basis of the NeurIPS 2025 sublinear algorithms.

Recommenders & agents

Filter bubbles rewire L; 2026 agent-security work reuses stubborn-neighbour dynamics.

A thesis problem

Learn s and L from X interaction data — with signs and partial observability.

Weeks 1–2 · template

Kipf & Welling 2017; Gilmer et al. 2017; Bronstein et al. “Geometric Deep Learning” 2021

Week 3 · expressivity

Xu et al. (GIN) 2019; Barceló et al. 2020; Grohe “Logic of GNNs” 2021

Week 4 · the audits

Platonov et al. 2023; Luo et al. ICML 2025; Arnaiz-Rodriguez & Errica ICLR 2026

Week 5 · new theory

Morris et al. ICML 2024 position; Kemper et al. NeurIPS 2025; Wittig et al. ICML 2026

Week 6 · communities

Abbe’s SBM survey 2017; Decelle et al. 2011; Leiden 2019

Week 7 · opinions

Musco, Musco & Tsourakakis 2018; the NeurIPS 2025 opinion-intervals oral; Cinus et al. ICLR 2026

Week 8 · temporal & bots

Poursafaei et al. 2022 (EdgeBank); TGB 2023; TwiBot-22

Alongside

Shalizi & Thomas 2011; Steering the Herd (ICLR 2026)

1 · OPINIONS UNDER PARTIAL INFORMATION

Learn innate opinions s and the signed graph L from X interactions, then optimise P + D with only partial feedback.

Anchors: NeurIPS 2025 oral, ICLR 2026 bandits, forest sampling.

2 · RELATIONAL SIGNALS AGAINST LLM BOTS

Content signals are dying; coordination structure is the defensible signal. Heterophily and camouflage are first-order, with certified injection robustness.

Anchors: TwiBot-22, BWGNN, 2026 coordination preprints.

3 · LOGIC FOR SOCIAL GRAPHS

Balance, status and stubbornness are already logical or algebraic. Sound rule extraction and learnability bounds for logically definable social predicates.

Anchors: Barceló 2020, temporal-GNN logic NeurIPS 2025, Wittig ICML 2026.

warm-up

Find two connected, non-isomorphic graphs that 1-WL cannot tell apart.

warm-up

Prove a signed complete graph is balanced iff it splits into two hostile camps.

core

Prove P + D = s̄ᵀ(I + L)⁻¹s̄ is convex in L.

core

Derive the k = 2 SBM detectability threshold from the non-backtracking spectrum.

research

What is the heterophilous analogue of Friedkin–Johnsen — and what social behaviour would it model?

research

A sample-complexity bound for learning a graded-modal-logic node classifier with a GNN.

Baselines first: a tuned GNN+, EdgeBank for temporal tasks, tree ensembles for anomalies.

Honest splits: time-based and community-based, with historical and inductive negatives.

Name the homophily role: prior, data property or confound — for every assumption.

Identify before you model influence: Shalizi–Thomas comes first.

Separate the targets: bots, coordination and misinformation are three labels.

Simulations generate hypotheses; real data tests them.

Checked

2025–26 items marked with a venue were checked against conference pages, proceedings or arXiv records. Classic pre-2024 papers use their standard citations but were mostly not re-opened.

Flagged

Unconfirmed venues: FrontierCO, Kormann et al., Davidson & Dym, Arroyo et al., AgentPrune, RelGNN, Griffin, RelGT and most 2026 preprints. Vendor claims (KumoRFM-2) are marked as such.

Gaps

ICML 2026 is thin on robustness, fairness, temporal graphs and opinion dynamics. No verified 2025–26 top-venue papers on influence maximisation, signed GNNs or GNN physics. Absence reflects the search budget, not the literature.