Graph Neural Networks Are More Powerful Than we Think
Authors: Charilaos Kanatsoulis
Alejandro Ribeiro
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph neural networks
expressive power
representation
graph isomorphism
classification
spectral decomposition

Abstract: Graph Neural Networks (GNNs) are powerful convolutional architectures that have shown remarkable performance in various node-level and graph-level tasks. Despite their success, the common belief is that the expressive power of standard GNNs is limited and that they are at most as discriminative as the Weisfeiler-Lehman (WL) algorithm. In this paper we argue the opposite and show that the WL algorithm is the upper bound only when the input to the GNN is the vector of all ones. In this direction, we derive an alternative analysis that employs linear algebraic tools and characterize the representational power of GNNs with respect to the eigenvalue decomposition of the graph operators. We show that GNNs can distinguish between any graphs that differ in at least one eigenvalue and design simple GNN architectures that are provably more expressive than the WL algorithm. Thorough experimental analysis on graph isomorphism and graph classification datasets corroborates our theoretical results and demonstrates the effectiveness of the proposed architectures.

GRAPH NEURAL NETWORKS ARE MORE POWERFUL THAN WE THINK
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) are powerful convolutional architectures that have shown remarkable performance various node-level and graph-level tasks. Despite their success, the common belief is that the expressive power of standard GNNs is limited and that they are at most as discriminative as the Weisfeiler-Lehmen (WL) algorithm. In this paper argue the opposite and show that standard GNNs, with anonymous inputs, produce more discriminative representations than the WL algorithm. In this direction, we derive an alternative analysis that employs linear algebraic tools and characterize the representational power of GNNs with respect the eigenvalue decomposition of the graph operators. We prove that GNNs are able to generate distinctive outputs from white uninformative inputs, for, least, all graphs that have different eigenvalues. We also show that simple convolutional architectures with white inputs, produce features that count the closed paths in the graph and are provably more expressive than the WI. representations. Thorough experimental analysis on graph isomorphism and graph classification datasets corroborates our theoretical results and demonstrates the effectiveness the proposed approach.
INTRODUCTION
Graph Neural Networks (GNNs) have emerged in the field of machine learning and artificial intel- ligence as powerful tools that process network structures and network data. Their convolutional architecture allows them inherit all the favorable properties of convolutional neural networks (CNNs), while they also exploit the graph structure. Despite their remarkable performance, the success of GNNs is still to be demystified. A lot of research has been conducted to theoretically support the experimental developments, focusing on understanding the functionality of GNNs and analyzing their properties. In particular, permutation invariance-spiivariace (Maron et al. 2018).
stability perturbations (Gama al. 2020) and transferability (Ruiz et al. 2020a Levie et al. 202
are properties tantamount to the success of the GNNs.
Lately, the research focus has been shifted towards analyzing the expressive power of GNNs, since their universality depends on their ability to produce different outputs for different graphs. The common belief is that standard anonymous GNNs have limited expressive power (Xu al.) 2019) and that is upper bounded by the expressive power of the Weisfeiler-Lehman (WL) algorithm (Weisfeiler & Leman 1968). This induced increased research activity towards building more expressive GNNs by either mcreasing their complexity, or employ independent graph algorithms to design expressive inputs. In this work we argue the opposite. We prove that standard anonymous graph convolutional structures are able to generate more expressive representations than the WL algorithm. Therefore, resorting to handerafted features or complex GNNs to break the WL. limits is not necessary.
Our work is motivated by the following research problem:
Problem definition: Given pair of different graphs 9 and anonymous inputs X, X; ; is there GNN ó with parameter tensor H such that & [X;9, H), o (X:.. H) are nonisomorphic?
As anonymous inputs, we define inputs that are identity and structure agnostic, i.c., they cannot distinguish graphs or nodes of the graph before processing. Why anonymous? Because if the inputs discriminative prior to processing, concrete conclusions the discriminative power of GNNs,

---

cannot be derived. Analyzing GNNs with powerful input features only indicates whether GNNs will maintain or ignore valuable information, not if they can produce this information. This study does not underestimate the importance of drawing powerful input features, which is crucial for most tasks. However, it underscores the need for an alternative analysis.
This paper gives an affirmative answer to the above research question. Our analysis utilizes spectral decomposition tools to show that the source of the WL test as a limit for the expressive power of GNNs the use of the all-one input. This is expected, since analyzing the representational capacity of Φ (X; G. H) by studying & (1; G 7)) cannot lead to definitive conclusions. For this reason we study GNNs with white random imputs and show that they generate discriminative outputs, for at least all graphs with different eigenvalues. In particular, we prove that e (X;9, H), ø (X; 7 belong to nonisomorphic distributions, even though the input X is drawn from the same distribution. This implies that standard anonymous GNNs are provably more expressive than the WL algorithm as they produce discriminative representations for graphs that fail the WL test, yet have different eigenvalues. In fact, having different eigenvalues is a very mild condition that is rarely not met practice.
From a practical viewpoint, using white noise as an input to a GNN may be computationally intractable. We show, however, that there are two alternative architectures that are equivalent to GNN with white random inputs: (i) A GNN that operates on graph representations without requiring any input. (ii) A GNN in which input features are the number of closed paths each node participates. Note that these features can be viewed as the output of the first GNN layer, i.e., they can be generated from GNN. These results also imply that & (X: G, H) is more powerful than the WL algorithm even if we restrict out attention to countable inputs X. Our numerical results show that our proposed GNNs are better anonymous discriminators some graph classification problems.
Our contribution is summarized follows:
(C1) We provide meaningful definition to characterize the representational power of GNNs and develop spectral decomposition tools to study their expressivity.
(C2) We explain that the WL algorithm is not the real limit on the expressive power of anonymous GNNs, but it is associated with the all-one vector an input.
(C3) We study standard GNNs with white random inputs and show that they can produce discrim- inative representations for any pair of graphs with different eigenvalues. This implies that standard anonymous GNNs are provably more expressive than the WL algorithm.
(C4) We prove that standard GNNs with white random inputs can count the number of closed paths of each node, which enables the design of equivalent architectures that circumvent the use of random input features.
(C5) We demonstrate the effectiveness of using GNNs with white random inputs, or the proposed alternatives, vs all-one inputs in graph isomorphism and graph classification datasets.
The first work to study the approximation properties of the GNNs was by (Scarselli ct al.] (008a). Along the same lines (Maron et al.) [019b] Keriven & Peyre 2019) discuss the
Related work:
universality of GNNs for permutation invariant equivariant functions. Then the scientific attention focused on the ability of GNNs to distinguish between nonisomorphic graphs. The works of (Morris)
et al. 2019 Xu et al., 2019) place the expressive power of GNNs with respect to that of the WL algorithm and prompted various follow-up works in the area. Specifically, (Abboud et al. 2021
Sato et al. 22221) use random features to increase the separation capabilities of GNNs, whereas
(Tahmasebi et al. 2020) You et al.] 2021 [ouritsas et al. 2022) compute features related to the subgraph information. (1shiguro et al.] (020) uses label features in WL settings and (Corso et al.)
Beaini et al. 2021) use multiple and directional aggregators, respectively, to increase the GNN expressivity. GNNs that use k-tuple and k-subgraph information have been designed by (Maron et al. 2019a] Murphy et 2019 Azizian et al.) 2020) MMrris et al. [020]] Geerts & Reutter] | Giusti et al., 2022). These works use a tensor framework, and employ more expressive structures compared to simple GNNs. However, they are usually computationally heavier to implement and also prone to overfitting. Moreover, (Balcilar et al. 2021) design convolutions in the spectral domain to produce powerful GNNs, whereas (Loukas] [2019) studies the learning capabilities of GNN with respect to its width and depth. Finally. (Chen et al. 2019) reveal a connection between the universal approximation and the capacity capabilities of GNNs.
2020
(2019)
2

---

2 ON THE EXPRESSIVE POWER OF GNNS
One of the most influential works in GNN expressivity by (Xu et al. 2019), compares the representa- tional capabilities of GNNs with those of the WL algorithm (color refinement algorithm). The claim is that GNNs are at most as powerful as the WL algorithm in distinguishing between different graphs. This is indeed true when the input to the GNN is the constant (all-one) vector.
A question that naturally arises is Why limit attention to features x = 12", The constant vector might be an obvious choice study anonymous GNNs, however it represents only a small subset of GNN inputs. As we show in the next session, it is also associated with certain spectral limitations, that prohibit rigorous examination of the GNN representational power. The need for further analysis with general input signals is therefore clear.
To this end, consider graphs G, 9 with graph operators S, S E {0, 1J.N.. In this paper we focus graph adjacencies, but any graph operators can be used instead. We assume that S, S are both symmetric and thus admit eigenvalue decompositions S UAUT $ = ÜÄÄT, where U, U are orthogonal matrices containing the eigenvectors, and A, Å are the diagonal matrices of corresponding eigenvalues. G, 9 are nonisomorphic if and only if there is no permutation matrix II such that S IISIT".
A broad class of nonisomorphic graphs have different eigenvalues. To be more precise, let S, & be the set containing the unique eigenvalues of S and $ with multiplicities denoted by my, mi respectively. The following assumption is heavily used in the main part of this paper:
Assumption 2.1 S, S have different eigenvalues, ie., there exists X E S, such that X & S or my # m
When Assumption 2.1 holds, G. 9 are always nonisomorphic. Assumption 2.1 is not restrictive. Real nonisomorphic graphs have different eigenvalues with very high probability (Haemers Spence 2004). Corner cases where Assumption [.1 doesn' 't hold are studied in Appendix H First, we consider GNÑs that are constructed by the following modules, corresponding to the neurons a typical (non-graph) neural network:
Y=o E S*XH
The module in (1) is composed by a graph filter of length K followed by a nonlinearity a()). H represents the filter parameters and can be a matrix, a vector, scalar. In order to characterize the representational power of GNNs with general input X E NDD we provide the following theorem:
Theorem 2.2 Let 9, 9 be nonisomorphic graphs with graph signals X, X. Also let Vx, VA be the eigenspaces corresponding to X in S, S respectivelly. There exist GNN & (X;9. G, H) that produces nonisomorphic representations for G and & if:
1. There does not exist permutation matrix such that X =IIX, or
2. There exists X E S, such that X & â and X + 0, or
3. There exists X E 8, S, such that my & vix and X
#o
Theorem 2.2 highlights the importance of the imput X in the representational capabilities of a GNN. For problems in which inputs are given, it states that GNN can distinguish between nonisomorphic graphs if they have different graph signals or their signals are not orthogonal to the eigenspace associated with the eigenvalue that differentiates them. In problems where inputs not available, Theorem 2.2 provides guidelines on how to design input X from the graph.
Theorem 2.2 also indicates that the limitations of GNNs discussed in (Xu et al. 2019) are not due to the architecture but they are limitations associated with the input. In particular, x = I fails to satisfy condition 1, while it is also prone to fail condition 2 and 3, since the majority of real graphs have eigenvectors that are orthogonal to 1. This observation is the impetus to study GNNs with white
We define VA + V = {u u
E Vx; Vx: T4, an & V. V3) the exclusive of subspaces
3

---

random inputs. White inputs unonymous (they carry no information the graphs), they model
large set of GNN inputs and always satisfy the conditions of Theorem 2.2 Furthermore, as we show in section GNNs with random inputs can generate deterministic, countable features:
X diag (5") diag (S') diag (S?)..... diag (S--1)] NNx
that satisfy the conditions of Theorem 2.2 A nice interpretation of this result, given in section 5
connects X in (2 with high-order subgraphs and shows that GNNs count closed paths.
3 LIMITATIONS OF GNNS WITH 1 INPUT AND THE WL ALGORITHM
Using Theorem 2.2 we can explain why feeding a GNN with æ is limiting. The limitations associated with input problem appears in graphs that admit spectral decompositions with eigenvectors that are orthogonal (they sum up to zero). According Theorem 2.2 two graphs are the same except eigenvalues corresponding to eigenvectors that sum up to zero, GNNs with constant inputs are likely to produce isomorphic representations for the two graphs. To see this consider the graphs G, 9 with spectral deconpositions:
are also highly related to the limitations of the WL algorithm. The
S = UAU = Annnuy + Azuzus + Azuguy
(3)
$ = ÜÂU = =u + teugu + dguzuy
(4)
where A3 # 'z. If ug is orthogonal to 1 then:
s ==1:UA -AAT" ='== $*1 - = +
2 + A uguuu X2 (u u1 (u.1) u2
(5)
Nfuzu11 + Ajugu.1 xi (u u1 + X3 (u. u2 (6)
The diffused information GNNs with this naive input related to S* and therefore in the above example the decisive information that differentiates the two graphs is highly likely be omitted.
Graphs with cigenvectors orthogonal to can also affect the performance of the WL algorithm. the absence of features the WL algorithm is initialized with nodes iteratively. In graphs with eigenvectors orthogonal to 1, the propagated degrees have suffered critical information loss in the initialization, which in certain graph structures is impossible recover, as WL iterations progress. Further analysis on this subject can be found in Appendix C
S1, which is propagated through the
Classic examples of graphs with different eigenvalues, that the WL algorithm and GNNs with 1 input cannot tell apart, are presented in Figs.
In particular, these approaches decide that G and 9 in Fig. I and G and ; in Fig. 2 are the same. This due to the fact that these graphs con- tain eigenvectors that The case of Fig. T is straightforward. All
(a) g
(b) &
orthogonal 1.
Figure 1: WL indistinguishable graphs.
the nodes of G and & have the same degree, i.c., x is an eigenvector in both graphs and thus orthogonal all the remaining eigenvectors. As result, the node degrees (which the same for both graphs) are the only information that the WI. algorithm and GNNs with 1 input are able to process. The case of Fig. is more complicated; æ is not eigenvector in any of the graphs, but it is orthogonal to the eigenvectors corresponding to the cigenvalues that differentiate the two graphs. Consequently, the operation S1 negates vital information and the two approaches fail.
Detailed information about the eigenvalues and eigenvectors of the graphs in Figs. can be found in Tables 8 of Appendix
This information corroborates the issues discussed in the previous paragraph. As noted earlier and will be explained in more detail in the upcoming sections, GNNs are discriminative enough to overcome these issues and provide nonisomorphic repre-
(a) g
(b) ğ
Figure 2: WL indistinguishable graphs
sentation for and & in both Figs. 1
4

---

máne
Stechaste GNN Hick
Diggoral
(a) Stochastic GNN module
(b) equivalent model
Figure 3: GNN with random Gaussian input
4 FEEDING THE GNN WITH RANDOM INPUT
In this section we study the representational power of GNNs, by feeding them with random white inputs. Our analysis overcomes the GNN limitations associated with æ and derives rigorous conclusions. Consider the GNN module in ①
where H3 is scalar, i.e., y (Ek= St Before choosing an appropriate nonlinearity, let us focus on the linear convolutional graph filter of length K:
K-1
St x,
2
which we load with white random input æ TRN, i.e. E a: 0, E zero-mean random vector, also random vector with EE [z Thus, the expected value provides no information about the network. Measuring the covariance, on the other hand, yields:
[xx"'
O²I. Since æ is
K-1
K-1
K-1
K-1
cov [z]
22
Σ
S
vvx"
Σ
Sm
ax
S
K=0
K-
K
K-1K-1
2K-2
0²
S
hm Smh
hyhm
S* 5m
(8)
1m
m==
M=U
where h/g = o² Em,r Amhy, such that m + + k. The results of equation are noteworthy. We have shown that the covariance of a graph filter with random white input corresponds to a different graph filter with no input. Furthermore, the resulting filter has length 2K 1, whereas the original filter has length K. In other words the nonlinearity introduced by the covariance computation enables the filter to gather information from a broader neighborhood compared the initial filter. However, there is caveat that the degrees of freedom for h are K and not 2K 1. Further discussion on the subject can be found in Appendix D
In practice we want to associate the output of a GNN with feature for each node that is permutation equivariant. This is not the case with the rows or columns the covariance matrix in Therefore we choose (-) to be the variance of each node i.e..
2K Σ R=U
2K 2
(z) = var [z]
diag (cov [z]) = diag
N
Σ
Mydiag (S*). (9)
K=U
The stochastic GNN module, defined by the linear filter in and the variance operator is illustrated in Fig. 3a Regarding its expressive power, we present the following theorem:
Theorem 4.1 Let G, be nonisomorphic graphs. If Assumption 2.1 holds, there exists a GNN with modules in Fig. 3a that produces nonisomorphic representations, for the two graphs.
The implications of Theorem 4.1 are noteworthy. A GNN á (X;g, H) with white input produces outputs that are drawn from different distributions for all graphs with different eigenvalues. Further- more, measuring the variance produces equivariant node representations that can separate all graphs with different eigenvalues.
Proposition 4.1 The GNN module in Fig. 3a with white random input is equivalent to the GNN module in Fig. 3b with input up to degrees of freedom (dependencies) in the filter parameters.
5

---

The proof of Proposition 4.1 is by the definition (equation ( of the GNN module in Fig. 3b The claim is eminent. proves equivalence imput followed by variance operator with a deterministic graph filter followed by diagonal operator. Depending on the problem and the variance of the system one has the option to choose either of them. Further discussion the stochastic approach can be found in Appendix I
two GNN architectures; a standard graph filter with white
THE DIAGONAL MODULE
Proposition 4.1 proved the equivalence of the two GNN modules in Fig. 3 In this section focus on the module in 3b and analyze its unique properties. To be more precise, we study the following diagonal GNN module:
K
diag (st))
(10)
Note that the module (T0p is not exactly the same as the one Fig. 3b
since a nonlineatity is
added and the filter is of length K. As example. we test the proposed diagonal module on the graphs Figs.
[ and present the output y of (10) with parameters (ho. h1, h2, h3, hg, his) =
(10, 1, - 2. 4 i
and ReLU nonlinearity, in Table
Table 1: Outputs of G and ý of of the proposed diagonal module for the graphs in Figs.
NODE
GRAPH
B
C
FtG. 1
y
10.42
10.42
10.42
10.42
10.42
10.42
9
1.75
1.75
1.75
1.75
1.75
1.75
FIG.
y
7.5
7.5
7.25
7.25
5.25
5.25
7.25
7.25
7.5
7.5
7.9
7.9
7.65
7.65
5.65
5.65
7.65
7.65
7.9
7.9
observe that the output 10 of the proposed diagonal module produces embeddings that are different for the nodes of G and & in both Figs. 1 Therefore, there does not exist permutation
matrix II such that y = Hÿ and the proposed architecture is able to tell & and apart in both Figs. 1 input and the WL algorithm that fail distinguish between these graphs (as discussed in section 3}. We now study the diagonal module in the frequency
22
This is in stark contrast GNNs with
domain analyse the representational capabilities of standard GNNs:
An H un 2 ) =a
hadiag Σ
Σ
h A
=
Σ ha (Ar)
Un
K= n=1
(1I)
where h (An) EK-1 A the frequency response of the graph filter in 7 at Xn In simple words, the frequency representation of the proposed diagonal module, or standard GNNs with white input, depends on the absolute values of the graph adjacency eigenvectors. On the contrary, standard GNNs with constant inputs admit a different frequency representation:
K-1
K-1
K
N
N
=1-0
Σ 0
S
Σ
Σ
& u, u Ag
a
Σ
h (An)) u. 1um
(12)
J
n=1
As we can see both outputs y, Y1 are functions of the graph eigenvectors. The question that arises is which function, |u,.] or (u u., results in more expressive GNNs. The naive answer is that depending the graph, there is trade-off between the information loss caused by |u,,l or (u un However, after adding a second layer, GNNs with white inputs are always more powerful than GNNs initialized by 1. This will be explained in more detail in the next section.
closer look at equations [00 and reveals further insights regarding standard GNNs with anonymous inputs. In particular,

---

Ag
dud
2
x
7
8 x
He
Y
Byee-
Type2
(a) Type-1 GNN module
Type-2 GNN module
Figure 4: Proposed GNN modules
Theorem 5.1 A standard GNN d (X;9, H) defined in can count all the closed paths each
node participates, if initialized with white input.
The proof is the combination Theorem 4.1 and equation GNN can compute the following vector representations:
In particular, standard anonymous
dh diag (5*)
A uun
(13)
that count the number of k- length closed paths of each node. For instance, when & = 2, d indicates the degree of each node, whereas for = 3, it counts the number triangles each node involved in, multiplied by constant factor. For & 4, d holds information about the degrees of h-hop and 2 2-hop neighbors as well as the 4-th order cycles. Similar observations are derived by considering larger values of k. Graph adjacency diagonals are not only associated with k hop neighbor degrees but also with motifs that are present in the graph. This observation becomes even more valuable, if consider the significance of subgraph mining in graph theory (Kuramochi & Karypis 2001 Danisch et al. 2018)) 8). Our final observation is that, the k-th order closed paths are associated with the absolute values of the adjacency eigenvectors [u,],, whereas degrees are connected with (u,, un
The following theorem characterizes the expressive power of GNNs with modules as in (10
Theorem 5.2 Let G, be nonisomorphic graphs. If Assumption 2.1 holds, there exists a GNN with diagonal modules as in (10) that produces distinct representations for G, S.
DESIGNING POWERFUL GNN ARCHITECTURES
After analyzing GNNs with white inputs and introducing the GNN module in (TO). it is time to build practical powerful architectures. The modules we employ to build the proposed GNN architecture are presented in Fig. 4 Regarding their functionality provide the following result:
Proposition 6.1 A GNN designed with the diagonal modules of Fig.
4a (eq. (T0) in the input layer
equivalent to a standard GNN designed with the modules of Fig. 4b in the input layer, if the input the modules of Fig. 4b
(eq. eq. (T)) is designed according to:
X
diag (S") diag (S²) (54),da) ,diag (S?))...,,dis diag (SD-1))-
(14)
The claim of Proposition 6. is fundamental and relates standard GNN with white input standard GNN with countable input defined by (3T) Specifically, combining propositions 4. and y.ilds direct connection between the three considered architectures; standard GNNs with white input and variance nonlinearity, GNNs with no input and diagonal operator, and standard GNNs with input as in (4). Guided by these findings
design the GNN architectures presented in Fig. 5) The architecture on the left uses one type of GNN blocks (type-2) and the input is designed by equation (1). Furthermore, it is symmetric architecture and admits all the favorable properties of symmetric designs. On the other hand, the architecture on the right uses a combination of type-1 and type-2 GNN blocks and designing an input is not necessary. Although the design is not symmetric, it offers reduced number of trainable parameters and reuse of first layer features, which has been observed to benefit convolutional architectures. The expressive power of the proposed architectures is demonstrated in the following theorem:
Theorem 6.1 Let 9, be nonisomorphic graphs with graph signals X, X designed according to 14h. If Assumption 2.7 holds, then the proposed GNNs in Fig. can tell the two graphs apart.
7

---

Appn liker
Jibler
Upad Ciker
(a) Type-2 architecture
(b) Type-1 and type-2 architecture
Figure 5: Proposed GNN architectures
Corollary 6.2 The proposed architectures in Fig. Jae strictly more expressive compared GNNs with æ 1 or a S1 inputs.
Corollary 6.2 follows from Theorem 6.1 and the fact that both diag (Sº) = 1, diag (5²) = =S1 are included the proposed input X, dehned in (14).
Overall, our proposed analysis proves that standard GNNs @ ( are more powerful than the WL algorithm for both countable and continuous inputs.
7 SIMULATIONS
In this section we test the effect of using anonymous all-one inputs vs anonymous random inputs on the expressivity of GNNs. The task of interest is graph classification. In particular, we use graph isomorphism and graph classification datasets and train the standard convolutional GNN in (T) and GIN (Xu et al. 2019). GIN initialized with 1 is denoted as GIN, and GIN with random input denoted as GIN plus- For the standard GNN model we only test random inputs. To avoid practical issues associated with random inputs we the equivalent model of section instead, i.e., intialize both standard convolutional GNN and GIN according to equation 14
7.1 THE CSL DATASET
Our first experiment involves the Circular Skip Link (CSL) dataset, which was introduced in (Mur) phy al. 2019) to test the expressiveness of GNNs; it is the golden standard when it comes to
benchmarking GNNs for isomorphism (Dwivedi et al. 2020). CSL is symmetric graph dataset. contains 150 4-regular graphs, where the edges form cycle and contain skip-links between nodes. A schematic representation of the CSL graphs can be found in Appendix K Each graph consists of 41 nodes and 164 edges and belongs one of 10 classes. All the nodes have degree 4 and thus an cigenvector of every graph and orthogonal to all the remaining cigenvectors. As a result the degree vector is uninformative and so is any message passing operation of the degree.
is
and the WL algorithm fail to provide any essential information for this set of graphs and the classification task is completely random, as shown in Table 4 The proposed GNN architectures, on the other hand, have no issue in dealing with this dataset. In particular single diagonal GNN module with parameters (hg, ht. h2, h3g h4, hs, heg h7, hy he)
GNNs initialized with
1, 3: 1: 8: 7: 8: }) and a(.) being the linear function, is able to classify these graphs with 100% accuracy. To see this, we present in Table 2 the output 1 for every class, where is defined in (10) with the aforementioned parameters. The output the same for each graph in the same class but different for graphs that belong different classes. Therefore, perfect classification accuracy is achieved by passing the GNN output to a simple linear classifier or even a linear assignment algorithm.
Table 2: GNN output y for every class of the CSL graphs.
CLASS
5
9
73616
-45968
1059
-30593
-25345
-26001
-17555
-28543
16065
-21163
8

---

7.2 SOCIAL AND BIOLOGICAL NETWORKS
Next, we test the performance of the proposed architecture with standard social, chemical and bioinformatics graph classification datasets (Errica al., 2019). The details of each dataset can be found in Table To perform the graph classification task, we train a GNN with 4 layers, each layer consisting of the same number of neurons. The input to each GNN is designed by equation (14) with K = 10 and we also pass the k-th degree vector. Apart from feeding the output of each layer to the next layer, we also apply a readout function that performs graph pooling. The graph pooling layer generates a global graph embedding from the node representations and passes it to linear classifier. The nonlinearity is chosen to be the ReLU. An illustration of the used architecture, as well as detailed description of the experiments, is presented in Appendix K
To test the performance of the anonymous architectures we divide each dataset into 50- - 50 training- testing splits and perform 10-fold cross validation. We measure the micro Fl and macro Fl score for each epoch and present the epoch with the best average result among the 10 folds. The mean and standard deviation of the testing results over 10 shuffles are presented in Table 4 In Table M we ob-
Table 3: Datasets
Dataset
Graphs
Average # Vertices
Average Edges
Classes
Network Type
CSL
150
41
164
10
Circulant
IMDSBINARY
1,000
20
193
2
Social
"MDAMUTTT
1,500
13
132
Social
REDDI TIBENARR
2000
430
498
Social
REDD TTM
5000
509
595
5
Social
PTE
344
26
52
Bioinformatic
PROTEINS
1,113
39
146
Bioialormatic
MUTAC
188
18
20
Chemical
NC11
4110
39
73
2
Chemical
Table 4: Average testing score and standard deviation over 10 shuffles
Proposed
GIN
GIN pau (proposed-GiNN micro F1
Dataset
micro F1
macro
micro F1
macro F1
macro F1
CSL
100 + 0
100 + 0
10 + 3.3
1.8 + 0.6
100 + 0
100 + 0
IMDEBINARY
71.7 2.5
71.3
74.7 : 3.2
74.6 =: 3.2
71.6 1 3.4
71 1: 3.8
IMDEMULTI
46.1 2.8
44.2
50.3 = 2.8
48 + 3.4
48.6 + 2.9
46.1 + 4.2
REDDITBINARY
87.2+ 4.1
87.1 4.3
81.6 + 5.6
81.5 + 5.7
89.8 + 2.3
89.7 - 2.3
REDDITMULTT
5.2
52.4
22
50.9 1 2.4
5511.5
53.6 1.7
PTC
63.6
6.9
65.7 8.8
65.1
9.1
62.5 + 5.1
61.4+
PROTEINS
4.2
73
4.6
72.3 + 4.5
74.3 1: 4.8
73.1 = 4.5
MUTAG
99.3.7..3
87.2
9.3
89.8 + 7.6
88.6 1 8.8
89.8 +:
88.7 = 8.6
NCI1
2.1
74.3
2.1
77.2 = 1.9
77.2 = 1.9
76.3 + 3.7
76.2 = 3.8
serve that the proposed architecture and GIN plus markedly outperform GIN, in the REDDI TIITTIINAR dataset, and also show notable improvement in the RMULIT dataset. GIN, on the other hand, has a 3% advantage in the IMDBBINARE dataset, whereas in the remaining datasets the performances of the competing algorithms are statistically similar. The latter can be explained, since the vital classification components, of these datasets, are not orthogonal to x 1 and GIN, is not undergoing critical information loss. Overall, we conclude that properly designed GNNs, as the proposed and GIN can not only demonstrate remarkable performance in graph classification tasks, but can also handle pathological datasets such as the CSL. This is an indicator on the importance of the representational properties. However, what equally important is generalization capability, data handling and optimization, which we do not study in this paper.
8 CONCLUSION
In this paper we studied the expressive power of GNNs with spectral decomposition tools. We showed that, contrary to common belief, the WL algorithm is not the real limit and proved that anonymous GNNs can distinguish between any graphs with different eigenvalues. Furthermore, we explained the limitations of GNNs with all-one inputs and designed GNN architectures that overcome these limitations. Experiments with graph isomorphism and graph classification datasets demonstrated the validity of the proposed approach. With this work we move one step closer to understanding the properties of GNNs and analyzing their functionality.

---

REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. IJCAI, 2021.
Waiss Azizian et al. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2020.
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, pp. 599-608. PMLR, 2021.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. Advances in neural information processing systems, 29, 2016.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference Machine Learning, pp. 158-758. PMLR, 2021.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 33:13260-1327 2020.
Maximilien Danisch, Oana Balalau, and Mauro Sozio. Listing k-cliques in sparse real-workd graphs. In Proceedings of the 2018 World Wide Web Conference, pp. 589-598, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844 3852, 2016.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982, 2020.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. arXiv preprint arXiv: 19/2:v:9/2.00999/ 2019.
Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions Signal Processing, 68:5680-5695, 2020.
Floris Geerts and Juan Reutter. Expressiveness and approximation properties of graph neural networks. In International Conference on Learning Representations, 2021.
Lorenzo Giusti, Claudio Battiloro, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa.
Simplicial attention neural networks. CoRR, 2022.
Samar Hadou, Charilaos Kanatsoulis, and Alejandro Ribeiro. Space-time graph neural networks. In International Conference on Learning Representations, 2021.
Willem H Haemers and Edward Spence. Enumeration of cospectral graphs. European Journal of Combinatorics, 25(2):199-211 2004.
Ehsan Hajiramezanalli Arman Hasanzadeh, Nick Duffield, Krishna R Narayanan, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. In Neural Information Processing Systems (NeurIPS), 2019.
10

---

William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Katsuhiko Ishiguro, Kenta Oono, and Kohei Hayashi. Weisfeiler-lemmn embedding for molecular graph neural networks. arXiv preprini arXiv:2006.06909 2020.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32, 2019.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: IXX:::669..00 (0666099900)) 2016.
Michihiro Kuramochi and George Karypis. Frequent subgraph discovery. In Proceedings 2001 IEEE international conference on data mining, pp. 313-320. IEEE, 2001.
Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. Journal of Machine Learning Research. 22(272): 1-59, 2021.
Yujia Li, Richard Zemel, Mare Brockschmidt, and Daniel Tarlow. Gated graph sequence neural networks. In Proceedings of ICLR' 16, 2016.
Xiaorui Liu, Wei Jin, Yao Ma, Yaxin Li, Hua Liu, Yiqi Wang, Ming Yan, and Jiliang Tang. Elastic graph neural networks. In International Conference Machine Learning, pp. 6837-6849. PMIR, 2021.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2019.
Haggai Maron, Heli Ben- Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2018.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019a.
Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pp. 4363 0663-437. PMLR, 2019b.
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 Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances Artificial Intelligence, pp. 4602 4609, 2019.
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33: 21824-21840, 2020.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673, PMLR, 2019.
Andrei Nicolicioiu, Iulia Duta, and Marius Leordeanu. Recurrent space-time graph neural networks. Advances in Neural Information Processing Systems, 32, apr 2019.
Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transferability of graph neural networks. In Advances Neural Information Processing Systems, volume 33, pp. 1702-1712, 2020a.
Luana Ruiz, Fernando Gama, and Alejandro Ribeiro. Gated graph recurrent neural networks. JEEE Transactions Signal Processing, 68:6303-6318. 2020b.

---

Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp- 333-341. SIAM, 2021.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. Computational capabilities of graph neural networks. IEEE Transactions on Neural Networks, 20 (1):81-102, 2008a.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20( 20(1):61-80, 2008b.
Youngjoo Seo, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In Advances in Neural Information Processing Systems, pp. 362-3622-7 322,373,22 2018.
Behrooz Tahmasebi, Derek Lim, and Stefanic Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:2012.03114, 2020.
Petar Veličković, Arantxa Casanova, Pietro Liò, Guillem Cucurull, Adriana Romero, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations, ICLR 2018- Conference Track Proceedings. International Conference on Learning Representations, ICLR, 2018.
Yanbang Wang, Pan Li, Chongyang Bai, and Jure Leskovec. Tedic: Neural modeling of behavioral patterns in dynamic social interaction networks. In Proceedings of the Web Conference 2021, WWW '21, pp. 693-705, New York, NY, USA, 2021.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. N71, Series, 2(9): 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https
//openrevi n httt:/oorrmm.drrrre.... A55ml
Jiaxuan You, Jonathan M Gomes-Selman, Rex Ying, and Jure Leskovee. Identity-aware graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
12

---

Appendix
Table of Contents
A Preliminaries
13
A.1 Graph Neural Networks (GNNs)
14
A.2 Multiple feature GNNs
14
A.3 3 Notation
14
Relation to other architectures
Associating the WL. algorithm with the spectral decomposition graph
16
D The stochastie GNN module
17
D.I The effect of square nonlinearity
17
D.2 Computing the Covariance recursively
18
E
Proof of Theorem 2.2
18
E.1 Case 1: There does not exist permutation matrix II such that X IIX
18
E.2 Case 2:
There exists À E S, such that À & & and X V, + 0.
18
E.3
Case 3: There exists À E S, such that my F my and x V1 + V/
# #0.
19
F
Proof of Theorems 5.2 6.1
20
Proof Proposition 6.1
21
I nonisomorphic graphs with the same of eigenvalues
22
H.1 Graphs with the same distinct eigenvalues
22
H.2 Graphs with the same eigenvalues which are not distinet.
25
GNNs and isomorphic graphs
25
GNNs vs spectral decomposition
26
J.1
two graphs have different eigenvalues
26
J.2
two graphs
same of eigenvalues are distinct
26
J.3
The graphs have the multiset of eigenvalues that distinct
27
J.4
Stability and discriminability of GNNs
27
K
Experimental details
28
K.
Experiments associated with the graphs in Figs. and
28
Details on the experiments of section
28
A PRELIMINARIES
......,) N} is the set of vertices (nodes) and ε = (v, u)} are the edges between pairs of nodes. The 1-hop neighborhood (())) of node v is the set of nodes
Networks are naturally represented by graphs G == (V,E), where fI,...,
that satisfy (u, v) E A graph can also modeled by Graph Shift Operator (GSO) S E NNN, where S(i,)) quantifies the relation between node i and node j and = V/. Popular choices of the GSO is the graph adjacency, the graph Laplacian weighted versions of them. The nodes of the graph are often associated with graphs signals X E R xD also known as node attributes, where D is the dimension of each graph signal (feature dimension).
13

---

A.1 GRAPH NEURAL NETWORKS (GNNS)
A graph convolution is defined as:
K-1
2 S
(15)
where H (S) EK= S4 is linear filter of length K and æ, E R are the input and output of the filter respectively. Let S UAUT, be the eigenvalue decomposition of S. Then:
U
(16)
K-1
U
(17)
K-1
= Σ
A
(18)
where á, & are the frequency representations of æ respectively. The frequency representation of the graph filter is H (A) Σk- h& and can also be written as:
(
Σ h
(19)
Á (X:) is polynomial on X; and E; - A (X,) The simplest form of a Graph Neural Network (GNN) is array of graph filters followed by point-wise nonlinearities. The 1-th layer of the GNN is a graph perceptron, which is described by:
Σ T S* x )
x (+1)
(20)
Note that here we are using recursive equation, whereas in the main paper we used X for input and Y for output, make things simple. Common choices of (-) are the Rectified Linear Unit (ReLU) activation function, the Leaky ReLU or the hyperbolic tangent function.
A.2 MULTIPLE FEATURE GNNS
As mentioned carlier, the nodes of the graph are usually associated with graph signal, which is multidimensional, i.e., D and (')) a matrix. Although the architecture in (20) can also handle multidimensional graph signals, multiple feature GNNs are commonly used, which are described by following recursion formula:
X ( = S*x"
(21)
where ( E FxG represents set of F x G graph filters. Compared to the architecture in (20). the MIMÓ GNN employs multiple filters instead of one. and the outputs of the filters are combined produce layer output X (1+1) that has feature dimension equal G.
A.3 NOTATION
Our notation is summarized in Table
B RELATION TO OTHER ARCHITECTURES
GNNs have attracted significant attention and numerous architectures have been proposed. The first
GNNs of (Scarselli al. 2008b Kipf & Welling 2016 Battaglia et al. 2016 Defferrard al. 2016)
14

---

Table 5: Overview of notation.
Graph
Set of nodes
Set of edges
N x graph operator
X
GNN input; represents the N D matrix of node attributes (graph signal)
GNN input; represents the vector of node at- tributes (graph signal)
matrix output of a linear filter vector output of linear filter
Y
matrix output of GNN module; Y = a (Z)
y
vector output of GNN module; y = a (z)
scalar
vector
matrix
A
transpose of matrix A
A
A[k,;], k-th row of matrix A], k-th column of matrix A eigenvector matrix k-th row (row vector) k-th column of U
dg
U
U
Ul:.K k)
AA
k-th eigenvector, k-th column of U Identity matrix
1
vector of ones vector or matrix of zeros
point-wise absolute value
binomial coefficient
used simple convolutions in static data and graphs, whereas more sophisticated architectures utilize variety of attention mechanisms (Hamilton et al. 2017: Veličković et al. 2018 Liu ct al.
2021
Graph convolutional architectures have also been designed for tie-varyiin graphs and signals.
Some
of them exploit both the graph and the time structure (Hajiramezanali et al. 2019 Wang et al.
2021
Hadou et al.] 202 I), while others employ recurrent architectures (Li et al. 2016 Seo et al. Nicolicioiu al. 2019 Ruiz al. 2020b).
2018
is often the case that GNNs are presented in the literature using different definitions. The GNN by (Kipf& & Welling 2016) for example is written
x (1+1) = D 1/2 +S++1D0 (S 1/2 x ( = (D= H + +D x H
(22)
where S E (0, (0.1]NxM represents the graph adjacency, D is a diagonal matrix, with D(i, i) being the degree of node i. The matrix 1-2 (S I) D D-122 is also GSO S' and the formula in 22 can be written as:
x ((+1)
(23)
which is special of the MIMO GNN in 21 for K 2. Another way that GNNs represented in the literature via the following equations:
A AGGREGATE
x : : :uE(()))
((x!!)
(24)
((D COMBINE (1) AS
(25)
x ((+1)
( B(!)
(26)
15

---

where x
is the signal of node in layer I and the w-th row of the feature matrix X i.e.,
X (1)
X
Equivalently, A. B are rows of matrices A B respectively and
(
represent signals associated with node The majority of the architectures based the equations (24)-(6) can be written as combinations of the GNN modules in (21). Different architectures employ different functions for AGGREGATE and COMBING Popular choices of AGGREGATE functions include the mean, the sum, pooling functions or LSTM functions. The COMBINE routine, on the other hand, usually utilizes the concatanation or summation function. The settings that are mainly used are summation function for AGGREGATE and concatenation for COMBINE. This is due to the fact that summation-concant concateaon preserves the more information compared to other options Xu et al. (019)) It is then easy to see that:
A = ()
(27)
B = [A x()
(28)
((+1) (B() H() (Sx"H) H + xx
(29)
H (1)
where S is the graph adjacency and (
Therefore, the GNN defined in 29 is special
case of the GNN in for =
Now consider the GNN defined in (29) that consists of K layers and o--) is the linear function for the hidden layers and a nonlinear activation function in the output layer, i.c.,
X (1-1) Sx 10 H (1) HD (S I) x H for (O...., K 2}
(30)
(1-1)) a (SX(H x H for K-1
(31)
Then it holds that:
( (S 1) 1) ( H() H for lorl= {0,..... , K 2)
(32)
((++)) (sx ( x H() for K 1
(33)
As result:
K (()) =
x = o ((S 1)* ( H (11)..
(34)
which again corresponds the GNN in 21
The last equality holds since
K
x
K
SK-1
(35)
1=0
where (t) kI(n-Rji is the binomial coefficient. Overall there is direct connection between the GNNs defined by the equations (4 (26) and the GNNs defined by (2T). Furthermore, apropriate
n!
selection of GSO and nonlincarities in 21 with respect to the AGGREGATE and CCMB INE functions
in (24 26 makes the described architectures equivalent.
C ASSOCIATING THE WL ALGORITHM WITH THE SPECTRAL DECOMPOSITION OF A GRAPH
In section 3 we observed a connection between the limitations of the WL algorithm and graphs with eigenvectors orthogonal to 1. The WT. algorithm is initialized with either S1 and in
16

---

the remaining iterations this information is propagated (diffused) through the nodes. In particular, iteration & of the WL algorithm, node receives a multiset defined as:
Tht 23 b Σ An (u,,1) un (), j JEN,
(36)
where N² denotes the k- neighborhood of node If there is one-to-one correspondence between T7 and 1*)(1) for all nodes i then the WL algorithm can be analyzed by building and comparing the following features for each node:
X = S
S
(37)
In other words, if the summation operation is proper hash function for a specific graph, the WL algorithm equivalent to the feature generation of (37). In that case, we can use the spectral decomposition of S and the analysis of section 3 to characterize the limitations of the WL algorithm. Then the WI. algorithm admits the same limitations as the GNNs with æ input and it omits the information associated with eigenvectors that are orthogonal to 1.
D THE STOCHASTIC GNN MODULE
In this section we elaborate more on the proposed stochastic GNN module in Fig. 3a In order to implement it, we can either use the equivalent model in Fig. Bb or we can design empirical variance model. In practice, the input to the empirical model is a matrix E XM where each element is independently drawn from Gaussian distribution with zero mean and unit variance and M is the total number of samples. The output of the filter is Z = Σn S E N.NM M and the maximum likelihood estimate of the empirical covariance of Z takes the form:
Q = M
Zz"
(38)
Then the GNN output can be written as:
-ddag (Q) = M diag (zzT)
z
(39)
.M
The GNN module of the empirical variance model is illustrated in Fig. 6
X
2
Ag
z
Fmpiriiaal
Figure 6: Empirical variance GNN module
D.1 THE EFFECT OF SQUARE NONLINEARITY
Now discuss the effect of square nonlinearity in the representation of nodes, introduced by the variance operator. As mentioned in section 4 the nonlinearity added by the variance computation allows the proposed GNN to gather information from farther neighborhoods compared filter or the WI algorithm. To make things more concrete, consider the graph in Fig. 6 and let K 2, which corresponds running the WI. algorithm for iterations and graph filters that process S and S
linear
Table we present the representations produced by the stochastic GNN and the WL algorithm for each node of the graph in Fig. 6 In particular, present two iterations of the WL algorithm and the value that y in (39) converges to, for filter values (he. h1, h2) = (3, 5, 7). We observe that the WL algorithm represents nodes A and D with the same value, whereas the output of the stochastic GNN capable of separating these two nodes. Overall, the the nonlinearity in the variance operator allows acquiring global information, which can be vital in the resulting node representation of the graph.
17

---

Table 7: GNN vs WL algorithm on the graph in
Fig. for K
NODE
WL ALGORITIIM
GNN
A
2,33
675
B
3,
2
1085
C
3,233
1134
D
2,
3
633
E
1,
223
F
3,
2.
896
Table 6: graph
D.2 COMPUTING THE COVARIANCE RECURSIVELY
In the main core of the paper we presented 3 almost eguivalent GNN modules; the stochastic module with random Gaussian input, the diagonal module with no input and the standard GNN module with input designed by (14). On the basis of the requirements and constraints of each task, we can employ either of them in GNN architecture. For instance, in applications where computing the adjacency power diagonals is computationally prohibitive, we can use the empirical module Fig. [ The drawback is that for systems with high variance, significant number of samples will be required for the output to converge. This can be mitigated by computing the output in (39 recursively. To be more precise, let 2m be the m ma-th column of the filter output Z and Q(M)): Y(Mr) be the empirical covariance and output after obtaining M samples. Then the recursive equations can be written as:
Q(ar)=
1
Σ
Zm
1
M
Σ
Zm 2
ZM
M-1 --1
Q Q(
+
1
ZM (40)
M
M
M
M
M
diag (Q(M-1)) + diag (MM²MM = M -
1
y(M) diag (Q(M))
M V(M-1) +
|z 12
M
M
M
(41)
Therefore, using V(M) M-1 V(M-11 + M7 1/ allows for online computations and reduces the required memory complexity.
E PROOF OF THEOREM
To prove Theorem
2.2 consider the GNN module in I where Hş is scalar, that is,
Y
S X
(42)
k=0
E.1
CASE 1: THERE DOES NOT EXIST PERMUTATION MATRIX II SUCH THAT X IIX.
Consider an 1- layer GNN with 2 neurons defined by ho = 1, h, = 0, i + 0 and fgg -1, /1 0, i 0, i.e.,
Y, (X), Y, = o (-X)
(43)
Summing up the output of the 2 neurons to produce the final GNN output yields Y Y = when the o-)) ReLU((). As result, the output of the GNN is the graph signal and since there does not exist permutation matrix II such that X IIX, this GNN decides that and 9 are different.
E.2 CASE 2: THERE EXISTS À E S, SUCH THAT À & AND X VA * 0.
Let = ..,..., Ap} be the set containing the unique (non-repeated) eigenvalues of S and $ (Âi...., ) be the set containing the unique eigenvalues of S. Note that the eigenvalues of S, $
18

---

not required to be distinct. Also, let (M1....., My] be the set of all distinct eigenvalues of S and S, i.e., 14 E S US and 14 + Pj: i + j. Suppose that S, S have least one different eigenvalue, ie., there exists À E S such that & S.
Recall from Appendix A that graph filter can be represented in the frequency domain by:
K-1
H H = Σ
h&
(44)
k=0
Then:
H (H1)
Mi 11 K
ho
H (12)
p2 11 ... 112
K-1
h1
Wh
(45)
:
i (ma)
My My ... Mg
-h
Win is a Vandermonde matrix and when K = y the determinant of W takes the form:
det (W) = Higisiso (#--H4 (11-))) M4y)
(46)
Since the values μ4 are distinct, W has full column rank and there exists graph filter H (-) with unique parameters h that passes only the À eigenvalue, i.e.
H ((L) = 11 if -=
(47)
if
Under this parametrization, the filter H (-) takes the form H (S) = VVV." where VA is the eigenspace (orthogonal space of the eigenvectors) corresponding to X, and $ = 0. Then the output of the GNN, for the two graphs, takes the form:
Y = (H (S) X) = (VAVTT)
(48)
Ý = a H (8) =0
(49)
Under the assumption that X" VA * O. we also have V V As result a (VAVI X) + 0, there does not exist permutation II such that Y = HY and the proposed GNN decides that the two graphs are different. Note a (V3 V X) * O always holds when, for example, leaky ReLU used that allows both positive and negative values to pass. In the case where o.) =ReLU(.) the proof still valid as long as there is at least one positive value in V, V X. In case V, V X < 0 we can without loss of generality consider the filter:
-1, if
H (m4)
(50)
0, #F
that results in (-VAV + O.
E.3 CASE 3: THERE EXISTS À S, SUCH THAT my + my AND X (v #0.
Let S fai.... Ap) be the set containing the unique (non-repeated) eigenvalues of 5 with multiplicities (ma,...., mx,} and $ { A be the set containing the unique eigenvalues of S with multiplicities ...., m J. distinct. Also, let (/1....,,4) be the set of all distinct eigenvalues of S and Š, i.e., P4 E SUŠ and 14 * pg; V Vi j. Suppose that S, S have at least one common eigenvalue but with different multiplicity, i.e., there exists À S,S,such such that my o m..
Note that the eigenvalues of S, Å are not required to be
Under the parametrization of 47 H (S)) = VAVY where VA E RNxxs is the eigenspace
of S corresponding to X, and H S = V.VT. where VA E Nx is the eigenspace of Š
19

---

corresponding to A. Then the output of the GNN, for the two graphs, takes the form:
Y = (H (S) X) = (V)Vz'
(51)
== H ( = (ViV2')) x)
(52)
The subspaces Vx; VA can be written
Vi Qc Qnl W. V2 Qcc. Qn w,
(53)
where Q E RN is the common subspace between V, and V, and Qn RNX((x-)) Qn
R NNx are subspaces of V, and VA such that Qn no, (0). Since mA # m,, Qn Qn +
{0), where + denotes here the sum between subspaces. Furthemore W E Rm W RMAXA are square orthogonal matrices.
As result
Qnl Y= σ (VAV, x) (Qc:.Q.) Qc. Qul" xx a (Q.Q) + Qx
(54)
Y (VVXx) (1Q:. [io] Qn Qn 1" x o x
Qn)"
(55)
We define:
V e V2 = {u u VA: Vx w VA U b.b.
(56)
as the exclusive sum of subspace. If x Vx t
* 0 then either Q X + 0 or Q X + 0.
Therefore, there no permutation II such that V, V X nV, V X since there no permutation
that makes these vectors collinear. Our previous analysis shows that suitable nonlinearities will also guarantee that there is permutation II such that Y IIY.
F PROOF OF THEOREMS
5.2 6.1
The proof of Theorems 5.2 2
is equivalent and very similar the proof of Theorem 4.1
We begin
by proving Theorem 5.2 To prove Theorem 5.2 let us consider again the GNN module in 10
didi (5²)
(57)
For simplicity we assume that a (-) a linear function. In eq. 443 we show how to produce the linear function from ReLU, Assumption 2.1 holds, there exists À E S, such that $ S or ma o myx We use the proof of Theorem 2.2 and conclude that there exists a graph filter H (-) with unique parameters that passes only the eigenvalue, i.c.,
( = Of
(58)
First we study the case where S, but $ S. Then H (S) = V V. where VA E Nxma
the eigenspace of S corresponding X, and H (s) 0. The output y of (57). for the two graphs, takes the form:
y diag [H (S)) [V 1 + VA m] Σ V3
(59)
9 diag
H ()) 0
(60)
20

---

where V1 is the i-th column of Vi. Since VA by definition, there does not exist permutation II such that y = Hy and the proposed GNN can tell the two graphs apart.
Next we study the case where À S, but mı + mix Then H (()) V.VA and H S
VA V.V. where VA E No is the eigenspace of Š corresponding to The output y of 75). for the graphs, takes the form:
diag [ (S)) =
Vali i]
(61)
ÿ diag H (T()) =
V 1il
(62)
We observe that:
1 y 1d diag
[H (5)) Trace (V.V)) ma
(63)
1 1d diag H $
Trace [iV
mi
(64)
Since my F my, there is permutation II such that y T and the proposed GNN can tell the two graphs apart. This concludes the proof for Theorem 5.2 Using Proposition 6.1 we prove the equivalence of Theorems 5.2 and 6. and therefore the proof the same.
To prove Theorem 4.1 we need one more extra step. In particular, we plug the filter, with parametriza-
tion as in 58) in equation for S, S,i.e.,
K
K-1
cov [z; S
Sk
Σ
Sm
V.V. =VV
(65)
m=
K
K-1
cov
S
S
Sm = VA VA
(66)
m==
where the last equality in 65 holds, since VA, VA are orthogonal. Then the output of 9 for the two graphs, can be written as:
var [2; S) diag (cov [1) = VAl. 111 + + [3/.m
V
(67)
m
9 = var [z; S) diag (cov S)) = VAl. 111 + m/
V
(68)
If S but $ S. If E S, but m. A m.. 1" y 7 1 In any case, there does exist permutation II such that = Hī and the proposed stochastic GNN can separate the two graphs.
G PROOF OF PROPOSITION 6.
The output of type-1 module can be cast as:
y hediag (s*) (Xh),
(69)
hg :
when X is designed as in 14 and
is the vector of filter parameters. The same output
hg -
can be produced by the type-2 module when Hg is vector and K 1. On the other hand, set of
21

---

K type-1 modules in the input layer can produce the X in 14 To see this, consider the following type-1 GNN modules.
K Σ
Vi
hi
diag
(5*))
i=
00 o......,K K-1,
(70)
A=
where
1, if i-i=k
(71)
0, if i
Concatenating the outputs yi into W = Iyo..... 9K-1l results in the in (14 which we can apply type-2 module and produce the same output type-2 GNN module with input in (4).
H NONISOMORPHIC GRAPHS WITH THE SAME SET OF EIGENVALUES
In the core of this paper, we discuss the ability of GNNs to distinguish between nonisomorphic graphs that have different eigenvalues. This analysis covers the majority of real graphs, since real graphs almost never share the same eigenvalues. However, there exist interesting cases of graphs with the same set of cigenvalues that GNNs can also distinguish. In this section, we study these cases and provide interesting results.
H.1 GRAPHS WITH THE SAME DISTINCT EIGENVALUES
We consider the case where S, S have distinct eigenvalues which are the same, i.c., A. Formally:
Assumption H.1 S, Š have the same distinct eigenvalues, i.e., S S S and S S S, with X; + Xj for all i,
Lemma H.2 characterizes nonisomorphic graphs with distinct eigenvalues.
Lemma H.2 When S, S have the same distinct eigenvalues, G, 9 are nonisomorphic if and only if there is no permulation matrix II and diagonal 11 matrix D such that:
-ÜÜ
Proof: S UAU Śー Since S, Å have the same distinct eigenvalues, have Å. To prove the 'fowward' statement assume that G, 9 are nonisomorphic, i.c., there does not exist permutation matrix such that S ISSII If there exist permutation matrix and +1 diagonal matrix D such that U NÙ D, then:
S = UAUT
= IISIT.
By contradiction when S, $ have the same distinct eigenvalues, 9, 9 are nonisomorphic if there do not exist a permutation matrix II and diagonal +1 matrix D such that U NÚD.
To prove the 'backward' statement assume that there not exist permutation matrix II and diagonal 11 matrix D such that U IıD D. If I, & are isomorphic, i.e., there exists permutation matrix II such that S IISII", then:
UAUT ATAÜ
which implies that un +IIū, for all where un ún refer the columns of U, Ú respectively. As result, U DÚD and by contradiction we prove the "backward' statement which concludes the proof. 0
In nutshell, Lemma H.2 states that in order for G, I to be nonisomorphic, while Assumption H.I holds, the two graphs need to admit different eigenvectors that correspond to the same eigenvalucs. As side note, mention that S, S can still span the same columnspace, under row permutation. However, the power on each eigendirection has to be different for them to be nonisomorphic.
We extend the results of Theorem 2.2 the following:
22

---

Theorem H.3 Let 9, & be nonisomorphic graphs with graph signals X, X. There exists a GNN that tells 9 and & apart if:
1. There does not exist permutation matrix such that X IIX, or
2. Assumption 2.1 holds and V X + O, or
3. Assumption H.1 holds and X un O for all eigenvectors un or X + 0 for all eigenvectors ú.
Proof: The proof for cases I and 2 can be found in Appendix E Case 3 includes Assumption H.l
i.e., both S, S have N distinct eigenvalues, where N is the number of nodes in each graph, and also
S. S share the same cigenvalues. To prove this last part of Theorem 2.2 we consider 1-layer GNN with N neurons. Each neuron consists of a graph filter that isolates one eigenvalue and sets to one, in Appendix E Then, each neuron is described by the following set of equations:
Y, (H, (S)
I....,N N
(72)
(Ax) = 1. in 0, in
n1 n= N
(73)
For the rest of the proof, we will assume that a(.) is the linear function. This is without loss of generality since if we double the number neurons in the layer and set (+) =ReLU(.) we can produce the same output as the linear function by using the same trick as in Appendix F. In particular, N of the graph filters will follow the equations in (73) and the remaining N filters will follow the same equation with - instead,
in (0).. Then for each eigenvalue we have a pair of
filters, one with +1 and one with -1 in the filter equations. Summing up the outputs of these neuron pairs will produce an output that is the same if (-)) was the linear function.
The output of the GNN for the two graphs takes the form
Yn Hn (S) = un X,
n n= I....,NN N
(74)
Y, Hn (5) X = in un X I...,,N N
(75)
Y. un [2 1l ... u [DD]
n= 1..,,,, N
(76)
Y, in 1 2
N
(77)
Now we assume that X un * for all eigenvectors un 1, N. As result, there exist least one column in each Y, that is not equal to the zero column. We can then collect one nonzero column from each Y, and form matrix M as:
Ta 0. 0
0, 0,02...... ....0....
M [u (uf ,..., un (u)) [uj01.... uNaN]= =
A, (78)
L.. aN
where T;, Øy columns of X such that u. + 0. u/ # 0, A is diagonal matrix and a, * for all n. If also collect the corresponding columns for each Y, we can form:
d 0
0, 0..2. 0
M- = [1ū] (ūf i.) ..... Vxx (ūK [us didd...... ucdāN]=
Ô A, (79)
0.0,..., .N.
23

---

En Audioo )
En Audkag (5*)
Ex X
Σn hudian (5th)
Figure 7: GNN architecture
where Á is diagonal matrix but &n are necessarily nonzero, as ū T;, u are not necessarily nonzero. Since G, are nonisomorphic and Assumption H.1 holds, we can use Lemma H.2 Consequently, there are no permutation matrix II and diagonal +1 matrix D such that = HUD. This implies that there does not exist permutation matrix such that M = IIM. To complete the proof, we consider the output of the considered GNN to be the concatenation of Yn, n I,...,N. N.
In particular, the outputs for G, 9 are:
Y Yi, Y2..... YNl
(80)
Y Y1, Y2, ...,, YN
(81)
The columns of M, M are also columns of Y. Y. Since there does not exist a permutation matrix II such that M IIM, there does not exist II such that Y IT and the GNN decides that G, ğ are nonisomorphic. Note that the same analysis is applicable if we assume that X ûn * 0 for all eigenvectors ü, ,,..., N and is therefore omitted. Now our proof is complete. 0
We also extend the results of Theorems 4.1 5.2 the graphs are the same.
6.1
to incorporate the cases where the eigenvalues of
Theorem H.4 Let G, be nonisomorphic graphs. Then there exists a GNN with modules as in Fig. or as in Fig that tells the two graphs apart if:
1. Assumption 2.1 holds or
2. Assumption H. holds and
(a) There no permutation matrix II such that [0| HÚ or
(b) J uu, # 0 for all eigenvectors uh or T û. F 0 for all eigenvectors ú...
Proof: The proof of Case 1 can be found in Appendix F In order to prove case 2 of Theorem H.4 we use the architecture illustrated in Fig. 7 This GNN is designed with 2 layers, each them consisting of N neurons. Recall from the previous proofs that there exists graph filter H (S) with unique parameters that isolates one eigenvalue (the ni-hh eigenvalue) and sets it to one, i.e.,
1, if i=n
H (1.)
(82)
0. i
Since the considered graphs have N distinct eigenvalues, we build the first layer of Fig. with N neurons described by the following set of equations:
yn (diag
H (1) (S)))
N n n= N
(83)
1. if
0 (A,) (A)) = 0. if if
(84)
24

---

Under the above parametrization, the filter H²) (S) takes the form H (S) un where un is the eigenvector corresponding to the n-th eigenvalue of S. Then the output of the first layer for the two graphs takes the form:
yn (diag ( uun
||t, 2
1, N
(85a)
Yn a (diag (ú., |
N
(85b)
Since both S, S have distinct eigenvalues, we can concatenate the output of each neuron and result in layer-1 outputs
yo U0 Y O
(86)
If there does not exist permutation matrix II such that [U] proposed GNN can tell the two graphs apart.
NU one layer sufficient and the
For the second layer of the GNN Fig. we consider the following parametrization:
Yn
H (S) (S)x);
,,...,NN N
(87)
1. if i=n
H 3 (A:)
N,
(88)
if
where X y [U] is the output of the first layer. Then the final output of the GNN for the two graphs can be written as:
Y, H (S) X = un u. n= ,,...,NN
(89)
Y, H ($) x u Ü/ n I....,A N
(90)
Y, Un U1 Ub
T .....
u Muun I....,N [ []
(91)
Y, ún [1
n = I,...,N
(92)
If we assume that [ Un, * O for all eigenvectors u, or ÜT úú, o O for all eigenvectors ün we can use the same steps as the proof of Theorem H.3 and show that the proposed GNN decides that the two graphs are different. Note that in layer we can use the stochastic modules in Fig. 3a and the proof still holds, since the filter with parameters as in (84) yields:
K-1
cov [z; S
hg. S
hm Sth Ur u Un u U. un
(93)
and the same output as in 86) can be produced. Also, by using Proposition 6.1 we can substitute the modules the first layer with the modules Fig. and the proof still holds.
H.2 GRAPHS WITH THE SAME EIGENVALUES WHICH ARE NOT DISTINCT.
The last case appears when the graph adjacencies have the same eigenvalues, which are not distinct and have the same multiplicities. This case is more complicated, since the two graphs can be nonisomorphic even if there exist permutation matrix II and diagonal matrix D such that U NÚ D (the condition in Lemma H.2 does not hold). Analysis and results for this case left for future work.
I GNNS AND ISOMORPHIC GRAPHS
The core of this paper studies the ability of GNNs to distinguish between nonisomorphic graphs. Another important question is whether a GNN can tell if two graphs isomorphic. The answer affirmative. GNNs are permutation equivariant architectures and can always detect isomorphic graphs. To make things concrete, we present the following proposition:
25

---

Proposition L1 Let 9, 9 be two isomorphic graphs, i.e. S ISSIT Also let X, X be the graph signals associated with G, 9 that satisfy X IIX. Then any GNN with modules as in decides the two graphs are the same.
is permutation equivariant. To see this, consider the graph adjacencies and $ such that S IISII where II is permutation matrix. Then equation
Proof: To prove this proposition, it suffices to show that the output in T
I
gives:
K- Σ
K Σ kmm0
==o o
Shh
H
!
Σ km0
hy (IIS"II) H
@
hi IIS
XH&
(94)
K-1 S* XH
II
IIY
(95)
R=0
where equality (1) holds because (ISIITT** II and equality (2) comes from the fact that II'II I. Therefore, Y is equivariant in permutation. Overall GNNs with modules in produce permutation equavariant outputs for isomorphic graphs.
Let 9, & be isomorphic graphs. Then any GNN with modules as in Fig. or Fig. decides that the two graphs are the same.
Proposition 1.2
Proof: To prove this proposition, it suffices to show that the output in 10 is permutation equivariant.
To see this, consider two graph adjacencies S and such that S ISI where II is a permutation matrix. Then Equation (T0) gives:
K
K-
hgdiag (st)
)
Σ ha diag (II
(2)
he Mdiag (s*)
(96)
A=
K- diag (St)
II
Hy:
(97)
where equality (1) holds because (IIIII+)* II and equality (2) comes from the fact that diag (ISIIT") Iddaa (S). The output is permutation equivariant and conclude that the proposed architectures produce permutation equivariant outputs for isomorphic graphs.
J GNNs VS SPECTRAL DECOMPOSITION
In this paper, we discuss the ability of GNNs to distinguish between different graphs. Our analysis uses spectral decomposition tools and provides conditions under which GNN can tell two graphs apart. These conditions are related to the eigenvalues and eigenvectors the graph operators. Therefore, it is natural to study the similarities and differences of GNNs and spectral decomposition algorithms.
J.1 THE TWO GRAPIIS HAVE DIFFERENT EIGENVALUES
As explained in the main part of the paper, there always exists a GNN that can distinguish between pair of graphs with different eigenvalues. Furthermore, computing the eigenvalues of the two graphs can also attest that the two graphs are nonisomorphic. Therefore, the two approaches are equally powerful. The difference lies in the fact that GNN needs to be trained to perform the isomorphism test, whereas the spectral decomposition is unsupervised. On the other hand, computing the spectral decomposition for real graphs can be computationally very challenging.
J.2 THE TWO GRAPHS HAVE THE SAME SET OF EIGENVALUES THAT ARE DISTINCT
This case is a bit more complicated. Since the eigenvalues are the same, one must resort to the eigenvectors distinguish between the graphs. When the eigenvalues distinet, the eigenvectors
26

---

of the graph unique up to sign for each eigenvector. To be more precise, let 9, 9 be isomorphic graphs with eigenvectors U, U respectively. Then have the following:
U = HUD,
(98)
where II is a permutation matrix and D is diagonal matrix with elements +1. We observe the following:
Remark J.1 When Assumption H. holds, the eigenvectors of isomorphic graphs are not permutation equivariant, since there exists a sign ambiguity for each eigenvector. On the contrary, the produced GNN node embeddings are always permutation equivariant, according to Propositions (.2 I. In other words, GNNs always produce equivariant node embeddings for isomorphic graphs, which is not the case for the spectral decomposition.
If 9, 9 are nonisomorphic the story is different. According Lemma H.2 there does not exist permutation matrix II such that U IT D and the GNNs detect nonisomorphic graphs under Theorem H.3 or Theorem H.4 Let us focus on the conditions of Theorem H.4 i.e.
(a) There does not exist permutation matrix II such that U| = Nū.
(b)
UT U4n * O for all eigenvectors U, or [ 0n * 0 for all eigenvectors iu..
We see that these conditions involve the eigenvectors of the graphs and therefore we can construct an eigen-based algorithm with the same guarantees. Note that these guarantees are only sufficient and there might be cases where the GNNs can distinguish between nonisomorphic graphs, whereas an algorithm based on the above conditions might fail. Furthermore, calculating the complete set of eigenvectors of a real graph might be computationally prohibitive.
J.3 THE TWO GRAPHS HAVE THE SAME MULTISET OF EIGENVALUES THAT ARE NOT DISTINCT
Scenario 1:
The graphs are isomorphic. GNNs will always produce equivariant embeddings for isomorphic graphs. On the contrary, eigenvectors are not unique and they will not provide equivariant representations (up to scaling) for isomorphic graphs.
The graphs are nonisomorphic. The GNN analysis for this case is relegated for future work. Regarding the spectral decomposition, we need resort to eigenvectors, which are not unique. Therefore, detecting nonisomorphic graphs is challenging.
Scenario 2:
J.4 STABILITY AND DISCRIMINABILITY OF GNNS
From discussion so far, have observed similarities and differences between the functionality of GNNs and the spectral decomposition the graph. There is one more fundamental difference that has not yet been discussed and involves the stability and discriminabilityy properties of GNNs (Gama et al. 2020). In particular, a GNN is stable under small perturbations of the graph operator, Le., the output of GNN is similar for 'similar' graphs. On the other hand, small perturbations of the graph can result in essential changes in the eigenvalues and eigenvectors of the graph operator, which makes the spectral decomposition more unstable. Therefore, there seems to be stability vs. discriminability trade-off between GNNs and spectral decomposition. However, the architectural nonlinearities allow GNNs to be both stable and discriminative.
To recap, the conditions of this paper involve the eigenvalues and cigenvectors of the graph operator. Compared eigen-
algorithms, there an advantage GNNs when the eigenvalues are exactly the same with the same multiplicities. This is due to the fact that the eigenvectors of graph operator are not unique and therefore isomorphic graphs do not admit permutation equivariant eigenvectors, whereas GNNs always produce permutation equivariant node embeddings for isomorphic graphs. On the other hand, when the eigenvalues are different, GNNs and spectral decomposition are equally powerful. Furthermore, GNNs robust to small changes of the graph. which is not the case for spectral decomposition. Finally, the spectral decomposition is computationally heavy and unsupervised, but GNNs are lighter to execute and require training.
27

---

(a) g
(b) 9
Figure 8: CSL graphs
K EXPERIMENTAL DETAILS
In this appendix we provide further details on the experiments presented in the main paper.
K. EXPERIMENTS ASSOCIATED WITH THE GRAPHS FIGS. A 2
In Tables 8 we present the cigenvalues and the sum of the corresponding cigenvectors of the graphs in Figs. respectively.
Table Eigenvalue and eigenvector information for the graphs in Fig.
GRAPH
π
3
6
An
3
-2
-2
0
u
-2.45
0
0
Am
-3
ú 1
-2.45
0
0
Table Eigenvalue and eigenvector information for the graphs in Fig.
GrAPH
An
2.303
1.618
1.303
0,618
-2.303
-1.618
-0.618
-1
-1.303
3.048
0
-0.8
816
0
0
0
0
-0.210
G
Rm
2,303
1.861
0.618
0.618
0.254
-1.303
-1.618
-1.618
-2.115
3.048
0
-0.816
0
0
-0.210
0
0
We observe that G and & in both figures admit a different of eigenvalues. However, the eigenvectors that correspond to the eigenvalues that differentiate them are orthogonal to the vector of all all-ones (they sum up to zero). Therefore, the WI. algorithm and GNNs with input fail tell them apart.
K.2 DETAILS ON THE EXPERIMENTS OF SECTION 7
In Fig. we present a paradigm of two graphs the CSL. dataset that belong to different classes. is clear from the figure that the two graphs consist of nodes that all have degrees equal to 4. Therefore, æ = an eigenvector of both graphs and orthogonal to the remaining cigenvectors. Any valuable the WL algorithm feed GNN with
information that separates the graphs is lost when x 1.
Next, present the details the experiments of section 7.2 specifications suggested in (Xu et al., 2219)) In particular, we train a 4-layer graph neural network where the output of each layer and the input are passed through graph pooling layer and then
For the most part, use the
28

---

Baear
Figure 9: GNN architecture
linear classifier. A schematic representation of the considered architecture is presented Fig. 9 The nonlinearity used in experiments is the ReLU and the readout function that performs graph pooling is 1 (9) for I 0, . 5. X represents the output of layer with X X. For each type-2 GNN block, we only use 1 tap for 1. This is due to the fact that we pass the output of every layer the final classifier, additional taps might be redundant.
To train the proposed architecture, we use Adam optimizer with a learning rate equal to 10-2, batch size equal 128 and dropout ratio equal 0.5. Training carried out over 200 epochs with 50 iterations per epoch. To assess the performance of the proposed architecture, we divide each dataset into 50 50 training-testing splits and apply 10-fold cross-validation. The only parameter tune is the hidden dimension for each layer. In particular, the number of modules for each layer is the same and we tune over {8. 16, 32, 64, 128, 256} modules.
We also compare our proposed architecture with GIN (Xu et al. 2019 initialized with = 1 and GIN initialized according equation (14). We use the publicly available codo provided by the authors. We use the exact same specification for fair comparisons and tune the hidden layer over (8, 16, 32, 64, 128, 256} dimensions.
All experiments are conducted on a Linux server with NVIDIA RTX 3080 GPU. The data are publicly available, and the code proposed architectures with all the experiments can found in this repository
hhttp://githhu.co com/weihua9 f//o:/// f/powerful-gnns
29


Reviews:
[{"review_id": "rjmsTqJhksR", "reviewer": "Reviewer_GLDQ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper provides a spectral analysis perspective on the expressivity of GNNs. The analysis is done under the assumption that graphs differ in at least one eigen value. The paper claims GNNs can achieve separation power greater than 1-WL by augmenting the node feature with appropriate choices and demonstrate the disadvantages of using an all-1 input vector. The authors suggest augmenting the input to the GNN with the diagonal of powers of the adjacency matrix to improve expressive power.", "summary_of_the_review": "I think this work provides an interesting view on the analysis of GNN expressivity. However, the final proposed model lacks novelty and the experimental evaluation is not convincing enough. \n\nI therefore think this paper is below the bar for ICLR but will consider raising my score upon addressing my concerns. \n\n", "strength_and_weaknesses": "### 1. Strengths\n\n- The paper provides expressivity analysis from a spectral perspective. \n- The authors show that using random input features and a covariance operator yields a GNN model that is more expressive than 1-WL and show equivalence to a model that sidesteps the need to use random features. This result bridges betweenthe role of random features and substructure input features in increasing expressivity of GNNs.\n\n### 2. Weaknesses\n\n1. **Novelty**\n\n   The paper suggests to augment the node features with the diagonal of adjacency powers, which are, the k-cycle couts (with repeatitions) for each node in the graph. This idea has appeared before e.g., in [1] that generally proposed to add information on subgraph isomorphism counts including cycles. Altough the proposed model was derived from a different thoretical perspective, I believe the novelty of the proposed model is quite limited.  The authos do not cite [1]. Can the authors provide a discussion upon relations of their work to [1]?\n\n2. **Model complexity**\n\n   Theorem 2.2 implies that in order to distinguish between two graphs the filter length should be at least $q$, the size of the set of all unique eigen values in the union of both graphs’ eigen values. This number grows with the number of nodes in the graph and could impose high complexity for large graphs. \n\n3. **Too strong claims**\n\n   The authors repeatedly state that the analysis of the expressive power of GNNs is limited to the case of an all 1 input vector. However, lots of works extended this result and the authors overview them in the related woprk section. I would suggest that the authors soften their claims dismissing other works that have already been done. \n\n4. **Experimental Evaluation**\n\n   Experimental evaluation is not convincing enough. The proposed method shows comperable performence to GIN where the improvement is insignificant. The results on the CSL dataset are not surprising, again since properties of the cycle counts features has already been analysed in [1]. Furthermore, [1] outperforms the current model across all social and biological datasets.\n\n   \n\n[1] Bouritsas, G.; Frasca, F.; Zafeiriou, S.; Bronstein, M. M. Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting. arXiv July 5, 2021.\n\n### ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "iYozPoXHri9", "reviewer": "Reviewer_4qSA", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper uses the spectral decomposition perspective to study the expressive power of GNNs. It argues that the 1-WL is not the real limit of GNN expressiveness. Instead, it only serves as the limit when we use all-one vectors as input features. Further, this paper proposes a new model, which uses features derived from powers of matrix representations and can be more expressive than regular GNNs.", "summary_of_the_review": "Overall, I think this work has merits in terms of the motivation and the analysis. However, the technical assumption and contribution have not met the standard of ICLR.", "strength_and_weaknesses": "Strengths:\n\n1. The motivation of analyzing GNNs from the spectral decomposition view is good.\n\n2. The analysis of using random input features can help improve expressiveness is great.\n\nWeakness:\n\n1. The fundamental assumption that 1-WL only serves as the limit when using all-one vectors as input features is not clearly correct to me. Specifically, to prove that 1-WL is the limit of GNNs in the GIN paper, the only assumption is that the input feature space is countable. In other words, the input features do not have to be all-one vectors to achieve the proof. Hence, it is unclear to me why this fundament assumption hold in this paper.\n\n2. The proposed new model uses features obtained from powers of matrix representations. However, the similar idea has been investigated in exiting work, such as SIGN [1]. Hence, the proposed model is not novel from this view.\n\n[1] Rossi, Emanuele, et al. \"Sign: Scalable inception graph neural networks.\" arXiv preprint arXiv:2004.11198 7 (2020): 15.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "BgIEtJq5zP", "reviewer": "Reviewer_jQZJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "GNNs are known to have a discriminative power of at most 1-WL algorithm in the graph isomorphism problem. This paper pointed out that this result assumed that inputs are the all-one vectors and analyzed the expressive power of GNNs in the graph isomorphism problem when inputs are not necessarily all-one.\nFirst, this paper gave sufficient conditions on the spectrum of the adjacency matrices and the input vectors for a GNN to discriminate between two non-isomorphic graphs (Theorem 2.2). In particular, it was shown that this condition held when inputs were an appropriate number of Gaussian random noise (Proposition 4.1). Also, the condition is achieved when inputs are numbers of cycles of appropriate length in the graphs (Theorem 5.1. Theorem 6.1). ", "summary_of_the_review": "The sufficient conditions derived in this paper for a GNN to discriminate a pair of non-isomorphic graphs are flexible. On the other hand, enriching the input of GNNs may not be a novel approach in the theoretical analysis of the expressive power of GNNs. In addition, the statements and architectural descriptions are somewhat informal, and there is room for improvement.", "strength_and_weaknesses": "Strengths\n- Sufficient conditions (Assumption 2.1) are general and have broad applicability.\n\nWeaknesses\n- Mathematical arguments are somewhat informal, and the description has room for improvement.\n- Experiments on real data have not shown that the proposed methods (in terms of both architectures and input features) are practically effective on prediction tasks on graphs.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject