When topology becomes evidence

A dataset becomes a graph when its units have identities and its relations carry task-relevant structure. Write a graph as G = (V, E). The set V contains nodes such as atoms, accounts, documents or services. The set E contains relations such as bonds, transfers, citations or dependencies. Node v may have features x_v; edge (u,v) may have features e_uv, including type, direction, time or weight.

The graph-network literature frames this as a relational inductive bias: the architecture assumes that entities, relations and compositions matter, rather than forcing a generic learner to rediscover those regularities from flattened input.[1] That bias can improve sample efficiency and generalisation when it matches the data-generating process. It can also impose the wrong computation when edges are administrative, incomplete or unrelated to the target.

First name the prediction object

A graph does not imply one kind of answer. A node-level task predicts something about each entity, such as a service state. Relabelling node identifiers should relabel outputs in the same way, a property called permutation equivariance. A link-level task predicts whether, when or how two entities relate. A graph-level task predicts a property of the whole structure, such as a molecule’s energy or whether a dependency network contains a vulnerable configuration; its output should normally be invariant to node renaming.

The distinction decides what evidence must arrive where. Node classification needs a receptive field around each target node. Link prediction needs representations for two endpoints and often their enclosing subgraph, while avoiding the target edge itself leaking into the input. Graph prediction needs a readout that preserves task-relevant multiplicity and structure across all nodes. Calling all three “graph learning” can hide very different failure conditions.

A table remains useful inside every case. Node and edge attributes are still tables, and a relational database can store the complete graph without loss. The decisive question is computational: does the predictor process entities independently, consume precomputed relational summaries, traverse explicit relations or learn a joint function over the structure? Graph storage and graph reasoning are separate design choices.

The relational necessity test

Let X denote the multiset of node-feature rows and E the edge set. Suppose two valid cases have the same X but different edges, E₁ and E₂, and the target satisfies y(X,E₁) ≠ y(X,E₂). Any model whose input is only X must return the same value for both cases. It therefore cannot be correct on both, regardless of capacity or optimisation.

Thought experiment 1: rewire without changing anyone

Hold every node feature, label frequency and train-test membership fixed. Randomly rewire only the edges while preserving each node’s degree. If the true task is “predict a node’s own colour from its temperature”, the correct answers should not change. If the task is “predict whether a signal can reach the node within three hops”, many answers should change. This single intervention separates the existence of a graph from the relevance of its topology.

Degree-preserving rewiring is useful because it prevents a cheap explanation. A model cannot claim success merely because high-degree nodes are more likely to have one label. Yet even this intervention must respect the domain. Rewiring chemical bonds may create invalid molecules; rewiring transaction edges may violate time or account type. The test needs a valid counterfactual generator, not arbitrary corruption.

An edge is an observation, not an ontological guarantee

Some edges are direct measurements, such as a recorded transfer or chemical bond. Others are inferred by entity resolution, similarity thresholds, co-occurrence windows or business rules. These constructions have false positives, false negatives and effective times. A message-passing model usually treats the supplied adjacency as the route along which information may flow, so graph-construction errors become computational errors before learning begins.

Absence also needs a declared meaning. In a complete molecular graph, no bond between two atoms may be meaningful. In a social or enterprise graph, a missing edge may mean only that the relation was unobserved. Treating unobserved as false creates a closed-world assumption that can distort negative sampling and neighbourhood statistics. Edge confidence can be represented as a feature, but a confidence score does not repair systematic missingness.

Direction and time are equally causal. A payment from A to B is not the same event as a payment from B to A. A dependency from service A to service B may mean that A fails when B fails, so messages should travel against the drawn operational arrow for one prediction and with it for another. An edge that becomes known after the prediction time cannot authorise a historical inference. The graph builder therefore defines part of the hypothesis class.

Negative control: when the graph is unnecessary

Now define the label of each account as whether its own synthetic balance exceeds a threshold. Keep balances fixed and apply every topology from Figure 1. The answer for account 11 is unchanged. A multilayer perceptron on the row has all required evidence. A graph model may match it, but any gain is likely due to regularisation, leakage, extra tuning or chance rather than relational necessity.

Controlled comparisons have found exactly this warning in real graph benchmarks: under uniform experimental procedures, structure-agnostic baselines can remain competitive, and some datasets do not show that graph structure is being exploited.[11] “The data has links” is therefore a schema observation, not a model-selection result.

flowchart LR
  A["The duplicated account table"] --> B["When topology becomes evidence"]
  B --> C["How message passing computes<br/>on relations"]
  C --> D["What local aggregation cannot<br/>carry"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#7B4CD8,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

How message passing computes on relations

Message passing turns the edge set into a repeated local computation. Each node begins with a state h_v⁽⁰⁾ = x_v. At layer ℓ, it constructs messages from neighbours, combines those messages with an order-insensitive aggregator, and updates its state. Gilmer and colleagues unified a family of molecular models under this message-passing neural-network form.[2]

A minimal worked example

Consider three nodes in a path, A-B-C. Their scalar starting states are 1, 0 and 0. At each step, retain 20 per cent of a node’s old state and take 80 per cent of the mean of its neighbours. After one step, the states are 0.2, 0.4 and 0: B averages A and C before applying the 0.8 neighbour weight, while C can hear only B’s old zero. After two steps, C is 0.32. The signal has travelled two graph hops through two local updates.

This reveals the operational meaning of depth. A one-layer model cannot make C depend on A unless a direct edge, global feature or alternative mechanism shortens the path. A two-layer model can, but it has also mixed every intermediate neighbourhood twice. More layers increase reach and simultaneously increase opportunities for dilution, noise and loss of identity.

Why the aggregate ignores order

Node identifiers are usually arbitrary. Relabelling accounts 3 and 8 should relabel their outputs, not change the underlying prediction. A sum, mean or max over neighbours gives the same result however the neighbour list is ordered. Graph-level readouts similarly aggregate node states to produce a result invariant to node numbering. This symmetry is a useful prior when identity names have no intrinsic meaning.

The cost is information loss. A mean cannot distinguish one neighbour with value 2 from two neighbours with value 2 unless degree is supplied elsewhere. A max discards multiplicity. A sum preserves multiplicity but entangles count and magnitude. Xu and colleagues showed that common neighbourhood aggregators differ in discriminative power, and that suitably injective aggregation can match the one-dimensional Weisfeiler-Leman test within the standard message-passing class.[5]

From local updates to graph convolution

Kipf and Welling’s graph convolutional network combines node features with a degree-normalised adjacency operator, giving a scalable local model whose cost is linear in the number of edges for a layer.[3] GraphSAGE learns aggregating functions that can generate representations for previously unseen nodes rather than assigning a fixed embedding to every training identity.[4] These are different implementations of the same broad intuition: reuse one local rule across the graph.

The simulator below strips away learned weights so topology is visible. It uses h^(t+1) = ρh^(t) + (1−ρ)Ph^(t). Here h^(t) is the vector of node activations after t steps, P is the row-normalised operator that averages each node’s neighbours, and ρ is the retained share of the old state. Repeated application weights walks through the graph. Increasing ρ slows diffusion; increasing t admits longer walks.

from collections import deque
from math import isclose

N = 12

def edges(name):
    if name == "line":
        return [(i, i + 1) for i in range(N - 1)]
    if name == "ring":
        return edges("line") + [(N - 1, 0)]
    if name == "star":
        return [(0, i) for i in range(1, N)]
    if name == "two_communities":
        result = []
        for start, stop in ((0, 6), (6, 12)):
            result += [(i, j) for i in range(start, stop)
                               for j in range(i + 1, stop)]
        return result + [(5, 6)]
    raise ValueError(name)

def propagate(name, steps=4, rho=0.2, source=0):
    neighbours = [[] for _ in range(N)]
    for u, v in edges(name):
        neighbours[u].append(v)
        neighbours[v].append(u)
    state = [0.0] * N
    state[source] = 1.0
    history = [state.copy()]
    for _ in range(steps):
        state = [
            rho * state[v] + (1 - rho) *
            (sum(state[u] for u in neighbours[v]) / len(neighbours[v]))
            for v in range(N)
        ]
        history.append(state.copy())
    return history

def feature_only_label(target_feature):
    return int(target_feature > 0.5)

# Positive case: same node features, different edges, different target state.
values = {
    name: propagate(name, steps=4)[-1][11]
    for name in ("line", "ring", "star", "two_communities")
}
assert values["line"] == 0.0
assert values["ring"] > 0.1
assert values["star"] > values["ring"]
assert values["two_communities"] > 0.0

# Negative case: topology cannot change a target determined by its own feature.
target_feature = 0.8
labels = {name: feature_only_label(target_feature) for name in values}
assert len(set(labels.values())) == 1

print("step-4 target activation")
for name, value in values.items():
    print(f"{name:18s} {value:.6f}")
print("feature-only labels", labels)
print("all tests passed")

What local aggregation cannot carry

Message passing solves a representational omission by introducing relations. It does not make every graph property easy. Its strongest bias, local repeated aggregation, creates three different failure mechanisms that are often merged under the vague claim that “deep GNNs do not work”. Keeping them separate changes the remedy.

Distance: the receptive field is a contract

After one ordinary message-passing layer, a node can depend on one-hop neighbours. After L layers, it can depend on nodes within L hops. This statement is precise only for the declared graph. Adding a virtual node, rewiring, positional features, global attention or precomputed path statistics changes the communication graph and therefore the radius.

Depth should follow a task-distance distribution, not a fashionable architecture. Measure the shortest relation path between evidence and decision for positive cases. If decisive evidence commonly lies ten hops away and the chosen model has three local layers, failure is designed in. Conversely, adding ten layers to a two-hop task increases mixing without adding relevant reach.

Oversmoothing: when repeated agreement erases identity

For a simple mean-propagation operator, repeated updates act like diffusion. Connected nodes move towards similar values, especially when the graph has strong mixing. Li, Han and Wu showed that the graph convolution in a GCN can be understood as Laplacian smoothing, which helps nearby nodes share signal and creates concern about oversmoothing with depth.[7]

The mechanism is not merely “too many layers”. Residual connections, normalisation, nonlinear updates, edge types and supervision can preserve distinctions. A recent position paper cautions that oversmoothing, oversquashing, heterophily and long-range difficulty should not be treated as universal or interchangeable explanations.[14] The operational test is whether node representations required to differ become less separable as propagation depth increases.

Oversquashing: a topology can have more reach than bandwidth

A binary tree illustrates the mismatch. The number of leaves within k hops of the root grows exponentially, yet a conventional message-passing layer compresses their combined evidence into a fixed-width root vector. If the target depends on a precise configuration across many leaves, each leaf’s influence may become vanishingly small even though every leaf is technically within the receptive field.

Alon and Yahav analysed this long-range bottleneck as over-squashing and demonstrated failures to fit tasks requiring distant interaction.[8] Topping and colleagues linked the problem more precisely to graph bottlenecks using an edge-based curvature analysis and tested curvature-guided rewiring.[9] Rewiring, global attention, hierarchy and larger states are plausible interventions, but each changes cost, invariance or edge semantics.

Expressivity: some different graphs look locally identical

Consider a cycle of six nodes and two disconnected triangles. Give every node the same initial feature. Every node in both graphs has two neighbours with the same feature. After one message-passing layer every node still has the same state; by induction this remains true at every layer. A sum readout sees six copies of the same vector in both cases.

Yet the graphs differ in a decision-relevant property: one is connected and the other is not. Standard message-passing GNNs are bounded by the one-dimensional Weisfeiler-Leman test in their ability to distinguish graph structures, as formalised independently by Xu and colleagues and by Morris and colleagues.[5][6] The limitation can be broken with additional identifiers, positional or structural encodings, higher-order states, subgraphs or global mechanisms, but those are extra information or computation.

Thought experiment 2: reverse what an edge means

Keep the same graph and node features. In world A, an edge means “similar accounts tend to transact”. In world B, it means “buyer and seller occupy complementary roles”. A mean aggregator that pulls neighbours together helps in the first world and can destroy the class boundary in the second. The topology did not become irrelevant; the semantic relation changed from homophilous similarity to heterophilous interaction.

Research on low-homophily graphs shows that popular GNNs can be outperformed by models that ignore the graph, while designs that separate ego and neighbour states or combine different neighbourhood orders can recover value.[10] An edge is not an instruction to average. Direction, type, sign, time and role determine the appropriate message.

stateDiagram-v2
  [*] --> Claim
  state "First name the prediction object" as Claim
  state "The relational necessity test" as Test
  state "Thought experiment 1: rewire<br/>without changing anyone" as Revision
  Claim --> Test: expose mechanism
  Test --> Decision: evidence survives
  Test --> Revision: rival survives
  Revision --> Claim: narrow or rebuild
  Decision --> [*]

How a graph earns its place in a system

A graph model should enter an architecture through evidence, not visual plausibility. The strongest test is a ladder in which each extra relational capability must beat the simpler level below it under the same data boundary and tuning budget.

Production-shaped worked scenario: a payment-service dependency graph

Consider a synthetic technology estate supporting payment processing. Nodes represent services, queues, databases and external gateways. Directed edges represent “depends on”, not generic similarity. At 10:00, each node has point-in-time telemetry: error rate, latency, saturation and deploy version. The task is to rank services likely to experience a downstream failure during the next fifteen minutes after a gateway incident.

A row baseline sees each service’s own telemetry. A feature-engineered baseline adds counts such as number of unhealthy direct dependencies and minimum distance to the incident. A message-passing model sends direction-aware messages along dependency edges, retaining edge type and observation time. A global model additionally allows long-range interaction or uses positional encodings. All four are evaluated on later incidents, never on a random split of nodes from the same incident.

The graph can win for a legitimate reason: two services with identical local telemetry may occupy different positions relative to the failing gateway. But it can also win illegitimately. If an edge added after 10:00 is included, the future has leaked into the input. If the dependency inventory is more complete for high-priority services, topology encodes an operational selection process. If train and test contain the same incident’s neighbouring nodes, message passing can carry labels across the split.

The graph admission protocol

The following instrument is a practitioner synthesis developed for this paper. It converts “graph-shaped data” into a sequence of falsifiable gates. A failure does not always reject graphs; it identifies the mechanism that must be added or the claim that must be narrowed.

A baseline ladder that can attribute the gain

Start with a row model using only point-in-time node features. Add hand-crafted relational summaries such as degree, typed neighbour counts, shortest valid distance or motif counts. Then train the same graph architecture on shuffled or semantically invalid edges. Finally, train on the true graph. If the true-edge model does not beat the shuffled-edge control, it has not shown use of topology. If hand-crafted summaries match it, the graph may still be useful, but the claimed mechanism is simpler than end-to-end message passing.

Match hyperparameter search, parameter budgets and data splits. Errica and colleagues’ large controlled comparison shows why this matters.[11] Use application-shaped temporal or domain splits where possible. The Open Graph Benchmark was designed around standardised evaluators and meaningful application-specific splits because random partitions can hide scale and out-of-distribution difficulty.[12]

Minimal worked example: hold the rows fixed and move one edge

Consider four nodes with identical scalar features. The target for node D is one only when it is connected, through exactly one intermediate node, to source A. In the first graph the path is A to B to D; in the second, only the edge B to D is replaced by C to D. The feature table is unchanged, but the correct label changes. A row model must give the same answer to both graphs. Two rounds of typed message passing can distinguish them because the source signal reaches D only along the valid path.

Now run the negative control. Replace the four identical features with a flag on D that directly states the target. The row model becomes sufficient and the edge intervention adds no information. The contrast shows what the graph has earned: not general superiority, but access to a relation that the table deliberately withholds. It also reveals the required depth. One message-passing round cannot carry A's signal across a two-edge path, so a one-layer failure does not refute relational necessity.

Intervene on the graph builder, not only the neural layers

Production graphs are inferred objects. Identity resolution merges records, event windows decide whether a relation still exists, and direction or type determines which message is legal. These choices can create a larger causal effect than attention weights or hidden width. Test them as model parameters. Split one uncertain entity, expire one stale edge, reverse one directional relation and withhold one high-degree hub. Record which predictions change and whether confidence responds.

A useful perturbation preserves the competing explanation. Randomly deleting edges can make every method worse without showing that the declared relation matters. Prefer matched interventions: swap an edge for another with the same degree and timestamp but different semantics, or preserve node features while changing only the path that carries the target evidence. If the graph model survives because a correlated node feature still reveals the answer, the topology claim remains untested.

Authority and uncertainty travel on different channels

An edge can state evidence without granting authority. A payment-service dependency may justify propagation of an incident signal, but it does not authorise one service owner to change another service. Likewise, a customer-account link may support investigation while remaining too uncertain to license an adverse action. Keep relation type, provenance, confidence, effective time and permitted use in the graph contract. Message passing can combine evidence; a deterministic policy boundary must still decide which effects are allowed.

When relations are uncertain, compare three treatments. A hard graph admits or rejects each edge. A weighted graph passes a confidence-scaled message. An ensemble samples plausible graphs and exposes prediction variance. These choices answer different questions. Weighting can hide uncertainty by turning it into one smooth number, while sampling can show that several graph completions support incompatible decisions. If that disagreement crosses a consequence threshold, abstention or evidence acquisition is more defensible than another propagation layer.

The operating test is a graph-version replay

For every released decision, preserve the effective graph version, feature snapshot, model version and target policy. Rebuild the same graph from its source events and verify that the prediction is reproducible. Then replay with corrections that arrived later, such as a merged identity being split or an edge being superseded. The difference separates what the system could know at decision time from what later became true.

This replay also defines the failure boundary. If the graph cannot be reconstructed, attribution is lost even when the model is accurate on average. If graph construction changes faster than evaluation can be refreshed, the benchmark no longer represents the operating system. A graph model should therefore be released with lineage, temporal splits, perturbation tests and a simpler fallback, not as a neural component isolated from the relation-building process.

When local plus global is the right answer

A graph Transformer or hybrid can combine real-edge message passing with global attention and positional or structural encodings. GraphGPS is one published recipe that explicitly combines local message passing, global attention and encodings, with experiments across sixteen benchmarks.[13] This is a competing mechanism, not an automatic upgrade. Global interaction can reduce underreaching while increasing computation and weakening the clean causal meaning of an edge-routed path.

The choice should follow the failure diagnosis. Use more depth for genuinely local multi-hop dependencies that remain stable. Use typed or directional messages when relation semantics differ. Use global or hierarchical mechanisms when long-range evidence is common. Use higher-order or positional structure when the target exceeds one-dimensional Weisfeiler-Leman expressivity. Use no graph when the negative control shows that entity features already determine the answer.

Open hypothesis: topology sensitivity predicts useful graph gain

A discriminating experiment would generate families of graphs where node features, degree distribution and label balance remain fixed while only task-relevant motifs, path lengths and bottlenecks vary. Compare row models, relational summaries, message-passing networks and local-global hybrids under equal compute. The result would not crown one architecture. It would test whether a measurable causal property of the task predicts when relational computation earns its cost.

Compact glossary

Topology

The pattern of connections, independent of the labels used to name nodes.

Message passing

A repeated local rule that constructs, aggregates and updates information along edges.

Homophily

A tendency for connected nodes to share relevant features or labels. It is task-specific, not an intrinsic virtue.

Oversmoothing

Loss of useful distinction among node states under repeated propagation.

Oversquashing

Loss of sensitivity when many distant signals are compressed through limited paths and fixed-width representations.

1-WL

The one-dimensional Weisfeiler-Leman refinement used as a reference for standard message-passing expressivity.

sequenceDiagram
  participant Q as Question
  participant M as Mechanism
  participant E as Evidence
  participant D as Decision
  Q->>M: The duplicated account table
  M->>E: First name the prediction object
  E-->>M: compare rival explanations
  E->>D: Admit the graph only when edges change the answer
  D-->>Q: revise scope or act

Admit the graph only when edges change the answer

The duplicated table gives the durable intuition. When two valid worlds have identical entity features and different targets because their relations differ, a row-only representation has thrown away evidence. A graph restores that evidence by preserving identity and relation. Message passing then supplies a reusable local computation whose symmetry matches arbitrary node ordering.

That mechanism has a defined reach and a finite channel. It can underreach, smooth away identity, squash distant signals, mix incompatible roles and fail to distinguish graphs that are globally different but locally identical. These are not reasons to reject graphs. They are reasons to state the model’s contract.

The changed architecture decision is to require two proofs. First, a topology intervention must show that relations are necessary beyond node features and simple summaries. Second, the chosen computation must show that it can carry the relevant relation across the observed distances, semantics, bottlenecks and shifts. Only then has a graph earned its place as more than an attractive drawing.