Graph Neural Networks Gone Hogwild

Thank you for your detailed read of our work and helpful comments. We have organized our responses below to address what we see as your main concerns, and then answer miscellaneous questions.

Other questions (continued):

• I have trouble understanding the definition of $\tau_i^j(t)$, shouldn’t it be the last updated timestep rather than the amount by which the embedding is outdated (this in my understanding is the quantity $s\_{ij}$)

We agree the wording is confusing. It would be more clear to say given update times $T^j \subset \\{0,1,2,...\\}$ for node j, $\tau\_i^j(t) \in T^j$ is the time corresponding to node i’s view of node j at time t, where $s\_{ij} = t -\tau\_i^j(t) \in$ 0,t $$ is the staleness.

• A5 Appendix; nodes never deviate by more than one, i.e. which means regular updates. Is this correct?

Yes, in our experiments the number of updates a node has executed doesn’t deviate from the other nodes in the graph by more than one. We thought it was a reasonable assumption that nodes update at some regular frequency, as this depends only on local computation at the node. On the other hand, it is reasonable to assume communication with other nodes is less reliable; we thus set the staleness bound on messages relatively high, being at most outdated by 20 updates. An empirical examination of the effect of different levels of staleness and relative frequency of node updates would be interesting, although we can partially predict these effects by observing the relationship between the maximum asynchronous learning rate and staleness bound (as shown in appendix A.4.2). Note that the assumptions of partial asynchronous algorithms state that B is both a bound on the amount (in time) that a node can go without updating, and a bound on the message staleness. Intuitively, convergence will likely be slower as B increases and the maximum learning rate decreases.

• In Section 5, how does the energy function enable robustness? Isn’t this a property of the implicit GNNs and not limited to EGNN?

Yes, it is not a property limited to energy GNN. Energy GNN achieves robustness to asynchrony through optimization of the convex energy function, while implicit GNNs achieve robustness by iterating on a contractive fixed point equation.

• I did not follow the statement “not necessarily convex with respect to the features”, but the node embeddings, but usually the initial node embeddings are the features? I also think it would be good to make explicit where the convexity is required

In our architecture, the node embeddings are defined implicitly as the embeddings which minimize the convex energy function. Only convexity with respect to the node embeddings is required for the energy function. The node features are provided as fixed inputs to the energy function and there is no requirement that the energy is convex with respect to the node features. The solution to the energy minimization does not depend on the initialization of the embeddings (we initialize to zero, or, during training, to the solution from the previous epoch) as the energy is convex (this is the same as for implicit GNNs in general; the same fixed point is reached for the node embeddings regardless of initialization).

• Do you have any intuition on why IGNN is first stable, but then diverges for larger graphs?

We assume you mean why IGNN performance decreases for larger graphs on the chains experiment? Generally it is known that contractive updates make long range communication challenging. One intuition is provided by Li et al. https://arxiv.org/pdf/1511.05493.pdf, who show that repeated contractive updates decrease the dependence of distant node values. The authors of EIGNN argue that they achieve better long range communication than the original IGNN paper by solving for the fixed point directly instead of using iterative solvers.

Final comments: We have additionally uploaded an updated version of the paper with broken reference links fixed and other concerns addressed (e.g. the description of $\tau_i^j(t) \in T^j$).

Other questions (continued):

• What is the limiting factor of scaling to larger graphs? Could you go beyond the size of 100 nodes used in the paper, what are the tradeoffs?

We do go to a size beyond 100 nodes in the benchmark datasets; the average number of nodes in a graph in the PPI dataset is 2373. The tradeoff for larger graph sizes is typically seen in the backward pass; the size of the linear system being solved to obtain parameter gradients using implicit differentiation is proportional to the number of nodes in the graph.

• Are the models trained on the same graph sizes that they are run on during inference? Or do you only train on one and then generalize across sizes for the synthetic tasks?

For the counting experiments, we generate n linear graphs of size $1-n$. We train on 90% of the graphs and test on 10%; test performance is reported on unseen graphs (with unseen number of nodes). For all other synthetic tasks, the number of nodes is constant across the dataset.

• The results provided in the main part of the paper are only on individual modes and not reported as the mean over multiple runs if I understand correctly? I see that it might not be straightforward, as you also need to avg. over the used schedule - but I would appreciate it if the results would be averaged over multiple learned models.

We agree with this feedback, and will run these experiments and report updated values averaged across multiple random seeds for training. Updated results will be up by Friday end of day.

• The required step size is in O(1/nb) (which seems quite small). Could you provide an intuition on why this has to be dependent on n, to me this is not obvious (I would have thought maybe a graph parameter such as the node degree might be necessary?)

The intuition would be that the dimension of the optimization variable (i.e. the node embeddings for the whole graph) in the overall energy function is proportional to the number of nodes.

• I was not quite able to follow the task setup for 6.3. I think a precise formulation of the problem using mathematical notation would help to clarify the task and training objective (can also be included in the Appendix).

The task can be summarized as follows: let $D \in \mathbb{R}^{n \times n}$ be the target distance matrix, where $D\_{i,j}= ||Y^i - Y^j||\_2$ for all $i \in$ 1,...n $, j \in$ 1,...,n $$. Here, $Y^i \in \mathbb{R}^2$ is the true position of the node, which for random graphs we obtain by uniform random sampling in the unit square, and for lattice graphs we obtain by constructing a triangular lattice graph in the unit square. In this task we don’t care about node predictions matching the true positions exactly; instead, we want the nodes to determine their own 2D coordinate system where distances between all nodes in the graph are correct. For random graphs, nodes share an edge if their distance is below 0.5, and for lattice graphs, connectivity is determined by the lattice structure. Node features are one-hot embeddings of node IDs, and edge features are distances to connected neighbors. The loss for each graph in the dataset is $\frac{1}{n^2} \sum\_\{i\=1\}^n \sum\_{j=1}^{n} (||(\hat{Y}\_i - \hat{Y}\_j)||\_2 - D\_{i,j})^2$, where $\hat{Y}_i \in \mathbb{R}^2$ is the predicted position of node i, obtained by executing a GNN. The loss can be stated in words as the mean squared error between the predicted distance between two nodes, and the actual distance.

• In the related work section, I would encourage to include the work on asynchronous GNNs (rather than the focus on distr. training which is not that close to the presented ideas). This includes the work of Faber et al. and Dudzik et al

We were unaware of this work but agree it is relevant. Faber et. al appear to use an RNN-type architecture per node to generate message outputs and iterate the node state, and attempt to train the architecture to be robust to things like message delays by simulating this process during training. They do not fall into the class of GNNs which is provably robust to asynchronous, distributed inference. Dudzik et. al. point out certain classes of GNNs, namely a specific form of pathGNN that use only max aggregation and use specific message functions (for example, a tropical linear transformation) that depend only on sender nodes, can be executed fully asynchronously. The motivation for the paper is to achieve algorithmic alignment between GNNs and existing asynchronous algorithms, rather than examining asynchronous GNN inference in general.

Regarding other strategies to asynchrony:

There are certainly a number of strategies that one could imagine adopting in making a synchronously-operating GNN robust to asynchronous execution. The strategy we explore is architectures which have guaranteed robustness under partial asynchronism by virtue of using either a fixed point iteration or a convex optimization procedure to obtain node embeddings. This offers a massive benefit over strategies like training with asynchrony or using the Scarcelli architecture; under mild assumptions, we get theoretical guarantees that under asynchronous inference the same performance can be achieved as in synchronous inference. As we note in the paper, the node update function proposed by Scarcelli is not a contraction map over the whole domain and thus does not share the same convergence guarantees as energy GNN and IGNN. We thus exclude comparisons to this work, as it falls into the class of GNNs that are not inherently robust to asynchronous inference.

Regarding “simplicity” of existing implicit GNNs:

We do not necessarily claim that existing implicit GNNs are too simple: a more precise statement would be to say they are restrictive and difficult to build on. We identify only two existing implicit GNN architectures, IGNN and EIGNN, which are robust to asynchronous inference. They have a similar node update function and both parameterize the update function to be contractive. Our energy GNN is very different, employing an input-convex GNN, which allows for more flexibility in the the choice of architecture compared to IGNN and EIGNN.

Regarding efficiency and Figure 2:

We do not claim that an energy GNN is more efficient than other GNNs. As the reviewer points out, during asynchronous inference, it can take thousands of node updates for the dataset loss to converge. (The dataset loss for the chains dataset is the mean binary cross entropy loss between node predictions and targets). Note firstly that we used a staleness bound of B=20 in our experiments, which is relatively high. Convergence would be faster with a smaller bound. Second, we show convergence starting from node embeddings initialized to the zeros vector. This initialization is relatively far from the energy minimum, so many iterations are required to converge. During what we might call “blank slate” inference, where the node embeddings are not initialized in any informed way, this could be a problem. However, in many cases a good initial solution may be available. For example, during training we use the solution from the previous epoch. During inference in a continuously operating multi agent system, the solution from the previous time step can be used. Finally, in Figure 2, we run inference well past the point when 100% dataset accuracy is achieved, in order to show that as the GNN continuous asynchronous updates, the loss remains stable and does not change. Good predictions can still be obtained if the process is stopped earlier (e.g. accuracy of 90% corresponds to log loss of approx. -2.2); in fact, an interesting and potentially useful property of energy GNNs and implicit GNNs is that they are an ‘any-time’ algorithm, in which predictions get better with more iterations and a solution can be queried at any point in time.

We also point out that in cases where distributed, asynchronous inference is desired, it may be reasonable to sacrifice efficiency (in terms of number of node updates) since benefits are gained in other places. There is no requirement for central control and coordination of node updates; this removes communication bottlenecks and prevents a single failure point. In the application of asynchronous distributed inference over large graphs, memory requirements are distributed and thus reduced per processor.

Other questions:

• How long do the implicit GNNs and the EGNN run in practice? How deep are the “infinite depth” gnns in practice?
  • The number of iterations required to either achieve a fixed point (IGNN) or energy minimum (energy GNNs) will depend on the embedding initialization, the method of solving for the fixed point or the minimum, and the convergence tolerance. Since the number of iterations required for convergence depends on a number of factors, we simply report values from our experiments for reference. During training, we always use the solution from the previous epoch in order to speed up convergence, and our convergence tolerance is 1e-3. For energy GNNs we use L-BFGS to solve for the minimum, typically requiring no more than 10 iterations per graph. For IGNNs we iterate on the fixed point, which may take upwards of 500 iterations.

Regarding experiments:

While inference over large graphs is one application where asynchronous, distributed inference may be desired, there are a number of other applications on small graphs (i.e. multi-agent setting). In this work we simply point out large graphs as a possible application (this may have been miscommunicated), but do not focus on this application. Instead, our work establishes the conditions under which GNNs become amenable to distributed, asynchronous inference and we propose a novel architecture that meets these conditions. We feel it is sufficient to show that our architecture achieves competitive performance on synthetic and benchmark datasets, as the goal is to add to the class of GNNs which are amenable to asynchronous, distributed inference (in the hope that this class of GNNs may be further explored and used in relevant applications). Certainly, we hope inference over large graphs is an application that will explored in future work.

The goal of our experiments was to 1) explore a number of synthetic tasks inspired by applying GNNs to parameterize communication between agents in a multi agent system such as a robots swarm (e.g. counting of number of agents, summing agent features, performing localization) where distributed, asynchronous inference would be desired and 2) compare performance of our proposed architecture to existing GNNs on a number of standard benchmark datasets to better gauge its expressive power.

For the synthetic tasks we are explicitly interested in performance during asynchronous, distributed inference; for this reason, we only consider one ‘finite-depth’ or synchronous GNN (a 2 layer GCN) because all GNNs of this flavor will exhibit the same malignancies under asynchronous inference. We consider “unreliable-under-asynchrony” GNNs to be a single group and choose one representative, since empirical performance of synchronous architectures under asynchronous execution is not really the focus of the paper. We only compare against one other implicit GNN, IGNN, because to our knowledge this is one of the only existing implicit GNN architectures which has convergence guarantees under asynchronous inference. EIGNN is another instance that we mention (which we note is extremely similar to IGNN), but we found in our experiments that performance of their architecture depends on solving for the fixed point exactly rather than using an iterative method (see appendix 10); the forward pass thus requires global information, which is not easily amenable to distributed inference. Due to global communication requirements of EIGNN’s forward pass and its similarity to IGNN, we exclude comparisons against EIGNN. Another architecture we mention is the implicit GNN architecture proposed by scarcelli; however, as we note in the paper, their node update function is not a contraction map over the whole domain and thus does not share the same convergence guarantees as energy GNN and IGNN.

We understand the confusion about emphasis on long-range communication in the experiments; the multi-agent inspired tasks in the synthetic experiment section all essentially require long-range communication for good performance and thus this is discussed in the results section. Our goal was not to focus on long range communication, rather we point out that energy GNN is able to accomplish this. We see this as an added benefit to energy GNNs (and implicit GNNs in general, as they do not limit the number of rounds of message passing) rather than the main feature.

We would also like to clarify the reported values in Table 4 and 5 in A.10. The asterisked values are obtained from other papers. We stress that for MUTAG and PROTEINS, these values are likely over-estimates of the test performance, since inspection of the code corresponding to these papers shows that test performance is computed by creating 10 train/test splits, and averaging the best test performance achieved during training. For our results (not asterisked) we measure mean test performance across 10 splits after a consistent number of epochs that is not determined by test performance for that split, so the value we report are strictly lower than that in the other papers. We note that we outperform GCN on MUTAG regardless of if we take the value reported in other papers or the result obtained by our implementation. For PROTEINS we outperform GCN when using our evaluation metric and for PPI the accuracy is almost identical. As a final note on the discrepancy between energy GNN performance and asterisked IGNN performance on the benchmark datasets: the IGNN architecture from the original paper had multiple layers. We do not explore multi-layer energy GNNs in this paper, and leave this to future work. It is likely that performance on benchmarks could be improved if multiple optimization layers were used.

Thank you for your time in reviewing our work. We believe there may have been a misunderstanding about the focus of the paper. While inference over large graphs is one application where asynchronous, distributed inference may be desired, there are a number of other applications on small graphs (i.e. multi-agent setting). In this work we point out large graphs as a possible application, but do not focus on this per se. Our synthetic experiments are particularly motivated by tasks that would be relevant to multi-agent systems (e.g. counting of number of agents, summing agent features, performing localization). In these applications, asynchronous and distributed inference is absolutely desirable, as it has the benefits of not requiring central control, which introduces algorithmic and communication overhead as well as a central point of failure for the system.

Furthermore, it is entirely possible that distributed inference might be desirable even if the GNN was trained in a non-distributed manner. Training and inference can have vastly different resource requirements. Models are only trained once and so that can be done in a centralized way if desired, but inference will be done indefinitely and is constrained by whatever device(s) the network will be deployed to. To use a modern example of this discrepancy: although it cost tens of millions of dollars for OpenAI to train ChatGPT, that cost is exceeded by a single week of providing inference as a service with the model. Finally, distributed inference and distributed training are essentially independent problems. For instance, for extremely large graphs we could have trained using an existing distributed training method.

We also point out that while the maximum graph size in our synthetic experiments is 100 nodes, we also run on the PPI dataset, where the average graph contains over 2000 nodes.

Responses to other questions:

• Why some entries of the tables have the std while some others have not?

A standard deviation is always included for running GCN asynchronously, since under asynchronous execution the predictions vary across random runs. We perform 10 random runs to obtain these standard deviations. For IGNN and energy GNN, performance does not depend on the run since these architectures guarantee convergence of embeddings under asynchronous execution, so no standard deviation is provided. For the 10 node counting experiment, the dataset is extremely small and consists of only 10 graphs, so we report average performance across 10 folds of the data. Finally, for the MUTAG and PROTEINS datasets, we report mean accuracy and standard deviation across 10 splits of the dataset. For all other table entries where standard deviation was not included, it is either because we report performance on a single test set from the dataset, or because the architecture gives the same predictions under asynchronous execution.

That being said, we have decided for all experiments to run across 10 folds, as well as with random network parameter initializations. After this, standard deviations will be included in all table entries. We will have updated results uploaded to the paper by end of day Friday.

• The paper is hard to follow and tends to lack clarity. The appendix is confusing and it contains broken pointers (see the number of "??") thus I did not find it useful in understanding the paper better.

Could you expand on what lacked clarity or was hard to follow? We have fixed the broken pointers in the appendix and uploaded an updated version of the paper.

• Also what is the meaning of the "*" in the tables?

The asterisked values are obtained from other papers. We stress that for MUTAG and PROTEINS, these values are likely over-estimates of the test performance, since inspection of the code corresponding to these papers shows that test performance is computed by creating 10 train/test splits, and averaging the best test performance achieved during training. For our results (not asterisked) we measure mean test performance across 10 splits after a consistent number of epochs that is not determined by test performance for that split, so the value we report are strictly lower than that in the other papers. We note that we outperform GCN on MUTAG regardless of if we take the value reported in other papers or the result obtained by our implementation. For PROTEINS we outperform GCN when using our evaluation metric and for PPI the accuracy is almost identical.

We understand that the motivation behind our choice of architectures to compare to in experiments may not have been clear in the paper.

• For the synthetic tasks we are concerned with performance during asynchronous, distributed inference. We only consider one ‘finite-depth’ or synchronous GNN (a 2 layer GCN) because all GNNs of this flavor will exhibit the same malignancies under asynchronous inference. We compare against IGNN, because to our knowledge this is one of the only existing implicit GNN architectures which converges under asynchronous inference. EIGNN is another instance that we mention (which we note is extremely similar to IGNN), but we found in our experiments that performance of their architecture depends on solving for the fixed point exactly rather than using an iterative method (see appendix 10); the forward pass thus requires global information, which is not easily amenable to distributed inference. Due to global communication requirements of EIGNN’s forward pass and its similarity to IGNN, we exclude comparisons against EIGNN. Another architecture we mention is the implicit GNN architecture proposed by Scarcelli; however, as we note in the paper, their node update function is not a contraction map over the whole domain and thus does not share the same convergence guarantees as EGNN and IGNN.
• For the real world experiments we only compare against our implementation of GCN and IGNN; however, we do provide values reported in other papers for other architectures. We asterisk these values in our tables because their evaluation metrics are biased to overstate the typical-case performance. Inspection of the code corresponding to these papers shows that test performance is computed by creating 10 train/test splits, and averaging the best test performance achieved during training. For our results (not asterisked) we measure mean test performance across 10 splits after a consistent number of epochs that is not determined by test performance for that split, so the value we report are strictly lower than that in the other papers. We could have added a more comprehensive comparison, but as our goal was not to show SOTA performance, we believe the context we provide for performance of other methods was sufficient.

Other questions:

• Furthermore, in all experiments we see the proposed energy GNN performs best, but is this always the case and could there be cases where energy GNN fails to perform well?
  • Certainly there are cases where energy GNNs will fail to perform ‘well’, in the sense that other GNN architectures may perform better (this is certainly the case for our real-world dataset experiments; while we achieve competitive performance with existing architectures, we do not achieve SOTA performance). However, most architectures are not robust to asynchronous inference; energy GNNs are. What we attempt to show in our experiments is that energy GNNs both have this property and are reasonably performant.

Thank you for your time taken to review our paper. We address your concerns and questions in this comment and the following one.

We agree that several of the terms we used could have been clearer, and may have lead to confusion. Regarding each of the terms you mention:

• Finite depth GNNs are GNNs that have a fixed number of layers of message passing. Infinite depth GNNs are defined in the background section.
• We use the term “contractive” short for “contraction map” throughout the paper as an attribute of functions (e.g., “update functions” in the abstract, “message passing function” in 2.3, etc.). A function $f$ is a contraction map with respect to its argument, which is to say $\exists \mu \in [0, 1)$ such that $||f(x) - f(y)|| \leq \mu ||x - y||$ for any $x, y$ in the domain of $f$. Informally this means that the distance between any two points decreases after we apply the function. In the context of GNNs, the argument in question is the node embedding (which we denote with $h$ in this work).
• We use the term “energy function” to refer to the objective function associated with the optimization problem. In the first two paragraphs of section 5 we explain the optimization-based view of GNN node updates and proceed to call the objective function being optimized an ‘energy function’
• We do use implicit GNN and fixed point GNN somewhat interchangeably, which is not technically accurate. Implicit GNNs (as a concept) refer to GNNs in which the mapping from data (features) to node embeddings is given implicitly rather than explicitly. Optimization based GNNs and fixed point GNNs are both implicit GNNs in this broad view. In our evaluation section, we are overloading “IGNN” to mean the specific architecture presented in the paper “Implicit GNNs” Gu et al. 2020.

We have made several edits to the main paper to attempt to clarify this terminology.

Regarding the final paragraph of section 4, it may be clarifying to provide an example. Suppose the input graph has dynamic/time-varying node or edge features; for instance, a sensor network where where the node features correspond with sensor measurements (which change over time). Consider the case of using a finite-depth GNN to generate predictions. At some time $t$, a forward pass is executed, in which each node performs a fixed number of rounds $L$ of message passing to generate predictions. If at some time $t’ > t$ the features of the nodes or edges change, the node predictions will now be outdated. To update predictions, another forward pass of the network needs to be coordinated. Coordinating with a global controller is non-trivial, fragile, and adds communication overhead and bottlenecks. Distributed coordination amongst the nodes is similarly non-trivial. The implicit GNN operates continuously, repeatedly updating its embedding, and changes in feature inputs are handled ‘for free’ in the sense that the network does not need to re-start a forward pass. This feature is not necessarily important for GNNs in general, but it certainly is for applications where we want distributed GNN inference and the graph features are dynamic inputs. We do not consider any applications where this is relevant but hope to pursue this in future work.

Responses to questions:

• What's the performance of GCN (async) on real-world datasets?

GCN (and other architectures assuming synchrony across layers) does not provide reliable predictions under asynchronous execution. If reliable predictions are desired, these GNNs are automatically disqualified. When we perform experiments with real-world datasets, we momentarily ignore asynchronous inference, and instead provide an initial evaluation of how expressive/powerful energy GNNs are relative to other GNNs on a level (synchronous) playing field.

• Is $\tau\_i^j(t)$ in Equation 8 a staleness bound? If yes, how to set this term in your evaluation? What's the effect of changing this term?

$\tau\_i^j(t)$ is not a staleness bound, it is the time step corresponding to node i’s view of node j at time t. This time step may correspond to any time in [0, t]; under partial asynchrony, we assume a staleness bound B, where $t - B < \tau_i^j(t) \leq t.$ This information is found in appendix A.1 which discusses partial asynchrony; if there are confusions or there is some information that should be in the main paper, please let us know! We set the staleness bound to 20 in our asynchronous inference experiments; the maximum step size that can be used for energy minimization is inversely proportional to $B$ (see appendix A.4), so convergence will tend to be slower the more staleness is introduced.

• It would be great if the authors can provide a similar histogram in Figure 1(d) for Energy GNN.

Energy GNNs, given enough iterations and small enough step size, always converge to the same value (within some numerical tolerance). The histogram in this case would just be a single peak (again, within some numerical tolerance).

• Some reference links in the supplementary material are broken / The citation format is not consistent. Some first names are abbreviated (e.g., A Bojanczyk) but some are not.

Fixed in new upload, thank you for pointing this out.

Thank you for taking the time to read and comment on our paper. We first address your main concerns then answer the specific questions posed.

Regarding your concerns about providing convergence curves for energy GNN: do you mean at inference time, or at training time? We provide curves demonstrating the convergence of the log dataset loss during asynchronous energy GNN inference for the chains experiment (in Appendix A.7, Figure 2). While we can certainly provide these curves for other experiments, the purpose of Figure 2 is to illustrate empirically that energy GNNs (and IGNNs) are robust to asynchronous inference, supplementing the theoretical guarantees for convergence that we show hold in appendix A.4. If the reviewer instead means that training curves are not provided, we can certainly provide those.

Regarding concerns about providing efficiency and time complexity for energy GNN, we again would like to clarify 1) what is meant by efficiency and 2) if the reviewer means during inference time or during training.

• For time complexity at training time, we have two considerations: the number of iterations required to minimize the energy with respect to the embeddings, and the time required to solve the linear system during implicit differentiation in the backward pass. The time complexity for minimizing the energy depends on the method used to minimize it (we can use any convex optimization procedure). We use iterative solvers for the forward pass (specifically LBFGS) so the actual number of iterations required for convergence depends on where the embeddings are initialized. In practice, we always initialize the embeddings to the energy-minimizing embeddings from the previous epoch of training, which makes convergence fast since small changes in energy parameters (like those from one epoch to the next) typically correspond to small changes in the energy minimizing embeddings. The time complexity for the backward pass also depends on the method used to solve the linear system induced by implicit differentiation, which is a sparse linear system that can be solved efficiently with a method like conjugate gradient. The same approach of initializing the solution to be the solution from the previous epoch makes the backward pass converge faster.
• During asynchronous inference, the time complexity is much more difficult to reason about and is not trivial to derive, requiring an analysis akin to that done in “Hogwild!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent” by Nui et. al. (2011). We do not believe this analysis to be necessary to support the main ideas of the paper.

Regarding concerns about performance on real-world datasets, we first would like to clarify the reported values in Tables 4 and 5 in A.10. The asterisked values are obtained from other papers. We stress that these values are likely over-estimates of the test performance, since inspection of the code corresponding to these papers shows that test performance is computed by creating 10 train/test splits, and averaging the best test performance achieved during training. For our results (not asterisked) we measure mean test performance across 10 splits after a consistent number of epochs that is not determined by test performance for that split, so the value we report are strictly lower than that in the other papers. We note that we outperform GCN on MUTAG regardless of if we take the value reported in other papers or the result obtained by our implementation. For PROTEINS we outperform GCN when using our evaluation metric and for PPI the accuracy is almost identical.

We also emphasize that our goal is not necessarily to outperform other GNNs on either the real world or synthetic experiments. Our overarching goal is instead to provide a novel architecture for an asynchronous-friendly GNN (of which there are very few, IGNNs being the prime example that we compare against) and evaluate its representational power. We do not claim that this is a superior GNN architecture for all use cases, but for situations where asynchronous, distributed inference is required, we believe we have shown that energy GNNs are a competitive architecture. Even compared to GNNs operating in the synchronous regime (in our real-world experiments) we achieve competitive performance.