ON GRAPH NEURAL NETWORKS VERSUS GRAPH- AUGMENTED MLPS
Year: 2021

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 WeisfeilerLehman (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.

heading: 1 INTRODUCTION
text: 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 on neighborhood-aggregation 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 in training as well as bottleneck effects (Kipf & Welling, 2016; Li et 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 a node-wise function to the augmented node features, usually realized by a Multi-Layer Perceptron (MLP) (Wu et al., 2019; NT & Maehara, 2019; Chen et al., 2019a; Rossi et al., 2020). Because of the usage of graph operators for augmenting the node features, we will refer to such models as Graph-Augmented MLPs (GA-MLPs). These models have achieved competitive performances on various tasks, and moreover enjoy better scalability 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 to 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-MLPs from the viewpoint of graph isomorphism tests, we propose a new perspective that better suits the setting of node-prediction tasks: we analyze the
∗Equal contributions. Code available at https://github.com/leichen2018/GNN_vs_GAMLP.
expressive power of models including GNNs and GA-MLPs as node-level functions, or equivalently, as functions on rooted graphs. Under this perspective, we prove an exponential-in-depth gap between the expressive powers of GNNs and GA-MLPs. We illustrate this gap by finding a broad family of user-friendly functions that can be provably approximated by GNNs but not GA-MLPs, based on counting attributed walks on 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-MLPs 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-MLPs in terms of the equivalence classes on rooted graphs that they induce.
• Showing that the functions that count a 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.

heading: 2 RELATED WORKS
text: Depth in GNNs Kipf & Welling (2016) observe that the performance of Graph Convolutional Networks (GCNs) degrade as the depth grows too large, and the best performance is 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 et al. (2019) explain the failure of deep GCNs by the over-smoothing of the node features. Oono & Suzuki (2020) show an exponential loss of expressive power as the depth in GCNs increases in the sense that the hidden node states tend to converge to Laplacian sub-eigenspaces as the depth increases to infinity. Alon & Yahav (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 neighborhoodaggregation 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, in 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 as well as normalization steps (Ioffe & Szegedy, 2015; Ulyanov et al., 2016). Recently, Li et al. (2019; 2020a) and Chen et al. (2020a) build deeper GCN architectures with the help of various residual connections (He et al., 2016) and normalization steps to 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 on graph- and mesh-based tasks.
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 Convolution (SGC), which removes the intermediary weights and nonlinearities in GCNs. Chen et al. (2019a) 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-PageRank-based (Klicpera et al., 2018; 2019) and triangle-based (Monti et al., 2018; Chen et al., 2019b) adjacency matrices.
Expressive Power of GNNs Xu et al. (2019) and Morris et al. (2019) show that GNNs based on neighborhood-aggregation are no more powerful than the Weisfeiler-Lehman (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
GNN models whose expressive power are not limited by WL (Morris et al., 2019; Maron et al., 2019a; Chen et al., 2019c; Morris & Mutzel, 2019; You et al., 2019; Bouritsas et al., 2020; Li et al., 2020b; Flam-Shepherd et al., 2020; Sato et al., 2019; 2020). Other perspectives for understanding the expressive power of GNNs include function approximation (Maron et al., 2019b; Chen et al., 2019c; Keriven & Peyré, 2019), substructure counting (Chen et al., 2020b), Turing universality (Loukas, 2020) 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 a new perspective of approximating functions on rooted graphs, which is motivated by node-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 equivalence classes that they induce on rooted graphs.

heading: 3 BACKGROUND

heading: 3.1 NOTATIONS
text: Let G = (V,E) denote a graph, with V being the vertex set and E being the edge set. Let n denote the number of nodes in G, A ∈ Rn×n denote the adjacency matrix, D ∈ Rn×n denote the diagonal degree matrix with Dii = di being the degree of node i. We call D− 1 2AD− 1 2 the (symmetrically) normalized adjacency matrix, and D−αAD−β a generalized normalized adjacency matrix for any α, β ∈ R. Let X ∈ Rn×d denote the matrix of node features, where Xi denotes the d-dimensional feature that node i possesses. For a node i ∈ V , letN (i) 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 ∈ Rn. For a positive integer K, we let [K] = {1, ...,K}. We use {...}m to denote a multiset, which allows repeated elements. We say a function f(K) is doubly-exponential in K if log log f(K) is polynomial in K, and poly-exponential in K if log f(K) is polynomial in K, as K tends to infinity.

heading: 3.2 GRAPH NEURAL NETWORKS (GNNS)
text: Following the notations in Xu et al. (2019), we consider K-layer GNNs defined generically as follows. For k ∈ [K], we compute the hidden node states H ∈ Rn×d(k) iteratively as
M (k) i = AGGREGATE (k)({H(k−1)j : j ∈ N (i)}) , H (k) i = COMBINE (k)(H (k−1) i ,M (k) i ) , (1)
where we set H(0) = X to be the node features. If a graph-level output is desired, we finally let
ZG = READOUT({H(K)i : i ∈ 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 permutationinvariant. 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-layer GNNs, either. For this reason, we will not distinguish between GNN and WL in discussions on expressive powers.

heading: 3.3 GRAPH-AUGMENTED MULTI-LAYER PECEPTRONS (GA-MLPS)
text: 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 Ω = {ω1(A), ..., ωK(A)} ⊆ Rn×n be a 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 Ω that give rise to existing GA-MLP models are listed in Appendix B. In its general form, a GA-MLP first computes a series of augmented features via
X̃k = ωk(A) · ϕ(X) ∈ Rn×d̃ , (3)
with ϕ : Rd → Rd̃ being a learnable function acting as a feature transformation applied to each node separately. It can be realized by an MLP, e.g. ϕ(X) = σ(XW1)W2, where σ is a nonlinear activation function and W1,W2 are trainable weight matrices of suitable dimensions. Next, the model concatenates X̃1, ..., X̃K into X̃ = [X̃1, ..., X̃K ] ∈ Rn×(Kd̃), and computes
Z = ρ(X̃) ∈ Rn×d ′ , (4)
where ρ : RKd̃ → Rd′ is also a learnable node-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 ϕ to be the identity function, in which case (3) and (4) can be written together as Z = ρ([ω1(A) ·X, ..., ωK(A) ·X]) (5) Such a simplification improves computational efficiency since the matrix products ωk(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) in this paper, but the lower-bound result in Proposition 2 remains valid even when we restrict to the subset of models where ϕ is taken to be the identity function.

heading: 4 EXPRESSIVE POWER AS GRAPH ISOMORPHISM TESTS
text: We first study the expressive power of GA-MLPs via their ability to distinguish non-isomorphic graphs. It is not hard to see that when Ω = {I, Ã, ..., ÃK}, where Ã = D−αAD−β for any α, β ∈ R generalizes the normalized adjacency matrix, this is upper-bounded by the power ofK+1 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 Ω consists of integer powers of any normalized adjacency matrix of the form D−αAD−(1−α) 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 Ω 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 is given in Appendix K. Together, we summarize the results as:
Proposition 1. If Ω ⊆ {Ãk : k ∈ N}, with either Ã = A or Ã = D−αAD−(1−α) for some α ∈ [0, 1], there exists a pair of graphs which can be distinguished by GNNs but not this GA-MLP.
Nonetheless, if we focus on not particular counterexamples but rather the average performance in distinguishing random graphs, it is not hard for GA-MLPs to reach the same level as WL, which is known to distinguish almost all pairs of random graphs under a uniform distribution (Babai et al., 1980). Specifically, building on the results in Babai et al. (1980), we prove in Appendix F that:
Proposition 2. For all n ∈ N+, ∃αn > 0 such that any GA-MLP that has {D,AD−αn} ⊆ Ω can distinguish almost all pairs of non-isomorphic graphs of at most n nodes, in the sense that the fraction of graphs on which such a GA-MLP fails to test isomorphism is 1− o(1) as n→∞.
The hypothesis that distinguishing 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 we count the number of equivalence classes that either of them induce on graphs that occur in realworld datasets. This further raises the question of whether graph isomorphism tests along suffice as a
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 Ω contains the power graph adjacency matrix introduced in Chen et al. (2019b), min(A2, 1), then the GA-MLP can distinguish between a hexagon and a pair of triangles, which WL cannot distinguish.

heading: 5 EXPRESSIVE POWER AS FUNCTIONS ON ROOTED GRAPHS
text: To study the expressive power beyond graph isomorphism tests, we consider the setting of nodewise 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, ..., in} is a set of nodes in the graphs {G1, ..., Gn} (not necessarily distinct) and with node-level labels {Yi1 , ..., Yin} known during training, respectively, then the goal is to fit a function to the input-output pairs (G[in]n , Yin), where we use G
[i] to denote the rooted graph with G being the graph and the node i 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 F on E , we can define an equivalence relation 'E;F among all rooted graphs such that ∀G[i], G′[i ′] ∈ E , G[i] 'E;F G′[i ′] if and only if ∀f ∈ F , f(G[i]) = f(G′[i′]). By examining the number and sizes of the induced equivalence classes of rooted graphs, we can evaluate the relative expressive power of different families of functions on E in a quantitative way. In the rest of this section, we assume that the node features belong to a finite alphabet X ⊆ N and all nodes have degree at most m ∈ 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[i] is a depth-K rooted tree with a (possibly many-to-one) mapping from every node in the tree to some node in G[i], where (i) the root of the tree is mapped to node i, and (ii) the children of every node j in the tree are mapped to the neighbors of the node in G[i] to which j is mapped. An illustration of rooted graphs and rooted aggregation trees is given in Figure 4. Hence, each equivalence class in E 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 to 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 and m ≥ 3. The total number of equivalence classes of rooted graphs induced by GNNs of depth K grows at least doubly-exponentially 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 Ω = {I, Ã, Ã2, ..., ÃK}, in which Ã = D−αAD−β with any α, β ∈ R is a generalization of the normalized adjacency matrix. From formula (3), by expanding the matrix product, we have
(Ãkϕ(X))i = ∑
(i1,...,ik)∈Wk(G[i])
d−αi d −(α+β) i1 ...d −(α+β) ik−1 d−βik ϕ(Xik) , (6)
where we define Wk(G[i]) = {(i1, ..., ik) ⊆ V : Ai,i1 , Ai1,i2 , ..., Aik−1,ik > 0} to be set of all walks of length k in the rooted graph G[i] starting from node i (an illustration is given in Figure 2). Thus, the kth augmented feature of node i, (Ãkϕ(X))i, is completely determined by the number of each “type” of walks in G[i] of length k, where the type of a walk, (i1, ..., ik), is determined jointly by the degree multiset, {di1 , ..., dik−1} as well as the degree and the node feature of the end node, dik and Xik . Hence, to prove an upper bound on the total number of equivalence classes on E induced by such a GA-MLP, it is sufficient to upper-bound the total number of possibilities of
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 Ω = {I, Ã, Ã2, ..., ÃK}, where Ã = D−αAD−β for some α, β ∈ R. Then the total number of equivalence classes in E induced by such GA-MLPs is poly-exponential in K.
Compared with Proposition 3, this shows that the number of equivalence classes on E 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 et al. (2019c; 2020b) on the equivalence between distinguishing non-isomorphic graphs and approximating arbitrary permutation-invariant 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-exponentially in K; Fixing α, β ∈ R, the VC dimension of all GA-MLPs with Ω = {I, Ã, Ã2, ..., ÃK} as functions on rooted graphs is at most poly-exponential in K.
Meanwhile, for more general operators, we can show that the equivalence classes induced by GAMLPs are coarser than those induced by GNNs at least under some measurements. For instance, the pair of rooted graphs in Figure 2 belong to the same equivalence class induced by any GA-MLP (as we prove in Appendix I) but different equivalence classes induced by GNNs. Rigorously, we characterize such a gap in expressive power by finding certain equivalence classes in E induced by GA-MLPs that intersect with many equivalence classes induced by GNNs. In particular, we have the following general result, which we prove in Appendix I: Proposition 5. If Ω 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 Ω, each of which intersects with doubly-exponentiallyin-K many equivalence classes in E induced by depth-K GNNs, assuming that |X | ≥ 2 and m ≥ 3. Conversely, in constrast, if Ω = {I, Ã, Ã2, ..., ÃK}, in which Ã = D−αAD−β with any α, β ∈ 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 so far, this occurs when the image of each equivalence class in E induced by GNNs under this function contains a single value, whereas the image of some equivalence class in E induced by GA-MLPs contains multiple values. Inspired by the proofs of the results above, a 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 J: Proposition 6. For any sequence of node features {xk}k∈N+ ⊆ X , consider the sequence of functions fk(G[i]) := |Wk(G[i]; (x1, ..., xk))| on E . For all k ∈ N+, the image under fk 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 exponentiallyin-k many equivalence classes in E induced by this GA-MLP whose image under fk contains exponentially-in-k many values.
In other words, there exist graph instances where the attributed-walk-counting-function fk takes different values, yet no GA-MLP model can predict them apart – and there are exponentially many
Cora Citeseer Pubmed
# Nodes 2708 3327 19717 K GNN GA-MLP GNN GA-MLP GNN GA-MLP
1 37 37 31 31 82 82 2 1589 756 984 506 8059 3762 3 2301 2158 1855 1550 12814 12014 4 2363 2359 2074 2019 12990 12979 5 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.
Cora RRG
Model Train Test Train Test
GIN 3.98E-6 9.72E-7 3.39E-5 2.61E-4 GA-MLP-A 1.23E-1 1.56E-1 1.75E-2 2.13E-2 GA-MLP-A+ 1.87E-2 6.44E-2 1.69E-2 2.13E-2 GA-MLP-Ã(1) 4.22E-1 5.79E-1 1.02E-1 1.58E-1 GA-MLP-Ã(1)+ 4.00E-1 5.79E-1 1.12E-1 1.52E-1
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 as the number of hops increases. This suggests the possibility of lower-bounding the average approximation error for certain functions by GA-MLPs under various random graph families, which we leave for future work.

heading: 6 EXPERIMENTS
text: The baseline GA-MLP models we consider has operator family Ω = {I, A, ..., AK} for a certain K, and we call it GA-MLP-A. In Section 6.2 and 6.3, we also consider GA-MLPs with Ω = {I, Ã(1), ..., ÃK(1)} (Ã( ) is defined in Appendix B), denoted as GA-MLP-Ã(1). For the experiments in Section 6.3, due to the large K as 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 L.

heading: 6.1 NUMBER OF EQUIVALENCE CLASSES OF ROOTED GRAPHS
text: Motivated by Propositions 3 and 4, we numerically count the number of equivalence classes induced by GNNs and GA-MLPs among the rooted graphs found in actual graphs with node features removed. For depth-K GNNs, we implement a WL-like process with hash functions to map the depth-K egonet associated with each node to a string before comparing across nodes. For GAMLP-A, we compare the augmented features of each egonet computed via (3). From the results in Table 1, 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.

heading: 6.2 COUNTING ATTRIBUTED WALKS
text: 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 6. 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−→blue−→blue starting from i. On the RRG, the label is given by the number of walks of the type blue−→blue−→blue−→blue starting from i. The number of nodes for training and testing is split as 1000/1708 for the Cora graph and 300/700 for the random regular graph. We test four GA-MLP models, two with as 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 in the gap of expressive power between GNNs and GA-MLPs.

heading: 6.3 COMMUNITY DETECTION ON STOCHASTIC BLOCK MODELS (SBM)
text: We use the task of community detection to illustrate another limitation of GA-MLP models: a lack of flexibility to learn the family of operators. SBM is a random graph model in which nodes are partitioned into underlying communities and each edge is drawn independently with a probability
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, 2017). We select 5 pairs of in-group and out-group connectivity, resulting in 5 different hardness levels of the task.
Among all different approaches to community detection, spectral methods are particularly worth mentioning here, which usually aim at finding a certain eigenvector of a 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 (Krzakala et al., 2013). In particular, the Bethe Hessian matrix is 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 spectral 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 L.
We first compare two variants of GAMLP models: GA-MLP-A with K = 120, and GA-MLP-H with Ω generated from the Bethe Hessian matrix with the oracle data-dependent parameter also up to K = 120. From Figure 3, we see that the latter consistently outperforms the former, indicating the importance of the choice of the operators for GA-MLPs. As reported in Appendix L, replacingA by Ã(1) yields no improvement in performance. 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 (further details given in Appendix L). We see that its performance is comparable to that of GA-MLP-H . Thus, this
demonstrates a scenario in which GA-MLP with common choices of Ω do not work well, but there exists some choice of Ω that is a priori unknown, with which GA-MLP can achieve good performance. 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.

heading: 7 CONCLUSIONS
text: We have studied the separation in terms of representation power between GNNs and a popular alternative 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 non-isomorphic graphs, in terms of approximating node-level functions, there exists a gap growing exponentially-in-depth between GA-MLPs and GNNs in terms of the number of equivalence 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 detection, 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 features through learnt diffusion operators, while GA-MLPs are limited to a fixed family of diffusions.
While we do not attempt to provide a decisive answer of whether GNNs or 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 a gap is more likely to
be seen – those exploiting stronger structures among nodes like counting attributed walks, or those involving the learning of 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-MLPs and spectral methods, and how this can help learning diffusion operators.

heading: ACKNOWLEDGEMENTS
text: 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-1901091, Capital One, Samsung Electronics, and the Institute for Advanced Study.

heading: A GA-MLP WITH GENERAL EQUIVARIANT GRAPH OPERATORS FOR NODE FEATURE AUGMENTATION
text: For a graph G = (V,E) with n nodes, assume without loss of generality that V = [n]. Let Sn denote the set of permutations of n, and ∀π ∈ Sn, it maps a node i ∈ [n] to π(i) ∈ [n]. For π ∈ Sn and a matrix M ∈ Rn×n, we use π ? M ∈ Rn×n to denote the π-permuted version of M , that is, (π ? M)i,j = Mπ(i),π(j). For π ∈ Sn and a matrix Z ∈ Rn×d, we use π ? Z ∈ Rn×d to denote the π-permuted version of M , that is, (π ? Z)i,p = Zπ(i),p.
Below, we define a more general form of GA-MLP models that extend the use of equivariant linear operators for node feature propagation to that of general equivariant graph operators. We first define a map ω : Rn×n × Rn×d → Rn×d′ , whose first input argument is always the adjacency matrix of a graph,A, and second input argument is a node feature matrix. We say the map satisfies equivariance to node permutations if ∀π ∈ Sn, ∀Z ∈ Rn×d, there is ω(π ?A, π ?Z) = π ?ω(A,Z). With a slight abuse of notations, we also use ω[A](Z) to denote ω(A,Z), thereby considering ω[A] : Rn×d → Rn×d′ as an operator on node features. If ω satisfies equivariance to node permutations as defined above, we then call ω[A] an equivariant graph operator. We can then define a general (nonlinear) GA-MLP model as
X̃ = ω[A](X) Z = ρ(X̃) (7)
where ω is an equivariant graph operator, and ρ is a node-wise function.
It is easy to see that Proposition 7. If ω[A](X) = m(A) ·X , where m(·) = Rn×n → Rn×n is an entry-wise function or matrix product or compositions thereof, then ω[A] is an equivariant graph operator.
A.1 EXTENDING THE PROOF OF PROPOSITION 5 AND 6 TO GENERAL GA-MLPS
An extension of the first half of Proposition 5 is Proposition 8. If ω[A] is an equivariant graph operator, then there exist exponentially-in-K many equivalence classes in E induced by the general GA-MLPs with ω[A], each of which intersects with doubly-exponentially-in-K many equivalence classes in E induced by depth-K GNNs, assuming that |X | ≥ 2 and m ≥ 3.
Proof : Similar to the proof of Proposition 5 given in Appendix I, we consider the set of full m-ary rooted trees of depth K, Tm,K,X , that is all rooted trees of depth K in which the nodes have features belonging to the discrete set X ⊆ N and all non-leaf nodes have m children. Tm,K,X is a subset of E , the space of all rooted graphs. Suppose f is a function represented by a general GA-MLP defined in (7) with an equivariant graph operator ω[A]. Let Vk denote the set of nodes at depth k of T . Notice the following symmetry among nodes in each Vk: if π is the permutation of a pair of nodes in some Vk for 1 ≤ k ≤ K, then π ? A = A. By the equivariance property of ω, this implies that
ω[A](π ? Z) =ω[π ? A](π ? Z)
=π ? ω[A](Z) (8)
Let X denote the node feature matrix associated with T , and π ?T denote the rooted tree in Tm,K,X 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 ) =ρ (ω[A](X)1,:) =ρ (
(π ? ω[A](X))1,: ) =ρ (ω[A](π ? X)1,:)
=f(π ? T )
(9)
This implies that for two trees T and T ′ ∈ Tm,K,X , if ∀0 ≤ k ≤ K,∀x ∈ X , they satisfy |Wk(T ;x)| = |Wk(T ′;x)|, then f(T ) = f(T ′) for all such f ’s, and hence T and T ′ belong to
the same equivalence class in E induced by GA-MLPs. Therefore, by the rest of the argument given in Proposition 5, Proposition 8 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 {xk}k∈N+ ⊆ X , consider the sequence of functions fk(G[i]) := |Wk(G[i]; (x1, ..., xk))| on E . For all k ∈ N+, the image under fk of every equivalence class in E induced by depth-k GNNs contains a single value, while for any GA-MLP using equivariant graph operators, there exist exponentially-in-k many equivalence classes in E induced by this GA-MLP whose image under fk contains exponentially-in-k many values.
The proof replies on the same extension as described above in the proof of Proposition 8.

heading: B EXAMPLES OF EXISTING GA-MLP MODELS
text: For ∈ R, let Ā( ) = A + I , D̄( ) be the diagonal matrix with D̄( ),ii = ∑ j Aij + , and Ã( ) = D̄ −1/2 ( ) Ā( )D̄ −1/2 ( ) .

heading: C EQUIVALENCE CLASSES INDUCED BY GNNS AND GA-MLPS AMONG REAL GRAPHS
text: Given a space of graphs, G, and a family F of functions mapping G to R, F induces an equivalence relation that we denote by 'G;F among graphs in G such that for G1, G2 ∈ G, G1 'G;F G2 if and only if ∀f ∈ F , f(G1) = f(G2). For example, if F is powerful enough to distinguish all pairs of non-isomorphic graphs, then each equivalence class under'G,F contains exactly one graph. Thus, by examining the number or sizes of the equivalence classes induced by different families of functions on G, we can evaluate their relative expressive power in a 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, we
remove their node features and count the total number of equivalence classes among them induced by depth-K GNNs (equivalent to K-iterations of the WL test, as discussed in Section 3.2) as well as GA-MLPs with Ω = {I, A, ..., AK} for different K’s. We see from the results in Table 3 that as soon as K ≥ 2, the number of equivalence classes induced by GNNs and the GA-MLPs are both close to the total number of graphs up to isomorphism, implying that they are indeed both able to distinguish almost all pairs of non-isomorphic graphs among the ones occurring in these datasets.

heading: D ADDITIONAL NOTATIONS
text: For any k ∈ N+ and any rooted graph G[i] = (V,E, i) ∈ E , define
Wk(G[i]) = {(i1, ..., ik) ⊆ V : Ai,i1 , Ai1,i2 , ..., Aik−1,ik > 0} (10)
Wk(G[i]) = {(i1, ..., ik) ∈ Wk(G[i]) : i 6= i2, i1 6= i3, ..., ik−3 6= ik−1, ik−2 6= ik} (11)
as the sets of walks and non-backtracking walks of length k in G[i] starting from the root node, respectively. Note that when G[i] is a rooted tree, a non-backtracking walk of length k is a path from the root node to a node at depth k. In addition, for 0 ≤ d1, ..., dk ≤ m and x1, ..., xk ∈ X , define the following subsets ofWk(G[i]):
Wk ( G[i]; (d1, ..., dk), xk ) = {(i1, ..., ik) ∈ Wk(G[i]) : {di1 , ..., dik}m = {d1, ..., dk}m, Xik = xk}
(12) Wk ( G[i]; (x1, ..., xk) ) = {(i1, ..., ik) ∈ Wk(G[i]) : (Xi1 , ..., Xik) = (x1, ..., xk)} (13)
Wk(G[i];xk) = {(i1, ..., ik) ∈ Wk(G[i]) : Xik = xk} (14) We also defineWk ( G[i]; (d1, ..., dk), xk ) ,Wk ( G[i]; (x1, ..., xk) ) andWk(G[i];xk) similarly.
E ILLUSTRATION OF ROOTED GRAPHS AND ROOTED AGGREGATION TREES

heading: F PROOF OF PROPOSITION 2
text: With node features being identical in the random graphs, we take X ∈ Rn×1 to be the all-1 vector. Thus,
(DX)i = di , (15)
and (AD−αX)i = ∑ j∈N (i) d−αj . (16)
Since (4) and (2) together can approximate arbitrary permutation-invariant functions on multisets (Zaheer et al., 2017), if two graphs G = (V,E) and G′ = (V ′, E′) cannot be distinguished by the GA-MLP with an operator family Ω that includes {D,AD−α} under any choice of its parameters, it means that the two multisets {(di, ∑ j∈N (i) d −α j ) : i ∈ V }m = {(di′ , ∑ j′∈N (i′) d −α j′ ) : i
′ ∈ V ′}m, and therefore both of the following hold:
{di : i ∈ V }m ={di′ : i′ ∈ V ′}m (17) { ∑
j∈N (i)
d−αj : i ∈ V }m ={ ∑
j′∈N (i′)
d−αj′ : i ′ ∈ V ′}m (18)
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 n elements, all of which are integers between 0 and n. Consider the function hα(S) := ∑ u∈S u
−α defined for multisets S. If α > lognlogn−log(n−1) , hα is an injective function on Sn.
Proof of Lemma 1: For hα to be injective on Sn, it suffices to require that ∀l ≤ n − 1, there is l−α > n(l + 1)−α, for which it is sufficient to require that (n − 1)−α > n−α+1, or α > lognlogn−log(n−1) .
Lemma 2 (Babai et al. (1980), Theorem 1). Consider the space of graphs with n vertices, Gn. There is a subsetKn ⊆ Gn that contains almost all such graphs (i.e. the fraction converges to 1 as n→∞) such that the following algorithm yields a unique identifier for every graph G = (V,E) ∈ Kn:
Algorithm 1: Set r = [3 log n/ log 2], 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 γi = {dj : j ∈ N (i), dj > d̄(G)}m; Finally define a multiset associated with G, F (G) = {γi : i ∈ V }m, which is the output of the algorithm.
In other words, ∀G,G′ ∈ Kn, G and G′ are isomorphic if and only if F (G) = F (G′) as multisets. In particular, we can choose Kn such that the top r node degrees of every graph in Kn are distinct.
Based on these lemmas, we will show that when α > lognlogn−log(n−1) and for G,G ′ ∈ Kn, (17) and (18) together imply thatG is isomorphic toG′. 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 ∀i ∈ V ,∑
j∈N (i)
d−αj = ∑
j′∈N (i′)
d−αj′ , (19)
which, by Lemma 1, implies that {dj : j ∈ N (i)}m = {dj′ : j′ ∈ N (i′)}m. We then have γi = {dj : j ∈ N (i)}m = {dj : j ∈ N (i)}m ∩ (d̄(G),∞) = {dj′ : j′ ∈ N (i′)}m ∩ (d̄(G′),∞) = γi′ , and therefore F (G) = F (G′), which implies that G and G′ are isomorphic by Lemma 2. This shows a contradiction. Therefore, if G,G′ ∈ Kn are 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−α} ⊆ Ω that makes it return different outputs when applied to G and G′. This proves Proposition 2.

heading: G PROOF OF PROPOSITION 3
text: 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 E induced by GNNs, we only need to focus on a subset of all possible rooted aggregation trees, namely those in which every node has exactlym children. Letting T Am,K,X 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 to X , we will first prove the following lemma:
Lemma 3. If |X | ≥ 2, then |T Am,K,X | ≥ (m− 1)(2 K−1).
Note that a rooted aggregation tree needs to satisfy the constraint that each of its node must have its parent’s feature equal to one of its children’s feature, and so this lower bound is not as straightforward to prove as lower-bounding the total number of rooted subtrees. As argued above, this will allow us to derive Proposition 3.
Proof of Lemma 3: Define B := {0, 1}. Since |X | ≥ 2, we assume without loss of generality that B ⊆ X . To prove a lower-bound on the cardinality of T Am,K,X , it suffices to restrict our attention to its subset, T Am,K := T Am,K,B, where all nodes have feature either 0 or 1. Furthermore, it is sufficient to restrict our attention to the subset of T Am,K which contain all 2K possible types of paths of length K from the root to the leaves. Formally, withWk defined as in Appendix D, we let
T̃ Am,K = {T ∈ T Am,K : ∀x1, ..., xK ∈ B,WK(T ; (x1, ..., xK)) ≥ 1} , (20)
and it is sufficient to prove a lower bound on the cardinality of T̃ Am,K . Define Pk = {(x1, ..., xk) : x1, ..., xk ∈ B} to be the set of all binary k-tuples. By the definition of (20), we know that ∀τ ∈ PK , |WK(T ; τ)| ≥ 1. This means that ∀τ ∈ PK , there exists at least one leaf node in T such that the path from the root node to this node consists of a sequence of nodes with features exactly as given by τ . We call any such node a node under τ .
We show such a lower bound on the cardinality of T̃ Am,K inductively. For the base case, we know that T̃ Am,1 consists of all binary-featured depth-1 rooted trees with at least 1 leaf node of feature 0 and 1 leaf node of feature 1, and hence T̃ Am,1 = 2(m− 1). Next, we consider the inductive step. For every K ≥ 1 and every T ∈ T̃ Am,K , we can generate rooted aggregation trees belonging to T ∈ T̃ Am,K+1 by assigning children of feature 0 or 1 to the leaf nodes of T . First note that, from two non-isomorphic rooted aggregation trees T and T ′ ∈ T̃ Am,K , we obtain non-isomorphic rooted aggregation trees in T̃ Am,K+1 in this way. Moreover, as we will show next, for every T ∈ T̃ Am,K , we can lower-bound the number of distinct rooted aggregation trees belonging to T̃ Am,K+1 obtained from T in this way.
There are many choices to assign the children. To get a lower-bound on the cardinality of T̃ Am,K+1, we only need to consider a subset of these choices of assignments, namely, those that assign the same number of children with feature 0 to every node under the same τ ∈ PK . Thus, we let q̄K+1,τ denote the number of children of feature 0 assigned to every node in τ . Due to the constraint that each node in the rooted aggregation tree must have its parent’s feature equal to one of its children’s feature, not all choices of {q̄K+1,τ}τ∈PK lead to legitimate rooted aggregation trees. Nonetheless, when restricting to the choices where ∀τ ∈ PK , 1 ≤ q̄K+1,τ ≤ m− 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 or 1. Moreover, for such choices, the rooted aggregation tree of depthK+1 obtained in this way contains all 2K+1 possible paths of lengthK+1, and therefore belongs to T̃ Am,K+1. Hence, it remains to show a lower bound on how many distinct trees in T̃ Am,K+1 can be obtained in this way from each T . Since for τ, τ ′ ∈ PK such that τ 6= τ ′, a node under τ is distinguishable from a node under τ ′, we see that every legitimate choice of the tuple of 2K integers, (q̄K+1,τ )τ∈PK , leads to a distinct rooted aggregation tree of depth K + 1, and there are (m− 1)2K of these choices. Hence, we have derived that |T̃ Am,K+1| ≥ (m− 1)2
K |T̃ Am,K |, and therefore |T̃ Am,K | ≥ (m− 1) ∑K k=1 2 k = (m− 1)2K−1.

heading: H PROOF OF PROPOSITION 4
text: According to the formula (3), by expanding the matrix product, we have (Ãkϕ(X))i = ∑
(i1,...,ik)∈Wk(G[i])
d−αi d −(α+β) i1 ...d −(α+β) ik−1 d−βik ϕ(Xik)
=d−αi ∑
{d̄1,...,d̄t−1}m, d̄k,x
∑ (i,i1,...,ik)∈
Wk(G[i];{d̄1,...,d̄k−1}m,d̄k,x)
(d̄1...d̄k−1) −(α+β)d̄kϕ(x)
=d−αi ∑
{d̄1,...,d̄k−1}m, d̄k,x
( (d̄1...d̄k−1) −(α+β)d̄kϕ(x) ) ∣∣∣Wk(G[i]; {d̄1, ..., d̄t−1}m, d̄k, x)∣∣∣ ,
(21)
with Wk(G[i]; {d̄1, ..., d̄t−1}m, d̄k, x) defined in Appendix D. Hence, for two different nodes i in G and i′ in G′ (G and G′ can be the same graph), the node-wise outputs of the GA-MLP at i and i′ will be identical if the rooted graphs Gi and G′[i
′] satisfy Wk(G[i]; {d̄1, ..., d̄k−1}m, d̄k, x) = Wk(G′[i ′] ; {d̄1, ..., d̄k−1}m, d̄k, x) for every combination of choices on the multiset {d̄1, ..., d̄k−1}m, the integer d̄k and the node feature x, under the constraints of d̄1, ..., d̄k ≤ m and x ∈ X . Note that there are at most ( k+m−2 m−1 ) ≤ (k + m − 2)m−1 possible choices of the multiset {d̄1, ..., d̄k−1}m, m choices of d̄k and |X | choices of x, thereby allowing at most |X |m(k +m− 2)m−1 possible choices. Because of the constraint∑
{d̄1,...,d̄k−1}m, d̄k,x ∣∣∣Wk(G[i]K ; {d̄1, ..., d̄t−1}m, d̄k, x)∣∣∣ = |Wk(G[i])| ≤ mk , (22) We see that the total number of equivalence classes on E induced by such a GA-MLP is upperbounded by (mk+|X |m(k+m−2)m−1−1 |X |m(k+m−2)m−1 ) , which is on the order of O(mk m
) with k 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.

heading: I PROOF OF PROPOSITION 5
text: Consider the set of full m-ary rooted trees of depth K, Tm,K,X , that is all rooted trees of depth K in which the nodes have features belonging to the discrete set X ⊆ N and all non-leaf nodes have m children. Tm,K,X is a subset of E , the space of all rooted graphs. If f is a function represented by a GA-MLP using operators of at most K-hop, then for T ∈ Tm,K,X , we can write
f(T ) = ρ( ∑ j∈V ajXj) , (23)
where we denote the node set of T by V and the vectors aj’s depend only on the topological relationship between j and the root node. Let Vk denote the set of nodes at depth k of T . By the assumption that the operators depend only on 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 ∀1 ≤ k ≤ K and ∀j, j′ ∈ Vk, there is aj = a′j =: a[k]. Thus, we can write
f(T ) =ρ( ∑
0≤k≤K ∑ j∈Vk a[k]φ(Xj))
=ρ( ∑
0≤k≤K ∑ x∈X ā[k],x|Wk(T ;x)|) (24)
for some other set of coefficients āVk,x’s, and where Wk(T ;x) is defined in Appendix D. In other words, for two trees T and T ′ ∈ Tm,K,X , if ∀0 ≤ k ≤ K,∀x ∈ X , they satisfy
|Wk(T ;x)| = |Wk(T ′;x)|, then f(T ) = f(T ′) for all such f ’s, and hence T and T ′ belong to the same equivalence class in E induced by GA-MLPs. Thus, for a certain subset of these equivalence classes, we can lower-bound the number of equivalence classes in E induced by GNNs that they intersect by lower-bounding the number of distinct trees in Tm,K,X that they contain, because GNNs are able to distinguish non-isomorphic rooted subtrees. In particular, as 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, with B := {0, 1}.
In a rooted tree T ,Wk(T ;x) gives the total number of nodes with feature x at depth k. For integers q0, q1, ..., qK such that 0 ≤ qk ≤ mk, ∀k ≤ K, define
Tm,K,(q0,q1,...,qK) = {T ∈ Tm,K : ∀k ≤ K, |Wk(T ; 0)| = qk} , (25)
that is, the subset of trees whose per-level-node-counts, {|Wk(T ; 0)|}k≤K (and therefore {|Wk(T ;x)|}k≤K,x∈B) are given by the tuple (q0, q1, ..., qk). From the argument above, all trees in the same Tm,K,(q0,q1,...,qK) belong to the same equivalence class in E induced by GA-MLPs. On the other hand, every pair of non-isomorphic trees belong to different equivalence class in E induced by GNNs. Thus, to show Proposition 5, it is sufficient to find sufficiently many choices of (q0, q1, ..., qK) such that Tm,K,(q0,q1,...,qK) contains sufficiently many non-isomorphic trees. Specifically, we will show the following: Lemma 4. For all integers q0, q1, ..., qK such that ∀2 ≤ k ≤ K,
2k − 2k−2 ≤ qk ≤ 1
2 mk , (26)
there is |Tm,K,(q0,q1,...,qK)| ≥ 2 2K−1−1 (27)
Proof of Lemma 4: To prove such a lower bound on the cardinality of Tm,K,(q0,q1,...,qK), it is sufficient to prove a lower bound on the cardinality of its subset,
T̃m,K,(q0,q1,...,qK) = {T ∈ Tm,K,(q0,q1,...,qK) : ∀x1, ..., xK ∈ B,WK(T ; (x1, ..., xK)) ≥ 1} . (28) A 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 |T̃m,0,(0)| = |T̃m,0,(1)| = 1, and |T̃m,1,(0,0)| = |T̃m,1,(0,1)| = |T̃m,1,(0,2)| = |T̃m,1,(1,0)| = |T̃m,1,(1,1)| = |T̃m,1,(1,2)| = 1. We next prove the inductive hypothesis that, for K ≥ 2 and when q0, q1, ..., qK satisfying (26), there is
|T̃m,K,(q0,q1,...,qK)| ≥ 2 2K−2 · |T̃m,K−1,(q0,q1,...,qK−1)| . (29)
To see this, we will next show that ∀T ∈ T̃m,K−1,(q0,q1,...,qK−1), we can generate enough number of depth-K trees in T̃m,K,(q0,q1,...,qK) 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 are nonisomorphic, this will allow us to lower-bound the total number of trees in T̃m,K,(q0,q1,...,qK).
Consider the set of binary k-tuples, Pk = {(x1, ..., xk) : x1, ..., xk ∈ B}, of cardinality 2k. As T ∈ T̃m,K−1,(q0,q1,...,qK−1), we know that ∀τ ∈ PK−1, |WK−1(T ; τ)| ≥ 1. This means that ∀τ ∈ Pk, there exists at least one leaf node in T such that the path from the root node to this node consists of a sequence of nodes with features given by τ . We call any such node a node under τ . The total number of the children of all nodes under τ is thusm·|WK−1(T ; τ)| ≥ m. Thus, the total number of children with feature 0 of all nodes under τ is bounded between 0 andm·|WK−1(T ; τ)|. Conversely, for any 2K−1-tuple of non-negative integers, (q̄K,τ )τ∈PK−1 , which satisfy ∀τ ∈ PK−1, 1 ≤ q̄K,τ ≤ m · |WK−1(T ; τ)| − 1 can be “realized” by at least some depth-K tree T ′ obtained by appending children to the leaf nodes of T , in the sense that ∀τ = (x1, ..., xK−1) ∈ PK−1, there is WK(T ′; (x1, ..., xK−1, 0)) = q̄K,τ and WK(T ′; (x1, ..., xK−1, 1)) = m · |WK−1(T ; τ)| − q̄K,τ , and hence T ′ ∈ Tm,K,(q0,...,qK−1,q̄K), with q̄K = ∑ τ∈PK−1 q̄K,τ . Because of the requirement that 1 ≤ q̄K,τ ≤ m · |WK−1(T ; τ)|−1, we further have that ∀τ ′ ∈ PK ,WK(T ′, τ ′) ≥ 1, which implies that T ′ ∈ T̃m,K,(q0,...,qK−1,q̄K). Therefore, for some fixed qK , in order to lower-bound the cardinality of T̃m,K,(q0,...,qK) by that of T̃m,K−1,(q0,...,qK−1), it is sufficient to show a lower bound (which
is uniform for all T ∈ T̃m,K−1,(q0,q1,...,qK−1)) on the number of 2K−1-tuples, (qK,τ )τ∈PK−1 , which satisfy
qK = ∑
τ∈PK−1
qK,τ
∀τ ∈ PK−1, 1 ≤qK,τ ≤ m · |WK−1(T ; τ)| − 1 (30)
A simple bound can be obtained in the following way. For every such T , we sort the 2K−1-tuples in PK−1 in ascending order of |WK−1(T ; ·)|, and define P′K−1,T to be the subset of the first 2K−2 of these elements according to this order. Thus, for example, ∀τ ∈ P′K−1,T ,∀τ ′ ∈ PK−1 \ P′K−1,T , there is |WK−1(T ; τ)| ≤ |WK−1(T ; τ ′)|. As a consequence, we have ∑ τ∈P′K−1,T |WK−1(T ; τ)| ≤ ∑ τ∈PK−1\P′K−1,T
|WK−1(T ; τ)|, and so ∑ τ∈P′K−1,T |WK−1(T ; τ)| ≤ 12 ∑ τ∈PK−1 |WK−1(T ; τ)| = 1 2m
K−1 ≤∑ τ∈PK−1\P′K−1,T |WK−1(T ; τ)|.
Lemma 5. Let K ≥ 2 and qK satisfy (26). Then for all choices of the 2K−2-tuple of integers, (q̄K,τ )τ∈P′K−1,T , such that ∀τ ∈ P ′ K−1,T , q̄K,τ = 1 or 2, we can complete it into at least one 2K−1-tuple of integers, (q̄K,τ )τ∈PK−1 , which satisfy (30).
Proof of Lemma 5: For any such 2K−2-tuple, (q̄K,τ )τ∈P′K−1,T , in order to satisfy the constraints of (30), it is sufficient to find another 2K−2 integers, (q̄K,τ )τ∈PK−1\P′K−1,T , which satisfy∑
τ∈PK−1\P′K−1,T
q̄K,τ =qK − ∑
τ∈P′K−1,T
q̄K,τ (31)
∀τ ∈ PK−1 \ P′K−1,T , 1 ≤q̄K,τ ≤ m · |WK−1(T ; τ)| − 1 (32)
On one hand, since q̄K,τ = 1 or 2, ∀τ ∈ P′K−1,T , there is qK − 2K−1 ≤ qK − ∑ τ∈P′K−1,T
q̄K,τ ≤ qK − 2K−2. On the other hand, with the only other constraint being (32), it is possible to find (q̄K,τ )τ∈PK−1\P′K−1,T such that ∑ τ∈PK−1\P′K−1,T equals any integer between 2K−2
and m · ∑ τ∈PK−1\P′K−1,T
|WK−1(T ; τ)| − 2K−2, and hence any integer between 2K−2 and m · 12m K−1 − 2K−2 = 12m K − 2K−2. Hence, as long as 2K − 2K−2 ≤ qK ≤ 12m
K , which is the assumption of (26), Lemma 5 holds true.
Lemma 5 implies that ∀T ∈ T̃m,K−1,(q0,q1,...,qK−1), there are at least 22 K−2
distinct choices of 2K−1-tuples (qK,τ )τ∈PK−1 that satisfy the constraint of (30), and hence at least 2
2K−2 nonisomorphic trees in T̃m,K,(q0,q1,...,qK−1,qK) obtained by appending children to the leaf nodes of T . This proves the inductive hypothesis. Hence, we have
|T̃m,K,(q0,q1,...,qK)| ≥ K∏ k=2 22 k−2 = 22 K−1−1 , (33)
which implies Lemma 4.
Since m ≥ 2 by assumption, 12m K − (2K − 2K−2) grows exponentially in K. This proves Proposition 5.

heading: J PROOF OF PROPOSITION 6
text: Since the number of walks of a particular type that has length at most k is completely determined by the rooted aggregation tree structure of depth k, it is straightforward to see that all egonets in the same equivalence class induced by k 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.
For the second part of the claim pertaining to GA-MLPs, we assume for simplicity that X = B = {0, 1}, as the extension to the general case is straightforward but demanding heavier notations. Following the strategy in the proof of Proposition 5, it is sufficient to find exponentially-in-k many choices of the tuple (q0, q1, ..., qk), with 0 ≤ qk ≤ mk, such that the image of Tm,k,(q0,q1,...,qk) (as defined in (25)) under fk contains exponentially-in-k many values.
To make it simpler to refer to different nodes in the tree, we index each node in a rooted tree by a tuple of natural numbers: for example, the index-tuple [1, 3, 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 is 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, it suffices to specify the node features of all nodes under one such way of indexing.
Given x1, ..., xk ∈ B, we consider a set of depth-k full m-ary trees that satisfy the following: ∀k′ ≤ k − 1 and l1, ..., lk′ ∈ [m], x[l1,l2,...,lk′ ] = xk′ if l1 = 1 and ¬xk′ if l1 > 1. Note that these trees satisfy, for k′ ≤ k − 1, qk′ = mk ′−1 if xk′ = 0 and qk′ = (m − 1)mk ′−1 if xk′ = 1. Thus, ∀l2, ..., lk ∈ [m], the node [1, l2, ..., lk] is under the path τ = (x1, ..., xk) if and only if x[1,l2,...,lk] = xk, whereas for l1 > 1, the node [l1, l2, ..., lk] is not under the path τ regardless of the feature of [1, l2, ..., lk]. Therefore, fk(G[i]) = |Wk(G[i]; (x1, ..., xk))| equals the number of node of feature xk among the set of mk−1 nodes, {[1, l2, ..., lk]}l2,...,lk∈[m]. Hence, if for k′ ≤ k − 1, we set qk′ = mk ′−1 if xk′ = 0 and qk′ = (m − 1)mk ′−1 if xk′ = 1, then choosing any qk between mk−1 and (m− 1)mk−1, we have that for every integer between 0 and mk−1, there exists a tree T in Tm,k,(q0,...,qk) such that fk(T ) equals this integer. Since there are (m − 2)mk−1 choices of qk (and therefore the tuple (q0, ..., qk)) and mk−1 + 1 values in the image of Tm,k,(q0,...,qk) under fk, this proves the proposition.

heading: K PROOF OF PROPOSITION 1
text: We will first prove that the pair of graphs cannot be distinguished by any GA-MLP with Ω ⊆ {Ak}k∈N. 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 ′ ∈ R14×1 both being the all-1 vector. Moreover, ∀i ∈ [14],
(AkX)i = wk(i) , ((A ′)k(X ′))i = w ′ k(i) (34)
where we use wk(i) and w′k(i) to denote the numbers of walks (allowing backtracking) of length k starting from node i in graphs G and G′, respectively. Thus, to show that any GA-MLP with Ω ⊆ {Ak}k∈N necessarily returns the same output on G and G′, it is sufficient to show that ∀k ∈ N, AkX = (A′)k(X ′), and therefore sufficient to show that ∀k ∈ N and ∀i ∈ [14], there is wk(i) = w′k(i). In fact, we will prove the following lemma:
Lemma 6. ∀k ∈ N, wk(i) =w ′ k(i), ∀i ∈ [14] (35)
wk(1) =wk(2) (36) wk(3) + wk(9) =wk(6) + wk(8) (37) wk(5) + wk(7) =wk(4) + wk(10) (38)
Proof of Lemma 6: We prove this lemma by induction. For the base case, we have that w0(i) = w′0(i),∀i ∈ [14]. Next, we assume that (35) - (38) hold for some k ∈ N and prove it for k + 1. A first property to note is that ∀k ∈ N, wk+1(i) = ∑ j∈N (i) wk(j) and w ′ k+1(i) = ∑ j∈N ′(i) w ′ k(j), where we use N (i) and N ′(i) to denote the neighborhood of i in G and G′, respectively. To show (35) for k + 1, we look at each node separately:
• i = 1 wk+1(1) =wk(3) + wk(5) + wk(7) + wk(9)
=wk(5) + wk(6) + wk(7) + wk(8) =w′k(5) + w ′ k(6) + w ′ k(7) + w ′ k(8) =w′k+1(1)
(39)
• i = 2 wk+1(2) =wk(4) + wk(6) + wk(8) + wk(10)
=wk(3) + wk(4) + wk(9) + wk(10) =w′k(3) + w ′ k(4) + w ′ k(9) + w ′ k(10) =w′k+1(2)
(40)
• i = 3 wk+1(3) =wk(1) + wk(11) + wk(12)
=wk(2) + wk(11) + wk(12) =w′k(2) + w ′ k(11) + w ′ k(12) =w′k+1(3)
(41)
• i = 4 wk+1(4) =wk(2) + wk(13) + wk(14)
=w′k(2) + w ′ k(13) + w ′ k(14) =w′k+1(4)
(42)
• i = 5 wk+1(5) =wk(1) + wk(13)
=w′k(1) + w ′ k(13) =w′k+1(5)
(43)
• i = 6 wk+1(6) =wk(2) + wk(11)
=wk(1) + wk(11) =w′k(1) + w ′ k(11) =w′k+1(6)
(44)
• i = 7 wk+1(7) =wk(1) + wk(13)
=w′k(1) + w ′ k(13) =w′k+1(7)
(45)
• i = 8 wk+1(8) =wk(2) + wk(12)
=wk(1) + wk(12) =w′k(1) + w ′ k(12) =w′k+1(8)
(46)
• i = 9 wk+1(9) =wk(1)
=wk(2) =w′k(2) =w′k+1(9)
(47)
• i = 10 wk+1(10) =wk(2)
=w′k(2) =w′k+1(10)
(48)
• i ∈ {11, ..., 14} For each of these i’s, N (i) = N ′(i). Therefore,
wk+1(i) = ∑
j∈N (i)
wk(j)
= ∑
j∈N ′(i)
w′k(j)
=w′k+1(i)
(49)
Next, for (36) - (38) at k + 1,
wk+1(1) =wk(3) + wk(5) + wk(7) + wk(9)
=wk(4) + wk(6) + wk(8) + wk(10)
=wk+1(2)
(50)
wk+1(3) + wk+1(9) =2wk(1) + wk(11) + wk(12)
=2wk(2) + wk(11) + wk(12)
=wk+1(6) + wk+1(8)
(51)
wk+1(5) + wk+1(7) =2wk(1) + wk(13) + wk(14)
=2wk(2) + wk(13) + wk(14)
=wk+1(4) + wk+1(10)
(52)
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 5), 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 1 and 2 in G are both {3, 2, 2, 1}m, while their rooted aggregation trees in G′ are {2, 2, 2, 2}m and {3, 3, 1, 1}m, respectively.

heading: L EXPERIMENT DETAILS
text: L.1 SPECIFIC ARCHITECTURES
In Section 6, we show experiments on several tasks to confirm our theoretical results with several related architectures. Here are some explanations for them:
• GIN: Graph Isomorphism Networks proposed by Xu et al. (2019). In our experiment of counting attributed walks, we take the depth of GIN as same as the depth of target walks. The number of hidden dimensions is searched 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 a variant with Jumping Knowledge (Xu et al., 2018).
• sGNN: Spectral GNN proposed by Chen et al. (2019b), which can be viewed as a learnable generalization of power iterations on a collection of operators. While the best performing variant utilizes the non-backtracking operator on the line graph, for a fairer comparison with GA-MLPs, we choose a variant with the base collection of operators being {I, A,A2} 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 attributed walks, we choose the operators from {I, Āk{ }}. 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, Āk{ }, H̃
k} where H̃ 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 learning rate selected from {0.1, 0.02, 0.01, 0.005, 0.001, 0.0001}. Additionally, we use Batch Normalization (Ioffe & Szegedy, 2015) in community detection after propagating through each operator, following the normalization strategy from Chen et al. (2019b). We choose ϕ to be the identity function.
L.2 BETHE HESSIAN
The Bethe Hessian matrix is defined as
H(r) := (r2 − 1)I − rA+D.
with r being a flexible parameter. In SBM, an optimal choice is rc = √ c, where c is the average degree. Spectral clustering (Saade et al., 2014) can be performed by computing the eigenvectors associated with the negative eigenvalues of H(rc) to 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 H̃ as
H̃ := κI −H(rc),
so that the smallest eigenvalues of H become the largest eigenvalues of H̃ . We choose κ = 8 in our experiments. For GA-MLP-H , we then let Ω = {I, H̃, ..., H̃K}.
L.3 RESULTS FOR GA-MLP-Ã(1) IN COMMUNITY DETECTION

Review summaries:
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. 

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.

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: