What graph neural networks cannot learn: depth vs width
Authors: Andreas Loukas
Venue:  (2020)
Keywords: graph neural networks
capacity
impossibility results
lower bounds
expressive power

Abstract: This paper studies the expressive power of graph neural networks falling within the message-passing framework (GNNmp). Two results are presented. First, GNNmp are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNNmp can lose a significant portion of their power when their depth and width is restricted. The proposed impossibility statements stem from a new technique that enables the repurposing of seminal results from distributed computing and leads to lower bounds for an array of decision, optimization, and estimation problems involving graphs. Strikingly, several of these problems are deemed impossible unless the product of a GNNmp's depth and width exceeds a polynomial of the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.

Published as a conference paper at ICLR 2020
WHAT GRAPH NEURAL NETWORKS CANNOT LEARN: DEPTH VS WIDTH
Andreas Loukas
Ecole Polytechnique Fédérale Lausanne andreas loukas@epfl.com ch
ABSTRACT
This paper studies the expressive power of graph neural networks falling within the message-passingg framework (GNNmp). Two results are presented. First, GNN are shown to be Turing universal under sufficient conditions on their depth, width, node attributes, and layer expressiveness. Second, it is discovered that GNN can lose a significant portion of their power when their depth and width is restricted. The proposed impossibility statements stem from a new technique that enables the repurposing of seminal results from distributed computing and leads lower bounds for an array of decision, optimization, and estimation problems involving graphs. Strikingly, several of these problems are deemed impossible unless the product of GNNmp 's depth and width exceeds polynomial of the graph size; this dependence remains significant even for tasks that appear simple or when considering approximation.
INTRODUCTION
A fundamental question in machine learning is to determine what model can and cannor learn. In deep learning, there has been significant research effort in establishing expressivity results for feed- forward (Cybenko) 1989, Hornik et al., 1989. Lu et al. 2017) and recurrent neural networks (Neto) 1997). as well as more recently for Transformers and Neural GPUs (Pérez et al.] 2019). We have also seen the first results studying the universality of graph neural networks, i.e., neural networks that take graphs as input. Maron et al. (2019b) derived universal approximation theorem over invariant functions targeted towards deep networks whose layers are linear and equivariant to permutation of their input. Universality was also shown for equivariant functions and a particular shallow architecture (Keriven & Peyré 2019).
Universality statements allow us to grasp the expressive power of models in the limit. In theory, given enough data and the right training procedure, universal network will be able solve any task that it presented with. Nevertheless, the insight brought by such results can also be limited. Knowing that sufficiently large network can be used solve any problem does not reveal much about how neural networks should be designed in practice. It also cannot guarantee that said network will be able to solve given task given particular training procedure, such stochastic gradient descent.
On the other hand, it might be easier to obtain insights about models by studying their limitations. After all, the knowledge of what cannor be computed (and thus learned) by network of specific characteristics applies independently of the training procedure. Further, by helping us comprehend the difficulty of a task in relation model, impossibility results can yield practical advice on how to select model hyperparameters. Take, for instance, the problem of graph classification. Training graph classifier entails identifying what constitutes a class, i.c., finding properties shared by graphs in one class but not the other, and then deciding whether new graphs abide to said learned properties. However, if the aforementioned decision problem shown to be impossible by a graph neural network of certain depth then can be certain that the same network will not learn how classify sufficiently diverse test set correctly, independently of which learning algorithm is employed. We should, therefore, focus networks deeper that the lower bound when performing experiments.

---

Published as a conference paper at ICLR 2020
problem
bound
problem
bound
eycle detection (odd)
dw Qn log n)
shortest path
d [ logn)
cycle detection (even)
du = 52( V / log n)
max. indep. set min. vertex cover perfect coloring girth 2-approx. diam. 9/2aaprrxx
dw [ /log n) for w 0(1)
subgraph verification*
dv w 92( / log n))
dw = ②n /log 2 n) for w = 0(1)
min. spanning tree
d 52( / log n)
dw 52(n /log n) for w O(1)
min. cut diam. computation
d/w w = S2( / log n)
du = 52 /////ooo
dw (m//logn)
dw 92( ((vrn/lgg))
Table I: Summary of main results. Subgraph verification* entails verifying one of the following predicates for given subgraph: is connected, contains a cycle, forms a spanning tree, is bipartite, is a cut, is an 8-/ cut, All problems are defined in Appendix A
1.1 MAIN RESULTS
This paper studies the expressive power of peessage-passing graph neural networks (GNN Giimer ett al. (017)_ This model encompasses several state-of-the-aa networks, including GCN (Kipt & Welling 2016). gated graph neural networks (Li et al. 2015), molecular fingerprints (Duvenaud et al.
2015). interaction networks (Battaglia et al. 2016), molecular convolutions (Kearnes et al. (016)) among many others. Networks using global state (Battaglia al. 2018 or looking at multiple hops per layer (Morris et al. 2019 Liao et al. can often be re-expressed as such. The provided contributions are two-fold:
2019 Isufi et al. (020) are not directly GNN but they
I. What GNN can compute. Section 3 derives sufficient conditions such that GNN can compute any function on its input that is computable by a Turing machine. This result compliments recent universality results (Maron et al. [2019b Keriven & Peyré 2019) that considered approximation (rather than computability) over specific classes of functions (permutation invariant and equivariant) and particular architectures. The claim follows in straightforward manner by establishing the equivalence of GN with LOCAL (Angluin 1980, Linial 1992 Naor Stockmeyer 1993). classical model in distributed computing that is itself Turing universal. In nutshell, GNN are shown to be universal if four strong conditions are met: there are enough layers of sufficient expressiveness and width, and nodes can uniquely distinguish each other. Since Turing universality is a strictly stronger property than universal approximation, Chen et al. (2019) 's argument further implies that Turing universal GN can solve the graph isomorphism problem sufficiently deep and wide network can compute the isomorphism class of its input).
II What GNN cannot compute (and thus learn). Section 4 analyses the implications of restrict- ing the depth d and width of GNN that do not use a readout function. Specifically, it is proven that GNN lose a significant portion of their power when the product dw, which I call capacity, is restricted. The analysis relies on new technique that enables repurposing impossibility results from the context of distributed computing to the graph neural network setting. Specifically, lower bounds for the following problems are presented: (i) detecting whether graph contains a cycle of specific length; (ii) verifying whether a given subgraph is connected, contains a cycle, is a spanning tree, is bipartite, is simple path, corresponds to cut or Hamiltonial cycle; (iii) approximating the shortest path between two nodes, the minimum cut, and the minimum spanning tree; (iv) finding a maximum independent set, minimum vertex cover, a perfect coloring; (v) computing or approximating the diameter and girth. The bounds are summarized in Table and the problem definitions can be found in Appendix A Section presents some empirical evidence of the theory.
Though formulated in a graph-theoretic sense, the above problems are intimately linked to machine learning on graphs. Detection, verification, and computation problems are relevant to classification: knowing what properties of a graph a GNN cannot see informs us also about which features of graph can it extract. Further, there have been attempts use GNN mp to devise heuristics for graph- based optimization problems (Khalil et al.) [017]] Battaglia et al., 2018 Li et al., [2018] Joshi al. 2019, BBianhhi et al. 2019), such as the ones discussed above. The presented results can then be taken as worst-case analysis for the efficiency of GNN in such endeavors.
1.2 DISCUSSION
The results of this paper carry several intriguing implications. To start with, it is shown that the capacity du of a GNN plays significant role in determining its power. Solving many problems
2

---

Published as a conference paper at ICLR 2020
is shown to be impossible unless du = [(n"), where 8 E [1/2, 2). is the number of nodes of the graph, and f(n) ((g(n)) is interpreted as f(n) being, up to logarithmic factors, larger than g(n) as n grows. This reveals a direct trade-off between the depth and width of a graph neural network. Counter-intutivelyy the dependence on n can be significant even if the problem appears local in nature or one only looks for approximate solutions. For example, detecting whether G contains a short cycle of odd length cannot be done unless dw = (()).. Approximation helps, but only to limited extent; computing the graph diameter requires dw = (nn) and this reduces to du = ( nn) for any 3/2-factor approximation. Further, it is impossible to approximate within any constant factor the shortest path, the minimum cut, and the minimum spanning tree, all three of which have polynomial-tne time solutions, unless d/w = 22 (n() Finally, for truly hard problems, the capacity may even need to be super-linear on n. Specifically, it is shown that, even if the layers of the GN are allowed to take exponential time, solving certain NP-hard problems necessitates d (2n")) depth for any constant-width network.
Relation to previous impossibility results. In contrast universality (Maron al.) 2019b Keriven & Peyré 2019), the limitations of GN have been much less studied. In particular, the bounds presented here are the first impossibility results that (i) explicitly connect GN properties (depth and width) with graph properties and that (ii) go beyond isomorphism by addressing decision, opti- mization, and estimation graph problems. Three main directions of related work can be distinguished. First, Dehmamy et al. (2019) bounded the ability of graph convolutional networks (i.e., GNN w/o messaging functions) to compute specific polynomial functions of the adjacency matrix, referred to as graph moments by the authors. Second, Xu et al. (2018) and Morris et (2019) established the equiv- alence of anonymous GN (those that do not rely on node identification) to the Weisfeiler-Lehiie (WL) graph isomorphism test. The equivalence implies that anonymous networks are blind to the many graph properties that WL cannot see: e.g., any two regular graphs with the same number of nodes are identical from the perspective of the WL test (Arvind et al. 2015 Kiefer al., 2015). Third, in parallel to this work, Sato et al. (2019) utilized a connection to LOCAL to derive impossibility results for the ability of class of novel partially-labeled GN to find good approximations for three NP-hard optimization problems. Almost all of the above negative results occur due to nodes being unable distinguish between neighbors at multiple hops (see Appendix D). With discriminative attributes GNN become significantly more powerful (without necessarily sacrificing permutation in/equivariance). Still, as this work shows, even in this setting certain problems remain impossible when the depth and width of the GNN is restricted. For instance, though cycles can be detected (something impossible anonymous networks (Xu et al. 2018 Morris et al.. 2019)), even for short cycles one now needs dw- 22()). Further, in contrast to Sato et al. 2011 . an approximation ratio below 2 for the minimum vertex cover is not impossible, but necessitates dw = ((())).
Limitations. First, all lower bounds are of a worst-case nature: problem is deemed impossible if there exists graph for which it cannot be solved. The discovery non worst-case capacity bounds remains an open problem. Second, rather than taking into account specific parametric functions, each layer is assumed to be sufficiently powerful to compute any function of its input. This strong assumption does not significantly limit the applicability of the results, simply because all lower bounds that hold with universal layers also apply to those that are limited computationally, Lastly, it will be assumed that nodes can uniquely identify each other. Node identification is compatible with permutation invariance/equivariann particular way the ids have been assigned. In the literature, one-hot encoded node ids are occasionally useful (Kipf & Welling, 2016; |Berg et al., 2017). When attempting to learn functions across multiple graphs. ids should be ideally substituted by sufficiently discriminative node attributes (attributes that uniguely identify each node within each receptive field it belongs to can serve as ids). Nevertheless, similar to the unbounded computation assumption, if a problem cannot be solved by a graph neural network in the studied setting, it also cannot be solved without identifiers and discriminative attributes. Thus, the presented lower bounds also apply to partially and fully anonymous networks.
as long as the network output is asked to be invariant to the
Notation. I consider connected graphs G = (V, E) consisting of n = | nodes. The edge going from By to U/ is written as esej and it is asserted that ese- then also eje; E E. The neighborhood NR of node E V consists of all nodes ;y for which Ciej E E. The degree of u, is denoted by deg. A is the maximum degree of all nodes and the graph diameter dG is the length of the longest
3

---

Published as a conference paper at ICLR 2020
shortest path between any two nodes. In the self-loop graph G (V,E*), the neighborhood set of 0/ is given by Ni NG U Dj.
2 THE GRAPH NEURAL NETWORK COMPUTATIONAL MODEL
Graph neural networks are parametric and differentiable learning machines. Their input is usually an attributed graph G. (G, (a: U, E V), (at=) Ci- E E)), where vectors di..... On encode relevant node attributes and aıej are edge attributes, c.g., encoding edge direction.
Model I formalizes the graph neural network operation by placing it in the message passing model Gilmer et al., 2017). ). The computation proceeds in layers, within which a message mæej is passed along each directed edge Ctej & going from E; to and each node updates its internal representation by aggregating its state with the messages sent by its incoming neighbors vj E W, The network output can be either of two things: vector x; for each node f single vector aG obtained by combining the representations of all nodes using a readout function. Vectors x//0g could be scalars (node/graph regression), binary variables (node/graph classification) or multi-dimensional (node/graph embedding). I use the symbols GNN mp and GNN to distinguish between models that return a vector per node and one per graph, respectively.
Computational model 1 Message passing graph neural network (GNNmp)
(0) Initialization: Set xi = a; for all 02 E V. for layer = 1.....d. .d do
for every edge c E E (in parallel) do
m minj
(8)
MSG
(e-1) (1-1)
Ubi Uj aims)
for every node i E V (in parallel) do
(6) UP Σ
m
ByENT
Set 24
return Either x; for every U; V (GNN DG
READ (f2; : 04 V}) (GNN
The operation of a GNN is primarily determined by the messaging, update, and readout functions. I assume that MsG, and UP, are general functions that act on intermediate node representations and node ids (the notation is overloaded such that v/ refers to both the i-th node as well as its unique id). As is common in the literature (Lu et al.) 2017 Battaglia et al., 2018), these functions are instantiated by feed-forward neural networks. Thus, by the universal approximation theorem and its variants (Cybenko) 1989; Hornik et al. 1989.. they can approximate any general function that maps vectors onto vectors, given sufficient depth and/or width. Function READ is useful when one needs to retrieve a representation that is invariant of the number of nodes. The function takes as an input a multiset, i.e., a set with possibly repeating elements, and returns a vector. Commonly, READ chosen be a dimension squashing operator, such as a sum or histogram, followed by feed-forward neural network (Xu et al. 2018 Seo et 2019).
Depth and width. The depth d is equal the number of layers of the network. Larger depth means that each node has the opportunity to learn more about the rest of the graph (i.e., it has a larger receptive field). The width of GNNmp is equal the largest dimension of state 2 over all layers and nodes v; E V. Since nodes need to be able to store their own unique ids, in the following it is assumed that each variable manipulated by the network is represented in finite-precision using p @llog n) bits (though this not strictly necessary for the analysis).
3 SUFFICIENT CONDITIONS FOR TURING UNIVERSALITY
This section studies what graph neural networks can compute. is demonstrated that, even without readout function, network is computationally universa |
if it has enough layers of sufficient
It can compute anything that Turing machine can compute when given attributed graph as input.
4

---

Published as a conference paper at ICLR 2020
width, nodes can uniquely distinguish each other, and the functions computed within each layer sufficiently expressive. The derivation entails establishing that GNN mp is equivalent to LOCAL, a classical model used in the study the distributed algorithms that is itself Turing universal.
3.1 THE LOCAL COMPUTATIONAL MODEL
fundamental question in theoretical computer science determining what can and cannot be computed efficiently by distributed algorithm. The LOCAL model, initially studied by Angluin (1980), Linial (1992), and Naor & Stockmeyer (1993), provides a common framework for analyzing the effect of local decision. Akin to GNN mp- in LOCAL graph plays double role: it is both the input of the system and captures the network topology of the distributed system that solves the problem. In this spirit, the nodes of the graph are here both the machines where computation takes place as well as the variables of the craph-theoretic problem we wish to solve solve-similed similarly, edges model communication links between machines well relations between nodes. Each node v; E V is given problem-specifie local input and has to produce a local output. The input contains necessary the information that specifies the problem instance. All nodes execute the same algorithm, they are fault-free, and they are provided with unique identifiers.
A pseudo-code description is given in Model 2 Variables s(") and s refer respectively to the state of 2; in round / and to the message sent by vy to o; in the same round. Both are represented as strings. The computation starts simultaneously and unfolds in synchronous rounds ( 1,..., Three things can occur within each round: each node receives string of unbounded size from its incoming neighbors; each node updates its internal state by performing some local computation; and each node sends string to every one of its outgoing neighbors. Functions ALG| and AL. algorithms computed locally by a Turing machine running on node o. Before any computation is done, each node U is aware of its own attribute a, as well of all edge attributes {au-j : By E }
Computational model 2 LOCAL (computed distributedly by each node iú E V).
Initialization: Set s = (a,, v.) and ji-j = (aj, 2z) for all city E. for round =1, d do (t-1)
Receive sizj from Uj E Mit compute
(E)
ALGE (((
( a+t)) : uy ENi] ,
(6-1) [bt))
8
and send jut ALO? (,19) (5 20) uy EN; (d) return 8
In LOCAL, there are no restrictions on how much information a node can send at every round. (E)
Asserting that each message 8 is at most bits yields the CONGEST model (Peleg 2000
3.2 TURING UNIVERSALITY
The reader might have observed that LOCAL resembles closely GNN in its structure, with only a few minor differences: firstly, whereas a LOCAL algorithm may utilize messages any way chooses, a GNN network N always sums received messages before any local computation. The two models also differ in the arguments of the messaging function and the choice of information representation (string versus vector). Yet, as the following theorem shows, the differences between GNND mp and LOCAL are inconsequential when seen from the perspective of their expressive power:
Theorem 3.1 (Equivalence). Let Ne(Ga) be the binary representation of the state (a ..... (1) a GNN; mp network N and Ae(G.) (f) ...., .....()) ( that of LOCAL algorithm A. If MSG, and UP: are Turing complete functions, then, for any algorithm A there exists N (resp. for any N there exists A) such that
(L)
Ac(G.) N:(G.) for every layer l and Go E Ga.
where Ga is the set of all altributed graphs.
5

---

Published as a conference paper at ICLR 2020
This equivalence enables to reason about the power of GNN by building on the well-studied properties of LOCAL. In particular, it is well known in distributed computing that, as long as the number of rounds of a distributed algorithm is larger than the graph diameter dg, every node in LOCAL can effectively make decisions based on the entire graph (Linial 1992). Together with Theorem 3.1 the above imply that, if computation and memory are not an issue, one may construct a GNN that effectively computes any computable function w.r.t. its input.
Corollary 3.1. GN can compute any Turing computable function over connected attributed graphs if the following conditions are jointly met: each node is uniquely identified; MsG, and UP, are Turing-complete for every layer E; the depth is at least d Z 5G layers; and the width is unbounded.
Why is this result relevant? From a cursory review, it might seem that universality is an abstract result with little implication machine learning architects. After all, the utility of a learning machine is usually determined not with regards to its expressive power but with its ability to generalize to unseen examples. Nevertheless, can be argued that universality an essential property of good learning model. This is for two main reasons: First, universality guarantees that the learner does not have blind-spots in its hypothesis space. No matter how good the optimization algorithm is, how rich the dataset, and how overparameterized the network is, there will always be functions which non universal learner cannot learn. Second, a universality result provides a glimpse on how the size of the learner's hypothesis space is affected by different design choices. For instance, Corollary [.1 puts forth four necessary conditions for universality: the GNN should be sufficiently deep and wide, nodes should be able uniquely and consistently identify each other, and finally, the functions utilized in each layer should be sufficiently complex. The following section delves further into the importance of two of these universality conditions. It will be shown that GNN lose significant portion of their power when the depth and width conditions are relaxed.
The universality of GNN Though a universality result could also be easily derived for networks with a readout function, the latter is not included as deviates from how graph neural networks are meant to function: given a sufficiently powerful readout function, a GNN of d depth and O(A) width can be used to compute any Turing computable function. The nodes should simply gather one hop information about their neighbors; the readout function can then reconstruct the problem input based on the collective knowledge and apply any computation needed.
4 IMPOSSIBILITY RESULTS AS A FUNCTION OF DEPTH AND WIDTH
This section analyzes the effect of depth and width in the expressive power of GNN will consider problems that cannot be solved by network of given depth and width.
mp Specifically, I
To be able to reason in terms of width, will be useful to also enforce that the message size in LOCAL at each round is at most b bits. This model goes by the name CONGEST in the distributed computing literature (Peleg 2000). In addition, will be assumed that nodes do not have access to a random generator. With this in place, the following theorem shows us how to translate impossibility results from CONGEST to GNN
Theorem 4.1. Ifa problem P cannot be solved in less than d rounds in CONGEST using messages of at most b bits, then P cannot be solved by a GNNip of width w S (b log, n)/p = O logn) and depth d.
The p (log r2) factor corresponds to the length of the binary representation of every variable- the precision needs to depend logarithmically on for the node ids to be unique. With this result in place, the following sections re-state several known lower bounds in terms of GNN 's depth and width.
4.1 IMPOSSIBLLITY RESULTS FOR DECISION PROBLEMS
I first consider problems where needs to decide whether a given graph satisfies certain prop- crty (Feuilloley & Fraigniaud] 2016). Concretely, given a decision problem P and a graph G. the GNN should output I; E (rrue for all v E V. The network then accepts the premise if the logical conjunction of (æ1,..., In } is true and rejects it otherwise. Such problems connected to graph classification: classifying a graph entails identifying what constitutes a class from some training set and using said learned definition decide the label of graphs sampled from
intimately

---

Published as a conference paper at ICLR 2020
the test set. Instead, will suppose that the class definition is available to the classifier and I will focus on the corresponding decision problem. As a consequence, every lower bound presented below for decision problem must also be respected by a GNN classifier that attains zero error on the corresponding graph classification problem.
Subgraph detection. In this type of problems, the objective is decide whether G contains subgraph belonging to a given family. focus specifically on detecting whether G contains a cycle Ck. i.e. simple undirected graph of & nodes each having exactly two neighbors. As the following result shows, even with ids, cycle detection remains relatively hard:
Corollary 4.1 (Repurposed from (Drucker et al., 2014; Korhonen & Rybicki 2018)). There exists graph G on which every GNN of width w requires depth at least d = 22 V / (w logm)) and d= (n/(ww n)) to detect if G contains a cycle C₁ for even l 2 4 and odd l 2 5, respectively.
Whereas an anonymous GN cannot detect cycles (e.g., distinguish between two C3 vs one Ce (Maron et al. 2019ab), it seems that with ids the product of depth and width should exhibit an (at least) linear dependence on n. The intuition behind this bound can be found in Appendix C and empirical evidence in support of the theory presented in Section
Subgraph verification. Suppose that the network is given a subgraph H = (VH, En) of G in its input. This could, for instance, be achieved by selecting the attributes of each node and edge to be a one-hot encoding of their membership on Vи and Eh. respectively. The question considered is whether the neural network can verify certain property of H. More concretely, does graph neural network exist that can successfully verify H as belonging to a specific family of graphs w.r.t. G? In contrast to the standard decision paradigm, here every node should reach the same decision accepting or rejecting the hypothesis. The following result a direct consequence of the seminal work by Sarma et al. (2012):
Corollary 4.2 (Repurposed from (Sarma et al., 2012)). There exists graph G on which every GNN mp of width w requires depth least d = 2 log" +6G) to verify if some subgraph of G connected, contains cycle, forms a spanning tree of G. bipartite, is cut of G. or is an s-t cut of G. Furthermore, the depth should be at least d = Ω (( ve log
+ +dc)) with 7 = 1 200
to verify if H is a Hamiltonian cycle or simple path.
Therefore, even if one knows where to look in G. verifying whether a given subgraph meets a given property can be non-trivial, and this holds for several standard graph-theoretic properties. For instance, if we constrain ourselves to networks of constant width, detecting whether a subgraph is connected can, up to logarithmic factors, require (V) depth in the worst case.
4.2 IMPOSSIBILITY RESULTS FOR OPTIMIZATION PROBLEMS
I turn my attention to the problems involving the exact or approximate optimization of some graph- theoretic objective function. From machine learning perspective. the considered problems can be interpreted as node/edge classification problems: each node/edge is tasked with deciding whether belongs the optimal set or not. Take, for instance, the maximum independent set, where one needs to find the largest cardinality node set, such that no two of them are adjacent. Given only information identifying nodes, GNN will be asked to classify each node being part of the maximum independent set or not.
Polynomial-time problems. Let me first consider three problems that possess known polynomial- time solutions. To make things easier for the GNN I relax the objective and ask for an approximate solution rather than optimal. An algorithm (or neural network) said attain an a-approximation it produces a feasible output whose utility is within factor a of the optimal. Let OPT be the utility of the optimal solution and ALG that of the a-approximation algorithm. Depending on whether the problem entails minimization or maximization, the ratio ALG/OPT is at most a and at least 1/a, respectively.
According to the following corollary, it is non-trivial to find good approximate solutions:
Corollary 4.3 (Repurposed from (Sarma et al. 2012 Ghaffari & Kuhn 2013)). There exists graphs G and G of diameter dG O(log n) and oo: (11) on which every GNN; of width w requires
7

---

Published as a conference paper at ICLR 2020
2 respectively, to approximate within any constant factor: the minimum cut problem, the shortest s-t path problem, or the minimum spanning tree problem.
depth at least d ( woog and d' ( 1og with y
Thus, even for simple problems (complexity-wise), in the worst case a constant width GNN mp should be almost (Vyn) deep even if the graph diameter is exponentially smaller than n.
NP-hard problems. So what about truly hard problems? Clearly, one cannot expect GNN to solve NP-hard time in polynomial time" However, it might be interesting thought experiment to consider a network whose layers take exponential time on the input size-e.g. by selecting the MsG; and UP: functions to be ferw-fo networks of exponential depth and width. Could one ever expect such a GNN mp to arrive at the optimal solution?
The following corollary provides necessary conditions for three well-known NP-hard problems:
Corollary 4.4 (Repurposed from (Censor-Hillel et al. 2017)). There exists graph G on which every GNN of width w O(1) requires depth at least d = Mn' /log" n) to solve: the minimum vertex cover problem; the maximum independent set problem: the perfect coloring problem.
Thus, even if each layer is allowed to take exponential time, the depth should be quadratically larger than the graph diameter 5G = (n)) to have a chance of finding the optimal solution. Perhaps disappointingly, the above result suggests that it may not be always possible exploit the distributed decision making performed by GN architectures to find solutions faster than classical (centralized) computational paradigms.
4.3 IMPOSSIBILITY RESULTS FOR ESTIMATION PROBLEMS
Finally, I will consider problems that involve the computation or estimation of some real function that takes as an input the graph and attributes. The following corollary concerns the computation of two well-known graph invariants: the diameter åG and the girth. The latter is defined the length of the shortest cycle and is infinity if the graph has no cycles.
Corollary 4.5 (Repurposed from (Frischknechtt al. 2012).. There exists a graph on which every GNN mp of width w requires depth at least d = (2nn/ ( log n) + åG) to compute the graph diameter dG and d (L/vn/C (w log n) + àG) to approximate the graph diameter and girth within a factor of 3/2 and 2, respectively.
Term &G appears in the lower bounds because both estimation problems require global information. Further, approximating the diameter within 3/2 factor seems to be simpler than computing it. Yet, in both cases, one cannot achieve this using a GNN whose capacity constant. As final remark,
the graphs giving rise to the lower bounds of Corollary 4.5 have constant diameter and (n22) edges. However, similar bounds can be derived also for graphs with (n log n) edges (Abboud et al. 2016).
For the case of exact computation, the lower bound is explained in Appendix C
5 EMPIRICAL EVIDENCE
This section aims to empirically test the connection between the capacity die of a GNN the number of nodes n of its input, and its ability solve given task. In particular, I considered the problem of 4-cycle classification and tasked the neural network with classifying graphs based on whether they contained cycle of length four. Following the lower bound construction described in Appendix A I generated five distributions over graphs with n E (8, 16, 24, 32, 44) nodes and an average diameter of (4, 6, 8, 9. 11), respectively (this was achieved by setting p E (6, 8, 10, 12, 14), see Figure Ba). For each such distribution, I generated training and test set consisting respectively of 1000 and 200 examples. Both sets were exactly balanced, i.e., any example graph from the training and test set had exactly 50% chance of containing 4-cycle.
The experiment aimed to evaluate how able were GNN of different capacities to attain high accuracy
on the test set. To this end, I performed grid search over the hyperparameters w E (2, 10, 20) and
Unless P-NP.
8

---

Published as a conference paper at ICLR 2020
c-16
n-24
n=-32
hy:40
2000
0.0
25.
350 700
532
100
2003
sapth
dusth
training accuracy of all trained networks
1.0
3.5
3.0
502
depth wi8t
sapth
supth
death with
(b) test accuracy of all trained networks
1.0
0.9
test accuracy
0.9
0.8
0.8
n=8
n=8
training
n=16
n=16
n-24
2-
0.6
0.6
n-32
n-
n040
40
0
100
200
300
400
100
200
300
400
depth width
depth width
(c) best training accuracy
(d) best test accuracy
Figure I: Accuracy function of GNN capacity du and (Best seen in color.)
d E (5, 10, 20, 15). To reduce the dependence the initial conditions and training length, for each hyperparameter combination, I trained 4 networks independently (using Adam and learning rate decay) for 4000 epochs. The GNN chosen was that proposed by Xu al. (2018), with the addition of residual connections this network outperformed all others that experimented with.
is important to stress that empirically verifying lower bounds for neural networks is challenging. because it involves searching over the space of all possible networks in order to find the ones that perform the best. For this reason, an experiment such as the one described above cannot be used to verify the tightness of the bounds: we can never be certain whether the results obtained are the best possible or whether the optimization resulted in local minimum. In that view, the following results should be interpreted in a qualitative sense. The question that I will ask is: which extend do the trends uncovered match those predicted by the theory? More specifically, does the ability of network to detect 4-cycles depend the relation between dw and n?
To answer this question, Figure T depicts the training and test accuracy as function of the capacity dw for all the 240 networks trained (5 distributions x 3 widths x 4 depths x 4 iterations). The accuracy of the best performing networks with the smallest capacity is shown in Figures Tc and Td] important to stress that, based Weisfeiler-Lehman analyses, anonymous GNN cannot solve the considered task. However, as it seen in the figures, the impossibility is annulled when using node id Indeed, even small neural networks could consistently classify all test examples perfectly (i.e., achieving 100% test accuracy) when < 16. Moreover, as the theoretical results predicted, there is strong correlation between the test accuracy, dw and n (recall that Corollary [4. predicts dw n)). Figure Id shows that networks of the same capacity were consistently less accurate on the test set as n increased (even though the cycle length remained 4 in all experiments). It is also
Thii evaluation paradigm, however, can be used invalidate the theoretical results if one finds that GNN of small depth and width can solve all lower bound problem instances. "The considered graphs featured the same node set (with different edges) and one-hot encoding of the node-ids used input features.

---

Published as a conference paper at ICLR 2020
anonymous
degree
random unique id
unique id
0.9
0.9
test accuracy
0.9
0.8
0.7
0.7
0.6
0.5
0.5
1000
2000 epech
3000
2000 epoch
4000
0
0.5
depthhicriecal
(a) effect of anonymity
(b) depth vs width
Figure (a) GNNs are significantly more powerful when given discriminative node attributes. (b) Test accuracy indicated by color as function of normalized depth and width. Points in highlighted areas correspond to networks with super-critical capacity, whereas the diagonal line separates networks that more deep than wide. (For improved visibility, points are slightly perturbed. Best seen in color.)
striking to observe that even the most powerful networks considered could not achieve a test accuracy above 95% for n 16; for 40 their best accuracy was below 80%.
Effeet of anonymity. Figure 2a plots example training and test curves for GNN trained with four different node attributes: no attributes (anonymous), one-hot encoding of the node degrees (degree), a one-hot encoding of node ids (unique id), and one-hot encoding of node ids that changed across graphs (random unique id). can be clearly observed that there is a direct correlation between accuracy and the type of attributes used. With non- or partially-discrninaatyy attributes, the network could not detect cycles even in the training set. The cycle detection problem was solved exactly with unique ids, but when the latter were inconsistently assigned, the network could not learn to generalize.
Exchangeability of depth and width. Figure 2b examines further the relationship between depth, width, and test accuracy. This time, networks were separated depending on their depth and width normalized by the square root of the "critical capacity". For each n. the critical capacity is the minimum du of a network that was able to solve the task on graph of nodes here, solving amounts to a test accuracy above 95%. In this way, a network of depth d and width w tested on nodes corresponds to point positioned at x d/ v/v /citical, y w//v Veritical and no network positioned at ay < can solve the task non-highlighhted region the bottom left corner). As seen, there is a crisp phase transition between the regime of under- and super-critical capacity: almost every network meeting the condition dw 2 critical was able to solve the task, irrespective of whether the depth width was larger. Note that, the exchangeability of depth and width cannot be guaranteed by the proposed theory which asserts that the condition dw 52( (n())) is necessary- but not sufficient. The empirical results however do agree with the hypothesis that, for 4-cycle classification, depth and width are indeed exchangeable.
6 CONCLUSION
This work studied the expressive power of graph neural networks falling within the message-passing framework. Two results were derived. First, sufficient conditions were provided such that GNN can compute any function computable by a Turing machine with the same connected graph as input. Second, it was discovered that the product of GNN 's depth and width plays prominent role in determining whether the network can solve various graph-theoretic problems. Specifically, was shown that GNN with du = 2(nn)) and 8 E [0.5. 2| cannot solve a range of decision, optimization, and estimation problems involving graphs. Overall, the proposed results demonstrate that the power of graph neural networks depends critically on their capacity and illustrate the importance of using discriminative node attributes.
eeknowledgements. thank the Swiss National Science Foundation for supporting this work in the context of the project "Deep Learning for Craph-Sttuctured Data" (grant number P700P2 179981).
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Amir Abboud, Keren Censor-Hillel, and Seri Khoury. Near-linear lower bounds for distributed distance computations, even in sparse networks. In International Symposium on Distributed Computing, pp. 29-42. Springer, 2016.
Dana Angluin. Local and global properties in networks of processors (extended abstract). In Proceedings of the Twelfth Annual ACM Symposium on Theory of Computing, STOC '80, pp. 82-93, New York, NY, USA, 1980. ACM. ISBN 0-89771-017-6. doi: 10.1145/80014..80466 URL http:://oo. acm. 111.//0...1//0001.1.1111 804655
Vikraman Arvind, Johannes Köbler, Gaurav Rattan, and Oleg Verbitsky. On the power of color refinement. In International Symposium on Fundamentals of Computation Theory, pp. 339-350. Springer, 2015.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. 4502-4510 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.014 2018.
Rianne van den Berg, Thomas N Kipf, and Max Welling, Graph convolutional matrix completion. arXiv preprint 1rXiv:1706.022: 02263, 2017.
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Mincut pooling in graph neural networks. arXiv preprint arXiv: /907,009970044 2019.
Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and near-quadratic lower bounds for the congest model. arXiv preprint arXiv: 2017.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. arXiv preprint 19X.v:1905.12560 2019.
Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity. SIAM Journal on Computing, 17(2):30-261, 1988.
George Cybenko. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems, 2(4):303-314 1989.
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. arXiv preprint (007vv9977.0000000 2019.
Andrew Drucker, Fabian Kuhn, and Rotem Oshman. On the power of the congested clique model. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pp. 367-376.
ACM, 2014.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molccular fingerprints. In Advances in neural information processing systems, pp. 2224-2232, 2015.
Laurent Feuilloley and Pierre Fraigniaud. Survey of distributed decision. arXiv preprint arXiv: 1404.44444 2016.
Pierre Fraigniaud, Amos Korman, and David Peleg. Towards complexity theory for local distributed computing. Journal of the ACM (JACM), 60(5):35, 2013.
Silvio Frischknecht, Stephan Holzer, and Roger Wattenhofer. Networks cannot compute their diameter in sublinear time. In Proceedings of the twenty-thine annual ACM-SIAM symposium on Discrete Algorithms, pp. 1150-1163 Society for Industrial and Applied Mathematics, 2012.

---

Published as a conference paper at ICLR 2020
Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In International Symposium on Distributed Computing, pp. 1-15. Springer, 2013.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Vooninng-Voluee 70, pp. 1263-1272. JMLR. org, 2017.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359 -66,, 1989.
Elvin Isufi, Fernando Gama, and Alejandro Ribeiro. Edgenets:edge varying graph neural networks, 2020.
Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 1906.0/227, 2019.
Bala Kalyanasundaram and Georg Schintger. The probabilistic communication complexity of set intersection. SIAM Journal on Discrete Mathematics, 5(4):545-557, 1992.
Steven Kearnes, Kevin McCloskey, Mare Berndl, Vijay Pande, and Patrick Riley. Molecular graph convolutions: moving beyond fingerprints. Journal of computer-aided molecular design, 30(8): 595-608, 2016.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. arXiv preprint arXiv:1905.0490 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems, pp. 6348 6358, 2017.
Sandra Kiefer, Pascal Schweitzer, and Erkal Selman. Graphs identified by logics with counting. In International Symposium on Mathematical Foundations of Computer Science, pp. 319-330. Springer, 2015.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprini arXiv: (e09.666999977 2016.
Janne H Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast congest. In 2t International Conference on Principles of Distributed Systems (OPODIS 2017). Schloss Dagstuhl-Leibnniz-ZZettun fuer Informatik, 2018
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint
2015.
Zhuwen Li, Qifeng Chen, and Vladlen Koltun. Combinatorial optimization with graph convolutional networks and guided tree search. In Advances in Neural Information Processing Systems, pp- 539-548, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In International Conference on Learning Representations (ICLR), 2019.
Nathan Linial. Locality in distributed graph algorithms. SIAM Journal Computing, 21(1):193201, 1992.
Zhou Lu, Hongming Pu, Feicheng Wang, Zhigiang Hu, and Liwei Wang. The expressive power of neural networks: view from the width. In Guyon, U. V. Luxburg, S. Bengio, H. Wallach, Fer-
gus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems
30, pp. 6231-6239. Curran Associates, Inc., 2017. URL wtt.:http//// http::::///ppp..... nips cctpcppr//ppccccccccccccccee.e
www--the-expressieeepoooo www.iiieeepp-eeeeee www.p-owwoo-oooo neural www.wres-w-aaeee.....e oeee from- witth.
pdf
Sitao Luan, Mingde Zhao, Xiao Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-
scale deep graph convolutional networks. arXiv preprint arXiv: 1906.02 /74, 2019.
12

---

Published as a conference paper at ICLR 2020
Haggai Maron, Heli Ben-Hamu. Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. arXiv preprint 1rXiv:1905.11133 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. arXiv preprini arXiv: 190100931.9 2019b.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4602-4609, 2019.
Moni Naor and Larry J. Stockmeyer. What can be computed locally? In STOC, 1993.
J Pedro Neto, Hava Siegelmann, J Félix Costa, and CP Suárez Araujo. Turing universality of neural nets (revisited). In International Conference Computer Aided Systems Theory, pp. 361-366.
Springer, 1997.
D. Peleg. Distributed Computing: A Locality-Sensiiive Approuch. Society for Industrial and Applied Mathematics, 2000. doi: 10. (13/137/1.0 1980898719777..
Jorge Pérez, Javier Marinković, and Pablo Barcel6. On the turing completeness of modern neural network architectures. arXiv preprint arXiv: 19010049 2019.
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, (1(5):1235-11 2012.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, 2019.
Jochen Scidel. Anonymous distributed computing: computability, randomization and checkability. Phl) thesis, ETH Zurich, 2015.
Younjoo Seo, Andreas Loukas, and Nathanael Peraudin. Discriminative structural graph classification. arXiv preprint
2019.
Jukka Suomela. Survey of local algorithms. ACM Computing Surveys (CSUR), 45(2):24, 2013.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.008826. 2018.
A GRAPH THEORY DEFINITIONS
The main graph-theoretic terms encountered in this work are:
k-cycle detection: a k-cycle is a subraph of G consisting of k nodes, each with degree two. The k-cycle detection problem entails determining if G contains k-cycle.
Hamiltonian cycle: cycle of length n
(minimumn) spanning tree: a spanning tree is a tree subgraph of G consisting of n nodes. The minimum spanning tree problem entails finding the spanning tree of G' of minimum weight (the weight of a tree is equal to the sum of its edge weights).
(minimum) cut: cut is subgraph of G that when deleted leaves G disconnected. The minimum cut problem entails finding the cut of minimum weight (the weight of is equal the sum of its edge weights).
s-t cut: subgraph of G such that removing all subgraph edges from G' will leave the nodes and of G disconnected.
(shortest) path: a simple path is subgraph of G where all nodes have degree except from the two endpoint nodes whose degree is one. The shortest path problem entails finding the simple path of minimum weight that connects two given nodes (the weight of a path equal to the sum of its edge weights).
13

---

Published as a conference paper at ICLR 2020
(maximum) independent set: independent set is set of nodes in graph no two of which adjacent. The maximum independent set problem entails finding the independent set of maximum cardinality.
(minimumm) veriex to at least one node the set. The minimum vertex cover problem entails finding the vertex cover of minimum cardinality.
vertex cover of G is set of nodes such that each edge of G is incident
(perfect) coloring: coloring of G is a labeling of the nodes with distinct colors such that no two adjacent nodes are colored using same color. The perfect coloring problem entails finding coloring with the smallest number of colors.
diameter: the diameter dG of G equals the length of the longest shortest path.
girth: the girth of G equals the length of the shortest cycle. It is infinity if no eycles are present.
B DEFERRED PROOFS
B. PROOF OF THEOREM
The claim is proven by expressing the state of node i; in the two models in the same form, is not diffieult that for each layer of the GNN has
4 UPe Σ
miej)
(by definition)
MYENT
UPr Σ
MSGa (I! (f-1) (6-1)
Ug, aits)s)))
(2) (substituted mi+jj'
, Uks Uji
UyEA
= AGG (((1,) (1-1) (f-1) 3j Us Uy aits) uy E Nit)). (from (uu et al. 2018 Lemma 5))
where AGG, is an aggregation function, i.c., map from the set of multisets onto some vector space. In the last step, I used a result of Xu al. Xu et al. (2018) stating that each aggregation function can be decomposed as an dlement-wise function over each element of the multiset, followed by summation of all elements, and then final function.
Similarly, one may write:
ALG'
(((s (8-1) airs) vy E &Ni o:)
(by definition)
ALG ({(ALA (ALCÊ ( ((((1)),)))) ..)). aits) 0y E EN 2/-
(substituted 8
( Ui, Uj di-s) :y NN;))
(8-1)
ALG
with the last step following by restructuring the input and defining AL.G, the Turning machine that simulates the action of both ALGŽ and ALG.
Since one may encode any vector into string and vice versa, w.l.o.g. one may assume that the state of each node LOCAL is encoded as a vector H;. Then, to complete proof, one still needs to demonstrate that the functions
AGG (1 (2., Ty. vi, Vj, (ie-j) U. E and ALG ((az,, Us, Vj, aie-)) by E N
are equivalent (in the interest of brevity the layer/round indices have been dropped). If this holds then each layer of GNN is equivalent a round of LOCAL and the claim follows.
I first note that, since its input is a multiset, ALG, is also an aggregation function. To demon- strate equivalence, one thus needs to show that, despite not having identical inputs, each of the two aggregation functions can be used to replace the other. For the forward direction, it suffices to show that for every aggregation function AGG there exists ALG with the same output. Indeed, one may always construct ALG AGG g, where g takes as input {(Zj, Vi, Uj, di-z) 0ú E N, identifies 2; (by searching for vs U.) and appends to each element of the multiset yielding {(x,, Zz. Us. Uj, a(e-)) My E A The backward direction can also be proven with elementary construction: given ALG, one sets AGG = ALG o h, where h deletes 2; from each element of the multiset.
14

---

Published as a conference paper at ICLR 2020
B.2 PROOF OF COROLLARY 3.1
In the LOCAL model the reasoning is elementary (Linial| 1992 Fraigniaud et al. [0113] Seidel 2015): suppose that the graph is represented by set of edges and further consider that ALG; amounts to union operation. Then in d = ōg rounds, the state of each node will contain the entire graph. The function ALG; then be used to make the final computation. This argument also trivially holds for node/edge attributes. The universality of GNN mp then follows by the equivalence of LÓCAL and GNN mp
B.3 PROOF OF THEOREM 4.1
First note that, since the GNN and LOCAL models are equivalent, if no further memory/width restrictions are placed, an impossibility for one implies also an impossibility for the other. It can also be seen in Theorem 3.1 that there is a one to one mapping between the internal state of each node at each level between the two models (i.e., variables x; and s, As such, impossibility results that rely on restrictions w.r.t. state size (in terms of bits) also transfer between the models.
To proceed, I demonstrate that a depth lower bound in the CONGEST model (i.e., in the LOCAL model with bounded message size) also implies the existence of depth lower bound in the LOCAL model with bounded state size-with this result in place, the proof of the main claim follows directly. As in the statement of the theorem, one starts by assuming that P cannot be solved in less than d rounds when messages are bounded to be at most bits. Then, for the sake of contradiction, it supposed that there exists an algorithm A E LOCAL that can solve state of at most bits, but unbounded message size. argue that the existence of this algorithm also implies the existence of a second algorithm A' whose messages are bounded by c + log2 n. since each message $ sj=; is the output of a universal Turing machine ALG; that takes as input the tuple (s)"),) v:),, algorithm A' directly sends the input and relies on the universality of ALG to simulate the action of ALG The message size bound follows by adding the size of the state with that of representing the node id (log2 n bits suffice for unique node ids). This line of reasoning leads to contradiction when e S log2 n, as it implies that there exists an algorithm (namely A') that can solve P in less than d rounds while using messages of at most b bits. Hence, no algorithm whose state is less than b log, n bits can solve P in LOCAL, and the width of GNN mp has be least (b log2 n)/p.
less than rounds with a
C AN EXPLANATION OF THE LOWER BOUNDS FOR CYCLE DETECTION AND DIAMETER ESTIMATION
common technique for obtaining lower bounds in the CONGEST model is by reduction to the set- sel-disjointness problem in two-player communication complexity: Suppose that Alice and Bob are each given some secret string (s, and s₁) of q bits. The two players use the string to construct set by selecting the elements from the base set {1, .1.,....0. 4 for which the corresponding bit is one. It is known that Alice and Bob cannot determine whether their sets are disjoint or not without exchanging at least agg) bits (Kalyanasundaram & Schintger 1992 Chor & Goldreich 1988).
The reduction involves constructing a graph that partially known by each player. Usually, Alice and Bob start knowing half of the graph (red and green induced subgraphs in Figure 3 The players then use their secret string to control some aspect of their private topology (subgraphs annotated in dark gray). Let the resulting graph be G(sa, sb) and denote by cut the number of edges connecting the subgraphs controlled by Alice and Bob. To derive a lower bound for some problem P. one needs to prove that solution for P in G(s., sb) would also reveal whether the two sets are disjoint or not. Since each player can exchange at most O(b cut) bits per round, at least Q(g/ (b cut)) rounds are needed in total in CONGEST. By Theorem 4.1 one then obtains d = 2(g/ (w log cut)) depth lower bound for GNN mp-
The two examples in Figure illustrate the graphs G(s.. sp) giving rise to the lower bounds for even k-cycle detection and diameter estimation. To reduce occlusion, only subset of the edges are shown.
15

---

Published as a conference paper at ICLR 2020
Alice
Bob
Bob
(a) 10-cycle lower bound graph
(b) diameter lower bound graph
Figure 3: Examples of graphs giving rise to lower bounds.
(a) In the construction of Korhonen Rybicki (2018). each player starts from complete bipartite graph of p v nodes (nodes annotated in dark grey) with nodes numbered from to 2p. The nodes with the same id are connected yielding cut size 2p. Each player then uses its secret (there are many bits as bipartite edges) to decide which of the bipartite edges will be deleted (corresponding to zero bits). Remaining edges are substituted by a path of length k/2 1. This happens in way that ensures that G(Sa. 8b) contains a cycle length (half known by Alice and half by Bob) if and only if the two sets are disjoint: the cycle will pass through nodes f and p f of each player to signify that the 1-th bits of 8, and 8, are both one. It can then be shown that n = @(p²) from which follows that:
CONGEST requires least d [bg/(b- cut)) ((n/(b ((bpp)))))))))))))))) = -(Vvn/) bits to decide
if there is a cycle of length k; and GNND mp has to have the same.
folvn/Ce (w n)) depth to do
(b) In the construction of Abboud al. (2016), each string consists of q = M() bits. The strings are used to encode the connectivity of subgraphs annotated dark gray: an edge exists between the red nodes and q if and only if the i-th bit of is one (and similarly for green). Due to the graph construction, the cut between Alice and Bob has Ollog q) edges. Moreover, About al. proved that G(sa, sb) has diameter least five if and only if the sets defined by Sa and 8t are disjoint. This implies that d Q(nn/ log n)) depth necessary to compute the graph diameter in GNN mp
D THE COST OF ANONYMITY
There is striking difference between the power of anonymous networks and those in which nodes have the ability to uniquely identify each other, e.g., based on ids or discriminative attributes (see the survey by Suomela (2013)).
To illustrate this phenomenon, consider thought experiment where a node is tasked with recon- structing the graph topology in the LOCAL model. In the left, Figure 4 depicts the red node's 's knowledge after two rounds (equivalent to GNN mp having d = 2) when each node has a unique identifier (color). At the end of the first round, each node is aware of its neighbors and after two rounds the entire graph has been successfully reconstructed in red's memory.
In the right subtigure, nodes do not possess ids (as in the analysis of (Xu et al. 2018 Morris et al. 2019)) and thus cannot distinguish which their neighbors are themselves adjacent. As such, the red node cannot tell whether the graph contains eycles: after two rounds there least two plausible topologies that could explain its observations.
16

---

Published as a conference paper at ICLR 2020
knowledge
knowledge
knowledge
knowledge
(a) nodes can identify each other
(b) nodes cannot identify each other (WL test).
Figure Toy example of message exchange from the perspective of the node. The arrows show where each received message comes from and the message content is shown in light gray boxes. Red's 's knowledge of the graph topology is depicted at the bottom.
17


Reviews:
[{"review_id": "rkxbq22pYH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "Summary\n\nThis paper studied the expressive power of graph NNs, specifically, their universality and limitations under the non-anonymous setting, via the theory of distributed computations. For the universality, it proved the Turing completeness of graph NNs if messaging and aggregation functions are sufficiently strong. For the limitation, it characterized the lower bound of width for solving graph-theoretic tasks (such as subgraph detection, subgraph verification, approximate, and exact optimization problems) using graph NNs. The key idea is to reduce the computation model of graph NNs to LOCAL (for Turing completeness) or CONGEST (for limitations), which are well-studied in the literature of distributed computations and use the known results for these models.\n\n\nDecision\nThis paper gave us a new approach to analyzing the expressive power of graph NNs. Not only does this paper give new theoretical results, but also it opens the door to a new research direction by bridging the theories of graph NNs and distributed computations. However, I cannot confirm the correctness of the proof of Theorem 3.1 (see Suggestions section). For now, I am tending to accept the paper. But I want to determine the final decision after I am certain that the proof of the theorem is correct.\nWe can roughly divide existing approaches for studying the expressive power of graph NNs into two. One is to compare the power of discriminating non-isomorphic graph pairs with isomorphism tests such as the WL isomorphism test (Xu et al., 2019). The other one is to theoretically justify the oversmoothing phenomena (Li et al., 2018). The proof techniques the authors used are different from both of the two. It related a graph NN to the computational models LOCAL and CONGEST, and enabled to incorporate the theory of distributed computations. By doing so, the authors successfully derived many lower bounds in a systematic way, proving the effectiveness of their strategy. I think we can expect that a more refined analysis inspired by this approach will appear in the future.\n\nRegarding the Experience Assessment: I have published several papers in graph NNs (4). But I do not know much about the area of the theory of distributed algorithms (1--3).\n\n\nSuggestions\n\n- Section 3.2\n\t- Theorem 3.1 proves the equivalence of GNN_n and LOCAL. However, the definition of equivalence is missing. Please write it in the main part, since this theorem is the key result of this paper.\n\t- I could not find any reference for the Turing completeness of the LOCAL model. Could you add the reference for it?\n\t- The description of the CONGEST model is only available in the appendix informally (Appendix B.3). Could you write it in the main part?\n\t- The authors emphasized the importance of the universality and limitation results in the introduction and paragraph after Corollary 3.1. In my opinion, the importance of such tasks is in machine learning community (Cybenko's paper on the universality of MLPs (Cybenko, 1989) is one of the most cited papers in the community). Rather, I think many graph NN researchers who are expected to read this paper are not familiar with the theory of distributed computations. Therefore, I would recommend to use page resources to explain the basic concepts of the distributed computation theory.\n\n\nQuestions\n\n- Is there any existing work which tries to solve the graph theoretical tasks using graph NNs? If there is, can the theorems in this paper give explanations for the results?\n\n\n[Cybenko, 1989] Cybenko, George. Approximation by superpositions of a sigmoidal function. Mathematics of control, signals and systems 2.4 (1989): 303-314.\n[Li et al., 2018] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning. In Proceedings of the 32nd AAAI Conference on Artificial Intelli- gence, pp. 3538–3545, 2018.\n[Xu et al., 2019] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJxkAi7AFS", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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 studies theoretical properties of GNN in particular their expressive power. There are many recent works on this topic and the 2019 ICLR paper 'How Powerful are Graph Neural Networks?' is the closes related to this paper. In the 2019 paper connects GNN with the  Weisfeiler-Lehman graph isomorphism test in theoretical computer science. This paper makes a connection between GNN and the locality notion developed in distributed computing.\nThis connection is rather obvious and GNN being particular local algorithms, their expressive power is at least as limited as the expressive power of local algorithms. In this paper, results in distributed computing are reformulated in a GNN framework mapping the number of rounds required by a local algorithm to the depth of the GNN in order to solve a given graph problem in a worst case scenario.\nIn my opinion, this paper is rather incremental. In order to improve it, it would be nice to see experiments supporting the theoretical results in section 4. Here it is not clear at all if the bounds given are tight in practice.\n\n###\nThe authors added experiments supporting their theoretical results. I am upgrading my rating to weak accept.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJgvajA15r", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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 studies impossibility results of GNN in the worst-case sense. In particular, it reduces GNN to a distributed computing model CONGEST and adapt the impossibility result from distributed computing to GNNs. The impossibility results show that for certain problems, e.g., subgraph detection, there exists a graph such that GNN can not solve the problem unless the product of a GNN’s depth and width exceeds (a function of) the graph size.\n\nI am not an expert of distributed computing and I did not check all the proofs thoroughly. But I do think this paper provides a solid contribution to broaden the community’s understanding about what the limitations of GNNs are. Overall, I tend to accept it and would like to increase the score based on authors’ feedback.\n\nPros:\n\n1, I like the contribution of the paper which tries to build connections between GNNs and distributed computing models. From the perspective of computation, GNNs and distributed algorithms do share a lot of similarities. Therefore, some algorithm design choices in distributed computing would shed some light on designing novel GNNs. This may open a new direction for the community.\n\n2, The depth and width dependency results are novel in the context of GNNs.\n\nCons & Questions & Suggestions:\n\n1, Since these impossibility results for a certain subclass of GNNs are in the worst-case sense, it is not clear how it would be useful for practical machine learning problems. Some discussion along this line would be very helpful.\n\n2, It would be great to discuss the relationship between the Turing universality and the universality of function approximation studied in [1]. \n\n3, For people who have no background of distributed computing, it would be great to describe CONGEST before going to the impossibility results reduced from CONGEST to GNNs.\n\n4, I do not recommend authors to refer to the computation model 1 as GNN. You could name it as MPNN in order to make the claim more accurate. GNN in general has a few variants which does not fall into this category and could have higher capacity than MPNN. For example, the authors claim that “graph neural networks always sum received messages before any local computation”. However, this is not true in GraphSAGE [2] where the aggregation is a LSTM rather than a simple sum. It makes the model resemble more to the computational model 2. Recent spectral graph convolutional networks [3,4] leverages Krylov subspace methods to compute approximated eigenvalues and eigenvectors of the graph Laplacian which are further used to compute long-range propagation / high-power Laplacian to improve representation power. The results on depth may not hold for these models any more since one layer graph convolution could aggregate multi-hop information. Therefore, being more specific on the model class would make the conclusion more accurate. It would be great to discuss these models separately from the computation model 1.\n\n[1] Chen, Z., Villar, S., Chen, L. and Bruna, J., 2019. On the equivalence between graph isomorphism testing and function approximation with GNNs. arXiv preprint arXiv:1905.12560.\n[2] Hamilton, W., Ying, Z. and Leskovec, J., 2017. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (pp. 1024-1034).\n[3] Liao, R., Zhao, Z., Urtasun, R. and Zemel, R.S., 2019. Lanczosnet: Multi-scale deep graph convolutional networks. arXiv preprint arXiv:1901.01484.\n[4] Luan, S., Zhao, M., Chang, X.W. and Precup, D., 2019. Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks. arXiv preprint arXiv:1906.02174.\n\n======================================================================================================\n\nThe response from authors address most of my concerns. I improved the score.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "N/A", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a theoretical background for the expressive power of graph convolutional networks. The results are obviously useful, and the discussion went in the positive way. All reviewers recommend accepting, and I am with them.
Decision: Accept (Poster)