Graph Neural Networks Gone Hogwild
Authors: Olga Solodova
Nick Richardson
Deniz Oktay
Ryan P Adams
Venue: ICLR 2025 Poster (2025)
Keywords: graph neural networks
multi-agent
asynchronous
decentralized
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph neural networks (GNNs) appear to be powerful tools to learn state representations for agents in distributed, decentralized multi-agent systems, but generate catastrophically incorrect predictions when nodes update asynchronously during inference.
  This failure under asynchrony effectively excludes these architectures from many potential applications where synchrony is difficult or impossible to enforce, e.g., robotic swarms or sensor networks.
  In this work we identify ''implicitly-defined'' GNNs as a class of architectures which is provably robust to asynchronous ''hogwild'' inference, adapting convergence guarantees from work in asynchronous and distributed optimization. 
  We then propose a novel implicitly-defined GNN architecture, which we call an energy GNN. 
  We show that this architecture outperforms other GNNs from this class on a variety of synthetic tasks inspired by multi-agent systems.

Published as a conference paper at ICLR 2025
GRAPH NEURAL NETWORKS GONE HOGWILD
Olga Soludova, Nick Richardson, Deniz Oktay, Ryan P. Adams Department of Computer Science
Princeton University Princeton, NJ, USA
(solodova, njkrichardson, doktay, xpal@princeton. edu
ABSTRACT
Graph neural networks (GNNs) appear to be powerful tools to learn state representations for agents in distributed, decentralized multi-agent systems, but generate catastrophically incorrect predictions when nodes update asynchronously during inference. This failure under asynchrony effectively excludes these architectures from many potential applications where synchrony is difficult impossible to enforce, e.g., robotic swarms or sensor networks. In this work we identify fimplicity-ddefnned"" GNNs as a class of architectures which is provably robust to asynchronous "hogwild" inference, adapting convergence guarantees from work in asynchronous and distributed optimization. We then propose a novel implicitly-dene -eefieed GNN architecture, which we call energy GNN. We show that this architecture outperforms other GNNs from this class on a variety of synthetic tasks inspired by multi-agent systems.
INTRODUCTION
Coordination and control of distributed and decentralized multi-agent systems is a major project spanning engineering and computational science. Success this program has implications across a broad spectrum of applications; autonomous vehicle navigation, energy/resource management and distribution in smart grids, and robotic swarms (for exploration, search and rescue, environmental monitoring, and construction), to name few. Agents in these systems must take action based on direct observation and communication with the collective. At the level of any individual, a controller takes as input the agent's ' 'state representation' which ideally unifies direct measurements and peer-derived messages in a coherent manner.
In the distributed/decenttraiied regime, the communication constraints associated with the system can be encoded as a graph in which each node associated with an agent, and each edge with an agent- agent-to-agent communication link. Adopting the graph view of the system, graph neural networks (in particular, message- passing variants (Gilmer et al., 2017]: (aamltoon] 2020)) have been widely studied as methods for deriving flexible, data-dependent, and parametric state representations. GNN-based state representations have been explored in a variety of applications; for example, flock formation, target tracking, path planning, goal assignment. and channel allocation in wireless networks (Jiang and Lu 2018 Nakashima al. 2019
ct al. al. 2021 Zhou al., 2021 Gossich et al.] 2022]] liang et al.] [023] Goarin and Loianno, (024)). The
2019 Khan et al.] 2019: Jiang et al., 20200 Gama et al.] 2020 : Blumenkamp et al. [021]] Grattarola
motivation to use GNNs can be traced to three core features. First, a GNN is a parametric family of functions
for deriving state representation, enabling domain-specificity by choosing from this family and optimizing the state representation for a given task end-to-end. Second, message passing within a given GNN layer satisfies the constraint that agents must derive state representations using only information obtained through local communication with neighbors. Third, GNNs with multiple layers allows state representations to depend on information outside of a given agent's local neighborhood.
All that said, there is a major conundrum in applying GNNs to these problems. On the one hand, asynchronous execution and unreliable communication are ubiquitous in real-world decentraizeeddiisrrhhueed multi-agent systems. On the other hand, these features render conventional GNNs inoperable in the multi-layer regime, the very setting in which GNNs offer a putative advantage through longer range communictioo//cordinatioo This is because GNN architectures implicitly assume that synchronization barrier is enforced across all nodes between layers of message passing. If nodes update asynchronously or messages can be delayed or lost, embeddings from neighbors do not necessarily correspond with the intended layer in the GNN (from the perspective of the receiving node). The effective architecture (and therefore output) of the GNN diverges catastrophically from that used in training. Figure illlstrraess the issue a toy problem.

---

Published as a conference paper at ICLR 2025
(a)
(d)
node
node
Node outputs over random asynchronous runs
Node 1
Node
0
O
1
(b)
synchronows execution
cc)
asynchronous execution
26
Node 3
Node 4
Figure I: Modifications to the computation graph of an I--laer message-passing GNN resulting from asynchronous, distributed, per-node inference with communication delays. (a) An undirected linear graph with binary features written in the node body. (b) Synchronous per-layer execution of 3-layer GNN the graph from (a); all nodes update the same time, using neighbor information from the previous layer. Arrows represent network weights. are all equal to 1, and the value of node embedding at the next layer the sum of incoming values. (c) Asynchronous inference of the GNN from (b). Nodes update at random times and can use neighbor information corresponding to the incorreet layer, which introduces modifications to the computation graph. Gray arrows correspond to connections that were removed from the original computation graph, and red arrows unintended connections resulting from asynchrony and/or message delays. (d) To demonstrate the effect of asynchrony, we show the output of GNN varies significantly over asynchronous runs with different node update orderings.
demonstration, weights
Unfortunately, enforcing synchronization distributed and decentralized system costly (e.g. throughput is limited by the slowest node) and is particularly difficult to enforce in systems where nodes can join or leave the network, or are prone to failure. Existing work on using GNNs for computing agent state embeddings either use single layer GNNs (where synchronization is unnecessary), ignore the constraint of asynchronous execution altogether, limiting the prospect of fielding the method. If were possible to perform "hogwild" inference in multi-layer GNNs (nodding the asynchronous optimization work of al. (201T)) GNNs would be a significantly more powerful tool in computing state embeddings for decentralized multi-agent systems.
In this work we present a unified framework for GNNs which can execute inference asynchronously. adapting classical results from the distributed optimization literature. Our analysis illuminates the boundary between GNNs which are/are not amenable to asynchronous inference, and we articulate sufficient conditions for given architecture's robustness to asynchrony. We call the class of GNNs which are provably robust asynchronous inference -implicity-definedd:: in an implicitlyddefined GNN, node embeddings correspond
with a solution an optimization problem (Gu et al., 2020 Liu et al. 2021 Yang al.) 202T Zhu al. 2021; Ma et al. 2021 Scarselli et al. 2009). This is in contrast to GNNs in which node embeddings are computed the output of statically defined feed-forward computation, such as graph attention networks (GAT, Veličković et al, 2))8)) and graph convolutional networks (GCN, Kipf and Welling (201))) we refer to these architectures as "explicitly-definedd"
In addition to analysis of GNNs under asynchronous execution, we contribute a novel asynchronous-capale (implicitly-define)) architecture, which we call energy GNN. Our architecture exposes rich parameterization of optimization problems using input-convex neural networks operating over nodal neighborhoods. We show that energy GNNs outperform other implicitly-deffee defined GNNs on variety of synthetic tasks motivated by problems which are relevant multi-agent systems, where synchronous inference may be undesirable. We also achieve competitive performance on tasks with benchmark graph datasets, certifying the merit our approach even as a stand-alone GNN architecture.
2

---

Published as a conference paper at ICLR 2025
2 PRELIMINARIES
2.1 PARTIALLY ASYCHRONOUS ALGORITHMS
Computational models for asynchronous algorithms vary depending on the constraints imposed on the sequencing frequency of computation communication. We consider partial asynchronism defined by Bertsekas and Tsitsiklis (1989), which we summarize here.
Consider collection of nodes carrying noted h2 E IRA which corresponds to one "block" (row) of the aggregate state H == (h1,-- hn)) E RREX The algorithm being executed consists of iterative node updates, where each node i 1, ..... iteratively updates its state according to h; == (H) using some node-specific update function f TR - TR*
distributed computation. Each node has hidden state de-
We given set T S (0, 2.... ) of times at which each node i is updated; this accounts for asynchrony in the execution of the algorithm. Additionally, for each & E T we are given variables 0 S 7f(1) S which represent the time associated with node i's view of node j at time If communication is instantaneous and reliable, then (t) is always equal to t, as node i's view of all other nodes is the actual value those nodes hold at time t. Staleness (i.e. (t( t) results from delays losses in communication between nodes, For instance, suppose T {0. 4, 73. T {2, 3, 5]. and (4)
This means that when node executes its second update (at t = 4), it uses the stale value of node 1 that was computed at t = rather than its actual value 4 (due to loss or delay of the message containing the value of node which was computed at f = 3).
We can now describe the asynchronous algorithm using the following node update equations:
(t+ 1) ht) if
(1)
= f h.. (t)) ift
(2)
2 Partial asynchronism corresponds to the following assumptions:
Assumption 2.1 (Partial chroniroissm
Bertsekas and Tsitsiklis 1989) Assumption 5.3) There exists an integer B > O such that:
(a) (Bounded time to next update) For every node i and every 1 2 0, at least one of the elements of the set {t, t 1,...,t+ B 1} belongs to T".
(b) (Bounded staleness) There holds B < T()( S for all i, and all t belonging T
(c) There holds +(( for all i 1,2, and E T
Informally, (a) states that each node updates at least once every time units, (b) states that information from other nodes can be stale by at most B time units, and (c) states that node i maintains the current value of h;-
2.2 GRAPH NEURAL NETWORKS
Consider directed graph with collection of n vertices V = (1, n). and edges E FCV x V. The connectivity of the graph is contained in its adjacency matrix {0, 1]nxn, where A = there is edge from node to node and 0 otherwise. The graph may also have associated node and edge features X E Raxp and E E R [E|,,, so we use G X, to denote the graph. We use (iii) denote set of neighbors of node i.
In GNN, each node i is associated with a v-vector embedding h; which is updated through iterations (or layers) of message passing. Each node constructs a "message" m, by aggregating information from nodes j E (iii) in its local neighborhood, then uses this aggregate message to update its embedding. The node update equation for all nodes and layers E {0,..., L. 1} is as follows:
h ++1 1 (h), wi (h/, a,, etyl E EN(())) un n/.
+ JEN(
m hτ. x,, F,,, (.)) ub (h/ x., m!)
(3)
3

---

Published as a conference paper at ICLR 2025
where b is aggregation function, and th and ma are, e.g., neural networks. We use H := (h1..... ) Raxh to denote the aggregate embedding of nodes in the graph. H is typically initialized as the node features X. For convenience, omit the layer index E from fg in contexts where there is only one parameterized layer, when referring generally message passing layer. In the final layer, readout function og & R is applied to each embedding, which results in node predictions y = (o=(h)), og (h)))) E [R
EXPLACITLY-DERNED VS. IMPLICITLY-DEFINET GNNS
In a conventional feea-forward message passing architecture that consists of L layers, it is assumed that all update functions for a given layer are applied in a synchronized manner. That is, each node embedding is derived from the previous layer embeddings. In distributed systems synchrony is either impossible or
comes with substantial overhead. If nodes update asynchronously according to Equations ( and (2).
GNN architectures that assume synchronicity will fail catastrophically and nondeterministically because the architecture at inference time is different than it was during training. This effect is illustrated in Figure [
This failure motivates to distinguish between two types of GNN architectures: ppllicttyydeffinee GNNs which specify a specific feed-forward layer-wise computation, and implicityydeffied GNNs in which the layer-wise message passing updates correspond iterations toward a fixed point. We further subdivide implicitly-defined GNNs into two types: fixed-point GNNs and the important special case of optimization- based GNNs. Explicity-ddcfnne GNNs are susceptible failure under asynchrony, while implicitly-defined GNNs are robust (as we discuss in Section
3.1 FIXED-POINT GNNS
Fixed-point GNNs obtain node embeddings as the fixed point of contractive message passing function. Using h E Rnnk to denote the unrolled embeddings H and taking Fe : TRnk -> IR be the aggregate update of the hidden state from applying fo to the neighborhood subgraph of each node i = -,.... in graph G, a fixed-point GNN iterates F' until numerical convergence of node embeddings, i.c., (h) h.
Convergence to a unique fixed point is guaranteed provided the update function F6 is contraction map with respect to the embeddings, i.e. [|F (h) - F& (h')ll II S 14 h- h'll holds for 0 < μ < 1 and Vh, h' E Runk Since it is difficult design non monntrivial parameterizations of F& which are contractive by construction, existing fixed-point GNN architectures (c.g. IGNN (Gu et al. 2020). EIGNN (Liu et al. 202T), and APPNP (Gasteiger al. 2019) are limited in diversity. These architectures use linear transformations of the node embeddings in computing messages m,, where the parameters can easily be constrained such that Fg is contractive. Gu et al. (2020) apply component-wise non-expansive nonlinearity compute updated node embeddings from these messages, while Liu et al. (2021): Gasteiger et al. (2019) directly take m. as the node embeddings for the next iteration.
The original 'nonlinear GNN' proposed by Scarselli et al. (2009), in which Sa contains general multi-layer neural networks operating on the input data, represents another approach to parameterizing a fixed-point GNN. Their method encourages rather than guarantees contraction via a multi-objective problem that includes the norm of the Jacobian of the update function as a quantity to be minimized. This heuristic can work practice, but the sequence of iterates does not definitively converge, particularly if node embeddings are initialized far from the fixed point (as the norm the Jacobian is only penalized at the fixed point). We thus do not consider this non-linear GNN to be a true fixed-point GNN, We provide more details on existing fixed-point GNN architectures in appendix
3.2 OPTIMIZATION-BATE GNNs
Optimization- based GNNs obtain node embeddings by minimizing a convex scalar-valued graph func- tion Eg 9 x R + .. with respect to the aggregate graph node embeddings H, where 0 are parameters:
H" = arg minH Eg(g, H).
(4)
Assuming Eg is separable per node, Eg can be expressed as:
Eg H) = Ei= eo (h;, Fi (hj, Fy eij 1 E N(())) Ei c/-
(5)
4

---

Published as a conference paper at ICLR 2025
Crucially, due to the dependence of each ej on only local information, gradient- gradient-based minimization of Eg can be expressed per node via message passing:
(t + 1) = ht(t) - a EjENoon 9x(())
(6)
g).(t) := Vn, (h) (t).()))5' e ((G)))
where a E 1R and node and edge features are omitted for clarity. We assume that time t, node obtains the values Пزi and hj (needed to compute 9::) from neighbors j E (i).. The number of iterations is dictated by the convergence of the embeddings to fixed point.
Existing optimization- based GNNs Yang et al.
2021 Zhu et al.
2021 Ma et al. 2021 use an objective Eg
where node embeddings arise as:
H arg min H go (x) Btr(HH LH),
where ge: IR + R and is applied independently to each node feature, L is a function of A and can be viewed as generalized incidence matrix (assumed to be symmetric and positive semi-definite), 7 and B are constants, and tr() is the trace. The first term drives node embeddings to approximate some function of the node features X, and the second term is regularizer that rewards smoothness of neighboring node embeddings. The overall objective Eg is separable per node. We refer to optimization- GNNs which use this form of objective as GSDGNNs, since minimizing the objective can interpreted as performing graph signal denoising (GSD).
Previous work has shown that embeddings obtained by the fixed- ixed-point message passing scheme defined by APPNP (Gasteiger et al.) 2019) and EIGNN (Liu al. 2021) correspond to minimization of this form of objective (Ma et al. [02]] Yang et al, 202T). Correspondence between fixed-point GNNs and optimization- GNNs
always be expressed as satisfying a fixed point equation (i.e., the gradient of the convex graph function is equal to zero at the solution), not all fixed-point equations correspond with convex optimization problems. For this reason, we distinguish between these two types of implicit GNNs.
based GNNs does not always exist; while node embeddings in optimization-bats
4 ASYNCHRONOUS GNN INFERENCE
In this section, we discuss GNN inference under the asynchronous execution model presented in Section 2.1 In the general asynchronous update in Equation (2) is assumed that node i has access to all of the values hi,...,, required for performing its update. In general these values could be obtained, for example, by providing nodes access to a shared memory structure which contains these values. However, in this work, we are interested the setting where neither centralized memory nor centralized controller are used, We assume that individual nodes store their own values h, (and vj e.y), and these values are needed by other nodes to perform their update, they must obtain them by communicating with neighbors. Our aim in this section is to demonstrate that node updates can be performed only using information that can be obtained through local communication.
4.1 EXPLICITLY-DEFNED GNN AND FIXED-POINT GNN INFERENCE UNDER PARTIAL ASYNCHRONISM
Without loss of generality, assume that the embedding dimension A: is fixed for all layers of parameterized node update functions. We do not write indexed by layer, but this is straightforwardly generalized to the case of layerfspecific parameters and functions described in Section 2.2 As a slight abuse of notation, let fö denote fo applied to node i's neighborhood. Without loss of generality, assume the embedding update function fo is continuously differentiable, so that the following restriction can be stated:
0. Th
j (
(z)
O Vz E
With this restriction, the general node update from Equation 2 can be adapted to describe partially asyn- chronous message passing, in which node updates are performed using only information from a node's local neighborhood. In particular, for node i and for 2 0 and t T the update equation is:
hz + 1) = fo (t,, (ha(7)(0) ( (())))
(10)
5

---

Published as a conference paper at ICLR 2025
where we omit node and edge features for clarity. Note the crucial difference introduced by asynchrony: the neighbor data h (T)())) may correspond to the incorrect layer in the network. For explicitly- GNNs such as GCN or GAT, the number of iterations |T.| executed by each node is fixed and equal to the number of layers L in the GNN. For fixed point GNNs, the number of iterations is not pre-specified.
Since explicityy-defined GNNs implement a specific feed-forward neural network architecture, inference using Equation (IO) corrupts the computation performed by the network. We illustrate this in Figure [ where asynchrony results in a (different) computation graph with some connections removed, and new connections that are not present in the original synchronous computation graph. This means that there no convergence guarantees under partial asynchrony, and in general the final node embeddings may vary significantly with respect the particular node update sequence.
In contrast, fixed-point GNNs in which Fg is contractive with respect to embeddings h are provably robust to partially asynchronous inference. particular, they satisfy the assumptions of the following proposition (Bertsekas 1983).
Proposition 4.1. Ff 9 x Rnn + Rnn contractive with respect to node embeddings h, then under the bounded staleness conditions in Theorem 2.7 the fixedpooin iteration of Equation 70 converges.
4.2
OPTIMIZATION-BASSE GNN INFERENCE UNDER PARTIAL ASYNCHRONY
In order to examine inference of optimization- based GNNs under partial asynchrony, we assume gradient-based optimization is used in computing node embeddings. Recall that optimization- based GNNs performing minimization of a separable objective Eg. as defined in Equation (5). We thus state the following restriction, analogous the restriction in Equation
deh (z) = 0 for all 2 E E 0h
j j
(11)
We could then naively adapt the general node update equations from Equation | to describe partially asynchronous, gradient- based minimization of Eg as follows:
ha = hz(t) - - (T((0)
(12)
g ()(()((())) = Cg,
(c) eN()))
(13)
where a E Ry is the step size, and node and edge features are omitted for clarity. This formulation would allow to directly cite a proof of convergence from Bertsekas and sitsiikis (1989), as we did in Section 4.1 for partially asynchronous txietpoiit GNN inference.
However, recall that for a node to perform update using only local communication, previously assumed that 93z was obtained by node from its neighbor j. With the formulation in Equations 12 and 13 node j cannot provide node i with gjı since the value depends the neighbors of node j. rather than deferring to node j's view of its neighbors. That is, node needs access to information about its 2-hop neighbors in addition to its I-hop neighbors. Since we assume communication is only possible with I-hop neighbors, 2-hop neighbor information would need to be forwarded by direct neighbors of node i. This inflates the cost of communication, requiring number of bits per transmission which is proportional to [N]]).. Furthermore, as the number of neighbors that are shared between node i and node j increases, the contents of these messages become increasingly redundant.
node i's view of the embeddings (and reatures) of
Instead, we preserve fully local communication and fixed-size transmissions where neighbors j send fixed-size packets containing only (h gjx) to node by defining 9 (1) as follows:
(T)()(())) = Vn, ( (T)(), (hy (T) (7((0) j EN())).
(14)
The crucial difference between equations Equation (3 and Equation 14) is that instead of 95; (t) depending on node i's view of 2-hop neighbors j' at time I, it now depends on neighbor j's view of its neighbors at time (1). the time corresponding node i's view of j time l.
Proposition 4.2. Eg is strongly convex and separable per node, and is twice differentiable (w.r.. H) with a Hessian of bounded norm, then for sufficiently small step size and the bounded staleness conditions in Theorem 2.1 the optimization procedure of Equations 12 and will converge when executed under partial asynchrony.
See Appendix D for a proof adapting results from Bertsekas and Tsitsiklis 1989
6

---

Published as a conference paper at ICLR 2025
5 ENERGY GNNS
Under the assumptions of Section 2.1 implicitly-eefned GNNs in which node embeddings are updated iteratively using local information are well suited for partially asynchronous, decentralized, and distributed inference. However, the diversity of existing implicit GNN architectures is limited (see Section 3
We propose a novel implicitty-defined, optimization-base GNN architecture which we call the energy GNN. Energy GNNs compute node embeddings that minimize a parameterized, convex graph function Eg, which we refer to as the "energy' function. In contrast to previous work on optimization- basedd GNNs, our energy function makes use of partially input-convex neural networks (PICNNs, [Amos al. (0177). PICNNs are scalar-vall valued neural networks that constrain the parameters in such a way that the network is convex with respect to a specified subset of the inputs. This exposes rich and flexible class of convex energy functions Eg of the form:
et
Eo(g, H) Ei= %
where
(15)
cg u (m; hi, Rz x,; 0w) + (9/2) 1 m; = ΣSEN()) m(h; hj, Fs Bj Eijs 0m)
(16)
(17)
where m is function that is both convex and nondecreasing (in each dimension) with respect to h2 and h and the function is convex with respect to m. and h; These functions are both implemented as PICNNs and their composition is convex. Summing these functions along with the squared norm penalty results in Eg being
strongly convex with respect to the node embeddings H. This architecture for the energy can be described as a (single layer) partially input-convex GNN; we provide more details in Appendix B
This formulation for Fgg offers significantly more flexibility than the architectures of other implicitly-defii GNNs. The functions m and are parameterized by multi-layer PICNNs, and any combination of inputs to and u are valid provided that Eg remains a convex function of H. This means that edge features are casily incorporated into the model, and neighbor-specific neighbor agnostic messages take in information from just a node's 's neighbor, or information pertaining to both a node and its neighbor); in experiments in Section 6.33 we show that this translates empirically to improved performance on various tasks. Since the aggregation in Equation (17) is only constrained to be a non-negative sum over neighbors, it can be replaced with, for example, a mean or sum weighted by the entries of the symmetric renormalized adjacency matrix (as in GCNs, see Appendix (A). Alternativlyy. Equation (17) can easily incorporate neighbor attention mechanism (as in GATs), where neighbor contributions to the sum are scaled by neighbor-speciff attention weights (see Appendix B. The attention weights can depend on any of the non-convex inputs (i.e., the features).
be used (e.g.. m can
EXPERIMENTS
6.1 SYNTHETIC MULTI-AGENT TASKS
We perform experiments several synthetic datasets, motivated by prediction tasks which are of interest for multi-agent systems where distributed, asynchronous inference is desirable. We describe each task and associated dataset below.
The ability to communicate information across long distances in group of agents is important when agent predictions depend on global information. This communication is made more difficult in the absence of a central controller (as is the case for distributed, asynchronous inference). The chains dataset, used in Gu et al. (2020): Liu et al. (002T). meant evaluate the ability to capture long-range dependencies between nodes, The dataset consists of undirected linear graphs with nodes, with each graph having a label & E {1,,.., P}. The task is node classification of the graph label, where class information contained only in the feature of the first node in the chain; the node feature matrix X E Raxp for graph with class k has XI, at all other indices. Perfect elassification accuracy indicates that information successfully propagated from the first node to the final node in the chain. For our dataset, we use chains with length / = 100.
Chains
and zeros
Counting Counting the number of agents in a group may be important in various multi-agen tasks. This value can be used, for example, to calculate means, in agent decisions which rely group size. We construct a dataset meant to evaluate the ability of GNNs to count in undirected chain graphs. Our dataset consists of 50 graphs with 1-50 nodes. Since no informative node features are present for this task, set
7

---

Published as a conference paper at ICLR 2025
node features one-hot embeddings of node degrees. The prediction target for each node in given graph is the total number of nodes in that graph.
Sums For this task, we consider summation, basic functional building block relevant for many multi-agent tasks. For instance, in reinforcement learning tasks, agents might aim to perform actions that optimize their collective rather than individual rewards, requiring each agent to sum the rewards associated with all other agents. Many distributed and asynchronous algorithms exist for summation (Kempe et al. 2003). We construct a dataset evaluate the ability of GNNs to perform binary sums undirected chain graphs. Our data are 2000 graphs with 50 nodes each, with different instantiations of binary node features æ; E {0, 1]. The prediction target for each node in a given graph ÿ, := Σ; Zz
Coordinates A common task for multi- agent collectives such as robot swarms is localization. This problem has previously been tackled in various ways that all employ a bespoke algorithm tailored for the task (Todescato) itt al. 2016; Huang and Tian 2017 2018). We test the ability of GNNs to solve this problem on static graphs We construct dataset where each node has a position in TR² and neighbors within some radius are connected by an edge. We do not assume global coordinate system; instead, we focus on relative localization, where pairwise distances between nodes are maintained. Each node predicts a position in IR, and the objective is the mean squared error between true pairwise node distances, and distances between their predicted positions. In order to break symmetries, each node has a unique ID which is one-hot encoded and used as the node feature. Distances to connected neighbors graphs consist of 20 nodes. We sample uniformly in the unit square to get node positions and connect nodes by an edge if they are within a distance of 0.5.
provided as edge features. We generate 1500 random graphs where all
MNIST "Terrain" " The final synthetic task we consider is "terrain" classification. Suppose a number of agents are placed in an environment where each agent performs some local measurement, and the agents must collectively make predictions about some global state of the environment using only local communication. For this experiment, we use MNIST images (those with 0/1 labels only) to represent the environment (LeCun) et al. 2010). Agents are placed at random locations in the image, and use the coordinates and pixel value at their location as their node features. The prediction target for each agent is the image label. We resize the images to 10 x 10 pixels, and sample 10 random pixels for agent locations. Nodes share edge if they are within pixels of each other. Unlike the previous synthetic tasks, in which existing distributed algorithms can be applied, no bespoke algorithm exists for the MNIST terrain task. This is precisely the type of problem which motivates the development of GNNs which are robust to asynchronous and distributed inference.
6.2 EXPERIMENTAL SETUP
For each synthetic task, we compare performance of energy GNNs to other implicitly-eefined GNNs we identified in Section 3 We employ three energy GNN architecture variants; node-wise, where messages are constructed using information from individual nodes, edge-wise, where messages are constructed using information pertaining to both nodes on an edge, including edge features. and edge-wise energy GNN with neighborhood attention. In terms of other implicitly-deii -effnee GNNs, we focus on the fixed-point GNN architecture IGNN defined by Gu et al. (2020) which is described in Appendix A and against GSDGNN, optimization- GNN which uses the objective from Equation (8). Two fixed point GNN architectures identified in Scction 3 are excluded: EIGNN (Liu al. (021) and the GNN proposed by SScarellii et al., (2009). The former is excluded because the fixed point is solved for directly in the forward pass using global information rather than iteratively using local information; the latter is excluded because fixed point convergence may not be achieved. In addition to implicitly-define defined GNNs, we also compare against two common xxplicity-deffnne GNN architectures; GCN (Kipf and Welling 2017), and GAT (Veličković al., 2018).
The cost of the forward and backward pass (in terms of computation and/or memory) for implicitly-definet GNNs is variable, depending on the number of iterations required for convergence. We mitigate this cost during training in two ways. Since convergence for both fixed-point GNNs and optimization- based GNNs is guaranteed implicit differentiation can be used to obtain gradients of the task-specific loss function L with respect to parameters 9. This avoids unrolling the fixed-point iterations in the backward pass, and requires fixed amount of computation and memory. We derive the gradient in Appendix C. Furthermore, since the solution of the forward pass is unique (i.e. not dependent on the initialization of H) the number of iterations in the forward pass be reduced by initializing H to be the solution from the previous epoch of training.
8

---

Published as a conference paper at ICLR 2025
In our work employ both of these strategies during training. Additional training details for the synthetic experiments are in Appendix F
We additionally perform experiments benchmark datasets MUTAG (Srinivasan et al. 1996), PROTEINS (Borgwardt et al. 2005), and PPI (Hamilton et al., 2017) for node and graph classification to evaluate energy GNNS as synchronous GNN architecture. Although our objective is not performance in the synchronous setting, we show that they are nevertheless competitive on each dataset. Details are provided Appendix
6.3 RESULTS
In Table we report synchronous performance of each GNN architecture on the synthetic tasks. For regression tasks (counting, sums, coordinates) task performance is calculated as the root mean squared error over the test dataset normalized by the root mean value of the test dataset prediction targets. For classification tasks (chains, MNIST) task performance is calculated as the mean test dataset classification error. Table reports performance for each task, with mean and standard deviation taken across 10 dataset folds and 5 random parameter seeds.
The results of the synthetic experiments empirically demonstrate the superiority of our energy GNN architecture compared to other -mplicitlydeffined GNNs. The node-wise energy GNN architecture improves performance over IGNN and GSDGNN, which we attribute to the use of PICNNs. When edge-wise rather than node-wise observed. information is used in constructing messages neighbors, further improvements in performance The strong performance on tasks requiring long-distance communication between nodes for correct predictions (chains, counting, and sums) shows that architecture is capable of capturing long-range dependencies between node predictions.
Table 1: Task performance on test data, reported as percentage error (relative root mean squared error for COUNT, SUM, COORDINATES), Mcan and standard deviation are across 10 random seeds and 5 train/test splits. Although inference on these experiments is done synchronously, the poor performance of the spplicitlydeffnnd GCN and GAT can be attributed their depth-limiter limited ability to propagate information.
MODEL
CHAINS
COUNT
SUM
COORDINATES
MNIST
IGNN
26.9 + 13.3
5.5
12.8
5.5
30.4 0.7
GSDGNN
35.9 6.3
4.6
0.2
4..0
2..3
ENERGY GNN NODE-WISE
17.9
19.5
1.72
41.3
13.8
ENERGY GNN EDGE-WISE
1.2
4.0
4.3
3.2
13.0 0.6
ENERGY GNN + ATTENTION
0.25
3.8
6.0 4.0
4.8
13.8 + 0.8
GCN GAT
+7.00:...
1.0
13.1 + 0.3
53.2 2 0.9
29.7 + 0.5
47.0
4.8
12.9 + 0.5
39.3 1.0
15.3 - 3.2
Table 2: Decrease in task performance (decrease in accuracy for CHAINS, MNIST, and increase in relative RMSE for COUNT, SUM, COORDINATES) observed from switching from synchronous asynchronous inference sub-sample of data (10 samples) using one trained model instance. Mean and standard deviation are across asynchronous runs, The poor performance GCN GAT are consistent with the expected unreliability explicilly-defined GNNs asynchronous inference. Decreases in task performance for all implicitly-defind GNNs (IGNN, GSDGNN, and energy GNN variants) is less than 0.1% (i.e. result from numerical error); these values omitted from the table for concision.
MODEL
CHAINS
COUNT
SUM
COORDINATES
MNIST
GCN GAT
38.8 3.3
584.6 42.4
2.6 + 0.2
63.4 0.0
37.4 + 10.3
1.8
250.3 + 58.6
45.1 + 2.1
97.0 + 34.4
50.4 + 3.5
In 2 we demonstrate empirically that explicitly-definel architectures such as GCN and GAT perform poorly and unreliably under asynchrony, with task performance decreasing for all experiments. In our experiments, simulate asynchronous inference; of the performance decrease large as a result of inconsistent predictions under different random node update schedules and communication delays. In cases where the variance is low, observe that predictions
algorithm is in Appendix [ In most cases the variance

---

Published as a conference paper at ICLR 2025
for different random schedules collapse to the same/similar values due non-linearities in the architecture. For implicitly-define GNNs, the decrease in performance under asynchronous inference is less than 0.1 0.1%, empirically confirming the convergence guarantees given by Proposition 4.1 and Proposition 4.2
RELATED WORK
Dudzik et al. (2023) axiomatically derive GNN layers which are invariant to asynchrony. For instance, using max- aaggreattonn for messages is by construction invariant to asynchrony; messages from neighbors can be processed as they arrive rather than waiting for all inputs to be available, and the final aggregated message will still be correct. Later work in this thread aims at enforcing asyncrony invariance through self-supervised loss function rather than using layers which are asynchrony invariant by construction (Monteagudo-Lage et al. 2024). The motivation for this line of work is apply GNNs for neural algorithmic reasoning, where the GNN is trained to emulate classical algorithms such as the Bellman-Fore algorithm. Enforcing asyncrony invariance in the GNN serves improve alignment between the algorithm be learned and the GNN computation. The asynchronous model of computation used in these works differs from ours in that nodes must maintain information from all layers in the GNN, rather than executing layer-wise.
Faber and Wattenhoter (2024) also explore asynchronous communication between nodes during GNN inference. Their approach consists of processing node updates in a queue, rather than applying all node updates in a layer in parallel. The goal of their work is to leverage sequential node updates to improve under-reaching and over-squashing in learned node embeddings. Asynchronous execution in their model is deterministic in that there are no random delays in communication between nodes; nodes receive messages and perform updates in the same order across different runs. They show that random delays and node update orderings leads to unstable training and results in decreased task performance. This makes their approach unsuitable for the settings we consider, in which asynchrony is not controlled.
8 CONCLUSION
GNNs have the potential to provide learning frameworks for decentralized multi-agent systems, with appli- cations to robotics, remote sensing, and other domains. However, asynchronous execution and unreliable communication between agents are common features in real-world deployment, and conventional GNN architectures do not generate reliable predictions in this setting. In this work, we characterize the class of implicitly-defiin deffned GNNs as being provably robust to partially asynchronous inference. Motivated by lack of diversity in this class of architectures, we contribute a novel addition in the form of energy GNNs, which achieve better performance than other implicitlydeffined GNNs on number of synthetic multi-agent tasks.
The positive results of our synthetic experiments motivates additional work in applying GNN architectures to multi-agent systems, particularly making use of implicitly-defii control tasks, rather than for prediction tasks. A specific line of work which we expect to be interesting is real-time inference on dynamic graphs because the relevance to problems in, e.g., robotics. Distributed and asynchronous inference for datasets consisting of large graphs, where inference must be distributed among multiple processors due to scale, is another application for implicitly-defined GNNs which should be explored.
GNNs to generate state representations for
There are several limitations of this work, particularly in training implicitly-defiie deffneed GNNs. The forward pass re- quires convergence of node embeddings via a fixed point iteration, and requires an amount of time/computation that cannot be known in advance. During training, we decrease the number of iterations required for conver- gence by initializing node embeddings to those from the previous epoch of training. Real-time inference in multi-agent systems is likely to also enjoy the benefits of warm-start initialization. This is because the graph features and structure are often expected to change slowly over time, meaning that after an initial "boot-up" from random initialization, a continuously operating implicitly-defined GNN is likely to have embeddings initialized close to the solution from one time step to the next (assuming the node embeddings H are not extremely sensitive to small changes in the graph). For optimization- based GNNs using gradient-based optimization in the forward pass, the condition number of the Hessian of Eg affects the convergence rate, but is difficult to control. Similarly, if F& is poorly conditioned in fixed-point GNNs, convergence can be slow and is susceptible to numerical instability. During training, we use implicit differentiation to obtain gradients w.r.t. parameters rather than simple backpropagation; this avoids unrolling through the iterative process in the forward pass, but requires solving linear system using the Hessian of Eg (for optimization-ban based GNNs) or the Jacobian of F, (for fixed-poin GNNs), either of which may be poorly conditioned. Finally, operationalizing the theoretical results may require constants that are not readily available.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was partially supported by NSF grants I1S-2007278 and OAC-2118201.
11

---

Published as a conference paper at ICLR 2025
REFERENCES
B. Amos, I.. Xu, and J. 7. Kolter. Input convex neural networks. In Proceedings of the 34th International Conference on Machine Learning, volume 70, pages 146-155, PMLR, 2017.
D. Bertsekas. Distributed asynchronous computation of fixed points. Mathematical Programming, 27(1): 107-120, 1983.
D. P. Bertsekas and J. N. Tsitsiklis. Parallel and distributed computation: Numerical methods, 1989.
J. Blumenkamp, S. D. Morad, J. Gielis, Q. Li, and A. Prorok. A framework for real-world multi-robot systems running decentralized gnn-based policies. 2022 International Conference on Robotics and Automation (ICRA), pages 8772-8778, 2021.
K. M. Borgwardt, C. S. Ong. S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21:147-156, 2005.
A. J. Dudzik, T. von Glehn, R. Pascanu, and P. Veličković. Asynchronous algorithmic alignment with cocycles. In The Second Learning on Graphs Conference, 2023. URL htttps:///pperreeeetstt Id=ba4bb24KKF]
wwt. forum?
V. P. Dwivedi, L. Rampášek, M. Galkin, A. Parviz, G. Wolf, A. T. Luu, and D. Beaini. Long range graph benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Truck, 2022. URL BRRLittps:///peereeree wtt.i/ewwweeeeeeeeeeeeeeeeeeeeee (xce:r/
L. Faber and R. Wattenhofer. Gwac: Gnns with asynchronous communication. In Proceedings of the Second Learning on Graphs Conference, Proceedings of Machine Learning Research. PMLR, 27-30 Nov 2024. URL https://ppppt httss:///occeeinggs..iio http:/pprree///2//aae//2222 html
F. Gama, Q. Li, E. V. Tolstaya, A. Prorok, and A. Ribeiro. Synthesizing decentralized controllers with graph neural networks and imitation learning. IEEE Transactions on Signal Processing, 70:1932-1946, 2020.
Gasteiger, A. Bojchevski, and Günnemann. Combining neural networks with personalized pagerank for classification on graphs. In International Conference on Learning Representations, 2019.
J. Gilmer, S. S. Schoenbolz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. International Conference on Machine Learning, pages 1263-1272. PMLR, 2017.
M. Goarin and G. Loianno. Graph neural network for decentralized multi-robot goal assignment. IEEE Robotics and Automation Letters, 95)::18, May 2024. ISSN 2377-3766. doi: 10.10091LRA.222.3377110 Publisher Copyright: C 2016 IEEE.
W. Gosrich, S. Mayya, R. Li, J. Paulos, M. Yim, A. Ribeiro, and V. Kumar. Coverage control in multi-robot systems via graph neural networks. In 2022 International Conference Robotics and Automation (ICRA), pages 8787-8793, 2022. doi: 10. 11110/9C//4666992000 9112249111154
D. Grattarola, I.. Livi, and C. Alippi. Learning graph cellular automata. Advances in Neural Information Processing Systems, 34:20983-20994, 2021.
Gu, H. Chang, W. Zhu, S. Sojoudi, and El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems, volume 33, pages 11984-11995, 2020.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30, 2017.
W. L. Hamilton. Graph representation learning. Synthesis Lectures Artificial Intelligence and Machine Learning, 14(3):1-159, 2020.
X. Huang and Y.-P. Tian. Localization in sensor networks with communication delays and package losses. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), pages 3974-3979, 2017. doi: 10. 2WW.CDDC.2017.82442444
Z. Huang and Y.-P. Tian. Asynchronous distributed localization in networks with communication delays and packet losses. Automatica, 96: 114-14440 10 2018.
12

---

Published as a conference paper at ICLR 2025
C. Jiang, X. Huang, and Y. Guo. End-to-end decentralized formation control using a graph neural network- based learning method. Frontiers in Robotics and AI, 10, 2023. ISSN 2296-9144. doi: 10.3389/ frobt.2023.128541.. htttt:///w/eee www.:frrome frontiersin. org/ journals articles/10, 0tt.cceees/..3399//// Frobt 2023. 1285412
J. Jiang and Z. Lu. Learning attentional communication for multi-agent cooperation. In Neural Information Processing Systems, 2018.
J. Jiang, C. Dun, T. Huang, and Z. Lu. Graph convolutional reinforcement learning. In ICLR, 2020.
D. Kempe, A. Dobra, and J. Gehrke. Gossip-based computation of aggregate information. In 44th Anmual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pages 482-491. IEEE, 2003.
A. Khan, E. V. Tolstaya, A. Ribeiro, and V. R. Kumar. Graph policy gradients for large scale robot control. In Conference on Robot Learning, 2019.
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Y. LeCun, C. Cortes, and C. Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http://yann.lecm http://www.cc.../////////eaaae/e wwt.///mm///iistttt.oooomo 2, 2010.
Q. Li, F. Gama, A. Ribeiro, and A. Prorok. Graph neural networks for decentralized multi-robot path planning. CoRR, Abss/912..0605, 2019. URL / 06095
J. Liu, K. Kawaguchi, B. Hooi, Y. Wang, and X. Xiao. Eignn: Efficient infinite-depth graph neural networks. In Advances in Neural Information Processing Systems, 2021.
Y. Ma, X. Liu, T. Zhao, Y. Liu, J. Tang, and N. Shah. A unified view on graph neural networks graph signal denoising, 2021.
Monteagudo-Lage A. Rosinski. A. Dudzik, and Veličković. Asynchrony invariance loss functions for graph neural networks. In ICML 2024 Workshop on Geometry-grounded Representation Learning and Generative Modeling, 2024. URL htttps://openrevieee wtw.ppeeeeeeeeeeeeeeerrrrrra wow.orrmmmmeeeeeeoooo.o..
K. Nakashima, S. Kamiya, K. Ohtsu, K. Yamamoto, T. Nishio, and M. Morikura. Deep reinforcement learning- based channel allocation for wireless lans with graph convolutional networks. 2019 IEEE 90th Vehicular Technology Conference (VTC2019-Fall), pages 1-5, 2019.
Niu, B. Recht, Re, and S. Wright. Hogwild!: A lock-free approach parallelizing stochastic gradient descent. In J. Shawe-Taylon Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger, editors, Advances in Neural Information Processing Systems, volume 24, 2011.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEFE Transactions on Neural Networks, 20(1):61-80, 2009. doi: 10.1109/TNN 20.1099/NNN20000205500 20056000505..
A. Srinivasan, S. H. Muggleton, M. J. Sternberg, and R. D. King. Theories for mutagenicity: A study in first-order and feature-based induction. Artificial Intelligence, 85(1-2):7772999 1996.
M. Todescato, A. Carron, R. Carli, A. Franchi, and L. Schenato. Multi-robot localization via gps and relative measurements in the presence of asynchronous and lossy communication. In 2016 European Control Conference (ECC), pages 2527-2532, 2016. doi: 10.110//CC..011...888 781006...
P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL http://////eeeeveww.nemm 6115mmm
Y. Yang, T. Liu, Y. Wang, Z. Huang, and D. Wipf. Implicit vs unfolded graph neural networks, 2021.
L. Zhou, V. D. Sharma, Q. Li, A. Prorok, A. Ribeiro, P. Tokekar, and V. R. Kumar. Graph neural networks for decentralized multi-robot target tracking. 2022 IEEE International Symposium on Safety, Security, and Rescue Robotics (SSRR), pages 195-202, 2021.
M. Zhu, X. Wang, C. Shi, H. Ji, and P. Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 2215-1226, 2021.
13

---

Published as a conference paper at ICLR 2025
A GNN ARCHITECTURES
2017 replace the adjacency matrix with the symmetric normalized adjacency matrix with added self-loops, A (D + I) (A +I) With node embeddings initialized to be equal to the node features, fa is defined as:
Graph Convolutional Networks GCNs (Kipf and Welling
m = ΣjEN(O) A h
h++1= := ReLU(mm))
(18)
where 0 R X
This update
be succinetly described at the graph level Note that for explicitly-defined message passing GNNs which have
H = ReLU(AAH L layers, such as GCN, it is impossible to propagate information farther than L hops.
Graph Attention Networks GATs (Veličković al. 2018) apply attention mechanism determine the weighting of information from different neighhors. With node embeddings initialized to be equal to the node features, fg is defined as:
te,,e,lle h2)))) 0s EnEN(i) exp (LeakyReLU(( [0 himli h. h,
exp (Leaky
(19)
m = Ejev() 0i h
(20)
b f-1 = RellU(mm)),
(21)
where of E [Rxx and 0g E 2229 are additional parameters used in aggregation. Multiple attention heads be used, in which there are lt aggregation functions with their own parameters. The messages generated by each of the attention heads are either concatenated or averaged to generate single message m
Implicit Graph Neural Networks (IGNNs) IGNNS Gu et al. (2020) are fixed point GNN architecture, in which each parameterized node update layer is contractive with respect to the node embeddings. For simplicity, we assume a single parameterized layer fo and exclude the layer superscript from our notation. The parameterized node embedding update is repeated for steps = O,.... T - 1, where the stopping point T determined by when node embeddings converge (within some numerical tolerance). IGNNs use similar embedding update function GCN, but add node features an additional input to the update function. A layer fe is defined as:
(t) = EjEN() (,
h. (t + 1) == (t) + g( (w));
(22)
where 8m E kxk 9o R + Rank and & is a component-wisg wise non-expansive function such as ReLU. Convergence is guaranteed by constraining [|0m ao < (A) -1 where Aps (A) is the maximum eigenvalue of [ This ensures that the update is contractive, sufficient condition for convergence. Since the fixed point is unique, (0) can be initialized arbitrarily (although convergence time will vary).
Efficient Implicit Graph Neural Networks (EIGNNs) EIGNNs Liu et al. (222]) are another fixed point GNN architecture which are very similar to IGNNs, The message passing iteration is constructed such that closed-fone solution can be obtained for the fixed point of layer, which is more efficient than iterating message passing to convergence. A layer fo is defined as:
m!(()= = T (O.),,() ((;))
yo..A.,
h + 1) m.(() + æs,
(23)
where 6m E _ a > O is scaling factor equal to [[ (" with arbitrarily small e, and E (0, 1] is an additional scaling factor. The overall scaling factor you is chosen to ensure that the update is contractive, from which it follows that the sequence of iterates converges.
Nonlinear Fixed Point GNN
Scarselli et al. (009) introduce general nonlinear fixed point GNN whose
update can be written as
mi(1) Σ
m7; By exg; 0m.)
(24)
JEN())
(t + 1) u(m (t), f),,.)) (t), 2;;00,
(25)
where m and u are multi-layer neural networks. As we discuss in Section 3 this flexible parameterization of message passing comes at cost: it is difficult to enforce that the overall update is definitely contractive.
14

---

we refer to the resulting architecture m in Equation (17) corresponds PICNN which has node embeddings h4, I.....M n as its convex inputs (all other features are non-convex inputs). A second PICNN corresponds with the update function u in Equation (16), which convex in the node embeddings and the messages computed by the message function, Published as a conference paper at ICLR 2025
B INPUT-CONVEX GNN ARCHITECTURE DETAILS
As in Amos et al. 2017). we construct a parametric family of neural networks fa(x, y) with inputs E In y E EK" which are convex with respect y (i.e. subset of the inputs). An L-layer partially convex neural network is defined by the following recurrences:
41+1 Dr( WW,, + br)
Z1+1 - -96(
w (ze (W ur + +b,
w (y (W(vw) (vw) us + b, ((2) 1)+
8
W (1) ue be)
fa y) 21 Uo = σ; 20 = 0
Provided the (=) are elementwise nonnegative for all layers and the activation functions ge are non- decreasing in each argument, it follows that fe is convex in
In the context of energy GNN, Eg comprised of two PICNNs, specialized to operate on graph structures; partially input-convex GNN (PICGNN). The message function
and nonconvex in the node features. The graph energy Eg can then be written as the sum of the outputs of the second PICNN.
B.1 NEIGHBORHOOD ATTENTION
We can incorporate neighborhood attention mechanism in the PICGNN by modifying the aggregation of messages m, as follows:
m. = Ejen(y) aiym(hi h2s 0i, Fj Cij; 0m)
where
(26)
exp (LeakyReLU(O.) (0 x x.110m, x; 10, ex,l))
aij EnEN(s) exp (LeakyReLU((Oo)) 10 x 0 x; 110m, eig)))
(27)
where 6n, E R2*P, On. E RR*x and 0g E 12 are additional parameters used in aggregation. As in GATs, multiple attention heads can be used, in which there are k aggregation functions with their own parameters. The messages generated by each of the attention heads are either concatenated or averaged to generate a single message m.
C IMPLICIT DIFFERENTIATION
Since we use an optimization procedure to compute the node embeddings within the forward pass in implicitly- defined GNNs, need to obtain derivatives of the node embeddings with respect the parameters of the model. We compute derivatives by implicitly differentiating the optimality conditions. For fixed-point GNNs, use the fact that the fixed point, have parameters 6* E R and node embeddings H E R such that:
g(H', B) fo (o =
(28)
For optimization-basse GNNs, we use the fact that at the solution of the minimization problem, we have:
dEg-
g H 0)
( 0.
(29)
HH
Let hi* hi*())= H", that can write the optimality conditions in terms of the parameters only:
g(h (0"),') 0.
(30)
15

---

Published as a conference paper at ICLR 2025
Given objective L IR" > R, the desired quantity is the total derivative of L with respect to the parameters. By the chain rule,
dC
dh 0C
OC
(31)
db
oh
d6
00
BC and ac using normal automatic differentiation, and the solution Jacobian di We compute 8h B0 differentiation. Notice that, the fixed point (where the optimality constraint is satisfied), we have:
do using implicit
d g(
(0), 0)
(32)
do
0g dh-
0g
(33)
Oh d0
00
0g dh'
0g
(34)
Th d0
ae
This is the primal (or tangent) system associated with the constraint function In our setup we utilize reverse mode automatic differentiation, since p >>>>> 1 parameters are mapped to single scalar objective. Provided a invertible, we can rewrite the solution Jacobian
dh
0g - 0g
(35)
d0 Oh 00
and substitute this expression into Equation
(31) as follows:
dC 0L 0g - 0g 0c
+ 00
(36)
de ah Oh 0e
For reverse mode, we compute the dual (or adjoint) of this equation,
dC
0g" T
0g
OL T
OC
(37)
d8
00
Th
00
And solve the dual system:
0g
Oc
X
(38)
Oh
for the dual variable
D PROOF OF CONVERGENCE UNDER PARTIAL ASYNCHRONY
Our guarantee of convergence uses the classical result from Bertsekas and Tsitsiklis 1989 Chapter 7.5), which depends several formal assumptions. We reproduce these assumptions here, in the notation used in the present paper, and address how they are satisfied our problem setting. In the following, s,) is the "search direction" taken by node i, i.e., the vector used by node to take optimization step. Ideally, this would be the negative gradient - v., Eg, but partial asynchrony means may be a vector constructed from stale information. Our goal is to show that convergence of the optimization is nevertheless guaranteed. We use E Rnn to denote the unrolled embeddings H.
Assumption D.1 (Bertsekas and Tsitsiklis (1989) Assumption 5.1)
(a) There holds Es Z for every T.
(b) (Lipschitz Continuity of Eg) The function Eg is continuously differentiable and there exists a constant K1 such that
(h) FFg(h')l S - Yh, h/ RRk
For part (a), since both convexity and absolute continuity are preserved under nonnegative summation, the graph energy E given in Equation (5) is smooth, strictly convex function. Without loss of generality, we can assume the node energies cp described in Equation (5) satisfy eg 2 for h, E Rd. This follows because the ea are strictly convex. therefore the optimal value P (nf thus é cg P is nonnegative. Thus, have that the graph energy is the sum of nonnegative terms: h2,, h, for all (h ha...,..... h.)) E B
achieved and
For part (b), the assumption of the eg having a bounded Hessian implies that their sum also has a bounded Hessian, which further implies Lipschitz continuity of the gradient of Eg.
16

---

Published as a conference paper at ICLR 2025
Assumption D.2 (Bertsekas and Tsitsiklis (1989) Assumption 5.5)
(a) (Block- Descent) There holds st(t) Eo((t)) I /|ss((t)ll//ks for all i and all t E T
(b) There holds ||s,(t]]| 2 Eo for all and all t T*.
For part (a), the situation is slightly more complex than the conventional optimization setup, as the gradients for the search direction st(t) are being computed from polentially-outdatedd outdated neighbor embeddings, rather than it being the gradients themselves that are outdated. Writing the negative search direction for node i at time t in terms of the update times 7t), we have
(1) == (1)
(39)
h.. = -..ce + (Vnc) ...
(40)
JEN(()
where the the gradient communicated from node may have used stale versions of the embedding both for node: itself and for other nodes connected j. Contrast this with the "true" gradient computed at which would be computed from its current estimate of the complete state of the graph:
Vv, (t) Vn, e (h1 (TI(t), ..... h (t)) Σ
Vn. (t)))) (t))
(41)
JEN())
We introduce the following notation to simplify the exposition:
k/W (t) Vn, of V (1 (f))).... h (T (1))) 9
(42)
which can be read as "gradient of eb with respect h, from the perspective of node the time corresponding to some node k's view of node j at time t.". With this notation, we define
(t) 9
Σ
(t)(()
V (t((t))) (t)+ Σ (
(43)
JEN()
JEN(()
We wish to show that the inner product between (t( and Vn, (h((tt) is greater than [|s:(t]] for some K3 > and all i and t.
Lemma D.3
There exists an >> 0 such that (t) (V,,,,, (a(tt)) 2 (t)l//)
Proof. Starting with the squared error in the negative search direction:
[[:(()) Vn, Es (h = (l) Vn, Es (b(())) (5:(1) Vn, En((())
(44)
= (1) Ea (h(())) - 21; Vn, Ea((t))
(45)
we find an expression for the inner product:
st) Vn, (b)(tt) (1)) I|V Es (t(t)) (1)((() Vn, Eo(
(46)
and require the following to be greater than equal to zero:
(t) T Eo((tt) - [t)l|/ K3
2
(1 K₃
(1s,(()) + I1 (B) 11 Vn, Eo (hh
(47)
We can use the triangle inequality to find an upper bound on the term being subtracted:
(t) Vn, (b(()))
01/000 + Σ
(1+++++++++++++
(48)
JEN())
JEN(()
///(00) 9ff110
(49)
jEN())
Σ
(1/%//())) 0///
(50)
JEN(()
Σ (
(n,c)((((7()))))
JEN(()
(51)
17

---

Published as a conference paper at ICLR 2025
Any difference between the states ((T and (t)) would arise because node i and node observe different staleness states of one more of their shared neighbors j'; these different staleness states correspond to differences in the number of gradient steps taken by shared neighbors j'. as observed by node i and j. Note that we can assume that node i and agree the values of neighbors j' of either node i or which are not shared between them. Assuming the norm of the gradient bounded, i.e., Il, diil2 S Ko, and the number of neighbors a node has is bounded, i..., IWG') I Amax. then the staleness bound B and the step size a imply h(T (t))l2 I aB where
||((T
Bo == 2m (1) (NU)B
(52)
where we assume (1) includes node itself. The constant 2 in the incquality above arises because the staleness of the gradient received by node i from node is outdated by at most B time units, and node j's view of its neighbor embeddings is also outdated by at most B time units; this means the staleness of the embeddings in the gradient received by node i is stale by at most 2B time units. The Lipschitz continuity condition then gives
Vh, (( - V & Ko
(53)
and therefore
(t) W, Eo(h(tt) ||:((t)1//KK
(54)
1
(1
[|)]( + Es (1,,(t) - Vn. Es
(55)
2
K3
1
22
(1
(1,,(()) + V - (cNN0)
(56)
K3
We therefore satisfy the assumption by choosing & > 0 such that
(1 Kg (1)) VI Es (h
2 a
(57)
(No(i)Bo,,K)))
For part (b) we require there to exist lower bound on the magnitude of st(t) relative the magnitude of the true gradient; this prevents the step from being too small.
Lemma D.4
There exists an a >> O such that 8, (1) VA, (a(()) Z (1)(
Proof. We can use a nearly identical argument to that done above in part (a), but instead of Equation (54) we write
(.(t) T Vn, (t))(() - ((((())))KK/VVAFFa(((())))
(58)
2 (115,()))1 + (1- 2kg Vv, (lo -15,(() VA, (ob((t))
(59)
2 2 (115,(t)11 + l BBV:://...AAAA000------CCC011111
(60)
We can then choose a to be
+ 21 aa²
(61)
(L
Lemma D.5
Vn, (t)
(o((t) E. then ||s:(t]]| 2 K2 Eo(((t)))
Proof. Noting that [ts((t)]| [|s,(t]], we have
||s;(0)) 1IV Ee((t)) Vn, > Rn (a(
(62)
Dividing both the left and right sides by ||V Eo((()) gives the desired result.
Having satisfied the assumptions, we can now apply the result that guarantees convergence. Proposition D.1 (Bertsekas and Tsitsiklis (1989), Proposition 5.1). Under Assumptions 2.7 D.
and
D.2 there exists some ag > (depending on n, B, K,. and Kz) such that if then lime-soo V (h())) 0.
a
Og
18

---

Published as a conference paper at ICLR 2025
E ASYNCHRONOUS GNN IMPLEMENTATION
In our asynchronous inference experiments, we simulate partially asynchronous execution (see Algorithm D We fix the maximum staleness bound to B = 5. Node updates are staggered across time and messages sent between nodes can incur delays. In particular, when a node updates, its next update time is selected randomly between time + 1 and t + S, where S := 5 is the "stagger" time, and one of the last D == values of its neighbors is chosen for performing the node update. This satisfies assumptions and 2 of partial asynchronism; nodes update at least every S time units, and messages node's view of its neighbors is stale due to message delay by at most D time steps.
F EXPERIMENT DETAILS (SYNTHETIC EXPERIMENTS)
F.1 ARCHITECTURE DETAILS
For all -mplicitlydeefned GNN architectures, we use the same node embedding size with h; E R2, The architectures are chosen such that the number of parameters approximately equal between models (with the constraint of using the same node embedding size). All architectures employ an output function og which is parameterized as an MLP with layers (4, 4, 1) ((4, 4, 2) for the coordinates experiment, as node predictions are positions in R.).
Energy GNN For energy GNN, we use PICNN with layer sizes (4,4,2) for the message function
in Equation 17 and a PICNN with layer sizes (4, 4, 1) for the update function u in Equation (16). The aggregation in Equation (77) uses the entries of the unnormalized adjacency matrix A with self-loops added. We add an independently parameterized self-loop to the message passing function m (instead of using the same parameters as for neighbors). We set = 0.04.
Energy GNN Attention For energy GNN with the attention mechanism, the attention weights asy are computed as in Equation (19); however, to maintain convexity with respect to the embeddings, the node and edge features (if present) are used in rather than using the embeddings h. We use 2 attention heads, where the attention head outputs are concatenated to form the message m, in Equation (7
For GSDGNN (where Equation (8) describes the optimization objective for obtaining embed- dings), parameterize go as MLP with layer sizes (16, 16, 16,2). 2). We use the symmetric renormalized Laplacian matrix L = I A
GSDGNN
(D + I) (A + I) + I) for the Laplacian regularization term, and set 7 1.0, 3 = 5.0. (Note that gradient- based optimization of this objective function has direct correspondence to the embedding update funetion of APPNP APPNP Gasteiger et (2019))
IGNN For IGNN (described Equation (22). we parameterize go Raxp Bank as an MLP with layer sizes (16, 16, 16.
GCN and GAT For GCN, we use 5 layers of message passing with layer sizes (10, 10, 10, 10, 10). For GAT, we use 5 layers of message passing with layer sizes (3, 3, 3, 3, 3), and concatenate the output of 3 attention heads at each layer.
F.2 TRAINING DETAILS
For binary classification experiments, we use binary cross entropy loss for training. For regression experiments, we use mean squared error. We use the Adam optimizer with weight decay, where we set the optimizer parameters as a = 0.001, 3 = 0.9, 3322 = 0.999. We set the learning rate to 0.002, and use exponential decay with rate 0.98 ever 200 epochs. In the forward pass for IGNN, we iterate on the node update equation until convergence of node embeddings, with a convergence tolerance of 10 5. The maximum number of iterations is set to 500. In the forward pass for the optimization-ba based GNNs, we L-BFGS to minimize Eg w.r.t node embeddings, with a convergence tolerance of 10-5 5 The maximum number of iterations is set to 50. We train for maximum of 5000 epochs. These experiments were performed single NVIDIA RTX 2080 Ti.
19

---

Published as a conference paper at ICLR 2025
Algorithm Simulated asynchronous GNN inference
Initialize each node in & with all GNN parameters, its own node features X,, and for each of its neighbors J. the node and edge features x, Exj. and weights Ai, Let L be the number of layers in the GNN, equal to for implicitly-defing
GNNs. Let T be the total number of simulated node updates. Let n be the number of nodes in the graph. Let S be the maximum number time units between updates for any node, and D be the maximum delay incurred by messages from neighbors.
procedure UPDATENODEOPTTHH X, E. A, 0,
> Sum of nodes current view of neighbors' gradients
g: f- EjeNGiju (1))
b Node latent update a single gradient step
h; + thi-- agg
b Node gradient is updated with new latent value
96j ah, (Hz(t)(t))),
Beb
VJENUi
procedure UPDATENODEFINITE HH, X, E, A,0,t,
D Update node message and latent m. DENN( m' (hi, h (T) 24, 0% h; - u (mi his Øz; 01:)
procedure SIMULATEASYNC(X. E, A,T.T,,,,S,D)D).
update time fimettte_tmeeee----- f- [] for i = 1....., do
b Initialize current iteration count.
4 5-0
b Randomly select first update time in (1, update _timet Uniform(1,
update sineee_tte@eeee <- update_time,
for MerjeNe (i)) do b Initiaaizee staleness view of each neighbor 0
for / 0...., do
update_non soceeeenoeese-eeee <- (i=11 1,......
update_timel = 1}
for E cocdatc_nodeer do if t, < L then
for neighbors j of node do
Sammle an updated stale view for node
(T-)² Uniform(0. (0, min(t T). D))
T- (T))'
& Update the current node (finite GNN shown) UndateNodeFFnite(HH X, E, A, 0, 4.
Randomly select next update time in (0, S)
update time, ~ Uniform(1, S) update time [i] + aadate_time, b Increment current iteration
t, - t +1
else
D Use readout to compute output
0: o
20

---

Published as a conference paper at ICLR 2025
G EXPERIMENT DETAILS (BENCHMARK DATASETS)
G.1 DATASET DETAILS
The benchmark datasets we report performance for are MUTAG, PROTEINS, Peptides-fund and Peptides- struct, where the prediction task is graph dlasification/regrssion. and PPI, where the prediction task is node classification.
MUTAG MUTAG dataset consisting of 188 graphs, each of which corresponds nitroaromatic compound (Srinivasan et al., 1996). The goal is to predict the mutagenicity of each compound on Salmonella typhimurium. Nodes in the graphs correspond to atoms (and are associated with a one-hot encoded feature in I corresponding to the atom type), and edges correspond to bonds. The average number of nodes in graph is 17.93, and the average number of edges is 19.79.
PROTEINS The PROTEINS dataset Borgwardt et al. (2005) consists of 1113 graphs, each of which corresponds to a protein. The task is predicting whether or not the protein is an enzyme. Nodes in the graph correspond to amino acids in the protein (and are associated with node features in R representing amino acid properties). Edges connect amino acids that are less than some threshold distance from one another in the protein. The average number of nodes is 39.06, and the average number of edges is 72.82.
Peptides-fune & Peptides-struct The peptides-fung and peptides-struct datasets Dwivedi et al. (2022)
consist of the same 15535 graphs, with different prediction targets. Each graph corresponds to a peptide; nodes correspond to heavy atoms (and are associated with 9 categorical node features representing atom properties) and edges correspond to bonds (and are associated with 3 categorical edge features representing bond properties). For peptides-func, the prediction task is multi-label graph classification (10 classes) of the peptide function. For peptides-struct, the prediction task is graph regression of various peptide properties (11 regression targets). The average number nodes in a graph is 150.94, and average number of edges is 307.30. We use train/valid/test split consistent with Dwivedi al. (2022).
PPI The PPI dataset (Hamilton) 2020) consists of 24 graphs, each of which corresponds to protein-protein interaction network found in different areas of the body. Each node in the graph corresponds to protein, with edges connecting proteins that interact with representing some properties of the protein. Each protein has 121 binary corresponds to some ontological property that the protein may may not have. We use 20/2/2 vtain/vali//test split consistent with Hamilton et al. (2017).
associated with features in 50 another. Nodes prediction targets, each of which
G.2 RESULTS
For all experiments with benchmark datasets, we use the same training procedure and architectures as described in Appendix F For node classification tasks, the final layer of output function os is modified to use layer sizes (4, 4, (num_classes)) where num_classes is the number of distinct class labels. For graph classfficationrregression tasks, we obtain graph-level predictions by passing the mean of the node-level predictions through a graph readout function parameterized by an MLP with layers (4, 4, (num classes))
For PROTEINS and MUTAG, we perform 10-fold cross validation and report average classification accuracy and standard deviations in 3 For PPI, we use a 20/2/2 train/valid/test split consistent with Hamilton al. (2077), and report average micro-fl scores in Table 4 For Peptides-func and Peptides-struct, we use train train/valid/test split consistent with Dwivedi et al. (0022 and report average precision and mean average error, respectively, in T Non-asterisked values correspond to our experimental setup, where the number of parameters (and embedding dimension) is equal across architectures. When parameter numbers are equal, the energy GNN architecture achieves the best performance on MUTAG, PPI, and Peptides-fune, and achieves competitive performance PROTEINS and Peptides-struct. We note that these reported results under synchronous evaluation (similar to the synthetic experiments, Table 6 demonstrates that under asynchronous execution, we observe decrease in performance for GCN and GAT, the representative explicitly-defined defined GNNs).
In Tables andd 4 we also include performance reported by other works (marked by asterisk), which correspond to architectures using a higher number of parameters and larger embedding dimensions. Where layer specifications are not included (for asterisked values), we were unable determine them from the eited
21

---

Published as a conference paper at ICLR 2025
DATASET
MODEL
MUTAG
PROTEINS
Energy GNN (edge-wise)
87.6 + 3.4
72.5 + 0.3
Energy GNN + attention
79.5 + 1.8
72.5 0.5
IGNN (1 layer)
73.0 0.6
71.8 + 1.3
GSD GNN
78.4 2.2
72.8 + 0.8
GCN (5 layer)
78.0 + 1.4
73.7 0.5
GAT (5 layer)
76.1 + 1.5
71.7 + 3.2
GCN (Xu et al.
2019
(5 layer, embedding dimension=64)
85.6 5.8
76.0 + 3.2
IGNN
Gu et al
2020
(3 layer, embedding dimension=32)
89.3 6.7
77.7 = 3,4
GIN (uu et al.
2019) layer, embedding dimension=64)
89.4 + 5.6
76.2 + 1.9
Table 3: Graph classification accuracy (%) Results are averaged (and standard deviations are computed) using 10 fold cross validation with random parameter seeds. Asterisked values are obtained from the work cited. Non-asterisked values correspond to architectures with the same number of parameters and 2-dimensional embeddings.
MODEL
miero fl
Energy GNN (edge-wise)
76.2
Energy GNN attention
76.0
IGNN (1 layer)
75.5
GSD GNN
76.0
GAT (5 layer)
74.3
GCN (5 layer)
76.2
MI.* Gu et al. 2020
46.2
GCN*
Gu ct al 2020
59.2
GraphSAGE= Veličković al. 2018) (3 layer, embedding dimensions=(512, 512, 726])
76.8
GAT VVeličkovic et al.
2018) (3 layer, embedding 10mension=1024)
97.3
IGNN*
al. 2020
layer, embedding dimensions=11024, 512, 512, 256, 121))
97.6
Table 4: Mean micro-Fl score for node classification PPI dataset (%). Asterisked values obtained from the work cited. Non-asterisked values correspond to architectures with the same number of parameters and 2-dimensional embeddings.
paper. Experiments with larger energy GNN architectures, including multi-layer energy GNN architectures, is left to future work.
22

---

Published as a conference paper at ICLR 2025
DATASET
MODEL
Peptides-fune (AP)
Peptides-struct (MAF)
Energy GNN wisge-wise)
0.348
0.367
Energy GNN + attention
0.381
0.402
IGNN (1 layer)
0.211
0,426
GSD GNN
0.343
0.375
GCN (5 layer)
0.362
0.366
GAT (5 layer)
0.355
0.335
Table Performance on Peptides-func (average precision) and Peptides-struct (mean average error) datasets from the LRGB benchmarks. Values correspond to architectures with the same number of parameters and 2-dimensional embeddings.
DATASET
MODEL
MUTAG (%)
PROTEINS (%)
PPI (micro f1)
Peptides- func (AP)
Peptides- struct (MAE)
GCN (5 layer)
16.0 + 10.2
24.0 + 4.9
25.1 + 9.5
0.194 0.085
0.734 + 0.041
GAT (5 layer)
28.0 11.7
40.0 - 5.8
29.4 + 12.3
0.494 = 0.031
0.335 + 0.115
Table Decrease in task performance observed from switching from synchronous to asynchronous inference on sub- sample of test data (10 samples) using one trained model instance. Mean and standard deviation are across 5 asynchronous runs. The poor performance of GCN and GAT are consistent with the expected unreliability of explicitly-defined GNNs with asynchronous inference. Decreases in task performance for all amplicitly-define GNNs (IGNN, GSDGNN, and energy GNN variants) is less than 0.1% of synchronous performance (i.e. result from numerical error); these values are omitted from the table for concision.
23


Reviews:
[{"review_id": "ke2GVxOAeA", "reviewer": "Reviewer_GQeF", "summary": "This paper investigates the performance of Graph Neural Networks (GNNs) in partially asynchronous inference settings, where nodes update in a staggered or asynchronous manner. The authors categorize GNNs into two types: \"explicitly-defined\" and \"implicitly-defined.\" They demonstrate that explicitly-defined GNNs are highly vulnerable to asynchronous updates. In contrast, implicitly-defined GNNs are shown to be robust. Additionally, the authors propose a novel explicitly-defined model, termed Energy GNN, which achieves notable improvements over existing methods on synthetic datasets.", "questions": "- Could you provide a more intuitive explanation of implicitly defined GNNs, specifically highlighting the mechanisms contributing to their robustness under asynchronous updates?\n- Do you have any insight into why the performance on real-world datasets is not as great as on synthetic data?\n- Can you offer an explanation or hypothesis as to why explicitly defined GNNs did not perform as poorly as expected on the PPI dataset under asynchronous conditions?\n\nLine 369. There appears to be a typo in the index notation within the description of targets for the Sums dataset.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- Although I am not deeply familiar with the literature on asynchronous inference in GNNs, the proposed Energy GNN model introduces a novel and meaningful contribution to this field.\n- The paper is of high quality. The authors provide comprehensive mathematical proofs for the convergence of Energy GNNs. They also provide a detailed description of the experimental setup and results, which are well-organized and easy to follow.\n- The paper is generally well-structured, with a clear definition of the problem space and a concise summary of related GNN methods. The paper clearly defines the problem of asynchronous inference in explicitly-defined GNNs.\n- The proposed Energy GNN model demonstrates significant improvements on synthetic datasets, and competitive performance on real-world datasets.", "weaknesses": "The paper lacks a clear and intuitive explanation of implicitly-defined GNNs, which is essential for understanding their robustness to asynchronous updates. While the authors offer detailed explanations for explicitly-defined GNNs, which are more straightforward, they do not provide the same depth of insight into implicitly-defined GNNs. This makes it difficult for readers unfamiliar with the topic to understand how implicitly-defined GNNs work and why they are resilient to asynchronous inference.\n\nAdditionally, although the proposed Energy GNN shows strong results on synthetic datasets, its performance on real-world datasets is rather competitive. On the PPI dataset, in particular, its performance is comparable to that of explicitly-defined GNNs, which were expected to fail under asynchrony. This discrepancy between synthetic and real dataset performance is not explained. A broader evaluation across various real-world datasets would increase the credibility of Energy GNNs as a robust solution.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "988jQJIuyi", "reviewer": "Reviewer_FLMf", "summary": "The paper studies GNNs in the asynchronous “hogwild” setup – when node states are not updated simultaneously at the same time. Such setup is common in distributed environments, agentic systems, and temporal learning where enforcing synchronous node updates might be impossible or too expensive to maintain. Standard, explicitly-defined GNNs trained in the synchronous mode fail in the async mode, so the authors turn their attention to implicitly-defined GNNs (further categorized into fixed-point and optimization-based GNNs). \n\nIt is shown that implicit GNNs are robust to partial asynchronicity. Motivated by the theoretical findings, the authors propose EnergyGNN - an optimization-based implicit GNN where node states minimize a convex energy function. The space of possible energy functions is rather wide and allows for node-wise, edge-wise, and attention-based parameterizations. Experimenting on a range of synthetic tasks, the proposed EnergyGNN outperforms other implicit GNNs in the synchronous regime, is robust to the delayed node update setup, and is on par with synchronous baselines on MUTAG and Proteins datasets.", "questions": "Stemming from the weaknesses:\n\n**Q1 (W1)**. Is there a different way to evaluate the differences among implicit GNNs other than on sync tasks?  \n**Q2 (W1)**. How strong is EnergyGNN compared to more long-range optimized GNNs like Half-Hop, DRew, and graph transformers?  \n**Q3 (W2)**. Does the synthetic EnergyGNN performance correlate with the tasks from more real-world benchmarks like LRGB and TGB?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "**S1**. A theoretical study on the async inference with GNNs is timely and important - many real-world tasks are of that nature, so having a principled, robust approach for such problems (instead of tinkering standard sync GNN architectures) might be of interest to the graph learning community.\n\n**S2**. The paper is well-written - complex concepts are properly introduced and explained (which is often a challenge in the literature on implicit GNNs), the story and motivation are easy to follow.", "weaknesses": "The main problem of the work is in the experiments - it is hard to judge the claimed effectiveness of the proposed EnergyGNN using only synthetic experiments and basic GCN / GAT as baselines.\n\n**W1**. In the proposed suite of tasks, all implicit GNNs are robust in the async setup (the main goal of the work), and the main difference lies in the performance in the sync setup. Is there a different way to evaluate the differences among implicit GNNs other than on sync tasks? EnergyGNN is better than other implicit models but comparing against vanilla GCN and GAT on benchmarks defined to be of a long-range nature (where vanilla GNNs are bound to fail) is questionable. There is a variety of explicitly-defined GNNs that might be stronger baselines in such setups like Half-Hop [1], DRew [2] and other graph rewiring methods, as well as various graph transformers from the dedicated Long-Range Graph Benchmark [3]. \n\n**W2**. The proposed synthetic benchmarks are rather small and might not correlate with the performance on real datasets where async inference is important (or MUTAG and Proteins with sync inference); it seems to be a stretch to attribute chains, node counting, and node sums to “agentic” tasks. Instead, experiments on more real benchmarks might be more informative and evidential: \n* Since some tasks focus on the long-range dependencies, LRGB [3] is a suitable choice;\n* As async inference implies nodes appearing and disappearing at some moments of time, temporal graph benchmarks with many snapshots [4] might be a great choice.\n\nGenerally, I am willing to increase the score if the authors add more modern baselines and/or real-world datasets.\n\n[1] Azabou et al. Half-Hop: A graph upsampling approach for slowing down message passing. ICML 2023.   \n[2] Gutteridge et al. DRew: Dynamically Rewired Message Passing with Delay. ICML 2023.  \n[3] Dwivedi et al. Long Range Graph Benchmark. NeurIPS 2022.   \n[4] Huang et al. Temporal Graph Benchmark for Machine Learning on Temporal Graphs. NeurIPS 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "bfsIYryZTg", "reviewer": "Reviewer_9p4E", "summary": "This paper introduces Graph Neural Networks (GNNs) for distributes multi-agent systems with asynchronous communication. Traditional GNNs struggle with asynchronous execution and unreliable communication. This results in unreliable predictions. To address this, the authors focus on implicitly-defined GNNs, a class of models that can handle partial asynchrony. They introduce a model called energy GNNs, which outperform existing implicitly-defined GNNs on synthetic multi-agent tasks.\n\nThe experimental results highlight potential applications for GNNs in control tasks and real-time inference on dynamic graphs. This is an important property for multi-robot systems. The paper also notes the training limitations for implicitly-defined GNNs, particularly in achieving convergence, as it requires complex and often unpredictable computations. Strategies like warm-start initialization and implicit differentiation could help with these challenges, but challenges remain in achieving stability.", "questions": "Please consider changing the term energy GNN. My first reaction was that this solution was energy-efficient which is a very big concern in AI at the moment. However this work is not about energy efficient AI. \n\nThe experiments are on toy examples that do not need machine learning. Please expand the experimental range to other problems and to larger problem scale. \n\nCan you be clearer about what you summarize from existing work and what are the new contributions in sections 2, 3, 4 \n\nThe description of energy GNN is very sparse, please explain the computation of the neuron and node, architecture, and the method for training in the main manuscript. Please address summarize the properties of this model in Section 5. \n\nCan you say anything about the performance and energy consumption of these models?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "By focusing on implicitly-defined GNNs, the work addresses a major limitation of conventional GNNs in handling asynchronous and unreliable communication, making it highly relevant for real-world multi-agent systems.\n\nExperimental results show that energy GNNs outperform other implicitly-defined GNNs on synthetic tasks, providing empirical validation for the architecture's effectiveness in multi-agent tasks (although most experiments are toy-ish.)", "weaknesses": "The experiments are conducted on toy examples. \n\nFor the experiments other than the \"terrain\" examples there are great solutions that do not require machine learning. The results on the benchmark datasets in the supplementary show small improvements as compared to the more toy examples in the main manuscript.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "qVAefbyQnq", "reviewer": "Reviewer_M6Fj", "summary": "In this paper, the authors tackle the issue of asynchrony in graph neural networks (GNNs). Traditional GNNs, particularly multi-layer variants, assume synchronized node updates, which is often unrealistic in real-world distributed systems like robotic swarms or sensor networks. \n\nThe authors identify a class of GNNs called \"implicitly-defined\" GNNs that are robust to asynchronous or \"hogwild\" inference. They propose a novel implicitly-defined GNN architecture called \"energy GNN\", which leverages input-convex neural networks to parameterize a convex energy function. The results from experiments on synthetic multi-agent tasks and benchmark graph datasets demonstrate the superior performance of energy GNNs under asynchrony and their competitiveness even in synchronous settings.", "questions": "1) How does the choice of the staleness bound B and stagger time S affect the performance and convergence of energy GNNs in practice? Is there a principled way to select these parameters?\n2) The authors mention the potential for numerical instability due to ill-conditioned Hessians or Jacobians. Have they explored techniques like preconditioning to address this issue?\n3) How does the performance of energy GNNs scale with the size of the graph and the number of nodes? Would these be applicable to very large graphs? (I see a comment on this in conclusion section but would be interesting to know the authors intuition about this)", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1) Adoption of GNNs in real-world distributed systems.\n2) Theoretical guarantees for the robustness of implicitly-defined GNNs to asynchrony, drawing on concepts from distributed optimization.\n3) The proposed energy GNN offers a flexible and expressive way to define convex energy functions, potentially leading to more powerful GNN models.\n4) Experiments on both synthetic (chains, counting, sums, coordinates) and benchmark datasets (MUTAG, PROTEINS, PPI) demonstrate the effectiveness of the proposed approach.", "weaknesses": "1) Even though the paper proposes mitigation strategies for trraining implicitly-defined GNNs. They are computationally expensive due to the iterative nature of the forward pass. This would be a challenge in practical scenarios.\n2) The experiments primarily focus on single-layer energy GNNs. The performance of multi-layer variants and their scalability to larger graphs are unclear.\n3) The convergence of implicitly-defined GNNs can be sensitive to the choice of hyperparameters like step size and convergence tolerance. Have the authors investigated the robustness perspective?\n4) While the paper motivates the problem with real-world scenarios(in abstract) the experiments are primarily on synthetic datasets. Unsure how well these would be effective in real world scenarios due to few of the weaknesses pointed above", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Poster)