Towards characterizing the value of edge embeddings in Graph Neural Networks
Authors: Dhruv Rohatgi
Tanya Marwah
Zachary Chase Lipton
Jianfeng Lu
Ankur Moitra
Andrej Risteski
Venue: ICML 2025 poster (2025)
Keywords: graph neural networks
theory
representational power
communication complexity
memory tradeoffs
edge embeddings
Primary area: theory->deep_learning
TL;DR: We characterize the added representational power conferred to by edge embeddings in GNNs, considering additional constraints like memory and symmetry.

Abstract: Graph neural networks (GNNs) are the dominant approach to solving machine learning problems defined over graphs. Despite much theoretical and empirical work in recent years, our understanding of finer-grained aspects of architectural design for GNNs remains impoverished. In this paper, we consider the benefits of architectures that maintain and update edge embeddings. On the theoretical front, under a suitable computational abstraction for a layer in the model, as well as memory constraints on the embeddings, we show that there are natural tasks on graphical models for which architectures leveraging edge embeddings can be much shallower. Our techniques are inspired by results on time-space tradeoffs in theoretical computer science.  Empirically, we show architectures that maintain edge embeddings almost always improve on their node-based counterparts---frequently significantly so in topologies that have "hub" nodes.

Towards characterizing the value of edge embeddings in Graph Neural Networks
Dhruv Rohatgi"
Tanya Marwah 2
Zachary Chase Lipton
Jianfeng Lu Ankur Moitra'
Andrej Risteski
Abstract
characterizing the representational limitations stemming from the symmettyypresserye properties of GNNs when the node features are not informative (also called "anonymous GNNs") - in particular, relating GNNs to the Weisfeiler- Lehman graph isomorphism test (Leman & Weisfeiler 1968). Another line of work (Oono & Suzuki 2020) focuses the potential pitfalls of the (over)smoothing effect of deep GNN architectures, with particular choices of weights and -oneaiiea,,,ies, in an effort to explain the difficulties of training deep GNN models. Yet another (Black et al. 2023) focuses on training difficulties akin to vanishing introduced by "bottlenecks" " in the graph topology.
Graph neural networks (GNNs) are the dominant approach to solving machine learning problems defined over graphs. Despite much theoretical and empirical work in recent years, our under- standing of finer-grained aspects of architectural design for GNNs remains impoverished. In this paper, we consider the benefits of architectures that maintain and update edge embeddings. On the theoretical front, under a suitable computa- tional abstraction for a layer in the model, as well as memory constraints on the embeddings, we show that there are natural tasks on graph- ical models for which architectures leveraging edge embeddings can be much shallower. Our techniques are inspired by results on time-space tradeoffs in theoretical computer science. Empir- ically, we show architectures that maintain edge embeddings almost always improve on their node- based counterparts- frequently significantly so in topologies that have "hub" nodes.
In this paper, we focus on the benefits of maintaining and up- dating edge embeddings over the course of the computation of the GNN. More concretely, a typical GNN maintains node embedding h. at each node of the underlying graph. In each layer of the GNN, the embedding at node v is up- dated based on the embeddings at its neighbors. But an alternative paradigm is to maintain data at each edge e of the graph, and update this edge embedding based on the embeddings of the edges that share node with e.
Intuitively, this paradigm seems at least expressive as maintaining node embeddings, since in principle each edge could maintain the embeddings of its incident nodes. Addi- tionally, there may be tasks where initial features are most naturally associated with edges (e.g.. attributes of the rela- tionship between two nodes) or the final predictions of the network are most naturally associated with edges (e.g.. in link prediction, where we want to decide which potential links are true links).
1. Introduction
Graph neural networks (GNNs) have emerged as the domi- nant approach for solving machine learning tasks on graphs Over the span of the last decade, many different architec- tures have been proposed, both in order to improve different notions of efficiency, and to improve performance on vari- cty of benchmarks. Nevertheless, theoretical and empirical understanding of the impact of different architectural design choices remains elusive.
GNNs that fall in the general edge-based paradigm have been used for various applications - including link pre- diction (Cai et al., [202T] Liang et al.) 2025) as well as reasoning about relations between objects (Battaglia et al.) 2016), molecular property prediction (Gilmer al.) 2017
One previous line of work (Xu et al. 2019) has focused
'Department of EECS, Massachusetts Institute of Technol- ogy, Cambridge, MA, USA 'Department of Machine Learning, Carnegie Mellon University, Pittsburgh, PA. USA 'Department of Mathematics, Duke University, Durham, NC, USA. Correspon- dence to: Dhruv Rohatgi <drohatgi @ edu,, Andrej Risteski <aristesk andrew.cmu.cdu..
Choudhary & DeCost 2021), and detecting clusters of com- munities in graphs (Chen et al. 2019) with robust empir- ical benefits. These approaches instantiate the edge- based paradigm in a plethora of ways. However, it is difficult to disentangle to what degree performance improvements come from added information from domain-specific initial edge embeddings, versus properties of other particular archi-
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).

---

Towards characterizing the value of edge embeddings in GNNS
tectural choices, versus inherent benefits of the edge-based paradigm itself (whether representational, or via improved training dynamics).
memory per processor. The lower bound on node message- passing protocols tracks the "flow of information" in the graph, reminiscent of graph pebbling techniques used to prove time-space tradeoff's in theoretical computer science (Grigor' ev 1976 Abrahamson 1991p. See (TeeTeee I] The crucial Lemma 2 can be viewed as an information-theoret
We focus on theoretically and empirically quantifying the added representational benefit from maintaining edge em- beddings. We find that (1) theoretically, for certain graph topologies, edge embeddings can have substantial represen- tational benefits in terms of the depth of the model; and (2) these benefits can be witnessed empirically, even when equalizing for all other architectural and data design choices.
formalization of the celebrated phenomenon of oversquash- ing (Alon & Yahav 2021).
The view from symmetry. Above, we are not imposing any symmerry constraints - that is, invariance of the com- putation at a node or edge to its identity and the identities of its neighbors. Indeed, the edge message-passing proto- col constructed above is highly non-symmetric. However, we show there is (different, but also natural) task where even symmetric edge message-passee better depth/memory tradeoff than node message-passingg protocols. See Theorem 4
2. Overview of results
2.1. Representational benefits from maintaining edge embeddings.
protocols achieve a
Our theoretical results elucidate the representational benefits of maintaining edge embeddings. More precisely, we show that there are natural tasks on graphs that can be solved by shallow model maintaining constant-size edge embeddings, but can only be solved by a model maintaining constant-size node embeddings if it is much deeper.
Importance of the memory lens. The memory con- straints are crucial for the results above. Without memory constraints, we can show that the node message-passing architecture can simulate the edge message- paassag--assingg... archi- tecture, while only increasing the depth by 1 (Proposition 3). Moreover, the symmetric node message- -aasagggg architecture can simulate the symmetric edge message-pass passing architec- ture, again while only increasing the depth by 1. See The- orem We view this as evidence that many fine-grained properties of architectural design for GNNs cannot be ad- judicated by solely considering them through the classical lens of invariance (Xu et al. 2019).
To reason about the impact of depth on the representational power of edge-embedding-basee and node-embeddingg- based architectures, we introduce two local computation models. In the node-embedding case (Definition I). we as- sume each node of the graph G supports a processor that maintains a state with a fixed amount of memory. In one round of computation, each node receives messages from the adjacent nodes, which are aggregated by the node into a new state. In this abstraction, we think of the memory of the processor as the total bits of information each embedding can retain, and we think of one round of the protocol as corresponding to one layer of a GNN. The edge-embedding case is formalized in a similar fashion, except that the pro- cessors are placed on the edges of the graph, and two edge processors are "adjacent" if the edges share a vertex in com- mon (Dfinition 2}. In both cases, the input is distributed across the edges of the graph, and is only locally accessible.
2.2. Empirical benefits of edge- architectures.
The theory, while only characterizing representational power, suggests that architectures that maintain edge em- beddings should have strictly better performance compared to their node embedding counterparts. We test this in both real- life benchmarks and natural synthetic sandboxes.
With this setup in mind, our first result focuses on proba- bilistic inference on graphs, specifically, the task of maxi- mum a-posteriori (MAP) estimation in a pairwise graphical model on a graph G = (V, E). For this task, given edge attributes describing the pairwise interactions ((a,)), the goal is to compute arg m0,, (z) where po (x(x) x exp E ( ((a,b) (Za,
Ablation on GNN benchmarks. We consider several popular GNN benchmarks. Equalizing for all other aspects of the architecture (e.g., depth, dimensionality of the embed- dings), we find that the accuracy achieved by edge- based architectures is always comparable and typically slightly better than that of their node-based counterparts. This con- firms that - all else being equal - the representational advantages of edge-based architectures do not introduce additional training difficulties. However, it suggests that standard benchmarks could be too easy to clearly identify better architectures !
A depth separation between node and edge architectures. We show that there is a graph with (n)) vertices and edges, for which MAP estimation with any node message- passing protocol requires ((v')) rounds, but MAP estima- tion with an edge message passsagg protocol only requires O1) rounds, when both protocols are restricted to O(1)
Details are included in SScciin 8.
Note, the goal of these experiments is not propose new architecture there are already variety of (very computationally efficient) GNNs that some manner maintain edge emheddings.
2

---

Towards characterizing the value of edge embeddings in GNNS
Synthetic stress-tests. Next, we consider two synthetic settings stress test the performance of edge-based archi- tectures. Inspired by the graph topology that provides theoretical separation between edge and node-based pro- tocols (Theorem and [Theorem 4), we consider graphs in which there is a hub node, and tasks that are "naturally" solved by an edge-based architecture, Precisely, we consider a star graph, in which the labels on the leaves are generated by "planted" edge-based architecture with randomly cho- sen weights. The node-based architecture, on the other hand, has to pass messages between the leaves indirectly through the center of the star. Empirically, we indeed observe that the performance of edge-basee based architectures is significantly better. Details are included in Section 8.2
Communication complexity methods to prove repre- sentational separations: Tools from distributed compu- tation and communication complexity have recently been applied not only to understand the representational power of GNNs (Loukas) 2020abb), but also the representational power of other architectures like transformers (Sanford et al. 2024b a). In particular, (Sanford et al. 2024a) draws a con- nection between number of rounds for a MPC (Massively Parallel Computation) protocol, and the depth of attention- based architectures.
GNNs for inference and graphical models: (Xu & Zou 2023) consider the approximation power of GNNs for calcu- lating marginals for pairwise graphical models, if the family of potentials satisfies strong symmetry constraints. They do not consider the role of edge embeddings or memory.
Finally, again inspired by the theoretical setting in Theo- rem I we consider probabilistic inference on free graphs precisely, learning a GNN that calculates node marginals for an Ising model, a pairwise graphical model in which the pair- wise interactions are just the product of the end points. An added motivation for this setting is the fact that belicf prop- agation -a natural algorithm to calculate the marginals- can be written as an edge-based meessage-passing algorithm. Again, empirically we see robust benefits of edge-based architectures over node-based architectures, though we find that directionality is more critical architecture choice. De- tails are included in Section 8.3
4. Setup
We denote the graph associated with the GNN as G (V, E), denoting the vertex set as V and the edge set as E. The graph induces adjacency relations on both edges and nodes. For u, E V and e, E E, we have: v of if (u, E E; u e if = (u,u) for some u E V; and ~ e' if e, share at least one vertex. For all graphs considered in this paper, we assume that (v,0) E E for all v E V, so that adjacency is reflexive. We then define adjacency functions N = NG : VUR + V and M = MM VUE + E as Na == {o veEV:a ~ f) and
3. Related Works
Mc(a) = fe E E:ame]
The symmetry lens GNNs: The most extensive theoret- ical work GNNs has concerned itself with the representa- tional power of different GNN architectures, while trying to preserve equivariance (to permuting the neighbors) of each layer. (Xu et al. 2019) connected the expressive power of such architectures to the Weisfeiler-Lehman (WL) test for graph isomorphism. Subsequent works (Maron et al. 2019 Zhao et al., 2022) focused on strengthening the represen- tational power of the standard GNN architectures from the perspective of symmetries more precisely, to simulate the k-WI. test, which for k: as large as the size of the graph be- comes as powerful as testing graph isomorphism. Our work suggests this perspective is insufficient to fully understand the representational power of different architectures.
Graph Neural Networks. A typical way to parametrize layer I of a GNN (Xu et al. 2019) is to maintain, for each node v in the graph, a node embedding (!), which is calculated in terms of its neighbor set (v) as
a (1+1) = AGGREGATE
10 : MME(()))
(((1)) = COMBINE (Q41) nO))
(1)
for parametrized functions AGGREGATE and COMBINE. These updates can be viewed implementing (trained) message-passing algorithm, in which nodes pass messages to their neighbors, which are then aggregated and combined with the current state (i.e., embedding) of a node, The initial node embeddings h are frequently part of the task specifi- cation (e.g.. vector of fixed features that can be associated with each node). When this is not the case, they can be set to fixed values (e.g., the all-ones vector) or random values.
Two recent papers (Loukas 2020a b) considered properties of GNNs when viewed as "local computation" machines, in which a layer of computation allows a node to aggregate the current values of the neighbors (in an arbitrary fashion, without necessar- ily considering symmetrics). Using reductions from the CONGEST model, they provide lower bounds on width and depth for the standard node-embedding based architec- ture. However, they do not consider architectures with edge embeddings, which is a focus of our work.
GNNs computational machine:
But an alternative way to parametrize a layer of computation is to maintain, for each edge e, an edge embedding (1)
Thhe graph is assumed to be undirected, as is most common in the GNN literature. Dependence of the adjacency functions on G is omitted when clear from context.
3

---

Towards characterizing the value of edge embeddings in GNNs
which is calculated as:
Definition 2 (Fdge message-passing protocol). Let T, B N and let G = (V, F)) be graph. An edge message-passing protocol P on graph G with I rounds and B bits of mem- ory is a collection of functions (ft.))ne(T).neR where ft.
0 11+1) AGGREGATE (N :a E M(e))
_ ((+1)= = COMBINE
de (111)) (1)
x B
x Φ + X' for all L, e, together with a collection
of functions (fu)eetv] where f. : Xg x + {0, 13. For an input E $b the compulation of P at timestep / E [T] is the map P((: E XB defined inductively by: (r(e; I) == ft.e (Pt (() e))e [ee) where Po = 0. We say that P computes a function : &b + {0, 13 on
Recall that M(e) denotes the "neighborhood" of edge e, i.e. all edges a that share a vertex with e.
Local memory-constraingg computation. In order to reason about the required depth with different architectures, we will define mathematical abstraction for one layer of computation in the GNN. We will define two models for local computation, one for each of the edge-embedding and node-embedding architecture. Unlike much prior work on GNNs and distributed computation, we will also have memory constraints - more precisely, we will constrain the bit complexity of the node and edge embeddings being maintained.
inputs I C 6F if T.((Pr(e:T))eemma = g()), for all V E V and all E
Remark 3 (Relation to distributed computation literature). These models are very related to classical models in dis- tributed computation like LOCAL (Linial 1992) and CON- GEST (Peleg, 2000). However, the latter models ignore memory constraints, so we cannot usefully port lower and upper bounds from this literature.
In both models, there is an underlying graph G (V, E), and the goal is to compute a function g : FE + {0, 1) where & is the fixed-size input alphabet, via several rounds of pesssage-psssing on the graph G. This domain of g is & because in both models, the inputs are given on the edges of the graph - the node model will just be unable to store any additional information on the edges. As we will see in Section 5| this is natural setup for probabilistic inference on graphs.
Remark 4 (Computational efficiency). In the definitions above, we allow the update rules ft, St,e to be arbitrary functions. In particular, a priori they may not be efficiently computable. However, our results showing a function can be implemented by an edge pesssage-passing protocol (The] orem 1 Part 2 and (Theorem 4) Part 2) in fact use simple functions (computable in linear time in the size of the neigh- borhood), implying the protocol can be implemented in par- allel (with one processor per node/edge respectively) with parallel time complexity O max, [M(())) On the other hand, for the results showing a function cannot be im- plemented by node message- pessagg-passing protocol (Theorem I] Part I and [Thoorem 4, Part 1), we prove an impossibility result for a stronger model (one in which the computational complexity of Jt. is unrestricted) which makes our re- sults only stronger.
In both models, protocol is parametrized by the number of rounds T required, and the amount of memory B required per local processor. For notational convenience, for B e N we define Xg= = {0, 135, i.e. the length-B binary strings. Recall that ((v). denote the sets of vertices and edges adjacent to vertex v in graph G, respectively.
Definition (Node message-passinn N and let G = (V, E) be graph. A node message- passing protocol P on graph G with T' rounds and B bits of memory is a collection of functions (ft,w) (e(.))e where ft.o =XN(V)) x M-M(v)- + XB for all f, v. For an input I E EE the computation of P at a round E [T]] is the map P)(:;T)= : V + X' defined inductively by P( I): := (L.o((P Dere (T()))eM(()) where Po = O. We say that P computes a function g :: T - 13, on inputs I C &E if Pr(v; D) = g()), for all u E V and all I.I.
protocol). Let E
coonttre-c protocols. Typically, GNNs are architecturally constrained to respect the symmetries of the underlying graph. Below we formalize the most natural no- tion of symmetry in our models of computation. Note, our abstraction of a round in the message- message-passing protocol gen- eralizes the notion of layer in graph neural network- and the abstraction defined below correspondingly generalizes the standard definition of permutation equivariance (Xul ct al. 2019). We use the notation B to denote a multiset.
Definition 5 (Symmetric node message- pressage-passing protocol). A node message- message-passing protocol P = (Jt=))ee(T).e on graph G = (V, E) is symmetric if there are functions (J (*"")))(TT) so that for every t E [T] and u E V. the function fi, can be written as:
In words, the value computed by vertex v at round t is some function of the previous values stored at the neighbors v' E A(u), as well as possibly the problem inputs on the edges adjacent to e (i.c. ((()))eeM())) Note that Pe /) may indeed depend on P._ (w; I), due to our convention that e E (o)). We can define the edge message- passsigg- protocol analogously:
= (c(o), ((())))M(o)
of E (N()))
4

---

Towards characterizing the value of edge embeddings in GNNS
Our definition of symmetric edge message-passing proto- col is analogous; we defer it to Appendix A due space constraints.
Additional notation. For a set K contained in universe U. we let K := K \ U denote the complement of K in U (where U will be clear from context). We let (SS) denote the family of distributions over set S.
Figure I. The graph G for which [Theorem exhibits separation between edge pesssage-passing and node message-passing The graph consists of / paths of length vni, well a single "hub vertex" connected to all other vertices.
5. Depth separation between edge and node message passing protocols under memory constraints
We now consider a common task in probabilistic inference on a pairwise graphical model: calculating the MAP (maxi- mum a-posterior) configuration.
edge, respectively), assuming that each processor reads its entire input in each round. The graph G has node with (()) neighbors, in any node message- message-passing its processor must perform (2(BB) computation per round, for overall time complexity of Q(nBT)) = 22(2/33. In contrast, the constructed edge message-passing protocol is implementable in time O(n) per round, and hence (n) time overall.
passing protocol
Definition 6 (Pairwise graphical model). For any graph G = (V, E), the pairwise graphical model on G with potential functions ((v,b) 10. + TR is the distribution Ps E A(10, 1))) defined as po(x) x cxp(- E(a.bEE P(a.b) (o)).
Definition 7 (MAP evaluation). Let 4 S {6 : (0, [R be finite set of potential functions. A MAP (maximum a-posteriori) evaluator for G (with potential function class 4) is any function g E + {0,1) 1) that satisfies g()) E arg ma,,1 (x) for all @ E o
We provide proof sketch of the main techniques here, and relegate the full proofs to Appendix [ The graph G that exhibits the claimed separation is a disjoint union of vn path graphs, with an additional "hub vertex" that is connected to all other vertices in the graph (Fig. Tp. The intuition for the separation is that MAP estimation requires information to disseminate from one end of each path to the other, and the hub node is bottleneck for node message- passing but not edge message- passage-passing.. We expand upon both aspects of this intuition below.
With this setup in mind, we will show that there exists a pairwise graphical model, and a local function class 4 such that an edge message passing protocol can implement MAP evaluation with constant number of rounds and a constant amount of memory, while any node message protocol with T rounds and B bits of memory requires TB- = 2 (DVVV)). Precisely, we show:
Lower bound for node message-passing protocols: Our main technical lemma for the first half of the theorem is Lemma 2 It gives generic framework for lower bounding the complexity of any node message- passsnn protocol that computes some function g. by exhibiting a set of nodes S V where computing g requires large "information flow" from distant nodes. More precisely, for any fixed set of "bottleneck nodes" K, consider the radius-T' neighborhood of S when K is removed from the graph. In any T-round protocol, input data from outside this neighborhood can only reach S by passing through K. But the total number of bits of information computed by K throughout the protocol is only T |) This gives a bound on the number of values achievable by g on S. We formalize this argument below (proof in Appendix B):
Theorem 1 (Main, separation between node and edge mes-
sage-passing protocols). Fix n E N. There is a graph G with (n)) vertices and (n) edges, and a function class +b of size (1)), so that:
1. Let g be any MAP evaluator for G with potential function class D. Any node message-passing protocol on G with T rounds and B bits of memory that computes g requires TB 2 -n-1.
2. There is an edge message-passing protocol (fr.e)t.c on G with O(1) rounds and O(1) bits of memory that com- putes a MAP evaluator for G with potential function class &. Additionally, for all t, e,e, the update rule ft,e can be evaluated in (())())) time.
Lemma 2. Let G = (V, E) be graph. Let P be node message-passinee protocol on G with T rounds and B bits of memory, which computes a function g F + {0, 1 Pick any disjoint sets K, S CV Define H == G[K) F= M(NT-1(S) (S)), where - (S) is the (T hoph neigh- M(N H
The construction for the above result also implies a separa- tion between the parallel time complexity of node and edge bessage--assingg protocols (with one processor per node or
5

---

Towards characterizing the value of edge embeddings in GNNS
borhood S S in H.
The separation discussed above crucially relies on the ex- istence of a high-degree vertex in G. When the maximum degree of G' is bounded by some parameter A, it turns out that any edge message-pane paagggggpasinggggge protocol can be simulated by a node messaage-assing protocol with roughly the same number of rounds and only a A factor more memory per processor. The idea is for each node to simulate the compu- tation that would have been performed (in the edge message- passing protocol) on the adjacent edges. The following proposition formalizes this idea (proof in in[Appendix B):
Then: TB2 2
1 [K]
log m
{os (IF, 17 $r)
Remark 8. The proof technique is inspired by and related to classic techniques (specifically,, Grigoriev's method) for proving time-space tradeoff's for restricted models of com- putation like branching programs ((Grigor's ev 1976), see Chapter 10 in (Savage 1998) for a survey). There, one de- fines the "flow" of a function, which quantifies the existence of subsets of coordinates, such that setting them to some value, and varying the remaining variables results in many possible outputs. In our case, the choice of subsets is inher- ently tied to the topology of the graph G. Our technique is also inspired by and closely related to the "light cone" technique for proving round lower bounds in the LOCAL computation model (Linial 1992). However, our technique takes advantage of bottlenecks in the graph to prove stronger lower bounds (which would be impossible in the LOCAL model where memory constraints are ignored).
Let T, B 2 1. Let G = (V, be a graph with maximum degree D. Let P be edge message-passing protocol on G with T rounds and B bits of memory. Then there is a node message-passing protocol P' on G that computes P with T + 1 rounds and ( bits of memory.
Proposition 3.
6. Depth separation under memory and symmetry constraints
One drawback of the separation in the previous section is that the constructed edge protocol was highly non- symmetrie, whereas in practice GNN protocols are typically architecturally constrained to respect the symmetries of the underlying graph. In this section prove that there is separation between the memory/round trade-offs for node and edge passsage-passingg protocols even under additional symmetry constraints.
Remark 9 (Relation to oversquashing and virtual nodes). The above lemma can be seen as information thhorreti formalization and explanation of the commonly observed phenomenon of "oversquashing" (Alon & Yahav 2021), wherein GNNs on graphs with a hub node that needs to "pass information" between two large sets of nodes seem to perform poorly. It also demonstrates a difficulty for memory- constrained virtual nodes which are hub nodes that are of- ten artificially added to graphs in practice (Cai et al. 2023
Theorem 4. Let n E N. There is a graph G = (V, with (n) vertices and O(n) edges, and a function 10, + 13, so that:
The proof of Part 1 of Theorem I now follows from an application of Lemma 2 with a particular choice of K and S. Specifically, we choose K to be the "hub" node (i.e. K = (0) and S to be the set of left endpoints of each path. To show that any MAP evaluator has large information flow to S (in the quantitative sense of Lemma 2), it suffices to observe that in pairwise graphical model on G where a different external field is applied to the right endpoint of each path, and all pairwise interactions along paths are positive, the MAP estimate on each vertex in S must match the external field on the corresponding right endpoint.
1. Any node prsssage-passingg protocol on G with T rounds and B bits of memory that computes g requires TB- 2 2((n)).
2. There is symmetric edge message-passing protocol on G with O(1) rounds and O(log n) bits of memory that computes g.
For intuition, we sketch the proof of a relaxed version of the theorem where the input alphabet is [n]. It is conceptually straightforward to adapt the construction to binary alpha- bet (essentially, by adding new vertices and using unary encoding). We defer the full proof to Appendix C
Upper bound for edge message--pssing protocols: The key observation for constructing a constant-roumt round edge besssage-asssing protocol for MAP estimation on G is that all of the input data can be collected on the edges adjacent to the hub vertex. At this point, every such edge has access to all of the input data, and hence can evaluate the function. If G were arbitrary graph, this final step would potentially be NP-hard. However, since the induced subgraph after removing the hub vertex is a disjoint union of paths, in fact there is a linear-tima time dynamic programming algorithm for MAP estimation on G (Lemma 6). This completes the proof overview for Theorem
Let G = (V, E) be a star graph with root node 0 and leaves [1, (1...., n). We define a function g : [m]] + {0. 1)" by g()), = if and only if there is some edge + {0, v} such that I(e) = I(f0, e}), i.e. the input edge {0. v} equals the input on some other edge. Since y is defined to be equivariant to relabelling the edges, and all edges are incident to each other, it is straightforward to see that there is a symmetric ooe-round edge ceessage-passingg protocol that computes g with O(log n) memory (in contrast, the edge
6

---

Towards characterizing the value of edge embeddings in GNNS
message-passing protocol constructed in Section 5 was not symmetric, it required that the edges incident to the high- degree vertex were labelled by which path they belonged to). However, there is no lowmemory, low-round node message- passing algorithm. Informally, this is because vertex 0 is an information bottleneck, and (2(z) bits of information need to pass through it. Similar to in Section 5| this intuition can be made formal using Lemma
throughout the paper) take this functional perspective, analogous to the classical representational theory for neural networks (Telgarsky) 2016). Theorem 5 shows that even with arbitrary input features on the edges, the computation of a GNN with edge embeddings and symmetric updates can be simulated by a GNN with only node embeddings, without losing symmetry.
To prove Theorem 5| note that it suffices to simulate the protocol P for which the update rules fsym, faym in Defini tion 11 are identity functions on the appropriate domains. In order to simulate P. we construct a symmetric node passsng protocol P for which the computation at time t and node v on input I is the multiset of features computed by P time at edges adjacent to et Qx 1) == (e; 1): e M(v) This is possible since the computation of P at time t and edge e (u, v) is P((e; I) = (I(e), Pr- I), (u; 1), Qr- R)D)- The node peessage-passingg protocol is tracking Q I); moreover, it can recursively compute Pt-1 (e; 1) using the same formula. See(Appendix Doror the formal proof.
7. Symmetry alone provides no separation
In the previous sections we saw that examining memory constraints yields a separation between different GNN ar- chitectures (whether or not we take symmetry into consid- eration). In this section, we consider what happens if we solely consider symmetry constraints (that is, constraints imposed by requiring that the computation in round of the protocol is invariant to permutations of the order of the neighbors). This viewpoint was initiated by (Xu et al. 2019). who showed that when the initial node features are uninformative (that is, the same for each node), a standard GNN necessarily outputs the same answer for two graphs that are I-Weisfeiler-Lehmaa equivalent (that is, graphs that cannot be distinguished by the Heisfeiler-Lehmaal test, even though they may not be isomorphic).
8. Empirical benefits of edge-based architectures
In this section we demonstrate that the representational ad- vantages the theory suggests are borne out by experimental evaluations, both on real-life benchmarks and two natural synthetic tasks we provide. Note that all the experiments were done on machine with 8 Nvidia A6000 GPUs.
To be precise, we revisit the representational power of sym- metric GNN architectures in the setting where the input fea- tures may be distinct and informative. We show that if we remove the memory constraints from (eeeeSetionn 5] but impose permutation invariance for the computation in each round, any function that is computable by a T-llyer edge message- passing protocol can be computed by (T + 1)-layer node pessage-passingg protocol. Note that this statement is in- comparable to [Proposition 3) because we impose constraints on symmetry, but remove constraints on memory.
8.1. Performance on common benchmarks
First we compare the performance of the most basic GNN ar- chitecture (Graph Convolutional Network, (Kipf & Welling 2017) with node versus edge embeddings. In the notation
of I and D the AGGREGATE and COMBINE operations are integrated together, giving either ( or
Theorem 5 (No separation under symmetry constraints). Let T 2 1. Let P be symmetric edge ppessage-passingg pro- tocol (Definition) 17 on graph G = E) with T rounds. Then there is a (T + 1)-round symmetric node message- passing protocol (Definition 5) p' on G that computes the same function as P.
h(+11 6,99 + + AvG(h :w E E(()) \ (o))) (3) A!!+1) = n( + (vGWW) if e M(e) / (et)) (4)
for trained matrices W(lh) and choice of non-linearity o. The only difference between these architectures is that in the latter case, the message passing happens over the line graph of the original graph (i.e. the neighborhood of an edge is given by the other edges that share a vertex with it) - thus, this can be viewed as an ablation experiment in which the only salient difference is the type of embeddings being maintained. To also equalize the information in the input embeddings, we only use the node embeddings in the benchmarks we consider: for the edge-based architecture
Remark 10. Theorem 5 and its proof are closely related to the fact that the 1- L-Weisfeiler-Lehmaan test is equivalent to the 2- Weeisfeeiler-Lehmmn test, which was reintroduced in the context of higher-order GNNs (Huang & Villar 2021). ) The main difference is conceptual rather than technical. Prior works on expressivity of GNNs (with respect to the Weisfeiler-Lehmall test) measure expressivity by asking "for a given input, what are the possible outputs" (Xu et al.) 2019). In contrast, particularly for computation on graphs with informative input labels, it is natural to ask what func- tions a GNN can represent, i.c. "what are the possible mappings from inputs to outputs". In the above result (and
"This is the "residual" parametrization, which we in experi- ments unless otherwise stated.
7

---

Towards characterizing the value of edge embeddings in GNNs
Table 1. Comparison of node-based (3) and edge-hased 4 GCN architectures across various graph benchmarks. The performance of the
odge-based architecture robustly matches or improves the node- based architecture.
ZINC
MNIST
CIFAR-10
Peptides-Func
Peptides- Strucct
Model
MAE (L)
ACCURACY (1)
ACCURACY (t)
(1)
MAE (L)
GCN
0.3430 + 0.034
95.29 + 0.163
55.71 + 0.381
0.6816 + 0.007
0.2453 + 0.0001
Edge-GCN (Ours)
0.3297 + 0.011
94.37 + 0.065
57.44 + 0.387
0.6867 + 0.004
0.2437 + 0.0005
we initialize the edge embeddings by the concatenation of the node embeddings of the endpoints.
in the star graph and the depth k of the planted edge-based model. In each case, the numbers indicate RMSE of the best-performing edge-based and node-based architecture, sweeping over depths up to 10 (2x the planted model), widths E {16, 32, 64), and a range of learning rates.
In Table 1] we show that this single change (without any other architectural modifications) uniformly results in the edge-based architecture at least matching the performance of the node-based architecture, sometimes improving upon it. Note, the purpose of this table is not to advocate a new GNN architecture]- but confirm that the increased representational power of the edge-based architecture indi- cated by the theory also translates to improved performance when the model is trained. For each benchmark, we follow the best performing training configuration as delineated in (Dwivedi et al. 2023).
Since the planted edge-based model satisfies both invari- ance constraints (by design of the GCN architecture) and memory constraints (since the planted model maintains 10- dimensional embeddings),
view these results as em- pirical corroboration of Theorem 4|-and and even for simpler topologies than the proof construction.
8.3. A synthetic task for inference in Ising models
Finally, motivated by the probabilistic inference setting in
8.2. A synthetic task for topologies with node bottlenecks
Theorem 1 we consider synthetic sandbox of using GNNs to predict the values of marginals in an Ising model [Ising
The topologies of the graphs in Theorem I and Theorem 4 both involve a "hub" node, which is connected to all other nodes in the graph. Intuitively, in mode-embedding architec- tures, such nodes have mediate messages between many pairs of other nodes, which is difficult when the node is con- strained by memory. To empirically stress test this intuition, we produce a synthetic dataset and train a GNN to solve regression task on a graph with a fixed star- -raph topology- a simpler topology than the constructions in Theorem I| and Theorem 4 but capturing the core aspect of both. A star graph is graph with a center node Up, set of leaf nodes [e])) and edge set {foo, e. ii }- A training point in the dataset is list (14, 91 ) 1=1 where un is the inpul feature and y is the label for leaf node Ey
1924 Onsager 1944) - a natural type of pairwise graphical model where each node takes a value in (+1), and each edge potential is a weighted product of the edge endpoint values. Concretely, the probability distribution of Ising
model over graph G = E) has the form: Vx E {+1}"
PJA. (1) x exp E[.,EE (1,) + Eiey haa
Similar to in Section 8.2 we construct a training set where the graph G and and edge potentials stay fixed (precisely, Jr 1 for all {i.j} E E). A training data-point con- sists of vector of node potentials (h, Jeen). and labels [B[rs]iee consisting of the marginals from the resulting Ising model P.M.- The node potentials are sampled from a standard Gaussian distribution.
The input features are in R100 and sampled from a standard Gaussian. The labels yı are produced as outputs of a planted edge-based architecture. Namely, for a standard edge-based GCN in 4 we randomly choose values for the matrices [Wajiess) for some number of layers k, and set the labels to be the output of this edge-based GCN, when the initial edge features to the GCN are set as h (0) "[m..::) := x., i.e. the input feature I; at the corresponding leaf i. In Table 2
Table 2. Performance (in RMSE J) of edge-based and node-based architectures on a star-graph topology. The first number is the performance of the best edge-based model, and the second is the best node-based model, across a range of depths up to 10, widths E (16, 32, 64). and range of learning rates.
Depth of Planted Model (RMSE)
of Leaves
we show the performance of edge-based and node-based architectures on this dataset, varying the number of leaves n
Edge
Node
Edge
Node
Edge
Node
64
0.004
0.379
0.011
0.360
0.008
0.375
'In particular, the edge- based architecture is often much more computationally costly to evaluate.
32
0.003
0.366
0.005
0.363
0.003
0.361
16
0.007
0.334
0.002
0.210
0.002
0.285
8

---

Towards characterizing the value of edge embeddings in GNNS
There is a natural connection between GNNs and calculating marginals: classical way calculate [E[= when G is tree is to iterate message passing algorithm called belief
Acknowledgments
We thank the anonymous reviewers for their feedback that improved the presentation of this paper.
propagation ( in which for each edge {i,j} } and direc- tion i ++ J. message Vi=jj is calculated that depends on messages ( (k.i)e The belief- propaaatooo updates (7) naturally fit the general edge-message passing paradigm from 22. In fact, they fit even more closely "directed" ver- sion of the paradigm, in which each edge {i,j} maintains two embeddings h4-sj. j such that the embedding for direction æリ-ي depends on the embeddings / E - and it is possible to derive a similar "directed" node-based architecture (See (Appendix F.2). For both the undirected and directed version of the architecture, taining edge embeddings gives robust benefits over main- taining node embeddings-fora a variety of tree topologies including complete binary trees, path graphs, and uniformly randomly sampled trees of a fixed size. Details are included in Appendix
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
References
see that main-
Karl Abrahamson. Time-space tradeoffs for algehraic prob- lems on general sequential machines. Journal of Com- puter and System Sciences, 43(2):269-289, 1991.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In In- ternational Conference on Learning Representations, 2021. URL https::/ httpeeiwwwwweeeeeeeeeee net//orum
9. Conclusions and future work
id= Id=18COPhOCVHD
Graph neural networks are the best-performing machine learning method for many tasks over graphs. There is a wide variety of GNN architectures, which frequently make opaque design choices and whose causal influence on the final performance is difficult to understand and estimate. In this paper, we focused on understanding the impact of maintaining edge embeddings on the representational power, as well as the subtleties of considering constraints like mem- ory and invariance. We highlight two notable directions for future work:
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquashing in gnns through the lens of effective resistance. In International Conference on Machine Learning, pp. 2528-25547 PMLR, 2023.
Chen Cai, Truong Son Hy, Rose Yu, and Yusu Wang. On the connection between mpnn and graph transformer. In International conference on machine learning, pp. 3408- 3430. PMLR, 2023.
1. One significant downside of maintaining edge embed- dings is the computational overhead on dense graphs Hence, a fruitful direction for future research would be to explore more computationally efficient variants of edge-based architectures that preserve their repre- sentational power and performance. While there are a variety of interesting heuristics aimed at improving the performance of GNNs (for example, graph rewiring (Topping et al., 2022), ). understanding for which graphs and tasks these heuristics can improve representational tradeoffs is largely an open question.
Lei Cai, Jundong Li, Jie Wang, and Shuiwang Ji. Line graph neural networks for link prediction. IEEE Transactions on Pattern Analysis and Machine Intelligence, 44(9):5103- 5113, 2021.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. In International Conference on Learning Representations, 2019. URL hatttss://openeeviee net. forum? 1d=1 1003A9FM
Kamal Choudhary and Brian DeCost, Atomistic line graph neural network for improved materials property predic- tions. npj Computational Materials, 7(1):185, 2021.
2. The empirical results on common graph benchmarks (Table 1p suggest much weaker benefits of edge embed- dings than the synthetic TTalle 2) and theoretical re- sults. These benchmarks also largely have less skewed degree statistics. Experimenting with a wider range of benchmarks and understanding the impact of degree on performance could yield valuable additional insights.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Ma- chine Learning Research, 24(43): 488, 2023.

---

Towards characterizing the value of edge embeddings in GNNS
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In International conference machine learning, pp. 1263-1272. PMLR, 2017.
Lars Onsager. Crystal statistics. i. a two-dimensional model with order-disorder transition. Physical Review, 65 (3-4):117, 1944.
Kenta Oono and Taiji Suzuki. Graph neural networks expo- nentially lose expressive power for node classification. In International Conference on Learning Representations, 2020. URL (ttL::tt::////o /tttpp:://ppenevveww wet.ewewwweee.eeeeee.e..... www.:/wunett/ttnr
Dmitrii eur'evich Grigor' ev. Application of separability and independence notions for proving lower bounds of circuit complexity. Zapiski Nauchnykh Seminarov POMI, 60:38-48, 48, 1976.
id=S11
Johan Håstad and Avi Wigderson. The randomized com- munication complexity of set disjointness. Theory of Computing, 3(1):211-219,2)) 2007.
David Peleg. Distributed computing: locality-sensitive approach. SIAM, 2000.
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Trans- formers, parallel computation, and logarithmic depth. In Forty-first International Conference on Machine Learn- ing. 2024a. URL
Ningyuan Teresa Huang and Soledad Villar. A short tutorial on the weisfeiler-lehman test and its variants. In ICASSP 2021-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 8533-8537. IEEE, 2021.
net/
Forum ditimiddd000200iii1
Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Rep- resentational strengths and limitations of transformers. Advances in Neural Information Processing Systems, 36, 2024b.
Ernst Ising. Beitrag zur theorie des ferro-und paramag- netismus. PhD thesis, Grefe & Tiedemann Hamburg, Germany, 1924.
Thomas N. Kipf and Max Welling. Semi-supervised clas- sification with graph convolutional networks. In In- ternational Conference on Learning Representations, 2017. URL
John E Savage, Models of computation, volume 136. Addison- Wesley Reading, 1998.
Matus Telgarsky. Benefits of depth in neural networks. In Conference on learning theory, pp. 1517-1539. PMLR, 2016.
id=SJu4ayYg
AA Leman and Boris Weisfeiler. A reduction of a graph to canonical form and algebra arising during this reduction. Nauchno-Technicheskee Informatsiya, 2(9): 12-16, 1968.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Cham- berlain, Xiaowen Dong, and Michael M. Bronstein. Un- derstanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022. URL htttps:////: net/forum?id-70n RUm
Jinbi Liang, Cunlai Pu, Xiangbo Shu, Yongxiang Xia, and Chengyi Xia. Line graph neural networks for link weight prediction. Physica A: Statistical Mechanics and its Ap- plications, pp. 130406, 2025.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL
Nathan Linial. Locality in distributed graph algorithms. SIAM Journal on computing, 21(1):193-201, 1992.
net forum?
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020a. URL https: //openreview.oo hit.:e/wne....rrrmmm11111111111
id=ryGs6i 6m
Tuo Xu and Lei Zou. Rethinking and extending the proba- bilistic inference capacity of gnns. In The Twelfth Inter- national Conference on Learning Representations, 2023.
Andreas Loukas How hard is to distinguish graphs with graph neural networks? Advances in neural information processing systems, 33:3465-3476, 2020b.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any GNN with lo- cal structure awareness. In International Conference on Learning Representations, 2022. URL https:// openreview net www.eoiruuiiddoeeeoeoooerdm dsskk WYKoEH
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and
Yaron Lipman. Provably powerful graph networks. Ad- vances in neural information processing systems, 32, 2019.
Mare Mezard and Andrea Montanari. Information, physics, and computation. Oxford University Press, 2009.
10

---

Towards characterizing the value of edge embeddings in GNNS
[0.1]
{0.2)
IMON (y)) and (Pe(k; D Indeed, by definition, Pi(e; I) is determined by Lon()) for any v E V \ K. For any t > 1 and v E VV K. P((1; is determined by (Pi-1 (WV)))) and (E())) N(w) S (N( U.. K. Thus, using the induction hypothesis for each v' E Nn((), we get that (Pr-i (ENe is determined by UVENZ(U) LMING ((e") and (Pt(k; (EE(LE))) I MMN7'')) (o)) and (Pr(k; D)) completing the induction.
3
{0.8)
10,3)
Note that
{0,7)
(0.4)
[0.6]
(0.5)
Figure 2. A visualization of the information bottleneck induced by "hub nodes", which is the key intuition hehind [Thorrmm and 4 Here, G is star graph with 8 leaves. Left: The star graph G' itself, which describes the connectivity of the processors in node-based message- passing protocol on G. Any message between Iwo leaves must pass through the hub node (as depicted by the red arrows). Since the hub node has only constant memory, if all nodes need to pass information then intuitively (2(n) rounds are necessary. Right: The line graph L(G), which describes the connectivity of the processors in edge-based peessage-passing protocol on G. Each box corresponds to an edge of the original graph. Messages can be passed directly between boxes (as depicted by the red arrows), so there is no bottleneck.
So I((w; is determined by
VV K, we get that gs(() is determined by -M(N7-((S)) = Ip and (Pr(k; Mek Thus, for any fixed TF E &r. we have
Since P computes and S V
{f aos (F, 17 E x0)
< (Po(N: (Jr, [e))EMMAEE) 1/ E ΦF)
2TBIK)
Appendix
The lemma follows.
A. Omitted definitions
Definition 11 (Symmetric edge message-passing pro- tocol). An edge mhessage-passing protocol P = (ffr.))eETT)eeEE) (fo)eev) on graph G = (V, E) is sym- metric if there are functions ((e"")) and faym so that for every t E [T] and e = {u, E E, the function fi,e can be written as:
Proof of Theorem /
Let G be the graph on vertex set V ==
{0} U [v
n
x
Va
with edge set defined below (see also
ig.
E =
[v]] U (l(...).. (I+ : s
Let & be the following set of four potential functions:
= f ((d) M(w)
$ = { + 1 [ + 2z),
MM)BBB)
(Ia, 2b) + 1|xra + 1 V xb # 1].
and for every v E V. fo can be written as f(((c(())))M)) = form(((((e) :ee M())))
(Ia, 2b) + 1 # 0 V x # 0].
(Ta, 266 + 0}.
B. Omitted Proofs from Section 5
Lower bound. We start by proving the lower bound against node message-passing protocols, using Lemma Let g EE + {0, 1 be any MAP evaluator for G with potential function class D and consider any node message- passing protocol on G with T rounds and B bits of memory that computes g. Let K = {0} (the "hub node" of graph G) and S = {11,j) : j E [v]]} (the set of left-hand end- points of the paths in G). Suppose that T S vn 2. Let F == M(NT {(/n (vn,5)) & F for all j [v]]..
In this section we give the omitted proofs from Section 5 In particular we give the formal proof of Theorem I which states that there is a depth separation between edge message- passing protocols and node message-passing protocols for a natural MAP estimation problem on the underlying graph G. Additionally, see [Fg. 2 for a visualization of the key in- sight behind the proofs Theorems II [and 4 the "hub node" information bottleneck. Finally, we remark that quanti- tatively stronger (and in fact tight) separation is possible one considers general tasks rather than MAP estimation tasks- see Appendix
By assumption on T, we have that
Let Tp F + + be the mapping that assigns the function (Ia, + to each edge {0, (i, E F and (aa, (s) +
1[z, # 2a) to each edge (i. (1+1,)) E F. Intuitively, this means that we are focusing on the graphical models where the hub node has no interactions with the rest of the
First, we argue by induction that for each E [T) and e E V \ K, Pr(r; T) is determined by
Proof of Lemma 2

---

Towards characterizing the value of edge embeddings in GNNS
graph, and every non-hub-node is incentivized to match its neighbors.
the third line the function is computing go and ((3)) on the input (a) E T defined
We claim that even after fixing the potentials on F, the number of restrictions of possible MAP assignment to the set S is still exponentially large:
J(x), { (1(0,00))) (=(0
if [(,, (k-)),,k(144)) 1,2)] if c = {0, (k: {)}
Hos(LE 1F) : 1p E 00)
// 2
where we use the notation Va:b for a vector and indices o, b E N to denote (V/= Vo+1: v6). Note that (a) is well-defined function of x for every edge {0, (2, }), be- cause (0, (i.j)} ~ {o, (k:, ))} for all j, k. E [n]] Finally, define all other functions fr.e to compute the all-zero func- tion, and define
(5)
Indeed, for any string y E 10,1 consider the mapping
F F + & that assigns the function (Iaa 16) + 1/x, + Uj rb F yj] to each edge ((vm (, (vn.j)} E F, assigns (Ia, + 0 each edge {0, (i,5)) E E F. and
assigns (Ia, J66 + 1 [xx o mul to all remaining edges in E F. Then every minimizer of
fo(z): = (11000)))
if 0
(2(0,)))3:
otherwise
Σ
min
This function is well-defined since v = 0 is adjacent to edge {0, (1.1)} and any vertex v E VV {0} is adjacent to edge (0,
(0())
{a.b)ER
satisfies T(I.)) =... -. I((J))) Jj for all j E [V
since 1F incentivizes =(v(n.)) y/ and there are positive
Fix any I E & From the definition, it's clear that Pa(f0, (I = (T(0.).(+11))) [(0.0..))) for all I and (i.j) E [V 1] x [vn]. Hence () I for all edges e of the form (0, (i,])), and so Pa(10, (I: =
interactions along each path. Hence, gs(rr, 17) y. Since was chosen arbitrarily, this proves the claim 5 But now Lemma 2 implies that TB2 2 Vn.
=
(6.))) (f) for all (i,j) e [v]] x [vn]. This means that ((((((e MeMM()) g(), for all E V, so the protocol indeed computes g.
We now construct an edge message-passing protocol P on G with T = 3 and B = 4. We (arbitrarily) identify & with {0, 132. Intuitively, the three steps of the protocol do the following:
It remains to argue about the computational complexity of the updates fie It's clear that for all E E and e [1,2], the function fi,e can be evaluated in input-linear time. The only case that requires proof is when = 3 and e e= {0, (i. ]}} for some i E VT. In this case [M(e)]] = (n)) so it suffices to give an algorithm for evaluating the function g: _ + {0, 13V on an explicit input J in (n) time. This can be accomplished via dynamic programming Lemma 6).
1. First, each edge not adjacent to the hub node "reads" its own input.
2. Second, each edge {0, (i, adjacent to the hub node 0 "reads" its own input and the input of the adjacent edge (1,55). + 1.
3. Third, each edge {0, (i.j)} adjacent to the hub node computes the MAP estimate of the graphical model specified by the input, using the fact that all of the data
Lemma 6. Fix n E N. Let G, tb be as defined in Theorem 1 Then there is an ((n) -time algorithm that computes a MAP evaluator for G with potential function class T.
is now stored on edges incident to {0, (. It then
stores the indices of this MAP estimate corresponding to node 0 and node (i.
We proceed make this idea formal, which requires defin- ing a collection of update functions (fe,))e.- For all i,j E vn, define update functions
Proof. Intuitively, this is possible since we can iterate over possible values for the hub node 0, and once the hub node is fixed, the graphical model reduces /n independent Markov chains, for which MAP estimation is tractable via dynamic programming. We proceed to the formal proof.
(L..,.)..CH1))))...).)) = f2,0,005)) v) = (F(0))..++)))) 2.0 (00))))) f3.40,t.,)) (z. v)= =
ifi Vn
if vn
(J))
Fix any J E _ As preliminary notation, for each c, co e 10, and i.j E /nn let (ii.j) = {0} U (k: < k < i}. and let E(i,j) be the edge set of the induced subgraph (i) For all indices i, E vn and values
where the second line is well-defined since edge {0, (i.1)} adjacent to both itself and edge ((i.j), (i 1,5)); and in
12

---

Towards characterizing the value of edge embeddings in GNNS
Go E (0, let (ee; () denote the set of all partial configurations {0, 1) ((d)) satisfying the "boundary conditions" zo co and ((ts)) With this notation, define
for all u E V and inputs I. For each V, we define function fl, by
(1 (()))eEM()))
(ey(e, J) == arg min =E xex(ec)))))) (a.b))F((.s)
Σ
Ja. (b),
== f-- ((c(v)) ((c(v)c)eEM())) (e(v")))eeM()))) I(e"))
for each ex (u, M(r). Then by definition and the inductive hypothesis, we have
Cis(c,co;)) == min
Σ
Jaa (1).
x)x(co,())) (a.b)ER((.s))
Pi(u; D).
For each j E [Vn], let
-iollPP ()):vo))) ((()))eMM(o))
(( mig (ms(()ca:1)) .00:)). cE(0.1)
- ((P)- (v; Do)e
d) = -imm
(eL=(("; [(e"))
ft-1. ((Pt-2(P)))))) ((P==2(s)T)oemm))) MoEM())
Finally, let ((c;; J) E 10, be the vector which takes
(P-2(ce; De)eMMtr)) I(e*))
value co on vertex O, and value (co; J), on vertex (i.j)
= PP-i((e;;
for all j.j E vn. Let
for any edge ex = v*) E E, since M(e) = M(u) U M(u*). This completes the induction and shows that Pi+1 (1; T) (Pr(e: M)eM())) for all v, T. Replacing FT+L by fr.e o fT+,, completes the proof.
a(J) = arg max p. (5((oo; J)).
co
We claim that itJ) is maximizer of pzr)). Indeed, for any fixed co E [0,1]. #(co; J) is maximizer of ps(œ) subject to 2n = co. because under this constraint the maximization problem decomposes into v independent maximization problems, one for each path in G, which by definition are solved by L (co; . (n(oo;
C. Omitted Proofs from Section 6
Moreover, it's straightforward to see that for any fixed j. Cy(co: can be computed in Ovyn) time by dy- namic programming. Indeed for any i.j. Ocg(c, J) can be computed in O(1) time from (,, and C,-1, co; J) as well as ((o,(t.5)) and 1((6-1,).66.))) Once the values Cz,5 (c. cu: J) have been computed for all i E [v and c E (0, }}. the vector (C(: J) can be com- puted in (VVR) time via reverse scan over i = vR,..., follows that (J) can be computed in (n) time.
In this section we provide a formal proof of Theorem 4] For notational convenience, define = [vn] J. We define
graph G = (V, E) that is perfect n--ry tree of depth
two. Formally, the graph G has vertex set V = {0) U [m] U
([m] x [m]]. Vertex 0 is adjacent to each E [m]] and each E [m]] is additionally adjacent to (i, for all j E [m]. We
define a function g : {0, 1) - {0, 13 as follows. On input I {0. 1)²² for each edge e E F,, define the imput
summation at be
C(I):= d'EM(R)
Σ I(c').
Proof of Proposition 3) We claim that there is node message- wressageppsssing protocol P' on G with T + I rounds that at each time E [T' + 1] has computed
Intuitively, one may think of C(I), as simulating the in- put on e in the "large alphabet" construction described in Section 6 Next, define
(e; = ((P::))))(e(((ee)
(()) 0. 9(l), := 1[# e M((0 ut)
That is, each node "simulates" the computation of all inci- dent edges. The key point that for any edge (u, v) e E, the neighborhood. M(e)) is equal to M()) U UMM()) node can simulate the computation at using its own data and appropriate data from node u.
C(I). C(I) > m + 1].
g(Dn = 1 E [m] g()) 1].
In words, g()) is the indicator for the event that, among the 2m+1 edges adjacent to (0, u) (which include (0, u} itself), more than m + 1 edges have the same input summation as (0, u). At high level, this definition of g was designed
We make this idea formal by arguing inductively. Since Po = 0, it's clear that this can be achieved for = 1. Fix any t > and suppose that P (u; T) = (Pr ())EM()))
13

---

Towards characterizing the value of edge embeddings in GNNS
to satisfy three criteria. First, g(),, depends on the input values other branches of the tree: in partieular, if 7 [o.=) O for all v E [rr], then ( = qo.ut for all edges in the subtree of u, so g( exactly measures the event that there at least one edge outside the subtree of u for which C(J). - (o.uc. Second, there is no concise "summary" of / such that ()),.. can be determined from this summary in conjunction with the inputs on the subtree of u. Third, g() is equivariant re-labelings of the tree.
Then 4() u for all 1 (()) (v mm22xyymm? for all m/2 v m. It follows that for any 1 S u S n/2, Zu = 1 if and only if there exists some E [m²] \ u with (o.) = C (o.0). and hence I. = ()) We conclude that
S m/2, and
Kos(le.d)) 4 E x²)
2 2m/
Applying claimed.
Lemma 2 we conclude that TB 2 ((m) as
The first two criteria, together with the fact that the root vertex 0 is an "information bottleneck" for G. can be used to show that any node message- passing algorithm that com- putes 9 on G requires either large memory or many rounds. The third criterion enables construction of a symmetric edge cressage-passing protocol for g. The arguments are formal- ized in the claims below.
Claim 8. For graph G and function 9 as defined above, there is symmetric edge message-pussing protocol G that computes with ((1) rounds and (logm) bits of memory.
Claim 7. For graph G and function as defined above, any node message-passing protocol on G that computes 9 with rounds and B bits of memory requires TB 2 (mm).
Proof. In the first round, each edge processor reads its input value. In the second round, each edge processor sums the values computed by all neighboring edges (including itself). In the third round, each edge processor computes the indica- tor for the event that strictly more than m + 1 neighboring edges (including itself) have the same value as itself. In the final aggregation round, the output of a vertex is the indicator for the event that any neighbor has value 1.
Proof. Consider any input I (0, with I((0, u)) 0 for all u E [m]. Then for any j E [m], we have
C(1)fu((a5)) (()) Σ (u,
By construction, the value computed by any edge after the second round is exactly C(T).. Thus, after the third round, the value computed by any edge {0, u} is exactly (..).. Moreover, the value computed by any edge {u, (u, is O after the third round, since such edges only have m + 1 neighbors. It follows by construction of the final aggregation step that the protocol computes g.
Thus g()), = if and only if there exists some v E ml] \ {u} with (o.) = (o.) or equivalently Ee (u,
Em= 1(tv, iI)
Fix B and suppose that P is node message-passingg passing protocol on G that computes g with T rounds and B bits of memory. Define sets of vertices K := {0} and S = (1...., .......m//) m/2). Let H == G[K] and F == M(N (S)).
Then for any T, we have that
F= (10 : 11:1 m/2]
Proof of Theorem 4 Immediate from Claims and
(1, 15 m/2 1 S Sis m
Define a vector T E F by
D. Omitted Proofs from Section 7
[10,0) for
m/2
[[,(a))) j S w] for 1 < a < m 2, S S m.
Now fix any E 10.1 We claim that there is some I E o such that (IF, 1,,,, 1p) x. Indeed, let us define by:
Proof of Theorem 5 Without loss of generality, we may as- sume that the functions (f.5M )<E[T] and faym are all the identity function (on the appropriate domains). The reason is that any symmetric edge message-passing protocol P on T rounds may be simulated by running P and then applying a universal function (depending only on P) to each node's output value see Lemma
I by:
I[o.n)= 0 for m/2 < $ m (u((n.)) = 2 1 S v m/2]
for m/ 2 m, < m.
14

---

Towards characterizing the value of edge embeddings in GNNS
We argue by induction that for each [7], there is (t + ))-runnd symmetric node message-passing protocol that, on any input L, computes the function Qz /) := (P((e: E [M(x] B for every node u E V. That is, the protocol at node u simulates the multiset of computations performed by edges incident to u. This is similar to the idea for Proposition but requires significant care to ensure symmetry of the protocol is preserved.
the data (P'(u; D, (PP((; [(u, w))) : u (())))
By the induction hypothesis, this is equal the data (Qr-1(u; 1), ((Qc_i(e; 1), (), E For notational convenience, write
1.-1,- == D) :
and
11 == M(QQ((1Q11100 ((,, w))) (wEN)
Consider t 1. For any e (u, v) E, we have by symmetry and the initial assumption that
where Q1:-11 I) refers to the tuple (Qi (w; 1)....,.A........ Qt-1 (u; I)). Observe that Qia- (v; 1) can be determined from Q 7) (for any u) due to the exis- tence of the functions TI..... Y hence, S can be computed from Si-1,u. Using these observations, defining Pi+1 (u; 7) via the following sequence of transformations to the data (Q 1), S.-1,w) is well-defined:
Pi(e: 1) (I(e), o, :O::0''' d' e B(u)), f0: u' e (()))))
(6)
We define a two-round node message pasiggggppsinggggg protocol on G where the first update at node u computes
P( 1) = [e()): : : M(u)
(Q:-1(u; 1), S(
+ (Qu=-1(u;;) I), 11))
For the second update at node u, the node is required to compute a function of the data (P; I), (P(((e; 1), [(fu,v))) E (N))))
+ [(I((,u
It does so by applying the following transformation to this data:
(()
= :1)
[Qe-1
+ (((((u))).,,KKV)))((((()))))))
=
+ [((((u.)))), [I) N())
The second transformation inserts Q1:t1 I) into each element of the multiset S 7) and symmetrizes with Q1=-1 I). The final transformation drops Qu==2(u; I) and Q (v; 2) and inserts P1-1((u, 1): This insertion is well-defined because the definition of Pt-1 (-1(fu,, v); I) can be iteratively unpacked, and it is ultimately a function of the existing data
[)) [()) N())
I),
where the first step drops the term Pu; T), inserts the constant [W) into each element of the multiset, and re- places each set (2; I) by its cardinality; the second step symmetrizes the tuple (L)( (P; I))): and the equality uses the fact that (v; I)] = [V(x together with Eq. (6) By construction, this protocol is symmetric, and we can see that (2 I) = Qe(u; I), which proves the induction for step / -
(I(fu, (.f,,,)))..QQ0---1 (Q:.-
Q1:--10;;1) (un=-
To conclude, we have shown that l computes Qr I) at node on input I, and that this can be achieved while satisfying symmetry. This completes the induction. Since Qr(u; 7) is precisely the output of P at node u on input I (after the node aggregation step), this shows that P can be simulated by (T + 1)-round symmetric node message- passing protocol G.
Now pick any >>> 1. For any {u, v} E E, we know that the original protocol's computation at e can be written as:
P((e: (((e), I), (Q.-1(u; I), Q B)).
By the induction hypothesis, there is a I-round symmetric node message-passingg protocol p' that, at node v on input I, computes
Lemma 9. Let T 2 1. and let P (Ur.o)eET (fu)vev) be a symmetric edge message- passing protocol on G =V,EE with T rounds. Consider the T-round edge message-passing protocol pe = (Uie)ett)) (fi)vev) where for all t,e,
Pt(x;; 1) = (P:- e M(v) = Iv:
Note that since Pr (e; 7) is an element of the tuple Po(e; I), for each 1 < < t - -1 there is a fixed func- tion Yo such that 7, (w; I)) = (u; I) for all u, J. Using this fact, we extend Pr to +++1 rounds. The update at round t +1 1 and node u is required to be a function of
(ldee))) I(e))
= (I(e) fc(ee) :d M(u)).
(e(e') E M(v)
15

---

Towards characterizing the value of edge embeddings in GNNS
every evvery v E V,
the node message-passing protocol is restricted constant memory per processor.
(e(lde))eEM()) = (c(e) e M(o)B.
At technical level, the lower bound proceeds via a reduc- tion from the set disjointness problem in communication complexity, similar to the lower bounds in (Loukas 2020a)
Then there is function h such that (fe(PPj(e:D)eem
Mo))))))))))) for all I.
Definition 12. Fix m E N. The disjointness function
DISJ {0, 1) x {0, 1) 1 + {0, is defined
Proof. We prove by induction that for each t E {0, (o..... T}
DISJ (A, B) = 1 [Vi E [m]] : A,B; 0].
there is a function h4 such that Pr(e; /) = h4 (P (e; T)) for all e, I. Fort = 0 this is immediate from the convention that Po = Pp
The following fact is well-known; see e.g. discussion in (Hástad & Wigderson 2007).
Fix any t E (l..... T). Since P
symmetric, there is a function ft'm so that for all e (u, v) E and inputs I,
Lemma 10. In the two-party deterministic comumunica- Pa(e; = f: (I Pr-(ee I) (P-i(d: e M(u) B, tion model, the deterministic communication complexity of DISJm is at least m.
e "i
The main result of this section is the following:
( ( (P==((p M()))
Theorem 11. Fix any even n E N. Define {0, + 10, 11"") by
which indeed a well-defined function (independent of e, I) of
g(l) := 1[3(i,5} E E, : (, n/2
Ie :P E M(U))).
M(u)).
Al((i,5) [([n + 1 i, +++1- 1-1 = 1]
for all E [0,1) and v e [n]. Then the following properties hold:
This completes the induction. Finally, since is symmetric, there is function faym such that (e((P((e; M()))))))) faym ( eee write
Any node message-passing protocol Kn, with T rounds and B bits of memory that computes requires TB 2 (m))
for all v, I. Hence we can
[((((((e MeeM)))) = jaym (Pr(( f (Ppr( eM())
There is an edge pressage-passing protocol on K₂ with ((1) rounds and ((1) bits of memory that computes
9.
which is well-defined function (independent of I) of (e; e M(v)} as needed.
(Stw)t, be a node message-passing protocol on Kn that computes with T rounds and B bits of memory. We design a two-party communication protocol for DISJ,, as follows. Suppose that Alice holds input X E {0, 1)" and Bob holds in- put Y {0, 1) Let index the edges (i,j} En with i,j < n/2 by [m]. and similarly index the edges (i.j} E F,, with i, n/2 by [m]. in such way that edge {i,}} has the same index as edge {n+ 1 i, + 1 j}.
Proof. Let == (n/3). Let P
E. A quantitatively tight depth/memory separation
For each n E N. let K, = ([n], E.) ) be the complete graph on [n]. In this section we show that there is function that can be computed by an edge message-passing protocol on Kn, with constant rounds and constant memory per pro- cessor, but for which any node massage-passing protocol with I' rounds and B bits of memory requires TB > (n)). We remark that this separation is quantitatively tight due to Proposition 3. although it is possible that a larger (e.g. even super-polynomiaa in n)) depth separation may possible if
Let / E [0 be defined by
X(is) Yos 0
if n/2
T((i,)) =
if n/2 otherwise
16

---

Towards characterizing the value of edge embeddings in GNNS
for all v E {1. (1...., n/2), and Bob computes Po(u) == 0 for all E {n/2 + n.. The communication proto- col then proceeds in T rounds. At round t E [TT, Alice sends (P=-1("))soow)) to Boh, and Bob sends (P=-1(0))//+1sees to Alice. Alice then computes
Initially, Alice computes Po(v)
Also define S. : {0, 1) + {0, 1] for each [x] by fa(2)) == [=..1)- It can be checked that the computation of P at timestep t = is
Po(fi.J):1)
= 1 E [ ((1 = I((n 1- k, 2})1
= =(().
Pi(u): f(o(((P-1(())))ee
((.,))))Mxx(()))
From the definition of f, follows that P computes g.
for each 1 < I n/2, and Bob computes the same for Note that for any i I n/2 and edge
each n/2 <
E Mx, (i), Alice can compute I(e). Similarly, for any >> n/2 and edge E Mx., (t), Bob can compute I(e). Thus, this computation is well-defined. After round T, Alice and Bob output 1 - P1( and 1 - Pr(n) respectively.
F. Further details on synthetic task over Ising models
This defines communication protocol. Since P((u) E {0. 1) for each E [n]] and L [T], the total number of bits communicated is at most nBT. Moreover, by in- duction it's clear that Alice and Bob output 1 - PT(1;T) and 1 - (n:: I) respectively. By assumption that P com- putes g and the fact that g(T), = 1 DISJ (X. Y) for all Pr(n; and (1; = 11-11PPrff (r 1 if DISJ (4) 1. Thus. this communication protocol com- putes DISJ By Lemma 10 follows that nBT Q(n²), so BT = I(n) as claimed.
F.1. Background on belief propagation
A classical way to calculate the marginals [R[as]} of an Ising model, when the associated graph is a tree, is to iterate the message passing algorithm:
E [n]. we have that Pr(1;
if
mm (I)
(+11) tanh V
h4
Σ kEa.v
tanh tanh-"(ttnna (tanb(JJ))))
Next, we exhibit an edge message- message-passing protocol on Kn that computes g with six rounds and one bit of memory. Intuitively, the protocol proceeds via the following steps:
When the graph is a tree, it is a classical result (Mezard & Montanari] (009). Theorem 14.1) that the above message- passing algorithm converge to values 1² that yield the cor- rect marginals, namely:
1. First, each edge "reads" its input.
2. Second, each edge {i.}} swaps its value with the value at (n + 1 i, n + 1 j}; since these two edges are not adjacent, this takes two steps.
E [x,] tanh
h4 +
Σ tanh (tanh(Jat)( KEB:
3. Third, each edge {i,j} with i,j S n/2 checks if the input at {n + 1 2, n + 1 - j} (which it now knows) equals its own input.
The reason the updates converge to the correct values on a tree topology is that they implicitly simulate a dynamic program. Namely, we can write down a recursive formula for the marginal of node i which depends on sums spanning each of the subtrees of the neighbors of (i.e., for each neighbor j, the subgraph containing j that we would get if we removed edge (i.j]).
4. Fourth, an aggregation step is performed across the entire graph. Since the graph is complete, this can be done in two steps.
If we root the tree at an arbitrary node r, we can see that after completing a round of message passing from the leaves to the root, and another from the root to the leaves, each subtree of i will be (inductively) calculated correctly.
We proceed to make this intuition more formal. For L 6 and e En, define fie {0, M()( x 1) {0.1) as follows:
f1,0,)) (I, y
Moreover, even though the updates 7 are written over edges, the dynamic programming view makes it clear an equivalent message-passing scheme can be written down where states are maintained over the nodes in the graph. Namely, for each node U, we can maintain two values h down and hp.up. which correspond to the values that will be used when sends a message upwards (towards the
(x, #1n+1-i,d1
J3,0,, (I, = -fi.n-1-ji
= [ = F(..)) A ú.j < n/2]
fo,00.) (4,9) 1 1[3k [n] : [(,))) 1]
fo, (1, (2,8) 133 [n] [ = =]].
17

---

Towards characterizing the value of edge embeddings in GNNS
root) or downwards (away from the root). Then, for appro- priately defined functions F, G (depending the potentials
The architectures in the legend (Node-U, Edge-U, Node- D, Edge-D) are based a standard GCN, and detailed in Section
J and f),, one can "simulate" the updates in 7
P2
Re.up" - F (1 E U Children(w)}
(8)
We can see that for both the undirected and directed ver- sions, adding edge embeddings improves performance. The improved performance all directed versions compared to their undirected counterpart is not very surprising: the standard, undirected GCN architecture treats all neighbors symmetrically hence, the directed versions more easily simulate something akin to the belief propagation up- dates (7) as well as the node-based dynamic programming
(t+1) ",,dwnn"
[100 + ("Parent(s) {
(1 }
up f we Children(s)
(9)
Intuitively, he,up captures the effective external field in- duced by the subtree rooted at e on Parent(v). After the upward messages propagate, the root r can compute its cor- rect marginal. Once (Parent(s),doww dowwn is the correct marginal for Parent(v) at some step, he de,down will be the correct marginal for v at all subsequent steps.
F.2. GCN-based architectures to calculate marginals
The belief-propagation updates 7 naturally fit the gen- eral edge-message passing paradigm from ( In fact, they fit even more closely "directed" version of the paradigm, in which each edge {i,j} maintains two em- beddings hi-bj, h such that the embedding for direction h4-3 depends on the embeddings (ha-si (R. (k.))Eg- With this modification to the standard edge GCN architecture Eq. (4) is straightforward to implement (7) with one layer, using particular choice of activation functions and weight matrices W (since, in particular, in dataset all edge potentials Ji, are set to 1). Similarly, with a directed version of the node GCN architecture Eq. (3) where each node maintains an "up" embedding as well as a "down" embedding, it is straightforward to implement the based" dynamic programming solution -
We call the architectures that do not maintain directionality Node-U and Edge-U U (depending whether they node- based or edge-based GCN). We call the "directed" architec- tures Node-D and Edge-D respectively. Since there are only initial node features (input as node potentials (h; hi,, for the edge based architectures we initialize the edge features as a concatenation of the node features of the endpoints of the edge. The results we report for each architecture are the best over sweep of depth (5, 10, 15, 20, 25, 30} and width {10, 32, 64).
F.3. Edge-based models improve over node-based models
In Figure 3 we show the results for several tree topologies: a complete binary tree (of size 31), a path graph (of size 30), and uniformly randomly chosen trees of size 30 (the results Figure are averaged over 3 samples of tree).
18

---

Towards characterizing the value of edge embeddings in GNNS
Comparison Edge based and Node based GNNs across Graph Types
Edge-D
Node-D
0.06
Edge-U
Node-U
0.05
0.04
MSE
0.03
0.02
0.01
0.00
Binary Tree
Line Graphs Graph Types
Prufer Tree
Figure 3. Comparison of four architectures for calculating node marginals in an Ising model. The architectures considered are node- versions of GCN (correspondingly labeled Node-U and Edge-U), well their "directed" counterparts, as described in Section F2 correspondingly labeled Node-D and Edge-D. The x-axis groups results according to the topology of the graph, the y-axis is MSE (lower better). The mean and variances are reported runs for the best choice of depth and width over the sweep described in Scction
embedding (3) and edge-embedding
19


Reviews:
[{"review_id": "w8g9ssCdwJ", "reviewer": "Reviewer_1eR5", "summary": "The authors explore when edge embeddings are more effective than the traditional node embeddings approaches in graph processing. Their theoretical findings suggest that node-based message passing struggles with certain tasks, especially under tight memory constraints, whereas edge processing offers a more efficient alternative in these cases. Interestingly, without memory limits, the two approaches are nearly equivalent. Experiments further support the benefits of edge embeddings, showing that they can enable shallower yet expressive architectures.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and we appreciate the positive comments, particularly that the reviewer finds our work to be “of significant interest to the graph machine learning community”!\n\nRegarding the *size of the performance gain for edge-based GNNs on the real-world experiments*: we agree that the gain is marginal. However, we believe this is still a valuable experimental outcome. Note that edge-based GNNs are a pre-existing architecture with already numerous applications, and our goal in this paper was not to make an argument that they are inherently superior to node-based GNNs but rather to understand their benefits or drawbacks in controlled settings. A priori, edge-based architectures could have been much better or much worse than node-based architectures on existing benchmarks; Table 1 indicates that they are in fact slightly better. \n\nThis outcome is consistent with our theoretical results since most of the graphs in these benchmarks do not have as skewed degree distributions as our theoretical constructions and synthetic examples (e.g. the chemistry graphs from ZINC/Peptides-func/Peptides-struct are subject to physical/molecular constraints, and the computer vision graphs from MNIST/CIFAR-10 are constructed in such a way that all degrees are within a factor of two – see Appendix C.5 in [1]). We agree completely that understanding whether there are naturally-arising “harder” benchmarks is an interesting direction for future research.\n\n[1] Dwivedi et al. “Benchmarking Graph Neural Networks”. JMLR, 2023.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not verify the correctness of all the theoretical proofs in appendix.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "This paper will be of significant interest to the graph machine learning community as it explores the applicability and trade-offs between edge-based and node-based embeddings, providing valuable theoretical insights.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n\n[0] The authors provide a thorough analysis of edge embeddings in GNNs\n\n[1] The writing is mostly clear and easy to follow\n\nWeakness\n\n[0] The performance gain in practice is quite small, though, in theory, there may exist graphs where the improvement is significant. However, it remains uncertain whether such graphs would naturally occur in real-world scenarios.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "In the real-world experiments provided, the edge-based GNN models' improvement over others appears to be marginal. I wonder whether the trade-off justifies the practical use of this approach?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}, {"review_id": "rbYre1O9tK", "reviewer": "Reviewer_WSVk", "summary": "This paper studies how edge-based embeddings, rather than the more conventional node-based embeddings, can influence the representational power and performance of graph neural networks (GNNs). The authors formalize two message-passing models (one that maintains node embeddings, and another that maintains edge embeddings) and compare their ability to solve tasks under constraints on memory and depth.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and we appreciate the positive comments! \n\nRegarding the *computational challenge posed by dense graphs*: we agree that mitigating this challenge while maintaining the representational power of edge-based architectures is an interesting direction for future work. A variety of heuristics have been proposed in the GNN literature to try to address related issues (e.g. graph rewiring, as mentioned by reviewer m8Mu). Developing a fuller theoretical understanding for these practical approaches is an exciting direction, and we are happy to add discussion to this effect in the paper.", "claims_and_evidence": "The claims are well supported by rigorous theoretical arguments for which formal proofs are provided.  The authors also provided empirical evidence.", "methods_and_evaluation_criteria": "The experimental evaluation follows standard protocol and is adaquate. The authors clearly contrast edge-based vs. node-based architectures.", "theoretical_claims": "The main theoretical claims revolve around the existence of tasks (e.g., MAP inference on particular graphs) that require large depth for node-based but not for edge-based protocols, given constant local memory. Formal proofs are given an seem accurate to me — I did not identify any errors or issues in the line of argument.", "experimental_designs_or_analyses": "The experiments on benchmark datasets apply standard training/test splits and well-accepted metrics (MAE, accuracy). This design is reasonable.\n\nThe authors also propose synthetic stress tests (star graphs and Ising trees). These are well motivated and precisely target the “hub bottleneck” phenomenon. \n\nThe experiments confirm the theoretical insight that hub-centered graphs show big performance gaps favoring edge embeddings.", "relation_to_broader_scientific_literature": "The related literature is accurately described and cited.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n- The paper provides both rigorous theoretical analysis and empirical support for its main assertion.\n- The carefully designed synthetic experiments strongly highlight the advantages of edge-based GNNs in specific graph topologies.\n- The authors’ presentation is generally clear, with explicit definitions (e.g., node vs. edge protocols) and clearly written proofs.\n\nWeaknesses:\n- In dense graphs, maintaining an embedding for each edge can become computationally expensive; the paper mentions this but could discuss more practical engineering considerations.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "see weaknesses", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "nd1i0kyyHG", "reviewer": "Reviewer_CZSf", "summary": "The paper focuses on message-passing that also consider edge embeddings. The authors show theoretically that edge embeddings can have substantial benefits in terms of how deep a model needs to be and run some experiments to verify this claim.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and we appreciate the positive comments! Below, we address the reviewer’s concerns and questions:\n\n**Interpretation of our main conclusions:** The reviewer is correct that it’s unsurprising that adding edge embeddings may provide additional (representational) power. However, the goal of our work is not just to answer this yes/no question, but rather to investigate *when* edge embeddings help, *how much* they help (in particular, what are instances in which edge embeddings are particularly helpful), and understand the *mechanism* by which they help. Our main theoretical conclusions are that:\n\n(1) adding edge embeddings (substantially) improves representational power in terms of required depth when there are *hub nodes*, and conversely does not improve representational power when the degree is bounded; \n\n(2) this phenomenon is a consequence of *memory constraints* (and in particular, their interplay with depth) and not present under the standard theoretical lens where the only constraint on the protocol is symmetry. \n\nWe note these results can be viewed as GNN parallels of well-studied depth separation results for feedforward architectures [1] and Transformers [2] in which the goal is, similarly, to understand when and how much depth helps. These results were very influential in understanding the benefits of depth for classical architectures—but such theory is much less developed for GNNs. \n\nOur experimental results validate the “hub nodes” finding (Table 2) and demonstrate a noticeable but small gain on real-world benchmarks (Table 1). We hope that these results will enrich the conversation on *when* to use edge embeddings, motivate the search for real-world benchmarks with larger performance gaps (if they exist), and inspire the development of architectures that match the representational power of edge embeddings with better computational efficiency.\n\nWe hope that this addresses the reviewer’s concern about whether our conclusions are “illuminating”.\n\n**Interpretation of Table 1:** We agree with the reviewer that the closest analogue of the theory would be an experiment of the form “edge-based architectures achieve the same accuracy with lower depth”. Table 1 is morally equivalent so long as one believes that higher depth improves accuracy: “edge-based architectures achieve higher accuracy with the same depth”. We chose the latter because sweeping over depths to match accuracies is computationally expensive (and, ultimately, accuracy subject to compute/size constraints is an important desideratum in its own right), but we agree that an experiment trying to determine some representational “thresholds” as a function of depth would be scientifically interesting.\n\n**Interpretation of Table 2:** Table 2 is actually about the planted model (section 8.2), not the Ising model – we apologize if the location of the table caused this confusion. Since the planted model is edge-based, it is obvious that the edge-based architecture is representationally powerful enough to solve the task, but Table 2 shows that the learning procedure also works (i.e. there are no unexpected training difficulties). Table 2 also shows that the node-based architecture empirically cannot learn (even though e.g. there is a node for every edge, since the graph is a star), consistent with our theoretical finding that hub nodes cause issues for node-based architectures.\n\n[1] Telgarsky, “Benefits of depth in neural networks”, COLT 2016.\n\n[2] Sanford et al. “Transformers, parallel computation, and logarithmic depth” ICML 2024.", "claims_and_evidence": "While the contributions of the work are mainly theoretical, Table 2 aims to provide support for the empirical claims.", "methods_and_evaluation_criteria": "Table 1 includes mostly standard benchmarks. However I believe it is missing a key evaluation which is checking if the depth can be less for edge-GCN when compared to normal GCN. This is in fact seems to be one of the main claims: that maintaining edge information allows one to train a more shallow MPNN.\n\nI also think that Table 2 might not be very surprising as it seems to me like the task heavily requires edge information, although I am only vaguely familiar with the Ising model.", "theoretical_claims": "I cannot comment on the proofs as they are quite far from my main area of research. As a consequence, I am not sure how illuminating they are.", "experimental_designs_or_analyses": "Experimental section is rather limited, with Table 1 not contributing to the main claims very strongly in my opinion and Table 2 being a synthetic experiment.", "relation_to_broader_scientific_literature": "As this paper is far from my area of expertise I am not completely sure. I found remark 9 on oversquashing interesting, there are indeed works that study the connection between oversquashing and information theory. I would have been interested on further comments on this connection.", "essential_references_not_discussed": "I would not say this is essential, but in remark 9 I believe the info-theory and over-squashing could be better acknowledged, for example [1]\n\n[1] Banerjee et al. Oversquashing in GNNs through the lens of information contraction and graph expansion", "other_strengths_and_weaknesses": "The paper tackles what I believe to be a relatively under-studied topic as people often ignore edge-embeddings. It is interesting to see this kind of work and the main intuitive results seem somewhat interesting. I am not sure that the main conclusion however of \"adding edge embeddings provides additional power\" is particularly illuminating.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could the authors provide more information on why they believe Table 1 supports the main claim that edge embeddings provide additional representational power? Should this not be an ablation involving depth of the model as this seems to be a main theoretical result?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "1wkqM8gJpH", "reviewer": "Reviewer_m8Mu", "summary": "*Updates after rebuttal: I have increased my score since my concern was addressed by the authors.*\n\n———\n\nThis paper studies the benefits of using edge embeddings in graph neural network (GNN) as opposed to node embeddings. The authors theoretically show that  under memory constraints on the embeddings, an edge embedding GNN can solve certain graphical model task using a shallow model, whereas a node embedding GNN requires a much deeper model. The authors shows that such depth separation continues to hold with additional symmetry constraints (corresponding to commonly-used GNNs that satisfy permutation invariance). On the other hand, the authors prove that without memory constraint and using only symmetry constraints, there is no separation between edge embedding GNNs and node embedding GNNs. The theoretical findings on the benefits of edge embeddings GNNs are supported by empirical evidence on selected graph benchmarks and synthetic datasets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their thoughtful review and we appreciate the positive comments! Below, we address the reviewer’s concerns and questions:\n\n**Efficient approaches that close the separation between edge-based and node-based?** Thanks for pointing us to the reference by Topping et al. on graph rewiring; we’ll add it to the discussion. We agree that it would be nice to design more efficient approaches to close the separation. There are a variety of interesting heuristics for improving GNNs, though the trade-offs of such approaches are still not theoretically fully-understood. In particular, it would be very exciting to understand what representational effects (i.e. on required depth/width of a GNN) such heuristics have for specific choices of graphs and tasks.     \n\n**Does the depth separation translate to time complexity separation (Question 1)?** Yes, there is a separation in parallel time complexity (with one processor per node/edge in the respective models), modulo an assumption that each processor reads all of its neighbors’ input at each round. In the edge model, the procedure can be implemented in time O(n) as the reviewer states. In the node model, we prove $TB \\geq \\sqrt{n}$. Since the hub node has $O(n)$ neighbors, each round requires parallel time at least $O(nB)$ if the hub node reads the $B$ bits for each neighbor, so the overall parallel time complexity is at least $O(nTB) = O(n^{3/2})$. We will clarify this point in Remark 4.\n\n**Remark about input features in WL test?** We agree that the k-WL refinement procedure can utilize informative features, and we apologize for the imprecise wording of Remark 10. \n\nIn Remark 10 we were trying to briefly make a somewhat subtle point (which we will expand on): prior works on expressivity of GNNs (w.r.t. the WL test) measure expressivity by asking “for a particular input, what are the possible outputs” (and they show this is characterized by number of WL refinement steps). However, particularly for GNNs that take as input both a graph and informative input labels, we would argue the central representation question is what functions the GNN can represent, i.e. “what are the possible mappings from inputs to outputs”. This is what matters for downstream learning tasks, and what motivated our framework (see also the paragraph “GNNs as a computational machine” in Sec. 3). This is also analogous to the classical representational theory for standard neural networks.\n\n**Implication for virtual nodes (Question 2)?** Thanks for bringing up virtual nodes and the reference to Cai et al.; this is an interesting connection and we will add a remark to the paper. Since our main construction uses a node that is connected to the rest of the graph, it can be interpreted as showing a difficulty for memory-constrained virtual nodes (or even a motivation for designing GNNs with larger memory at the virtual node, which perhaps could be implemented by variable dimensionality of the embeddings maintained at different nodes in the GNN). \n\n**Choice of real-world benchmarks (Question 3)?** We tried to choose diverse tasks that enable fair comparison of edge-based vs. node-based models (thus, we ruled out edge classification and node classification tasks, because they introduce a confounder – they require substantively different collation layers between the two architectures). ZINC/MNIST/CIFAR-10 are graph classification/regression datasets from the original GNN benchmark of Dwivedi et al. [1], and Peptides-Func/Peptides-Struct are the graph classification/regression datasets from the long-range graph benchmark [2]. \n\nMost of these graphs in fact do not have as skewed degree distributions as the synthetic examples (e.g. the chemistry graphs are subject to physical/molecular constraints, and the image graphs are constructed so that all degrees are within a factor of two – see Appendix C.5 in [1]). The goal of Table 1 was primarily to perform a controlled comparison between edge and node architectures on commonly-used GNN benchmark datasets. Of course, expanding the range of datasets (or even constructing more challenging ones reflective of natural GNN tasks) and exploring the impact of e.g. degree statistics on performance is an interesting future direction.\n\n**Notation in Lem. 2 / Def. 6 / Prop. 3?** The overline notation in Lem. 2 means set complement, and the Delta({0,1}^V) in Def. 6 means the set of distributions over {0,1}^V. We will clarify these (and Prop. 3).\n\n**Ablation on the number of layers?** We used the same number of layers for both architectures in Table 1 so as to equalize everything except the design choice “node-based vs edge-based”. Anecdotally we did not find significant changes with deeper node architectures, but unfortunately doing a thorough sweep over depths for both architectures would have been computationally taxing.\n\n[1] Dwivedi et al. “Benchmarking Graph Neural Networks”. JMLR, 2023.\n\n[2] Dwivedi et al. “Long Range Graph Benchmark”. NeurIPS 2022.", "claims_and_evidence": "Overall, the theoretical claims are mostly well supported. There are a few claims that required further explanations and/or revisions.\n\n1. The main result on separation between node and edge message-passing protocols (Thm.1): while it is clear that there is a depth seperation (i.e. the number of message-passing rounds, or layers in GNN), it is unclear if this translates to difference in terms of total computational time. More concretely, Thm.1-2 shows that the edge protocol requires $O(1)$ rounds and $O(|\\mathcal{M}(e)|)$ time. For star graphs, the centroid node of the star requires $O(n)$ time to evaluate the update rule, which suggests the total time is $O(n)$. On the other hand, the lower bound of node protocol shows $TB \\ge \\sqrt{n} - 1$, which suggests the total time is $\\Omega(\\sqrt{n})$. If so, then there seems to be no separation in terms of total computation time for this graphical model task? That said, I do appreciate the authors provide the tighter separation result using set disjointness in Appendix. E without the ambiguity of total compute time.\n\n2. Remark 10: The authors claim that the $k$-Weisfeiler-Lehman (WL) test only characterizes the expressivity of higher-order GNNs with uninformative input features, which is not true. The graph can have informative node features and edge features, which will be utilized during the initialization step of $k$-WL, making the test more discriminative.", "methods_and_evaluation_criteria": "The authors demonstrated their theoretical insights on the benefits of edge embedding GNNs on synthetic graphs that are aligned with the theoretical construction. However, I am not sure the evaluation on some of the chosen real-world graphs is particularly meaningful, e.g. on MNIST and CIFAR-10 graphs; do the authors choose these benchmarks due to their topology resembling a star graph?", "theoretical_claims": "I checked the proof of Thm.1: the overall argument seems correct but there are a few notation undefined. Specifically, in the statement of Lemma 2, the notations $\\bar{K}, \\bar{F}$ are undefined. \n\nI also checked the correctness of the proof of Thm.4 and the proof sketch of Thm.5.", "experimental_designs_or_analyses": "To provide more comprehensive empirical evidence for highlighting the theoretical insight, it will be nice to ablate on the number of layers when comparing the edge-based GNNs and node-based GNNs in Table 1.", "relation_to_broader_scientific_literature": "The comparison between edge-based GNN and node-based GNN is clearly of interest to the community, including both theoreticians and practitioners. The main theoretical results in showing the benefits of edge-based GNN mostly utilize the hub-node topology. This seems also  related to the practical heuristic in training GNNs for long-range task by adding virtual nodes (VN) (see more discussion and references in [1] Cai et al.). It will be nice for the authors to discuss their result in the context of virtual nodes.", "essential_references_not_discussed": "The following work investigates the power of using virtual node in node-based MPNNs.\n[1]. Cai, Chen, et al. \"On the connection between mpnn and graph transformer.\" International conference on machine learning. PMLR, 2023.\n\nThe following work discusses a mitigation strategy of over-squashing using graph rewiring.\n[2]. Topping, Jake, et al. \"Understanding over-squashing and bottlenecks on graphs via curvature.\" International Conference on Learning Representations.", "other_strengths_and_weaknesses": "Strengths: The paper is well written overall, with interesting theoretical results on the depth separation between edge-based and node-based GNNs, using tools from communication theory and theoretical computer science. The theoretical insights are illustrated in both synthetic and real-world tasks. \n\nWeakness: \n1. As shown in prop.3 by the authors, the main depth separation result crucially relies on the existence of a high-degree vertex in the graph. As acknowledge by the authors, the edge-based GNNs often suffer from higher computational complexity. In light of these findings, the paper can be strengthened by proposing efficient approaches that close the separation between edge-based and node-based GNNs, such as graph rewriting in Topping et al.[2].\n2. Some of the theoretical claims require further clarification/revision (see Claims and Evidence above).", "other_comments_or_suggestions": "The notation $\\Delta$ appears in Defn 6 (without explanation) and re-appears in Prop. 3 (with likely a different meaning). Consider fixing the possible notation clash.", "questions_for_authors": "1. Does the depth separation result on MAP evaluator translate to time complexity separation? (See more details in Claims and Evidence)\n\n2. Can the authors comment on the implications of their findings to the heuristic of virtual nodes in node-based GNNs? (see Relation to Literature)\n\n3. Can the authors explain their choice of real-world graph benchmarks? (see Methods and Evaluation Criteria).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies how edge-based embeddings, rather than the more conventional node-based embeddings, can influence the representational power and performance of graph neural networks (GNNs). It is shown that certain tasks can be solved with a one layer GNN using edge representations and limited memory per feature, while they take $\Omega(\sqrt{n})$ layers for node-based GNNs with limited memory per feature. This shows that the memory lens, which is often overlooked by other forms of expressivity analysis, is an important aspect that affects expressivity. The paper also compares symmetry preserving and non-symmetric architectures. The results are corroborated by experiments.


All reviewers were positive about the paper, and agreed that the topic is timely and important, the paper is well written and clear, and the theoretical contribution is interesting, insightful, and rigorous. The reviewers also agreed, as stated also in the paper, that the main limitation of edge-based GNNs is that they often suffer from higher computational complexity with respect to node-based GNNs.


The authors are asked to implement the reviewer’s comments in the final version of the paper if accepted.
Decision: Accept (poster)