Finally, this lens doesn't consider computation per layer. A typical GNN layer (e.g. a GCN layer) for the edge-based architecture would be more expensive compared to the node-based architecture. It would be nice if "rewiring" ideas in the literature can get best-of-both-worlds.

This echoes a message from recent position papers (e.g. arxiv.org/pdf/2502.14546) that we need better benchmarks for graph-based tasks to "see" fine-grained differences between improved architectures/methods/etc. (This argument has been made more broadly for benchmarks in SciML)

Empirically, on "standard" benchmarks edge embeddings provide only modest benefit---but it's easy to construct (synthetic, diagnostic, but natural) datasets which have a "hub" structure on which edge embeddings perform dramatically better.

The proof techniques are reminiscent of and inspired by techniques in time–space trade-offs in computational complexity, which measure "information flow" between variables in a function. A nice survey if interested here: cs.brown.edu/people/jsava...

In some ways, this supports recent remarks in a recent position paper arxiv.org/abs/2505.15547 that phenomena like oversquashing conflate topological and computational bottlenecks --- and in fact, that their interaction matters a lot.

The separation manifests on graphs with topological bottlenecks (i.e. hub nodes), and when solving the task requires routing information through a narrow cut. The hub nodes need to either have a lot of memory or the length of the protocol has to grow.

We show that there are natural functions computable by edge architectures with constant depth and memory. However, in any node-based architecture, depth x memory has to be Ω(√n), where n = # nodes of the graph. Moreover, without the memory constraint there is *no* separation.

We examine a modest architectural change: edges maintain their own state (common GNNs maintain node states). This change was introduced in the literature mostly to naturally handle edge-centric tasks & edge features---but we show it has representational benefits too.

We introduce an additional resource budget—memory per processor (viewing GNNs as a message-passing protocol), which ≈ models the dimensionality of the hidden representation (at finite precision), similar to the viewpoint in arxiv.org/abs/1907.03199

The Weifeiler-Lehman hierarchy lens classifies GNNs according to their distinguishing power wrt the graph isomorphism problem (see e.g. arxiv.org/abs/2204.07697). While powerful, this lens ignores other computational resources that can influence expressiveness.

Congratulations!