Beyond GNNs: A Sample Efficient Architecture for Graph Problems
Authors: Pranjal Awasthi
Abhimanyu Das
Sreenivas Gollapudi
Venue:  (2021)
Keywords: Graph Neural Networks
Deep Learning Theory
Graph Connectivity
Minimum Spanning Trees

Abstract: Despite their popularity in learning problems over graph structured data, existing Graph Neural Networks (GNNs) have inherent limitations for fundamental graph problems such as shortest paths, $k$-connectivity, minimum spanning tree and minimum cuts. In all these instances, it is known that one needs GNNs of high depth, scaling at a polynomial rate with the number of nodes $n$, to provably encode the solution space. This in turn affects their statistical efficiency thus requiring a significant amount of training data in order to obtain networks with good performance. In this work we propose a new hybrid architecture to overcome this limitation. Our proposed architecture that we call as GNNplus networks involve a combination of multiple parallel low depth GNNs along with simple pooling layers involving low depth fully connected networks. We provably demonstrate that for many graph problems, the solution space can be encoded by GNNplus networks using depth that scales only poly-logarithmically in the number of nodes. This significantly improves the amount of training data needed that we establish via improved generalization bounds. Finally, we empirically demonstrate the effectiveness of our proposed architecture for a variety of graph problems.


Under review as a conference paper at ICLR 2021
BEYOND GNNS: A SAMPLE-EFHICIENT ARCHITEC- TURE FOR GRAPH PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Despite their popularity in learning problems over graph structured data, exist- ing Graph Neural Networks (GNNs) have inherent limitations for fundamental graph problems such as shortest paths, k-connectivity, minimum spanning tree and minimum cuts. In all these instances, it is known that one needs GNNs of high depth, scaling a polynomial rate with the number of nodes n, to provably encode the solution space. This in turn affects their statistical efficiency thus requiring a significant amount of training data in order to obtain networks with good per- formance. In this work propose new hybrid architecture to overcome this limitation. Our proposed architecture that we call as GNN+ networks involve a combination of multiple parallel low depth GNNs along with simple pooling layers involving low depth fully connected networks. We provably demonstrate that for many graph problems, the solution space can be encoded by GNN+ networks using depth that scales only noly-logarithmicalyy in the number of nodes. This signifi- cantly improves the amount of training data needed that we establish via improved generalization bounds. Finally, we empirically demonstrate the effectiveness of our proposed architecture for a variety of graph problems.
INTRODUCTION
In recent years Graph Neural Networks (GNNs) have become the predominant paradigm for learning problems over graph structured data (Hamilton et al., 2017; Kipf & Welling, 2016; Veličković et al., 2017). Computation in GNNs is performed by each node sending and receiving messages along the edges of the graph, and aggregating messages from its neighbors to update its own embedding vector. After a few rounds of message passing, the computed node embeddings are aggregated to compute the final output (Gilmer et al., 2017). The analogy to message passing leads to simple and elegant architecture for learning functions on graphs. On the other hand, from a theoretical and practical perspective, we also need these architectures to be sample efficient, i.e., learnable from small number of training examples, where each training example corresponds to graph. Recent works have shown that generalization in GNNs depends upon the depth of the architecture, i.e., the number of rounds of message passing, as well as the embedding size for each node the graph (Garg et al., 2020). However, this requirement is in fundamental conflict with the message passing framework. In particular, using GNNs to compute several fundamental graph problems such as shortest paths, minimum spanning tree, min cul etc., necessarily requires the product of the depth of the GNN and the embedding size to scale as /n where n is the size of the graph (Loukas, 2020). This in turn places a significant statistical burden when learning these fundamental problems on large scale graphs. The above raises the the following question: Can one develop sample efficient architectures for graph problems while retaining the simplicity of the message passing framework?
Several recent works have tried to address the above question by proposing extensions to the basic GNN framework by augmenting various pooling operations in conjunction with message passing rounds to capture more global structure (Ying et al., 2018; Simonovsky & Komodakis, 2017; Fey et al., 2018). While these works demonstrate an empirical advantage over GNNs, we currently do not know of a general neural architecture that is versatile enough to provably encode the solution space of variety of graph problems such as shortest paths and minimum spanning trees, while being significantly superior to GNNs in terms of statistical efficiency. In this work propose theoretically principled architecture, called GNN networks for learning graph problems. While the basic GNN framework is inspired from classical message passing style models studied in distributed computing.

---

Under review as a conference paper at ICLR 2021
we borrow from two fundamental paradigms in graph algorithm design namely, sketching and parallel computation, to design GNN networks. As a result of combining these two powerful paradigms, we get new neural architecture that simultaneously achieve low depth and low embedding size for many fundamental graph problems. As a result our proposed GNN architecture have a significantly smaller number of parameters that provably leads better statistical efficiency than GNNs. Before we present our improved architecture, we briefly describe the standard GNN framework.
Model for GNNs. In this work we will study GNNs that fall within the message passing framework and using notation from previous works we denote such networks as GNN (Loukas, 2020). A G network operates in the AGGREGATE and COMBINE model (Gilmer et al., 2017) that captures many popular variants such as GraphSAGE, Graph Convolutional Networks (GCNs) and
GIN networks (Hamilton et al., 2017; Kipf & Welling, 2016; Xu et al., 2019a). Given a graph denote the feature representation of node at layer kt Then we have
G = (V, B), let xe
(k 1) AGGREGATE (k-1) :jE (()))
0j
(1)
COMBINE (1-1) (1-1))..
(2)
Here (i) is the set of neighbors for node i. Typically the aggregation and combination is per- formed via simple one or two layer full connected networks (FNNs), also known as multi layer perceptrons (MLPs). In the rest of the paper we will use the terms interchangeably.
GNN+ Networks. Our proposed GNN+ networks consist of one or more layers of a GNN+ block shown in Figure 1. The GNN+ block comprises of parallel GNN networks follows by parallel fully connected network modules for pooling where r and are the hyperparameters of the architecture. More importantly we restrict the r GNN modules to share the same set of weights. Hence the parallel GNN"P modules only differ in the way the node embeddings are initialized. Furthermore, we restrict each GNN to be of low depth. In particular, for degree-d d graphs of diameter D, over n nodes, we will restrict the GNN to be of depth O(dd + D) polylog(n)). Similarly, we require the s fully connected networks to be of depth O(dd + D) polylog(n)) and share the network weights. We connect the outputs of the GNN modules to the fully connected pooling networks in a sparse manner and restrict the input size of each fully connected network to be O((d + D) polylog(n)). Stacking up L layers of GNN+ blocks results in a GNN+ network that is highly parameter efficient and in total has ((d + DDL - polylog(n)) parameters. For such network we call the depth as the total number of message passing rounds and the number of MLP layers used across all the L stacks. Since we restrict our MLPs and GNN blocks inside a GNN+ network to be of low depth, we will often abuse notation and refer to GNN architecture with L stacks of GNN blocks as a depth L architecture. Our proposed design lets us alternate between local computations involving multiple parallel GNN blocks and global post-processing stages, while still being sample efficient due to the enforced parameter sharing. We will show via several applications that optimal near-optimal solutions to many popular graph problems can indeed be computed via a GNN+ architecture. Below we briefly summarize our main results.
Overview of Results. To demonstrate the general- ity of our proposed GNN+ architecture, we study several fundamental graph problems and show how to construct efficient G networks to compute optimal or near optimal solutions to these problems. In particular, we will focus on degree-d graphs, i.e., graphs of maximum node degree d, with n nodes and diameter D and will construct GNN+ networks of depth polylog(n) and O(D + d'polylog(n:) total parameters.
MLP,
MLP,
GNN,
GNN,
GNN
Figure 1: The basic GNN+ block.
Shortest Paths. The first problem we consider is the fundamental graph problem of computing
(approximate) all pairs shortest paths in undirected graphs. Given graph G = (V, E), let de (u, v) be the shortest path between nodes u and v. We say that an output (do v) u.v V) is an
2

---

Under review as a conference paper at ICLR 2021
a-approximate solution if for all u # v it holds that
da(u, u) S da(u, v) I ada(u,
We construct efficient GNN+ networks for all pairs shortest paths with the following guarantee. Theorem 1 (Informal Theorem). For any constant > L, there is a depth O(D log d log n) GNNT network with (( + ()polylog(nn) parameters that computes (Ac 2))ppproximmte all pairs shortest paths in the undirected unweighted degree-d graphs over n. nodes. On the other hand, computing c-approximate shortest paths using GNN networks requires network of depth 12(n).
From the above theorem we that by setting using O log d + log n) GNN+ network with only O(d polylog(n)) parameters. This is in stark contrast with the depth requirement of ((n)) for the traditional GNN"PP "P networks.
Ollog n.)
encode c-approximate solution
Connectivity Mcasures. Next we consider computing various graph connectivity measures. We first study the popular measure based graph effective resistances (Chandra et al., 1996).
Definition 1 (Effective Resistance). Let G be weighted undirected graph G with adjacency matrix A and the associated Laplacian L D -A. Given an edge u, U, the effective resistance between u, is defined as
Ru, - Lu,e
Here Eu.v is an n dimensional vector with +1 at position u, -1 at position u and zeros everywhere. L refers to the matrix pseudo-inverse,
We also study the following connectivity measure that was proposed by Panigrahy et al. (2012) in the context of web graphs. Given undirected graph G, let Gp be the random graph obtained by sampling each edge with probability p.
Definition 2 (Affinity). For any two vertices u, v and for p E [0, 1]. probability that u. are connected in Gp. Then the affinity between u and u is defined as
define Ap v) to be the
A(u, v) = EplAA(u,
where the expectation taken over p drawn from the uniform distribution in [0, 1].
For the above measures show the following
Theorem 2 (Informal Theorem). There exists GNN architecture with O log(nd)) parameters, and depth O log(nd) on graphs of diameter D with n nodes and maximum degree d, that approximate the above connectivity measures up constant factors. On the other hand using GNN"P networks to compute the above measures, even approximately, necessarily requires a network of depth Q2 (n))).
Clustering, Minimum Cuts and Minimum Spanning Trees. Finally, showcase the power of a GNN+ architecture for computing other fundamental graph problems. Given an undirected graph G. the spectral clustering of G corresponds to the cut obtained by taking the sign of the eigenvector v corresponding to the second smallest cigenvalue (L). where L is the graph Laplacian. For computing the spectral clustering via GNN+ networks we show the following
Theorem (Informal Theorem). There is a GNN network of depth = 0( ماا logn), with O(d) parameters that computes e-approximate spectral clustering graphs of degree d. On the other hand, using GN networks to even approximately compute the spectral clustering requires depth ())n)..
Next we consider the classical problems of computing global minimum cut and minimum spanning trees undirected graphs.
Theorem (Informal Theorem). There exist GNN networks of of depth O( + log n) log n). and (d) parameters for computing a global minimum cut (MINCUT) and minimum spanning tree (MST) in degree d graphs of diameter D. Furthermore, using GNN"P networks to compute these primitives (even approximately) necessarily requires depth (2
3

---

Under review as a conference paper at ICLR 2021
Generalization Bounds. Our final result concerns the generalization properties of depth L GNN architecture. For ease of exposition, we state here the results for the case when the GNN architecture produces one dimensional output. More general results are presented in Appendix D. Our generalization bounds depend on the depth 1. and the total number of parameters in the GNN network. Following recent work providing generalization bounds for fully connected and convolutional neural networks (Bartlett et al., 2017; Long & Sedghi, 2020) that are based on distance initialization, we consider the class F3 of depth L GNN networks with / parameters that are at distance 3 from a reference parameter configuration (typically the parameters at random initialization). Let y E denote the output of the network and consider a Lipschitz loss function C(y, 5). Then, we provide following guarantee.
Theorem 5 (Informal Theorem). Let E(g. v) be Lipschitz loss function bounded in 10, B). Then, given m i.d. samples (G1, y1), (G2. y2).... (Gm, Dm) generated from a distribution D, with proba- bility at least 2/3, it holds that for all f E FB.
DEllsl---ol -
S so BV
P(3 + L)
We refer the reader to Theorem 16 in Appendix D for a formal statement and the proof. Notice that the above theorem implies that our proposed GNN architecture for the above graph problems can indeed be trained using very few samples as opposed to the traditional GNN networks since the GNN+ network requires much fewer parameters and depth. Furthermore, since GNN network is special case of a GNN+ architecture, our analysis also leads to an improved bound on the generalization guarantees for GNN networks as well. In particular, the above theorem improves upon the recent work of Garg et al. (2020) that provides generalization guarantees for training GNNs that scale with the branching factor of the graph. Using our improved analysis we are able to remove this dependence the branching factor. See Appendix D for details.
RELATED WORK
GNNs operate primarily in the message passing framework where nodes aggregate and combine messages from their neighbors to update their embeddings. Several variants of this basic paradigm have been proposed, with each differing in how the aggregation and combination is performed. Popular variants include GraphSAGE (Hamilton et al., 2017), Graph Convolutions Networks (Kipf & Welling, 2016), GIN networks (Xu et al., 2019a), and graph pooling (Ying et al., 2018).
Various recent works have also studied the representation power of GNNs. The work of Xu et al. (2019a) demonstrates that the GNNs as considered in equation are as powerful as the Weisfeiler- Lehman test for graph isomorphism (Weisfeiler & Lehman, 1968). The recent work of Xu et al. (2019b) compares the message passing framework of GNNs in representing computations involving dynamic programming. GNN networks that can capture higher order variants of the WL test have also been proposed recently (Maron et al., 2019).
Several works have also explored the limitations of GNNs for computing graph primitives. The work of Loukas (2020) established a correspondence between the message passing GNN framework and the well studied CONGEST model of distributed computing (Peleg, 2000). Based on the above correspondence it follows that in order to represent several important graph problems such as shortest paths, minimum cuts and minimum spanning tree, either the depth of the GNN or the embedding size of the nodes has to scale with the graph size at a polynomial rate. Notice that these lower bounds apply to any form of message passing framework and as a result recent work in incorporating non-symmetric node messages (Sato et al., 2019) in GNNs also run into the same barriers.
In order to address the above limitations recent works have proposed combining the GNN architecture with pooling mechanisms for aggregating more global information (Ying et al., 2018; Defferrard et al., 2016; Simonovsky & Komodakis, 2017: Fey et al., 2018; Bianchi et al., 2019; Du et al., 2019). For example the work of Ying et al. (2018) proposes a hierarchical approach where a GNN network is followed by a clustering step to compute higher level "nodes" to be used in the subsequent GNN operation. While these approaches show empirical promise, ours is the first work to design principled architecture with theoretical guarantees that merges local distributed computations with global postprocessing stages.
4

---

Under review as a conference paper at ICLR 2021
Finally, the question of generalization for GNNs has also been studied in recent works. The most relevant to us is the recent work of Garg et al. (2020) that analyzes the Rademacher complexity of GNNs with the aggregate mechanism being simple addition and the combine mechanism being a one layer neural network. Via analyzing the Rademacher complexity the authors show that the generalization for GNNs depends on the depth, the embedding size and the branching factor of the graph. Our improved analysis in Section D extends the result of Garg et al. (2020). Not only does our generalization bound apply to the more general GNN networks, for the case of GNNs considered in (Garg et al., 2020) our analysis shows that the dependence on the branching factor can be eliminated in the generalization bounds. Generalization bounds have also been proved recently for GNN based networks that use the Neural Tangent Kernel (NTK) during the aggregation and combination operations (Du et al., 2019).
3 SHORTEST PATHS
In this section we provide proof sketch of Theorem showing how to construct efficient GNN architecture for the Shortest Paths problem. In particular we study all pairs shortest paths.
All Pairs Shortest Paths. The input is a graph G (V, E) with nodes. The desired output is an dimensional vector containing (approximate) shortest path values between each pair of vertices. Given a graph G, let da(u, u) be the shortest path between nodes u and v. We say that an output {do (u, v): u E V} is an a-approximate solution if for all u # v it holds that
da(u, v) S de(u,,) v) S odg(u, v).
We first show that the GNN networks are highly inefficient for learning this problem.
Theorem 6. Consider a GNN" N of depth L over n nodes where each node has a representation size of B. N encodes a-approximate all pairs shortest paths for graphs of diameter bounded by D, and for a < 3/2, then it must hold that B L 2 (1n)). Furthermore, for any GNN that encodes a(n) approximate all pairs shortest paths it must hold that B L 2 Q (2 ((aan)oog)) holds for undirected unweighted graphs as well.
The lower bound
Proof. The recent work of Loukas (2020) established that computation in GNNmp networks is equivalent to the CONGEST model of computation popularly studied in the design of distributed algorithms (Peleg, 2000). In particular, lower bound on the product of depth (I.) and representation size (B) can be obtained by establishing the corresponding lower bound the product of the number of rounds and the size of messages in the CONGEST model of computing. Furthermore, the result of Holzer& & Wattenhofer (2012) shows that in the CONGEST model approximating all pairs shortest paths, even on unweighted undirected graphs requires the product of the number of rounds and the message size to be (n.). This was improved in the work of Nanongkai (2014) to show that for any (()) approxxxxxinn,,nn,, the product of the number of rounds and the message size to be ? (x log Hence the corresponding lower bound on B follows.
Circumventing Lower Bounds via GNN+ Next we detail our proposed GNN+ architecture that can encode approximate shortest paths with significantly smaller depth and parameter requirements.
Unweighted Graphs. To illustrate the main ideas we study the case of undirected unweighted graphs. See Appendix A for the more general case of weighted graphs. The starting point of our construction is the following fundamental theorem of Bourgain (1985) regarding metric embeddings.
Theorem 7 (Bourgain, 1985)). Any n-point metric (X, d) can be embedded into the Euclidean metric of dimensionality Olog n) and distortion O n).
The above theorem suggests that in principle, if we only want to estimate shortest paths up to an approximation of Ollog n),, then we only need node embeddings of size O(log n). If there were "N network that could produce such embeddings, then one could simply compute the Euclidean distance between each pair of points to get the approximate shortest path. Furthermore, computing the Euclidean distance given the node embeddings can be done easily via a low depth full connected network. Unfortunately, producing the necessary low dimensional embeddings is exactly the task for
5

---

Under review as a conference paper at ICLR 2021
which GN networks require large depth proved in Theorem 6 above. While there do exist semi- definite programminng based algorithms (Linial et al., 1995) for computing the embeddings required for Bourgain's 's theorem, they are not suitable for implementation via efficient neural architectures. Instead we rely on sketching based algorithms for computing shortest path distances.
In particular, for the unweighted case we adapt the sketch based approximate shortest path algorithms of Das Sarma et al. (2010) for designing an efficient network architecture. The sketch proposed in the work of Das Sarma et al. (2010) computes, for each node u. the distance of u. from random subset S of the nodes. This can be done via simple breadth first search (BFS). Repeating this process k-times provides a #-dimensional embedding for each vertex and for an appropriate choice of k, these embeddings can be used to compute approximate shortest paths. Notice that this sketch based procedure is highly amenable to be implemented in a message passing framework. Overall, the algorithm performs multiple parallel BFS subroutines to compute the embeddings. It is also well known that BFS on diameter D can be implemented by a GNN of depth O(D).
Based on the above intuition, our proposed architecture is shown in Figure 2. It consists of k parallel breadth first search (BFS) modules for l (n log n) for constant e >> 1. Module computes the shortest path from each vertex in G to any vertex in the set S.. The sets S1, S.....,. ..... Sy are randomly chosen subsets of the vertex set V of various sizes. In particular there are ( subsets of size 1, O(n-) subsets of size 2, (n=)) subsets of size 2², and so on up to ((n)) subsets of size 2 [log nJ. The BFS module produces n distance values u(4)
( These modules are followed by (*)
fully connected networks where each module is responsible for computing the approximate shortest (2)
path distance between pair of vertices. In particular we have da(ss t) max; |o!") Ug
Notice from the discussion in Sec- tion 1 that the architecture in Fig- ure 2 is a GNN network with sin- gle GNN block. In the next section we will show how we can generalize to suite of graph problems by stack- ing up multiple GNN+ blocks. For our proposed network we have the fol- lowing guarantee.
dgOn (n 1,n)
dc(1.2)
MLP(1.2)
MLP(n P(n - 1,m)
n- Vi
2/
11-2 1/
BFS(S, D)
BFS(S,. D)
BFS(S,.D)
Theorem 8. For any integer and for a fixed graph topology over nodes with maximum degree d and diameter D, there exists a neural net- work as shown in Figure 2 of size 2 parameters, and depth O(D log d + logn), that en- codes (2c 1) -ppprooxiee all pairs
1,
Figure 2: The network architecture for approximate all pairs shortest paths in unweighted graphs.
O(n ((22+1/o) Önn))
shortest puths in G.
Before proving the theorem above we establish two supporting lemmas concerning the implementation of the BFS modules and the MIP module in the network architecture described in Figure 2.
The BFS module in Figure 2 can be implemented by a GNN of depth O(D), O(1) total parameters and with each node having a representation size of O(1).
Lemma 1.
Lemma 2. For any k, the MLP module in Figure 2 can be implemented by a network of depth Ollog k), (I22) total parameters.
Proof of Theorem 8. The correctness of the network architecture follows from the work of Das Sarma al. (2010). Next we establish bounds on the total depth, size and the number of parameters. We have k (n log n) copies of the BFS module. Each BFS module of size Ond log d) since there are n nodes and each node implements min function of size Odd d). Hence, in total the BFS modules have size O( D(n1+1/edlo log d'logn) Next we have (7) MLP modules each of size
Ok log k) for total size of 21n2+1/cloo log n). Hence the total size of the neural network is bounded by O logn).

---

Under review as a conference paper at ICLR 2021
Next we bound the depth and the total number of parameters. The BFS module has O(D) rounds with each requiring a depth of Ollog d) for a total depth of Oog d). The MLP module has a depth bounded by (log k) (log n). Hence the total depth is O(D log D + log Finally, the BFS module requires (1)) parameters and the MLP module requires ( parameters. Hence, the total number of parameters in our architecture are bounded by O = (n2//))
MINIMUM CUTS
To illustrate another application, in this section we design an efficient GNN based architecture for computing the minimum cut in an undirected graph. We first argue in Appendix that even computing an approximate mincut using traditional GNN networks requires 52 (V)n) rounds. Our efficient GNN based architecture is based on the parallel algorithm for computing mincut (Karger & Stein, 1996) and is shown in Figure 3. More importantly the architecture comprises of mul- tiple layers of GNN+ blocks in contrast to single GNN block in the case of shortest paths. The algorithm of Karger & Stein (1996) relies on the following
lemma.
Lemma 3 (Karger & Stein, 1996)). Let G = (V, E) be undi- rected unweighted graph with m edges and n vertices. Then with probability least T., a random ordering L of the edges contains a prefix L' of L such that the graph G¹ = (V, I') contains exactly two connected components corresponding to the global minimum cut in the graph.
Update Prefix
GNN
Update Prefix
Using the above, Karger& & Stein (1996) proposed a Monte-Carlo randomized algorithm to compute the global minimum cut. For a given ordering L, the algorithm estimates the length of the prefix L' corresponding to the cut by using a binary search procedure. This provides the set of active edges, i.e., edges in L'. Then one run a connected components algorithm using edges in L'. If the prefix is too small. it results in more than two connected components; if it is too large it produces one connected component. If the number of connected components is two then the algorithm stops. Otherwise it recurses on the appropriate side of L'.
GNN
Figure 3: The network archi- tecture for minimum cut.
We can implement the above algorithm using the GNN+ architecture of depth Olog m) where the computation in each pair of (GNN.Update Prefix) blocks corresponds executing one call of the above binary search procedure. During each call one needs to perform a connected component subroutine. This can be done via BFS and is implemented in the GNN block as shown in Figure 3. The GNN is followed by the UpdatePrefix module that an MI.P implementing the logic of selecting the appropriate side of the permutation to recurse on.
More formally, at each of the O(log m) O(log n) stages, each vertex the GNN maintains a list of which of its connecting edges are active. This requires ((d) representation size. The goal next is to infer whether the number connected components induced by the active edges is one, two, or more than two. This in turn decides the part of the ordering the next stage will focus on. The computation of connected components can be carried out using at most two breadth first searches and hence via O(D) rounds of a GNN"P network. Following this intuition we arrive at the proposed architecture in Figure 3. Formally, we have the following guarantee.
Theorem 9. For a fixed graph topology over n nodes with maximumm degree d and diameter D, the network in Figure 3 produces the minimum cut. Furthermore, the network is of depth E = O n), size (nE),, and has Old + log n) parameters.
Proof. Each vertex maintains an Odd) sized representation indicating which of its edges are currently active plus additional constant number of values to indicate its component id during different runs of BFS. Given list of active edges, the GNN module simply performs procedure compute whether the number of connected components is one, two, or more than two. This can be done with at most two BFS runs over the active edges. As we saw before in Section 3, this requires O(D) depth.
7

---

Under review as a conference paper at ICLR 2021
At the end of the GNN module each vertex gets an integer value specifying its component id. The UpdatePrefix module then takes this information and is required to perform two computations: a) check if the number of connected components is one, two, or more than two. This requires checking the number of distinct elements in a list of n numbers and can be done with an MLP O(log n) parameters and depth O(log n.). b) update the set of active edges for each vertex depending on the number of connected components. This requires taking in the ((d) sized representation and producing a new ((d) sized representation for each vertex. This can be achieved again by an MLP using (dd) parameters and depth (log d). Once given round of GNN and UpdatePrefix ends, the computations proceeds to the next layer. Importantly, the set of model parameters are shared across the different layers of the architecture as each time the computation required is the same. Hence overall we get O(D log r)) depth and Old - logg n) parameters.
5 EXPERIMENTS
We show the efficacy of GNN+ the aforementioned graph problems: Shortest Paths, Effective Resistance, Affinity, MINCUT and MST, and compare to state-of offte-of-the-art GNN"P model (Xu et al., 2019a).
Dataset. We generated synthetic random graphs between 500 and 1000 nodes. For the affinity measure, we used graphs with 250 nodes because of the need for using very dense graphs to have a reasonable number of alternate paths between any two end points. In general, sets as follows: we fix the number of nodes n in the graph to take values in [250, 1000). For each value of n generate graphs from the Erdos-Reny' model G(n, p) with edge sampling probability p e. We vary a depending on the problem. Specifically, we set o to be a constant in [1, 100) to capture varying degrees of sparsity. For each n. p we generate 30, 000 training examples consisting of tuples of the form (G, s, f, d(s, t)) where G is random graph drawn from G(n, p), s, t are two vertices uniformly drawn at random and d(s t) one of shortest path value, effective resistance, or affinity between the two vertices. In the case of min cut and minimum spanning tree, we generate tuples (g. va) where lg corresponds to the value of the minimum spanning tree or the global minimum cut.
generated the data
Models and Configurations. For our baseline GN implementation, we used the GIN model proposed in Xu et al. (2019a). This has been empirically shown (Xu et al., 2019a; Loukas, 2020; Errica et al., 2020) to be state-of-the-art GNN model on several datasets. GIN updates feature represen-
[k- tations (k) of each node at iteration A: as: zb MLP (1 (+))- =x +EuEN()) Zu
where MLP refers to a Multi-Layer Perceptron, (wv) is the set of neighbors of v, and is learnable parameter. For problems that involved weighted graphs (e.g. MST), we incorporated edge weights into the GIN update equation by replacing the sum of neighbor representations by weighted sum.
Our GNN+ implementation also used the same GIN implementation as its internal GNN"p block. All graphs in our experiments were undirected. For both baseline and GNN we used node degree as the input node features for MINCUT and MST. For Shortest Paths, Effective Resistance and Affinity, set input node features to be Boolcans indicating if the node is source/destination node or not.
Following Xu et al. (2019a), we performed 10-fold cross-validation for each of our experiments (corresponding the two models and five problems), and report the average validation mean squared error(MSE) across the 10 folds. We run each 10-fold crass-vali experiment 10 times to compute confidence intervals. We apply batch normalization at each layer, and an Adam optimizer and decay the learning rate by 0.5 every 50 epochs, and train for up to 600 epochs. For both the baseline GNN"P and the GNN model, we tune the following parameters: initial learning rate {0.001, 0,003, 0.005, 0.007, 0.01, 0.03, 0.05). number of hidden units E {8, 16, 32, 64). batch- size E {32, 64), dropout e {0, 0.5). For GNN"P we also tuned the depth (number of layers)
{2, 4, 8, 12). For the GNN+ model, we tuned the number of parallel GNNs in each GNN+ block to E {1, 3 with GNN depth (2, 4). We also tuned the number of GNN+ layers {1, 2,3. We fixed the depth of each MLP block in GN and GNN+ to 2.
Results. To validate our theory regarding the better generalization bounds for GNN+ models compared to GN we compare the test mean squared errors for the two models across the five datasets. For all the five problem, Table 1 lists the test MSEs and corresponding standard deviations
8

---

Under review as a conference paper at ICLR 2021
Problem
Label Variance
Avg. MSE (GNN
Avg. MSE (GNN*)
Shortest Path
7,482
0.975 0.031
0.849 + 0.022
Effective Resistance
7.949
0.397 0.025
0.187 = 0.008
Affinity
3.030
0.0025 = 1.75e-04 04
0.0018 + 1.89c-0900000 05
MST
4637.4
1011.39 + 106.94
733.901 + 30.97
MINCUT 11.964
0.963 + 0.110
0.694 + 0.07
Table I: Performance of the GNN GNN architectures
for the two models, As sanity check, we also plot the variance of the labels in our datasets, which corresponds the MSE obtained by a naive model that predicts the mean label. We observe significant gains in accuracy of anywhere between 15% relative MSE improvement over the GNN baseline (for Shortest Paths) to much as 108% relative MSE improvement (for Effective Resistance). Note that the naive mean predictor's 's MSE is at least an order of magnitude larger than all the MSE values for GNN and GNN+ (except for the MSTdataset, where it is around five times larger- - we suspect that the weighted graphs involved in this dataset make this a harder problem).
We posit that these accuracy gains directly stem from the sample-efficinnyy of the GNN+ models as captured in Theorems 1,2 and 4 the most compact GNN networks that can represent these problems are smaller than the corresponding most compact GNN networks. Hence, by Theorem such networks will have smaller generalization errors. In the appendix, we also plot the test accuracy as a function of number of epochs that suggest that our models also converge faster than the baseline GNN models, though do not have any theoretical justification supporting this observation.
Experiments on Real World Data. We further demonstrate the applicability of our proposed GNN+ architecture for solving classification tasks involving real world graphs. We experiment with the following real world datasets (Yanardag & Vishwanathan, 2015) that have been used in recent works for evaluating various GNN architectures (Xu et al., 2019a): IMDB-BINARY and 2) IMDB-MULTI datasets: These are movie collaboration datasets with nodes as actors and the class label being the genre. 3) COLLAB: This is scientific collaboration dataset with three classes. 4) PROTEINS: This is a bioinformatics dataset with 3 class labels. 5) PTC, 6) NCI and 7) MUTAG: These are various datasets of chemical compounds with two class labels each.
We train our GNN+ proposed architecture on these graphs using the cross-entropy loss and as before compare with the GIN architecture of Xu al. (2019a). We use the same input node features as in Xu et al. (2019a) and use the same experimental methodology as that for synthetic graphs above. In particular, when tuning hyperparameter tuning we allow the GNN architecture to explore depth upto 9 whereas the GNN architecture is tuned by restricting the depth upto 3. The results summarized in Table below, As can be seen, in each instance GNN+ either outperforms or matches the performance of the GNN architecture in terms of final test accuracy.
Dataset
Test Acc. (GNNDM)
Test Acc. (GNN+)
IMDB-BINARY
0.742 = 0.09
0.769 0.02
MULIT
0.523 = 0.06
0.527 + 0.04
COLLAB
0.802 = 0.02
0,816 = 0.004
PROTEINS
0.7602 + 0.008
0.7654 + 0.015
NCI1
0.849 + 0.004
0.851 + 0.003
PTC
0.686 + 0.02
0.708 + 0.018
MUTAG
0.876 = 0.016
0.898 + 0.012
Table 2: Performance of the GNd GNN* architectures real world classification datasets.
REFERENCES
Raman Arora, Amitabh Basu, Poorya Mianjy, and Anirbit Mukherjee. Understanding deep neural networks with rectified linear units. arXiv preprint 161 2016.

---

Under review as a conference paper at ICLR 2021
László Babai, Peter Frankl, and Janos Simon. Complexity classes in communication complexity theory. In 27th Annual Symposium on Foundations of Computer Science (sfes 1986), pp. 337-347. IEEE, 1986.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky, Spectrally-normal normalized margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 0240-6249, 2017.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Mincut pooling in graph neural networks. arXiv preprint arXiv: /900:00077004.100000
Jean Bourgain. On lipschitz embedding of finite metric spaces in hilbert space. Israel Journal of Mathematics, 52(1-2):46-52 -2, 1985.
Ashok Chandra, Prabhakar Raghavan, Walter Ruzzo, Roman Smolensky, and Prasoon Tiwari. The electrical resistance of graph captures its commute and cover times. Computational Complexity, (1-))312-340, 1996.
Atish Das Sarma, Sreenivas Gollapudi, Mare Najork, and Rina Panigrahy. A sketch-based distance oracle for web-scale graphs. In Proceedings of the third ACM international conference Web search and data mining. pp. 401-410, 2010.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3854-3852, 2016.
Simon Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. In Advances in Neural Information Processing Systems, pp. 5723-5733, 2019.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. /CLR, 2020.
Matthias Fey, Jan Eric Lenssen, Frank Weichert, and Heinrich Müller. Splineenn: Fast geometric deep learning with continuous b-spline kernels. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 869-877, 2018.
Sebastian Forster and Danupon Nanongkai. A faster distributed single-source shortest paths algorithm. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 686-697. IEEE, 2018.
Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. ICMI., 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv:1704.01212, 2017.
Evarist Giné and Armelle Guillou. On consistency of kernel density estimators for randomly censored data: rates holding uniformly over adaptive intervals. In Annales de I'IHP Probabilités et statistiques, volume 37, pp. 503-522, 2001.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Stephan Holzer and Roger Wattenhofer. Optimal distributed all pairs shortest paths and applications. In Proceedings of the 2012 ACM symposium on Principles of distributed computing, pp. 355-364, 2012.
David R. Karger and Clifford Stein. new approach to the minimum cut problem. Journal of the ACM, 43:601-640, 1996.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. 2016.
arXiv preprint 1609.
Nathan Linial, Eran London, and Yuri Rabinovich. The geometry of graphs and some of its algorithmic applications. Combinatorica, 1552):2 1995.
10

---

Under review as a conference paper at ICLR 2021
Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks, 2020.
Andreas Loukas. What graph neural networks cannot lear: depth vs width. ICLR, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances Neural Information Processing Systems, pp. 2156-2167 2019.
Danupon Nanongkai. Distributed approximation algorithms weighted shortest paths. In Proceed- ings of the forty-sixth anmual ACM symposium Theory of computing, pp. 565-573, 2014.
Rina Panigrahy, Mare Najork, and Yinglian Xie. How user behavior is related to social affinity. In Proceedings of the fifth ACM international conference on Web search and data mining, pp. 713-722, 2012.
David Peleg. Distributed computing: a locality-sensitive approach. SIAM, 2000.
Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Panduran- gan, David Peleg. and Roger Wattenhofer. Distributed verification and hardness of distributed approximation. SIAM Journal on Computing,
2012.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp. 4081- 4090, 2019.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neural networks on graphs. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 3693-3702, 2017.
M Sollin. La trace de canalisation. Programming, Games, and Transportation Networks, 1965.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903,, 2017.
Boris Weisfeiler and Andrei A Lehman. A reduction of a graph to canonical form and an algebra arising during this reduction. Seuccno--Techicchssiee Informatsia, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019a.
Keyulu Xu, Jingling Li. Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What can neural networks reason about? arXiv preprint arXiv: 1905. 13211, 2019b.
Pinar Yanardag and S. V. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD '15, pp. 1374, 2015.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances neural information processing systems, pp. 4800-4810, 2018.


Reviews:
[{"review_id": "eS7r8YsuVhN", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new building block for GNNs, called GNN$^+$. This building block trades of depth for width and involves multiple parallel regular GNN processing units. Using the GNN$^+$ architecture, the authors establish bounds for the required network depth (and total parameters) for several combinatorial problems over graphs.\n\nPros:\n+ A parallel processing architecture, as opposed to sequential processing, is also likely to be computationally more efficient in large memory setups.\n\n+ I haven't carefully checked all the proofs, but the key theorems seem relevant and interesting.\n\n+ The paper is clearly written for most parts and the key intuitions behind the theoretical results are explained in sufficient depth.\n\n\nCons:\n- The parallel GNN$^{mp}$ and MLP modules within a GNN$^+$ block all share parameters and hence, the only source of difference in the computed function is due to differences in initialization of node features. How is that difference executed in practice, both in the problems considered in this work and more generally for any graph problem? From the description in the experiments section, it seems that the networks are implemented using same set of features for the nodes during initialization (eg, node degrees, booleans for source and/or destination nodes).\n\n- The paper lacks evidence if this model outperforms GNNs on real-world graph datasets. All the problems considered in this work are combinatorial optimization problems on Erdos-Renyi graphs, for which non-learning based solutions also exist. While many of the theoretical results are also custom to these problems, one would hope that the architecture is also evaluated on standard tasks (eg, classification) for real-world benchmark graph datasets.\n\n- The central premise of the paper seems to be that the GNN$^+$ models require less depth (and total parameters) compared to standard GNN architectures. This is not clear from the experiments. A more descriptive result would be to assess the performance of these models as a function of depth (and total parameters).\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "IPnXRSLQkbN", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a variation of GNN which they name GNN+, which runs several GNN modules in parallel (with weight sharing). The authors show that it works well in practice on several synthetic datasets, and show many theoretical results. \nI have some issue with the theoretical results and would raise the score if addressed.\n\n- Unless I am mistaken the  GNN+ architecture requires different features inputs for all copies of the GNN, this should be added into the parameter counting that is done.\n- When the parameters are the same across layers they are counted as one, while this is true if you enforce weight sharing but in general we train without this constraint. Furthermore this isn't done for GNNs which leads to an unfair comparison. The method should be the same, preferably without discounting weight sharing.\n- Maybe I am missing something basic but the node affinity definition doesn't make any sense to me. A_p(u,v) should be just p times the indicator of (u,v)\\in E so shouldn't be more informative then just the basic adjacency matrix.\n- It doesn't seem like there is any theoretical gain when comparing theorem 6 and 8. Considering that in theorem 6 alpha<3/2 and the number of parameters is O(B^2L) (also, GNN don't have to have a fixed representation size each layer) where B*L>Omega(n). While in theorem 8 we get number of parameters O(n^(2+1/c)log(n)) which for c<2 where they agree doesn't seem to give a better bound.\n- You do not show how to implement Bellmen Ford with a GNN which is missing from the proof.\n\n\n\n\nMinor remarks:\n- In App A first equation should be min not max\n- In alg. 1 should be x_i=min(x_i,a_i+1) not x_i=min(x_i,a_i), also switch between x and v which is confusing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4lVSNUxzPq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Overview: \n========\nThe paper suggests a modification to graph neural networks, which is claimed to overcome GNN expressiveness issues recently shown by Loukas (ICLR 2020).\n\nComments:\n=========\nI had multiple difficulties in following the content of the paper, some are detailed next.\n\n-- \"Unfortunately, [GNNs] require large depth as proved in Theorem 6 above\"\nThe lower bound in Theorem 6 is for approximation alpha < 1.5, but here you discuss approximation O(log n), doesn't this void the lower bound? Why cannot usual GNNs produce an O(log n) approximation (and specifically Bourgain's embedding)?\n\n-- \"While there do exist semidefinite programming based algorithms (Linial et al., 1995) for computing the embeddings required for Bourgain’s theorem, they are not suitable for implementation via efficient neural architectures. Instead [...] we adapt the sketch based approximate shortest path algorithms of Das Sarma et al. (2010)\"\n\nIn fact, the algorithm you implement is the one from Bourgain and Linial et al., not Dar Sarma et al. All those works use roughly the same sketching algorithm, which measures the distance of each point to randomly chosen clusters. However, the distance estimation procedure you implement (specifically ~d_G(s,t) = max_i|v_s^(i) - v_t^(i)|) is Bourgain's (this is just an ell-infinity embedding). Dar Sarma et al.'s estimation procedure is different and (building on the well-known work of Thorup-Zwick) relies on computing the common nearest neighbors of the given pair s,t in the random clusters. Note that this bears on the correctness of the proof of Theorem 8 (I think the statement still holds due to Matousek's analysis of Bourgain's embedding, but not for the reason you cite). Also note that in Theorem 8 (as well as all aforementioned results) c needs to be an integer (in particular, it is known that any approximation less than 3 is impossible with less than ~Omega(n^2) parameters).\n\n-- For min-cut, you write that traditional GNNs require Omega(sqrt(n)) depth/rounds, citing Loukas (2020). But doesn't that lower bound entail both the depth and the width (d*sqrt(w) = ~Omega(sqrt(n)))?\n\n-- I am unable to follow the proof of Theorem 9. Could you please explain the correctness of your construction.\n\n(On this note, the sentence \"Karger & Stein (1996) implies that with probability at least 1/n^2 there exists a prefix L' of L such that...\" seems like an unfortunate inaccuracy; the \"prefix\" exists deterministically, and their guarantee is that the iterative random contraction algorithm finds it with probability at least ~1/n^2.)\n\nConclusion:\n=========\nI am currently unable to recommend accepting this paper, due to what seems like multiple inaccuracies, misinterpretations of prior work, unclear statements, and possibly technical correctness issues. I will await clarifications from the authors on the points detailed above.\n\nPost discussion update\n=========\nAfter discussion with the authors, I have calibrated my score upward to 4, since the authors seemed willing to engage in discussion and correct/improve the paper, which I appreciate, but I still recommend not accepting the paper.\n\nThe authors generally acknowledged (though have not yet fixed) the issue of wrong attribution of the APSP algorithm. This isn't just a matter of citing B instead of A; the paper (still) contains a lengthy discussion of why A is not suitable, so instead they must resort to B, even though in reality they just use A (and B remains unused). This is glaring since these papers are famous classics, widely taught in graduate courses, their content is well known, and it is puzzling how a diametrically incorrect representation of them made its way into the paper.\n\nThe reason I dwell on this is that it signifies a larger issue with the paper. The original version was peppered with formal statements which were at best inaccurate, and even though the authors fixed (or said they would fix) the ones I pointed out, I remain unable to trust the overall technical soundness of the paper. The review time frame doesn't allow a reviewer to carefully verify every statement (nor would I want to), there must be some commitment of due diligence on part of the authors, that up to a small inevitable fraction of inaccuracies, the formal content is rigorously correct. I'm afraid the current version of the paper is quite off this mark.\n\nPutting formal soundness aside, my present understanding of the idea of the paper is the following: The authors observe that many basic computations on graphs can be parallelized into a few computations of small width and depth. Usual GNNs can implicitly implement this if their width is large enough, but this poses a computational burden, and there are obvious advantages to explicitly building this parallelism into the architecture. This seems like a sensible and potentially empirically useful observation, but the experimental section still seems too thin to make the case properly. That said, perhaps I have not fully understood the paper, since its frequent inaccuracies and fuzzy statements made it a bit hard for me to follow. \n\nIn conclusion. I think the paper should undergo a substantial revision:\n1. Clean up the theory part and ensure its formal soundness,\n2. Crystalize the point of the paper (in particular, rather than just presenting GNN+, I hope a revised version would include a more thorough comparison with usual GNNs - not just dismiss them with some citations of prior works which allegedly prove limitations - this leaves doubts about the exact model and assumptions, particularly since as discussed above, the prior work is not always cited accurately),\n3. Possibly expand the experimental section.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1ejc1mWKI2r", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The main question this paper tackles is: can one develop sample efficient architectures for graph problems while retaining the simplicity of the message passing framework?\n\nWhile combining message passing with GNNs has shown to have positive empirical results,  we do not know of a general neural architecture that is  versatile enough to provably encode the solution space of a variety of graph problems such as shortest paths and minimum spanning trees. \n\nThis paper introduces a theoretically principled architecture -- GCN+ -- which is attempts to make GCNs more efficient by using ideas from the subfields of sketching approximations and parallel computing.\n \n############\n\nI vote for accepting the paper due to its novelty and the pros listed below.  \n\n############\n\nPros\n\n+ An interesting paper with novel contribution combining ideas from parallel computing and sketching approximations. \n+ Major algorithmic contribution of interest to practitioners \n+ Theoretical contributions in the form of several theorems in the paper \n\nCons \n\n- No code provided with the submission", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a new GNN+ architecture and provide interesting theoretical observations about the architecture. The paper is quite promising and has several interesting insights. However, most of the reviewers believe that the paper is not ready for publication and can be significantly improved by: a) more formal and precise statements, b) clarifying the key points of the paper, c) more thorough experimental validation of the framework on real-world datasets. 


Decision: Reject