On Graph Neural Networks versus Graph-Augmented MLPs
Authors: Lei Chen
Zhengdao Chen
Joan Bruna
Venue: ICLR 2021 Poster (2021)
Keywords: Graph Neural Networks
expressive power
feature propagation
rooted graphs
attributed walks
community detection
depth separation

Abstract: From the perspectives of expressive power and learning, this work compares multi-layer Graph Neural Networks (GNNs) with a simplified alternative that we call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node features with certain multi-hop operators on the graph and then applies learnable node-wise functions. From the perspective of graph isomorphism testing, we show both theoretically and numerically that GA-MLPs with suitable operators can distinguish almost all non-isomorphic graphs, just like the Weisfeiler-Lehman (WL) test and GNNs. However, by viewing them as node-level functions and examining the equivalence classes they induce on rooted graphs, we prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count the number of attributed walks. We also demonstrate via community detection experiments that GA-MLPs can be limited by their choice of operator family, whereas GNNs have higher flexibility in learning.

Published as a conference paper at ICLR 2021
ON GRAPH NEURAL NETWORKS VERSUS GRAPH- AUGMENTED MLPs
Lei Chen', Zhengdao Chen' Courant Institute of Mathematical Sciences New York University, New York, NY (1c3909, ze1 21 (e12266)nyu.eee edu
Joan Bruna
Courant Institute of Mathematical Sciences
Center for Data Science
New York University, New York, NY bruna cims. nyu, edu
ABSTRACT
From the perspectives of expressive power and learning, this work compares multi-layer Graph Neural Networks (GNNs) with simplified alternative that we call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs)), which first aug- ments node features with certain multi-hop operators on the graph and then applies learnable node-wise functions. From the perspective of graph isomorphism test- ing, we show both theoretically and numerically that GA-MLPs with suitable op- erators can distinguish almost all non-isomorphic graphs, just like the Weisfeiler- Lehman (WI.) test and GNNs. However, by viewing them as node-level functions and examining the equivalence classes they induce rooted graphs, we prove a separation expressive power between GA-MLPs and GNNs that grows expo- nentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count the number of attributed walks. We also demonstrate via community detection exper- iments that GA-MLPs can be limited by their choice of operator family, whereas GNNs have higher flexibility in learning.
INTRODUCTION
While multi-layer Graph Neural Networks (GNNs) have gained popularity for their applications in various fields, recently authors have started to investigate what their true advantages over baselines are, and whether they can be simplified. On one hand, GNNs based allows the combination of information present at different nodes, and by increasing the depth of such GNNs, we increase the size of the receptive field. On the other hand, it has been pointed out that deep GNNs can suffer from issues including over-smoothing, exploding or vanishing gradients
biighborhooodaggreggatooo
in training as well bottleneck effects (Kipf & Welling 2016 Li al. 2018 Luan et al. 2019
Oono & Suzuki 2020 Rossi et al. 2020 Alon & Yahav 2020).
Recently, a series of models have attempted at relieving these issues of deep GNNs while retaining
their benefit of combining information across nodes, using the approach of firstly augmenting the node features by propagating the original node features through powers of graph operators such as the (normalized) adjacency matrix, and secondly applying node-wise function to the augmented node features, usually realized by Multi-Layer Perceptron (MLP) (Wu et al. 2019 NT & Maehara
2019 Chen al.) 2019a; Rossi et al. 2020). Because of the usage of graph operators for augment- ing the node features, we will refer to such models as Traph-Augmented MLPs (GA-MLPs). These models have achieved competitive performances
various tasks, and moreover enjoy better scala- bility since the augmented node features can be computed during preprocessing (Rossi et al. 2020 Thus, it becomes natural to ask what advantages GNNs have over GA-MLPs.
In this work, we ask whether GA-MLPs sacrifice expressive power compared to GNNs while gaining these advantages. A popular measure of the expressive power of GNNs is their ability distinguish non-isomorphic graphs (Hamilton et al. 2017 Xu et al. 2019 Morris et al.) 2019). In our work, besides studying the expressive power of GA-MLP from the viewpoint of graph isomorphism tests,
we propose a new perspective that better suits the setting of node preecttrdiction tasks: we analyze the
"Equal contributions. Code available at
chen201 10000018/GNNN 8/GNN_GNVVV L_______Aa_ GAMMLP

---

Published as a conference paper at ICLR 2021
expressive power of models including GNNs and GA-MLPs node-level functions, equiva- lently, as functions on rooted graphs. Under this perspective, we prove an exponential-in-eeeee gap between the expressive powers of GNNs and GA-MLPs. We illustrate this gap by finding broad family of user-friendly functions that can be provably approximated by GNNs but not GA-MLPs, based counting attributed walks the graph. Moreover, via the task of community detection, we show a lack of flexibility of GA-MLPs, compared to GNNs, to learn the best operators to use.
In summary, our main contributions are:
Finding graph pairs that several GA-MLPs cannot distinguish while GNNs can, but also proving there exist simple GA-MLPSs that distinguish almost all non-isomorphic graphs.
From the perspective of approximating node-level functions, proving an exponential gap between the expressive power of GNNs and GA-MIPs in terms the equivalence classes on rooted graphs that they induce.
Showing that the functions that count particular type of attributed walk among nodes can be approximated by GNNs but not GA-MLPs both in theory and numerically.
Through community detection tasks, demonstrating that GNNs have higher flexibility in learning than GA-MLPs due to the fixed choice of the operator family in the latter.
2 RELATED WORKS
Depth in GNNs Kipf & Welling (001)) observe that the performance of Graph Convolutional
Networks (GCNs) degrade as the depth grows too large, and the best performance achieved with 2 or 3 layers. Along the spectral perspective on GNNs (Bruna et al., 2013 Defferrard et al., 2016 Bronstein et al. 2017 NT & Maehara, 2019). Li et al. (2018) ) and Wu al. (2019) explain the failure of deep GCNs by the over-smoothing of the node features. Oono & Suzuki (2020) (2020) show an exponential loss of expressive power as the depth in GCNs increases the sense that the hidden node states tend to converge to Laplacian sub-eigenspaces as the depth increases to infinity. Alon & (2020) show an over-squashing effect of deep GNNs, in the sense that the width of the hidden states needs to grow exponentially in the depth in order to retain all information about long range interactions. In comparison, our work focuses on more general GNNs based on neighborhood- aggregation that are not limited in the hidden state widths, and demonstrates the their advantage in expressive power compared to GA-MLP models at finite depth, terms of distinguishing rooted graphs for node-prediction tasks. On the other hand, there exist examples of useful deep GNNs. Chen et al.] (2019b) apply 30-layer GNNs for community detection problems. which uses a family of multi-scale operators 2016). Recently. Li et al. (2019 (2000a) and Chen et al. (2020a) build deeper GCN architectures with the help of various residual connections (He al.J 2016) and normalization steps achieve impressive results in standard datasets, which further highlights the need to study the role of depth in GNNs. Gong et al.] (2020) propose geometrically principled connections, which improve upon vanilla residual connections graph- and mesh-based tasks.
well as normalization steps (loffe Szegedy 2015 Ulyanov et al.,
Existing GA-MLP-type models Motivated by better understanding GNNs as well as enhancing computational efficiency, several models of the GA-MLP type have been proposed and they achieve competitive performances on various datasets. Wu et al. (2019) propose the Simple Graph Con- volution (SGC), which removes the intermediary weights and nonlinearities in GCNs. Chen et al. (2019)) propose the Graph Feature Network (GFN), which further adds intermediary powers of the normalized adjacency matrix to the operator family and is applied to graph-prediction tasks, NT & Maehara (2019) propose the Graph Filter Neural Networks (gfNN), which enhances the SGC in the final MLP step. Rossi et al.) (2020) propose Scalable Inception Graph Neural Networks (SIGNs), which augments the operator family with Personalized -ww.lliizzzd---Pan---e PageRank-baase (Klicpera et al. 2018 2019
and triangle-based (Monti et al. 2018 Chen al.
2019b) adjacency matrices.
Expressive Power of GNNs Xu et al. (2019) and Morris et al. (2019) show that GNNs based on
bethhborhood-ggggegaale are no more powerful than the Weisfeiler-Lehmar (WL) test for graph isomorphism (Weisfeiler & Leman 1968), in the sense that these GNNs cannot distinguish between any pair of non-isomorphic graphs that the WL test cannot distinguish. They also propose models that match the expressive power of the WL test. Since then, many attempts have been made to build
2

---

Published as a conference paper at ICLR 2021
GNN models whose expressive power are not limited by WL (Morris al. 2019 Maron et al.
2019a
Chen et al., (011cc Morris & Mutzel, 2019 You et al. 2019; Bouritsas et al.
2020; Li et al,
2020b
Flam-Shepherd et al. 2020 Sato al. 2019; 2020). Other perspectives for understanding
the expressive power of GNNs include function approximation (Maron et al. 2019b Chen et al,,
2019c Keriven & P 2019), substructure counting (Chen al.
2020b) L Turing universality
[ooukas] (020) and the determination of graph properties (Garg et al. 2020). Sato (2020) provides
a survey on these topics. In this paper, besides studying the expressive power of GA-MLPs along
the line of graph isomorphism tests, we propose new perspective of approximating functions on
rooted graphs, which is motivated by node node-prediee pode-prediction tasks, and show a gap between GA-MLPs and
GNNs that grows exponentially in the size of the receptive field in terms of the equívalence classes that they induce on rooted graphs.
BACKGROUND
3.1 NOTATIONS
Let G = EV denote a graph, with V being the vertex set and E' being the edge set. Let n denote the number of nodes in G, Raxx denote the adjacency matrix, E Raxa denote the diagonal degree matrix with D;. = d; being the degree of node i. We call - the (symmetrically) normalized adjacency matrix, and A a generalized normalized adjacency matrix for any a E R. Let X E Raxd denote the matrix of node features, where X, denotes the d-dimensional feature that node i possesses. For node i V, let (()) denote the set of neighbors of i. We assume that the edges do not possess features. In a node prediction task, the labels are given by Y e R
For a positive integer K, we let [K] {1, -.., K). We use {.-))m to denote multiset, which allows repeated elements. We say a function f(K) is doubly-exponential in K log log fK) is polynomial in K, and poly-exponential in K if log f (K) is polynomial in K, as K tends infinity.
3.2 GRAPH NEURAL NETWORKS (GNNs)
Following the notations in Xu et al. (2019), we consider K K-layer GNNs defined generically as follows. For & E [K], we compute the hidden node states H E Rx iteratively as
M, (8)
AGGREGATE ((H)) :j (EN)),, H! COMBINE (K) (H, Mc(")), (1)
where we set (0) = XX to be the node features. If a graph-level output is desired, we finally let
ZG = READOOU((HH)))) (K) : V)),
(2)
Different choices of the trainable COMBINE, AGGREGATE and READOUT functions result in different GNN models, though usually AGGREGATE and READOUT are chosen to be permutation- invariant. As graph-level functions, it is shown in Xu et al. (2019) and Morris et al. (2019) that the maximal expressive power of models of this type coincides with running K iterations of the WL test for graph isomorphism, in the sense that any two non-isomorphic graphs that cannot be distinguished by the latter cannot be distinguished by the K- K-layer GNNs, either. For this reason, we will not distinguish between GNN and WL in discussions on expressive powers.
3.3 GRAPH-AUGMENTED MULTI-LAYER PECEPTRONS (GA-MLPS)
GA-MLPs are models that consist of two steps first augmenting the node features with some operators based on the graph topology, and then applying a node-wise learnable function. Below we focus on using linear graph operators to augment the node features, while an extension of the definition as well as some of the theoretical results in Section 5 to GA-MLPs using general graph operators is given in Appendix A Let Ω = (A). .... Wk (A)} S Rax" be set of (usually multi-hop) linear operators that are functions of the adjacency matrix, A. Common choices of the operators are powers of the (normalized) adjacency matrix, and several particular choices of S2 that give rise to existing GA-MLP models are listed in Appendix B computes series of augmented features via
In its general form, a GA-MLP first
Xx = (A) xX() Rxd
(3)
3

---

Published as a conference paper at ICLR 2021
10
10
11
02
13
11
14
Figure 1: A pair of graphs that can be distinguished by 2 iterations of the WL. test but not by GA-MIPs with Q E {AA:: &s E N.,. as proved in Appendix
with و R2 + Rd being learnable function acting feature transformation applied to each node separately, It can be realized by an MLP, e.g. (x() = (XX,, where a is nonlinear activation function and W1, W2 are trainable weight matrices of suitable dimensions. Next, the model concatenates X1, Xx into X
[X. E (=x(Kd), and computes
Z = p( E IRnd'
(4)
where p k2 + Rd is also learnable wise function, again usually realized by an MLP. If a graph-level output is desired, we can also add a READOUT function as in (2).
A simplified version of the model sets yp to be the identity function, in which case 3 and 44 written together as
can be
= p((w] (x(.),(((AA) X])
Such simplification improves computational efficiency since the matrix products wx. (A). X can be pre-computed before training (Rossi et al. 2020). Since we are mostly interested in an upper bounds on the expressive power of GA-MLPs, we will work with the more general update rule (3) this paper, but the lower-bourg result in Proposition crtoosttionrrmmiinn remains valid even when we restrict to the subset of models where yp is taken to be the identity function.
4 EXPRESSIVE POWER AS GRAPH ISOMORPHISM TESTS
We first study the expressive power of GA-MIPP via their ability to distinguish non-isomorphic graphs. It is not hard to see that when Ω = A, AKJ, where Á = D- for any a E R generalizes the normalized adjacency matrix, this is upper-bounded by the power of K + iterations of WL. We next ask whether it can fall strictly below. Indeed, for two common choices of Ω we can find concrete examples: 1) If 52 consists of integer powers of any normalized adjacency matrix of the form カ- AD= for some
[0. 1). then it is apparent that the GA-MLP cannot distinguish any pair of regular graphs with the same size but different node degrees; 2) If S2 consists of integer powers of the adjacency matrix, A, then the model cannot distinguish between the pair of graphs shown in Figure 1, which can be distinguished by 2 iterations of the WL test. The proof of the latter result given in Appendix K Together, we summarize the results as:
Proposition 1. If Ω C {Ā* E N}, with either = A or Ā = D- AD= for some [0, 1], there exists pair of graphs which can be distinguished by GNNs but not this GA-MLP.
Nonetheless, if we focus not particular counterexamples but rather the average performance in distinguishing random graphs, it is not hard for GA-MIPPs to reach the same level as WL, which is known distinguish almost all pairs of random graphs under uniform distribution (Babai et al., 1980). Specifically, building on the results in Babai et al. (1980), we prove in Appendix that:
Proposition 2. For all n E N4, 30,, > O such that any GA-MLP that has {D, (D,AD=*. S Ω can distinguish almost all pairs of non-isomorphic graphs of most nodes, in the sense that the fraction of graphs on which such GA-MLP fails to test isomorphism is o(1) as + oc.
The hypothesis that distinguishing non-isomonn non-isomorphic graphs is not difficult on average for either GNNs or GA-MLPs is further supported by the numerical results provided in Appendix C in which count the number of equivalence classes that either of them induce on graphs that occur in real- world datasets. This further raises the question of whether graph isomorphism tests along suffice as
4

---

Published as a conference paper at ICLR 2021
criterion for comparing the expressive power of models on graphs, which leads us to the explorations in the next section.
Lastly, we remark that with suitable choices of operators in Ω. it is possible for GA-MLPs to go beyond the power of WL. For example, if f2 contains the power graph adjacency matrix introduced in enChen et al. (011b)), min(A², 1). then the GA-MLP can distinguish between hexagon and a pair of triangles, which WL cannot distinguish.
5 EXPRESSIVE POWER AS FUNCTIONS ON ROOTED GRAPHS
To study the expressive power beyond graph isomorphism tests, we consider the setting of node- wise prediction tasks, for which the final readout step 2 is dropped in both GNNs and GA-MLPs. Whether the learning setup is transductive or inductive, we can consider the models as functions on rooted graphs, or egonets (Preciado & Jadbabaie 2010), which are graphs with one node designated as the root (i1,..., ) is a set of nodes in the graphs [G...., G. (not necessarily distinct) and with node-level labels (Y ...; Yr,} known during training, respectively, then the goal is to fit a function to the input-outpur pairs (Glf") Yr,,), where we use Gl to denote the rooted graph with G being the graph and the node in G being the root. Thus, we can evaluate the expressive power of GNNs and GA-MLPs by their ability to approximate functions on the space of rooted graphs, which we call E
To do so, we introduce a notion of induced equivalence relations on E, analogous to the equivalence relations on G introduced in Appendix C Given a family of functions FF on E, we can define an equivalence relation EFFF among all rooted graphs such that VGM G'i') E E, G ~EFF G'l(") if and only Vf E F. f(Gli) equivalence classes of rooted graphs, we can evaluate the relative expressive power of different families of functions on & in a quantitative way.
f(G'''). By examining the number and sizes of the induced
In the rest of this section, we assume that the node features belong to finite alphabet X' C N and all nodes have degree at most m E N... Firstly, GNNs are known to distinguish neighborhoods up to the rooted aggregation tree, which can be obtained by unrolling the neighborhood aggregation steps in the GNNs as well as the WL test (Xu et al. 2019 Morris et al. 2019) Garg et al.] 2020). The depth-K rooted aggregation tree of a rooted graph G a depth-K K rooted tree with a (possibly many-to-one) mapping from every node in the tree to some node in Glsl, where (i) the root of the tree is mapped to node i, and (ii) the children of every node in the tree are mapped to the neighbors of the node in Glf! to which j is mapped. An illustration of rooted graphs and rooted aggregation trees given in Figure Hence, each equivalence class in & induced by the family of all depth-K GNNs consists of all rooted graphs that share the same rooted aggregation tree of depth-K. Thus, to estimate the number of equivalence classes on E induced by GNNs, we need estimate the number of possible rooted aggregation trees, which is given by Lemma 3 in Appendix G Thus, we derive the following lower bound on the number of equivalence classes in E that depth-K GNNs induce:
Proposition 3. Assume that |x| 2 2 and 2 3. The total number of equivalence classes of rooted graphs induced by GNNs of depth K grows at least
in K.
In comparison, we next demonstrate that the equivalence classes induced by GA-MLPs are more coarsened. To see this, let's first consider the example where we take = (1, A, A 2 ...., A*) J. in which = D-a DD*AD AD-$ with any a, B E R is a generalization of the normalized adjacency matrix. From formula 3 by expanding the matrix product, we have
(A*+()));
Σ
d (a+8)
(a+ ( (Xxe)
(6)
where we define (G {( ix) CV Ar. An .... A > 0} to be set of all
walks of length & in the rooted graph GDI starting from node (an illustration is given in Figure 2 Thus, the kth augmented feature of node i, (X)), is completely determined by the number of each "type" of walks in Gl of length k. where the type of a walk, (i1...., (t..,..)), is determined jointly by the degree multiset, {di, ..., d,_,) as well as the degree and the node feature of the end node, d, and X;, Hence, to prove an upper bound on the total number of equivalence classes on E induced by such GA-MLP, it is sufficient to upper-bound the total number of possibilities of
5

---

Published as a conference paper at ICLR 2021
Figure 2: A pair of rooted graphs, GDJ (left) and G (right), in which blue nodes have node feature 0 and green nodes have node feature 1. They belong to the same equivalence class induced by any GA-MLP with operators that only depend the graph structure, but different equivalence classes induced by GNNs.
In particular, G and G E T2.2.(1.1.3) (defined in Appendix D. and (Ma(C (1, = 1 whereas [Ma(G* (L,1)) 0..
assigning the counts of all types of walks in a rooted graph. This allows us to derive the following result, which we prove in Appendix H
Proposition 4. Fix S = {T, A, A AK), where À = AD= for some o, 3 E R. Then the total number of equivalence classes in induced by such GA-MLPs is poly-exponential in K.
Compared with Proposition 3 this shows that the number of equivalence classes on & induced by such GA-MLPS is exponentially smaller than that by GNNs. In addition, as the other side of the same coin, these results also indicate the complexity of these hypothesis classes. Building on the results in Chen al. (2019c) 2020b) on the equivalence between distinguishing non-isomorphic graphs and approximating arbitrary
coomutatiooninvarian functions on graphs by neural networks, and by the definition of VC dimension (Vapnik & Chervonenkis) 1971. Mohri et al. 2018), we conclude that
Corollary 1. The VC dimension of all GNNs of K layers as functions on rooted graphs grows at least doubly-exponenttall in K; Fixing a. B3 E TR, the VC dimension of all GA-MLPs with f2 {I, A?, ..., A KK as functions on rooted graphs is at most roly-exponential K.
Meanwhile, for more general operators, we can show that the equivalence classes induced by GA- MLPs are coarser than those induced by GNNs least under some measurements. For instance, the pair of rooted graphs in Figure 2 bellnn to the same equivalence class induced by any GA-MLP (as we prove in Appendix ! but different equivalence classes induced by GNNs. Rigorously, we characterize such gap in expressive power by finding certain equivalence classes in È induced by GA-MIPS that intersect with many equivalence classes induced by GNNs. In particular, we have the following general result, which we prove in Appendix [
Proposition If Si is any family of equivariant linear operators on the graph that only depend on the graph topology of at most K hops, then there exist exponentially-in- K many equivalence classes in E induced by the GA-MLPs with St each of which intersects with doubly-exponentillyy
in-K many equivalence classes in E induced by depth-K K GNNs, assuming that [ > 2 and m 2 3. Conversely, in constrast, if i {I, A? ...,, AKJ, in which À = D-a AD-B with any a, B E R, then each equivalence class in E induced by depth-(K + 1) GNNs is contained in one equivalence class induced by the GA-MLPs with Ω
In essence, this result establishes that GA-MLP circuits can express fewer (exponentially fewer) functions than GNNs with equivalent receptive field. Taking a step further, we can find explicit functions on rooted graphs that can be approximated by GNNs but not GA-MLPs. In the framework that we have developed far, this occurs when the image of each equivalence class in & induced by GNNs under this function contains a single value, whereas the image of some equivalence class in & induced by GA-MLPs contains multiple values. Inspired by the proofs of the results above, natural candidate is the family of functions that count the number of walks of a particular type in the rooted graph. We can establish the following result, which we prove in Appendix[]
Proposition 6. For any sequence of node features {øx (zNN, C X. consider the sequence of func- tions (G == (G
xx)i] E. For all k E N4, the image under fir of every equivalence class in E induced by depth-k GNNs contains a single value, while for any GA-MLP using equivariant linear operators that only depend on the graph topology, there exist exponentially- in-k many equivalence classes in & induced by this GA-MLP whose image under Jkk contains exponentially-in -in-k many values.
In other words, there exist graph instances where the attributed-wan woaeeed-wwl--coouninn counting-functionn fa takes different values, yet GA-MLP model can predict them apart- and there are exponentially many

---

Published as a conference paper at ICLR 2021
Cora
Citeseer
Pubmed
Cora
RRG
Nodes
2708
3327
19717
Model
Train
Test
Train
Test
K
GNN
GA-MEP P
GNN
GA-MI P
GNN
GA-MLP
GIN
3.98F.6
9.72E-7
3.39F-5
2.61E.4
37
31
82
82
GA MLP.A
1.23E. 1
1.56E 1
1.75E.2
2.138.2
2
1589
756
984
306
8059
3762
1875-2
6.445-2
1.99:22
2.136-2
2158
12814
12014
MLP
4.22E-1
5.79E-1
1,02E-1
1.58E-1
2363
23559
2074
2019
12990
12979
GA-MLP-A
4.00E-1
5.79E-1
1.12-1
1.52B-
2365
2365
2122
2115
12998
12998
Table 1: The number of equivalence classes of rooted graphs induced by GNN and GA-MLP on node classification datasets with node features removed.
Table 2: MSE loss divided by label variance for counting attributed walks on the Cora graph and RRG. The models denoted as "+" contain twice as many powers of the operator.
of these instances the number of hops increases. This suggests the possibility of lower- boundigg the average approximation error for certain functions by GA-MLPs under various random graph families, which we leave for future work.
6 EXPERIMENTS
The baseline GA-MLP models consider has operator family Ω = Al. A for certain K, and we call it GA-MLP-A. In Section 6.2 and 6.3] we also consider GA-MLPs with & = AI)) A()) (A(e) is defined in Appendix B denoted GA-MLP-AA1)- For the experiments in Section 6.3 due the large K well as the analogy with spectral methods (Chen et al. 2019b),
we use instance normalization (Ulyanov et al., 2016). Further details are described in Appendix
6.1 NUMBER OF EQUIVALENCE CLASSES OF ROOTED GRAPHS
Motivated by Propositions 3 and we numerically count the number of equivalence classes in- duced by GNNs and GA-MLPs among the rooted graphs found in actual graphs with node features removed. For depth-K K GNNs, we implement a WL.-like process with hash functions to map the depth-K egonet associated with each node to string before comparing across nodes. For GA- MLP-A, we compare the augmented features of each egonet computed via (3). From the results in Table T. we see that indeed, the number of equivalence classes induced by GA-MLP-A is smaller
than that by GNNs, with the highest relative difference occurring at K = 2. The contrast is much more visible than their difference in the number of graph equivalence classes given in Appendix C
6.2 COUNTING ATTRIBUTED WALKS
Motivated by Proposition 6 we test the ability of GNNs and GA-MLPs to count the number of walks of a particular type in synthetic data. We take graphs from the Cora dataset (with node features removed) as well as generate a random regular graph (RRG) with 1000 nodes and the node degree being We assign node feature blue to all nodes with even index and node feature red to all nodes with odd index, due to which the node feature is given by 2-dimensional one-hot encoding. On the Cora graph, a node i's label is given by the number of walks of the type blue-sblue-bblee starting from On the RRG, the label is given by the number of walks of the type starting from i. The number of nodes for training and testing is split as 1000/1708 for the Cora graph and 300/700 7000 for the random regular graph. We test four GA-MLP models, two with many powers of the operator as the walk length and the other two with twice as many operators, and compare their performances against that of the Graph Isomorphism Network (GIN), a GNN model that achieves the expressive power of the WL test (Xu et al.) 2019). From Table 2 we see that GIN significantly outperforms GA-MLPs in both training and testing on both graphs, consistent with the theoretical result in Proposition 6 that GNNs can count attributed walks while GA-MLPs cannot. Thus, this points out an intuitive task that lies the gap of expressive power between GNNs and GA-MLPss
6.3 COMMUNITY DETECTION ON STOCHASTIC BLOCK MODELS (SBM)
We use the task of community detection illustrate another limitation of GA-MLP models: lack of flcxibility to lear the family of operators. SBM a random graph model in which nodes are partitioned into underfying communities and each edge is drawn independently with probability
7

---

Published as a conference paper at ICLR 2021
that only depends on whether the pair of nodes belong to the same community or not. The task of community detection is then to recover the community assignments from the connectivity pattern. We focus on binary (that is, having two underlying communities) SBM in the sparse regime, where it is known that the hardness of detecting communities is characterized by a signal-to-noise ratio (SNR) that is a function of the in-group and out-group connectivity (Abbe (017). We select pairs of in-group and out-group connectivity, resulting in 5 different hardness levels of the task.
Among all different approaches community detection, spectral methods are partieularly worth mentioning here, which usually aim at finding a certain eigenvector of certain operator that is correlated with the community assignment, such as the second largest eigenvector of the adjacency matrix or the second smallest eigenvector of the Laplacian matrix or the Bethe Hessian matrix (Krza-) kala et al. 2013). In particular, the Bethe Hessian matrix known to be asymptotically optimal in the hard regime, provided that a data-dependent parameter is known. Note that spectral methods bear close resemblance to GA-MLPs and GNNs. In particular, Chen et al. (2019b) propose a spec- tral GNN (sGNN) model for community detection that can be viewed as a learnable generalization of power iterations on a collection of operators. Further details on Bethe Hessian and sGNN are provided in Appendix D
We first compare two variants of GA- MLP models: GA-MLP-A with K = 120, and GA-MLP-H with Ω gen- erated from the Bethe Hessian ma- trix with the oracle data-dependent parameter also up K 120. From Figure 3 we see that the latter con- sistently outperforms the former, in- dicating the importance of the choice of the operators for GA-MI.Ps As re- ported in Appendix L replacing A by A(1) yields no improvement in per- formance. Meanwhile, we also test a variant of sGNN that is only based on powers of the A and has the same receptive field as GA-MLP-A (fur- ther details given in Appendix [L. We see that its performance is compara- ble to that of GA-MLP-IL HI. Thus, this demonstrates a scenario in which GA-MLP with common choices of 52 do not work well, but there exists some choice of Qi that is a priori unknown, with which GA-MLP can achieve good perfor- mance. In contrast, a GNN model does not need to rely on the knowledge of such an oracle set of operators, demonstrating its superior capability of learning.
XGNN GA-MLP-A GA MLP-
0.94 0.94 0.94
0.76
Overtap
0.40
0.42
0.21
0.22
0.25
0.18 0.16 0.17
Rank hardhess
Community detection on binary SBM with 5 choices of in- and out-group connectivities, each yielding to a different SNR. Higher overlap means better performance.
Figure 3:
CONCLUSIONS
We have studied the separation in terms of representation power between GNNs and a popular alter- native that we coined GA-MLPs. This latter family is appealing due to its computational scalability and its conceptual simplicity, whereby the role of topology is reduced to creating 'augmented' node features then fed into a generic MLP. Our results show that while GA-MLPs can distinguish almost all noniisomopphic graphs, in terms of approximating node-level functions, there exists a gap grow- between GA-MLPs and GNNs in terms of the number of equivalence
ing exponentially-in-dppi classes of nodes (or rooted graphs) they induce. Furthermore, we find a concrete class of functions that lie in this gap given by the counting of attributed walks. Moreover, through community detec- tion, we demonstrate the lack of GA-MLP's ability to go beyond the fixed family of operators as compared to GNNs. In other words, GNNs possess an inherent ability to discover topological fea- tures through learnt diffusion operators, while GA-MLPs are limited to a fixed family of diffusions.
While we do not attempt to provide decisive answer of whether GNNs GA-MLPs should be preferred in practice, our theoretical framework and concrete examples help to understand their differences in expressive power and indicate the types of tasks in which gap is more likely to
8

---

Published as a conference paper at ICLR 2021
be seen those exploiting stronger structures among nodes like counting attributed walks, those involving the learning graph operators. That said, our results are purely on the representation side, and disregard optimization considerations; integrating the possible optimization counterparts is an important direction of future improvement. Finally, another open question is to better understand the links between GA-MLPP and spectral methods, and how this can help learning diffusion operators.
ACKNOWLEDGEMENTS
We are grateful to Jiaxuan You for initiating the discussion on GA-MLP-type models, as well as Mufei Li, Minjie Wang, Xiang Song, Lingfan Yu, Michael M. Bronstein and Shunwang Gong for helpful conversations. This work is partially supported by the Alfred P. Sloan Foundation, NSF RI-1816753, NSF CAREER CIF 1845360, NSF CHS-1900091, Capital One, Samsung Electronics, and the Institute for Advanced Study.
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments, The Journal of Machine Learning Research, (8(1):644-65311 2017.
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05200 2020.
László Babai, Paul Erdos, and Stanley M Selkow. Random graph isomorphism. SlaM Journal on computing, 9(3):628-635, 1980.
Giorgos
Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.0922 09252, 2020.
M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: Going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42 2017.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally 2013.
connected networks on graphs. arXiv preprint
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. arXiv preprint 2Xiv:2007.02133, 2020a.
Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? a dissection graph classification. arXiv preprint arXiv:/905.0m 04599, 2019a.
Zhengdao Chen, Lisha Li, and Joan Bruna. Supervised community detection with line graph neural networks. Internation Conference on Learning Representations, 2019b.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pp. 18868-15877 2019c.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? arXiv preprint arXiv:2002.04005 2020b.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, pp.
2016.
Daniel She--Shepeerd, Tony Wu, Pascal Friederich, and Alan Aspuru-Guzik. Neural message pass- ing high order paths. arXiv preprint arXiv:2002.10413, 2020.
Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks, 2020.

---

Published as a conference paper at ICLR 2021
Shunwang Gong, Mehdi Bahri, Michael M Bronstein, and Stefanos Zafeiriou. Geometrically prin- cipled connections in graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11415-11424, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv:/502.03167, 2015.
Sergei Ivanov, Sergei Sviridov, and Evgeny Burnaev. Understanding isomorphism bias in graph data sets. arXiv preprint arXiv:1910. 12091, 2019.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems, pp. 7092-7101, 2019.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 1rXiv:160.002907, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In Advances in Neural Information Processing Systems, pp. 13354-13366, 2019.
Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. Spectral redemption clustering sparse networks. Proceedings of the National Academy of Sciences, 110652):20335-209M 2013.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint 077779,006.07739 2020a.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovee. Distance sesoding-desigeee provably more powerful gnns for structural representation learning. arXiv preprint arXiv:2009.00142, 2020b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for sepi-supervised learning. In Proceedings of the Thirly-Second AAAI Conference on Artificial telligence (AAAI-18), pp. 3538-3545 Association for the Advancement of Artificial Intelligence, 2018
Andreas Loukas. What graph neural networks cannot leam: depth vs width. In International Confer- ence on Learning Representations, 2020. URL htttps://openrev. net. forum?
B 12bp4wwS
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Advances in neural information processing systems, pp. 10945-10955, 2019.
Haggai Maron, Heli Ben-Hamu. Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2153-2164, 6 2019a.
10

---

Published as a conference paper at ICLR 2021
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. volume 97 Proceedings of Machine Learning Research, pp. 4363 4371, Long Beach, California, USA, 09-15 Jun 2019b. PMLR. URL http: http:://proceeiings mlrr press/
197/maron1 9a. ht.m
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. MIT press. 2018.
Foundations of machine learning.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: motif-based graph convolu- tional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp- 225 228. IEEE, 2018.
Christopher Morris and Petra Mutzel. Towards a practical k-dimensional weisfeiler-leman algo- rithm. arXiv preprint arXiv: /904.00494 2019.
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. Association for the Advancement of Artificial Intelligence, 2019.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXiv: 190..99550.0.... 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Victor M Preciado and Ali Jadbabaie. From local measurements to network spectral properties: Beyond degree distributions. In 49th IEEE Conference Decision and Control (CDC), pp- 2686-2691, IEEE, 2010.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Fed- erico Monti. Sign: Scalable inception graph neural networks. arXiv preprint 1rXiv:2004.11199 2020.
Alaa Saade, Florent Krzakala, and Lenka Zdeborová. Spectral clustering of graphs with the bethe hessian. Advances in Neural Information Processing Systems, pp. 406-414, 2014.
Ryoma Sato. A survey on the expressive power of graph neural networks. arXiv preprint arXiv:2003.04078 2020.
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.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprint arXhv:2002.03155, 2020.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing in- gredient for fast stylization. arXiv preprint arXiv:1607.0802. 2016.
V. N. Vapnik and A. Ya. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2):264-280, 1971. doi: 10.1137/11 16005.. htRLsstts::/ //ottps://o...... /dol. www.ooog./.00.... 1tt.:/1..1111/11 101////1110//1112....
B Weisfeiler and A Leman. The reduction of graph to canonical form and the algebra which appears therein. Nauchno-Tecah Technicheskaya Informatsia, 2(9): 12-16. 1968.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. volume 97 of Proceedings of Machine Learning Re- search, pp. 6861-6871, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL. http: //proceedings mlr www.sp/eee............. 9 wwwle..
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference Machine Learning, pp. 5453-5462, 2018.

---

Published as a conference paper at ICLR 2021
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International Conference on Machine Learning, pp. 7134-7143, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp. 3391- 3401, 2017.
12

---

Published as a conference paper at ICLR 2021
A GA-MLP WITH GENERAL EQUIVARIANT GRAPH OPERATORS FOR NODE FEATURE AUGMENTATION
For graph G (V, with nodes, assume without loss of generality that V [n]. Let S. denote the set of permutations n, and Vx E Sn, it maps a node i E [n] to (i) E [n]. For и E Sn and matrix M TRex,,
M R to denote the r-permuted version of M, that is, (IT * K) = Mx (()) For π E S, and a matrix Z E Raxd, we use π Z E Raxd to denote the π- r--pemuuted version of M, that is, (IT * Z i.p = (x)))
Below, we define more general form of GA-MLP models that extend the of equivariant linear operators for node feature propagation to that of general equivariant graph operators. We first define a map w R x Rxd > R "xx' whose first input argument is always the adjacency matrix of a graph, A, and second input argument to node permutations if VT E S., VZ E IR" 1xd there is w * A, 2) π A [A, Z). With a slight abuse of notations, we also use w ZZ) denote w(A, Z), thereby considering w[A] R Rexdd as an operator on node features. If satisfies equivariance to node permutations as defined above, we then call w w[A] equivariant graph operator. We can then define general (nonlinear)
node feature matrix. We say the map satisfies equivariance
GA-MLP model as
X = w[A[(X)
Z = p(X)
where w is equivariant graph operator, and is node-wise function.
easy to see that
Proposition 7. If [[] m(A) X, where m(-) x - R is an entry-wise function or matrix product or compositions thereof. then w[A] an equivariant graph operator.
A.1 EXTENDING THE PROOF OF PROPOSITION o TO GENERAL GA-MLPS
An extension of the first half of Proposition 5 is
Proposition 8. If [[[]] is an equivariant graph operator, then there exist exponentially-in- many equivalence classes in & induced by the general GA-MLPs with w[A), each of which intersects with -n many equivalence classes in E induced by depth-K K GNNs, assuming that | 2 2 and m 2
rooted trees of depth K, Km, K. that 5 giiven in Appendix we consider the set of full m--ay rooted trees of depth K in which the nodes have features belonging the discrete set X' C N and all non-leaf nodes have children. Tm.K,x x is subset of E, the space of all rooted graphs. Suppose f is a function represented by a general GA-MLP defined in (7) with equivariant graph operator w w(A] Let V2 denote the set of nodes depth of T. Notice the following symmetry among nodes in each VA:: if ı the permutation of a pair of nodes in some V, for k < K, then A A. By the equivariance property of w, this implies that
Proof:
Similar to the proof of Proposition
w[A[(T 2)
=w [T * A (IT 2)
(8)
= + w (A)
Let X denote the node feature matrix associated with T, and * T denote the rooted tree in Tm.K.N with the same topology (i.e., also a full m-ary rooted tree) but node feature matrix ग * X. Then, since the root node is not permuted under π, we know that
f(T) =p (X)
=P
(9)
=p (W] X)1.)
=s( TT)
This implies that for two trees T and T Tm. K,X, if 4O K, Vo X. they satisfy (T;+)) = (T))))) then S(T) S(T') for all such f's, and hence T and T" belong to
13

---

Published as a conference paper at ICLR 2021
the same equivalence class in & induced by GA-MLPs. Therefore, by the rest of the argument given in Proposition [] Proposition can be proven analogously for GA-MLPs with general equivariant graph operators.
Similarly, Proposition 6 can also be extended to Proposition 9. For any sequence of node features {ER) S X, consider the sequence of func- tions f == [Wi (x....,,.7)) on For all E N4, the image under I& of every equivalence class in & induced by depth-k GNNs contains single value, while for any GA-MLP using equivariant graph operators, there exist exponentially-ine many equivalence classes in induced by this GA-MLP whose image under fx contains exponentially iin- many values.
The proof replies on the same extension as described above in the proof of Proposition
B EXAMPLES OF EXISTING GA-MLP MODELS
For 6 E R, let A() A + cI, D()) be the diagonal matrix with Dig E, As + c, and A D 111/2 1 A() D.D.-11
Simple Graph Convolution (Wu et al. 2019:
(A) = { {{ for some K > 0. In addition, yp is the identity function and p(H) = softmar HW) for some trainable weight matrix W.
Graph Feature Network (Chen et al. 2019a):
?(A) {1, D, Acc).... (A()) for some K >> and >> 0. In addition, y is the identity function and p is an MLP.
Scalable Inception Graph Networks (Rossi et 2020
(2(4) = { U Q2 (A) U (2) ) U (lz(A)) where (A) A) is family of simple / normal- adjacency matrices, and (A) is family of triangle-based adjacency matrices. In addition, writing (a>([X, W Xx W W)) ou). with σд and 02 being nonlinear activation functions and W1,... WK and out being trainable weight matrices of suitable dimensions.
ized adjacency matrices, l22 (A) ) is a family of Personalized-Paggll
X = - ..... Xx). there is 2 = p(X)
C EQUIVALENCE CLASSES INDUCED BY GNNS AND GA-MLPS AMONG REAL GRAPHS
IMDBBINARY
IMDBMULTI
REDDITBINARY
REDDITMULTISK
COLLAB
# Graphs
1000
1500
2000
5000
5000
K
GNN
GA-MLP
GNN
GA-MLP
GNN
GA-MLP
GNN
GA-MLP
GNN
GA-MLP
51
51
49
49
781
781
1365
1365
294
294
537
537
387
387
1998
1998
4999
4999
4080
4080
537
387
387
1998
1998
4999
4999
4080
4080
ground truhh
537
4999
4080
The number of equivalence classes of graphs induced by GNN and GA-MLP on real datasets with node features removed. The last row gives the ground-truth number of isomorphism classes of graphs computed from the implementation of Ivanov et al. (2019).
Table 3:
Given a space of graphs, G, and a family F of functions mapping G to R. F induces an equivalence relation that denote by RG.F among graphs in G such that for Gr,G2 G. G1 "9FF G2 and only if Vf E F, f(G,) = f(G2). For example, if F is powerful enough to distinguish all pairs of non-isomorphic graphs, then each equivalence class under =g.5 contains exactly one graph. Thus, by examining the number or sizes of the equivalence classes induced by different families of functions on G. we evaluate their relative expressive power in quantitative way.
Hence, we supplement the theoretical result of Proposition 2 with the following numerical results on five real-world datasets for graph-predictions. For graphs in each of the two real datasets,
14

---

Published as a conference paper at ICLR 2021
remove their node features and count the total number of equivalence classes among them induced by depth-K K GNNs (equivalent to K K-iterations of the WL test, as discussed in Section 3.2) as well as GA-MLPs with Q {I, A, .... AK] for different K's. We see from the results in Table that as soon as K 2 2, the number of equivalence classes induced by GNNs and the GA-MLPs are both close the total number of graphs up isomorphism, implying that they indeed both able distinguish almost all pairs of non-isomorphic graphs among the ones occurring in these datasets.
D ADDITIONAL NOTATIONS
For any & E N4, and any rooted graph G (V, B,i) &, define
Wo(GG = {(i,, ... SV. Ai.,, Ain Aiz- > 0}
(10)
- in) E (e((!!)): i2 i1 + i3, 3 # 1,-1, $ ig]
(11)
as the sets of walks and non non-backtracking walks of length &o in Gldl starting from the root node, respectively. Note that when G a rooted tree, non-backtracking walk of length k is path from the root node node depth k. In addition, for 0 d1,- ...,.., dr. S and 2ı, my In E X, define the following subsets of (e
We (a (di, dx), mx) (()),..,;))) Wa(!!!) !di die Jm = .d.,..., da X., 2x
(12)
We (Z), xx)) (8.1...., Wa(!! (Ki,. Xix) (I11
(13)
(x(G4)22)) = {(11,.., (x) E Wa Xix = =kk We also define Wi (Gbl) (d1, dx),, mx). We (Gli); (k.),),,,,,)) and W&(Gll similarly.
(14)
E ILLUSTRATION OF ROOTED GRAPHS AND ROOTED AGGREGATION TREES
Figure 4: An illustration of rooted graphs and rooted aggregation trees. Left: a pair of graphs, G and G'. Center: the rooted graphs of 1 in G and G', G(" and !r Right: the rooted aggregation tree that both G!Ul and (1)1) correspond to.
F PROOF OF PROPOSITION 2
With node features being identical in the random graphs, we take X E [Rax1 to be the all-] vector. Thus,
(DX); d;
(15)
15

---

Published as a conference paper at ICLR 2021
and
X); = Σ dy"
(16)
JEN(()
Since 44) and 2 together can approximate arbitrary permutation invariant functions on multisets
Zaheer et al. 2017). if two graphs G = (V. and G' = (V', , EE' cannot be distinguished by the
GA-MLP with operator family & that includes (D,AD- under any choice of its parameters,
means that the two multisets {dd,, Ejev(y) d, : Jm {(dy, Even(yy dz") : E V') Jm.
and therefore both of the following hold:
(d: V) =dy V')
(17)
Σ d7" :E V =f Σ EV JEN())
(18)
('EN())
To see what this means, we need the two following lemmas.
Lemma 1. Let Sn be the set of all multisets consisting of at most elements, all of which are integers between 0 and n. Consider the function ha(S) = u defined for multisets S. If
log n log log(n-1) m- TT ha is an injective function on Sn.
Proof of Lemma 7 For ha to be injective on Sn, it suffices to require that AI S n 1, n + 1)-a, for which it is sufficient to require that (n 1) > -+1 or
there is 1 >
log n
log log--lo((n- log(n-1)
Lemma 2 (Babii al. (1980), Theorem 1). Consider the space of graphs with vertices, Gn- There is a subset Kn C Gn that contains almost all such graphs (i.e. the fraction converges to 1 as + c)) such that the following algorithm yields a unique identifier for every graph G (V, E) E Knn
Algorithm 1: Set [3 log n/ log and let d(G) be the degree of the node in V with the rth
largest degree; For each node i in G, define the multiset 7 = {dg : E N()), dj > d(G))mi Finally define a multiset associated with G. F(G) to : : Jm. which the output of the algorithm.
In other words, VG,G' Knn G and G' are isomorphic if and only if P(G) P(G') as multisets. In particular, we can choose Kn, such that the top node degrees of every graph in Kr, are distinct.
Based on these lemmas, we will show that when a > lng
logg-nn and for G, G' E Kn, (17) and
18 together imply that G is isomorphic to G'. To see this, suppose that 17 and (18) hold. Because of 17) we know that G and G' share the same degree sequence, and hence d(G) = d(G"). Because of 18 we know that there is a bijective map from V to V such that Vi V.
Ed Σ d,",
(19)
JEN()
(EE(2)
which, by Lemma I implies that {dy j E N(1) {dg j N(())) We then have %
{dy j E NN(i) mm {d, [d [ n (d(G), (dy: (('))) n (d(G"), oc) = 7y.
and therefore F(G) F(G"), which implies that and G' are isomorphic by Lemma 2 This shows contradiction. Therefore, if G, Knn not isomorphic, then it cannot be the case that both (17) and (18) hold, and hence there exists a choice of parameters for the GA-MLP with {D, AD C Ω that makes it return different outputs when applied to G and G'. This proves Proposition
G PROOF OF PROPOSITION 3
As argued in the main text, to estimate the number of equivalence classes on E induced by GNNs, we need to estimate the number of possible rooted aggregation trees. In particular, to lower-bound the number of equivalence classes on induced by GNNs, we only need to focus on a subset of all possible rooted aggregation trees, namely those in which every node has exactly children. Letting TA K. denote the set of all rooted aggregation trees of depth K in which each non-leaf node has degree exactly m and the node features belong X, we will first prove the following lemma:
16

---

Published as a conference paper at ICLR 2021
Lemma 3. 1f 2 2, then k,, 2 (m 1)(2*
Note that a rooted aggregation tree needs to satisfy the constraint that each of its node must have its parent's 's feature equal one of its children's feature, and so this lower bound is not as straight- forward to prove as power-bounding the total number of rooted subtrees. As argued above, this will allow us to derive Proposition
Proof of Lemma 3 Define B == {0, 1}. Since | 2 2, we assume without loss of generality that B _ X. To prove a lower-bound on the cardinality of Tm, K, it suffices to restrict our attention to its subset, Tm := Tm,,, K. where all nodes have feature either or 1. Furthermore, it is sufficient to restrict attention to the subset of T which contain all 2 possible types of paths of length K from the root to the leaves. Formally, with W. defined as in Appendix D we let
TA m.K = (T E Tm, V2,,,.,, JK E B, (x 2k)
(20)
and it is sufficient to prove lower bound on the cardinality of T k. K. Define Px. {(11, 2x))
Ti, mny Thk E B) be the set of all binary k-tuples. By the definition of (20). we know that V7 Pk, (WK((;;) 2 1. This means that Vr E Px, there exists at least one Ieaf node in T such that the path from the root node to this node consists of sequence of nodes with features exactly as given by T. We call any such node a node under T.
We show such a lower bound on the cardinality of TAA, inductively. For the base case, we know that TA, consists of all binary-featured depth-1 rooted trees with least 1 leaf node of feature and leaf node of feature 1, and hence T.A., 2(m 1). Next, we consider the inductive step. For every K and every T T we can generate rooted aggregation trees belonging to T E F K by assigning children of feature 0 or 1 to the leaf nodes of T. First note that, from two non-isomorphic we obtain non-isomorphic rooted aggregation trees in TA K+ in this way. Moreover, as we will show next, for every E TTA Tm, we can nower-bound the number of distinct rooted aggregation trees belonging T k obtained from T in this way.
mm..+
rooted aggregation trees T and T E T k.
There are many choices to assign the children. To get a lower-bound on the cardinality of T m,K ++- only need consider subset of these choices of assignments, namely, those that assign the same number of children with feature 0 to every node under the same 7 E PK- Thus, we let ςK+ I.r denote the number of children of feature assigned to every node in т. Due to the constraint that each node in the rooted aggregation tree must have its parent's 's feature equal to one of its children's 's feature, not all choices of (ik-I.-)TPp lead to legitimate rooted aggregation trees. Nonetheless, when restricting to the choices where Vr E Px. 1 S @K+ S - 1, we see that every leaf node of T gets assigned at least one child of feature 0 and another child of feature 1, thereby satisfying the constraint above whether its parent has feature 0 1. Moreover, for such choices, the rooted aggregation tree of depth K +1 obtained this way contains all 2 +1 possible paths of length +1, and therefore belongs to TAAK+1 -1- Hence, it remains to show a lower bound on how many distinct be obtained in this way from each T. Since for T, E PH such that * r',
trees in A m+ node under t is distinguishable from node under 7', we see that every legitimate choice of the tuple of 2 integers, (ọK+1.* +rer) leads to a distinct rooted aggregation tree of depth K + 1, and there are (m 1)2* of these choices. Hence, we have derived that [T 7 2 (m 1)2* I kl and therefore iT,A Kl (m 1 (m -1
17

---

Published as a conference paper at ICLR 2021
H PROOF OF PROPOSITION
According to the formula (3),
by expanding the matrix product, we have
(X())
Σ
d (a+
...d d x(x.))
(a+
ix-1
JeJ.
dj
Σ
Σ (idi
(d...d=-))(att0) dup(())
ddndde-im dk,z
=d
E
(1d)..d--1)- dep(z)) |Wa(G
( (di,
(ds mnn de-d
de
(21)
with (e (di,-.., dr mym x) defined in Appendix D Hence, for two different nodes i in G and &' in G' (G and G' can be the same graph), the node-wise outputs of and y' will be identical if the rooted graphs G and Gyll") satisfy
the GA-MLP (a {di,.., de-1 Jm de, x) = Wa(Gr ;dd,..., ..........dd. d dz,x) .) for every combination of choices the multiset (di,.n d the integer dj and the node feature under the constraints of di....de de S m and x X. Note that there are at most (K-=-?) S (A: + m m-m1 possible choices of the multiset (d1,..., d m choices of dy and | choices of x. thereby allowing at most [m + m 2)T 1 possible choices. Because of the constraint
Σ
[WicG (di,..., de 1mmm de. x) (W&(Gll)) S m
(22)
{d Jm.
de J
We see that the total number of equivalence classes on & induced by such GA-MLP is upper- +
bounded by (x1m((---2))--1 -1,, which is on the order 0(m*") with i growing and m bounded. Finally, since the total number of equivalence classes induced by multiple operators can be upper-bounded by the product of the number of equivalence classes induced by each operator separately, we derive the proposition as desired.
I PROOF OF PROPOSITION 5
Consider the set of full m-ary rooted trees of depth K, Tm. that is all rooted trees of depth K which the nodes have features belonging to the discrete set X C N and all non-leaf nodes have m children. Km, is subset of ε, the space of all rooted graphs. If f is function represented by GA-MLP using operators at most K- K-hop, then for Km,K.X' we can write
S(T) = Σ agx,),
(23)
JEV
where we denote the node set of T by V and the vectors aj 's depend only on the topological re- lationship between j and the root node. Let Va denote the set of nodes at depth & of T. By the assumption that the operators depend only the graph topology, and thanks to the topological symmetry of such full m-ary trees among all nodes on the same depth, we have that and Vj.j' E Vg. there is aj a' =: a(k)- Thus, we can write
S K
f(T) =pl Σ
Σ anj)(()))
OSKCK JEV.
(24)
=p( Σ
Σ
a.J, (T(T)=))
OSRCK ZEX
for some other set of coefficients āvy. 's, and where W, (T; x) is defined in Appendix D In other words, for trees T and E K,, if vO I k < K,Yr X. they satisfy
18

---

Published as a conference paper at ICLR 2021
(T; = [T) then f(T) f(T)) for all such f's, and hence T and T" belong to the same equivalence class in & induced by GA-MLPs. Thus, for a certain subset of these equiv- alence classes, we can lower-bound the number of equivalence classes in & induced by GNNs that the number of distinct trees in Km, that they contain, because GNNs are able to distinguish non-isomorphic rooted subtrees. In particular, a lower-bound is sufficient, we restrict attention to the subset of those trees with node features either 0 or 1, that is, trees belonging to Tm.K= == Tm.K,B. K,B, with B 10.
they intersect by lower-bounding
In rooted tree T. (T;; x) gives the total number of nodes with feature æ at depth k. For integers qo. Q1...., 9x such that 0 S 9k S m² vk - K. define
Tm, (..... = {T E Tm.K : V S K. (T:(T:)) = 7
(25)
(T) (and therefore are given by the tuple (go, f1y.-., 9x) From the argument above, all trees in the same Tm, (9x..)) belong to the same equivalence class in & induced by GA-MLPs. On the other hand, every pair of non-isomorphic trees belong to different equivalence class in & in- duced by GNNs. Thus, to show Proposition 5 it is sufficient to find sufficiently many choices of (qu, Q1- ..., 9K) such that Tm. (90-01 contains sufficiently many non-isomorppic trees. Specif- ically, we will show the following:
that is, the subset of trees whose per-level-node-comme { (T(;;=)))s<sKee
Lemma 4. For all integers qo, Uı,... .., QK such that V2 S Ks S K,
1
-h2hh2 S qb S
2 m
(26)
there is
ITm, K.g.K.99............
22
(27)
Proof of Lemma 4.
To prove such a lower bound on the cardinality of Tm, (.......)........))))) it is suffi- cient to prove lower bound the cardinality of its subset,
Tm,KK 1..90-91....... {T' (mo.K(009
VT a.. JK E B, W (T; (21, IK)) 2 1}
(28)
similar construction is involved in the proof of Lemma 3 in Appendix G Then, we will prove this lemma by induction on K. For the base cases, it is obvious that [mm. (Tm.. = and
(Tm.1.00.0)] = 1Tm,, = [mm.,.(0022) = 17m,,,(1.00| = 17,)1,(2.1)) = 17m,1.(1.2)) = 1. We next prove the inductive hypothesis that, for K and when go. 21,....... 9K satisfying (26). there
ITm, (g0. 9x) 2 2²"=² IT - (..
(9)
we can generate enough number of depth-K trees in T (g0 by appending children to the leaf nodes of T. Since any two depth-K trees generated from two non-isomorphic depth-(K 1) trees in this way non- isomorphic, this will allow us lower-bound the total number of trees in T Tm.K.(go.p) (g...............
To see this, we will next show that VT E Tmm.K-1.(qo...........
Consider the set of binary k-tuples, Pk {(I1,,.., FR. Ii, J' E B}. of cardinality 2t. As we know that VT E PK-1- PK-1.|WK- (W:-(T:77) 2 1. This means that Vr E Pk. there exists at least one leaf node in 7 such that the path from the root node to this node consists of sequence of nodes with features given by r. We call any such node node under T. The total number of the children of all nodes under 7 is thus m-
T Tm, (............
Z m. Thus, the total num- ber of children with feature 0 of all nodes under 7 is bounded between 0 and m- versely, for any 2 -uppe of non-negative integers, (ūK,r)rEPz 1. which satisfy VT E PK-
Con-
ỤK.r < m- (W=+(TT;)) - 1 can be "realized" by at least some depth-K K tree T" obtained by ap- pending children to the leaf nodes of T, in the sense that VT (I), ... IK-1) PK-1- there is WK(T'; (11, (IF1,.., "K1, 0)) ūK.r and W K (T"; (#1, #K-1, 1)) m W WK=i(T;>)] TK. and hence T" E "mm,K.on.....p 1.0))) with ēK- = ETeP TK.r. Because of the requirement that S "KKT 5 m- <m- [K=1(T;T) - 1, we further have that VT' E PK. (T( 2 1, which implies that T" E Tm..K. 9x ((x)) Therefore, for some fixed qK, in order to lower-bound the cardinal- ity of T Tm. by that of T -n, 1//00 10/_oo....00000 1x-1)) it is sufficient to show lower bound (which
19

---

Published as a conference paper at ICLR 2021
is uniform for all T Tm, satisfy
the number of 2 ltuplessss (EP which
9K Σ QK,7
TEPR-1
(30)
v7 E PK-1, Sqk,r S m. [
A simple bound can be obtained in the following way. For every such T, we sort the 2 -tuples in Pk-1 in ascending order of (W--1(T:-)l, and define P to be the subset of the first 2 of these elements according to this order. Thus, for example, Vr E P'K-1,7, VT' E PK-1 \ PKKI1TT there (T;-) S [Wk-I(T;7') As a consequence, we have ExEPk (T=]((T:) I ExEPR-NPk.n. [W I ! [Wx-((T;T]
and ErEPk_Id (K-1(T;T) EPEPK-IPK-IL. (T=)((
m S
Lemma 5. Let K 2 2 and qK satisfy 26 Then for all choices of the 2 -uppe of integers,
(TK.)) 1xx' such that VT E -, Qk. 1 or we can complete into at least one 2k -tupl of integers, (āK,-)rEPx-.) which satisfy 30
Proof of Lemma 5 For any such 2 2
30 it is sufficient to find another k integers, (ọK, K-1T" in order satisfy the constraints of
PPPK-XPPP 15 which satisfy
Σ
[K,t =KK -
Σ
QK,r
(31)
TEPx-1 1P K-17T
TEP K
11TTT
V PK-1
P P-,,,
S9K, S (T:i(T:T) -1
(32)
On one hand, since qx,= = 1 or 2, VT E -' there is 9x - 2- 9 - -Erer qK,r S
qK 2k-2 On the other hand, with the only other constraint being (32). it is possible find ((K.r)rEPr-1\PK..1 such that ErePk-NPPx-s. equals any integer between 2k-2
and m ErEPk-IlP--. (K:](T;+) 2K-2, and hence any integer between 2K-2 and m fmm K-1 2k- fmm K 2 Hence, as long as 2 - 2K SK S f which the assumption of (26) Lemma holds true.
least 2²--2 distinct choices of 2 tuples (9K,7)) that satisfy the constraint of (30). and hence at least 22"-2 non- isomorphic trees in Tm. Tm.K.(qu.91.. (q0.K.(00991....999 (00.91....9K-..00 obtained by appending children to the leaf nodes of T. This proves the inductive hypothesis. Hence, we have
Lemma implies that VT Tm, Tm,,K-1,(90.1a.. 119 1)+ there
K
Imm, (6o...()).
II
2
2 22k-1-1
(33)
k=2
which implies Lemma
Since m 2 by assumption, f - (2k 2k-2) grows exponentially in K. This proves Propo- sition
J PROOF OF PROPOSITION 6
Since the number of walks of a particular type that has length at most completely determined by the rooted aggregation tree structure of depth & it is straightforward to see that all egonets in the same equivalence class induced by iterations of WL (and therefore GNNs of depth k),, which yield the same rooted aggregation tree, will get mapped to the same value by fk-
20

---

Published as a conference paper at ICLR 2021
10
11
12
Figure 5: A pair of graphs with identical node features, G (left) and G' (right), which can be distin- guished by 2 iterations of the WL test but not by the GA-MIP with Q {A* )
For the second part of the claim pertaining to GA-MLPs, we assume for simplicity that X = =
{0. 1), as the extension the general case is straightforward but demanding heavier notations. Following the strategy in the proof of Proposition 5J it is sufficient to find exponentially-in-.. many choices of the tuple (go, 41.-..9uk) qx). with 0 S O% m² such that the image of Tm,,k (n.. (as defined in (25h) under fa contains exponentially-nn many values.
To make simpler refer different nodes in the tree, we index each node in a rooted tree by tuple of natural numbers: for example, the index-tuple [1, 2] refers to the node at depth 3 that is the second children of the third children of the first children of the root. Since there no intrinsic ordering to different children of the same node, there exist multiple ways of consistently indexing the nodes in a rooted tree. However, to specify a tree, suffices to specify the node features of all nodes under one such way of indexing.
Given T1. Th B, we consider set of depth-k full m-ary trees that satisfy the following: Vk' S k- 1 and 4,..., Iw E [m=) Fa.i.a.....g
if 1 1 and -P if 11 > 1. Note that these trees satisfy, for k < k - 1, qke = m k-K1 if Ig. = and que = (m 1)m k' -1 if xx 1. Thus, V12, la E [m]. the node [1,12, ..., 4x] is under the path
(21...., Ix) ) if and only if [[I.la.....N]] = Tg. whereas for 1 > 1, the node [1, (2.,2,..,,44 is not under the path regardless of the feature of 11, de]. Therefore, (G(t)) = [Wa [Wld;
axx)) equals the number of node of feature 2& among the set of m nodes, {11 ..., (e(m)) Hence, if for k' S k we set qK- m if Tu. = 0 and ga = (m 1)m*'= -1 if IM = 1, then choosing any 9 between = and (m --1 we have that for every integer between and m= there exists a tree T in T (mg...( such that (T) equals this integer. Since there are (m 2mm choices of qk (and therefore the tuple (go, ..., )))) and =-1 + 1 values in the image of (qo... under st. this proves the proposition.
K PROOF OF PROPOSITION 1
We will first prove that the pair of graphs cannot distinguished by any GA-MLP with Ω C ] Let X and A, X" and A' be the node feature vector and adjacency matrix of the two graphs, G and G', respectively. As these two graphs both contain 14 nodes that have identical features, we have X, X' IR 14141 both being the all-1 vector. Moreover, Vi E [14].
=x)==w<()) ((A))(X))) = (i)
(34)
where we use (i) and w(((1) denote the numbers of walks (allowing backtracking) of length A starting from node in graphs G and G', respectively. Thus, to show that any GA-MLP with
C [A*) keN necessarily returns the same output on G and G", it is sufficient to show that Vk
N. A = (X'), and therefore sufficient show that vk N and Vi [14]. there is ww (i)
w/. (i). In fact, we will prove the following lemma:
21

---

Published as a conference paper at ICLR 2021
Lemma 6. vk N,
(x (1), Vi E [14]
(35)
(x w (2)
(36)
wh (3) + wx (9) w (6) + wb (8)
(37)
w& (5) + (7) =w (4) + wk (10)
(38)
Proof of Lemma 6 We prove this lemma by induction. For the base case, we have that wo({)
(1), Vi E [14]. Next, assume that (35
38 hold for some k E N and prove it for l + 1. A
first property to note is that Ak E N, wkk 1
(EN(()) wx(3) and 2 (i) = Ejer'o ())
where we use (i) and (i) to denote the neighborhood of in G and G", respectively.
To show 35 for ls 1, we look at each node separately:
(1+)(11 (3) + WA (5) + wy (7) + (x
(5) wv (6) (x( wP wx((8)
(39)
(5) w/ w/ (8)
(1)
* i = 2
wk+1(2) =w) + wx (x( (10)
=3)(3) + (4) w (7
(40)
=3((33 + + (
12)+1(2)
i = 3
(k+1(3) =wx (1) + (x( #v
=w (2) + wg(11) + w (12)
(41)
=2( + (11) + (12)
(3)
-1=4
wk+1(4) -wx (2) + wy w23 wp (14) -w/( (2) + w w/ (14)
(42)
=w/+1 (4)
5
wk+1 (5) =w/ ur (13) =w (1) + w/ (13)
(43)
=w/+1
ii=0 6
(6) =w (2) + uk (11)
=wh(1) (1) (11)
(44)
=w((1) + (11)
=6/+1(6)
11=
(1+1(77 =w (1) + un (13)
=wy (1) + w/ (13)
(45)
-7)+1(7)
22

---

Published as a conference paper at ICLR 2021
8
Wk+1(8) (2) + wx (12)
=wx(1) (12)
(46)
=w((1) + 2 (12)
=
* i 9
wk+1 (9) = =w (1)
wk (2)
(47)
= (2)
=0 (9)
ii= 10
Wh+1 (10) =w (2)
=w (2)
(48)
01 (10)
ii E {11. 14)
For each of these i's, N(i) -i) Therefore,
Wk++ 1 (i) Σ wi)
jEN(()
= Σ wk(Ci)
(49)
JEN'())
=1)+1(1)
Next, for 36
38
at ls + 1,
wk+1(1) =w (3) + wk (5) + (7) + (9)
=wk (4) + wx (6) + (8) + (10)
(50)
= (2)
WK+1 (3) + Wk+t w (9) =2w; (1) =2w (2) + w/ (1( + w
(11) + wv (12)
(51)
Wh++ (6) + w2+1
Wk+1(55 + (7)
=2 (1) + wx(33) + w1(44)
=2w (2) (13)) + (144
(52)
Wk++ (4) + wx+1 (10)
This proves the inductive hypothethis for k 1.
We next argue that these two graphs can be distinguished by WL in 2 iterations. This is because 2 iterations of WL distinguish neighborhoods up to the depth-2 rooted aggregation trees (as will be defined in Section and it is not hard to see that the multiset of depth-2 rooted aggregation trees are different for the two graphs. Note that a depth-2 rooted subtree can be represented by the multiset of the degrees of the depth-1 children. Then for example, the depth-2 rooted aggregation trees of and 2 in are both {3, 2, 2, } m. while their rooted aggregation trees in G' are 2,2,,2,2, 2}... i and (3, 3, 1, 1, m. respectively.
L EXPERIMENT DETAILS
L. SPECIFIC ARCHITECTURES
In Section we show experiments on several tasks to confirm our theoretical results with several related architectures. Here some explanations for them:
23

---

Published as a conference paper at ICLR 2021
Graph Isomorphism Networks proposed by Xu et al. (2019). In experiment counting attributed walks, we take the depth of GIN as same as the depth target walks. The number of hidden dimensions is scarched in {8, 16, 32, 64, 256}. The model is trained with the Adam optimizer (Kingma & Ba 2014) with learning rate selected from {0.1, 0.02, 0.01, 0.005, 0.001}. We also train variant with Jumping Knowledge (Xu et al. 2018
GIN:
sGNN: Spectral GNN proposed by Chen et al. (2019b), which can be viewed as a lcarnable generalization of power iterations collection of operators. While the best performing variant utilizes the aanbbacktracking operator on the line graph, for fairer comparison with GA-MLPs,
choose variant with the base collection of operators being {L, A, A²) on each layer and depth 60, which then has the same receptive field as the chosen GA-MLP models. The model is trained with the Adam optimizer with learning rate selected from {0.001, 0.002, 0.004).
GA-MLP: a multilayer perceptron following graph augmented features. For counting at- tributed walks, choose the operators from (7, A ( The number of hidden dimensions is searched in {8, 32, 64, 256]. We take the highest order of operators as the twice depth of target walks at most. For comminity detection, we choose the operators from {I, [I. H²
where A is induced from the Bethe Hessian matrix H. The highest order of operators is searched in {30, 60, 120]. The number of hidden dimensions is searched in {10, 20). On both tasks, the model is trained with the Adam optimizer (Kingma & Ba 2014) with learn- ing rate selected from f0.1, 0.02, 0.01, 0.005, 0.001, 0.0001]. Additionally,
Batch Normalization (loffe & Szegedy 2013) in community detection after propagating through each operator, following the normalization strategy from Chen et al. (2019b). We choose ip to be the identity function.
L.2 BETHE HESSIAN
The Bethe Hessian matrix is defined as
H(r) = (p2 (f-1)=
with being flexible parameter. In SBM, optimal choice is Te Vc, where is the average degree. Spectral clustering (Saade et al. 2014) can be performed by computing the eigenvectors associated with the negative eigenvalues of (rre) get clustering information in assortative binary stochastic block model, which is the scenario we consider. In order to utilize power iterations for eigenvector extraction, we induce a new matrix as
H = kI - H(r.).
so that the smallest eigenvalues of // become the largest eigenvalues of Ii We choose 8 in our experiments. For GA-MLP-HH, we then let Ω (7, H, ..., Kk).
L.3 RESULTS FOR GA-MLP-A() IN COMMUNITY DETECTION
Table 4: Results for community detection binary SBM by GA-MLP-A Rank of hardness
2
5
Overlap
0.128
0.164
0.262
0.707
0,563
24


Reviews:
[{"review_id": "ncnlgkV228R", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 paper studies a variant of Graph Neural Networks (GNNs) namely, Graph Augmented MLPs (GA-MLPs). Unlike in GNNs where nodes send messages to neighbors, and aggregate received messages via non-linear MLPs,  GA-MLPs rely on a single augmented embedding computed once and then applying an MLP to the new embeddings. The augmented embeddings can be obtained by applying linear transformations of the form A, A^2, …, A^k to the input representations, thereby capturing larger neighborhoods. The main goal of the paper is to demonstrate a fundamental weakness when using GA-MLPs for solving graph problems as compared to GNNs. Along these line the paper the main results can be characterized as follows:\n       1) The paper identifies a specific instance of identifying non-isomorphic graphs that can be solved via a GNN but not by a GA-MLP framework.\n       2) The paper provides an empirical and experimental evaluation of the representation power of GNNs versus Graph-Augmented MLPs, and show a separation in expressive power between the two in terms of node level functions on rooted graphs. Specifically, they show that the set of functions that can be represented by a GNN of a certain depth) grows doubly exponentially in k, as opposed to only exponential growth of the function class when considering a similar GA-MLP architecture. They also empirically evaluate the difference in performance of the two models on community detection and counting walk problems. \n\nTo obtain the result in 1, the paper uses the recent equivalence between the computation in a depth-k GNN and the WL graph isomorphism test. The authors use this to construct two non-isomorphic graphs that the  WL test can distinguish using 2 iterations, but on which a GA-MLP will produce the same augmented embeddings. To obtain the result in 2, the authors count the number of distinct rooted trees that can be produced during the computations of a GNN and GA-MLP, and show a gap between the case of a GNN and a GA-MLP.\n\nMy main main concern with the paper is that it does not provide sufficiently rigorous findings on either the theoretical or the experimental front.   On the theoretical side, the paper establishes a somewhat expected performance gap between using a full GNN and an approximation such as a GA-MLP. Also it seems that the lower bounds for GA-MLPs only hold for the variant where the linear transformations are of the form A,A^2, and so on. Perhaps the authors can clarify this point?  Further there are no sample complexity or generalization bounds provided.   On the experimental front, it would have been much nicer to understand the tradeoffs in performance versus scalability or provide guidance on which models are more suitable for common, real-world GNN problems and applications. Counting attributed walks and community detection are not very representative problems for GNNs.", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZQCmV_0Gzxc", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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 paper compares graph neural networks (GNNs) with graph-augmented multi-layer perceptrons (GA-MLPs) where GA-MLPs are MLPs over nodes with additional node features computed over the graph. The paper contains theoretical results and experimental results for graph isomorphism testing and for node level functions. In the overflow of papers studying the expressivity of GNNs, the originality comes from the study of GA-MLPs and from the comparison for node level functions.\n\nThe paper is well written and there is a nice balance between theoretical results and empirical ones. Overall the results are not surprising but, to the best of my knowledge, they are not written elsewhere and the proofs are given. Thus, in my opinion, the paper is an original contribution to the field and can be published. I think that the paper could be improved by stating clearly (at the beginning of the paper) that the expressive power of GA-MLPs heavily rely on the choice of the operator family. And, along the paper, it should be made clear when considering GA-MLPs which class of GA-MLPs is considered (for instance, the class GA-MLPA is introduced in Section 6). Also, a synthetic comparison of the results for GA-MLPs w.r.t. the operator family could be given in the paper.\n\nPlease note that I read the proofs but I could not check them in detail.\n\nComments.\n\nIntroduction. In my opinion, there should be a more detailed description of graph operators used in the paper as well as the classes of GA-MLPs considered in the paper. Indeed, as such, the proposed contributions are not precise enough and can be misleading.\n\nSection 3.3. Choices for $\\Omega$ used in the paper should be presented here. Perhaps, classes of GA-MLPs should be named accordingly.\n\nSection 4. Only consider GA-MLPs. Already Prop.1, Prop. 2 and last § show the importance of the operator family for GA-MLPs.\n\nSection 5. Could be divided in two sections: one for GNNs and one for GA-MLPs. For GA-MLPs, again there is a clear hierarchy depending on the operator family.\n\nSection 6.2. GA-MLP mean GA-MLPA ?\n\nSection 6.3. The end of the section clearly shows the importance of the choice of the operator family and this should have been made clear before.\n\n\nDetails and Typos\n* §Depth in GNNs. the their\n* Not easy to find references in Appendix: ref to Appendix J is given before the proposition. Reference to Appendix E is not given.\n* Section 5 §2. \"analogous to the equivalence relations on $\\cal G$ introduced in Section 4\". I do not see such relations in Section 4.\n* Appendix F is \"Lemma 3\"\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WAjUFa9zpxQ", "reviewer": "AnonReviewer1", "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 paper is a theoretical analysis of two different classes of graph neural network: 1) GNN based on neighborhood aggregations (GNN) and 2) feature augmentation before MLP (GA-MLP).\nThe author contributions may be summarized as:\n- exhibiting graphs/problems that may be handled by one method and not the other,\n- giving an upper-bound on the number of equivalent clases induceds by linear GA-MLP in term of walks in a rooted tree.\n- showing a gap in expressivness between GNN and GA-MLP\n- showing that the choice of operator in GA-MLP is crucial and may have expressive power beyond WL.\n\nPros:\n+ The paper is well written.\n+ The theoretical analysis performed in the paper is new, non trivial, and very interesting, giving light on these two architectures.\n\nRemarks:\n- Section 3.1: shouldn't 2-EXP be: log log is polynomial (instead of linear)?\n- Section 5, corollary 1: 'poly-exponential'?\n\nQuestions:\n- How to go beyond linear operators in section 5?\n\nTypos:\n- after proposition 6: in words -> on other words\n- few sentences without verb and missing punctuation in the appendix\n- many references are incomplete, e.g. On the universality of invariant networks is ICML'19, What graph neural networks cannot learn: depth vs width is ICLR'20, etc", "extra_scores": {}, "extra_text": {}}, {"review_id": "W88qM50znyS", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 paper presents a theoretical analysis to compare expressive power of Graph-Neural Networks (GNNs) w.r.t a class of simpler graph modles called  Graph-Augmented MLPs (GA-MLPs).   GNNs, especially deeper ones can be more difficult to train, and GA-MLPs have a simpler structure, significantly easier to train, and have been shown to have competitive performance on a number of tasks.  The paper dives deep into several problems (graph-isomorphism, node-classification, and community detection) and through innovative analysis shows that GNNs at least theoretically can have significant advantages for some of the problems. \n\nI enjoyed reading this paper, and in my opinion it's an important contribution to the field.  It's much more common to see papers that do only experimental validations  (which are of course very important in their own right), but little attempt is usually done beyond simple intuition.  This paper employs a number of technical tools to formally establish that for some problems GNNs (at least in theory, and conditioned on being able to learn them well) are significantly more expressive than GA-MLPs.  Some of the discussion can be made clearer,  but overall the paper is very well written.  Experimental validation is fairly basic, but helpful, however, it's mostly on stylized problems, and a general outlook for practical graph-ML problems would be helpful. \n\nSome comments: \n1)  The applications you consider (apart from community detection) seem quite stylized, (e.g. counting the number of certain types of walks from a node), so it would be nice to make some comments on what your analysis may imply  for typical practical applications of GNNs  (e.g. combinatorial optimization / graph or node classification / various tasks of using graph NNs in material science / chemistry  and give some comments of where do you feel GA-MLPs may be competitive.   \n2) You also mentioned that there's recent progress in training deeper GNNs (using residual connections, and other tricks), so the outlook from the paper seems to be that for now GNNs are harder to tune, but more expressive, but the hope is that with advances in training that won't be an issue,  and then GA-MLPs will be less competitive, except on certain applications like graph-isomorphism?  \n3)  In section 4,  it seems that distinguishing almost any pair of graphs drawn from a uniform distribution is not a very complex tasks -- as such pairs of graphs are likely to be very different.  Would it be harder to distinguish two graphs, where the second graph starts from the first and includes some modifications / transformations (e.g. swapping edges, e.t.c). \n4) last sentence before the summary in section 1 seems to have grammatical issues. \n5) It could be useful to give a short motivating sentence for Bethe-Hessian (e.g. is connected to Bethe-free-energy?)\n6) What is laplacian sub-eigenspaces -- do you mean laplacian eigen sub-spaces?  (section  2). \n7)  I liked the analysis based on attributed walks , and rooted aggregated trees,  it may have some connections to computation-trees and walk-based type of analysis in graphical models literature: \ne.g. self-avoding walks for graphs and independent sets,  Chandrasekaran, Chertkov, Gamarnik et al, \"Counitng independent sets using the Bethe Approximation\",  and \"Walk-Sums and Belief Propagation in Gaussian Graphical Models\", johnson, malioutov, willsky, JMLR, 2006,  and  Yedidia, Freeman, Weiss, \"understanding belief propagation and its generalizations\". \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper compares “Graph Augmented MLPs” (GA-MLP), which augment node features by a single aggregation of neighbors and then pass the resulting features through an MLP, to graph neural networks (GNNs). The paper establishes results on representational power of some GA-MLP models being less powerful than GNNs. While practitioners may not change their behavior as a result, the work appears carefully done, is novel, and reviewers are mostly in agreement that the paper is a nice read and good contribution to the field.
Decision: Accept (Poster)