A New Perspective on "How Graph Neural Networks Go Beyond Weisfeiler-Lehman?"
Authors: Asiri Wijesinghe
Qing Wang
Venue: ICLR 2022 Oral (2022)
Keywords: Graph Neural Networks
Graph Isomorphism
Weisfeiler Lehman

Abstract: We propose a new perspective on designing powerful Graph Neural Networks (GNNs). In a nutshell, this enables a general solution to inject structural properties of graphs into a message-passing aggregation scheme of GNNs. As a theoretical basis, we develop a new hierarchy of local isomorphism on neighborhood subgraphs. Then, we theoretically characterize how message-passing GNNs can be designed to be more expressive than the Weisfeiler Lehman test. To elaborate this characterization, we propose a novel neural model, called GraphSNN, and prove that this model is strictly more expressive than the Weisfeiler Lehman test in distinguishing graph structures. We empirically verify the strength of our model on different graph learning tasks. It is shown that our model consistently improves the state-of-the-art methods on the benchmark tasks without sacrificing computational simplicity and efficiency.

Published as a conference paper at ICLR 2022
A NEW PERSPECTIVE ON "How GRAPH NEURAL NET- WORKS Go BEYOND WEISFEILER-LEHMAY?
Asiri Wijesinghe & Qing Wang School of Computing, Australian National University, Canberra, Australia (asirt ri. wi ggsin qing. ging.wang @anu. edu.
ABSTRACT
We propose new perspective on designing powerful Graph Neural Networks (GNNs). In a nutshell, this enables general solution to inject structural properties of graphs into a message-passiieee aggregation scheme of GNNs. As theoretical basis, we develop new hierarchy of local isomorphism on neighborhood sub- graphs. Then, we theoretically characterize how message--pssinng GNNs can be designed to be more expressive than the Weisfeiler Lehman test. To elaborate this characterization, we propose a novel neural model, called GraphSNN, and prove that this model is strictly more expressive than the Weisfeiler Lehman test in distinguishing graph structures. We empirically verify the strength of our model on different graph learning tasks. It is shown that our model consistently improves the state-of-the-art methods on the benchmark tasks without sacrificing computational simplicity and efficiency.
INTRODUCTION
Many Graph Neural Networks (GNNs) employ message- paasssggg aggregation scheme learn low-dimensional vector space representations for nodes in a graph (Kipf & Welling 2017 Veličkovid
al. 2017 Hamilton al., 2017 Gilmer al. 2017 Sato 2020 Loukas 2020 de Haan al.
2020
Let == (V, be graph. For each node v E V, a message paaagggg-asiingggg.. aggregation scheme recursively aggregates the feature vectors of nodes in the neighborhood of v and combines the aggregated information with the feature vector of itself to obtain representation. Since there is no natural ordering on nodes, such message-
aggregation schemes are usually required to be commutation-invaiian (Maron et al. 2018 Keriven & Peyré 2019 Garg et al. 2020).
Despite advances of GNNs in various graph learning tasks such as node classification (Kipf & Welling 2017: Xu et al. 2018), graph classification (Xu et al., 2019; Wu et al. 2019) and link prediction (Zhng & Chen (017). there is still a lack of theoretical understanding of how to design powerful and practically useful GNNs that can capture rich structural information of graphs. Recent studies (Xu et al. 2019; Morris et al. 2019) have explored the connections between GÑNs and the Weisfeiler-Leehaal (WI.) test (Weisteiler & Leman 1968). By representing neighhorhood multiset of feature vectors and treating the neighborhood aggregation as an aggregation function over multisets, Xu et al. (2019) showed that cressage-passingg GNNs are at most as powerful as the WL test in distinguishing graph structures. However, many simple graph structures still cannot be distinguished by the WL test, e.g., G2 and G2 shown in Figure D A question is: how design expressive yer simple GNNs that can go beyond the WL test with theoretically provable guarantee?
Recently, there have been three main directions of extending GNNs beyond WL: (1) building GNNs for higher-order WL (i.e. k-WL with A 2 3) or variants Maron et al. | Morris et al. 2020
2019); (2) counting on pre-defined substructures as additional features (Bouritsas et al. 20200) (3)
augmenting node identifiers or random features into GNNs (You et al.) 2021; Vignac et al. 2020
Sato et al. 202I). Unlike these works, we aim to introduce a general solution upon which GNNs can be enhanced to capture structural properties of graphs. This solution enables GNNs to provably be more expressive than the Weisfeiler-
test, but still computationally efficient. It overcomes the following limitations of existing works. Compared with higher-order WL methods in (1) which require high computational overhead and are impractical, our method goes beyond the WL test but is still computationally efficient. Compared with the methods counting substructures in (2), our

---

Published as a conference paper at ICLR 2022
Graphs
Neighborhood Subgraphs
Overlap Subgraphs
Embedding Space
G
GMP Framework
V2
V3
AGGREGATE
1.67
AGOREGATE
hu
COMBINE(
Figure 1: An overview of our proposed framework for GNNs that can go beyond the WL test in distinguishing non-isomorphic graphs G1 and G2. The overlap subgraphs of G1 and G2 structurally different, which are captured by structural coefficients defined in Eq.
method does not require to handcraft substructures. Compared with the methods of augmenting node identifiers or random features in (3), our method can flexibly quantify local structures (see examples in Figure 3 and also capture different classes of local structures w.r.t. different graph learning tasks.
Our work is grounded in three observations: (i) Treating a neighborhood vectors ignores the rich structure information among vertices in the neighborhood. thereby limiting neighborhood
multiset of feature
the representational capacity of the model. Thus, represent neighborhood subgraph in which vertices are structurally related, and show that the WL test is only as powerful distinguishing neighborhood subgraphs in terms of their subtree structures in the neighborhood. (ii) There exists a natural class of isomorphic graphs, which strictly lies in between neighborhood subgraph isomorphism and neighborhood subtree isomorphism. We call it overlap (subgraph) isomorphism. The notion of overlap subgraph enables us to characterize structural interactions of vertices and inject them into message-passingg aggregation scheme for GNNs. (iii) By designing proper function for quantifying structural interactions of vertices and preserving the injectiveness of a message-passee aggregation scheme, more expressive GNNs can be developed. We propose a new GNN model that is strictly more expressive than the WL test to demonstrate an instance of this kind.
Contributions. summary, the main contributions of this work are as follows:
We introduce hierarchy of local isomorphism to characterise different classes of local structures in neighborhood subgraphs, and discuss its connections with the WI. test and GNNs (Section and Theorems 1
We develop simple yet powerful framework to inject structural properties into message- passing aggregation scheme, and theoretically characterize how GNNs can be designed to be more expressive beyond the WL test (Section 3 and Theorem 3
We propose novel neural model for graph learning, called GraphSNN, and prove that GraphSNN is strictly more expressive than the the WL test in distinguishing graph structures (Section 4 and Theorem
We show that, due to the way of injecting structural properties into a structured-messagge passing aggregation scheme, GraphSNN can overcome the oversmoothing issue (Chen et al.
2020a: Zhao & Akoglu 2019 Li et al. 2018) (Section 5.4..
We have conducted experiments on benchmark tasks (Hu et al. 2020). The experimental results show that our model is highly efficient and can significantly improve the state-of-the- of-the-art methods without sacrificing computational simplicity.
Related work. Weisfeiler-Lehmanl (WL) hierarchy is a well-established framework for graph isomorphism tests (Grohe (017). Introduced by Weisfeiler and Lehman (Weisfeiler & Leman 1968). the Weisfeiler-Lehman algorithm (also called 1-WL color refinement) is computationally efficient heuristic for testing graph isomorphism (Babai & Kucera
1979). is known that k- WL is strictly 1992
more powerful than (k-1)-WI. when k>3
CCai et al.
Grohe 2017
2

---

Published as a conference paper at ICLR 2022
pessagg GNNs typically considered as a differentiable neural generalization of the Weisfeiler-Lehman algorithmss on graphs. It has been reported (Xu et al.] 2019)) that some popular GNNs such as GCN (Kipf & Welling 2017) and GraphSAGE (Hamilton et al. 2017) are at most powerful as 1-WI. in distinguishing graph structures. Xu et al. (2019) has shown that Graph Isomorphism Network (GIN) can be as powerful as 1 1-WT. At its core, GIN provides an injective aggregation scheme that is defined as a function over multisets of feature vectors, and thus GIN has the representational power to map any two different multisets of feature vectors to different representations in an embedding space.
considerable amount of efforts has been devoted to improve the expressive power of GNNs beyond 1-WL. Generally, there are three directions: (1) Several works proposed bigher-order variants of GNNs that are as powerful as k-WL. with 2 3 (Azizian & Lelarge| 2020). For example, |Morris set-based variant of k-WL, Maron et al. (2019) proposed reduced 2-order graph network that as expressive as 3-WL. and
et al. (2019) introduced k-order graph networks that are expressive
Morris et al. (0200) proposed local version of k-WL which considers only subset of vertices in neighborhood. However, these more expressive GNNs are impractical to use due to their inherent high computational costs and sophisticated design. (2) Some works attempted to incorporate inductive biases based on isomorphism counting on pre-defined topological features such as triangles, cliques, and rings (Bouritsas al., [020 [Lu al. 2020: Monti et 2018), similar the traditional ideas of graph kernels (Yanardag& & Vishwanathan 2015). However, pre-defining topological features requires domain- -specific expertise, which is often not readily available. (3) Most recently, several works explored the ideas of augmenting GNNs using node identifiers or random features. For example, Vignac et al. (020)) proposed a method that maintains a "local context" for each node based on manipulating node identifiers in permutation equivariant way. You et al. (202T) developed ID-GNN, by taking into account the identity information of vertices. [Chen et al. (2020b) and Murphy et al. (2019) assigned one-hot IDs to vertices based on the ideas of relational pooling. Sato et al. (2021) added a random feature to each node to improve the representational capability of GNNs.
Our work is fundamentally different from existing models by injecting properties of structural interactions among vertices based on a natural class of isomorphic graphs in the local neighborhood (i.e., overlap subgraph isomorphism) into message-passing aggregation scheme of GNNs.
2 A NEW HIERARCHY OF LOCAL ISOMORPHISM
In this section, we characterize a hierarchy of graph isomorphism based on local neighborhood subgraphs and explore its connections to 1-WL.
Let G = (V, E) be simple, undirected graph with set V of vertices and set E of edges. The set of neighbors of vertex is denoted by (vrr) = [u E Vi,,, u) E E). The neighborhood subgruph of a vertex v, denoted by S., is the subgraph induced in G by N(v) = -u) [b)) which contains all edges in E that have both endpoints in (w). For two adjacent vertices v and u, i.e., (v, u) E E, the overlap subgraph S.m. between u and u is defined as S.m. S. S..
Let S; and Sj be the neighborhood subgraphs of two vertices i and j that are not necessarily adjacent, and he be the feature vector of a vertex v V. In the following, we define three notions of isomorphism, which correspond to different classes of local structures in neighborhood subgraphs.
Definition 1. St and Sj are subgraph-isomorphic,, denoted as S, Ssubgraph Sj. if there exists a bijective mapping (t) - N() such that g(i) j and for any two vertices 01, U2 E (i), on and U2 are adjacent in St iff g(v)) and g(v2) are adjacent in Sj, and b (lg(v1) and hog hy(vz)-
denoted as Sy Soverlap Sj. if there exists bijective mapping g (i) + Nj) such that g(i) = j and for any v' E e() and g(v') v', Sw and Syu are subgraph-isomorphic
Definition 2. S₁ and S, are overlap
Definition 3. St and Sj are subtree- iobtrre-ioomopphic, denoted as S, Seubtree Sy. if there exists a bijective mapping 9 : :N( + (ij such that g(i) and for any v E (i) and g(v') = u', h = hw-
Theorem I states that there is a hierarchy among these notions of local isomorphism on neighborhood subgraphs, where aabgraph-isomorphie is the strongest one, subrree-isomorphism is the weakest,
3

---

Published as a conference paper at ICLR 2022
(a)
(b)
Si
S
Sv1
Svz
Sva
Su4
Overtap
subgraph
Subtree
Vs
Figure 2: (a) St and Sj are overlap-isomorphic (i.e., having the same overlap subgraph) but not subgraph-isomorphic; (b) Four neighborhood subgraphs {Su, 2, 3, 4} are subtree-isomorphic (i.e., having the same subtree) but not everlap-isomoryg
and overlap-isomorrhiism lies between. FigureZJshows two groups of graphs: one distinguishable w.r.t. subgraph-isomorphh isomorphism but not overlap-isomorphise while the other is distinguishable by overlap-isomorphin but not subtree-isonee cobbreeisommorphim..
Theorem 1. The following statements are true: (a) If S₁ Ssubgraph Sj. then S Soverlap Sj; but not vice versa; (b) If S; Soverlap Sj. then S Ssubtree Sy; but not vice versa.
Let S (S V} and Ç S + Hd mapping each neighborhood subgraph in S into node embedding in Rd. The following theorem states that GNNs that are powerful as 1-WL can distinguish two neighborhood subgraphs only w.r.t. subtree- -oobrreisomoopphism each layer.
Theorem 2. Let M be GNN. M is as powerful as 1-WL in distinguishing non-isomorpho graphs M has sufficient number of layers and each layer can map any S, and S into two different embeddings (i.e., {(S.) + ((S)) if and only if S; Suubtree Sj.
The complete proofs of these theorems are provided Appendix
A GENERALISED MESSAGE--ASSSIE FRAMEWORK
In this section, we present generalised message-pas passiegganin framework (GMP) which enables to inject local structure into an aggregation scheme, light overlap subgraphs. We theoretically characterize how GNNs can be designed to be more expressive than 1-WL in this framework.
Let S* = [S (v, u) E F} the set of overlap subgraphs G. We define structural coefficients for each vertex and its neighbors, i.e., w x - IR such that A = Ser.) A question arising is: what are the desirable properties such a function w? Ideally, it should quantify how vertex structurally interacts with its neighbor u in the local neighborhood. Thus, given S.n. (Vous Evu) and Sew' = (Ven', Evw(). carefully designed w should exhibit the following properties:
(1) Local closeness: w(S., Swu) > w(Sv, Sewr) if Sou and Spa' are complete graphs with Son K,, Sew = Kj. and > j. where K; refers to a complete graph on vertices.
(2) Local denseness: w(S,, Spu) w(S,, Spn) if Sou and San have the same number of vertices but differ the number edges s.t. (Voul = |Vew and Erall > E
(3) Isomorphic invariant: w(,,, Sew) (Sp, Syw') if Sou and Syw' are isomorphic.
Figure illustrates the first properties. Let ( denote multiset, Ā (Aou),,eEv where Anm normalised value of Av and X RVVV be matrix of input feature vectors where x.. R associates each v E V. We denote the feature vector of u at the t-th layer by (!) and (. Fe- Then, the (++1)-th layer of aggregation scheme can be defined as:
m(()) AGGREGATE ( (AAus) 1 1(9) ((())N)())))))))))))))))))))))))
m AGGREGATE' (H-Avulus (N)))
h (t+1) COMBINE ( m!!))
AGGREGATE (.) and AGGREGATE (.) are two possibly different parameterized functions. Here, (t)
me is message aggregated from the neighbors of and their structural coefficients, and ml
4

---

Published as a conference paper at ICLR 2022
(a)
(b)
u
V
Figure (a) Local closeness: for overlap subgraphs that are complete graphs, their structural coefficients increase with the number of vertices; (b) Local denseness: for overlap subgraphs that have the same number of vertices, their structural coefficients increase with the number of edges.
"adjusted" message from after performing element-wis multiplication between AGGREGATE' (+) and ( to account for structural effects from its neighbors. Then, m and ma are combined by COMBINE()) to obtain the feature vector he (f+11
The following theorem states that GNN can be more expressive than 1-WL w is powerful enough to distinguish structure beyond neighborhood subtrees and the neighborhood aggregation function O injective under a sufficient number of layers. The proof provided in Appendix C.
Theorem 3. Let M be GNN whose aggregation scheme & is defined by Eq. Eg. M strictly more expressive than I-WL in distinguishing non-isomorphic graphs if M has sufficient number of layers and also satisfies the following conditions:
(1) M can distinguish at least neighborhood subgraphs S₁ and Sj with St Ssubtree Sj. S e Subgraaph Sj and & AA (N(i) + [Ajulu' E (())):
(2) 1 (1 1h ( (Avu, h E N())B) is injective.
GRAPHSNN
Generally, there are many different ways of designing w and & functions, leading to GNNs with different expressive powers. To elaborate this, we propose a novel GNN model, named GraphSNN, whose aggregation scheme an instantiation of our generalised message-passinn framework. We prove that the expressive power of GraphSNN goes beyond 1-WL.
Model design. In the following, we provide a definition of that satisfies the properties of local closeness, local denseness, and isomorphic invariant. One key idea behind this definition is to make it capable being generalized to support different graph learning tasks, controlled by À > (will be further diseussed in Section 5.3)
Eval
(Se, Sow) Veul |Vr
Voul
A
(4)
This definition allows us formulate weighted adjacency matrix A (Aru).,ev for Graph-
SNN. To compare structural coefficients across different nodes, we normalize A to À by A = EocNtoy Avu Alternatively, can be normalized using Softmax or other normalization techniques. For each vertex v V, the feature vector the (t+ (t+1)-th layer is generated by
h (1+1) MI.Po (
Σ
Ana + +1) 1
(Aore (1)=+)))0)) NEN(e)
Σ
(5)
(EN())
where (()) is a learnable scalar parameter. Since (vv) refers one-hop neighbors of v, stack multiple layers to handle more than one-hop neighborhood. Note that, to ensure the injectivity in the feature aggregation in the presence of structural coefficients, add into the first and second terms in Eq. [5] This design is critical for guaranteeing the expressiveness of GraphSNN beyond 1-WL, will be discussed in the proofs of the lemmas and Theorem later.
Expressiveness analysis. We first generalise the result of universal functions over multisets (Xu et al. 2019) to universal functions over pairs of multisets since Eq. 5 involves not only node features but
5

---

Published as a conference paper at ICLR 2022
Method
Cora
Citeseer
Pubmed
NELL
ogbn-arxiv
GCN
81,5 1 0.4
70.3 1 0.5
79.0 0.5
66.0 1.7
71.74 0.29
GraphSNNcoN
83.1 + 1.8
72.3 = 1.5
79.8 + 1.2
68.3 + 1.6
72.20 = 0.90
GAT
83.0 0.6
72.6 0.6
78.5 + 0.3
GraphSNNcAT
83.8 + 1.2
73.5 + 1.6
79.6 + 1.4
GIN
17.6::11
66.1 = 1.5
77.0 + 1.2
61.5 + 2.3
GraphSNNGIN
79.2
68.3 = 1.5
78.8 1.3
63.8 2.7
GraphSAGE
79.2
71.6 1.9
77.4 + 2.2
63.7 5.2
71.49 = 0.27
GraphSNNGraphsAACe
80.5 + 2.5
72.7
3.2
79.0
3.5
66.3 5.6
71.80 0.70
Table 1: Classification accuracy (%) averaged over 10 runs on node classification.
also structural coefficients. Assume that H. A and W are countable sets where H. is node feature space, A is a structural coefficient space, and W (Aighal Asj E A... h, Hz. Let H and W be two multisets containing elements from H and W, respectively, and |H| = W/. We can prove Lemma] Lemma and Theorem below, where the proof details are provided in Appendix C.
Lemma 1. There exists function J s.l. π (H, Enen, [h, w) is unique for any distinct pair of multisets (H, W).
Then, the injectiveness of () can be extended to 7 (a, H, W) as in the lemma below.
Lemma 2. There exists a function I s.t. T/ (he; H, W) = (ho.. (H(b) + Ene Hn wew [(h, w) is unique for any distinct (he, H, W), where h, E H. H has E W, and can be an irrational number.
Since any function over (h.,, H, W) can be decomposed as (he (b.) Ehe S(h w)). similar to Xu et al. (2019), we use a parameterized multi-layer perceptron (MIP) to learn f and The following theorem characterises the expressive power of GraphSNN.
Theorem 4. GraphSNN is more expressive than I-WL. in testing non-isomorphic graphs
Since GIN is powerful 1-WL (uu al. 2019), this theorem implies that GraphSNN is more expressive than GIN, i... GraphSNN can map at least two different neighborhood subgraphs that correspond to the same multiset of feature vectors to different representations.
Complexity analysis. Similar to GCN and GIN, GraphSNN is computationally efficient. The time complexity and memory complexity are linear w.r.t. the number of edges in graph. Further, due to the locality of GraphSNN, the computation of aggregating feature vectors from neighborhood subgraphs at each layer be parallelized across all vertices. Structural coefficients computed with the time complexity ((m)), where m is the number of edges and the maximum degree of vertices in graph, and this computation can also be parallelized across all edges. Table in Appendix A summarizes the time and space complexities of several popular message-passing GNNs in comparison with GraphSNN.
be pre-
NUMERICAL EXPERIMENTS
In this section, we evaluate our models on node classification and graph classification benchmark tasks. All the results of our models are statistically significant at 0.05 level significance.
5.1 NODE CLASSIFICATION
Datasets. We use five datasets: three citation network datasets Cora, Citeseer, and Pubmed (Sen et al. 2008) for semi-supervisee document classification, one knowledge graph dataset NELL (Carlson
ct al. 2010) for semi-supervised entity classification, and one OGB dataset ogbn-arxiv from (Hu al. 2020 Table 10 in Appendix B contains statistics for these datasets.
Baseline methods. We consider the popular message-passe passing GNNs: GCN (Kipf & Welling 2017)
GAT (Veličković al.) 2017). GIN (Xu et al.) (201)), and GraphSAGE (Hamilton et al. (017). For each these baselines, we construct GraphSNN by model by replacing its aggregation scheme by aggregation scheme, which is detailed in Appendix A. The purpose of this setup is evaluate

---

Published as a conference paper at ICLR 2022
Method
MUTAG
PTC-MR
PROTEINS
D&D
BZR
COX2
IMDB-B
RDT-M5K
WL
5.74
39.94.3
75.0=31
0.4
78.5 = 0.6
0.7
1388399
52.5 =21
RetGK
90.3
62.5 1.6
=
816
7199
GNTK
9..0
679
75.6
75.6
83.6
76,9
P-WL
9.3
6..0
0.3
7..6
WL-PM
87.7 0.8
61.4
7
WWL
87.2+
66.3
742
0.56
84,4 2.0
78.2
7.
FGW
8.6
65.3
745=227
85.1 #411
77.2
63.8 3,4
EGCNN
58.6
75.5 0.9
79.3 0.9
70.0 0.9
48.7 4.5
CapsGNN
6.8
66.0
76.2
1..1
52.9
GraphSAGE
8.6
63.9 7.7
75.9
72.9 2.0
2.3
50.0 1.3
GIN
89.4 5.6
64.6 7.0
75.9 13.9224 2.8
75.1
15.1
57.5
1.5
GraphSNN (S)
91.57 + 2.8
06.70=311
76.83
2.5
81,97 2.6
88.69 + 3.2
82.86 3.1
77.86
3.6
58,43 +
GGaphSNN (R)
91.24 = 2.5
66,96=34
76.51 + 2.5
82.46 + 2.7
88,97
+ 299
83.13
+ 3.5
76.93
3.3
58.51 = 2.7
GraphSNN (S)
94.70
1.9
70.58 3.1
78.42 + 2.7
83.92
+ 2.3
91.12
+ 3.0
86,28
+ 3.3
78.51
2.8
59.86
+ 2.6
GriphSNN
1.2
71.01
78.21
2.9
84.61
1.5
91.88
3.2
86.72
2.9
77.87
3.1
60.23 2.2
Table 2: Classification accuracy (%) averaged over 10 runs graph classification. The results of WL and RetGK are taken from (Du et al. 2019), GraphSAGB from (Xu et al. 2019), DGCNN from (Maron et al. 2019) and others from their original papers. f indicates the reporting setting used in GIN and further details on the experimental settings are discussed in Appendix B.
how effectively our aggregation scheme with structural coefficients can learn representations for vertices, compared with the standard message-passing aggregation scheme.
Experimental setup. We use the Adam optimizer (Kingma & Ba, 2015) and X = 1. For ogbn- arxiv, our models are trained for 500 epochs with the learning rate 0.01, dropout 0.5, hidden units 256, and = 0.1. For the other datasets, we use 200 epochs with the learning rate 0,001, and choose the best values for weight decay from {0.001, 0.002, ..., 0.009) and hidden units from (64, 128, 256, 512]. For and dropout at each layer, the best value for each model in each dataset is selected from {0.1, 0.2, ..., 0.6]. GraphSNNGAAT uses the attention dropout 0.6 and 8 multi-attention heads. GraphSNN Graphs AGE AGE uses the neighborhood sample size 25 with the mean aggregation.
We consider two settings of data splits for all datasets except for ogbn-arxiv: (I) the standard splits in Kipf & Welling (2017). i.e., 20 nodes from each class for training. 500 nodes for validation and 1000 nodes for testing, for which the results are presented in Table I (2) the random splits in Pei et al. 2020)) i.e., randomly splitting nodes into 60%, 20% and 20% for training, validation and testing, respectively, for which the results are presented in Table T3 in Appendix B. For ogbn-arxiv, we follow Hu et al. (2020) to use time-based data split based publication dates.
5.2 GRAPH CLASSIFICATION
We evaluate GraphSNN from three aspects: (1) small standard graph datasets, (2) large graph datasets and (3) comparison with GNNs that are go beyond 1-WL.
Experiments small graphs. We eight datasets from two categories: (1) bioinformatics
datasets: MUTAG, PTC-MR, COX2, BZR, PROTEINS, and D&D (Debnath et al. 1991 Kriege et al.
2016 Wale al. 2008 Shervashidze al. 2011 (Sttherland al. [000]] BBrgwardt & Kriegel
2005 (2) social network datasets: IMDB-B B and RDT-M5K (Yanardag & Vishwanathan 2015).
Table I1 in Appendix B contains statisties for these small graph datasets.
We compare against eleven baselines: (1) Graph kernel based methods: WL subtree kernel (Sher- vashidze et al., (00T), RetGK (Zhang et al. (018b). GNTK (Du et al. 2019), P-WL (Rieck al.
2019). WL-PM (Nikolentzos et al., 2017). WWL (Togninalli et al. 2019) and FGW (Titouan et al. y (2) GNN based methods: DGCNN (Zhang al. (018a). CapsGNN (Xinyi & Chen 2018). GIN Xu et al. 2019)) and GraphS (Hamilton et al. 2017).
Both the standard stratified splits (Xu et al. 2019) and the random splits are considered. We use 10-fold cross validation with 90% training and 10 % testing, and report the best mean accuracy. For both settings, we use the Adam optimizer (Kingma & Ba 2015), batch size 64, hidden dimension 64, weight decay of 0.009, a 2-layer MLP with batch normalization, 500 epochs and dropout of 0.6, and = 0.1 over all datasets. The readout function as in (Xu et al. 2019) is used which concatenates representations of all layers to obtain final graph representation. For the standard stratified splits, we use the learning rate 0.009 over all datasets. For the random splits, we use the learning rate 0.008 for MUTAG and RDT-MSK and 0.007 for the other datasets. Table presents the results.
7

---

Published as a conference paper at ICLR 2022
Method
ogbg-molhiv
ogbg-moltox21
ogbg-molloxcast
ogbg-ppa
ogbg-molpcha
GIN
1..58
74.9110.51
63.41
68.92-11.00
22.66:10.28
GIN+VN
1..20+11.30
76.21
66.18+0068
70.37=1.07
27.03=+0.23
GSN
77.99+1.00
PNA
79.05:11.30
28.38:10.35
ID-GNN
78.30:+2.00
Deep LRP
17.19+1140
GraphSNN
1.75
1..45=1.10
65.4010.71 67.68
70.66 72.02=1448
24.96=1.50 1..50
GraphSNN+VN
79.72+1883
7..7
Table 3: Classification accuracy (%) averaged over 10 runs on graph classification, where X =
2. The
results of the baselines are taken from (Hu et al. 2020) and the leaderboard of the OGB website.
Method
MUTAG
PTC-MR
PROTEINS
BZR
IMDB-B
GSN-c
90.6 + 7.5
68.2 = 7.2
76.6 + 5.0
77.8 + 3.3
GSN
GSN-v
92.2 7.5
67.4 5.7
74.5 + 5.0
76.8 2.0
ID-GNN Fast
96.5 3.2
61.9 5.4
78.0 3.5
86.4 + 3.0
ID-GNNs
ID-GNN Full
5.6
62.5 = 5.3
77.9 + 2.4
88.1 4.0
Ours
GraphSNN
91.57 2.8
66.70 1.70
76.83 2.5
88.69 + 3.2
77.86 3.6
I-GNNNT NT
82.7
51.2 0.0
69.4 0.0
k-WL GNNs
1-GNN
82.2+
59.0
71.2 71.2
1-2-3-GNN
84.4 0.0
59.3 0.0
70.3 - 0.0
1-2-3-GNN
86.1 0.0
60.9 0.0
74.2 + 0.0
Ours
GraphSNN
87.30 3.1
61.63 2.8
74.01 = 3.2 82.72 1 3.9 74.81 = 3.5
Table 4: Classification accuracy (%) averaged over 10 runs on graph classification, where À = 2. The results of the baselines are taken from their original papers. GSN and ID-GNNs use the same experimental setup GIN, while k- WL GNNs uses the same experimental setup as CapsGNN. These experimental setups are detailed in Appendix B.
Experiments on large graphs. We use five large graph datasets from Open Graph Benchmark 1oogomol ogbg-moltoxcast and ogb-molpcha) and one protein-proter association network (oghg-ppa). Table Appendix B contains statistics for these large graph datasets.
(OGB) Hu et al. (2020). including four molecular graph datasets
12
We compare against the following methods that have reported the results on the above OGB datasets:
GIN and GIN+VN (Hu et al.) 2020), GSN (Bouritsas et al. 2020), PNA (Corso et al. 2020). ID-GNNs Yoou et al. 2021) and Deep LRP (Chen et al. 2000bb.. In addition to the original model of GraphSNN, we also consider a variant, denoted as GraphSNN+ VN, which performs the message passing over
augmented graphs with virtual nodes in GraphSNN (Hu al. 2020 Ishiguro et al. 2019).
We follow the same experiment setup as in Hu et al. (2020). We use the Adam optimizer with learning rate 0.001, batch size 32, dropout 0.5 and 100 epochs for all datasets. GraphSNN uses 8-layer MLP with embedding dimension 512 for ogbg-moltoxcee the embedding dimensions 300 and 256, and 8-layer and 5-layer MLPs for ogbg-moltoxcast and 1,bg-moltox21, respectively. For ogbg-molhiv, ogbg-molpcba and ogbg-ppa. both GraphSNN and GraphSNN+VN use 5-layer MLP and embedding dimension 200. Table 3 shows the results for the classification accuracy. Table 15 in Appendix B shows the results for the rumning time of the prepocessing step.
and ogbg-moltox21, while GraphSNN+VN has
Comparison with GNNs beyond 1-WL. We compare GraphSNN with the other GNNs that are more expressive than 1-WL, including: GSN (Bouritsas et al. 2020). ID-GNNs You et al. and k- KL GNN (Morris et al., 2019). We use the same experimental setup as in (Xu et al. 2019 Bouritsas al. 2020 Maron et al. 2019). Table shows the results.
2021
5.3 ABLATION STUDY
We perform an ablation study to analyze the effect of À values on model performance. Tables and show that À = 1 yields the highest performance for node classification. while À 2 is the best for graph classification. This reflects critical point - different classes structure information are needed by different graph learning tasks. X captures local density, e.g., overlap subgraphs may
8

---

Published as a conference paper at ICLR 2022
Dataset
Method
A=1
X=2
X=
X=
A=
GraphSNNGCX
83.1
1.3
82.312.4
81881.66
82.1
GraphSNNere
79.2=1.7
78.++1.2
78.5+1.
18.1
77.7+1.2
Cora
GraphSNN Groph8 AGE
80.5=2.5
80.3+2.1
79.8+19
79.2=1.9
79.4#2.2
GraphSNNG.a GAT
83.
83.5
83.2411.7
82.8.1.3
83.2.11.9
GraphSNNaON
72.3=115
71.721.3
71.121.
70.6=1.2
70.9
GraphSNNora GIN
68.3
68.34119
67.74114
67.1
1.
Citeseer
GraphSNN GraphSNNGraapSAAEE AGE
72.7=3.2
72.0#2.5
71.622.9
71.92.1
713+2.3
GraphSNNGAT GAT
73.5=1.6
72.911.7
72.5+111
72.621.6
72.0=1.3
Table 5: Classification accuracy (%) averaged over 10 on node classification with standard splits.
Dataset
Method
X=1
X=2
X=3
A=4
A=5
MUTAG
92.66:1:..4
94.14:1.22
93.38-1:.5
92.25-22.1
92.79-+2.0
PTC-MR
70.76=5.11
71.01=1.6
70.67+2.8
69.59+2.1
69.97#3.1
PROTEINS
77.90
78.21
78.15+2.1
77.2013.1
76.93+3.2
D&D
82.70+4.6
84.61+1.5
84.34+1.2
82.60+2.6
82.30+2.3
GraphSNN
BZR
87.61+4.9
91.88+3.2
91.45++2.6
91.38+2.1
90.90+3.1
COX2
86.2011.33
86.72:12.9
83.81
83.1342.6
83,9413.2
IMDB-B
77.07+5.2
77.87+3.1
77.60+3.6
77.32+3.2
77.10+3.3
RDT-M5K
59,53+2.6
60.23+2.2
60.10+2.3
60.00+2.1
59.90+2266
Table 6: Classification accuracy (%) averaged over 10 runs on graph classification with random splits.
considerably vary in the number of vertices but their local density can very close. Our experiments show that injecting such local density helps improve the performance of node classification. À = 2 captures local similarity, i.c., how similar two overlap subgraphs are. Two overlap subgraphs that considerably differ in the number of vertices would have very different structural coefficients. Since graph classification requires to compare the similarity of two graphs, = is thus the best.
5.4 OVERSMOOTHING ANALYSIS
We analyse the impact of model depth (number of layers) node classification performance. In addition to GCN and GraphSNNccw. we also compare these models with a residual connection (i.e., GCN+residual and CeophhSNNcx++rsiidee the standard splits and same hyperparameters as in Section 5. Table 7 shows the results. When increasing the model depth, GraphSNNGCN performs consistently better than GCN at each layer. This is because structural coefficients capture structural connectivity between target vertex and its neighbors. Thus, neighbor whose structural connectivity is weak would pass little messages to the target vertex, whereas a neighbor whose structural connectivity is strong would pass strong message to the target vertex. GraphSNN helps alleviate the oversmoothing issue even in the presence of residual connections. Further results of the oversmoothing analysis are provided in Appendix B.
We evaluate all the models Cora dataset using
#Layers
GCN
GCN+residual
GraphSNNGcN
GraphSNNocxx+trsiidal
79.6.10.5
80.310.7
80.110.8
81.6:11.6
81.510.4
82.8
83.1
84.1-11.7
3
80.3++0.6
82.3+0.5
82.0+0.38
83,4+0.7
4
78.2+00.
81.5+0.9
80.1+0.7
82.9+0.9
5
7.33
81.0-11.3
79.1
82.310.3
6
3..
80.6+0..5
7..5+11.3
1.2
31.6:10.9
79.7=0.6
1.
80,9+0.9
16.2+112
78.4+11.1
75.7++1.2
1..
Table 7: Classification accuracy (%) averaged over 10 runs on Cora dataset.
CONCLUSIONS
In this paper, we have introduced a GNN framework, which enables a general way of injecting structural information into a message- massang--psssng aggregation scheme. We have also introduced a novel GNN model, GraphSNN, for graph learning, and prove that GraphSNN is more expressive than 1-WL in distinguishing graph structures. It shown that GraphSNN consistently outperforms all the fate-oofthheaat approaches in both node classification and graph elassification benchmark tasks.

---

Published as a conference paper at ICLR 2022
REFERENCES
Waiss Azizian and Marc Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations (ICLR), 2020.
László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium on Foundations of Computer Science (SFCS), pp. 39-46, 1979.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM'05), pp. 8-pp. IEEE, 2005.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos 7afeiriou, and Michael M Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2000.09252. 2020.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound the number of variables for graph identification. Combinatorica, 12(4):389-410 1992.
Andrew Carlson, Justin Betteridge, Bryan Kisiel, Burr Settles, Estevam R Hruschka, and Tom M Mitchell. Toward an architecture for never-ending language learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI). 2010.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Mcasuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), pp. 3438 1488-3445,4 2020a.
Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems (NeurlPS), 2020b.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems (NeurIPS), 2020.
Pim de Haan, Taco Cohen, and Max Welling. arXiv:2007.083349 2020.
Natural graph networks. arXiv preprint
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure- acttvvity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
Simon Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. arXiv preprint 1rXiv:1905.13192, 2019.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. fair comparison of graph neural networks for graph classification. 2020.
Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning (ICML), pp. 3419-3430, 2020.
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), pp. 1263-1272. PMLR, 2017.
Martin Grohe. Descriptive complexity, canonisation, and definable graph structure theory, volume 47. Cambridge University Press, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), pp. 1024-1034, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovee. Open graph benchmark: Datasets for machine learning on graphs. Advances in Neural Information Processing Systems (NeurIPS), 2020.
10

---

Published as a conference paper at ICLR 2022
Katsuhiko Ishiguro, Shin-ichi Maeda, and Masanori Koyama. Graph warp module: auxiliary module for boosting the power of graph neural networks in molecular graph analysis. arXiv preprint arXiv:1902.01022 2019.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Diederick P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), 2015.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Nils M Kriege, Loeire-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. In Advances Neural Information Processing Systems (NeurIPS), pp. 1623-1631, 2016.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for supe-supee learning. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2018.
Xin Liu, Haojie Pan, Mutian He, Yangqiu Song. Xin Jiang, and Lifeng Shang. Neural subgraph isomorphism counting. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1959-1969, 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations (ICLR), 2020.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations (ICLR), 2018
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-222 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 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 (NeurIPS), 2020.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning (ICML), pp. 4663-4673, 2019.
Giannis Nikolentzos, Polykarpos Meladianos, and Michalis Vazirgiannis. Matching node embeddings for graph similarity. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chhann Chang, Yu Lei, and Bo Yang. Geom gen: Geometric graph convolutional networks. In International Conference on Learning Representations (ICLR), 2020.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent Weisfeiler-lehman procedure for graph classification. In International Conference on Machine Learning (ICML). pp. 5448-5458. PMLR. 2019.
Ryoma Sato. survey on the expressive power of graph neural networks. arXiv preprint wwXiv:2003.04078. 2020.
11

---

Published as a conference paper at ICLR 2022
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 2021 SIAM International Conference on Data Mining (SDM), pp. 333-341, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Radd Collective classification in network data. Al magazine, 29(3):93-93, 2008
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011,
Jeffrey J Sutherland, Lee A O'brien, and Donald F Weaver. Spline-fitting with genetic algorithm: A method for developing classification structure- activity relationships. Journal of chemical information and computer sciences, 13(6):1906-199)) 2003.
Vayer Titouan, Nicolas Courty, Romain Tavenard. and Rémi Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning (ICML), pp. 2019.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kernels. In Advances Neural Information Processing Systems (NeurIPS), pp. 6439-6449, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. International Conference on Learning Representations (ICLR), 2017.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural messsgg--pssinng In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14(3):347-373 2008.
Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 229): 1968.
Asiri Wijesinghe and Qing Wang. Dinets: Spectral cnns for graphs with feedback-looped filters. Advances in neural information processing systems (NeurIPS), 2019.
Jun Wu, Jingrui He, and Jiejun Xu. Demo-net: Degree-specific graph neural networks for node and graph classification. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 406 465,415,2000 2019.
Zhang Xinyi and Lihui Chen. Capsule graph neural network. In International conference on learning representations (ICLR), 2018
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In International Conference on Machine Learning (ICML), pp. 5453-5462. PMLR, 2018
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kemels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1365-1374, 2015.
Jiaxuan You, Jonathan Gomes-Selman Selman, Rex Ying, and Jure Leskovec. Identity- graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
Muhan Zhang and Yixin Chen. Weisfeiler-lehman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 575-583, 2017.
12

---

Published as a conference paper at ICLR 2022
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learnigg archi- tecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2018a.
Zhen Zhang, Mianzhi Wang, Yijian Xiang, Yan Huang, and Arye Nehorai. Retgk: Graph kernels based on return probabilities of random walks. In Advances in Neural Information Processing Systems (NeurIPS), pp. 3964-3974, 2018b.
Lingxiao Zhao and Leman Akoglu. Paimorm: Tackling oversmoothing in gnns. In International Conference on Learning Representations (ICLR), 2019.
13

---

Published as a conference paper at ICLR 2022
APPENDIX
A. CONNECTIONS TO PREVIOUS WORK
In the following. discuss how our framework generalizes the existing message-passing GNNS in the literature such as GCN (Kipf & Welling 2017). GraphSAGE (Hamilton et al., (017). GAT (Veličković al. 2017) and GIN (Xu et al., 2019) special cases. Table [
presents the local aggregation schemes used by these existing GNN models. They differ from each other w.r.t. the way of aggregating feature vectors in neighborhood and how they are combined with the current vertex's 's feature itself. i.e., summation or concatenation. Here, Qva is an attention coefficient capturing the importance of neighbor in GAT, e learnable or fixed scalar parameter used in GIN, W is learnable weight matrix and a is non-linear activation function, such as ReLU.
Note that, as defined in Equation me GATE (-) and AGGREGATE (-), respectively.
(t) and m.) refer to the messages aggregated by AGGRE-
GNN Model AGGREGATE" ())
AGGREGATE (-)
COMBINE(-)
GCN
E WEN(V)
WOR
(SUM(m!)) (8) .maa ml)))
GraphSAGE
Σ
ASO
hm
oW CONCAT(M!.) (4) ml)))
MEN(v:)
GAT
Σ (VN(v)
ave ((t
Qeu (+
(Sum(m))) (!), m())
GIN
Σ
(1)
(1 + c)ho
MLPO(SUM(())' ma ()))
(EN(v)
Table 8: Comparison of the aggregation schemes used in existing message-passiingg GNNs
COMPLEXITY ANALYSIS
Table 9 summarizes the time and space complexities of several popular message-passing GNNs and GraphSNN, where n and m are the numbers of vertices and edges in graph, respectively, k refers to the number of layers, and d are the dimensions of input and output feature vectors, respectively, is the number of attention heads used in GAT, and 8 is the number of neighbors sampled for each node each layer in GraphSAGE.
GNN Model
Time Complexity fkm (lemfd)
Memory Complexity
GCN (Kipf & Welling
2017
((m)
GIN
Xu et al. 2019)
(())
GAT
Veličković et al.
2017
Okkannfd + amd))
O(n²)
GraphSAGE (Hamiloo et al. 2017)
O(snfd)
O(n)
GraphSNN (ours)
O(kmfd)
((m)
Table 9: Time and space complexities of message-passing GNNs and GraphSNN.
FORMULATION OF GRAPHGNN
For each of these message-passing GNNs, denoted as M, we construct a variant GraphSNN by replacing its existing aggregation scheme by our aggregation scheme with structural coefficients as formulated in Eq. 3 These variants are used in our experiments for node classification benchmark tasks (see Section 5.1) in order evaluate how aggregation scheme with structural coefficients can improve performance, compared with their standard message-passsng aggregation schemes. Below the details of these variants.
GCN and GraphSNNGcN
14

---

Published as a conference paper at ICLR 2022
Graph Convolutional Network (GCN) (iipf & Welling 2017) applies normalized mean aggregation to combine the feature vector of a node with the feature vectors in its neighborhood N (()):
Wong
W
h(+11) = (((())
(6)
mE(A(()) VW(())
VI(()) is normalization constant for the edge (v, u), which originates from the normalized adjacency matrix D D-1/2 1/22D-1//2 W(tt) is a trainable weight matrix and a is a non-linear activa- tion function such as ReLU. We generalise GCN to model under the GMP framework, namely GraphSNNGcN to improve the expressive power GCN. We first construct a normalized structural coefficient matrix A. Formally, each neural layer of GraphSNNGGN may then be expressed as:
((+1) =0 (1000
w
w
). (7)
(E Apn +1) nEA((e)
Σ (EN())
(Amu + +1)
V V(WWN
GraphSAGE and GraphSNN GraphSNNGrvehsSACRR GraphSAGE
GraphSAGE (Hamilton al. 2017 learns aggregation functions induce new node feature vectors by sampling and aggregating features from a node's local neighborhood. GraphSAGE has considered three different aggregation functions such as mean aggregator, LSTM aggregator and pooling aggre- gator. In our work, we mainly focus on the mean aggregator that, for each vertex v, takes the mean of the feature vectors of the nodes in neighborhood and concatenates it with the feature vector of as shown below:
1(++1 = o (W(). CONCAT
1 n2 )) Σ MEN(()
(8)
[W())
where ('( is learnable weight matrix, and a represents non-linear activation function. We also generalise GraphSNN to a model under the GMP framework, namely GraphSNN GraphS This model first takes mean aggregation of the feature vectors in the neighborhood N(v) and then concatenates it with the feature vector of itself in the following manner.
((++)) -o (w CONCAT
Σ mEN(U)
(Aou + +1) 7000
(E mEN(w)
Σ
Apu + 1) (1())
(9)
GAT and GraphSNNGAT GAT
Graph Attention Network (GAT) (Veličković et al., 2017) linearly transforms the input feature vectors and performs weighted sum of the feature vectors for vertices in neighborhood after the transformation. GAT computes attention weights (1) using an attention mechanism and aggregates the feature vectors in neighborhood follows:
A ((+1) =o
Σ (1,8)ER
a (WW1O)!))
(10)
where W is a trainable weight matrix and a represents a non-linear activation function. We generalise GAT to model, called GraphSNNGAT: in the GMP framework. Firstly, we aggregate the feature vectors based on structural coefficients in our aggregation scheme, i.e., we compute
h + Σ (Aus+1 +1) VI((=)) ZEN(U)
7,00 = -0(00)
(Σ zEN(u)
Σ Ans +1) V (((W)I((()
(II)
and
7,00 7(()
Σ
Aoge A
(Aus +1) x'N((1))
Σ
(12)
(
15

---

Published as a conference paper at ICLR 2022
We then construct attention coefficients druu these aggregated feature vectors follows:
(1)
exp [L
(1) FM
(13)
EEEN(N) exp [eakyReLU(d""IW | ()
where represents the concatenation, w(()) is a learnabe weight matrix and a is a learnable weight vector. After that, we aggregate the neighborhood features follows using attention coefficients.
((+1) =o
Σ (U,
a ((1()))))
(14)
where W(()) is learnable weight matrix, and represents non-linear activation function. We use multi-head attention as stated in the original work Veličković et al. (2017).
GIN and GraphSNNGIN
Graph Isomorphism Network (GIN) (Xu et al. 2019) takes the sum aggregation over a neighborhood, followed by 2-layer MLP. The ((+1) is a learnable parameter or fixed scalar. Each neural layer is expressed as:
h(+1) MLP(++1) ( (++))))))
+
Σ h
(15)
kEN(2)
Here, we consider one of GIN variants employed in the original paper, where the learnable parameter é O, and generalise it to GraphSNNGrN as defined bwlow:
(t+1) = MLP(++1) (7(0)
Σ mEN(e)
Avw +)) +
Σ mEN(o)
(Aou + (on++1)a0 +))
(16)
B. EXPERIMENTS
DATASETS
Table TO contains the statistics for the five datasets used our experiments for node classification in
Section 5.
Dataset
Type
#Nodes
#Edges
#Classes
#Features
Cora
Citation network
2.708
5,429
1.433
Citeseer
Citation network
3,327
4,732
6
3,703
Pubmed
Citation network
19,717
44,338
500
NELL
Knowledge graph
65,755
266,144
210
5,414
ogbn-arxiv
Citation network 169,343
1,166,243
40
128
Table 10: Statistics for node classification datasets.
Table 11 below contains the statistics for the datasets used in our experiments on small graph
classification in Section [5.2] as well as the datasets used in an additional experiment for graph classification following the data splits and experimental setup in (Errica al. 2020). The results of this additional experiment are reported under Section "Graph Classification using Setup (Errica et al. " Appendix
Table 12 contains the statistics for the five large graph datasets from from Open Graph Benchmark (OGB) Hu et al. (2020), used in our experiments for large graph classification Section 5.2
EXPERIMENTAL SETUP ON SMALL GRAPHS
Previously, several experimental setups have been considered for evaluating graph classification small graphs TUD benchmark datasets (attps: chr chramrrs www.ers..iiiii wit.ub..hii.... io/ htto/aaasssssss. All the baseline methods in our paper the 10-fold cross validation technique. However, they differ in how they split soaning/validation/esstte classification accuracy. Below, discuss the details of their experimental setups.
data and how they report the final results in terms of
16

---

Published as a conference paper at ICLR 2022
Dataset
#Graphs
Avg Nodes
Avg # Edges
#Classes
MUTAG
188
17.93
19.79
2
PTC-MR
344
14.29
14.69
2
BZR
405
35.75
38,36
2
COX2
467
41.22
43,45
2
ENZYMES
32.63
64.14
6
IMDB-B
1000
19.77
96,53
2
PROTEINS
1113
39.06
72.82
2
D & D
1178
284.32
715.66
2
NCII
4110
29.87
32.30
2
RDT-M5K
5000
508.52
594.87
5
COLLAB
5000
74,49
2457.78
3
Table 11: Statistics for small graph classification datasets.
Dataset
#Graphs
Avg # Nodes
Avg # Edges
#Tasks
Task Type
ogbg-molmon moblolol
41,127
25.5
27.5
I
Binary classification
ogbg-moltox21
7,831
18.6
19.3
12
Binary classification
ogbg-moltoxcast
8,576
18.8
19.3
617
Binary classification
ogbg-molpeba
437,929
26.0
28.1
128
Binary classification
ogbg-ppa
158,100
243.4
2,266.1
Multi-class classification
Table 12: Statistics for large graph classification dataset (OGB graph datasets).
CapsGNN (Xinyi & Chen 2018) splits the datasets into 80 % for training, 10 % for validation, and 10 % for testing. The training is stopped when the performance the validation set goes to the highest. Then they obtain the test set accuracy that corresponds to the epoch with the highest validation accuracy each fold. The final results are reported by computing the mean accuracy and standard deviation over 10 folds.
DGCNN Zhang et al. 2a) splits the datasets into 90 % for training and 10 % for testing. They obtain the test accuracy of the last epoch in each fold. They report the final results by computing the mean accuracy and standard deviation on the test accuracy over 10 folds.
GIN and GraphSAGE (Xu et al. 2019) split the datasets into 90 % for training and 10 % for testing. They average the test accuracy on 10 folds and select the epoch with the highest averaged accuracy. Then they report the final results by computing the mean accuracy and standard deviation based on the selected epoch.
FGW (Titouan al. 2019) splits the datasets into 90 % for training and 10 for testing. Then, they use the nested cross validation technique on the same folds, and repeat the process 10 times. They report the final results by computing the mean accuracy and standard deviation.
The other baseline methods split the datasets into 90 % for training and 10 % for testing, and repeat their experiment times. Then they report the final results by computing the mean accuracy and standard deviation.
In our work, we split the datasets into 90 % for training and 10 % for testing. We obtain the best validation accuracy on each fold. Then report the final results by computing the mean accuracy and standard deviation over 10 folds"
NODE CLASSIFICATION USING RANDOM SPLITS
Following the work Pei et al. 2020), we randomly split graph nodes into 60%, 20% and 20% for training, validation and testing, respectively. The other hyperparameter settings the same as in Section 5. Table 13 shows the results. We see that our models consistently outperform all of the baseline methods on all benchmark datasets. Specifically, GraphSNocN improves upon GCN by margin of 1.5%, 1.7%, 1.6% and 2.4% on Cora, Citeseer, Pubmed and NELL, respectively.
'The implementation he found http:///tthhih.coommooos22226aaf

---

Published as a conference paper at ICLR 2022
GraphSNGAr improves upon GAT by 1.3%, 1.6% and 2.0% Cora, Citeseer and Pubmed, respec- tively. GraphSNGIN improves upon GIN by 3.8%, 1.7%, 1.8% and 1.6% on Cora, Citeseer, Pubmed and NELL, respectively. Graph AGE improves upon GraphSAGE by 1.3%, 1.7%, 1.1% and 2.3% on Cora, Citeseer, Pubmed and NELI, respectively.
Method
Cora
Citeseer
Pubmed
NELL
GCN
85.7 = 1.6
73.6 + 1.0
88.1 + 1.2
72.2 + 5.6
GraphSNNGcN
87.2 1.5
75.3 + 1.3
89.7 + 1.7
74.6 6.3
GAT
86.3 = 0.3
74.3 - 0.3
87.6 = 0.1
GraphSNNG.A
87.6 0.9
75.9 + 0.8
89.6 + 0.6
GIN
82.5 = 0.8
70.8 + 1.9
85.0 - 1.5
66.7 + 3.3
GraphSNNGIN
86.3 0.7
72.5 + 1.5
86.8 + 1.2
68.3 + 3.7
GraphSAGE
86.8 + 1.9
74.2 + 1.8
88.3 + 1.1
69.4 + 4.3
CraphhSNNGaaphS.Az
88.1 1.5
75.9
+ 1.3
89.4 + 2.4
71.7 + 4.5
Table 13: Classification accuracy (%) averaged over 10 random splits on node classification.
GRAPH CLASSIFICATION USING SETUP ERRIIAA ET AL.
2020)
Following the data splits and experiment setup introduced in (Errica al. 2020), we further evaluate our method. The experimental setup in (Errica et al. (020) provides fair performance comparison process on GNN methods. The evaluation process has two different phases: (1) model selection on the validation set, (2) model assessment on the test set. More specifically, they first split the datasets into 90 % for training and 10 for testing. Then the entire training set is further split into 90% of training and 10% of validation. They apply the inner hold-out method to select the best model based on validation accuracy. After selecting the best model, they train the model three times on the entire training set with early stopping.
We have conducted experiments on four bioinformatics datasets (NCII, PROTEINS, ENZYMES and D&D) and three social network datasets (COLLAB, IMDB-B and REDDIT-5K) with node features. The results of the baseline, DGCNN and GIN are taken from the paper (Errica et al. 2020). Note that the final results of DGCNN and GIN from the paper (Errica al. 2020) reported by computing the mean accuracy and standard deviation on the test set in these three runs, which are different from the original papers of DGCNN and GIN. Table shows the results.
Method
NCII
PROTEINS
ENZYMES
D&D
COLLAB
IMDB-B
REDDIT-5K
Baseline
69.8+2.2
75,8 +:7 3.7
65.246.4
78.4 4.5
70.2+:1.5
70.8+5.00
12.2=1.5
DGCNN
76.4+1..7
72.913.5
38.915.7
76.62:4.3
71.21:99
4..2+1.2 71.243.9
69.243.0
GIN
80.0+1.4
73.314.0
59.614.5
75.3+229
75.61:2.3
16.1
GraphSNN
81.6 1 2.8
1..5335
61.7 3.4
77.11..3
77.0 17.0....11
72.3 1 3.6
57.1 3.1
Table 14: Classification accuracy (%) averaged over 10 runs on graph classification.
GRAPH CLASSIFICATION ON OGB GRAPH DATASETS
Table 15 shows the results for the running time of the prepocessing step in our method GraphSNN for large graph datasets (averaged over 5 runs). Note that the preprocessing step can be parallellized efficiently at the node level. The CPU time shows the total preprocessing time of a dataset which each node is preprocessed sequentially, and the CPU time per node shows the average preprocessing time per node.
OVERSMOOTHING ANALYSIS
We have also conducted further experiments to analyze the effectiveness of our method in alleviating the over-smoothing issue. We compare GIN (i.e., spatial GNN), DFNets (Wijesinghe & Wang 2019) (i.e.. a spectral GNN), GraphSNNGIN and GraphSNN For a fair comparison, we remove the dense-net architecture of DFNets and use the same hyperparameters in the original paper. We
18

---

Published as a conference paper at ICLR 2022
Dataset
CPU time (seconds)
CPU time per node (milliseconds)
ogbg-molhit
66.97
0.06383
ogbg-moltox21
79.37
0.54565
ogbg-moltoxcast
380.84
2.36417
ogbg-ppa
820.12
4.71235
Table 15: Running time of the prepocessing step for large graph datasets averaged over runs.
evaluate all models over the cora dataset using the standard splits. The classification accuracy is averaged over 10 runs node-classffication
#Layers
GIN
GraphSNNGrX
DFNet
GraphSNN
I
13.
76.1
80.5
80.1
2
77.6=11.3
79.2+1..7
81.9
83.1+1.8
3
75.2
18.
8..611.3
82.0+:0.8
4
48.6:12.1
77.2+2233
80.7+00.6
80.1
5
10.3+1.9
75.942.1
75.6+0.3
19.1
6
36.1+2.3
73.3+1.8
6..3
1..
7 27.5#2.1
71.9
60.9
1..
8
20.3+
69.3+12.2
53.
1..
Table 16: Oversmoothing analysis of GIN and spectral GNN (DFNet) cora dataset.
GraphSNN can alleviate ovor-smoothing because structural coefficients capture structural connec- tivity between target vertex and its neighbors. Thus, neighbor whose structural connectivity is weak would pass little message to the target vertex, whereas a neighbor whose structural connectivity strong would pass strong message to the target vertex.
Figure 4 shows the results of GCN and GraphSNNGCN on the datasets Cora, Citeseer and Pubmed, in terms of classification accuracy averaged over 10 runs in the setting of standard splits.
(a) Cora
(b) Citeseer
(c) Pubmed
Rccuraty
GraphSNocr
30-
30
GCN
20
20
20
Number of Layers
Number Layers
Number of Layers
Figure 4: Oversmoothing analysis w.r.t. the model depth for node classification.
ABLATION STUDY WITH AUGMENTED NODE FEATURES
We consider an experimental evaluation setup called BL, which serves as the baseline for all experi- ments in this ablation study. In the setting of BL, the AGGREGATE' in GraphSNN is set to 1. Then, different variants of BL consider different local substructure counts as additional node features. This allows us analyse what types of local substructures our proposed architecture can distinguish.
There are five variants of BL. being considered in the ablation study:
(1) BLsc: Setting AGGREGATION! of GraphSNN to I and keeping structural coefficients for neighbors.
(2) clique, Setting AGGREGATION of GraphSNN 1, removing structural coefficients for neighbors, and adding additional node features (triangle and 4-clique counts) into the original feature vectors.
19

---

Published as a conference paper at ICLR 2022
Method
GSN-v
BL
BLsc
BLSC+NF
GraphSNN
MUTAG
92.20+7.5
90.21+2.3
94.06+2.44
95.16+2.55
94.70+1.9
PTC-MR
67.40115.7
67.13
70.1813.1
71.041:.11
70.58:3.1
PROTEINS
74.59:15.0
76.42:12.6
78.05:2..3
78.6612.11
78.42:42.7
BZR
86,82+3.1
90.67+3.11
91.98+3.2
91.12+3.0
IMDB-B
76.80+2.0
77.00+3.1
77.23+2.8
78.53+2.9
78.01+2.8
Table 17: Analysis the effects of structural coefficients with substructure counts, i.e, triangle and 4-clique counts. Classification accuracy (%) averaged over 10 runs on graph classification.
Method
ID-GNN
Byde
BLsc
BL BLC++N
GraphSNN
MUTAG
96.50+3.2
91.36+2.1
94.06+2.4
96.61+2.3
94.70+1.9
PTC-MR
61.90+5.4
67.57+3.3
70.18+3.1
71.76+3.2
70.58+3.11
PROTEINS
78.00113.5
77.26.1..5
78.05.1..3
78.95
78.42.12.7
BZR
86.40+3.0
86,83+3.3
90.67
91.75=+3.4
91.12+3.00
IMDB-B
76.3612.6
77.23+28
78.58
78.01
Table 18: Analysis the effects of structural coefficients with substructure counts, i.e, cycle counts. Classification accuracy (%) averaged over 10 runs on graph classification.
(3) BL BLSC+NFF Setting AGGREGATION of GraphSNN to 1, keeping structural coefficients for neighbors, and adding additional node features (triangle and 4-clique counts) into the original feature vectors.
oligue
BL NF Setting AGGREGATION of GraphSNN to removing structural coefficients for neighbors, and adding additional node features (cycle counts) into the original feature vectors.
cycle;
(5) BL BL SC++FFF Setting AGGREGATION of GraphSNN to keeping structural coefficients for neighbors, and adding additional node features (cycle counts) into the original feature vectors.
cycle
clique We compare GraphSNN with GSN-v (Bouritsas et al. 2020 BL cligue BLsc, and SCC++NP NF to analyze how our proposed architecture relates to the models with triangle and 4 clique counts as additional node features. Similarly, BLaycle BLsc, and eyele
compare GraphSNN with ID-GNNs (You et al.] (02T). SL to analyze how our proposed architecture relates the models with cycle counts as additional node features. We concatenate the counts of cycles with length to starting and ending at the given source node with its original feature vector as in (You al.. 2021). Table 17 and Table 18 show the experimental results. As AGGREGATE is set to 1 in setting of BL., the performance gap between BF and SL reflects the effectiveness of structural coefficients enhancing relational inference between target vertex and its neighbors. The performance gap between BLsc and GraphSNN above shows the effectiveness AGGREGATE' in our proposed model GraphSNN. Furthermore, BLsc+NF consistently performs best since incorporate both extra node features and structural coefficients into the feature aggregation. There is small performance gap between BLSC+ N and GraphSNN due to augmented node features that can capture additional structural information that cannot be captured using structural coefficients.
C. PROOFS FOR LEMMAS AND THEOREMS
Proof for Theorem I
Theorem 1. The following statements are true: (a) If S; Ssubgraph Sy. then S; -overlap Syi but not vice versa; (b) If S; Zoverlap Sy. then St Ssubtree Sy: but not vice versa.
Proof. In the following, we prove the statements in this theorem one by one.
For Statement (a), by S; Ssubgraph Sj and Definition 1, we know that there exists bijective mapping g' (i) + NG) such that for the vertex and any vertex o' @N((i), i and v' are adjacent in S; iff = gi) and u' = g(v") are adjacent in Sj. and h; = hy and h, = hus where g is bijective mapping between S; and S, defined by Definition Then for each pair of overlap subgraphs S
20

---

Published as a conference paper at ICLR 2022
and Sju', we can further extend g' along 9 on Siv and Sie' That is, g'(t) u g(u) u. If in Sier. by the definition of overlap subgraph, v must either be or a neighbor of i. Hence u = g'vv) in this case must be either
neighbor of j. By the definition of g and the fact that g'(v) iff g(v) = u, we know that for any two vertices e1 and v22 in Siør, they are adjacent in Sive iff their corresponding vertices o((1) and ('(22) are adjacent in Sju' and their corresponding feature vectors are indistinguishable, i.c, Sky Subbrraph Sjw' for any v' E (i) and g(v") w. Conversely, if S Coverlop Sy. then it is possible that St Feubgraph Sj as shown by the two graphs in Figure 2 a).
For Statement (b), if S; Soverlap Sj. then to prove S: Suhttree Sj we need to show that there exists bijective mapping g :V(i) - (J) such that g(t) j and, for any v' E Ei) and g(v') = n', the feature vectors of v and u' are indistinguishable, i.c., f, = hw. By Def. 2 we can find a bijective mapping o' : (i) + (j) such that (i) = j and, for any v' E (i) and g'(x') = u'. Si and Sju' are subgraph-isomorphic. This implies that g' cannot distinguish the feature vectors of v' and u' for any o' (i) and g(v') u'. Similarly, the converse does necessarily hold and one counterexample is the set of graphs as shown in Figure (b) which are subtree-isomorphic but not overlap- isomoohii.....
Proof for Theorem 2
Theorem 2. Let M be GNN. M is as powerful as 1-WL in distinguishing non-isomorphic graphs if M has a sufficient number of layers and each layer can map any S, and S3 S into two different embeddings (i.e., ((S.) + ((S))) if and only if S; Hsubtree Sj.
Proof. We first show that, for any two graphs G and G2, if they can be distinguished by I-WL, then they must be distinguishable by such a GNN M as well. Suppose that 1-WL takes k iterations to distinguish G1 and G2. i..., 1-WL yields the same multiset of node labels on G1 and G2 in the iterations from 0 to k-1, but two different multisets of node labels on G and G2 in the k-th iteration. To derive a contradiction, we assume that a GNN M that satisfies the above two conditions cannot distinguish 11 and G2 in the iterations from 0 to k. Since 1-WL can distinguish G1 and G2 in the k-th iteration, means that there must exist two neighborhood subgraphs, say S, and Sj. which correspond to two different multisets of node labels
G and G2 at the k-th iteration. These two different multisets of node labels correspond to two different multisets of feature vectors in their neighborhoods, i.e., /h EN(i)) * hh /u/uu E N By Def. 3 we know that S; Subtree Sy. Then this means that ((S)) + <(S;), which contradicts the assumption that M cannot distinguish G1 and G2 in the iteration k.
Now, we show the other direction that, for any two graphs G1 = (Vi, F.)) and G2 = (V2, E2). ). if they can be distinguished by such a GNN M, then they must be distinguishable by 1-WL. Similarly, suppose that at the k-th iteration, .M maps the neighborhood subgraphs of these two graphs into two different multisets of node embeddings. i.e., ((((S,)lo= E Vi 7 ((((S))lo V2B. This is means that we can find at least two different neighborhood subgraphs S; and S₁ such that ((S.) * ((5)). For such neighborhood subgraphs S and Sj. we know that S, Heubtree Sj. Then this means that S; and Sj correspond to either h; * h2 or (h, E ( * (ha]u E NN)) which can be relaheled by 1-WI. into two different new labels. Thus, 1-WI. can also distinguish such neighborhood subgraphs, and accordingly distinguish G1 and G2.
The proof is completed.
Proof for Theorem 3
Theorem 3. Let M be GNN whose aggregation scheme to is defined by Eq. Fgg 3 M is strictly more expressive than 1-WL in distinguishing non-isomorphic graphs if M has sufficient number of layers and also satisfies the following conditions:
(1) M can distinguish at least two neighborhood subgraphs S; and Sy with S; Ssubtree Sj. St + subgraph S₁ and & Aiorl =N(i)) + (Ajulul eN())::
(2) & ( 1
(0 E (()B.. (Amm,, 1 n ((v))) is injective.
21

---

Published as a conference paper at ICLR 2022
Proof. We prove this theorem in two steps. First, prove that GNN M satisfying the above conditions can distinguish any two graphs that are distinguishable by 1-WL by contradiction. Assume that there exist two graphs G1 and G2 which can be distinguished by 1-WL but cannot be distinguished by M. Further, suppose that 1-WI. cannot distinguish these two graphs in the iterations from 0 to k-1, but can distinguish them in the k-th iteration. Then, there must exist two neighborhood subgraphs S, and S3 whose neighboring nodes correspond to two different multisets of node labels at the k-th iteration, i.c. (1 |u E ( * [hg |u E M(j) By the above condition (2), we know that is injective. Thus, for S; and Sj. + would yield two different feature vectors at the k-th iteration. This means that M can also distinguish G1 and G2, which contradicts the assumption. Our proof in the first step is done. For the second step, we can prove that there exist at least two graphs that can be distinguished by M but cannot be distinguished by 1-WL. Figure] presents two of such graphs C
Proof for Theorem
We consider that, for each vertex in graph, its node features from countable set; similarly, for each pair of adjacent vertices in a graph, its structural coefficient is also from a countable set. Assume that H. A and W are countable sets where H is node feature space, A is structural coefficient space, and W = [Aihhil Aij E A, h4 E H}. Let H and W be two multisets containing elements from H. and W. respectively, and [ [W].
Lemma 1. There exists a function s.l. (H, W) EneH,wew [(h, w) is unique for any distinct pair of multisets (H, W).
Proof. Since H and W countable, there must exist two functions 4/1 H Nodd mapping h H to odd natural numbers and 4/2 W -> Neven mapping w E W to even natural numbers. Further, for any pair of multisets (H, W), since the cardinality of H and W is bounded, there must exist number N E N such that [ < N and W| < N. Thus, we can find a prime number P > 2N. Then we have a mapping I as [(h, w) = (h) + p-) such that EnEH. f'h, w) is unique for each distinct pair of (H, W).
L
Lemma 2. There exists a function f s.t. T' The H, W) (be. [H) +
EneH f(h, w) is unique for any distinct (hey H, W), where h. H. | ha E W, and 7/ can be an irrational number.
Proof. As hi E H and [h E W, we may have f(h,, [b), = (th) + ( where 4/ H + Nodd and v/2 : W Neven as defined in the proof for Lemma Let (bvr, Hi, Wi) and (hve, H2, W2) be two different tuples. Then, there are two cases:
(1) When hol = h22 but (H,,W) * (H2, W2). by Lemma I we know that ΣneH, w(,,w) # EneHs f(h, w). Thus, T'(ho,, Hi, Wi) # x' <'(he2, H2, W2).
(2) When he * hoz, we prove xt (ho1, H1. W1) + N' (hoz. H2, W2) by contradiction. Assume that T' (h.1. H,, Wi) = nt (h,2, H2, W2). Then, we have:
(heh Halbb)) +
Σ
[(h, w) = (1o H22))2)) +
Σ
5(h, w)
heHg.WEW2
This gives us the following equation:
r (f(brs H1 (ai)hh))-( fh. (2alhh2) (Hallhe))
-
Σ
f(h, f(h,w) ((h.w))-((
Σ
f(h, w)).
hENa.wEWs
NEHL.WEW
When is an irrational number, L.H.S. of the above equation is irrational but R.H.S. is rational. There is a contradiction. Thus, x' (ho,, H1, Wi) F x' (hoz, H2, W2).
Based on Lemma and Lemma can prove the following theorem.
22

---

Published as a conference paper at ICLR 2022
Theorem 4. GraphSNN is more expressive than 1-WL in testing non-isomorphic graphs.
Proof. We prove this theorem by showing that GraphSNN is GNN satisfying the conditions stated
in Theorem 3 For the first condition, consider the two graphs shown in Figure [I GraphSNN can distinguish these two neighborhood subgraphs St and Sy with I A Jv' E (N(ii) * {[ ju' NO) For the second condition, by Lemmas I and 2 as well as the fact that MLP as a universal approximator (Xu et al. 2019) can be used to model and learn the functions and g, we know that GraphSNN also satisfies this condition.
23


Reviews:
[{"review_id": "iVIrKbFpBqD", "reviewer": "Reviewer_csQY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The contribution of the work is definitely relevant and significant. The framework is solid, well-justified, and supported by proofs. The experimental results are quite convincing as they confirm the good performance of the method in classical datasets. \n\nI would however encourage the authors to work a bit more on the presentation of the paper. While the paper is generally well-written, there are parts that are difficult to follow for someone who is familiar with GNNs, but not working exactly on aspects of expressivity. For example, the notions of subgraph-isomorphic, overall-isomorphic, and subtree-isomorphic are very technical, and hard to follow. I would appreciate it if the authors could make them more clear, by for example, explaining better Fig. 2. \n\nSimilarly, the proposed choice of \\omega, in Eq. 4, should be better explained/motivated.  \n\nSome additional minor comments:\n   - '0.05 level of significance': how do you define it? Please elaborate. \n   - Any intuition on what the performance on the MUTAG dataset is not that great?\n   - Please double check the References to make them complete and consistent (e.g., Waiss Azizian et al..., Cosro....'33'?,2020)\n\n", "summary_of_the_paper": "This paper deals with the very challenging and important problem of designing Graph Neural Networks (GNNs) that are more expressive. The authors propose a new GNN framework, that injects structural information into a message-passing aggregation scheme. The proposed architecture (GraphSNN) is shown to be more expressive than the 1-WL in distinguishing graph structure. Finally, the framework is validated in state-of-the-art node classification and graph classification benchmarks. ", "summary_of_the_review": "This is a good paper, with some aspects of the presentation that should be improved. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "d44lOms2YB5", "reviewer": "Reviewer_FAad", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes an efficient method for message passing that can incorporate structural information (that of neighborhood subgraphs) that is provably more expressive than 1-WL. As compared to three strands of provably powerful (more than 1 WL) GNNs, the method has limited additional computational overhead, and can also show encouraging results on the oft-quoted \"over smoothing\" problem. This is borne out in extensive experimental results and a satisfactory ablation. \n\nIn the recent literature on GNNs, there have emerged three directions of research that aim to construct procedures more expressive than 1 WL:\n1. Higher-order WL-based methods, which often can get prohibitively expensive.\n2. Using features generated from substructures (most of the papers taking this approach claim this information is available through domain knowledge, but often just use triangles and the likes). \n3. Augmenting node features with identifying information to improve expressive power. \n\nThe central idea of the paper is grounded in the common observation that treating the neighborhood as a multiset of features ignores rich topological information, limiting the expressivity of message passing procedures that use such a representation. If the neighborhood is represented as a neighborhood subgraph, then 1-WL is only as powerful as distinguishing neighborhood subgraphs in terms of subtree structures.  The question then becomes if structural information can be incorporated in a way that can go beyond neighborhood subtree isomorphism. Towards this end, the authors show that there exists a class of isomorphic graphs that lie in between neighborhood subgraph isomorphism and neighborhood subtree isomorphism, which they call overlap subgraph isomorphism. It is shown that by incorporating structural information that can solve overlap subgraph isomorphism, one gets a message-passing network that is more expressive than WL. \n\nTo be more specific, section 2 provides the hierarchy of local isomorphism mentioned above. Theorem 1 states that subgraph isomorphism implies overlap subgraph isomorphism but not vice-versa, and that overlap subgraph isomorphism implies subtree-isomorphism but not vice-versa. 1-WL can only distinguish those graphs that can solve for sub-tree isomorphism at each layer. In order to go beyond 1-WL, the authors focus on overlap-subgraph isomorphism and define a set of structural coefficients for each vertex based on overlap subgraphs. These coefficients depend on reasonable notions of closeness, density, and invariance. The exact form of such coefficients is shown in section 4, and it is also shown that incorporating such information can give a method strictly more powerful than 1 WL. Since it just admits the same message passing paradigm, the computational overhead is limited. \n\nExtensive experiments on node classification (Cora, CIteseer, Pubmed, NELL, ogbn-arxiv), graph classification for the commonly used small graph datasets, and large graphs show across-the-board improvement compared to the competition (including the higher-order methods). The ablation shows the importance of the structural coefficients. Further, another set of experiments show that the proposed method is able to avoid the so-called oversmoothing problem (however, the results are presented without comment -- it would be beneficial to share some intuition on why this is the case). \n\nIn summary, I think the paper makes a solid contribution. It proposes a well-motivated method and validates it by extensive experimentation that leaves little doubt on its efficacy. \n\nMinor comments: \n- The paper will benefit from sharpening the writing in the abstract and intro -- it feels a little bit wayward and has some convoluted sentences. \n- The paper title, and most of the paper itself, uses the spelling \"Lehman.\" The actual spelling is Leman. Somewhere after the intro, when the original WL paper is cited (and in some following sentences), the correct spelling is used. I would suggest either using the correct spelling throughout, or sticking to Lehman throughout (since it is widely used, and Leman himself did not mind it https://www.iti.zcu.cz/wl2018/pdf/leman.pdf)\n- I don't believe that the citation of \"Provably Powerful Graph Networks' of Maron et al. is accurate. It is cited as a powerful (3 WL) method that is expensive, however, I think it is an efficient method. The authors might want to verify this claim. \n- Line 4 from the bottom of page 1: typo \"This solution enables GNNs to provably more expressive\": -> \"This solution enables GNNs to provably be more expressive\"\n- Line 2 from the bottom of page 1: \"which require high computational overheads and are impractical\" -> \"which require high computational overhead and are impractical\"\n- Line 1 page 2: \"(2), our method does not require any domain\" I am not sure it is accurate to say that these methods require domain knowledge. They can certainly benefit from it, and this claim is made in those papers, but they just stick to simple sub-structures such as triangles that are easy to treat. This repeats on page 3. \n- Line 3 of the second paragraph, page 2: \"capacity of a model\" --> \"capacity of the model\"\n\nDisclaimer: I have not verified the proofs for correctness. However, based on the statements of the theorems and the general idea, I can buy them to be true and base my review on that assumption (since I expect these statements to be true). ", "summary_of_the_paper": "This paper proposes an efficient method for message passing that can incorporate structural information (that of neighborhood subgraphs) that is provably stronger than 1-WL. As compared to three strands of provably powerful (more than 1 WL) GNNs, the method has limited additional computational overhead, and can also show encouraging results on the oft-quoted \"over smoothing problem\". The benefit of better expressivity coupled with the simplicity of the method is borne out in extensive experimental results and a satisfactory ablation. ", "summary_of_the_review": "Well motivated method that is provably more powerful than 1-WL, which incorporates structural information in a principled manner using the notion of overlapping-subgraph ismorphism. Extensive experimentation shows strong performance compared to the competition (including the higher-order WL procedures). ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "aaFIQr6Lq3_", "reviewer": "Reviewer_Z8WJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. **Originality**  \n\nThe paper belongs to a body of recent works which aim to break the expressive power limit of MPNNs in a sub-quadratic memory complexity in the number of nodes. As far as I’m aware, the aggregation scheme suggested in the paper is novel, providing a constructive way to design more powerful architectures than the 1-WL test. \n\n3. **Experimental evaluation** \n\n   ***Strengths*** - the paper demonstrates a boost in performance on node and graph classification. \n\n   ***Weaknesses*** -\n\n   1. Expressive power experiments  - also an experimental evaluation showing what types of structures the proposed architecture can distinguish would be interesting to see (e.g., cycles, d-regular graphs). \n   2. Over-smoothing - the empirical results are not explained. Do the authors have a conjecture as to why their proposed method circumvents over smoothing?\n\n   ***Suggestions***\n\n   - Further discussion on generalization to unseen graphs (With larger / smaller average neighborhoods)? Since the aggregation coefficients suggested are normalized (edges/vertices) it might be that the suggested model is more robust to size differences in graphs. It would be interesting to see how it performs. For example, a simple experiment like the ones performed in [1].\n\n   \n- **Clarity** - paper is well written; claims are well supported by theoretical proofs and guarantees.\n\n\n[1] Yehudai, G., Fetaya, E., Meirom, E., Chechik, G., & Maron, H. (2020). On Size Generalization in Graph Neural Networks. ArXiv, abs/2010.08853.\n\n\n\n", "summary_of_the_paper": "The paper introduces a general framework for designing message-passing neural networks (MPNNs) stronger than the 1-WL distinguishing power via structural information injection to the aggregation scheme in the message passing framework. Unlike common MPNNs which perform neighborhood aggregation based on a pre-defined fixed function (which does not depend on the neighborhood subgraph structure) or based on a learned function of the neighborhood node features, the paper suggests a weighting function in the aggregation step of MPNNs which depends on the structure of the neighborhood subgraph. The authors show that under reasonable conditions the resulting architecture has a superior expressive power than the 1-WL test. This also implies superiority in expressive power over common MPNNs while maintaining the same memory and time complexity. The paper introduces a hierarchy of 3 levels of neighborhood isomorphisms: subtree, overlap, and subgraph; which facilitate the proofs and theoretical guarantees. Furthermore, as a by-product, the authors show improved robustness to the notorious over smoothing problem in MPNNs.", "summary_of_the_review": "A well written paper with strong theoretical exposition and results. \n\n\n---\n**Post Rebuttal**: I am satisfied with the authors response and keep my original score. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "LMqgPiTK-SY", "reviewer": "Reviewer_HLe3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "* Pros:\n\n1. Overlap isomorphism is a nice point to find a balance between expressive power and computational efficiency. Based on that, it is persuasive to encorporate the three properties into structural coefficients.\n2. The setting of $\\lambda$ is very interesting to me. It brings the coefficients some flexibility so that different $\\lambda$'s may capture inherent key information in different learning tasks, as shown in experiments.\n3. GraphSNN shows impressive experiment results. On node classification, it improves the counterparts of traditional GNNs by considerable boost, but is also very easy to use. On graph classification, it outperforms baselines by an intriguingly large margin. The performance drops slowly when it stacks more layers.\n\n* Concerns:\n\n1. In the beginning of page 2, the sentence ``compared with the methods of augmenting node identifiers ...'' needs more explanation. If I understand correctly, the latter claim is from the ablation study of $\\lambda$ in Section 5.3. But I do not see its relationship with node id/random feature models.\n2. According to the definition of $\\tilde{A}_{vu}$ with normalization above (5), can the first summation over $u\\in \\mathcal{N}(v)$ be simplified as 1?\n3. Since structural coefficients emphasize strongly connected neighborhood, I am wondering whether it would hurt the performance when there is a task requiring long-range information [1] and the path is, to some extent, adversarially going through a path with weaker connectivity.\n4. With respect to oversmoothing on node classification, I am wondering whether the graph operator (can be derived from (5)) with different $\\lambda, \\gamma$ has dominating subspace [3] that aligns well with the labels. A possible experiment is to send features through leading eigenvectors and then do pure MLP, following [2].\n5. Expressive GNNs typically show better performance on graph regression tasks than graph classification. So it would be better to show comparision with expressive baselines on regression datasets such as QM9 and ZINC, instead of Table 4, if time permits.\n\nReference:\n\n[1] On the bottleneck of graph neural networks and its practical implications. U Alon, E Yahav.\n\n[2] Revisiting Graph Neural Networks: All We Have is Low-Pass Filters. NT Hoang, T Maehara.\n\n[3] Graph Neural Networks Exponentially Lose Expressive Power for Node Classification. Kenta Oono, Taiji Suzuki.", "summary_of_the_paper": "To overcome expressive weakness of message passing neural networks and computational efficiency of expressive GNNs, this paper proposes a new perspective by introducing overlap subgraphs and overlap isomorphism which is between subgraph isomorphism and subtree isomorphism. Based on that, it carefully design GraphSNN with local structural coefficients to control message passing to obtain more expressive power than 1-WL GNNs. Experiments are conducted on node-level and graph-level classification tasks with an abalation study on a key hyperparameter.", "summary_of_the_review": "I would like to recommend to accept this paper, for its expressive, efficient and easy-to-use GNN component with intriguing performance.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes an efficient method for message passing that can incorporate structural information that is provably stronger than 1-WL. As compared to three strands of provably powerful (more than 1 WL) GNNs, the method has limited additional computational overhead, and can also show encouraging results on the over smoothing problem. Overall speaking, all the reviewers like this paper quite a lot, although the also raised some minor concerns. The paper also attracted some unofficial reviewers who provided quite a few related works. The authors did a good job in interacting with the reviewers and addressing their minor concerns. So, we believe the paper is worth accepting, and could be a significant work in the field of graph neural networks.
Decision: Accept (Oral)