On the Ability of Graph Neural Networks to Model Interactions Between Vertices
Authors: Noam Razin
Tom Verbin
Nadav Cohen
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Networks
Expressivity
Interactions
Edge Sparsification
TL;DR: We theoretically quantify the ability of certain graph neural networks to model interactions between vertices, and develop, based on our theory, a simple and efficient edge sparsification algorithm.

Abstract: Graph neural networks (GNNs) are widely used for modeling complex interactions between entities represented as vertices of a graph. Despite recent efforts to theoretically analyze the expressive power of GNNs, a formal characterization of their ability to model interactions is lacking. The current paper aims to address this gap. Formalizing strength of interactions through an established measure known as separation rank, we quantify the ability of certain GNNs to model interaction between a given subset of vertices and its complement, i.e. between the sides of a given partition of input vertices. Our results reveal that the ability to model interaction is primarily determined by the partition's walk index --- a graph-theoretical characteristic defined by the number of walks originating from the boundary of the partition. Experiments with common GNN architectures corroborate this finding. As a practical application of our theory, we design an edge sparsification algorithm named Walk Index Sparsification (WIS), which preserves the ability of a GNN to model interactions when input edges are removed. WIS is simple, computationally efficient, and in our experiments has markedly outperformed alternative methods in terms of induced prediction accuracy. More broadly, it showcases the potential of improving GNNs by theoretically analyzing the interactions they can model.

On the Ability of Graph Neural Networks to Model Interactions Between Vertices
Noam Razin, Tom Verbin, Nadav Cohen
Tel Aviv University
{noamrazin, tomverbin) tau. ac.il, cohennadav@cs. tau il
Abstract
Graph neural networks (GNNs) are widely used for modeling complex interactions between entities represented as vertices of graph. Despite recent efforts theoretically analyze the expressive power of GNNs, formal characterization of their ability to model interactions is lacking. The current paper aims to address this gap. Formalizing strength of interactions through known as separation rank, we quantify the ability of certain GNNs to model interaction between given subset of vertices and its complement, i.e. between the sides of given partition of input vertices. Our results reveal that the ability model interaction is primarily determined by the partition's 's walk index graph-thear graph-theoretical characteristic defined by the number of walks originating from the boundary of the partition. Experiments with common GNN architectures corroborate this finding. As a practical application our theory. we design edge sparsification algorithm named Walk Index Sparsification (WIS), which preserves the ability of a GNN to model interactions when input edges are removed. WIS is simple, computationally efficient, and in experiments has markedly outperformed alternative methods in terms of induced prediction accuracy. More broadly, it showcases the potential of improving GNNs by theoretically analyzing the interactions they can model.
established measure
Introduction
Graph neural networks (GNNs) are family of deep learning architectures, designed to model complex interactions between entities represented as vertices of a graph. In recent years, GNNs have been successfully applied across wide range of domains, including social networks, biochemistry, and recommender systems (see, e.g., [36, 59, 45, 49, 96, 104, 101, 18]). Consequently, significant interest in developing mathematical theory behind GNNs has arisen.
One of the fundamental questions theory GNNs should address expressivity, which concerns the class of functions a given architecture can realize. Existing studies of expressivity largely fall into three categories. First, and most prominent, are characterizations of ability to distinguish non- isomorphic graphs [103, 74, 72, 70, 6, 15, 10. 17, 43, 42, 80], as measured by equivalence to classical Weisfeiler-Leman graph isomorphism tests [99]. Second, are proofs for universal approximation of continuous permutation invariant equivariant functions, possibly up to limitations in distinguishing some classes of graphs [73, 55, 25, 69, 3, 42]. Last, are works examining specific properties of GNNs such frequency response [77, 5] or computability of certain graph attributes, e.g. moments, shortest paths, and substructure multiplicity [35, 9, 26, 39, 69, 23, 17, 105].
A major drawback of many existing approaches in particular proofs of equivalence to Weisfeiler- Leman tests and those of universality - that they operate asymptotic regimes of unbounded
An implementation of WIS available httpa/////gttuubbcooomaararriiie
interactions.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

I
Ie
Interaction depth L GNN can model between and I
(L -)-k index of I:
# length walks from Cr
walk M1
walk 42
wall U4B
CI
Example: length walks
Figure 1: Illustration of our main theoretical contribution: quantifying the ability of GNNs to model interactions between vertices of an imput graph. Consider a partition of vertices 2"). illustrated on the left, and a depth L GNN with product aggregation (Section 3). For graph prediction. as illustrated on the right, the strength of interaction the GNN can model between I and Ie, measured via separation rank (Section 2.2), primarily determined by the partition's 's (L- 1)-walk index the number of length - walks emanating from Cz, which is the set of vertices with an edge crossing the partition. The same holds for vertex prediction, except that there walk index is defined while only considering walks ending at the larget vertex.
network width or depth. Moreover, to the best of our knowledge, none of the existing approaches formally characterize the strength of interactions GNNs can model between vertices, and how that depends on the structure of the input graph and the architecture of the neural network.
The current paper addresses the foregoing gaps. Namely, it theoretically quantifies the ability of fixed-size GNNs to model interactions between vertices, delineating the impact of the input graph structure and the neural network architecture (width and depth). Strength of modeled interactions is formalized via separation rank [12] - a commonly used measure for the interaction a function models between subset of input variables and its complement (the rest of the input variables). Given a function and a partition of its input variables, the higher the separation rank, the more interaction the function models between the sides the partition. Separation rank is prevalent in quantum mechanics, where it can be viewed as measure of entanglement [62]. It was previously used for analyzing variants of convolutional, recurrent, and self-attention neural networks, yielding both theoretical insights and practical tools [30, 33, 61, 62, 64, 100, 65, 85). We employ it for studying GNNs.
Key to our theory is widely studied correspondence between neural networks with polynomial non- linearity and tensor networks? [32, 29. 30, 34, 90, 61, 62, 7, 56, 57, 63, 64, 83, 100, 84, 85, 65]. We extend this correspondence, and use it analyze message-passinng We treat both graph prediction, where a single output is produced for an entire input graph, and vertex prediction, in which the network produces output for every vertex. For graph prediction, prove that the separation rank of a depth L GNN with respect to partition of vertices is primarily determined by the partition's (L- 1)-wak index-
GNNs with product aggregation.
characteristic defined to be the number of length L --1 1 walks originating from vertices with an edge crossing the partition. The same holds for vertex prediction, except that there walk index is defined while only considering walks ending at the target vertex. Our result, illustrated in Figure 1, implies that for a given input graph, the ability of GNNs to model interaction between a subset of vertices and its complement I", predominantly depends on the number of walks originating from the boundary between I and I". We corroborate this proposition through experiments with standard GNN architectures, such as Graph Convolutional Network (GCN) [59] and Graph Isoorphiss Network (GIN) [103].
graph-theoreticn
Our theory formalizes conventional wisdom by which GNNs can model stronger interaction between regions of the input graph that are more interconnected. More importantly, we show that it facilitates an edge sparsification algorithm that preserves the expressive power of GNNs (in terms of ability to model interactions). Edge sparsification concerns removal of edges from a graph for reducing computational and/or memory costs, while attempting to maintain selected properties of the graph (cf. [11, 93, 48, 20, 86, 98, 67, 24]). In the context of GNNs, our interest lies in maintaining prediction accuracy as the number of edges removed from the input graph increases. We propose an algorithm for removing edges, guided by our separation rank characterization. The algorithm, named Walk Index Sparsification (WIS), is demonstrated to yield high predictive performance for GNNs (e.g. GCN and GIN) over standard benchmarks of various scales, even when removing a significant portion of
TTnsor networks form a graphical language for expressing contractions of tensors muletidiimesional arrays. They are widely used for constructing compact representations of quantum states in areas of physics (see, e.g., (97, 79]).

---

edges. WIS is simple, computationally efficient, and in our experiments has markedly outperformed alternative methods in terms of induced prediction accuracies across edge sparsity levels. More broadly, WIS showcases the potential of improving GNNs by theoretically analyzing the interactions they can model, and we believe its further empirical investigation is promising direction for future research.
The remainder of the paper is organized as follows. Section 2 introduces notation and the concept of separation rank. Section presents the theoretically analyzed GNN architecture. Section theoretically quantifies (via separation rank) its ability to model interactions between vertices of an input graph. Section 5 proposes and evaluates WIS an edge sparsification algorithm for arbitrary GNNs, born from our theory. Lastly, Section 6 concludes. Related work is discussed throughout, and for the reader's ss convenience, is recapitulated in Appendix B.
2 Preliminaries
2.1 Notation
For N N, let [N] == (I,.... N). We consider undirected input graph g (V,E) with vertices V = [[]] and edges & C {} i,j E V). Vertices are equipped with features X = xDD) ( P. P
(x(1), x
one D_- di-deemssional feature vector per vertex (D₂ E N). For i E V. use. Miii f V: {i E E) denote its set of neighbors, and, as customary in the context of GNNs. assume the existence of all self-loops, i.e. E (i)) for all i E V (cf. [59, 50)). Furthermore, for I S V we (TI) == Ui)zN(ii be the neighbors of vertices in I, and Ie == V I be the complement I. We use Cr to denote the boundary of the partition (I. 1,), Le. the set of vertices with an edge crossing the partition, defined by Cj= == {i I (i) * 0] I :N()nZ + 0).² Lastly, we denote the number of length E N~0 walks from any vertex in I C V to any vertex in I C V by J). In particular, ()) = EieTjer ((())()))
Note that we focus on undirected graphs for simplicity of presentation. As discussed Section 4, our results are extended to directed graphs in Appendix D.
2.2 Separation Rank: A Measure of Modeled Interaction
A prominent measure quantifying the interaction a multivariate function models between subset of input variables and its complement (i.e. all other variables) is known as separation rank. The separation rank was introduced in [12), and has since been employed for various applications [51, 47, 13). It is also a common measure of entanglement, a profound concept in quantum physics quantifying interaction between particles [62]. In the context of deep learning, it enabled analyses of expressivity and generalization in certain convolutional, recurrent, and self-attention neural networks, resulting in theoretical insights and practical methods (guidelines for neural architecture design, pretraining schemes, and regularizers see [30, 33, 61, 62, 64, 100, 65, 85]).
Given a multivariate function f (R*=)~ + R, its separation rank with respect to a subset of input variables I S [NV] the minimal number of summands required to express where each summand is product of two functions - one that operates over variables indexed by I. and another that operates over the remaining variables. Formally:
Definition 1. The separation rank of f : (R) + R with respect to I C [N] is:
scp(f:Z)= = min
R E N20: E ()) .g..,....... ......"" ( (R | RR n() ..... ......())
(1R.))
RR.
s.t. S(X) = Σ r=1 Emm, (0) (X+) g (X
(1)
where X : (x()).... x (N)) Xx = (x(1) iez and Xz == (x) jeze. By convention, if is
identically zero then sep( IZ; = 0, and if the set on the right hand side of Equation (1) is empty then ()) co.
Due to the existence of self-loops, Cr is exactly the shared neighbors I and T f.e. Cr = N(I))N((I)) 'For E N20. a sequence of vertices io...., V is length / walk if (i } E E for all l' [I].
3

---

Interpretation If se f: = 1. the function is separable, meaning it does not model any inter- action between X, and XT,, i.e. between the sides of the partition (I,I"). Specifically. it can be represented as f(X) g(xx) g(Xx)) for some functions y and ø. In a statistical setting, where I is a probability density function, this would mean that Xr and X are statistically independent. The higher sep(f: I) is, the farther f is from separability, implying stronger modeling of interaction between XI and XT..
3 Graph Neural Networks
Modern GNNs predominantly follow the message-passing paradigm [45, 50), whereby each vertex is associated with a hidden embedding that updated according to its neighbors. The initial embedding of E V is taken to its input features: (( := x()) E RD=, Then,
depth L message-passing
GNN, common update scheme for the hidden embedding of i E V at layer / E [L] is:
h (1,s)
AGGREGATE (1 ((-1.)) j : EV()))
(2)
where {-B denotes a multiset, W(1) E RAXDD W(2) E RRxDD,
W(L) E Daxx are learnable weight matrices, with D2 E N being the network's width (i.e. hidden dimension), and AGGREGATE is a function combining multiple input vectors into a single vector. A notable special case is GCN [59], in which AGGREGATE performs weighted average followed by non-linear activation function (e.g. ReLU),² Other aggregation operators are also viable, egg. element-wise sum, max, or product (cf. [49, 53]). We note that distinguishing self-loops from other edges, and more generally, treating multiple edge types, is possible through the use of different weight matrices for different edge types [49, 88]. For conciseness, we hereinafter focus on the case of a single edge type. and treat multiple edge types in Appendix D.
After L layers, the GNN generates hidden embeddings (2,.1), ...., (L.VV) E RR,, For graph prediction, where single output is produced for the whole graph, the hidden embeddings are usually combined into a single vector through the AGGREGATE function. A final linear layer with weights ( E T 1x is then applied to the resulting vector. 6 Overall, the function realized by a depth graph prediction GNN receives an input graph 9 with vertex features X (x(2), (01
PRP,, and returns:
(graph prediction) (x))) = ( AGGREGATE| (( : VJ))
(3)
with 0 = (W())........ W(L), W denoting the network's ' learnable weights. For vertex prediction tasks, where the network produces an output for every & V, the final linear layer is applied to each (L.t) separately. That is, for a target vertex E V, the function realized by depth L vertex prediction GNN is given by:
(vertex prediction)
110.9.0 (X) = (L.0)
(4)
Our aim is to investigate the ability of GNNs to model interactions between vertices. Prior studies of interactions modeled by different deep learning architectures have focused on neural networks with polynomial non-linearity, building on their representation as tensor networks [32, 30, 34, 90, 61, 62, 7, 56, 63, 64, 83, 100, 84, 85, 65). Although neural networks with polynomial non-linearity are less common in practice, they have demonstrated competitive performance [28, 31, 91, 94, 27, 37, 53], and hold promise due to their compatibility with quantum computation [46, 14] and fully homomorphic encryption [44]. More importantly, their analyses brought forth numerous insights that were demonstrated empirically and led to development of practical tools for widespread deep learning models (with non- non-linearities such as ReLU).
Following the above, in our theoretical analysis (Section 4) consider GNNs with (element-wing product aggregation, which are polynomial functions of their inputs. Namely, the AGGREGATE operator from Equations (2) and (3) is taken to be:
AGGREGATE(2)) == xxEXX,
"In GCN, AGGREGATE also has access to the degrees of vertices, which are used for computing the averaging weights. We omit the dependence vertex degrees in our notation for conciseness.
"We treat the case of output dimension one merely for the sake of presentation. Extension of our theory (delivered in Section 4) to arbitrary output dimension is straightforward - the results hold as stated for each of the functions computing output entry.

---

where O stands for the Hadamard product and A' is a multiset of vectors. The resulting architecture can be viewed as a variant of the GNN proposed in [53], where it was shown to achieve competitive performance in practice. Central to our proofs are tensor network representations of GNNs with product aggregation (formally established in Appendix E), analogous to those used for analyzing other types of neural networks. We empirically demonstrate our theoretical findings on popular GNNs (Section 4.2), such as GCN and GIN with ReLU non-linearity, and use them to derive practical edge sparsification algorithm (Section 5).
We note that some of the aforementioned analyses of neural networks with polynomial non-linearity were extended to account for additional non non-linearisies, including ReLU, through constructs known as generalized tensor networks [29]. We thus believe our theory may be similarly extended, and regard this as an interesting direction for future work.
4 Theoretical Analysis: The Effect of Input Graph Structure and Neural Network Architecture on Modeled Interactions
In this section, we employ separation rank (Definition 1) to theoretically quantify how the input graph structure and network architecture (width and depth) affeet the ability of a GNN with product aggregation to model interactions between input vertices. We overview the main results and their implications in Section 4.1, while deferring the formal analysis to Appendix A due to lack of space. Section 4.2 provides experiments demonstrating our theory's 's implications on common GNNs, such as GCN and GIN with ReLU non-linearity.
4.1 Overview and Implications
Consider a depth L. GNN with width D, and product aggregation (Section 3). Given a graph G. any assignment to the weights of the network 0 induces a multivariate function - f(0.9) for graph prediction (Equation (3) and ((0.9.t) for prediction over given vertex E (Equation (4) (4))-wall whose variables correspond to feature vectors of input vertices. The separation rank of this function with respect C V thus measures the interaction modeled across the partition (I, I"), i.e. between the vertices in I and those in I The higher the separation rank is, the stronger the modeled interaction.
Key our analysis are the following notions of walk index, defined by the number of walks emanating from the boundary of the partition (I,I"), i.e. from vertices with an edge crossing the partition induced by (see Figure for an illustration).
Definition 2. Let C V. Denote by CI the set of vertices with edge crossing the partition (Z, Is), i.e. Cj = {i E I: : (i) nI + 0} U (j E I : :j) I o 0}, and recall that pr PC denotes the number of length / E N20 walks from any vertex in C7 to any vertex in J V. For L E N:
(graph prediction) we define the (L - 1-)-wwalkk index of I, denoted WI (I). be the number of length
walks originating from Cz, iee. WII-1(I) == PL PL-1 V); and
(vertex prediction) for t E V we define the (L - 1, t-alklk index of I, denoted WI,-1, to be the number of length L. walks from Cx that end at i.e. (II-1, PL-1(C1, (t)).
As our main theoretical contribution, we prove:
Theorem (informally stated). For all weight assignments 0 and E V:
(graph prediction) log (sg(sep(f (0.00) II) (log(Di) WII-1(I)) (I)).
(vertex prediction)
log(sep (f I)) (log(DA)) (I)-
Moreover, nearly matching lower bounds hold for almost all weight assignments. 7
The upper and lower bounds are formally established by Theorems 2 and 3 in Appendix A, respec- tively, and are generalized to input graphs with directed edges and multiple edge types in Appendix D. Theorem I implies that, the (I. 1) walk index of I in graph prediction and its (L 1, -alkk index in vertex prediction control the separation rank with respect to I, and are thus paramount for
Almost all in the sense of all weight assignments but of Lebesgue measure zero.
5

---

Low Walk Index
High Walk Index
1
22
I
D2
C
C
Low separation rank
High separation rank
Figure 2: Depth L GNNs can model stronger interactions between sides of partitions that have higher walk index (Definition 2). The partition (Zz, Zi) (left) divides the vertices into two separate cliques, connected by single edge. Only two vertices reside in Cz, the set of vertices with an edge crossing the partition. Taking for example depth L, = 3, the 2-walk index of I₁ is @(())) ) and its (2, f)-walk index is ((V))) for t E V. In contrast, the partition (Zz, I2) (right) equally divides the vertices in cach clique to different sides. All vertices reside in CT2, meaning the 2-walk index of I2 is @(IV 9) and its (2, w-akkk index is ((V))). for & V. Hence, both graph and vertex prediction scenarios, the walk index of I, relatively low compared to analysis (Section 1 and Appendix A) states that a higher separation rank can be attained with respect to Iz, meaning stronger interaction can be modeled across (Iz, Ii) than across (I,, I1). We empirically confirm this prospect in Section 4.2.
I2. Our
modeling interaction between I and I see Figure 2 for an illustration. It thereby formalizes the conventional wisdom by which GNNs can model stronger interaction between areas of the input graph that are more interconnected. We support this finding empirically with common GNN architectures (e.g. GCN and GIN with ReLU non-linearity) in Section 4.2.
One may interpret Theorem 1 as encouraging addition of edges to an input graph. Indeed, the theorem states that such addition can enhance the GNN's ability to model interactions between input vertices. This accords with existing evidence by which increasing connectivity can improve the performance of GNNs in practice (see, e.g., [40, 1].. However, special care needs to be taken when adding edges: it may distort the semantic meaning of the input graph, and may lead to plights known as over-smoothing and over-squashing [68, 78, 22, 1, 8). Rather than employing Theorem 1 for adding edges, we use select which edges to preserve in a setting where some must be removed. That is, we employ it for designing an edge sparsification algorithm. The algorithm, named Walk Index Sparsification (WIS), simple, computationally efficient, and in our experiments has markedly outperformed alternative methods in terms of induced prediction accuracy. We present and evaluate it in Section 5.
4.2 Empirical Demonstration
Our theoretical analysis establishes that, the strength of interaction GNNs can model across partition of input vertices primarily determined by the partition's 's walk index graph- -heorrttte character- istic defined by the number of walks originating from the boundary of the partition (see Definition 2). The analysis formally applies to GNNs with product aggregation (see Section 3), yet we empirically demonstrate that its conclusions carry over to various other passsae-passing GNN architectures, namely GCN [59], GAT [96], and GIN [103] (with ReLU non-linearity). Specifically, through controlled experiments, we show that such models perform better on tasks in which the partitions that require strong interaction are ones with higher walk index, given that all other aspects of the tasks are the same. A description of these experiments follows. For brevity, we defer some implementation details to Appendix H.2.
We constructed two graph prediction datasets, in which the vertex features of each input graph are patches of pixels from two randomly sampled Fashion-MNISS [102] images, and the goal is to predict whether the two images are of the same class. In both datasets, all input graphs have the same structure: two separate cliques with 16 vertices each, connected by a single edge. The datasets differ in how the image patches are distributed among the vertices: in the first dataset each clique holds all the patches of a single image, whereas in the second dataset each clique holds half of the patches from the first image and half of the patches from the second image. Figure 2 illustrates how
"Images are sampled such that the amount of positive and negative examples roughly balanced.

---

Table 1:
In accordance with our theory (Section 4.1 and Appendix A), GNNS better fit datasets in which the partitions (of imput vertices) that require strong interaction are ones with higher walk index (Definition 2). Table reports means and standard deviations, taken over five runs, train and test accuracies obtained by GNNs of depth 3 and width 16 on two datasets: one in which the essential partition - i.e. the main partition requiring strong interaction has low walk index, and another in which it has high walk index (sce Section 4.2 for detailed description of the datasets). For all GNNs, the train accuracy attained over the second dataset is considerably higher than that attained over the first dataset. Moreover, the better train accuracy translates to better test accuracy. See Appendix H.2 for further implementation details.
Essential Partition Walk Index
Low
High
Train Acc. (%)
70.4 + 1.7
81.4 + 2.0
GCN
Test Ace. (%)
52.7 = 1.9
66.2 + 1.1
Train Acc. (%)
82.8 1 2.6
88.5 1 1.1
GAT
Test Ace. (%)
69.6 = 0.6
72.1 + 1.2
Train Acc. (%)
83.2 + 0.8
94.2 + 0.8
GIN
Test Acc.
53.7 + 1.8
64.8 + 1.4
image patches are distributed in the first (left hand side of the figure) and second (right hand side of the figure) datasets, with blue and red marking assignment of vertices to images.
Each dataset requires modeling strong interaction across the partition separating the two images, referred to as the essential partition of the dataset. In the first dataset the essential partition separates the two cliques, thus it has low walk index. In the second dataset each side of the essential partition contains half of the vertices from the first clique and half of the vertices from the second clique, thus the partition has high walk index. For example illustrating the gap between these walk indices see Figure 2.
Table I reports train and test accuracies achieved by GCN, GAT, and GIN (with ReLU non-linearity) over both datasets. compliance with our theory, the GNNs fit the dataset whose essential partition has high walk index significantly better than they fit the dataset whose essential partition has low walk index. Furthermore, the improved train accuracy translates to improvements in test accuracy.
5 Practical Application: Expressivity Preserving Edge Sparsification
Section 4 theoretically characterizes the ability of GNN to model interactions between input vertices. It reveals that this ability is controlled by toaphthheoeetial property we call walk index (Definition 2). The current section derives a practical application of our theory, specifically, an edge sparsification algorithm named Walk Index Sparsification (WIS). which preserves the ability of GNN model interactions when input edges are removed. We present WIS, and show that it yields high predictive performance for GNNs over standard vertex prediction benchmarks of various scales, even when removing a significant portion of edges. particular, we evaluate WIS using GCN [59], GIN [103], and ResGCN [66] over multiple datasets, including: Cora [89], which contains thousands of edges, DBLP [16], which contains tens thousands of edges, and OGBN-ArXiv [52], which contains more than a million edges. WIS is simple, computationally efficient, and in our experiments has markedly outperformed alternative methods terms of prediction accuracy across edge sparsity levels. We believe its further empirical investigation is a promising direction for future research.
5.1 Walk Index Sparsification (WIS)
Running GNNs over large-scale graphs can be prohibitively expensive in terms of runtime and memory. A natural way to tackle this problem is edge sparsification removing edges from an input graph while attempting maintain prediction accuracy (cf. [67, 24I).
As opposed to edge rewiring methods that add or remove only few edges with the goal of improving prediction accuracy (e.g.. [106, 71. 95, 8J).
10 An alternative approach is to remove vertices from input graph (see, e.g., [60]. However, this approach is unsuitable for vertex prediction tasks, limit our attention to edge sparsification.
7

---

Algorithm 1 (Z. 1a-W Index Sparsification (WIS) (instance of a general scheme described Appendix F)
Input: 9 ---grphh. I. E N - GNN depth, N N number of edges to remove
Result: Sparsified graph obtained by removing N edges from g
for 7 = L, do
# per edge, compute walk indices of partitions induced by {t), for E V, after its removal for E (excluding self-loops) do initialize s ..... . 0) E RI remove from & (temporarily)
for every & E V, set s WII.- # == number of length L - 1 walks from Crp to t
add back to G end for # prune edge whose removal harms walk indices the least according to an order over (s(*) aee
for e E E, sort the entries of (()) in ascending order
let e' E argmaX.ge s( according to lexicographic order over tuples remove e' from G (permanently)
end for
Algorithm 2 1- Walk Index Sparsification (WIS) (efficient version of Algorithm for 2)
Input: g - -graph, .N E N - number of edges to remove
Result: Sparsified graph obtained by removing N edges from g
for ,,...,,N do for {i,j] E (excluding self-loops) do let degmin (i,j) min (()), WOD let degman (i, == max((w(() (NG)))) end for
# prune edge {i,j} E & with maximal deg (1, breaking ties using deg
(t,5)
let e' E argmax (degmin (i. degman (i.j)) according to lexicographic order over pairs
remove e' from G end for
Our theory (Section 4) establishes that, the strength of interaction a depth GNN can model across a partition of input vertices is determined by the partition's 's walk index, a quantity defined by the number of length L walks originating from the partition's boundary. This brings forth a recipe for pruning edges. First, choose partitions across which the ability to model interactions is to be preserved. Then, for every input edge (excluding self-loops), compute a tuple holding what the walk indices of the chosen partitions will be if the edge is to be removed. Lastly, remove the edge whose tuple maximal according to preselected order over tuples (e.g. an order based on the sum, min, or max of tuple's entries). This process repeats until the desired number of edges are removed. The idea behind the above-described recipe, which we call General Walk Index Sparsification, is that each iteration greedily prunes the edge whose removal takes the smallest toll in terms of ability to model interactions across chosen partitions - see Algorithm 3 in Appendix for a formal outline. Below describe specific instantiation of the recipe for vertex prediction tasks, which are particularly relevant with large-scale graphs, yielding our proposed algorithm - Walk Index Sparsification (WIS). promising avenue for future work.
Exploration of other instantiations is regarded
In vertex prediction tasks, the interaction between an input vertex and the remainder of the input graph is of central importance. Thus, it is natural to choose the partitions induced by singletons (i.e. the partitions ((4). V. (1)), where / E V)) as those across which the ability to model interactions is to be preserved. We would like to remove edges while avoiding significant deterioration in the ability to model interaction under any of the chosen partitions. To that end, we compare walk index tuples according to their minimal entries, breaking ties using the second smallest entries, and so
8

---

Cora (depth GCN)
DBLP (depth GCN)
OGBN-ArXiv (depth 3 GCN)
accuracy (96
test accuracy (9)
test: accuracy (%)
52
80-
+
rendoms
spectral
79
random
+
random
USS
spectral
LAWS (ours)
76
L-WI (ours)
L-WIS (ouns)
70
80
% of removed edges
of removed edges
% removed edges
Figure 3: Comparison GNN accuracies following sparsification input edges WIS, the edge sparsification algorithm brought forth by our theory (Algorithm 1), markedly outperforms alternative methods. Plots present test accuracies achieved by depth L = 3 GCN of width 64 over the Cora (left), DBLP (middle), and OGBN- ArXiv (right) vertex prediction datasets, with increasing percentage of removed edges (for each combination of dataset, edge sparsification algorithm, and percentage of removed edges. a separate GCN was trained and evaluated). WIS, designed to maintain the ability of GNN to model interactions between input vertices, compared against: (i) removing edges uniformly at random; (ii) a spectral sparsification method [93]; and (iii) an adaptation of UGS [24]. For Cora, we run both 2- 2-I, which is compatible with the GNN's depth, and 1 1-WIS, which can be viewed as approximation that admits a particularly efficient implementation (Algorithm 2). For DBLP and OGBN-ArXiv, due their larger scale only 1-WIS is evaluated. Markers and error bars report means and standard deviations, respectively. taken over ten runs per configuration. Note that 1-WIS achieves results similar to 2-WIS, suggesting that the efficiency it brings does not come at a significant cost in performance. Appendix H provides further implementation details and experiments with additional GNN architectures (GIN and ResGCN) and datasets (Chameleon. Squirrel, and Amazon Computers). Code for reproducing the experiment available at https: //gi thub. . com/noam aooamraziin, azin/ gnn_ interactions.
forth. This is equivalent to sorting (in ascending order) the entries of each tuple separately, and then ordering the tuples lexicographically.
Algorithm provides a self-contained description of the method attained by the foregoing choices. We refer this method as (L 1)-Wall Index Sparsification (WIS), where the "(L - 1)" indicates that only walks of length L - 1 take part in the walk indices. Since (L - 1))walk indices can be computed by taking the (L 1) power of the graph's adjacency matrix, (L - 1)-WIS runs in O(N(E log(L)) time and requires O(EE) V + ( memory, where N is the number of edges to be removed. For large graphs a runtime cubic in the number of vertices can be restrictive. Fortunately, 1-WIS, which can be viewed as an approximation for (L- LL-I)-WIS with L > 2, facilitates particularly simple and efficient implementation based solely on vertex degrees, requiring only linear time and memory- - see Algorithm 2 (whose equivalence to 1-WIS is explained in Appendix G). Specifically, 1-WIS runs in O(N(E) (V]) time and requires O(E)) [V/) memory.
5.2 Empirical Evaluation
Below an empirical evaluation of WIS. For brevity, we defer to Appendix H some implementation details, as well as experiments with additional GNN architectures (GIN and ResGCN) and datasets (Chamelcon [82]. Squirrel [82], and Amazon Computers [92]).
Using depth L = 3 GNNs (with ReLU non-linearity). we evaluate over the Cora dataset both 2- WIS, which is compatible with the GNNs' depth, and 1-WIS, which can be viewed as an efficient approximation. Over the DBLP and OGBN-ArXiv datasets, due to their larger scale only 1-WIS evaluated. Figure 3 (and Figure 8 in Appendix H) shows that WIS significantly outperforms the following alternative methods in terms of induced prediction accuracy: (i) baseline in which edges are removed uniformly at random; (ūi) a well- spectral algorithm [93] designed to preserve the spectrum of the sparsified graph's 's Laplacian; and (iii) an adaptation of UGS [24] - recent supervised approach for learning to prune edges." !I Both 2-WIS and 1-WIS lead to higher test accuracies, while (as opposed to UGS) avoiding the need for labels, and for training a GNN over the original (non monnspaariiiied) graph - a procedure which in some settings is prohibitively expensive in terms of runtime and memory. Interestingly. 1-WIS performs similarly to 2-WIS, indicating that the efficiency it brings does not come at a sizable cost in performance.
l1 "UGS [24] jointly prunes input graph edges and GNN weights. For fair comparison, we adapt it to only
remove edges.

---

Conclusion
6.1 Summary
GNNs are designed to model complex interactions between entities represented as vertices graph. The current paper provides the first theoretical analysis for their ability do so, We proved that, given a partition input vertices, the strength interaction that can be modeled between its sides is controlled by the walk inder a graph-theoretica. characteristic defined by the number of walks originating from the boundary of the partition. Experiments with common GNN architectures, e.g. GCN [59] and GIN [103], corroborated this result.
Our theory formalizes conventional wisdom by which GNNs can model stronger interaction between regions of the input graph that are more interconnected. More importantly, we showed that it facilitates a novel edge sparsification algorithm which preserves the ability of GNN to model interactions when edges are removed. Our algorithm, named Walk Index Sparsification (WIS), is simple, computationally efficient, and in our experiments has markedly outperformed alternative methods in terms of induced prediction accuracy. More broadly, WIS showcases the potential of improving GNNs by theoretically analyzing the interactions they can model.
6.2 Limitations and Future Work
The theoretical analysis considers GNNs with product aggregation, which are less common in practice (ef. Section 3). We empirically demonstrated that its conclusions apply to more popular GNNs (Section 4.2), and derived a practical edge sparsification algorithm based on the theory (Section 5). Nonetheless, extending our analysis additional aggregation functions a worthy avenue explore.
Our work also raises several interesting directions concerning WIS. naive implementation of (L - 1)-WIS has runtime cubic in the number of vertices (cf. Section 5.1). Since this can be restrictive for large-scale graphs, the evaluation Section 5.2 mostly focused on 1-WIS, which can be viewed as an efficient approximation of (L 1)-WIS (its runtime and memory requirements are linear- see Section 5.1). Future work can develop efficient exact implementations of (L - 1J-WIS (e.g. using parallelization) and investigate regimes where it outperforms 1-WIS in terms of induced prediction accuracy. Additionally, (L 1)-WIS a specific instantiation of the general WIS scheme (given in Appendix F), tailored for preserving the ability to model interactions across certain partitions. Exploring other instantiations, as well as methods for automatically choosing the partitions across which the ability to model interactions is preserved, are valuable directions for further research.
Acknowledgments and Disclosure of Funding
We thank Eshbal Hezroni for aid in preparing illustrative figures. This work was supported by Google Research Scholar Award, a Google Research Gift, the Yandex Initiative in Machine Learning. the Israel Science Foundation (grant 1780/21), the Tel Aviv University Center for AI and Data Science, the Adelis Research Fund for Artificial Intelligence, Len Blavatnik and the Blavatnik Family Foundation, and Amnon and Anat Shashua. NR is supported by the Apple Scholars in AI/ML PhD fellowship.
References
[1] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. International Conference on Learning Representations (ICLR), 2021.
[2] Arash Amini, Amin Karbasi, and Farokh Marvasti. Low-rank matrix approximation using point-wiss wise operators. IEEE transactions on information theory, 58(1):302-33 -10, 2011.
[3] Waiss Azizian and Mare Lelarge. Expressive power of invariant and cquivariant graph neural networks. International Conference Learning Representations (ICLR), 2021.
[4] Jimmy Lei Ba. Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv11607.064500 2016.
10

---

[5] Muhammet Balcilar, Renton Guillaume, Pierre Héroux, Benoit Gaüzère, Sébastien Adam, and Paul Honeine. Analyzing the expressive power of graph neural networks in spectral perspective. International Conference on Learning Representations (ICLR), 2021.
[6] Muhammet Balcilar, Pierre Héroux, Benoit Gauzere, Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In International Conference on Machine Learning (ICML), 2021.
[7] Emilio Rafacl Balda, Arash Behboodi, and Rudolf Mathar. A tensor analysis on dense connectivity via convolutional arithmetic circuits. Preprint, 2018.
[8] Pradeep Kr Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pages 1-8. IEEE, 2022.
[9] Pablo Barceló, Egor Kostylev, Mikael Monet, Jorge Pérez, Juan Reutter, and lubn-Pablo Silva. The logical expressiveness of graph neural networks. International Conference Learning Representations (ICLR), 2020.
[10] Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[11] Surender Baswana and Sandeep Sen. A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Random Structures & Algoritumss, 30(4):532-563, 2007.
[12] Gregory Beylkin and Martin J Mohlenkamp. Numerical operator calculus in higher dimensions. Proceed- ings of the National Academy of Sciences, 99(16):10246 10251, 2002.
[13] Gregory Beylkin, Jochen Gareke, and Martin Mohlenkamp. Multivariate regression and machine learning with sums of separable functions. SIAM Journal on Scientific Computing, 31(3):1840- 2009.
[14] Amandeep Singh Bhatia, Mandeep Kaur Saggi. Ajay Kumar, and Sushma Jain. Matrix product state-based quantum classifier. Neural computation, 31(7):149-11517, 2019.
[15] Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang. Pictro Lio, Guido F Montufar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[16] Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised inductive learning via ranking. International Conference on Learning Representations (ICLR), 2018.
[17] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
[18] Michael M Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. arXiv preprini urXiv:2104.13478, 2021.
[19] Richard Caron and Tim Traynor. The zero set of a polynomial. WSMR Report, pages 05-02, 2005.
[20] Alireza Chakeri, Hamidreza Farhidzadeh, and Lawrence O Hall. Spectral sparsification in spectral clustering. In 2016 23rd international conference on pattern recognition (icpr), pages 2301-2306. IHEE, 2016.
[21] Michail Chatzianastasis, Johannes F Lutzeyer, George Dasoulas, and Michalis Vazirgiannis. Graph ordering attention networks. Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2023.
[22] Deli Chen, Yankai I Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2020.
[23] Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph- graph-augmented mlps. International Conference on Learning Representations (ICLR), 2021.
[24] Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning (ICML), 2021.
11

---

[25] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomor- phism testing and function approximation with gnns. In Advances in Neural Information Processing Systems (NeurIPS). 2019.
[26]
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substruc- tures? In Advances Neural Information Processing Systems (NeurIPS), 2020.
[27] Grigorios G Chrysos, Stylianos Moschoglou, Giorgos Bouritsas, Yannis Panagakis, Jiankang Deng. and Stefanos Zafeiriou. P-nets: Deep polynomial neural networks. In Proceedings of the IEÉE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 7325-7335 2020.
[28] Nadav Cohen and Amnon Shashua. Simnets: A generalization of convolutional networks. Advances in Neural Information Processing Systems (NeurIPS). Deep Learning Workshop, 2014.
[291 Nadav Cohen and Amnon Shashua. Convolutional rectifier networks as generalized tensor dccompositions. International Conference on Machine Learning (ICML), 2016.
[30] Nadav Cohen and Amnon Shashua. Inductive bias of deep convolutional networks through pooling geometry. International Conference on Learning Representations (ICLR), 2017.
[31] Nadav Cohen, Or Sharir, and Amnon Shashua. Deep simnets. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[32] Nadav Cohen, Or Sharir, and Ammon Shashua. On the expressive power of deep learning: A lensor analysis. Conference On Learning Theory (COLT), 2016.
[33] Nadav Cohen, Or Sharir, Yoav Levine, Ronen Tamari, David Yakira, and Amnon Shashua. Analysis and design of convolutional networks via hicrarchical tensor decompositions. Intel Collaborative Research Institute for Computational Intelligence (ICRI-CI) Special Issue on Deep Learning Theory, 2017.
[34] Nadav Cohen, Ronen Tamari, and Amnon Shashua. Boosting dilated convolutional networks with mixed tensor decompositions. International Conference on Learning Representations (ICLR), 2018
[35] Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks learning graph topology. Advances in Neural Information Processing Systems (NeurIPS), 2019.
[36] David Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafacl Bombarell, Timothy Hirzel, Alán Aspuru-Guzie and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. Advances in neural information processing systems, 28, 2015.
[37] Timo Felser, Marco Trenti, Lorenzo Sestini, Alessio Gianelle, Davide Zuliani, Donatella Lucchesi, and Simone Montangero, Quantum-inspired machine learning on high-energy physics data, npj Quantum Information, 7(1):1-8, 2021.
[38] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arX3v:1903.022 02428, 2019.
[39] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), 2020.
[40] Johannes Gasteiger, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learning. Advances Neural Information Processing Systems (NeurIPS), 2019.
[41] Floris Geerts. The expressive power of kth-order invariant graph networks. arXiv preprint arXiv:2007. 10000007.233555 12035, 2020.
[42) Floris Geerts and Juan L Reutter. Expressiveness and approximation properties of graph neural networks. International Conference Learning Representations (ICLR), 2022.
[43] Floris Geerts, Filip Mazowiecki, and Guillermo Perez. Let's agree to degree: Comparing graph convolu- tional networks in the message-passing framework. In International Conference Machine Learning (ICML), 2021.
[44] Ran Gilad-Bachras Bachraa, Nathan Dowlin, Kim Laine, Kristin Lauter, Michael Nachrig, and John Werns- ing. Cryptonets: Applying neural networks to encrypted data with high throughput and accuracy. In International Conference on Machine Learning (ICML), 2016.
[45] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
12

---

[46] Edward Grant, Marcello Benedetti, Shuxiang Cao. Andrew Hallam, Joshua Lockhart, Vid Stojevic. Andrew G Green, and Simone Severini. Hierarchical quantum classifiers. npj Quantum Information, 4(1): 1-8, 2018
[47] Wolfgang HacKbusch. the efficient evaluation coalescence integrals population balance models. Computing, 78(2):145-159, 2006.
[48] Michael Hamann, Gerd Lindner, Henning Meyerhenke, Christian L Staudt, and Dorothea Wagner. cructure-preserving sparsification methods for social networks. Social Network Analysis and Mining, 6 (1):1-22, 2016.
[49] Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[50] William L Hamilton. Graph representation learning. Synthesis Lectures Artifical Intelligence and Machine Learning. 14(3)11-59, 2020.
[51] Robert J Harrison, George I Fann, Takeshi Yanai, and Gregory Beylkin. Multiresolution quantum chemistry in multiwavelet hases. In International Conference on Computational Science, pages 103-110. Springer, 2003.
[52] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[53] Chenqing Hua, Guillaume Rabusseau, and Jian Tang. High-order pooling for graph neural networks with tensor decomposition. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
[54] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International Conference on Machine Learning (ICML), 2015.
[55] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[56] Valentin Khrulkov, Alexander Novikov, and Ivan Oseledets. Expressive power of recurrent neural networks. International Conference on Learning Representations (ICLR), 2018.
[57] Valentin Khrulkov, Oleksii Hrinchuk, and Ivan Oseledets. Generalized tensor models for recurrent neural networks. International Conference on Learning Representations (ICLR), 2019.
[58] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11X1v:1412.6980, 2014.
[59] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR). 2017.
[60] Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 631 1--6,,662220 2006.
[61] Yoav Levine, Or Sharir, and Amnon Shashua. Benefits of depth for long-term memory recurrent networks. International Conference on Learning Representations (ICLR) Workshop, 2018.
[62] Yoav Levine, David Yakira, Naday Cohen, and Amnon Shashua. Deep learning and quantum entanglement: Fundamental connections with implications to network design. International Conference on Learning Representations (ICLR), 2018.
[63] Yoav Levine, Or Sharir, Nadav Cohen, and Amnon Shashua. Quantum entanglement in deep learning architectures. Physical review letters, 02666), 2019.
[64] Yoav Levine, Noam Wies, Or Sharir, Hofit Bata, and Amnon Shashua. Limits depth efficiencies of self-attention. Advances Neural Information Processing Systems (NeurIPS), 2020.
[65] Yoav Levine, Noam Wies, Daniel Jannai, Dan Navon, Yedid Hoshen, and Amnon Shashua. The inductive bias of in-context learning: Rethinking pretraining example design. International Conference on Learning Representations (ICLR), 2022.
[66] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint 277777,00,,,739 2020.
13

---

[67] Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Sgen: A graph sparsifier based graph convolutional networks. In Pacific-Asia Conference Knowledge Discovery and Data Mining, pages 275-287. Springer, 2020.
[68] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence (AAAI), 2018.
[69] Andreas Loukas. What graph neural networks cannot learn: depth vs width. International Conference on Learning Representations (ICLR), 2020.
[70] Andreas Loukas. How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information Processing Systems (NeurIPS). 2020.
[71] Dongsheng Luo, Wei Cheng. Wenchao Yu, Bo Zong, Jingehao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In Proceedings of the 14th ACM international conference on web search and data mining, pages 779-787, 2021.
[72] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[73] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International Conference on Machine Learning (ICML), 2019.
[74] Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.. 2019.
[75] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and leman go machine learning: The story so far. arXiv preprint 1:Xii::112.0999 099922.9999922... 2021.
[76] Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Fdu. Query-driven active surveying for collective classification. In 10th international workshop mining and learning with graphs, volume 8, page 1, 2012.
[77] Hoang NT and Takanori Machara. Revisiting graph neural networks: All have is low-pass filters. arXiv preprint
2019.
[78] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations (ICLR), 2020.
[79] Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of physics, 349:117-158, 2014.
[80] Pâl András Papp and Roger Wattenhofer. A theoretical comparison graph neural network extensions. International Conference on Machine Learning (ICML), 2022.
[81] Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVioo, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic diffcrentiation in pytorch. In NIPS-W. W, 2017.
[82] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. International Conference on Learning Representations (ICLR), 2020.
[83] Noam Razin and Naday Cohen. Implicit regularization deep learning may not be explainable by norms. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[84] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in tensor factorization. International Conference on Machine Learning (ICMI., 2021.
[85] Noam Razin, Asaf Maman, and Nadav Cohen. Implicit regularization in hierarchical tensor factorization and deep convolutional neural networks. International Conference on Machine Learning (ICML), 2022.
[86] Veeru Sadhanala, Yu-Xiang Wang. and Ryan Tibshirani. Graph sparsification approaches for laplacian smoothing. In Artificial Intelligence and Statistics, pages 1250-1259, PMLR, 2016.
[87] Venu Satuluri, Srinivasan Parthasarathy, and Yiye Ruan. Local graph sparsification for scalable clustering. In Proceedings of the 2011 ACM SIGMOD International Conference on Management of data, pages 721-732, 2011.
14

---

[88] Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European semantic web conference, pages 593-607. Springer, 2018.
[89] Prithviraj Sen, Galileo Namata, Mustafa Bilgic. Lise Getoor, Brian Galligher, and Tina Eliassi Eliassi-Rad. Collective classification in network data, Al magazine, 29(3):33-33, 2008.
[90] Or Sharir and Amnon Shashua. On the expressive power of overlapping architectures of deep learning. International Conference on Learning Representations (ICLR), 2018
[91] Or Sharir, Ronen Tamari, Nadav Cohen, and Amnon Shashua. Tensorial mixture models. arXiv preprini. 2016.
[92] Oleksandr Shehur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05860 2018.
[93] Daniel A Spielman and Nikhil Srivastava. Graph sparsification by effective resistances. SIAM Journal on Computing, 1913) 2011.
[94] E. Miles Stoudenmire. learning relevant features of data with multi-scale tensor networks. Quantum Science and Technology. 3(3)0334033, 2018.
[95] Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. International Conference on Learning Representations (ICLR), 2022.
[96] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations (ICiiitioonIRRR))) (ICLR), 2018.
[97] Guifré Vidal. Class of quantum many-body states that can be efficiently simulated. Physical review letters, (11(1 10501, 2008.
[98] Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel Yannakoudakis. Rank degree: An efficient algorithm for graph sampling. In 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM), pages 120-129. IEEE, 2016.
[99] Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI. Series, 2(9): 1968.
[100] Noam Wies, Yoav Levine, Daniel Jannai, and Amnon Shashua. Which transformer architecture fits my data? a vocabulary bottleneck in self-attention. International Conference on Machine Learning (ICML), 2021.
[101] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A compre- hensive survey on graph neural networks. IEEE transactions neural networks and learning systems, 32(1):4-24, 2020.
[102] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint urXiv:1708.07747, 2017.
[103] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Repressenations (ICLR), 2019.
[104] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983, 2018.
[105] Bohang Zhang, Shengjie Luo, Liwei Wang, and He. Rethinking the expressive power gnns via graph biconnectivity. International Conference on Learning Representations (ICLR), 2023.
[106] Cheng Zheng, Bo Zong, Wei Cheng. Dongjin Song, Jingchao Ni, Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. In International Conference on Machine Learning (ICML), 2020.
15

---

A Formal Analysis: Quantifying the Ability of Graph Neural Networks to Model Interactions
We begin by upper bounding the separation ranks GNN can achieve.
Theorem 2. For an undirected graph 9 and E V. let ((0 and ((0.9.t) be the functions realized by depth L graph and vertex prediction GNNs, respectively, with width Di, learnable weights and product aggregation (Equations (2) to (5)). Then, for any I S V and assignment of weights 0 it holds that:
(graph prediction)
log ((s((((((.))))))))))))))))) s log(D)) (00))((1pp--1))
(4PL-1(CZ,)) +1)
(6)
WTz 1(7)
(vertex prediction)
log log( (eep(F(....))I)))) Dn)(Dn) 4 1pL-1(CI,,t)
Proof sketch (proof in Appendix 1.2). Appendix E, we show that the computations performed by a GNN with product aggregation can be represented as tensor nefwork. In brief, a tensor network is a weighted graph that describes a sequence of arithmetic operations known as tensor contractions (see Appendices E.1 and E.2 for self-contained introduction to tensor networks). The tensor network corresponding to a GNN with product aggregation adheres to a tree structure - its leaves associated with input vertex features and interior nodes embody the operations performed by the GNN. Importing machinery from tensor analysis literature, we prove that sep( sep(f((.9); ((: Z) is upper bounded by a minimal cut weight in the corresponding tensor network, among cuts separating leaves associated with input vertices in I from leaves associated with input vertices in Ie. Equation (6) then follows by finding such a cut in the tensor network with sufficiently low weight. Equation (7) is established analogously.
A natural question is whether the upper bounds in Theorem 2 are tight, i.e. whether separation ranks close to them can be attained. We show that nearly matching lower bounds hold for almost all assignments of weights A. To this end, we define admissible subsets Cz, based on a notion of vertex subsets with repeating shared neighbors.
Definition 3. We say that I, C V have no repeating shared neighbors if every & E (ZZ) has only a single neighbor in each of I and J. i.e. (K(k) nz] = (N((k) ]J] 1. Definition 4. For I S V. we refer to C S Cr as an admissible subset of Cr I.J' C I with no repeating shared neighbors such that C = =N(IT' NNT'.. We use S(I) to denote the set comprising all admissible subsets of Cr:
of if there exist I' S
S(Z)= == {c C Cz C is an admissible subset of Cz}.
Theorem 3 below establishes that almost all possible values for the network's 's weights lead the upper bounds in Theorem 2 to be tight, up to logarithmic terms and to the number of walks from Cr being replaced with the number of walks from any single C E S(I). The extent to which Cr can be covered by an admissible subset thus determines how tight the upper bounds are. Trivially, at least the shared neighbors of any E I E I can be covered, since N (J) E S(I). Appendix C shows that for various canonical graphs all of Cr, or large part of it, can be covered by an admissible subset.
Theorem 3. Consider the setting and notation of Theorem 2. Given I C f. almost all assignments of weights iee for all but a set of Lebesgue measure zero, holds that:
(graph prediction)
log(sep (f (00.9) 2 max log(ac) PL- PL-I(C,V), CES(I)
(8)
(vertex prediction)
log(sep ((..5.0) > max log(oe,) PI, (1)), CES(I)
(9)
where:
D DPo(CCDD
if =
ac
(D - 1) -1--
if Lf 2
D
-
ac
(1 -1--1)P----0 (C,))
16

---

with D ;= min{Dr, Dr). If PL-I(C,VV = 0 or PL-I(C, (t}) 0. the respective lower bound (right hand side of Equation (8) or Equation (9)) is zero by convention.
Our proof follows line similar to that used in [64, 100, 65] for lower bounding the separation rank of self-attention neural networks. The separation rank of any f: (IR P. ))VI + R can be lower bounded by examining its outputs over a grid of inputs. Specifically, for M E N template vectors v(1), v(M) E R P=, we can create a grid tensor for f by evaluating it over each point in ((v(d)),.. ,.... v...,v(ddv v(div) 1)] 2 ..... =1 and storing the outcomes in tensor with [V] axes of dimension M each. Arranging the grid tensor as a matrix Bf)) where rows correspond to axes indexed by I and columns correspond to the remaining axes, we show that rank(B(()) S sep(f; I). The proof proceeds by establishing that for almost every assignment of 0, there exist template vectors with which log (B (f) and log(rank(BA ((..G.))) ( are greater than (or equal to) the right hand sides of Equations (8) and (9). respectively.
Proof sketch (proof in Appendix L.3).
Directed edges and multiple edge types Appendix D) generalizes Theorems 2 and 3 to the case of graphs with directed edges and an arbitrary number of edge types.
B Related Work
The expressivity of GNNs has been predominantly evaluated through ability to distinguish non-isomorphic graphs, as measured by correspondence to Weisfeiler-L (WL. graph isomorphism tests (see [75] for a recent survey). [103, 74] instigated this thread of research, establishing that message-passing GNNs are at most as powerful as the WL algorithm, and can match under certain technical conditions. Subsequently, architectures surpassing WL were proposed, with expressivity measured via higher-order WL variants (see, e.g., [74, 72, 25, 41, 6, 15, 10, 42, 17, 80]). Another line of inquiry regards universality among continuous permutation invariant or equivariant functions [73, 55, 69, 3, 42]. [25] showed that distinguishing non-isomorppic graphs and universality are, in some sense, equivalent. Lastly, there exist analyses of expressivity focused on the frequency response of GNNs [77, 5] and their capacity to compute specific graph functions, e.g. moments, shortest paths, and substructure counting [35, 9, 39, 69, 26, 23, 17].
Expressivity of GNNs
Although a primary purpose of GNNs is to model interactions between vertices. none of the past works formally characterize their ability to do so, as our theory does. 12 The current work thus provides a novel perspective on the expressive power of GNNs. Furthermore, a major limitation of existing approaches - in particular, proofs of equivalence to WL tests and universality - is that they often operate in asymptotic regimes of unbounded network width or depth. Consequently, they fall short of addressing which type of functions can be realized by GNNs of practical size. In contrast, we characterize how the modeled interactions depend on both the input graph structure and the neural network architecture (width and depth). As shown in Section 5, this facilitates designing an efficient and effective edge sparsification algorithm.
Measuring modeled interactions via separation rank Separation rank (Section 2.2) has been paramount to the study of interactions modeled by certain convolutional, recurrent, and self-attention neural networks. It enabled theoretically analyzing how different architectural parameters impact ex- pressivity [32, 29, 30, 34, 7, 90, 62, 61, 56, 57, 64, 100, 65) and implicit regularization [83, 84, 85). On the practical side, insights brought forth by separation rank led to tools for improving perfor- mance, including: guidelines for architecture design [30, 62, 64, 100], pretraining schemes [65], and regularizers for countering locality in convolutional neural networks [85]. We employ separation rank
In [21], the mutual information between the embedding of vertex and the embeddings of its neighbors was proposed as measure of interaction. However, this measure is inherently local and allows reasoning only about the impact of neighboring nodes on each other a GNN layer. contrast, separation rank formulates the strength of interaction the whole GNN models across any partition of an input graph's 's vertices.
We note that, over two-dinensional grid graph, message- message-passing GNN can be viewed as convolutional neural network with overlapping convolutional windows. Similarly, over chain graph. can viewed as a bidirectional recurrent neural network. Thus, for these special cases, our separation rank bounds (delivered in Section 4) extend those of [30.6 62. 56, 61]. which consider convolutional neural networks with oveerlalppingg convolutional windows and unidirectional recurrent neural networks.
17

---

for studying the interactions GNNs model between vertices, and similarly provide both theoretical insights and practical application edge sparsification algorithm (Section 5).
Edge sparsification Computations over large-scale graphs can be prohibitively expensive in terms of runtime and memory. As result, various methods were proposed for sparsifying graphs by removing edges while attempting to maintain structural properties, such as distances between ver- tices [11, 48], graph Laplacian spectrum [93, 86], and vertex degree distribution [98], or outcomes of graph analysis and clustering algorithms [87, 20]. Most relevant to our work are recent edge sparsifi- cation methods aiming preserve the prediction accuracy of GNNs as the number of removed edges increases [67, 24). These methods require training GNN over the original (non-sparsified) graph, hence only inference costs are reduced. Guided by our theory, in Section 5 we propose Walk Index Sparsification (WIS) - an edge sparsification algorithm that preserves expressive power in terms of ability to model interactions. WIS improves efficiency for both training and inference. Moreover, comparisons with the spectral algorithm of [93] and recent method from [24] demonstrate that WIS brings about higher prediction accuracies across edge sparsity levels.
C Tightness of Upper Bounds for Separation Rank
Theorem 2 upper bounds the separation rank with respect to I C V of a depth L GNN with product aggregation. According to it, under the setting of graph prediction, the separation rank is largely capped by the (L 1)-walk index of I. i.e. the number of length L --1 1 walks from CI- the set of vertices with an edge crossing the partition (I, J.). Similarly, for prediction over t E V, separation rank is largely capped by the (L 1.t))walk -walk index of I, which takes into account only length L 1 walks from Cz ending at t. Theorem provides matching lower bounds, up to logarithmic terms and to the number of walks from Cz being replaced with the number of walks from any single admissible subset C E S(T) (Definition 4). Hence, the match between the upper and lower bounds is determined by the portion of Cz that can be covered by an admissible subset.
In this appendix, to shed light on the tightness of the upper bounds, we present several concrete examples on which a significant portion of Ct can be covered by an admissible subset.
Complete graph Suppose that every two vertices are connected by edge, i.e. E {(i,j) : i,j E V). For any non-empty I ç. V, clearly Cr = N(I) n (W = = case, Ci V e S(T), meaning Cr is an admissible subset of itself. To see is so, notice that for any i E E I", all vertices are neighbors of both I' := { and J := {i}. which trivially have no repeating shared neighbors (Definition 3). Thus, up logarithmic factor, the upper and lower bounds from Theorems 2 and 3 coincide.
V.
In this
Chain graph Suppose that E = ((i, 1] ( (I), V). For any non-empty I S V. at least half of the vertices in CT can be covered by an admissible subset. That is, there exists C' E S(I) satisfying C > 2- -C/]. For example, such C can be constructed algorithmically as follows. Let I', J = 0. Starting from A = 1, if (k, k + 1) C Cr and one of {k. + 1} is in I while the other is in Is, then assign I' + I' U (tk, k + 1I IJII). J' + J U ((k, + 13 nz), and k <- h + 3. That is, add each of {k, k + 1} to either if it is in I or J if is in I", and skip vertex k + 2. Otherwise, set k + k + 1. The process terminates once k > |V] 1. By construction, I' C I and J' II. implying that ((I''
S Cz. Due to the chain graph structure, I'UJ" CN(I")NN(T)) and I' and J' have repeating shared neighbors (Definition 3). Furthermore, for every pair of vertices from Cr added to I' and J', we can miss at most two other vertices from Cz. Thus, C = (((') is an admissible subset of Cr satisfying |C| > 2-1. (zl.
General graph For an arbitrary graph and non-empty I S V, an admissible subset of Cz can be obtained by taking any sequence of pairs (11. (IM E I x I' with no shared neighbors, in the sense that (A( (. n [M(im)) UN = 0 for all m A m' E [M]. Defining I' : (i,,... iM) } and J == (fi...., 1.s..-.JMM ..M.. by construction they do not have repeating shared neighbors (Definition 3), and so (Z') (TT") E S(T). In particular, the shared neighbors of each pair are covered by (V(I') (N""))) Le U M (im)) ( CN(I') (JJ').
18

---

D Extension of Analysis to Directed Graphs With Multiple Edge Types
In this appendix, we generalize the separation rank bounds from Theorems and 3 to directed graphs with multiple edge types.
Let g - (V,E,T) be a directed graph with vertices V [ edges & C {(i,)) : i,j V}. and a map T E - [Q] from edges to one of Q E N edge types. For i E V. let Nin (i) ==
E : (i,) E E) be its incoming neighbors and and Nou (i) = U E V: (i, E 8) be its outgoing neighbors. For I S V, we denote N (Z) == Lnez/N (t) and Nout(Z) == Viur (i). As customary in the context of GNNs, we assume the existence of all self-loops (ef. Section 2.1).
Message-passingg GNNs (Section 3) operate identically over directed and undirected graphs, except that in directed graphs the hidden embedding of a vertex is updated only according to its incoming neighbors. For handling multiple edge types, common practice is to use different weight matrices per type in the GNN's update rule (cf. [49, 88]). Hence, we consider the following update rule for directed graphs with multiple edge types, replacing that from Equation (2):
h h AGGREGATE
(1 (w(0).0))) h (- :j E Non (1))
(10)
where (W(1.)) E E DRXD)= rE[Q] and (W(1.)) E RR. DA De). (E(2.....).e1(()) are learnable weight ma- trices.
In our analysis for undirected graphs (Appendix A), central concept is Cr - the set of vertices with an edge crossing the partition induced by I C V. Due the existence of self-loops it is equal to the shared neighbors of I and I", i.e. Cj = N (I*). We generalize this concept to directed graphs, defining C7' to be the set of vertices with an incoming edge from the other side of the partition
induced by I, i.e. C7' == fi E I Nin (t) n I * 0) Ui E I (i) nI & 07. Due to the existence of self-loops it is given by CT = Nout (I) n Nout oout (I"). Indeed, for undirected graphs C7' = Cr.
With the definition of CT' in place, Theorem 4 upper bounds the separation ranks GNN can achieve over directed graphs with multiple edge types. A technical subtlety is that the bounds depend on walks of lengths ( L- 1, L 2....... O. while those in Theorem 2 for undirected graphs depend only on walks of length L - 1. As shown in the proof of Theorem 2, this dependence exists in undirected graphs as well. Though, in undirected graphs with self-loops, the number of length E N walks from Cz decays exponentially as / decreases. One can therefore replace the sum over walk lengths with walks of length L- (up to a multiplicative constant). By contrast, in directed graphs this is not true in general, e.g., when C contains only vertices with no outgoing edges (besides self-loops).
Theorem 4. For a directed graph with multiple edge types 9 and t E V, let f( and f(0.5.0) be the functions realized by depth L graph and vertex prediction GNNs, respectively, with width D learnable weights 0, and product aggregation ( (Equations (3) to (5) and (10)). Then, for any I C and assignment of weights 0 it holds that:
(Ein PL..
(graph prediction)
(eg(spp(((0.0):11 s log(Dn)
(11)
(vertex prediction)
log (og(sep(((0...)) ((0....) II) S log(Dn) EL-PPLLCC (t)).
(12)
Proof sketch (proof in Appendix 1.4). The proof follows a line identical to that of Theorem 2, only requiring adjusting definitions from undirected graphs directed graphs with multiple edge types. N
Towards lower bounding separation ranks, we generalize the definitions of vertex subsets with no repeating shared neighbors (Definition 3) and admissible subsets of Cr (Definition 4) to directed graphs.
Definition 5. We say that I C V have no outgoing repeating shared neighbors if every k e (Z) [J) has only single incoming neighbor in each of I and J.iee (k) =
W (l) NJ] =1
Definition 6. For I V, we refer to C C C an admissible subset of CT if there exist I' C I, J' C I with no outgoing repeating shared neighbors such that C = Nout (I') n None
We use S (T) to denote the set comprising all admissible subsets of CT:
S) = C is admissible subset of C7' }
19

---

Theorem 5 generalizes the lower bounds from Theorem 3 to directed graphs with multiple edge types. Theorem 5. Consider the setting and notation of Theorem Given I S V. for almost all assignments of weights 8, i.e. for all but set of Lebesgue measure zero, it holds that:
(grupk prediction)
(s))p((((.0));))) z
max log(ac) PI. PI.-ICCV)), CES-
(13)
(vertex prediction)
log(sep log(sep(f(0...)) (f(0.
2
max log(ac,)) - (t]), CES '(I)
(14)
where:
D D1/mo(C.V)
ifL=1 =1
(D 1000-1-PP--1 -)- .fT.22
D - - (1) +1
.f
if 2
with :- Di Dn). If PL-1(C,,V) V) 0 or PL-1(C, {t)) 0, the respective lower bound (right hand side of Equation (13) or Equation (14)) is zero by convention.
Proof sketch (proof in Appendix L.5). The proof follows line identical to that of Theorem only requiring adjusting definitions from undirected graphs to directed graphs with multiple edge types. I
E Representing Graph Neural Networks With Product Aggregation as Tensor Networks
In this appendix, we prove that GNNs with product aggregation (Section 3) can be represented through tensor networks -a a graphical language for expressing tensor contractions, widely used in quantum mechanics literature for modeling quantum states (cf. [97]). This representation facilitates upper bounding the separation ranks of a GNN with product aggregation (proofs for Theorem 2 and its extension in Appendix D), and is delivered in Appendíx E.3. We note that analogous tensor network representations were shown for variants of recurrent and convolutional neural networks [61, 62). For the convenience of the reader, we lay out basic concepts from the field of tensor analysis in Appendix E. and provide self-contained introduction to tensor networks in Appendix E.2 (see [79] for more in-depth treatment).
E.1 Primer Tensor Analysis
For our purposes, a tensor is simply a multi multi-dimensional array. The order of a tensor is its number of axes, which are typically called modes (e.g. vector is order one tensor and matrix is an order two tensor). The dimension of mode refers to its length, i.e. the number of values it can be indexed with. For order N E N tensor A R x with modes of dimensions D1..... DN E N, will denote by Ad,,....y its (d1,..., . dy) 'th entry, where (di,..., dx) E [Di] x x [Dw]
It is possible to rearrange tensors into matrices process known as matricization. The matricization matrix
of A with respect to I C [N]. denoted [A: E glleez D.x[l D, is its arrangement where rows correspond to modes indexed by and columns correspond to the remaining modes. <
Specifically, denoting the elements in I by i < < ||2i and those in Ie by Ji Jazz the matricization [A; I] holds the entries of A such that Adi.....dN is placed in row index [I9
1+ ++ (d,, - 1) Di, and column index + (d - 11 Dj..
Tensors with modes of the same dimension can be combined via contraction generalization of matrix multiplication. It will suffice to consider contractions where one of the modes being contracted is the last mode of its tensor.
Definition 7. Let A E R XDr B E D1 xD'r for orders N, N' E N and mode dimensions DI...., DN, Dí... Di...., D'y N satisfying D,, D'y, for some E [N]. The mode-n contraction of A with B, denoted A ,, B B D.x DD x......x.... xxDn41X...xx is given element-wise by:
Dn
(A kn B) B)d,............. dn d.....dd di Aoti...d
d Adi...dy BB -
20

---

Vector
Matrix
Order N Tensor
Vector-Matrix Multiplication
D
D2
Mv
D2
M
M E R RRixD
T
R X
D2
E 1RP
D2
N
Figure 4: Tensor network diagrams of (from left to right): a vector v E R matrix M E P2 order N E N tensor T E PDxxx and vector-matrix multiplication Mv E Di. The mode index associated with a leg's 's end point is specified in gray, and the weight of the leg, specified in black, determines the mode dimension.
for all di E [Dil....,dmy da-1 E (Da-1), E IDI....,,''.. E [Dati]...... dx E [Dx].
1D'v-1),det dx+1 E
For example, the mode-2 contraction of A E RDDxXD with B E Dixx boils down to multiplying A with B from the right, i.e. A 2 AB" T It oftentimes convenient jointly contract multiple tensors. Given an order N tensor A and M e NeN tensors (()), ,..., (M), we use A A= ( to
denote the contraction of A with B ..... ( in modes 1...., M, respectively (assuming mode dimensions are such that the contractions are well-defined)
E,2 Tensor Networks
tensor network is an undirected weighted graph T (Vr, Ey, wy) that describes a sequence of tensor contractions (Definition 7), with vertices VT, edges E,, and function mapping edges to natural weights wy E > N. We will only consider tensor networks that are connected. To avoid confusion with vertices and edges of GNN's input graph, and in accordance with tensor network terminology, we refer by nodes and legs to the vertices and edges of a tensor network, respectively.
Every node in tensor network is associated with tensor, whose order is equal to the number of legs emanating from the node. Each end point of a leg is associated with a mode index, and the leg's weight determines the dimension of the corresponding tensor mode. That is, end point of & a pair (A, n) E Vi x N, with n ranging from one to the order of A, and wy(e) is the dimension of A in mode A leg
either connect two nodes be connected to node one end and be loose on the other end. If two nodes are connected by a leg, their associated tensors are contracted together in the modes specified by the leg. Legs with loose end are called open legs. The number of open legs is exactly the order of the tensor produced by executing all contractions the tensor network, i.e. by contracting the tensor network. Figure presents exemplar tensor network diagrams of vector, matrix, order N E N tensor, and vector-matrix multiplication.
E.3 Tensor Networks Corresponding to Graph Neural Networks With Product Aggregation
Fix some undirected graph 9 and learnable weights (W ((L), W Let f (0.G) and f(0.S.t), for t V, be the functions realized by depth L graph and vertex prediction GNNs, respec- tively, with width Dr and product aggregation (Equations (2) to (5)). For X = (x. x(V)
RDx we construct tensor networks T(X) and (X)(() whose contraction yields ((09)(()) and ((0.0.)) (X), respectively. Both T(X) and (X) adhere to tree structure, where each leaf node associated with a vertex feature vector, i.e. one of x1) ((V)), x..) ((V)), and each interior node associated with weight matrix from WiI)..... ..... ((4) Wi or 5-tensor with modes of dimension
D,, holding ones on its hyper-diagonal and zeros elsewhere. We denote an order N E N tensor the
latter type by ((N) R Dr x Dr, i.e. dx...dxx
((N)
if ... = dy and (N)
dx....dx .x 0 otherwise
for all di....,de dN [Da].
21

---

(4.)
(X)
(()
3/11/93 11++1)
W
w(O
W
h(44)
((1hh)
h(t-)jm)
(4.1))
h (L.PD
(a)
(b)
(c)
Figure 5: Tensor network diagrams of the operations performed by GNNs with product aggregation (Section 3).
(a) Hidden embedding update (ef. Equations (2) and (5)): h = (W (t @ ... @ (W (t-1.at
where (ii) = {íi, (........ ..M
........................ ). for ( [4], V. (b) Output layer for graph prediction (ef. Equations (3) and (5)): (X) = w (h((4) ---- @ h(L.))) (c) Output layer for vertex prediction over t E V (ef. Equation (4)): fl0.9.0 (X) = (L.)) We draw nodes associated with ô-tensors as rectangles to signify their special (hyper-diagonal) structure, and omit leg weights avoid clutter (legs connected to h (0.1) x(1)
for i E V, have weight D2 while all other legs have weight Da))
Intuitively, T(X) and (X) embody unrolled computation trees, describing the operations per- formed by the respective GNNs through tensor contractions. Let (1.2) (jeN(() ( (((h))))) be the hidden embedding of i E V at layer E [L] (recall (0.5) x() for j E V), and denote .(ii) = 1.......... We can describe h(.0)) as the outcome of contracting each h ((-151)).... (jm)) with w(), i.e. computing ((-15)) ..... ((-Ijw), followed by contracting the resulting vectors with g((((()++) which induces product aggregation (see Figure 5(a)). Furthermore, in graph prediction, the output layer producing f(9.G) = (Ove (1..))
amounts to contracting hL..1), ..... (L.//l) with g(V++11) and subsequently contracting the resulting vector with W (see Figure 5(b)); while for vertex prediction, (00.. (X) (X) h (4,1) is
contraction of (L.t) with W()) (see Figure 5(c)).
Overall, every layer in a GNN with product aggregation admits tensor network formulation given the outputs of the previous layer. Thus, we can construct tree tensor network for the whole GNN by starting from the output - - Figure 5(b) for graph prediction or Figure 5(c) for vertex prediction ....., and i V. A technical subtlety is that each h (1.i) can appear multiple times during this procedure. In the language of tensor networks this translate to duplication of nodes. Namely, there are multiple copies of the sub-tree representing (1.1) in the tensor network - one copy per appearance when unraveling the recursion. Figure 6 displays examples for tensor network diagrams T(X) and (+t)
and recursively expanding nodes associated with (4.6) according Figure 5(a), for
We note that, due to the node duplication mentioned above, the explicit definitions of T(X) and (X) entail cumbersome notation. Nevertheless, we provide them in Appendix E. for the interested reader.
E.3.1 Explicit Tensor Network Definitions
The tree tensor network representing xx).))() consists of initial input level - the leaves of the tree comprising PL ({t), V) copies of (1) for each E V. We will use ((-7) to denote the copies of ()) for V and E (Li), V)). In accordance with the GNN inducing ((0.)) following the initial input level are L + layers. Each layer / E [L] includes two levels: one comprising (V,1 V) nodes standing for copies of ( and another containing 8-tensors - PL-(((i), V) copies of ((((())++1) per i E V. We associate each node in these layers with its layer index and vertex of the input graph i E V. Specifically, we will use W(l.,)) to denote copies of (!)) and V, and E N. In terms of connectivity, every leaf x(in) has leg to W(1..)) The rest of the connections between nodes are such that each sub-tree whose root is (1.6.2) represents (1.0, i.e. contracting the sub-tree results in the hidden
PV,
((.,,)) to denote copies of g(1(())+1)) for 1 E [T],
22

---

V = (1,2,3) 8 = [(1.2), (22))) (3.3))
(x)
f (X)
depth
depth L =
614
W
6
W:30
Wno
W100
W::0
W
h
(
8F3
8
W
W 33
W
W
W
W
We:
x
R
x
x
x
x
x
X
x
T(X)
(X)
Figure 6: Tensor network diagrams of (X) (left) and 7 (X) (right) representing ((0,9) (X) and f(o.E.)) respectively, for t = 1 E V, vertex features X (x(")
x x(11)), and depth L - 2 GNNs with product aggregation (Section 3). The underlying input graph G. over which the GNNs operate, is depicted at the top. We draw nodes associated with d-tensors rectangles to signify their special (hyper-diagonal) structure, and omit
leg weights to avoid clutter (legs connected to x()), x ( have weight D2 while all other legs have weight Dr). See Appendix E.3 for further details on the construction T(X) and ( (X), and Appendix E.3.1 for explicit formulations.
G
2
3
V = (1,2,3) & (012) (112),((11)))2222..8333))
((0.)(xX) depth 2
(())
depth 1. =
WWW
b223)
g212
h 12.2
8220
1 gesz
g1.11
W
W1ZZD
WZ-2Z
1V (22
M/)))
h(t.:
Wy U.L.
W
L2Z
WILLO
((LLL)
1y(22
x0.
T(X)
g())
Figure 7: Tensor network diagrams (with explicit node duplication notation) of T(X) (left) and ( (X) (right) representing (* (X) and (( (X), respectively, for 1 = E V. vertex features X = (x) x (DD). and depth L 2 GNNs with product aggregation (Section 3). This figure identical Figure except that uses the explicit notation for node duplication detailed Appendix E. Specifically, each feature vector, weight matrix, and 5-tensor is attached with an index specifying which copy it is (rightmost index in the superscript). Additionally, weight matrices and d-tensors are associated with layer index and vertex in V (except for the output layer 5-tensor T(X) and W())). See Equations (15) to (20) for explicit definitions of these tensor networks.
23

---

embedding for E V at layer 1 E [L] of the GNN inducing f(..0) Last, is an output layer consisting of two connected nodes: 5 (1))+ node, which has leg to every ò-tensor from layer L, and W()) node. See Figure 7 (left) for example of tensor network diagram representing ((0,9)(X, with this notation.
The tensor network construction for f(0.G.t) (X) is analogous to that for f(0.5) (X), comprising an initial input level followed by layers. Its input level and first L layers are structured the same, up to differences the number of copies for each node. Specifically, the number of copies of x is PL (fi), {t)) instead of PL(fi). V), the number of copies of W() is PL-1+1(V, {+}) instead of PL-1+1 V), and the number of copies of 8(1V()-1) is P {f)) instead of p V). for i E V and I E [L]. The output layer consists only of ( node, which connected to the 5-tensor in layer L corresponding to vertex t. See Figure 7 (right) for an example of a tensor network diagram representing ((0.9.0(()) (X) with this notation.
Formally, the tensor network producing f(0.9) denoted T(X) = (Vrix), ET(x), WT(x)) is defined by:
(x0)) :i V,y (po(tt), DI
VT(x)
(Wilia) :1 [ v, (oL- DIJ
(15)
{olln)); :1e [
(r.), ( VU)
( woo.
ET())= = 1/4 ((,())))) 1), ( (w(u))) 2)} :i E loltti)
((0 (),
| (pL-((t), VnJ
((Bl)A)) ((ii + 1), (w( 2)) 10,1-,,,ee,, (r. (r.. 1y)
{ ((6())))))) .i), (8 (). [N(1) + 1) : u (100111) 11 1), (w(") 2)
+1)
(16)
wr(x)(e) = Dz if (x(())) 1)) is an endpoint of e E & for some E V.V. E [pL((i), V)]
Dr. otherwise
(17)
[4], E V, and y E ((t)) V)]. is used to map a 5-tensor copy corresponding to i in layer / to a w copy, and (ii),. for E V and j [[]] denotes the ''th neighbor of i according to an ascending order (recall vertices are represented by indices from 1 to [V]).
where (1, Excist KEN')) (L-) V). for for/=
Similarly, the tensor network (x)()) = (271) (x)) producing ((0.). (X), is defined by:
{x :ie v, (oc(()) { (wils)) :1 [A], V.r (2-)) (M))
Vx(9())
(18)
(gl(n)): : [1 V, (10) (00,
{ [Wlo).
24

---

MAM (yri fic : v.y V (22(00)))
1l4e 1 ETOO)) = ((x(l))) (it
(w 42. (1)) 1)) 1,
(( ( [W(i) + 1), ( (W 2)) (0-
(22,
((0lLA))) [(() + 1), (w()) .2)]
(19)
DD if (x((m) 1) is an endpoint of Ey for some i V, [ps(fi), {t))
()))(x)(e)=
Dr otherwise
(20)
where (12 (+)=())==++0)
KENG) KENG) PL-r((k), (t)), for E [L], V, and y E (pL- (t))).
used map d-tensor copy corresponding to in layer I to W( copy.
Proposition 1 verifies that contracting T(X) and ( yields ((0.0) and f(o. (X), respec- tively.
(X),
Proposition 1. For an undirected graph G and t E V, let f(0.S) and (( be the functions realized by depth L graph and vertex prediction GNNs, respectively, with width D learn- able weights 0, and product aggregation (Equations (2) to (5)). For vertex features X = (x(1), ...,,,,,(,II,I x(IV)) E DDxxiV,, let the tensor networks T(X) (VT(X), ET()), (T))) and be as defined in Equations (15) to (20), respectively. Then, performing the contractions described by T(X) produces f(0.9) (X), and performing the contractions described by T() produces (0..
(x) - (X)I) (x)
Proof sketch (proof in Appendix 1.6). For both T(X) and (X), a straightforward induction over the layer 1 E [L] establishes that contracting the sub-tree whose root is g(1...)) results in h(.i) for all E V and 7, where (1,5) is the hidden embedding for i at layer / of the GNNs inducing f(0-5) and f(O.G."), given vertex features x()), ......... .....x( x..,,((V) xVD. The proof concludes by showing that the contractions in the output layer of (XX and (X) reproduce the operations defining ((0 (X) and (ee.5.)) (X) in Equations (3) and (4), respectively.
F General Walk Index Sparsification
Our edge sparsification algorithm - Walk Index Sparsification (WIS)- - was obtained as an instance of the General Walk Index Sparsification (GWIS) scheme described in Section 5, Algorithm formally outlines this general scheme.
G Efficient Implementation of 1- 1-la Index Sparsification
Algorithm 2 (Section 5) provides efficient implementation for 1-WIS, i.e. Algorithm I with L 2. In this appendix, we formalize the equivalence between the two algorithms, meaning, we establish that Algorithm 2 indeed implements 1-WIS.
Examining some iteration E [N] of 1-WIS, let E R! be the tuple defined by s; (L))((t))
Pi(Cre {t)) for V. Recall that Cit) is the set of vertices with an edge crossing the partition induced by {t). Thus, if is not isolated, then C(g Att)) and s, ((t)+(ft) Otherwise, if is isolated, then C(t) @ and
[V()))
= 0. 1-WIS computes for each E (excluding loops) a tuple s(e) E R holding its t'th entry what the value of (It))(ft))
would be to removed, for all E V. Notice that sle) and agree on all entries except for
i,j since removing from the graph only affects the degrees of i and j. Specifically, for i
25

---

Algorithm 3 (Z. - 1)- Generall Walk Index Sparsification (GWIS)
Input:
g graph
E - GNN depth
NEW N - number of edges to remove
Iy...., IM S - vertex subsets specifying walk indices to maintain for graph prediction
JI...., Tas C V and tq...., twr E V - vertex subsets specifying walk indices to maintain
with respect target vertices, for vertex prediction
ARGMAX - operator over tuples (s(*) E M+++ Daes that returns the edge whose tuple is
maximal according to some order
Result: Sparsified graph obtained by removing N edges from g
for 7 = N..... do
for every edge, compute walk indices of partitions after the edge's removal
for E (excluding self-loops) do
initialize g(t) = (O..... ..... 0) E R-++M' remove from 9 (temporarily)
for every m E [M]. set Smm WIL-1(Im) #= P=PL-ICCIm..) V) for every m E [M'] set (e) MM = Wi (Jm) = (C {bm))
add back to G end for
prune edge whose removal harms walk indices the least according to the ARGMAX operator let e' E ARGMAX=ees(c)
remove e' from G (permanently)
end for
either s = s; - -1=
(e) if the removal did not isolate i, or s = s; - = 0 if did (due to self-loops, if a vertex has a single edge to another then (W(i) 2, removing that
edge changes ((i)) from two to zero). As a result, for any (i,j)e'' = [('''') E &, after sorting the entries of (e) and s((') in ascending order we have that s(e') is greater in lexicographic order than s(e) and only the pair (min(IW((t)) (WG'I) max (W('))) is greater in lexicographic order than ([in((W(()) [W[)] max((W(i) (.) Therefore, every iteration E [N] Algorithm 2 and 1-WIS (Algorithm with L = 2) remove the same edge.
H Further Experiments and Implementation Details
H.1 Further Experiments
Figure supplements Figure 3 from Section 5.2 by including experiments with additional: (i) GNN architectures - GIN and ResGCN; and (ii) datasets - Chameleon, Squirrel, and Amazon Computers. Overall, our evaluation includes six standard vertex prediction datasets in which we observed the graph structure to be crucial for accurate prediction, as measured by the difference between the test accuracy of GCN trained and evaluated over the original graph and its test accuracy when trained and evaluated over the graph after all of the graph's edges were removed. We also considered, but excluded, the following datasets in which the accuracy difference was insignificant (less than five percentage points): Citeseer [89], PubMed [76], Coauthor CS and Physics [92], and Amazon Photo [92].
H.2 Further Implementation Details
We provide implementation details omitted from our experimental reports (Section 4.2, Section 5, and Appendix H.)). Source code for reproducing our results and figures, based on the Py PyTorch [81] and ToTch Geometric [38] frameworks, can be found at https: //tp:::///ttttt com http//ooaaaiii///////
26

---

Cora (depth GIN)
DBLP (depth GIN)
OGBN-ArXiv (depth GIN)
accuracy (%)
test accuracy (%)
test: accuracy (9)
80
83
25-
rendoms
spectral
75
random
+
random
UGS
spectral
20-
(ours)
(ours)
55
14WIS (ouns)
65
70
% of removed edges
of removed edges
% removed edges
Cora (depth 10 ResGCN)
DBLP (depth 10 ResGCN)
OGBN-ArXiv (depth 10 ResGCN)
79
test accuracy (%6
test accuracy (%6
64
test accuracy 1%)
70-
82
80-
random spectral
80-
05
75-
random spectral
rondom spectral
UCS
2 WIS (ours) WI5
USS
60-
LGS
20
40
60
80
100
20
40
60
80
100
40
60
80
200
of removed edges
of removed edges
of removed edges
Chameleon (depth 3 GCN)
Squirrel (depth 3 GCN)
Amazon Computers (depth 3 GCN)
70
60
tost accuracy (9)
test accuracy
60-
test accuracy
80-
50-
40-
spectral
spectral
spectra
40-
USS
USS
UGS
1-W15 (ours)
1-W15 (ours)
1-415 (ours)
20
40
80
100
20
00
80
100
40
00
100
% of removed edges
% of removed edges
% of removed edges
Figure 8: Comparison of GNN accuracies following sparsification of input edges WIS, the edge sparsification algorithm brought forth by our theory (Algorithm 1), markedly outperforms alternative methods. This figure supplements Figure 3 from Section 5.2 by including experiments with: (i) a depth L = GIN over the Cora, DBLP, and datasets; and fiãi depth L = 3 GCN over the Chameleon, Squirrel, and Amazon Computers datasets. Markers error bars report means and GIN, and over five runs per configuration
datasets: (ūi) depth L = 10 ResGCN over the Cora, DBLP, and OGBN-ArA ArXiv
standard deviations, respectively, taken over ten runs per configuration for GCN ResGCN (we use fewer runs due to the larger size of ResGCN). For further details see caption of Figure 3 as well as Appendix H.2.
gmn_ini interactions. All experiments were run either on single Nvidia RTX 2080 Ti GPU or single Nvidia RTX A6000 GPU.
H.2.1 Empirical Demonstration of Theoretical Analysis (Table 1)
Models All models used, í.e. GCN, GAT, and GIN, had three layers of width 16 with ReLU non- linearity. To ease optimization, we added layer normalization [4] after each one. Mean aggregation and a linear output layer were applied over the last hidden embeddings for prediction. As in the synthetic experiments of [1], each GAT layer consisted of four attention heads. Each GIN layer had its parameter fixed to zero and contained a two-layer feed-forward network, whose layers comprised a linear layer, batch normalization [54], and ReLU non-linearit..
Data The datasets consisted of 10000 train and 2000 test graphs. For every graph, we drew Then, depending on the
uniformly at random a label from {0, 13 and an image from chosen label, another image was sampled either from the same class (for label 1) or from all other classes (for label 0). We extracted patches of pixels from each image by flattening it into vector and splitting the vector 16 equally sized segments.
Optimization The binary cross-entropy loss was minimized via the Adam optimizer [58] with de- fault 31, 82 coefficients and full-batcher (i.e. every batch contained the whole training set). Optimiza-
27

---

tion proceeded until the train accuracy did not improve by at least 0.01 over 1000 consecutive epochs or 10000 epochs elapsed. The learning rates used for GCN, GAT, and GIN were 5 1003 10,3,, 10-3 and 10-2, respectively.
Hyperparameter tuning For each model separately, tune the learning rate we carried out five
runs (differing in random seed) with every value in the range (10-1, 5- 10 10-2, 5 10-3 10-3) over the dataset whose essential partition has low walk index. Since our interest resides in expressivity, which manifests in ability to fit the training set, for every model we chose the learning rate that led to the highest mean train accuracy.
H.2.2 Edge Sparsification (Figures and 8)
Adaptations to UGS [24] [24] proposed UGS as a framework for jointly pruning input graph edges and weights of a GNN. At high-level, UGS trains two differentiable masks, m, and ma, that are multiplied with the graph adjacency matrix and the GNN's weights, respectively. Then, after a certain number of optimization steps, a predefined percentage P3 of graph edges removed according to the magnitudes of entries in mg. and similarly, ps percent of the GNN's weights are fixed to zero according the magnitudes of entries in mgg This procedure continues in iterations, where each time the remaining GNN weights are rewinded to their initial values, until the desired sparsity levels are attained see Algorithms I and 2 in [24]. To facilitate fair comparison of our (1-IS edge sparsification algorithm with UGS, we make the following adaptations to UGS.
We adapt UGS to only remove edges, which is equivalent to fixing the entries in the weight mask my to one and setting Pa = 0 in Algorithm I of [24].
For comparing performance across a wider range of sparsity levels, the number of edges removed at each iteration is changed from 5% of the current number of edges to 5% of the original number of edges.
Since our evaluation focuses on undirected graphs, we enforce the adjacency matrix mask my to be symmetric.
Spectral sparsification [93] For Cora and DBLP, we used a Python implementation of the spectral sparsification algorithm from [93], based on the PyGSP library implementation." 14 To enable more efficient experimentation over the larger scale OGBN-ArXiv dataset, we used a Julia implementation based on that from the Laplacians library."
Models The GCN and GIN models had three layers of width 64 with ReL.U non-linearity. As in the experiments of Section 4.2, we added layer normalization [4] after each one. Every GIN layer had trainable c parameter and contained a two-layer feed-forward network, whose layers comprised linear layer, batch normalization [54], and ReLU non-linearity. For ResGCN, we used the implementation from [24] with ten layers of width 64. In all models, a linear output layer was applied over the last hidden embeddings for prediction.
Data All datasets in our evaluation are multi-class vertex prediction tasks, each consisting of a single graph. In Cora, DBLP, and OGBN-ArXiv, vertices represent scientific publications and edges stand for citation links. In Chameleon and Squirre,, vertices represent web pages on Wikipedia and edges stand for mutual links between pages. In Amazon Computers, vertices represent products and edges indicate that two products are frequently bought together. For simplicity, we treat all graphs as undirected. Table 2 reports the number of vertices and undirected edges in each dataset. For all datasets, except OGBN-ArXiv, we randomly split the labels of vertices into train, validation, and test sets comprising 80%, 10,, and 10% of all labels, respectively. For OGBN-ArXiv, we used the default split from [52].
Optimization The cross-entropy loss was minimized via the Adam optimizer [58] with default 31, 32 coefficients and full-batches (i.e. every batch contained the whole training set). Optimization proceeded until the validation accuracy did not improve by at least 0.01 over 1000 consecutive epochs or 10000 epochs elapsed. The test accuracies reported in Figure are those achieved during the epochs with highest validation accuracies. Table 3 specifies additional optimization hyperparameters.
14 See https://github. http:/ahabb..cm//ppel/tttt/////p
See http:/twww........apppaaaaaaaaaa jl.
28

---

Table 2: Graph size of each dataset used for comparing edge sparsification algorithms in Figures and 8. # of Undirected Edges
of Vertices
Cora
2,708
5,278
DBLP
17,716
52,867
OGBN-ArXiv
169,343
1,157,798
Chameleon
2,277
31,396
Squirrll
5,201
198,423
Amazon Computers
13,381
245,861
Table 3: Optimization hyperparameters used in the experiments of Figures 3 and 8 model and dataset,
Learning Rate
Weight Decay
Edge Mask Regularization UGS
5
10
10 10-2
DBLP
10
10
10
GCN
OGBN-ArXiv
10 3
10
Chameleon
10-3
10-4
10-2
Squirel
5 5-10-1
10-4
Amazon Computers
10
10
10
Cora
10-3
10-3
10-2
GIN
DBLP
10
10-3
10-2
OGBN-ArXiv
10-4
10-2
Cora
5-10-
10-3
10-4
ResGCN
DBLP
3-10-
10-4
10-4
OGBN-ArXiv
10-3
10-2
Hyperparameter tuning For each combination of model and dataset separately, we tuned the learning rate, weight decay coefficient, and edge mask & regularization coefficient for UGS, and applied the chosen values for evaluating all methods without further tuning (note that the edge mask l regularization coefficient is relevant only for UGS). In particular, we carried out grid search over learning rates {10-3, 5 10-4 10100 10-4, weight decay coefficients {10-3 10-1 03, and edge mask l regularization coefficients {10-2 10- 10-1). Per hyperparameter configuration, we ran ten repetitions of UGS (differing in random seed), each until of the input graph's edges were removed. At every edge sparsity level (0%, 5%, 10%,.... ..... 100%). in accordance with [24], we trained new model with identical hyperparameters, but a fixed edge mask, over each of the ten graphs. We chose the hyperparameters that led to the highest mean validation accuracy, taken over the sparsity levels and ten runs.
Due to the size of the ResGCN model, tuning its hyperparameters entails significant computational costs. Thus, over the Cora and DBLP datasets, per hyperparameter configuration we ran five repetitions of UGS with ResGCN instead of ten. For the large-scale OGBN-ArXiv dataset, we adopted same hyperparameters used GCN.
To allow more efficient experimentation, we compute the edge removal order of 2-WIS (Algorithm 1) in batches size 100. Specifically, at each iteration 2-WIS, instead removing the edge e' with maximal walk index tuple s(r'), the 100 edges with largest walk index tuples are removed. For randomized edge sparsification algorithms random pruning, the spectral sparsification method of [93], and the adaptation of UGS [24] - the evaluation runs for given dataset and percentage of removed edges were carried over sparsified graphs obtained using different random seeds.
Other
I Deferred Proofs
I.1 Additional Notation
For vectors, matrices, or tensors. parenthesized superscripts denote elements in a collection, egg. (a(1) E ERD while subscripts refer to entries, egg. Ad E R is the (di, d2)'th entry of A D.xDs A colon is used to indicate range of entries, e.g. and is the first d entries of
29

---

E RP. We use to denote tensor contractions (Definition 7), o to denote the Kronecker product, and @ to denote the Hadamard product. For P Nzo- the P'th Hadamard power operator denoted by o", i.e. I0" A d2 A for A E RDxxD, Lastly, when enumerating over sets of indices an ascending order assumed.
I.2 Proof of Theorem
We assume familiarity with the basic concepts from tensor analysis introduced in Appendix E, and rely on the tensor network representations established for GNNs with product aggregation in Ap- pendix E. Specifically, we use the fact that for any
(x(1), ..... (o.())).....)....... x(VD) E I P= there exist tree tensor networks T (XX) and (X) (described in Appendix E.3 and formally defined in Equa- tions (15) (20)) such that: (i) their contraction yields ((0,9)()) and ((0.).)) respectively (Proposition 1); and (ii) each of their leaves is associated with vertex feature vector, i.e. one of x(1), "00),,..,,())) x(V)), whereas all other aspects of the tensor networks do not depend on x(1), x()),.... x(I))
The proof proceeds as follows. In Appendix 1.2.1, by importing machinery from tensor analysis literature (in particular, adapting Claim 7 from [62]), we show that the separation ranks of f((,0) and ((e.9.)) can be upper bounded via cuts in their corresponding tensor networks. Namely, sep ( (0.9)) Z) is most the minimal multiplicative cut weight in T(X), among cuts separating leaves associated with vertices of the input graph in I from leaves associated with vertices of the input graph in I", where multiplicative cut weight refers to the product of weights belonging legs crossing the cut. Similarly, scp(f (())) I) is at most the minimal multiplicative cut weight in T among cuts of the same form. We conclude in Appendices 1.2.2 and 1.2.3 by applying this technique for upper bounding sep(f (f ((.)) I) and eep(f(0.S.)) ;I) 2). respectively, i.e. by finding cuts in the respective tensor networks with sufficiently low multiplicative weights.
1.2.1 Upper Bounding Separation Rank via Multiplicative Cut Weight in Tensor Network
In a tensor network T = (VT, WT), every JT S VT induces cut (JT, i.e. partition of the nodes into two sets. We denote by ET(TT) == ((u,e) E ET u E JT, E JJ) the set of legs crossing the cut, and defin the multiplicative cut weight of JT to be the product of weights belonging to legs (JT)). ie:.
w+ = II II (JT) wT(e).
For X (x()), ,...,,.. ()VD) E D. let T(X) and 7 (X) be the tensor networks corresponding to (00.0) (X) and f ((o.G.) (X) (detailed in Appendix E.3), respectively. Both T(X) and (X) adhere tree structure. Each Icaf node is associated with vertex feature vector (i.e. one of ,""),...,x' ((V)), while interior nodes are associated with weight matrices or ô-tensors. The latter are tensors with modes of equal dimension holding ones their hyper-diagonal and zeros elsewhere. The restrictions imposed by d-tensors induce a modified notion of multiplicative cut weight, where legs incident to the same d-tensor only contribute once to the weight product (note that weights of legs connected to the same ś-tensor are equal since they stand for mode dimensions).
Definition 8. For a tensor network T = (Vr,En WT) and subset of nodes TT C Vy. let (T(Tr) be the set of edges crossing the cut JG). Denote by (T(TT) C (T(T)) subset of legs containing for each 8-tensor in V/ only a single leg from (T(TT) incident to along with all legs in Ey (JT) not connected to 8-tensors. Then, the modified multiplicative cut weight of JT is:
-II w (ITT) := ILEEE wr(c).
Lemma establishes that (0.)) and sep( (1000,)) I) are upper bounded by the minimal modified multiplicative cut weights in T(X) and ( (X), respectively, among cuts separating leaves associated with vertices in I from leaves associated vertices in I
Lemma 1. For any X (x(1)....,
,.,,, ((I)) RDDI lei T(X) ET(x)),T(xX) WT(X) and (()(x) = (X) (x)) (x)) be the tensor network representations of f(0.9) and ((0.9.0) X) (described in Appendix E.3 and formally defined in Equations (15) to (20)), respectively.
30

---

Denote by VT(x) [ S VT()) and (x) [ S V)O()) the sets of leaf nodes in T(X) and
(X), respectively, associated with vertices from the input graph g. Formally:
VT(x) (x((m) VT(X: : I, (oL( VI]}.
(x) [ = (x((m) ())O : LiEIYY [pe(()), (f)]}}
Similarly, denote by VT(X) [I9] C VT(X) and (TWOX) _ (x) the sets of leaf nodes in T(X)
and (X), respectively, associated with vertices in I. Then, the following hold:
(graph prediction)
sep(f(0.0);1
min PVoO
w (+(()((T(T))
(21)
an VT (Tx))TTTTOS and VTo (29))
(vertex prediction) scp(f(0.8.0) 1
min
(x) (x) (T)()()))
I (x) SV (x) (1) (10))) and V oz) (1915
(22)
where (x) (FT(x)) the modified multiplicative cul weight of JT(X) in T(X) and Will (x)) (x)) is the modified multiplicative cut weight of ITO in (X) (Definition 8).
Proof. We first prove Equation (21). Examining T(X), notice that: by Proposition its contraction yields ((0.9) (X); (ii) it has a tree structure; and (iii) each of its leaves is associated with a vertex feature vector, iee. one of "..,..,,((1)) whereas all other aspects of the tensor network do not depend on x()), ....... x(1)) Specifically, for any X and X' the nodes, legs, and leg weights of T(X) and T(X') are identical, up to the assignment of features in the leaf nodes. Let F R2.xx-XD D. be the order (V. tensor obtained by contracting all interior nodes in T(X). The above implies that we may write (( (X) as a contraction of IF with x(1), "i..,,((IM),, x(M). Specifically, it holds that:
(( (x) = I *nElpL (2.1)) x (m(n))
(23)
for any X= (x (I))) E RDXM where [pr. (V. v) + V maps a mode index of F
to the appropriate vertex of 9 according T(X). Let f (I) == {n E [pL V)] p(n) E I} be the mode indices of FF corresponding to vertices in I. Invoking Lemma 2 leads to the following matricized form of Equation (23):
(00.9) (X) = (onen- (2) (ufnil)) T [= (Z]] (oNEm-1 (zg)((())(((()))
where denotes the Kronecker product.
R: We claim that ( S rank [F: [I)]- - To see it so, denote R = rank [F: Lonk[[F:)
(T)
and let !!!) ....,, ((() E R (2, and (1)) ( D2 be such that [F; 1 -
DR ul) (1(r)). Then, defining (r)) (RPb) [z| R and g(r) : (IR + R. for r E [R). as:
(r)) (X+) = (() , u(r)))
(Xz=)) (2op (lu(n)) u(r))
where X1 == (x(1)) and Xx= == (x(1) (eze)
JEZe, we have that:
p10.5) (x) (onep- EEe u(*) " 1) (2oe
n
wn)) (onEa- um?))
( (Xz) g(r) (Xz+).
Since sep(f(0.0): I) is the minimal number of summands in representation of this form of f(P.0) indeed, sep( ((
(109); < R rank [Z)]
What remains is to apply Claim 7 from [62], which upper bounds the rank of tensor's matricization
with multiplicative cut weights in tree tensor network. In particular, consider an order N N
31

---

tensor A produced by contracting a tree tensor network T. Then, for any K S [N] we have that A K] is at most the minimal modified multiplicative cut weight in T, among cuts separating leaves corresponding to modes K. from leaves corresponding to modes KC. Thus, invoking Claim 7
from [62] establishes Equation (21):
sep ( I) I rank FFi (I)] S
min TroO (r and PCTF00
Equation (22) readily follows by steps analogous to those used above for proving Equation (21).
1.2.2 Cut in Tensor Network for Graph Prediction (Proof of Equation (6))
For X (x(1), ....., x x(D) RDxxIv let T(X) (VT(x) (T()) be the tensor network
corresponding to f( (X) (detailed in Appendix E.3 and formally defined in Equations (15) to (17)).
By Lemma 1, to prove that
sep(s(0.9); = D (0
suffices to find TT(x) S VT(x) satisfying: (i) leaves of T(X) associated with vertices in I are in JT(X), whereas leaves associated with vertices I are not in JT(x): and (ii) " (()) (JT()) S
D (C,,))C where (x) (JT()) is the modified multiplicative cut weight of JT(x) (Def- inition 8). To this end, define JT(x) to hold all nodes in VT(x) corresponding to vertices in I. Formally:
fx(tm) : :i I, (1i.).))11
JT(X)
(((h))) :1E [L],i I, (eL-
(gll :E [L], E I,> (o.,
Clearly, JT(x) upholds (i).
types of legs crossing the cut induced by JT(x) in T(X). First, those connecting a ô-tensor with weight matrix in the same layer, where one is associated with a vertex in I and the other with vertex in Ie. That is, legs connecting g(l.in)) with (I., where i V and ((); E are on different sides of the partition (I, Io) in the input graph, for j E [W(i)),, E [L), E [Pt) V)). The 8-tensors participating in these legs are exactly those associated with some ()). So, for every / E [7]] and i E Cz there are ( V) such d-tensors. Second, are legs from d-tensors associated with i E I in the L'th layer to the 8-tensor in the output layer of T(X). That is, legs connecting g(L.i.1) with g(1]++1) for E I. Legs incident to the same d-tensor only contribute once to will (x) (JT(x)). Thus, since the weights of all legs connected to 8-tensors are equal Dr, we have that:
As for (ii), there
Cz (recall Cr is the set of vertices with an edge crossing the partition
14 Eiery (1.1((10).)) = =D), -D)-Et T (() (X) (JT(X)) & D
Et (C.)
Lastly, it remains to show that ELe PL PL-1 V) < 4p1-1(C1, V). since in that case Lemma implies:
(ep({((.0); < WI (x(() S 1Cc which yields Equation (6) by taking the log of both sides.
The main idea that, in an undirected graph with self-loops, the number of length E walks from vertices with at least Pc(Cz, V) < Pi+ (Cz, , V) for all E N. Hence:
neighbor decays exponentially when I decreases. Observe that
L Σ Pt- 2 EiE 12
Pt. (C,, V).
(24)
Furthermore, any length E N2o walk in, ..,..., i E V from Cr induces at least two walks length [+ 2 from Cz, distinct from those induced by other length walks one which goes twice through the
.....
32

---

self-loop of to and then proceeds according to the length 1 walk, i.e. io du. du. f1...., 4g. and another that goes to neighboring vertex (exists since in E CT). returns to in. and then proceeds according to
the length / walk. This means that Pt-I(CI,, V) 2- PPL-142(C V) I ... S 2- 22-11/21, PL- --14/2).1--1 V)
for all E (3.5....,.. L- - -1.. Going back to Equation (24), this leads to:
Σ Pi-111- 2 _1E(1,,.....1) 211/21 PCI, V)
2 Ei 1=0
2 - 10.-1CC,1V
4pr.-1
completing the proof of Equation (6).
1.2.3 Cut in Tensor Network for Vertex Prediction (Proof of Equation (7))
This part of the proof follows line similar that of Appendix L.2.,, with differences stemming from the distinction between the operation of a GNN over graph and vertex prediction tasks.
For X (x(),, ..... x(M)) -P.x.IM let (T(((()))))
(x)x)(()))) (y()()) be the tensor network corresponding to f(0.C.) (X) (detailed in Appendix E.3 and formally defined in Equa- tions (18) to (20)). By Lemma 1, to prove that
sep (cp(r(0...) II) S D ((2.)1().(1))
suffices to find J(w(x) S V)(i(x) satisfying: (i) leaves of (X) associated with ver- tices in I are in (x) whereas leaves associated with vertices in Ie are not in Fre))) and (ii) w T.l x) (Tro(x)) I (((--((2::11) where ( (T)()))) is the modified multiplicative
weight of (x) (Definition 8). To this end, define (x()(x) to hold all nodes in (x() corresponding to vertices in I. Formally:
[T = {x(m) :i I,7 E (o.(())))))))
{wamn :1 [L], i e I, E (t0),
{ouL))) :E [L] E I, (0L
where Wi() == (W(') if E I and Wio) = otherwise. Clearly, (x( upholds (i).
As for (ū), the legs crossing the cut induced by TTw(x) in (X) are those connecting ô-tensor with a weight matrix in the same layer, where one is associated with vertex in I and the other with a vertex in Is. That is, legs connecting g(1.i.) with (l.)
where i E V and N(), E V are on different sides the partition (I,I") in the input graph, for j E [W(()) e [L],7 E [PL-I((i), {t])]. The 6-tensors participating in these legs exactly those associated with some i E Cj (recall Cr is the set of vertices with an edge crossing the partition ("). Hence, for every I E [L] and E Ci there are PL-1((i), (t)) such 8-tensors. Legs connected to the same 5 5-tensor only contribute once to Illl
(x) (J)((x)) Thus, since the weights all legs connected to 5-tensors are equal to Dr, we have that:
I Tro (x) (JTm(X)) = Dr Di
Ele Enery (0-1(10) = D Pz ((Zz((1))
Lastly, it remains to show that Ele PI. PI,, (1) < 4pr.-1(Cz, (4)), as in that case Lemma 1 implies:
scp(f(0.9.0) S Illl (x) (J)w(x)) I D (Cz.-1()) which leads to Equation (7) by taking the log of both sides.
The main idea is that, in an undirected graph with self-loops, the number of length E N walks ending that originate from vertices with at least one neighbor decays exponentially when / decreases. First, clearly (Cz, {(}) S Pt+ (Cz, (()) for all / E N. Therefore:
L Σt, PL- PC- (t)) $ EietLa.. L-13 PL- PL,, (t}).
(25)
33

---

Furthermore, any length E N20 walk io. f1....,, :1-.... E V from Cj to t induces at least two walks of length
from CI t, distinct from those induced by other length / walks one which goes twice through the self-loop of in and then proceeds according to the length / walk, Le. io io; io .......,4-11. and another that goes to a neighboring vertex (exists since in E Cr), returns to fo. and then proceeds according to the length I walk. This means that PL-1(Cz, (t)) S
2-1 P1.-142 (1) S ..... S 2-11/11 PI,- {1)) for all E (3,5..... 1-.. Going back to Equation (25), we have that:
Enn Pt- (t)) 2 LIE(L,,,....)) 214/21 PL-1(CT, (1))
2 >>>n 1=0
2- -PL-1
4pc-1(CI, (t))
concluding the proof of Equation (7).
1.2.4 Technical Lemma
Lemma 2.
For any order N tensor A DxxxX vectors x(), x(,,.. ,...,
(,,,,,(({)),, (N) RD, and subset
of mode indices I S [N], it holds that A +EENN x(() = (o)E1x(0) [A: E R.
Proof. The identity follows directly from the definitions of tensor contraction, matricization, and Kronecker product (Appendix I.1):
A *ie[NN] x(
Ed
dw=l Ad Adi....dN
II
(0iE)x(")) T [I: "AA [A xt. (0)
L.3 Proof of Theorem 3
We assume familiarity with the basic concepts from tensor analysis introduced Appendix E.
We begin by establishing general technique for lower bounding the separation rank of a function through grid tensors, also used in [64, 100, 65, 85]. For any f (IR".)N + R and M N template vectors v('),..., v(M) IRP,, we can create grid tensor ʃ. which a form of function discretization, by evaluating it over each point in {(v(dt),. ..... "..,,((x)) v(dx)), Jd,....dy= and storing the outcomes an order N tensor with modes of dimension M. That is, the grid tensor of f for templates v(1),... (M), denoted B(f) E R M..xx.MM. defined by Bff)
v(dx) for all di..... dy E [M]. 16 Lemma shows that Se is lower bounded by the rank of Bff)ss matricization with respect to I.
= =(v(d.),..
Lemma 3. For f : (R. + R. and M E N template vectors vi),..., ((M) E RP,,, let B(f) IR Mx XM be the corresponding order N grid tensor of Then, for any I S [N]:
rank [ S sep(J;T).
Proof. If sc is oo or zero, i.e. cannot be represented as finite sum of separable functions (with respect to I) or is identically zero, then the claim is trivial. Otherwise, denote R : sc)(f: and let (!),...,, (R) (R. + R and (1)),.. ......(R)) ()) (R22)) )T)) + IR such that:
S(x) -x (X
(26)
where X = (x(1) (("),...,.......... x())). Xx = (x) JEzz and Xx= == (xl1) jEZz. For r E [R]. let (rg
and (rr(r) be the grid tensors of (r) and g(r) templates v(1) v(M) respectively. That is,
B(g(t))
d.sez ((g(t))),szz
((v(()) and ((g(r)) (d g(r) )Ez))) for all d ... dN E [M].
16ehe template vectors of grid tensor B()) will be clear from context, thus omit them from the notation.
34

---

By Equation (26) we have that for any d1..... ...... dN E [M]:
B(
/( [(v(d), ...,,,dd vldx))
= R
r= ((v(((v( )(Ez) .g ((vle)) JEZz)
- r= ((g
n
B ((g djgjET=
dRiEz
Denoting by (r)) E R MM and (rr) E RM the arrangements of (( and ((g(t)) vectors, respectively for r E [R], this implies that the matricization of (f) with respect to can be written
as:
[ = Σ
R a
(a'r))
We have arrived at a representation of [B] as a sum of outer products between two vectors. An outer product of two vectors is a matrix of rank at most one. Consequently, by sub-additivity of rank we conclude: rank [ff): R sep(f:I).
In the context of graph prediction, let C E argmaxces(I) log(ac) PI.-i V). By Lemma 3, to prove that Equation (8) holds for weights 0, it suffices to find template vectors for which log(rank [B (f(0.))) =]] 2 log(ac-) PI- V). Notice that, since the outputs of f(0.9) vary polynomially with the weights 0, so do the entries of (Bf((.))):II for any choice of template vectors. Thus, according Lemma 9, by constructing weights and template vectors satisfying log(rank|] (f((.)) I]] log(ac-) PL-I(C",, V). may conclude that this is the case for al- most all assignments of weights, meaning Equation (8) holds for almost all assignments of weights. In Appendix I.3.1 we construct such weights and template vectors.
In the context of vertex prediction, let C₁ argmaxcesca log(uc,)) PL-1(C, (1)). Due to ar- guments analogous to those above, to prove that Equation (9) holds for almost all assignments of weights, we need only find weights and template vectors satisfying log(rank [ [B(((...))); log( log(Ac;,1) (C) {t)). In Appendix I.3.2 we do
Lastly, recalling that a finite union of measure zero sets has measure zero as well establishes that Equations (8) and (9) jointly hold for almost all assignments of weights.
I.3.1
Weights and Template Vectors Assignment for Graph Prediction (Proof of Equation (8)
We construct weights 9 and template vectors satisfying log(rank [f((())) 2 log(ac-) (C*, Pr. (C,, .V). where C* argmaxces(z) log(ac) Pt. V).
If PL (C", V)- 0, then the claim is trivial since there exist weights and template vectors for which [B I not the zero matrix (e.g. taking all weight matrices to be zero zero-padee pero-padded identity matrices and choosing a single template vector holding one in its first entry and zeros elsewhere).
Now, assuming that (C" V) > 0, which in particular implies that I + 0, V, and C* * 0, we begin with the case of GNN depth L = 1, after which we treat the more general 2 case.
Case L = 1: Consider the weights = (W(1), W given by ((1) = I E D.DD. and (0)) = 1I E IR where I is zero padded identity matrix, i.e. it holds ones on its diagonal and zeros elsewhere. We choose template vectors v()...., (D) (D)
D= such that (mm) holds the m th standard basis vector of IRD in its first D coordinates and zeros in the remaining entries, for m E [D] (recall D = min D Dr))). Namely, denote by e(1) e(!)...., (D) E R² the ,..., standard basis vectors of IRD i.e. e (m) if d m and e 0 otherwise for all m, d E [D]. We
let (m) c(m) and (m)
D+1: == 0 for all m E [D].
We prove that for this choice of weights and template vectors, for all dry E [D]:
((0,9) (v(di) v(dw))
{1
if d1 .... dnd
(27)
0
otherwise
35

---

To see it is so, notice that:
( v(dv.)) w
w (Oierh - -E II iev
hd
with h(1,0) = ()) ( (l()) = OJEN()) (Iv(4)) for V. Since v (d,)
e(d,) for all
j E (ii) and is a rero-padded D identity matrix, it holds that:
((0.0) (v (d)) v(dvil) = I d41
Due to the existence of self-loops (ie. i E Nii) for all i E V). for every E [D] the product IIeev.EeV()) ed (d,) includes each of e(di)) e....,e (dvi) at least once. Consequently,
II o/ = 1 if d1 = =.. = diyl = and Iev (()) = 0 otherwise. This
implies that (v(h)) ,..., v(dvi)) otherwise, for all di....,, dvi [D].
(d:),
if di = = dudp and ((l,)) ,.., v(dw))
Equation (27) implies that [B (0.0)) : has exactly non-zero entries, each in a different row and column. Thus, rank B (10.0)):: I = D. Recalling that ac- == D1/Po(C" . for L = 1, we conclude:
log rank B ((. (1(.,))) : =
log(D) = log(ac-) po(C", ,)).
Case of L 2 2: Let M = C (L- vi (D+pL- 1CHPL-1CC".V)-- 1)) be the multiset coefficient of D PL- (C²,VV) and (C*, V) (recall D = min Dz, Dr By Lemma 7, there exists Z E IR for which
rank (0pL_110' v) (ZZT)) = ((LLLc
with (V) standing for the PL-1(C", V/'th Hadamard power of ZZ For this Z. by Lemma 4 below we know that there exist weights 9 and template vectors such that [B( has an M x M sub-matrix of the form ((OPL-I(C*))) (ZZ Q) where S, Q R MMM are full-rank diagonal matrices. Since the rank of matrix is at least the rank of any of its sub-matrices:
rank ([B(F(()))) 2 rank ( (0 .1) (ZZ)) 2ZZ))))
rank (PP--1 , ((Zz))))))))))))))))
D )
where the second transition stems from S and Q being full-rank. Applying Lemma 8 to lower bound the multiset coefficient, we have that:
(oLddr,)) ( ( D-1 PL-1(C",V)
rank ([B((((0)))))))))
PL-1(C',,1) +1
Taking the log of both sides while recalling that ac- = (D- that:
- 1). p1-1 (C, + we conclude
log(rank B (B ((()))) : 2 log(ae:) PL-1(C",)))
Lemma 4. Suppose that the GNN inducing f(0.) of depth > and that PL-1(C",, V) > For any M E N and matrix with positive entries E M6D there exist weights 0 and M + template vectors v(1) (M++) E RDD. such that [B( has an M M sub-matrix S(OPL-1((0 (ZZ ))Q, where S,Q E MXM are full-rank diagonal matrices and PC--1 V) (ZZZ) is the PC- V) 'thh Hadamard power ZZ
36

---

Proof. Consider the weights 0 = (W(),... W W given by:
w = IE R D,XD=
1
W
E DaXDa
0
0
0
0 0
1I E (3....,LJ, w
E DR
W (1 0 0) RIXDs
where I is a zero padded identity matrix, Lee it holds ones on its diagonal and zeros elsewhere. We define the templates v(!),..., (MM E D= to be the vectors holding the respective rows of in their
first D coordinates and zeros in the remaining entries (recall D = min Da, Dr That is, denoting (m)
: 2 (m) and v VD+1 = 0 for all m E (M]. We set all entries of the last template vector to one, i.e. (M++) == (1...., R.
the rows of Z by , (M) E TR-S-- we let v.D (m)
Since C* E S(I), i.e. is an admissible subset of C3 (Definition 4), there exist I' CI,J'S S I with no repeating shared neighbors (Definition 3) such that C = (I') NW(T). Notice that I' and J' are non-empty as C * 0 (this is implied by P V) > 0). We focus on the M x M sub-matrix of [B(F((.0)): that includes only rows and columns corresponding to evaluations of (Mn) all variables indexed by J' are assigned the same template vector from v(1), ..... v(M), and all remaining variables are assigned the all-ones template vector v(M+1), Denoting this sub-matrix by U E IR M M it therefore upholds:
((0.9) where all variables indexed by I' are assigned the same template vector from v(1)
U ((000 (xx f- v(m)) IEED (x(5 f- v(n))
jegi (x(1) + v(M+1) kEM)
for all m.n E [M], where we use (x(+) + v(m)) Jer to denote that input variables indexed by I' assigned the value v(m). To show that U obeys the form ((cP)- (ZZ Q for full-rank diagonal S,Q. E IRM we prove there exist o, RD= - Ryo such that
Um, = ((v(m))(2))))) z (m)))P 1(C" ()l(()) for all m, n E [M]. Indeed, defining S to hold ((v(1) ).. (M)) on its diagonal and Q to hold
(M() on its diagonal, we have
that U = S(OP)-1(e*, v) (ZZ Q)Q. Since S and Q are clearly full-rank (diagonal matrices with non-zero entries on their diagonal), the proof concludes.
For m, n E [M], let (4,) E Rh. be the hidden embedding for E V at layer E [L] of the GNN inducing f00.5) over the following assignment to its input variables (i.e. vertex features):
(x(() - v((m)) ser (xx()= +- -v()) jegr (x( v(M+1) AEV((IUU))
Invoking Lemma 10 with v(m), v(m), J',, and H', for all E V it holds that: (L.)) = x(1.0) (v(m)) (2z (m), z'ny pa-1(e" (e0,ee100 (0t) ((L,))) (v(n)) Vd E (2....,pb) (L,)) 0,
for some ((1.1)) (5((x))) RR + Rso. Since
U Um, = f(0.9) (xx(0 t v(m)) iero (x(1 + v((l)) sear (xx(4) v(ds+11) v(al+11) (EP
= - (oierh
and W(o) (1.0.... ... 0), this implies that:
U U II
LEv h (L.))
II
Tep (s( ()()))(((())) (v(m)) (m( 2u ((0.))
.ti)) (5(T.)) (v(m))
37

---

Rearranging the last term leads to:
U mn (II (04.. (vlml) (zim) 2(11) Evev
PL PL- (0
(II
jev vi(k,)) (vin)))
Let Φ +++ Ihe ( (v) and v. - HEE (v).. Noticing that their range is indeed Ry0 and that Eiey PC, {i)) PI- V) yields the sought-after expression for U m,n
U = ((v(m)) (z(m), z (w My (v((()).
1.3.2
Weights and Template Vectors Assignment for Vertex Prediction (Proof of Equation (9))
This part of the proof follows a line similar to that of Appendix I.3.1, with differences stemming from the distinction between the operation of GNN over graph and vertex prediction. Namely, we construct weights 0 and template vectors satisfying log(rank) [B (9.C..)) I[] 2 log(ac;,) PC-1 (t)) where C₁ argmaxces(I) log(ac,)) PL,1(C, {t)).
If (C, {t]) = O, then the claim is trivial since there exist weights and template vectors for which [B( : is not the zero matrix (e.g. taking all weight matrices to be zero-padded identity matrices and choosing a single template vector holding one in its first entry and zeros elsewhere).
Now, assuming that (C,, {t]) > 0, which in particular implies that I * 0, I & V, and C₁ * 0, we begin with the case of GNN depth L = 1, after which treat the more general L, 2 case.
Case of L = 1: Consider the weights 0 = (w()), Wlo) given by W(1) = I E Drx and W = (1.....1) E IRIxD where I is zero padded identity matrix, i.e. it holds ones on its diagonal and zeros elsewhere. We choose template vectors v()...., v(D) (D)) E IR D= such that ((m) holds the m' th standard basis vector of IR." 2 in its first coordinates and zeros in the remaining entries, for m E [D] (recall D == min(D,, D).)). Namely, denote by e(1)... ...., (D) (D)
RD the
standard basis vectors of IR. i.e. e (m) if d = m and e (im) = 0 otherwise for all m, d E [D]. We let V.D (mm) and D++: == for all m E [D].
We prove that for this choice of weights and template vectors, for all di d d4p [D]:
((0.5 (v(a)) v(d = { 0 otherwise
d, d3 for all j.j E (t))
(28)
To see it is so, notice that:
((.())(((d)) v(4v)) w(.))
Ex -==
Da (1.0)
with (1.0) (e))(()) (Wa) = OzeN(n (I)) Since (d,) = e(d)) for all j E ((t) and
is a zero-padded D x D identity matrix, it holds that:
)(o.5.)) (v(d),
v(v))) = En d=1 II JEN())
(4)
(4) = lifd = d for all j E (()) and ] e(( = For every d E [D] we have that I ed otherwise. This implies that ((0.s.t) (yld)),.. (.ld),..., v(dvi)) ....,,,(dv))
if dj dy for j.J N(t) and ((0.5..) (v(d),,.... v(d))) otherwise, for all . dn E [D].
.....
Equation (28) implies that [B(((00.0)) has a sub-matrix of rank D. Specifically, such a sub-matrix can be obtained by examining all rows and columns of [B((()))))) correspond- ing to some fixed indices (d, E (D)) for the vertices that are not neighbors of t. Thus, rank ()((0.))))): I]] 2 D. Notice that necessarily Po(Cr, (1)) = 1, as it not zero and there can only be one length zero walk to (the trivial walk that starts and ends at f). Recalling that ac7,t == D for T. 1, we therefore conclude:
log (ogak)) | (1(06)))): 2 log(D) = log(ac; Po(C; (4).
38

---

Case of L 2 2: Let M := pp2- (11)) -(- (D+p (C2-(1))-) be the multiset coefficient of D P2--((2;(1))
and Pr.-1 ((}) (recall D min Dz,, Da))). By Lemma 7, there exists Z E RAxD for which
rank (PPt)-(- (zz)) = ((pL11e))
D
with OPE (ZZ") standing for the PL-1 (C;, (t)))th Hadamard power of ZZ' T. For this Z. by Lemma below we know that there cxist weights 0 and template vectors such that [ has an MM x M sub-matrix of the form S(Orz 1(27 (ZZ")) where S, Q RMx are full-rank diagonal matrices. Since the rank of matrix is at least the rank of any of its sub-matrices:
(( ) 2 rank (S( (o ((27.(9) (ZZ) (ZZ)))))
rank (P2-11C7 )
D -(p--11: )()))
where the second transition is due S and Q being full-rank. Applying Lemma 8 to lower bound the multiset coefficient, we have that:
PL-1(C2.(11)
rank (1
(om1):(1))
D
D ( +1
(L- (1))
Taking the log of both sides while recalling that oce,, == (D - PL- (t))) that:
+ we conclude
log(rank | ( p(o.s..)
: > log(ac;,)) PI.-1 PI,-I {f)).
Lemma 5. Suppose that the GNN inducing f( is of depth L 2 2 and that PL-1(Ci {tt) > O. For any M N and matrix with positive entries Z E B there exist weights O and M + template vectors v(I), .-.., (.),...,(MM... v(M++) E RD such that [B(F(0.8.0);; has an M M sub-matrix S (()PL-I(C7((t)) (ZZ) Q)Q, where S,Q RMX are full-rank diagonal matrices and (PL-1(C(-1(1) (ZZ)) is the PL-1 (C7 {(}) 'th Hadamard power of ZZ T.
Proof. Consider the weights 0 = (W(I).... W(L) W defined by:
W = I I R DuXD
0 0
((2)
R Da
0
0
0
VI E (3. w(
E RR Dr
0
W = (1 0 0) E
where is zero padded identity matrix, i.e. it holds ones on its diagonal and zeros elsewhere. We let
the templates (1)) ...., ...., (M) R= be the vectors holding the respective rows of Z in their first D
coordinates and zeros in the remaining entries (recall D = min Dz, Dx}). That is, denoting the (m)
rows of Z by (1) ...,,.".""". (M) e BB we let (m) = mm) and v V == for all m [M]. We set
all entries of the last template vector to one, i.e. (1++)) == (I....,1) 1) R
Since C; E S(Z), i.e. it is an admissible subset of Cr (Definition 4), there exist I' C II,J' C I with no repeating shared neighbors (Definition 3) such that C; = =I' (N(T). Notice that I' and J' are non-empty C, # 0 (this is implied by PL-1(C7 {t)) > 0). We focus the M x M
39

---

sub- sub-matrix of [B( I that includes only rows and columns corresponding to evaluations of (( where all variables indexed by I' are assigned the same template vector from v(1) v(M) all variables indexed by J are assigned the same template vector from v-t), ..... v(M) and all remaining variables are assigned the all-ones template vector v(M+1), Denoting this sub-matrix by U E TR. MMM it therefore upholds:
m,n /(0....) ((x() + v(m)) iern (x(1) t- v(w)) Jea (x(1) f- v(M+1) kem)orus))
for all n, [M], where use (x(*) v(m)) Hie denote that input variables indexed by I' are assigned the value v(m), To show that U obeys the form ((tP)-1(CT.tt))z ( for full-rank diagonal S, Q E RMXM, we prove there exist o, b RD, + Ry0 such that Um, of d(v(m)) (z(m)
for all m, E [M]. Indeed, defining S to hold ((v(1),..... ..... p(v ((v(M) on its diagonal and Q to hold dv(()) ()((M) on its diagonal, we have that U (( (()))((() ))Q. Since S and Q are clearly full-rank (diagonal matrices with non-zero entries on their diagonal), the proof concludes.
For m, n E [M], let ((.1) E Ph be the hidden embedding for E V at layer E [L] of the GNN inducing (0..).) over the following assignment to its input variables (i.e. vertex features):
(x(*) (mm)
JEI' (x(1) + v(())) jeg' (x(*) (M++2)) KEVI(TUU
Invoking Lemma 10 with v(m), v(m), I', and J it holds that:
h (T.,1) = -0i( (v(m)) (2 (m) slo 1(77 ((7,((1)) (L..0) (v(x)) Ad E (2....,Ppl } ha = 0,
for some (S(,,), v6(4,)) RDD= Rso. Since
Um, f(0.)11) (xx(0 + vm))) iezi (x10 v(()) jegr (xx10 v(M+1)) ) kEV
= (I,))
and W(o) (1, .... 0), this implies that:
.........
U Um,- = h1 (4,1) (511..)) (v(m)) ( (m(m) x (n)))e--(Ci,,e (077,(1)) w((.tt (v(nl).
Defining = ((h,t) and wi((.)) leads to the sought-after expression for U Umni
m, = (v((m)) (2(m), a 2m))er (C7,(()) 4b (v(nl)..
1.3.3 Technical Lemmas
For completeness, we include the vector rearrangement inequality from [61], which we employ for proving the subsequent Lemma 7.
Lemma 6 (Lemma 1 from [61]). Let a (").....(MM)))) E TR be M E N different vectors with non-
negative entries. Then, for any permutation [M] + [M] besides the identity permutation it holds that:
M Em= (a(m) ((((m)))
MM
Taking the P'th Hadamard power of rank at most matrix results in a matrix whose rank is at most the multiset coefficient
(?) (D+P-1) (see, e.g., Theorem in [2]). Lemma 7, adapted from Appendix B.2 in [64], guarantees that we can always find (P) x D matrix Z with positive entries such that rank(O" (ZZ )) is maximal, i.e. equal to ( (P))
Lemma (adapted from Appendix B.2 in [64]). For any D E and P E Nz0, there exists a matrix [2]x for which:
with positive entries Z E R R50
rank(o ((((())Z)) = (P)).
where OZZZZ] is the P'th Hadamard power of ZZ
40

---

Proof. We let M = (P) for notational convenience. Denote by z z(
z(),
RR the row
vectors of Z R >0
MxD Observing the (m,n) thh entry of
O ToP(P (Zz")]
m.n
-( (m))
P
Σ
d
% Zdd
(m) (n)
P
by expanding the power using the multinomial identity we have that:
D
10" (ZZ )] m.n
Σ
(
P
II
Z
d
(m)
d
(x))
30
9. E8
d=1
sL E 12=P
(29)
Σ
P
D II
22
(m))
((())))))
C1....
4D)
A go ENgo S.L. Ed d==P
where in the last equality we separated terms depending on m from those depending on n.
Let (D) E TR.
on EB A==P be M vectors defined by am (g)....9)))
Th (z) (m)) 90 for all 9....., QD N20 satisfying Ed 9d P and [M]. As can be seen from Equation (29), we can write:
ZZ ASAT,
where A E MxM the matrix whose columns are (a(9).m)))) gn. ( E. q==P and E MxM the diagonal matrix holding (
(...... for every ......, QD E N20 satisfying are positive, is of full-rank, i.e. rank(S) = M. Thus, to prove that there exists Z E M for which rank(o (ZZ )) M, it suffices to show that
Eb ld = P on its diagonal. Since all entries on the diagonal
choose (1)), ..... (M) with positive entries inducing rank (A) M, for A as defined above. Below, complete the proof by constructing such z ()),..,, (M)
We associate each of (1) "i,,,,,,(,,,,
(M) with a different configuration from the set:
{-= (qi.....q))) .i...... &D E N20, Σ d=1 EB =
where note that this set contains M = (P) clements. Form [M]. denote by q (m) the configuration associated with (!m)) For variable E R, to be determined later on, and every m E [M] and E [D], we set:
2 (m)
9
Given these (1)) ,..., (M), the entries of A have the following form:
(1),,..,,((()
Am, IT IT22((25 (m))
dd 2
II d=1 (1al
D (m)
4d
= = Des (n) of 70 (mmm)
a:[M]- c sign(o) Em (m) (m) (obm))) is polyno-
for all m, n E [M.. Thus, dct(A) = = Epermutation o:: mial in y. By Lemma >M <q (m)) (a(m))) > wom-lllaa (m)) for all which is not the identity
permutation. This implies that and it attained by a single element in Σ Permuuaation [:[M]][[M] sign(a) sign(o).>I*M.... -M ( (((())) that corresponding the identity permutation. Consequently, del (A) cannot be the zero polynomial with respect to 7. and so vanishes only on a finite set of values for r. In particular, there exists 7 such that del(A) (A) )+++ * O, meaning rank(A) (A) = M. The proof concludes by noticing that for positive y the entries of the chosen (1). (M) are positive as well.
(m) ||
is the maximal degree of monomial in det(A),
L
Additionally, make of the following lemmas.
41

---

Lemma 8. For any P.PE let (2) (D+P-1) be the multiset coefficient. Then:
D 2
D (D-++1) pp+
Proof. For any N K E N, a known lower bound the binomial coefficient (x)
x)) (*)
Hence:
(P) = D (----P-P))) 2 (D+P-1)= = D P
(Pp++1)
P
Lemma 9. For Di. D2, K E N. consider polynomial function mapping variables 0 E BK to
matrices (0) E DiDD,,, Le. the entries of A (0) are polynomial in O. If there exists a point 0* R
such that rank( (ak(((((")) 2 R. for R [min{D1, D2H,, then the set {0 R rrank(A(0)) < R}
has Lebesgue measure zero.
Proof. A matrix is of rank at least R if and only if it has R x R sub-matrix whose determi- nant non-zero. The determinant any sub-matrix of (0) is polynomial in the entries of (0)), and it is polynomial in 0 well. Since the set of polynomial is either the tire space or a set of Lebesgue measure zero [19], the fact that (unk(((0))) 2 R implies that {0 R&K (ran((A()) < R} has Lebesgue measure zero
Lemma 10. Lei V, E IR whose first D == min Dnd entries are positive, and disjoint I' I' C with no repeating shared neighbors (Definition 3). Denote by h(t.)) E BR the hidden embedding for E V at layer E [L] of a GNN with depth 2 2 and product aggregation (Equations (2) and (5)), given the following assignment to its imput variables (L.e. vertex features):
(x v
ver (x() -
(xx -V)
where 1 E Da is the vector holding one in all entries. Suppose that the weights W(). ..... W(L) of the GNN are given by:
W() IE R
DO
0
0
(
IR DA
0
0
e L3. W
E R. DAx
0
where is a zero padded identity matrix, i.e. holds ones on its diagonal and zeros elsewhere. Then, for all 1 E (....., .....,,, L) and E V, there exist (305)) 1b(1.)) RD= + R20 such that:
h (1.0) = (1.00) (v) (v.n, v (a)) Ad (2. (2.....A Dz) h = 0, where C = N(TT)
Proof. The proof is by induction over the layer / E ( L). For = 2, fix i E V. By the update rule of GNN with product aggregation:
(2,0)
OEN(()) (W()))))))))
Plugging in the value of W
we get:
h (2
II
E d=l
Dr
h
(1,))
vd {2, Da) h (2,6) 0.
(30)
JEN())
42

---

E DR be the vectors holding v.D and V.D in their first D coordinates and zero in the v' V. Let v,
remaining entries, respectively. Similarly, we use 1 E PR to denote the vector whose first D entries are one and the remaining are zero. Examining h (1:ا) for j E (i),, . by the assignment of input variables and the fact that W(1) is a zero padded identity matrix we have that:
h (1.)) ORENGi (w()x()) (o ()) o (oWWnnn (') @ (oNONTW')))
= =(oWGnnzll) o (o
(oWG)n3'(
Since the first D entries of and v' positive while the rest zero, the same holds for h (1,)) Additionally, recall that I'' and J' have no repeating shared neighbors. Thus, if E ((I))NN())
C. then has a single neighbor in I' and a single neighbor in J', implying h (1.)) v@v. Otherwise, j j & C, then N(j) nI' = 0 or ((() n J = must hold. In the former (1,)) does not depend on v, whereas the latter h (1-5) does not depend on v'.
Going back to Equation (30), while noticing that [V()) = PI {i)), we arrive at: Ds
h h
(E
d=1 h
(11))
III
(Ex=)
Dr
h
d=1
III
Dh
+ vld)
IIs ( Do h n((09)
DR
hd
(1,)
d=1
-V.D,, V(D) ( (c.1,))) JEATONE
(C,(0)
d=l
As discussed above, for each j ((ii) \ C the hidden embedding h(.))) does not depend
or it does not depend on v'. Furthermore, Een h (1,1 0 for all j E NN(i). Hence, there exist ((221) vl2.))) D= + Rz0 such that:
h 2. (2200()) (V.D. V' (r(.t))) (V).
completing the base case.
Now, assuming that the inductive claim holds for 1 2, we prove that holds for I. Let E By the update rule of GNN with product aggregation ((..) O)EN()) (W-") Plugging in
the value of (()) we get:
h (1.9)
II JEN(()
h h(-1.))
(1-1.))
AA ( Da3 h =0
By the inductive assumption h1 ((-15) = (VV- (V.n, V'D) 211,6)) (0-151))) for all j E
(t)), where ((1-1.1), (0(11,)) RD= + Rso. Thus:
II JE
h (1111))
= -ITYENrO) 2i I (V.D, V' a(C.U)) (((---)(v))
-III (V))))(v) (V.D, V'D) EiENOs 2(C,(i))
II II wa 1.0 (V))
Define zll.)). : - II JEN ( (v) and (((,))
12)
II ehlt lui) (v'). Since the range
of (5) and 25(l-15) is Ryz for j E ((i, so is the range of ((0.)) and vi(l.i) The desired result
thus readily follows by noticing that ΣjEN() Pt (C, = (c, (i)):
h (1.)) (v) (V.D. v pc (V))
1.4 Proof of Theorem 4
The proof follows line identical that of Theorem 2 (Appendix 1.2), requiring only slight adjust- ments. We outline the necessary changes.
Extending the tensor network representations of GNNs with product aggregation directed graphs and multiple edge types is straightforward. Nodes, legs, and leg weights are as described Ap- pendix E for undirected graphs with single edge type, except that:
43

---

Legs connecting ô-tensors with weight matrices in the same layer are adapted such that only incoming neighbors are considered. Formally, in Equations (15) (20). (i))) is replaced by (1) in the leg definitions, for i EE) V.
Weight matrices (Wil.)) (e14)1))) (E1 Namely, if at layer I E [Z] a d-tensor associated with i E V is connected to a weight ma- trix associated with j E Ni,(t), then W((.7G.)) is assigned to the weight matrix node, as opposed to W in the single edge type setting. Formally, let Willdn) be a node at layer / E [Z]] connected to g(h,,7) for i V.j (i) and some 7,7' E N. Then, Willdn)) stands for copy of (((.66))
are assigned to nodes in accordance with edge types.
For X = (x()), x(D) E P XP, let T(X) and (X) be the tensor networks corresponding
to f(0.9) (X) and f(o (X), respectively, whose construction is outlined above. Then, Lemma I (from Appendix 1.2.1) and its proof apply as stated. Meaning, sep( (0.9) :Z) and sep(f (0.0))))
are upper bounded by the minimal modified multiplicative cut weights in T(X) and (X).
respectively, among cuts separating leaves associated with vertices of the input graph in I from leaves associated with vertices of the input graph in I". Therefore, to establish Equations (11) and (12), suffices find cuts in the respective tensor networks with sufficiently low modified multiplicative weights. As is the case for undirected graphs with a single edge type (see Appendices 1.2.2 and 1.2.3), the cuts separating nodes corresponding to vertices in I from all other nodes yield the desired upper bounds.
1.5 Proof of Theorem 5
The proof follows a line identical to that of Theorem 3 (Appendix 1.3), requiring only slight adjust- ments. We outline the necessary changes.
In the context of graph prediction, let C* E arggaxces--c)) log(ac) PL.- V). By Lemma 3 (from Appendix I.3), to prove that Equation (13) holds for weights 0, it suffices to find template vectors for which log(rank|| ( (f :I]= 2 log(ac-)
(e((ac))-L-i(C P (C*, V). Notice that, since the outputs of f(9.5) vary polynomially with 6, so do the entries of [ [B ( ((0.0)): for any choice of template vectors. Thus, according to Lemma 9 (from Appendix I.3.3), by constructing weights and template
vectors satisfying log [rank[B ((.))) : 2 log(ac-) PL-1(C* PoL( V). we may conclude that this is the case for almost all assignments of weights, meaning Equation (13) holds for almost all assignments of weights. For undirected graphs with single edge type, Appendix 1.3.1 provides such weights W(),, ( ((") and template vectors. The proof in the case of directed graphs with multiple edge types is analogous, requiring only a couple adaptations: (i) weight matrices of all edge types at layer E [L] are set to the W chosen in Appendix 1.3.1; and (ii) Cr and SI) are replaced with their directed counterparts Cj' and S (I), respectively.
In the context of vertex prediction, let C₁ argmaxces- (() log(ac,:) -C, (t))) Due to arguments similar to those above, to prove that Equation (14) holds for almost all assignments of weights, we need only find weights 0 and template vectors satisfying log(rank| [B ((.(0...))): ) 2 log(ae (c;; .) PL-1 (C; {t)). For undirected graphs with a single edge type, Appendix L.3.2 provides such weights and template vectors. The adaptations necessary to extend Appendix I.3.2 to directed graphs with multiple edge types are identical to those specified above for extending Appendix I.3.1 in the context of graph prediction.
Lastly, recalling that finite union of measure zero sets has measure zero as well establishes that Equations (13) and (14) jointly hold for almost all assignments of weights.
L.6 Proof of Proposition
We first prove that the contractions described by T(X) produce ((9.9)()) Through an induction over the layer 1 E [Z], for all i E V and y E ((L))((i), V)] we show that contracting the sub-tree whose root is 8 ((.in)) yields (t.4) the hidden embedding for layer of the GNN inducing ((0.9) given vertex features x( ,..., (()))
44

---

For 1 = 1, fix some i E V and [PL-1(fi), V)]. The sub-tree whose root is g(1.n)) comprises [i) copies of W(1,, each associated with some j E (i) and contracted in its second mode with copy of x( Additionally, g(1.,)) which is copy of ((((@)++), is contracted with the copies of w(1) in their first mode. Overall, the execution of all contractions in the sub-tree can be written as ((W(0)+1) *J([)(())) (W(D)(M(())) where (t)j. for E [[)( denotes the j j'th neighbor of i according to an ascending order (recall vertices are represented by indices from 1 to (V]) The base case concludes by Lemma 11:
((L *SE(I((()) (WO))(O)) SeelLoll (w (((x))))))) h (1.))
Assuming that the inductive claim holds for / - 1 2 1, we prove that it holds for 1. Let i E V and y (ft), V)). The children of g(1,2n)) in the tensor network are of the form ((.. for j [[][))]], and each ((( is connected in its other mode 8 (
By the inductive assumption for 7 1-1, 1, we know that performing all contractions in the sub-tree whose root is 3(l-1N(0),.....(0 produces (111,,())), for all E [[A(())]] Since 5(1,an) is copy of 80W(0)+1)) and each (((, is copy of w the remaining contractions in the sub-tree of 8 (1.in) thus give:
8(L(()+1 *J((L(())) (WWDD-LNV))))
which according to Lemma 11 amounts to: ((W((++1) *JEl (w OJEL (w"hn--Nw6)) (1.0
establishing the induction step.
With the inductive claim hand, we show that contracting T(X) produces ((6.9)(X) Applying the inductive claim for I., we have that h (L.1), ..... (L.VV)) are the vectors produced by executing all contractions in the sub-trees whose roots are 8(4,1.1) 8(4.1V1.1) respectively. Performing the re-
maining contractions, defined by the legs of 5(12++1) therefore yields W(o) (((1)+ *<<[[V]] h(2.)))
By Lemma 11:
8(1++1)
*ie[|v|] h (م,ا) (h4
Hence, w (8(1)+))) * h(4.)) (O h(4.0)) ((0.9) (X), meaning contracting T(X) results in (x).))
An analogous proof establishes that the contractions described by 7(0 (X) yield ((0.9.0) (X). Specif-
ically, the inductive claim and its proof are the same, up to y taking values in [PL-i(fi), [t))]
instead of ((i))((i),) V)J, for E [L]. This implies that h (2.1) is the vector produced by contracting the sub-tree whose root is (LL,111) Performing the only remaining contraction, defined by the leg connecting gLL,111) with W thus results in (L,t) ((0.9.1(())
I6.1 Technical Lemma
Let 1 E Dxx.x be an order N + E N tensor that has ones on its hyper- diagonal and zeros elsewhere, i.e. (N+1)
Lemma 11.
di 1 if di = dN+1 and gN++1) d2....Ni1 = 0
otherwise, for all di,..., dpN1 E [D]. Then, for any x! x (N) E RD it holds that
g(N+1) *NENN (6) @zeNN ERD
Proof. By the definition of tensor contraction (Definition 7), for all d E [D] we have that:
(o(N+) *NENN] x x())
=Eo
(N+1) -Ed dy=1 dy II x
II x (OVELN)x(0)
45


Reviews:
[{"review_id": "ezzCiBp4Qo", "reviewer": "Reviewer_CGQv", "summary": "This paper proposes to analyze the expressivity of graph neural networks (GNNs) by their ability to model interactions. The authors consider GNNs with product aggregation scheme, and analyze their ability to model interactions for a given partition of the graph through the notion of separation rank. The authors show quantitatively that these GNNs can model interactions better for partitions with higher walk index (Theorem 1). Motivated from their theoretical analysis, the authors propose an edge sparsification algorithm --- Walk Index Sparsification (WIS, Algorithm 1, 2) --- to drop edges that have least amount of impact on GNN's ability to model interations for a given partition in a given graph. The utility of WIS is demonstrated on both graph-level prediction and vertex-level prediction tasks.", "questions": "\n1. The analysis focus on GNNs with product aggregation, i.e. multiplication of the neighborhood node's embedding vectors $\\mathbf{h}^{(l, i)}=\\odot_{j \\in \\mathcal{N}(i)}\\left(\\mathbf{W}^{(l)} \\mathbf{h}^{(l-1, j)}\\right)$, where $\\mathcal{N}(i)$ depends on the graph topology. In this set-up, the authors show that such GNNs can model interactions among two partitions in a graph better if they are more inter-connected. Yet, earlier work by Cohen and Shashuwa [3] show that for the case of convolutional neural networks (CNNs), their ability to model interactions depend on the choice of pooling functions. In light of this result, it seems plausible for GNNs to model partitions that are less-connected (e.g., Fig 2 -left) if one delineates the aggregation function from the graph topology, which is also commonly used in the literature of graph rewriting (e.g. [2]). Can the authors provide more explicit interpretations of their results and comparison with related work using separation rank for CNNs/RNNs?\n\n2. As a thought example: for GNNs with product aggregation, do they achieve maximally separation rank for a fully-connected graph? How would the WIS algorithm compare to a simple baseline: replacing the original graph with a fully-connected graph, followed by randomly dropping edges (as opposed to (i) edges are removed randomly from the original graph)? This baseline is motivated from [4], where the authors show that replacing the original graph with a fully-connected graph at the output layer can boost GNN performance. \n\n3. In line 264-266, the authors explain that the edge sparsification algorithm should first choose the partitions of interest, whereas in Algorithm 1 and 2, such choice is default to partitions induced by singletons and the rest of the nodes. It seems possible that the optimal partition choice depends on the downstream tasks (e.g., graph-level clustering versus node-level prediction). Can the authors provide more details and recommendations?\n\nReferences:\n\n[3] Cohen, Nadav, and Amnon Shashua. \"Inductive bias of deep convolutional networks through pooling geometry.\" arXiv preprint arXiv:1605.06743 (2016).\n\n[4] Alon, Uri, and Eran Yahav. \"On the bottleneck of graph neural networks and its practical implications.\" arXiv preprint arXiv:2006.05205 (2020).", "limitations": "The limitations were discussed, but can be explained more thoroughly through (1) detailed interpretations of the theoretical results (assumptions and applicability); (2) comparison with prior works that make use of separation rank to analyze expressivity of deep learning architectures.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "Strengths:\n\n1. The proposal to study the expressivity of GNNs via their ability to model vertex interactions is interesting. \n\n2. The theoretical analysis is novel: by focusing on GNNs with product aggregation, the authors connect them to tensor networks, of which the notion of separation rank can be used to study the network's ability to model interactions. \n\n3. The paper is overall well-written and easy to follow, where important technical details and illustrative examples are explained clearly in the supplementary materials.\n", "weaknesses": "Weaknesses:\n\n1. The theoretical analysis focus on a special kind of GNNs with product aggregation, whereas the empirical evaluations are all done using standard GNNs with mean aggregation with ReLU nonlinearity. Although the authors meant to show that theory results can carry over to standard GNNs, they do not explain explicitly how such connections can be drawn. If the main contribution of the paper is...\n(a) to show that using separation rank to understand GNNs is relevant, then the authors should outline how the analysis carries forward to standard GNNs\n(b) to show that walk index of partitions in a graph determines GNN performance, then the authors should examine the case where the original graph is replaced with a fully-connected graph, and discuss GNNs with Graph Transformers\n(c) to propose an edge sparsification algorithm, then comparisons with stronger baselines are needed, such as DropEdge [1] and curvature-based graph rewriting methods [2].\n\n\n2. The conclusion that GNNs can model interactions better on partitions that have high walk index (i.e. more interconnected) seems to crucially depend on the choice of aggregation function is tied to the graph topology. However, it seems possible to use different aggregation/pooling function that delineates from the graph topology to capture interactions among partitions with low walk index. More explanations on how to interpret the results are needed.\n\n\nReferences:\n\n[1] Rong, Yu, et al. \"Dropedge: Towards deep graph convolutional networks on node classification.\" arXiv preprint arXiv:1907.10903 (2019).\n\n[2] Topping, Jake, et al. \"Understanding over-squashing and bottlenecks on graphs via curvature.\" arXiv preprint arXiv:2111.14522 (2021).\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback, for highlighting the interest and novelty of our theory, and for noting that the paper is well-written. We treat your comments and questions below. If our response is satisfactory, we would greatly appreciate it if you would consider raising your score.\n> (a) to show that using separation rank to understand GNNs is relevant, then the authors should outline how the analysis carries forward to standard GNNs\n\nAnalyzing neural network architectures identical to those popular in practice is often notoriously difficult. Accordingly, it is customary for works in deep learning theory to analyze different variations of these architectures. Following numerous past works (see lines 144 to 152 of the paper), we analyze neural networks with product aggregation, and demonstrate the applicability of our conclusions to architectures with other aggregation types via experimentation, regarding formal proof of the applicability as an avenue for future work. As stated in lines 163 to 166, some of the past analyses of neural networks with product aggregation were later extended to account for additional aggregations. We believe our theory may be similarly extended, and intend to pursue this route in future work.\n\n> (b) to show that walk index of partitions in a graph determines GNN performance, then the authors should examine the case where the original graph is replaced with a fully-connected graph, and discuss GNNs with Graph Transformers\n\nIncreasing connectivity improves expressivity in terms of separation rank, and there is evidence for it improving performance in practice. However, the performance in practice depends not only on expressivity but also on optimization and generalization, and from that perspective excess connectivity may lead to problems, for example over-smoothing and over-squashing. This is discussed in lines 203 to 213. Regarding comparison to Graph Transformers, our work focuses on message-passing GNNs. Analyzing the strength of interactions that Graph Transformers can model and comparing it against our results for message-passing GNNs is a direction we view as appropriate (and interesting!) for future research.\n\n> (c) to propose an edge sparsification algorithm, then comparisons with stronger baselines are needed, such as DropEdge [1] and curvature-based graph rewriting methods [2].\n\nEdge sparsification algorithms, such as the one we propose, attempt to maintain the prediction accuracy as the number of removed edges increases, with the goal of reducing computational and/or memory costs. The sparsification is done once, as a preprocessing step, and is fixed during training. Thus, in their original form, DropEdge and graph rewiring algorithms such as that from [2], whose goal is improving prediction accuracy (rather than efficiency), are incomparable to edge sparsification methods. Specifically, DropEdge requires storing the whole graph throughout training, while graph rewiring algorithms typically add or remove only a few edges, with the resulting graph having roughly the same number of edges as the original one (or even more edges). One may try to adapt curvature-based rewiring algorithms to edge sparsification. We believe doing so and comparing them to WIS is an interesting topic for future work.\n\n> ...it seems plausible for GNNs to model partitions that are less-connected (e.g., Fig 2 -left) if one delineates the aggregation function from the graph topology, which is also commonly used in the literature of graph rewriting (e.g. [2]).\n\nThe aggregation in the standard message-passing GNN formulation is done according to the graph structure. Hence we focus on this case in the paper. Indeed, it is possible to detach the pooling geometry from the input graph structure, in which case our results apply as is with the walk index over the input graph replaced by that of the graph defining the pooling geometry. We hope the above has addressed your inquiry; if not please let us know.\n\n> Can the authors provide more explicit interpretations of their results and comparison with related work using separation rank for CNNs/RNNs?\n\nCNNs and RNNs can be cast as GNNs with certain input graph structures – grid graph for CNNs and chain graph for RNNs. Accordingly, our separation rank bounds extend those established for CNNs and RNNs to GNNs with arbitrary input graph structures.  We will mention this point in the text. Thank you for bringing it up!\n\n> How would the WIS algorithm compare to a simple baseline: replacing the original graph with a fully-connected graph, followed by randomly dropping edges (as opposed to (i) edges are removed randomly from the original graph)?\n\nSince the baseline ignores all information about the original graph structure, it is expected to yield poor prediction accuracy. To affirm this expectation, we ran experiments over the Cora dataset using GCN. Indeed, **it led to substantially worse test accuracy compared to the rest of the baselines and WIS**. Specifically, over the graphs obtained by the proposed baseline, the test accuracy was roughly 73% on average for each of the edge sparsity levels – 0%, 5%, 10%, …, 100%. This is around the test accuracy one gets when removing all edges, and in particular significantly lower than that achieved by WIS (or the other baselines) — cf. Figure 3 (left) in the paper.\n\n> “...It seems possible that the optimal partition choice depends on the downstream tasks (e.g., graph-level clustering versus node-level prediction). Can the authors provide more details and recommendations?”\n\nExcellent point. Indeed, the optimal choice of partitions can vary depending on the task at hand. As stated in lines 272 to 275, we focus on a specific instantiation of the general WIS scheme which is tailored for vertex prediction tasks (these are particularly relevant with large-scale graphs). Exploring other instantiations, and methods for automatically choosing partitions, are regarded as promising avenues for future work."}, {"review_id": "dzyLsMqsCc", "reviewer": "Reviewer_2FCe", "summary": "The paper proposes a new way to analyze the capacity of GNNs based on the complexity of interactions they can model across a partitioning of the nodes. In particular, this complexity is quantified via *separation rank*, and, for a certain kind of GNN with product aggregation, this rank is proved to scale with *walk index*, the number of random walks originating from a vertex on the partition's boundary. Experiments indicate that this finding generalizes beyond the particular GNN in the proofs. First, three different GNNs are shown to perform better at an image classification task when the data are converted to a graph so as to maximize walk index across the relevant partition. Second, the paper proposes WIS, a way to reduce the number of edges in the graph while maintaining GNN performance, based on maintaining high walk indices. WIS is shown to outperform prior methods on several real-world networks.", "questions": "- Do you see this work as totally orthogonal to WL-isomorphism-based limitation work? As I see it, those results are all-or-nothing, in the sense that they show GNNs either can or cannot distinguish two kinds of graphs. The bound here instead is somehow softer and more nuanced, showing that the complexity at which the GNN can model some interaction (as quantified by separation rank) scales with walk index. Is there some sense in which, or some specific cases for which, the WL results are subsumed by your new results?\n\n- Related to the second 'weakness' above, do you see walk index as the fundamental notion here? If so, why?", "limitations": "Some limitations are noted throughout the work -- for example, it is noted that the theoretical results only formally apply to GNNs with product aggregation. A more collected discussion of limitations of the current analysis/understanding, and possible future directions, would be helpful.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Conceptual and theoretical explanations on the capacity of GNNs are an important topic, and this paper takes a fresh approach as compared to much of the WL-isomorphism-based work.\n- The paper is well-organized, and the writing is grammatical and easy-to-read.\n- Experiments show the superior efficacy of the proposed WIS method for graph sparsification relative to prior methods.", "weaknesses": "- While the machinery of the proof appears to be quite complex, I would appreciate some description of the proof concept in the main paper, even if it is at a very high level.\n- Related to the prior point on the proof concept, I am not totally convinced that walk index is the fundamental quantity here. Particularly the results in Figure 3 for Cora, where 2-WIS's performance is essentially matched by 1-WIS (which simply relates to node degrees), suggest that there may be a simpler explanation. To convince the reader, perhaps there could be more conceptual description of walk index and separation rank, and why the two are fundamentally linked. Or perhaps there could be more experiments showing that walk index is more predictive of performance as compared to other notions of connectivity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the positive feedback and support!\n\n> While the machinery of the proof appears to be quite complex, I would appreciate some description of the proof concept in the main paper, even if it is at a very high level.\n\nDue to lack of space we deferred a high-level description of the proof concepts to Appendix A. For the camera-ready version, we will use the additional space to incorporate this content in the main paper. Thank you for the suggestion!\n\n> Related to the prior point on the proof concept, I am not totally convinced that walk index is the fundamental quantity here. Particularly the results in Figure 3 for Cora, where 2-WIS's performance is essentially matched by 1-WIS (which simply relates to node degrees), suggest that there may be a simpler explanation. To convince the reader, perhaps there could be more conceptual description of walk index and separation rank, and why the two are fundamentally linked. Or perhaps there could be more experiments showing that walk index is more predictive of performance as compared to other notions of connectivity.\n\nOur theory implies that the walk index is a fundamental quantity in the sense that it governs the strength of interactions that the analyzed GNNs can model across a partition of vertices. Intuitively, it characterizes the amount of computation a GNN performs to aggregate information across the partition. With regards to experimentation, it is challenging to judge this way whether the walk index is more fundamental than alternative quantities, the reason being that factors beyond expressivity (e.g. ones relating to optimization and generalization) may confound results. We did however show that WIS, which is explicitly based on the walk index, sparsifies edges better than known alternatives. 1-WIS is also based on the walk index (despite being expressible in simpler terms) so we do not view its strong performance as an indication that the walk index may not be the central quantity. We believe further exploration of WIS, and in particular regimes where higher-order WIS performs better than 1-WIS, is a promising direction for future work.\n\n> Do you see this work as totally orthogonal to WL-isomorphism-based limitation work? As I see it, those results are all-or-nothing, in the sense that they show GNNs either can or cannot distinguish two kinds of graphs. The bound here instead is somehow softer and more nuanced, showing that the complexity at which the GNN can model some interaction (as quantified by separation rank) scales with walk index. Is there some sense in which, or some specific cases for which, the WL results are subsumed by your new results?\n\nThis work can be viewed as orthogonal to WL-based analyses of expressive power. Namely, WL-based analyses characterize which graphs a GNN can distinguish between. In contrast, for a given graph topology and fixed-size GNN, our work characterizes the type of functions the GNN can represent with respect to the vertex features, as measured by separation rank. We believe both approaches bear significance, yet while studies of the ability of GNNs to distinguish non-isomorphic graphs are abundant, much less is known about the type of functions GNNs can efficiently represent with respect to the vertex features. We hope our work can lead to further progress along this line, whether through the notion of separation rank or through other notions of complexity that take into account the vertex features.\n\n> Some limitations are noted throughout the work -- for example, it is noted that the theoretical results only formally apply to GNNs with product aggregation. A more collected discussion of limitations of the current analysis/understanding, and possible future directions, would be helpful.\n\nAs you noted, we mentioned possible limitations of our work throughout. In the revised manuscript we will also include a concentrated account of them and future directions in the summary section. Thank you for the suggestion!\n\n\n"}, {"review_id": "YQoKo1RD6q", "reviewer": "Reviewer_uCaB", "summary": "The paper studies how to characterize the ability of Graph Neural Networks (GNNs) to model the interaction given a partition of vertices. They quanlify the interaction strength with separation rank, and prove that it is governed by walk index (number of walks starting from the partition boundary). This relation is empirically demonstrated in their experiments, where a GNN with higher walk index beats the one with lower Walk Index. Lastly, Walk Index Sparsification is proposed to perform edge deletion based on Walk Index, and it markedly outperforms other baselines in terms of preserving prediction accuracy. ", "questions": "See Weaknesses.", "limitations": "As stated in Weaknesses, the computational overhead is a concern.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- An overall interesting theoretical work that supports the intuition: the interaction between two parts in a graph depends on how much interconnected their boundary is.  \n- The orginization is good, the theoretical analysis looks sound and the experiments are solid. The application to edge sparsification is impressive. ", "weaknesses": "- Walk Index Sparsification is unable to scale up to large graphs with deep GNNs, given its $O(|E||V|^3\\log(L))$ complexity. Correspondingly, the experiments only covered 2-WIS and 1-WIS. To further improve, the authors could discuss some potentially efficient implementations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and feedback. We are glad that you found our theory interesting, supported by solid experiments, and with an impressive application to edge sparsification. We address your concern below, and would greatly appreciate it if you would consider increasing your score.\n\n> ​​Walk Index Sparsification is unable to scale up to large graphs with deep GNNs, given its $O(|E||V|^3 \\log (L))$ complexity. Correspondingly, the experiments only covered 2-WIS and 1-WIS. To further improve, the authors could discuss some potentially efficient implementations.\n\nAs discussed in lines 284 to 293 of the paper, a naive implementation of (L - 1)-WIS (i.e. WIS for depth L GNNs) indeed requires runtime cubic in the number of vertices. While exploration of more efficient exact implementations (including ones involving parallelization) is left for future work, we propose and evaluate an extremely efficient approximation, namely 1-WIS (i.e. WIS for depth 2 GNNs), which requires only linear runtime and memory. For example, we demonstrated the applicability of 1-WIS to depth 10 GNNs (see Appendix H) over the OGBN-ArXiv dataset, which has more than a hundred thousand vertices and a million edges. Running 1-WIS over OGBN-ArXiv takes only ~20 minutes on a single V100 GPU."}]

Author rebuttal:

Meta-review: This paper proposes to characterize how GNNs can model the interaction strength between a partitioning of nodes via separation rank, and proves the separation rank is positively related to a new defined walk index (the number of random walks starting from the partition boundary nodes). Reviewers agree that the theory is new and interesting, orthogonal to the traditional WL-based GNN expressivity analysis. One downside of the paper lies in its strong assumption on the element-wise product based neighbor aggregation function, which is rarely used in practical GNNs. The authors are suggested to extend their theory to standard sum/mean based aggregation functions (if possible to any extent) in addition to the empirical verification. Overall, a recommendation of acceptance is given.
Decision: Accept (poster)