Graph Neural Networks Gone Hogwild

Thanks for your review of our work. We address your questions below:

1. In our simulations of asynchronous inference, the staleness bound accounts for simulated delay or loss of messages, and stagger time of updates accounts for the level of asynchrony in node updates. These are parameters which are inherent to the distributed system under operation and are not controllable (assuming a fixed hardware setup). These values could be inferred by collecting telemetry from the system of interest. We essentially arbitrarily choose values for these bounds in our asynchronous simulation, without reference to a particular physical system. In theory and in practice, the higher the values of these bounds is, the slower the system will be to converge. However, they do not affect the performance of the system, in the sense that eventually the embeddings will converge to the same values regardless of bounds.

2. We did consider preconditioning; this could help with the linear system in the backward pass, but would be expensive since the preconditioner would need to be recomputed for every backward pass. This is because the Jacobian/Hessian depends on the model parameters and embeddings, which change over time. Furthermore, for optimization-based GNNs, poor conditioning of the Hessian causes difficulty not only in the linear system solve in the backward pass, but also in minimization of E_\theta in the forward pass (this is based on the simple fact that gradient-based optimization is more difficult for functions with poorly conditioned Hessians). Since the forward pass is a convex optimization problem, and cannot be framed as a linear system, preconditioning is unfortunately not applicable. We are also exploring other implicitly-defined GNN architectures in which the condition number of the Hessians/Jacobians could be more tightly controlled.

3. All implicitly-defined GNNs scale more poorly to large graphs than explicitly-defined GNNs due to the fact that the backward pass requires solving a linear system (which scales linearly with the number of nodes), and due to the iterative nature of both the forward and backward pass. That being said, there is nothing preventing implicitly-defined GNNs from being scaled to handle large graphs through distributed training approaches. We don’t implement distributed training in our work since the graphs in the experiments are relatively small compared to benchmark GNN datasets which require distributed training (but they are typical sizes for multi-robot systems - for instance, in the referenced papers where GNNs have been applied to decentralized multi-agent systems, the number of agents range from tens to at most hundreds).

Thanks for taking the time to review our work. We address your questions below:

1. We choose the name energy GNN due to the correspondence to energy-based models, where predictions result from energy minimization (i.e. [LeCun et al 2006]. A Tutorial on Energy-Based Learning).
2. The graphs in our synthetic experiments are relatively small compared to benchmark GNN datasets, but they are typical sizes for multi-robot systems - for instance, in the referenced papers where GNNs have been applied to decentralized multi-agent systems, the number of agents range from tens to at most hundreds. While some of the tasks do not require machine learning, they still have value and serve as a sanity check since it is known that they are solvable in decentralized and asynchronous settings. Regarding expanding to other problems - there are no standard benchmarks for applying GNNs to graphs describing multi-agent systems, which is the motivation behind the work. Standard GNN benchmark datasets do not correspond to the kind of tasks multi-agent systems are expected to perform. We believe the suite of synthetic experiments we propose make sense in the context of our motivation.
3. Section 2 is entirely background material. In section 3, we define implicitly-defined GNNs and contextualize existing architectures that fall under this definition. Section 4 is entirely novel, where we derive GNN updates under partial asynchrony and summarize results on convergence (for which a detailed proof is included in the appendix).
4. We believe we have summarized the main properties of the proposed energy GNN architecture in the final paragraph of section 5. The main details left to the appendix are the architecture of the PICNNs which make up the message function $m()$ and the update function $u()$; these are in the appendix since we simply restate information from the original work on Input Convex Neural Networks. Training details are provided in the experimental setup in section 6, as well as in the appendix.
5. We can qualitatively say that training implicitly-defined GNNs is more time and resource intensive than training explicitly-defined GNNs due to the iterative nature of the forward and backward pass. We aren’t sure what kind of quantitative measures you’re asking for regarding energy consumption, but generally energy consumption is non-trivial to measure and requires, e.g. hardware probes or simulations of execution on particular hardware.

Thanks very much for the review, and particularly for providing some criteria for updating your score.

1. Regarding additional ways to compare implicitly-defined GNNs (besides their synchronous performance): implicitly-defined GNNs could be compared on the basis of how quickly node embeddings converge. However, the speed of convergence depends on where node embeddings are initialized. A fair comparison could be made by evaluating implicitly-defined GNNs in the context of real-time inference on dynamic graphs and observing the number of iterations required for convergence when the graph changes from one state to the next. For instance, for the MNIST terrain task, nodes could be allowed to ‘boot up’ and iterate on their embeddings starting from random node embedding initialization. Following convergence, the graph could be modified by allowing the nodes to take a step on the image “terrain”. The number of iterations required for embeddings to converge following this step would then be a measure of how quickly nodes are able to respond to changes in their observations. We intend to perform this kind of evaluation in future work, where dynamic graphs are considered.
2. (&3) The main motivation of the paper is applying GNNs in multi-agent systems, where decentralized and asynchronous execution is desirable. We don’t perform comparisons against explicitly-defined SOTA GNNs because they cannot run asynchronously, making them unsuitable for the applications we’re interested in. We perform experiments with GCN and GAT for illustrative purposes, using them as representatives of explicitly-defined GNNs to demonstrate that under asynchrony the predictions computed by this class of GNNs are unreliable. Under asynchronous conditions, if reliable and consistent predictions are required (which is the setting that we consider), one is restricted to using implicitly-defined GNNs, so comparison between these models is the focus of our experiments. Due to time constraints, we chose 2 tasks from the LRGB benchmarks that you suggest; Peptides-func and Peptides-struct. Results for these tasks is summarized here:

Table 1. Synchronous performance on Peptides-func and Peptides-struct test data.

Table 2. Decrease in performance on sample of 10 test graphs from Peptides-func and Peptides-struct datasets, mean and standard deviation computed over 5 random asynchronous runs.

We first note that we have shown again that explicitly-defined GNNs drop in performance when executed asynchronously. This again justifies our decision not to run against more SOTA explicitly-defined GNNs, given our interest in asynchronous inference; no matter how good SOTA GNNs perform synchronously, they simply are not suitable in asynchronous settings. We also note that performance is not competitive with reported results from the literature using SOTA explicitly-defined GNNs; this is to be expected, since the models we use are small and have on the order of ~1000 parameters, while SOTA GNNs use on the order of ~500K parameters. Our model is inspired by and designed for distributed, decentralized, and often extremely resource constrained applications (imagine microcontrollers or very small processors on robotic platforms in the field). Standard GNN datasets are not the intended use case for our model (in this work), so we did not perform experiments with large scale models. Unfortunately, scaling the size of our model (and the other implicitly-defined GNNs) for the proposed benchmarks is not feasible given the time constraints for the rebuttal; the time required to train a ~500K parameter explicitly-defined GNN on the suggested datasets is at least 60hr (taken from the paper introducing the LRGB dataset), and implicitly-defined GNNs would certainly be expected to require more time. All that said, we want to flag our shared interests and inclination toward (1) long range dependencies and in particular (2) (temporally) dynamic graphs. We too are excited and motivated by these areas, particularly the latter (the former is actually the motivation behind work introducing the IGNN architecture), and suspect that Energy GNNs could be a good fit. While these delineations are admittedly subjective, we believe consideration of dynamic graphs constitutes a different work in full, and could not be meaningfully or seriously treated as an additional component of our current work (not least in a single 10 page document). But, we do intend to pursue these avenues in the future.

Thank you for your review of our work. We address each of your questions below:

1. Implicitly-defined GNNs fall into two categories: fixed-point GNNs and optimization-based GNNs. Fixed-point GNNs use iterated function application to produce a sequence $x_0, f(x_0), f(f(x_0)), \dots$ whose limit serves as the output of the layer (the node embeddings). This function depends on the data and the graph structure, and is constructed in such a way that the sequence of iterated applications converges (namely, by making $f$ a contraction map). Optimization-based GNNs define node embeddings as the minimizers of a convex function defined over the graph, and use a convex optimization procedure (e.g. gradient descent) to obtain embeddings. Robustness to asynchrony can be provably shown for contractive functions, and for gradient-based optimization of strongly convex functions (with bounded Hessian norms) provided the step size is small enough (we provide a proof in the appendix). You can think of this (roughly) as a statement about stability over coordinate-wise update ordering. For instance, suppose we are tasked with minimizing a function in $\mathbb{R}^2$, but we are only allowed to update one coordinate at a time. In the optimization-based GNN context, think of a graph with two nodes, whose scalar embeddings we want to choose. If the function is convex, its derivatives are bounded, we take small enough steps, and we never update just one coordinate too many times in a row, we can still minimize the function (under many particular sequences of updates). These are the (informal renditions) of the kinds of technical conditions that, if fulfilled by an implicit GNN, guarantees robustness.
2. (&3) There may be a misunderstanding re: the benchmark (real-world) dataset performance. Importantly, in the benchmark dataset results we report, the associated model is not executed asynchronously. So, this is the "normal" operating regime of an explicitly-defined GNN, we wouldn't expect them to fail. Like for the synthetic experiments, if we had performed asynchronous simulations for the benchmark datasets, we would have seen that the explicitly-defined GNNs had unreliable performance while the implicitly-defined GNNs had performance consistent to synchronous execution. What we aimed to signal with those benchmark results is: even run synchronously on standard/typical GNN benchmarks, our model is reasonably competitive. We don't mean to over-emphasize those results, or claim anything like our model being state of the art on typical GNN benchmarks.