GOING BEYOND 1-WL EXPRESSIVE POWER WITH 1-LAYER GRAPH NEURAL NETWORKS
Authors: Tianjun Yao
Yingxu Wang
Shangsong Liang
Venue: Submitted to ICLR 2023 (2023)
Keywords: graph neural networks
expressivity
memory-efficient

Abstract: Graph neural networks have become the \textit{de facto} standard for representational learning in graphs, and have achieved SOTA in many graph-related tasks such as node classification, graph classification and link prediction. However, it has been shown that the expressive power is equivalent maximally to Weisfeiler-Lehman Test. Recently, there is a line of work aiming to enhance the expressive power of graph neural networks. In this work, we propose a more generalized variant of neural Weisfeiler-Lehman test to enhance structural representation for each node in a graph to uplift the expressive power of any graph neural network. It is shown theoretically our method is strictly more powerful than 1\&2-WL test. The Numerical experiments also demonstrate that our proposed method outperforms the standard GNNs on almost all the benchmark datasets by a large margin in most cases with significantly lower running time and memory consumption compared with other more powerful GNNs. 

Under review as a conference paper at ICLR 2023
GOING BEYOND 1-WL EXPRESSIVE POWER WITH 1-LAYER GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks have become the de facto standard for representational learning in graphs. and have achieved SOTA in many graph-related tasks such as node classification, graph classification and link prediction. However, it has been shown that the expressive power is equivalent maximally to Weisfeiler-Lehmme Test. Recently, there is line of work aiming to enhance the expressive power of graph neural networks. In this work, we propose a more generalized variant neural Weisfeiler-Lehman test to enhance structural representation for each node in a graph to uplift the expressive power of any graph neural network. It shown theoretically our method is strictly more powerful than 1&2-WI 222 test. The Numer- ical experiments also show that our proposed method outperforms the standard GNNs almost all the benchmark datasets by large margin in most cases with significantly lower running time and memory consumption compared with other more powerful GNNs.
INTRODUCTION
Graph-structured data is ubiquitous in many real-world applications ranging from social network analysis Fan et al. (2019), drug discovery Jiang et al. (2020), personalized recommendation He et al. (2020) and bioinformatics Gasteiger al. (2021). In recent years, Graph Neural Networks (GNNs) have seized increasing attention due to their powerful expressiveness and have become dominant approaches for graph-related tasks. Message Passing Graph Neural Networks (MPGNNs) are the most common types of GNNs due to their efficiency and expressivity. MPGNNs can be viewed as a neural version of the WWeisfeiler--ehmme colors are replaced by continuous feature vectors and neural networks are used to aggregate over node neighborhoods Morris et al. (2019). By iteratively aggregating neighboring node features to the center node, MPGNNs learn node representations that encode their local structures and feature information. A graph readout function can be further leveraged to pool a whole- groole representation for downstream tasks such as graph classification.
(1-WI.) algorithm Weisfeiler & Leman (968), where
Despite the success of MPGNNs, it is proved in some recent literatures that the expressive power of MPGNNs is bounded by 1-WL isomorphism test (Morris al. 2019 Xu et al.] (0188), i.e, standard MPGNNs or 1-WL. GNNs cannot distinguish any (sub-)graph structure that 1 1-WL. cannot distinguish such as for any two n-node r-regular graphs, standard MPGNNs will output the same node representation.
Since then, a few works have been proposed to enhance the expressivity of MPGNNs. Methods proposed by (Morris et al., 2019; Chen et al. 2019 Maron et al.) 2019) aim at approximating high-dimensionall WL tests. However, these methods require learning all node tuples, which are computationally expensive and not able to scale well to large-scale graphs. Another line of works augment node features to enhance the expressive power of GNNs. E.g., works proposed by (Loukas) 2019 SSat et al., (021) inject one-hot features or random features to each node of graph, while other works incorporate structural features to enhance expressivity of GNNs such as distance-based features (Zhang& & Chen 2019 Li et al. 2020) and counting features of certain substructures Bourit- sas et al. (2022). More recently. (Zhang & Li 2021 Zhao et al. 2021) propose to leverage subgraph information that cannot be captured by 1- test infer node representations. Concretely, instead of hashing the direct neighborhood information in 1-WL test, these methods hash the subgraph information, and therefore inject additional structural information in the learning process. These

---

Under review as a conference paper at ICLR 2023
methods are able strike balance between effectiveness and running time complexity. However, scalability and memory consumption are still an issue as these methods need to materialize all the subgraphs into GPU memory.
Accordingly, in this paper we tackle the above defects by proposing a lightweight module which is extension of neural Weisfeiler-Lehman test to extract meaningful structural representations, which can be leveraged alone or plug into any MPGNN to enhance its expressive power. Our proposed method generalizes a rooted subtree by encoding multi-hop multi-color rooted subtree, which induces a different message passing function. It is shown theoretically and empirically that our method is strictly more powerful than I&2-WL test with significant reduction in computational complexity and memory consumption with comparable predictive performance or even superior to previous methods.
Our main contributions are summarized as follows:
(1) New methodologies. We develop a more generalized variant of neural WL test, where the message passing function induces multi-hop multi-color rooted subtree instead of rooted subtree. Our proposed methods enjoys high flexibility and can be leveraged alone or equipped with any graph neural network.
(2) Theoretical justification. We show our method provably more expressive than 1-WL GNNs with only 1 iteration of message passing.
(3) High efficiency. Our method be equipped with any base graph neural network, incurring almost no additional memory consumption while boosting the performance of the base GNN significantly.
(4) Superior performance. We conduct extensive experiments in a wide variety of datasets with different tasks. Empirically our approach outperforms all the baseline GNNs by large margin in most cases.
2
PRELIMINARY
We begin by introducing our notations, followed by presenting the concept of WL. test and message passing graph neural network framework.
2.1 NOTATION
graph can be represented as G = (V. E), where V= (vi...., .a......,,, 2n is the node set and & CCVX the edge set. X' {x,, Vu E V} is the node feature matrix and F {Caw Vea. E) denote the edge feature matrix. The k-hop neighborhood of a node C V is the set of nodes whose distance (shortest path) to v is no greater than and is denoted as (u)(U), furthermore
denote Ng. (v) to
be the k-th hop neighbors of node v. Given a set of nodes S C V, the subgraph induced by S is graph that has nodes S and every endpoint of the edges is in S. The k-hop neighborhoods of node constitute an induced subgraph denoted by G.y. We further denote D and A to be the diagonal degree matrix and adjacency matrix of G respectively, and ÅS be the k-hop neighborhood matrix of graph G. Ai) outputs the non-zero entries of the i-th node whose distance to it equals to k.
2.2 WEISFEILER LEHMAN TEST
WL test is family of very successful algorithmic heuristics used graph isomorphism problems. 1-WL test, being the simplest one in the family, works as follows each node is assigned the same color initially, and gets refined in each iteration by aggregating information from their neighbors' states. The refinement stabilizes after a few iterations and the algorithm outputs representation of the graph. Two graphs with different representations are not isomorphic. The test can uniquely identify& large set of graphs up to isomorphism (Babai & Kucera 1979), but there simple examples where the test tragically fails- for instance, two regular graphs with the same number of nodes and same degrees cannot be distinguished by the test. As result, natural extension to 1-WL test is k- WL test which provides a hierarchical testing process by keeping the state of k-tuples of nodes.
2

---

Under review as a conference paper at ICLR 2023
Perform dual message peasing
and concaterate andion feature to eecn node
Mutti Hop
READOUT
Base GNN
Obsain finel representation of node 1 via readour function
Figure 1: An illustration of the working procedure for GNN-M'HC-RYY where the root node is node 1. GNN-MPHC-RR first concatenate the random walk features to every node in the graph, then build multi-hop multi-color rooted subtree (in this case 2-hop 2-color rooted subtree), followed by performing message passing induced by standard rooted subtree and multi-hop multi-color rooted subtree. A readout function is then leveraged to summarize the node representations from the dual message passing procedure to get the final representation of node
2.3 GRAPH NEURAL NETWORKS
In this paper, we focus on message passing GNNs (MPGNNs). For a MPGNN, the goal to learn meaningful node representation h, based iterative aggregation of local network neighborhoods. The 1-th iteration of message passing can be written as:
a = O ((150-1) "ere"""eelll
elu ( 1. UPDATE (n!-")a!!))
(1)
where h denotes the node u's representation time stamp t - cwv is the edge feature of Cuv E. and N(v)) returns the set of neighbors of node v. AGG(1) and UPDATE()) are the aggregation and update functions at time stamp L, respectively. After T time steps, the iterations converge and the final node representation hi can then be summarized with a readout(pooling) function R(o) to extract graph-level representation lgg
hg =R (((LOOEVV))
There is close connection between MPGNN and I-WL test in that they both encode rooted sub- trees, and is not general enough to capture arbitrary patterns in graph. is proved that MPGNN's discriminative power is upper bounded by 1-WL test, and hence cannot distinguish any two n-node r-regular non-isomorphic graphs. Despite subgraph GNN (see definition in the following section) is proposed recently, the running time complexity and memory consumption overhead still issue for large graphs
3 PROPOSED METHOD
In this section, we propose our approach, Multi-Hop Multi-Color GNN (M²HC) which also encodes a rooted subtree structure as 1-WL MPGNNs do. However, by incorporating multi-hop information with different colors assigned to k-hop neighbors Ni((v) of the root node v. M provably go beyond I-WL discriminative power using only 1-layer message passing, therefore both fast and memory efficient. The overall procedure of GNN-M"HC-RW is illustrated in figure
Definition 1. (Rooted Subgraph) Given graph G and a node v, the height-h rooted subgraph g. induced by the nodes (V), i.c. the nodes whose distance to node v is greater than k.
The concept of Rooted Subgraph follows Zhang & Li (2021). Zhang & Li 2021). instead of iter- atively refining node v's representation using Eq. they propose a subgraph- based nested scheme to enhance the expressivity of MPGNNs. Similarly, Zhao et al. (222)) also proposes a rooted sub- graph based approach named Subgraph-1-WZ
The algorithm (Zhang & Li 2021 only runs for iteration, while the subgraph-I 1- WL runs for several iterations just as the standard 1-WL GNNs. We refer these variants of neural WI. test subgraph GNN.
3

---

Under review as a conference paper at ICLR 2023
Heigh=2
Heightm1
Figure 2: An illustration of resulted rooted subgraph and multi-hop multi-color rooted subtree for two non-isomorphic 4-node 2-regular graphs where the root node is node shown in the figure, both height-1 and height-2 rooted subgraph lead to the same representation for node 1. However using a 2-hop 2-color rooted subtree, node receive different representations hence can be distin- guishable.
As rooted subgraph is extracted for every node C independently, node in different context (rooted subgraph induced by different nodes in the graph 9) may receive different representations, which different from standard MPGNN in that node only receive universal representation. The discriminative power of subgraph GNN is enhanced due to the ability of each node being able aware of its context, i.e. the rooted subgraph induced by different nodes in the graph. It is guaranteed that subgraph GNN is able to exceed the expressive power of 1&2-WL test Zhao et al. (202T): Zhang & Li (202T).
Definition 2. (Multi-hop multi-color rooted subtree) For a K-hop rooted subgraph G k-hop neighborhood Ne(v)) in G is extracted and directly connected to the root node v and assigned with unique color ct. where k E [1, K].
an example to illustrates the resulting rooted subgraph and Multi Hop Multi-Cole rooted HC) for two 4-node 2-regular non-isormorphic graphs. Although the encoded rooted subgraph cannot distinguish the two graphs, MCHC is able to discriminate the structural disparity even if the node features remain the same. Hence, instead of using direct neighbors in WL test, we propose to leverage M HC as a variant that could lead to the following message passing and update function:
Viue m = (GG (f I [L, VVuue Aslo))))
(3)
h (
Here, fo(o) is the coloring function for the k-hop neighborhoods and u is a k-hop neighbor of node By directly transferring HC into message passing function and run iteratively, the model expressivity will get uplifted, however we aim for a memory efficient and fast approach. As we will later prove that I-iteration of Mº is sufficient to go beyond 1-WI. expressive power. Our message passing function for a K-hop MC is therefore simplified as:
(ALx) | E [1, (1,x7))
H =
(4)
where g(o) is the node readout function to summarize information from k E [1, K] hop neighbor- hoods get node representations H E XNF where F' is the hidden dimensions of node E V. The graph representation R( R(H) can be further obtained with a readout function R. In all the exper- iments, we set g(o) and R(o) be SUM or MEAN operators. Although being an extended version of rooted subtree, MC resembles subgraph GNN in that, thanks to the introduction of coloring function fs))), the same node can also obtain different representation for different root node as the relative distance to a different root node is subject to change, and hence by exploiting Ås, the subgraph structure is implicitly captured. Although being more expressive than rooted subtree structure, M2HC is less discriminative than subgraph GNN. In figure 3 we illustrate a failure case where subgraph GNN is able to capture the structural difference of the non-isomorphic graphs
4

---

Under review as a conference paper at ICLR 2023
Reoned rubgraph for sode
Atternn partects for MPAC
Adhen patter sulgraph
Figure 3: A failure case where subgraph GNN can distinguish the structrual difference while MC cannot differntiate it. The figure also illustrate the attentional pattern induced by subgraph GNN and MCHC,blue and orange dotted dash line denote different coloring functions. As shown in the figure, subgraph GNN and M2HC lead to different attention patterns.
while HC will output the same node representation and fail discriminate them. In the following discussion, we treat message passing functions as a particular form of attention model, and provide an intuitive explanation of the expressive power possessed by MCHC and subgraph GNN. As shown in figure 3] node can attend to its K- K-hop neighboring nodes, and hence for subgraph GNN, it follows bidirectional pairwise attention pattern while MCHC follows uni-directional hub-spoke capture its local substructure, therefore with injective readout function, subgraph GNN possess stronger expressive power than MC
pattern, all the nodes in the subgraph
To mitigate this weakness, we leverage scalable node feature augmentation method to make every node to be aware of its local substructure. We may resort to random features or one-hot features such those in (Sato et al. [202] Loukas 2019). Although being simple and fast, adding random features would hurt the generalization performance, while one-hot features only adapt to transductive setting. Inspired by previous works positional encoding (Dwivedi al. 2021 You et al. 2019),, adopt 1-step random walk self-landing probability of node v to summarise w's local graph structure as random walk can capture the status of given node in the network. For instance, hub node in the network will reach to itself much often than other nodes in a graph. Furthermore, A local change in the connection pattern will influence random walk dynamics, leading lald-nanding statistics (Lovász [993). We denote R = D A as the random walk matrix, the L-step C RR. Let RW denote the
different pattern of
self landing probability vector for node v equals to (Row: R R R2. self-landing probability matrix, the message passing function in matrix form for MC is:
H (= (A&X') ke (1, where X' CONCAT RW)
(5)
We term the model applying Eq. as M2HC-RW,am in all the experiments fa(o) is set be 2-layer or 3-layer MLP due to the universal approximation theorem (Hornik et al. 1989 Hornik 1991) and g(o) to be SUM or MEAN pooling functions.
Efficient Implementation. Here we propose an efficient implementation for A as the main com- plexity of Eq. 5 stems from it.
Fact. The (i. th entry of A counts the number of walk of length where the start and end vertices are i and j respectively.
Lemma Let du be the distance between nodes and j. Then there exists a walk of length de 2c between and j for a simple graph where E (0, 1, ......
Using Lemma 1, we can come to the conclusion that A + Å the non-zero entries Ax s.t. dij while A dij 2c. However, can calculate Aş using A and A1-1,,A-2.-..
efficiently using Eq. 6
k-
M 2 Σ
A.
[A*] 0, (i. E M
5

---

Under review as a conference paper at ICLR 2023
= 1 2 x
Here, Σ1-1 A, is binary matrix where non-zero entries (v, w) implies that <= dew <= 1, and 7()) returns a list of all the non-zero entries for Σ1 Aj. The second line of the equation sets [A4], Jsy to zero where the indices (i.j) is resulted from M and therefore now A only contains the non-zero elements i,j where d,j k. The last line in Eq 6 outputs A₁: as the binarized version [
1, yd.y = k. The iterative realization of A is efficient as the computation only involves sparse matrix multiplication, addition and fancy indexing.
of A where
DISCUSSIONS
In this section, we theoretically analyze the expressivity our proposed method, followed by a discussion of the computational complexity and memory requirement of MCHC-RW, finally We compare and contrast our method with other related works.
4.1 THEORETICAL ANALYSIS
In this subsection, we theoretically analyze the expressive power of HCHC-RW.
Theorem Subgraph GNN is strictly more powerful than &
Theorem can be directly obtained from Theorem of et al. (2021) and Theorem / from Zhang & Li (022). Although the proof sketch is not the quite the same, they both prove that subgraph GNN is more discriminative than I-WL graph isormorphism test. As the discriminative power of 2-WL equivalent to M- et 2019), subgraph GNN is proved be more powerful than &&2- WL. Next, we establish the connection between M²HC-RW RW and subgraph GNN in terms of their expressive power.
Theorem HC-RR at least as equivalent to the expressive power of subgraph GNN if the following conditions hold:
1. The coloring function f(o) readout function g(o) and graph readout function R. in Eq. should be injective.
2. For a K-hop M HC and L-step random walk probability matrix RW, should be sufficiently large to capture the structural information.
direct corollary derived from theorem
and 2 is:
Corollary 2.1 MHHC-RW is strictly more powerful than I 1&2-WL.
Theorem is proved by observing that incorporating send-lgnding probabilities augment node fea- tures could help resolve the expressivity issues incurred by hub-spoke attention pattern of HC We also provide toy example to illustrate that M2HC can successfully discriminate some cases where subgraph GNN fails to detect. Due to the exponential growth of K-hop neighbors, K should be set too large, which might require more expressive model extract meaningful representa- tions Loukas (2019), however K should not be too small neither it will lose useful information. K typically set to 3 or in the experiments to strike a balance between model complexity and predictive performance.
Theorem Let = {0, 1|nxa be any permutation matrix.if we define T be an alias operator for M HC-RWthhen T(A T (PAPT PX)...e M-CC-WW permutation invariant.
As HCH is experimented under the setting of graph classification. the permutation invariance property guarantees that for any node permutation P. the graph representation remains the same, hence is positive for the graph classification task.

---

Under review as a conference paper at ICLR 2023
4.2 COMPLEXITY ANALYSIS
As there are two stages for our approach, we analyze the running time complexity separately in the this section.
1. Preprocessing. In this stage, Ag and the self- probability matrix RW require some pre-computation. However, both of them can be computed efficiently. First, to compute Ag. we only need to compute A = A (R)-1), hence bottom-up dynamic programming approach only lead OKK m) computational complexity for a K-hop M&HC-RW and m is the number of non-zero entries for adjacency matrix A. Similarly, we need to precompute R. R2², Rt :.... R2 for L-step RW probability matrix,
can use similar approach leading to O(L m) running time complexity. Lastly, we can also precompute A for a sparse matrix G, the time complexity is O(mF) where F is the feature dimension of X. For sparse graph, as K << m, << m and F << m, the time complexity of the preprocessing stage is O(IVI).
2. Training and Inference. The computation for training and inference is fast and memory- efficient once the preprocessing stage finished. As fo(o) in Eq. 5 is a 2-layer or 3-layer MLP, the computational complexity is O(B))FH) where [B] is the batch size, F denotes the feature dimensions and H denotes the hidden dimensions of (x)).. MHHC-RW can be faster than 1-WL MPGNNs while being more expressive. Notably for Nested GNN Zhang & Li (2021), the computational complexity is O h))HH, where is the height of extracted rooted subgraph which is typically 4 5, and d is the average node degree. As subgraph GNN incurs an additional memory overhead of hd, HCHC-RW can consume 10x-50x less memory than subgraph GNN assuming d ranges between 3 to 10.
4.3 RELATED WORK
Detailed discussion on the related works is shown in appendix A.3
EXPERIMENTS
The following research questions guide the remainder of the paper: (Q1) Can MCHC-RW go beyond 1-WL expressive power? (Q2) Is M2HC-RW able to outperform 1-WL MPGNNs real-world datasets? (Q3) How does HCHC-RW perform in large-scale benchmark graph datasets? (Q4) How much training time and memory consumption do M*HC-RW incur?
We make of Pytorch Geometric (Fey & Lenssen 2019) to implement our proposed framework, and Pytorch Lightning that provides higher-level abstraction built upon Py Torch (Paszke et al. 2019) for efficient model training and inference. Our code is available hhttps:/ com/
reywqua/ III.uuaIICRO223..00 222333223_223
5.1 DATASETS
To answer Q1, we make use of the following synthetic datasets to examine if HC- can exceed 1&2- expressive power. i) LCC(X) SSto al. (202T), which contains no-node 3-regular random graphs for multi-label node classification problem, the class label for node v is the local clustering coefficient of node v. Both training set and test set consist of 1,000 graphs. ii) TRI(X) [Sato et al. (20T)) which also consists of 2,000 20-node 3-regular random graphs split by half for training and testing, the goal is to predict if two neighboring nodes are adjacent to each other. iii) EXP Abboud et al. (2020) contains 600 pairs of 1&2-WI WL failed graphs that are split into two classes where each graph of a pair is assigned to two different classes. iv) Graphlet counting Abboud et al. (2020). The goal is to count four substructures's 's number in random graphs.namele 3-star, traingle, trinee and 4-cycle. For TRI(X) and LCC(X) datasets, the evaluation metric is ROC-AUC as the label dis- tribution is skewed. For EXP dataset, the evaluation metric is Accuracy, and for graphlet counting dataset, MAE is adopted. To answer Q2, We adopt ENZYMES, DD, PROTEINS, MUTAG, NCII and BZR from TUDataset Morris et al. (2020) which is self-contained in Pytorch Geometric Fey & Lenssen (2019). We adopt Accuracy as the evaluation metric. To answer Q3, ogb-molhiv and ogb- molpcha from Open Graph Benchmark datasets Hu et al. 2020) and zinc- are used to verify the
7

---

Under review as a conference paper at ICLR 2023
Table 2: Results on counting 4 different substructures, the evaluation metric is Mcan Square Error. Truncation is performed when test error drops below 1,0E-4.
Method
3-Star
TTiannle
Tr..
4-Cycle
GCN
1.0E-4
2.43E-1
1,42E-1
1.14E-1
GAT
1.0E-4
2.47E-1
1,44E-1
1.12E-1
GIN
1.0E-4
2.06E-1
1,18E-1
1.21E-1
PPGN
1.0E-4
1.0E-4
2.61E-4
3.30E-4
M'HC
1.0E-4
8.61E-4
2.20E-3
5,83E-3
GIN-M'HC-RW
1.0E-4
8.76E-4
2.25E-3
5,27E-3
HC-R-
1.0E-4
1.0E-4
1.0E-4
1.0E-4
expressive power of the proposed method. The ogh-molhiv dataset contains 41K small molecules, the task of which is to classify whether molecule exhibits HIV virus or not. ROC-AUC is the stan- dard evaluation metric for this dataset. The ogbg-mo molppca dataset contains 438K molecules with 128 classification tasks. The evaluation metric is Average Precision over all the classification tasks. zinc- 12k (Sterling& & Irwin 2015
et al. 2018 Dwivedi et al. 2020) dataset contains 12K molecule graphs to regress molecular property known constrained solubility. Following Dwivedi et al. (020)) we adopt Mean Absolute Error(MAE) as evaluation metric.
5.2 EXPERIMENT RESULTS
For Q1, as illustrated in table HCHC-RW able to achieve 99.7% and 1.0 in LCC(X) and TRI(X) respectively. where GIN and GCN can only achieve 50% in terms of ROC- AUC score. For EXP dataset, M'HC-RW achieves 99.8% accuracy while 1-WL GNNs only achieves 50%. This im- plies that M'HC-RW exceeds 1-WL discriminative power and can discriminate the substructures that GIN and GCN do better than random guess. For the graphlet counting dataset, the experiment result is shown in table 2 MCHC-RW achieves much lower MAE compared with 1-WL GNNs. Sec- ond, equipped with M GIN and PPGN Maron et al.
Table 1:
Results on
LCC(X),TRI(X) and EXP. ROC- AUC is adopted as the evaluation metric for LCC(X) and TRI(X), and Accuracy(%) is used for EXP.
Method
LCC(X)
TRI(X)
EXP
GCN
50%
50%
50%
GIN
50%
50%
50%
M'HC-RW
99.7%
100%
99.8%
(2019) demonstrate higher expressive power, i.e., the result- ing MAF is significantly less than the models without MCHC- RW. This also implies that HC can equipped with more advanced models such as PPGN, to uplift their expressivity. Finally, PPGN with M HC-RW achieves the best MAE error consistently in all of the four substructures.
To answer Q2, first we can see that I-layer MCHC-RW can outperform all the 1-WL GNNs in almost all the datasets as shown table 3 in most cases by a large margin. We also test GNN-RW to verify the improved expressive power doesn't I come from injecting random-wald walk positional features- although the accuracy does improve a little bit in some datasets, GNN-M GNN-M2HC-RWV improves much more significantly. Finally 1-WL GNNs, together with HCHC-RW uplifts the model expressivity in almost all datasets. This implies that by encoding a rooted subtree and multi-hop multi-color rooted subtree in the message passing procedure, the model can leverage both inductive bias extract more meaningful representations. For all the datasets except MUTAG, the best performing model is achieved by GNN-M HCHC-RW.
To answer Q3, we adopt GIN+ Virtual (ooeeG"") as the base GNN method in GNN-M*HC-RW for ogbg-molhit and ogbg-molj molpeba, we can see that by equipping with MCHC-RW module. GIN discriminative power has been improved significantly and consistently in both datasets- from 77.07% to 78.21% %% in ogb-molhiv and 26.86% to 27.9 37.92% in egbg-molpche as illustrated in table 5 GIN" MOHC-RW is even comparable with or outperform some heavily-tuned leading methods. Finally, our method is comparable with subgraph GNN methods, i.e., Nested GNN Zhang & Li (2021) and GNN-AK Zhao et al. (202I). which is also consistent with our theorem terms of model expressivity. Finally we test GNN and GNN-M on zinc- 12k dataset which a large scale molecular benchmark. We GCN,GIN, GraphSage and PPGN the bascline methods and use only node label features, without leveraging any edge features to verify whether GNN-M2 can outperform the base GNN methods. As demonstrated in table 6, GNN-MPHC-RW outperforms
8

---

Under review as a conference paper at ICLR 2023
Table 3: Graph classification results on TU datasets in terms of Accuracy($5) (%) and one standard deviation, we use bold to highlight the best performing method.
D&D
PROTEINS
MUTAG
NCI1
BZR
ENZYMES
GCN
68.64444.7
69.42+4.1
74.73+6.8
64.92+1.1
80.93+5.1
24.21+3.7
GCN-RW
69.241:2.1
69.4711.4
70.7219.1
65.742.2
82.85:4.4
25.2916..0
GCN-M2HC-RE
7,26-5.2
74,5+188
85,3+10.2
73.38+1.7
81,23+3.9
36.66+7.1
Graphsage
69.79++.44
68,2+3.2
72.38+55.4
68.34+1.9
81.1=5.6
25.1+660
Graphsage-RW
70.12:33.5
69.613.11
75.98115.8
1..
82.77:33.6
23.33:66.
Graphsage- GraphsageM''CC-RY HC-
73.71=2.51
73.7+2.2
86.248.1
7..06+1.2
82.78+4.0
38.19+3.9
GIN
70,9814.5
70.3+3.1
87.8917.9
71.61=2.0
85.913.6
32.01
GIN-RW
1..85
69.5413.00
85.8411.2
71.811
86.32:14.4
31.6614.7
GIN-M'S HCW-W
72.26:t3.3
74.81111
84,516.53
74.17=1.7
87.5114.88
38,7513.6
M'HC-RW
73.41+3.88
73.224-2.6
84.9948.6
75.29
83.61+4.4
34.54+55.8
MAX IMPROVEMENT
10.14%
9.67%
19.22%
13.03%
2.07%
52.76%
Table Normalized running time and memory overhead for various methods. Our approach incurs significantly less memory usage.
Zine-128
Method
Run Time(S/Epoch) Memory(MB)
GIN
GIN-AK
1.57
15.41
GIN-AK*-S(RE
2.08
15.008
GIN-AK"-S(R-s
2
11.23
GIN-AK- -
1.8
3.16
GIN-M&HC-RW
1.24
1.04
all four GNN variants. PPGN-M'HC-RW achieves the best MAE across all the methods. Detailed experiment results are illustrated appendix A..
To answer Q4, we compare GNN-M with GIN-AK on zinc- 12k in terms of memory usage and per epoch running time. As the experiment setting different, we measure normalized running time and memory overhead where the time and memory incurred by GIN equals to 1. The experi- ment result shown in table[4] We should also note that GIN-AK ZZao al. (021) I different with GIN-AK in that GIN-AK* further leverages context encoding and distance-to to-centroid encoding in each layer to improve the model capacity, however the memory cost mainly arises from indepen- dently rooted subgraph extraction for each node in the graph, hence the memory overhead would be similar to GNN-AK. As we can see in table add HCHC-RW on GIN is nearly memory-free the additional memory consumption stems from the model parameters of coloring function fo) in Eq. [ As AX can be precomputed, the training and inference procedure is orthogonal to the graph structure information, hence is also fast. GIN-M*HC-RW consumes only 1/15 memory over- head compared with GIN-AK*. Although GIN-AK*-S introduces sampling operation, the training becomes slower as the sampling operation introduces more computation complexity to avoid redun- dant rooted subgraphs, and the inference stage, without using subgraph sampling, is still memory -S(=11) and is 25.6% inefficient.nn terms of speed, GIN-M2HC-RW is 43% faster than GIN-AK"-S(R=1) faster than GIN-AK".
CONCLUSION
In this paper we develop MCHC-RW, more generalized variant of neural Weisfeiler-Lehhmnn test to uplift GNN's representative power. M2HC-RW is fast, flexible and memory efficient. Further- more, it is provably more expressive than I-WL graph isomorphism testing using only iteration of message passing. Compared with other more powerful GNNs, M'HC-RW requires significantly less memory overhead, and can be applied to large-scale graphs. HCHC-RW can also be deployed to low-resource device for training and inference due to its low computational complexity and memory efficiency. In the future, we seek to incorporate attention mechanism into M2HC-RD RW and make compatible with edge attributes.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01179, 2020.
Sami Abu-EI-Haija, Bryan Perozz, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference machine learn- ing, pp. 21-29. PMLR, 2019.
László Babai and Ludik Kucera. Canonical labelling of graphs in linear average time. In 20th Annual Symposium on Foundations of Computer Science (sfes 1979), pp. 39-46. IEEE, 1979.
Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. arXiv preprint wrXiv:1912.06055 2019.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00993 2020.
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:21 10.0787. 2021.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pp. 417-426, 2019.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.024:3 022488, 2019.
Johannes Gasteiger, Florian Becker, and Stephan Günnemann. Gemnet: Universal directional graph neural networks for molecules. Advances in Neural Information Processing Systems, 34:6790- 6802, 2021.
Rafael
Jennifer N Wei, David Duvenaud, José Miguel Hernández-Lobato, Benjamín Sánchez-Lengeling, Dennis Sheberla, Jorge Iparaaree,,r Timothy D Hirzel, Ryan P Adams, and Alán Aspuru-Guzik. Automatic chemical design using data-driven contin- uous representation of molecules. ACS central science, 4(2):268 226, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
Xiangnan Hc, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. Proceedings of the 43rd International ACM SIGIR conference research and development in Information Retrieval, pp. 639-648, 2020.
Kurt Horiik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4 (2):251-257 1991.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Newral networks, 2(5):359-366, 1989.
Weihua Hu, Matthias Fey, Marinka Zitnkk Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 18-2218-..,, 2020.
10

---

Under review as a conference paper at ICLR 2023
Mingjian Jiang, Zhen Li, Shugang Zhang, Shuang Wang, Xiaofeng Wang. Qing Yuan, and Zhiqiang Wei. Drug- target affinity prediction using graph neural network and contact maps. RSC advances, 10(35):20001-20711 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprini arXiv: 1609.02977 2016.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance seroding-desigeee provably
more powerful gnns for structural representation learning. arXiv preprint SXXi:2009.001442, 2020.
Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint arXiv:1907.03199 2019.
László Lovász. Random walks on graphs. Combinatorics, Paul erdos is eighty, 2(1-46):4, 1993.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pp.
2019.
Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. arXiv preprint arXiv:2007.08663 2020.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130: 105-1992 2020.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. Global attention improves graph networks gener- alization. arXiv preprint arXiv:2006. 20000000007746 2020.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. Proceedings of the 202/ SIAM International Conference on Data Mining (SDM), pp. 313-333333 SIAM, 2021.
Teague Sterling and John J Irwin. Zinc 15-lid discovery for everyone. Journal of chemical information and modeling, 55(11):2324-2337 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Boris Weisfeiler and Andrei Leman. The reduction of graph to canonical form and the algebra which appears therein. NTI, Series, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 1rXiv:1810.. 00826, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pp. 5453-5462. PMLR, 20.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International conference on machine learning, pp. 7134-7143. PMLR, 2019.
Jiaxuan You. Jonathan M neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Rex Ying, and Jure Leskovec. awwae graph
11

---

Under review as a conference paper at ICLR 2023
Muhan Zhang and Yixin Chen. Inductive matrix completion based graph neural networks. arXiv preprint arXiv: 1900. 2019.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Process- ing Systems, 34:15734-15747, 2021.
Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. From stars to subgraphs: Uplifting any gnn with local structure awareness. arXiv preprint arXiv:2 10.03753, 2021.
A APPENDIX
A.1 EXPERIMENT SETTING
For the synthetic datasets, we directly verify the model performance of RW on LCC(X), TRI(X) and EXP. The baseline methods are Gipj & Welling (216)) and GIN Xu et al. (201 Sa). For graphlet counting dataset, GCN,GAT GEN Veličković et al. (2017). Graphsage, PPGN are used as the baseline methods. For GIN and PPGN, M is also equipped to each of these methods to ver- ify if there is uplift for the model expressivity. Besides, M²HC-RW is also experimented alone. All methods trained for 100 epochs. The best performing model at validation stage with specified evaluation metric is used for test dataset.
For the TUDatasets, we adopt GCN, GraphSage Hamilton GraphoaggHHmmilon et al. (2017) and GIN as the base methods. To demonstrate the uplifted power is not solely stemming from random-walk positional features, we also evaluate the performance of GCN-RW, GraphSage-RW and GIN-RW. Two variants of our proposed method are experimented, namely MWHC-RW and GNN-M HC--.. GNN-MMHC--R leverages both MºHC-RW and base GNN method, and concatenates the graph-level representa- tions from both models for the final classification. For all GNN models including GNN-M*HC-RW. the message passing layers in {2, 3, 4, 5] is searched, and the hidden dimensions of {16, 32} is searched. For M'HC-RW, 3-hop with 10-step random walk is used uniformly in all the experi- ments without any hyperparameter search. All models are trained uniformly for 150 epochs with 32 batch-size. We adopt the 10-fold cross validation method to ensure fair comparison. For each fold, we record the test accuracy according to the best validation performance and report the average accuracy across all 10 folds. It also noteworthy that ensure fair comparison, Jumping Knowl- edge Xu et al. (2088)) is not incorporated in GIN and all other methods, which is leveraged in Xu al. (2018a) enhance GIN's model capacity.
We then turn to large scale datasets to verify the performance of GNN-M For ogb-molhiv and ogbg-molpeba, we use GIN HC---, and compare with other advanced GNN methods, where GIN" refers to Virtul Node. A 1-layer or 2-layer K-hop L-step MCHC- RW used, where K is set to 3 and I. equals to 20. For zinc- 12k dataset, we ignore edge features and only leverage node features to facilitate the comparison between MCHC-RW and other baseline methods, namely GCN, Graphsage, GIN and PPGN. Finally, we compare base GNN methods with and without M2 HC module to verify if equipped with proposed method enhance the expressivity of base GNNs.
HC-N-M HC-RW and MCHC-RW.
A.2 EXPERIMENT RESULTS ON OGBG AND ZINC- 12K DATASETS
Table 5 illustrates the experimental results for ogbg-molhiv and ogbg-molpcha. As we can see, by equipping with MºHC-RW module, GIN*'s discriminative power has been improved significantly and consistently in both datasets- from 77.07% to 78.21% in ogb-molhiv and 26.86% to 27.92% in oglg-molpcba. Our approach is also comparable with subgraph GNN methods, i.c., Nested GNN Zhang & Li (202T) and GNN-AK et al. (202T) which is consistent with theorem in terms of model expressivity.
Table 6 shows the experimental result for zine-12k dataset. As demonstrated in the table, GNN- M2HC-RW RW outperforms all four GNN variants. PPGN-M2HC-RW achieves the best MAE across all the methods.
12

---

Under review as a conference paper at ICLR 2023
Table 5: Graph classification result oghg-molhiy and ogbg-molpcha in terms of roc-auc and
average precision
ogbg-molhiv
ogbg-molpcha Test
Method
Test
CCN
75.99:1..19
PNA
79.05+1.32
28.3
DGN
79.70=L0.97
28.85-10.3
DeeperGCN
27.81+0038
CIN
80,94
GIN
17.07=
27.03:1.223
Nested-GIN
78.34
28.32:40441
GIN-AK
78.29
27.40=
GIN-M-HC-RW
78.214:1.03
27.92
Table 6: Test results for zinc-12k dataset. bold indicates the best performing model in the test dataset. Only node feature leveraged, the edge feature leveraged even when it is available.
Method
ZINC-12k(MAR
GCN
0.31710.012
GCN-MPHC-RW
0,26+-0.004
GIN
0.31610.003
GIN-MPHC-RW
0.266
SAGE
0.26940.004
SAGE-M'HC-RW
0.247=0.004
PPGN
0.306+000051
PPGN-MPHC-RW
0.182+
A.3 RELATED WORK
In this section, we compare and contrast our approach with previous relevant works. As the expres- sivity of standard message passing GNNs, e.g. GCN and GIN is upper bounded by 1-WL graph isomorphism testing, fruitful line of works has been proposed aligning to k-WL test. Although the expressivity of these methods get uplifted with theoretical guarantee, most of them lacks an im- portant feature contributing to the recent success of GNNs: the locality of computations. Therefore, they hold more theoretical values than practical availability. However, our approach guarantees to surpass 1- I-L expressiviy without losing the benefit of localized computations.
In Zhang & Li (202T); Zhao et al. (2021). the authors propose variant of 1-WL test: instead of hash the direct neighbors a given node, a rooted subgraph utilized for representation refinement. Although these approaches(subgraph GNNs) enjoy theoretical guarantee to surpass the expressivity of 1-WL test and preserves locality of computation, it requires expensive memory consumption as an independent rooted subgraph needs to be extracted for each node in the graph. Thanks to this operation, each node is able to receive different representations specific to the node-induced rooted subgraph, which is different 1-WL GNNs where node calculates universal representation based on the rooted subtree. MC inherits the advantage from subgraph GNNs that a node get localized representation based on the root node u and the distance v. MCHC also adopts the idea of subgraph pooling from subgraph GNNs, i.e. the representation of a root node is obtained by pooling the multi-hop multi-color rooted subtree instead of calculating node representation in layer-by-layer regime in 1-WL. GNNs. Due to the adopt of A and precomputation of A MC is able to capture the notion of rooted subgraph implicitly without the need of rooted subgraph extraction, hence is significantly memory efficient and fast in both training and inference stage. Although MCHC is less expressive than subgraph GNNs due to its hub-spoke attention pattern, by adding random-wart self-landing probability as auxiliary feature, M2HC-RW is guaranteed to be as least expressive as subgraph GNNs. Another difference is that subgraph GNNs encode rooted subgraph the neural WL test, while GNN-M HAMPHC-RW leverages both rooted subtree and rooted multi-hop multi-color subtree to calculate the node representation, hence GNN-MPHC-RW can be
13

---

Under review as a conference paper at ICLR 2023
considered as an ensemble method where standard 1-WL test and more generalized version of 1-WL test are both leveraged.
Recent works propose provably enhance the expressivity of GNNs by augmenting node features with random feature or auxiliary coloring,Sato et al. (202)); Loukas (201)); Abboud et al. (2020); Puny al. (2020); Dasoulas al. (2019). although being scalable and easy implement, these approaches may not preserve permutation invariant property, thus would hurt the generalization per- formance outside of the training set. However, leveraging random-walk features as augmentation to MC doesn't t hurt the generalization performance as it is provably permutation invariant. Instead, ID-GNNYou et al. (202T) admits node coloring using different weight matrices, which is similar to the coloring function in our work to tag node colors. ID-GNN still uses standard 1-WL test, leading to a rooted subtree structure, the extra discriminative power stems from coloring the iden- tity node. Meanwhile, we propose new variant of 1-WI. test by hashing multi-hop multi-color rooted subtree. With I-layer message passing function, M2HC-RW is guaranteed to go beyond 1-WL expressivity thanks to the localized node representation and pooling operation. Another line of works resort to graph positional encoding to break the limit of 1-WL expressive power by inform- ing the localized substructure of arbitrary nodes in graphDwivedi et al. (2020) 202I You et al. (219).. unlike many previous works that inject positional encodings in 1-WL GNNs, we leverage positional encoding in our proposed multi-hop multi-color rooted subtree, leading to several advan- tages in uplifting the model expressivity: i) The view of each node is confined to rooted node e in MCHC, due to the hub-spoke attention flow, the internal connection pattern induced by non-root nodes are ignored which may lead to could capture the structural disparity therefore enrich the node representations. ii) Graph positional encoding is not restricted to a single M2HC and can capture expected statistics over all the MC induced by its neighboring nodes, hence can be viewed as context encodings. iii) node's 's represen- tation conditions on both global-level positional encoding and local-level distance information (via coloring funtion (o), leading to higher-quality representations. iv) The random- malk features is permutation invariant, therefore won't 't hurt the generalization performance outside of training set.
the employee of graph positional encoding
Recent work also proposes to use distance features to uplift GNN's expressivity et al. (2020), where a distance vector w.r.t the target node set is calculated for each node as its additional feature. Our approach is compatible with distance- -baed features due to the adoption of coloring function fo) Similar to our framework, Nikolentzos et al. (2020); Hlbu-El-Haija al. (019) also lever- ages multi-hop neighborhood to perform higher-order message passing. However, MixHor/Auu EII- Haija et al. 2019)) directly utilizes A in the message passing function, resulting in the entanglement of information from multi-hop neighborhood to the central node. While our framework leverages
As to disentangle the information from multi-hop neighborhoods to the root node, leading to a hub- spoke multi-color attention pattern. Nikolentzos et al. (2020) directly utilizes k-hop neighbors in the aggregation function instead of direct neighbors. Both Nikolentzos et al. (2020):
et al.) (2019) incorporate multi-hop neighborhood information into the message passing function and run for several iterations. However, MC extends the rooted subtree in WL test and is provably more expressive than 1-WL GNNs with only iteration.
A.4 PROOF OF THEOREM 2
We consider two graphs g and g², and select two nodes i1 E Gl and D2 E G2. For the extracted height-h rooted subgraph bh and 9h, let Q denotes the number of nodes in Th whose distance to root node U1 equals to h, similarly for Qt We consider the first case that (Q), Q2 ...... ... Q * (Qh Po..... . Q²,,, which means that at least one of the element Q! # Q as the topology of the two rooted subgraphs Th and Gh is not the same, the resulted representation from subgraph GNN for en and U2 will not be the same. Similarly, as the coloring function and readout function in M is injective, the node representation for U1 and tn will also be different. Consider another case that {Q',, ........ is different, figure 3 illustrates one such scenario for Gh and 9% where h = 2. Due to the bidi- rectional pairwise attention, subgraph GNN is able to capture the difference and generate different representations for U1 and U2 yet MC cannot distinguish the difference due to its unidirectional hub-spoke attention. However, with random walk features of sufficient steps, HCC can still be aware of the structural disparity thanks to the node feature augmentation. Finally, we consider the case where 9% is structurally identical to Gh hence for subgraph GNN the representation for vn and
Qt, 2
(Qt, v. t
... Qh }. howeeer the internal structure for Gh, and g
14

---

Under review as a conference paper at ICLR 2023
22 is identical, but is different for MC by incorporating random walk features every node in the graph can be aware of global structural disparity. Figure 4 demonstrates one such scenario where and leads to the same rooted subgraph hence the same representation using subgraph GNN while receiving different representation using M²HC-RW, This also stresses the advantage of approach that the receptive field of each node E 9 is enlarged given sufficient steps of random walk.
Left fgure and right fgure icads lo the same height-2 2 rooted subgraph for node Henoe the node representation ootained from subgraph GNN would be idenicall for node 1, However, the repe reprosentation for node pttained from our propased mathod would be difforent for the two Rggues do node is abie to aware the substructure disparty incurred by node 13.
"
Figure 4: One scenario where node in G' and G² is able capture the structural disparity with M'HC-RW, but not with subgraph GNN the resulted height-2 rooted subgraphs for node in the two figures are identical.
A.5 PROOF OF THEOREM
Let R=AD-1 denote the random walk matrix and RW [diag( R), diag (R²) ...... diag (R*)] be the L-step self-landing probability matrix. diag(o) is operator that takes in matrix and return a diagonal column vector. Given an arbitrary permutation matrix / = {0, 1,=xn, we need to prove that T(A, X) (PAPT, PX). where T the MCHC-RW operator and X is the input that consists of node features and self-landin random walk features RW. We expand T and get:
H - (f (Aw(X,
(7)
(f ([Axxx [diag (r) ddaag (r-2ALA2) ..... diag (r~*AAA*)
Eq. 7 we abuse X the node feature matrix, the input concatenation of node feature matrix X and L-step self-landing probability matrix RW. K denote the height of the HCHC-RW,
ie. K-hop MCHC-RW. For simplicity, we assume a r-regular graph, hence AD-1 -1 transformation of permutation matrix have:
With
H = g (f PT PX,, (TNPPT)))
9 (f [PAxX, As [diag 11- PAP4) PAPH) diag (v- - PA2 ....,diag (r- pp
pppppp PAL pT)) p²))
= g (ffx ([PAxX, PAp [diag (T-AAPT) diag (r 2A2pTT diag (A"AA'TT)]]
= g ff PAxx (diag (r-1 (T-IPAAAPT) diag (T=PPAAAPPT) ,..,, diag (r-b A-AAAAA-PT)
Clearly, PÁO X is row row-permutation of Å with injective function f(o) and injective read- out function g(o). 9 (fth (Axx)) o (1 (PΛ+X))) holds true. Next, we compare diag (r- (nA')) with diag (A-AAAL'
As diag (AT return permutation of diag (AgAA) without changing element values, and this holds true for all the 1 E [1, T], hence PRW pT returns row-permutation of RW, and per-
15

---

Under review as a conference paper at ICLR 2023
mutation invariance property also holds for RW. Based on the two observations, come to the conclusion that MCHC-RW permutation invariant.
16


Reviews:
[{"review_id": "pHnQSw24Ki9", "reviewer": "Reviewer_Znxn", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a GNN design that directly aggregates the multi-hop neighbors by assigning the node features based on the different hop numbers. The explicit node coloring augments the message passing process and thus enables the model to differentiate some non-isomorphic subgraphs that a regular 1-WL will fail to distinguish. In addition, this work proposes a feature augmentation scheme by using the landing probability of long random walks as the additional node features. The RW features helps expand the receptive field of the GNN and further improves the model expressive power. The expressive power is analyzed against 1- and 2-WL tests. Experiments on both synthetic and real-world datasets show performance gains on accuracy and memory consumption compared with the full graph-based GNNs. ", "summary_of_the_review": "In summary, I think the paper is below the bar of acceptance at its current stage. I encourage the authors to improve the theoretical soundness and make the SOTA comparison more complete. ", "strength_and_weaknesses": "## Strengths\n\n+ The paper is clearly written and easy to follow. \n+ The overall design is reasonable. Explicit node coloring is somewhat similar to the distance-encoding trick known to the community. The RW-based feature augmentation is a reasonable way to enlarge the receptive field without introducing more message passing steps in the GNN (while at additional cost of preprocessing)\n+ Extensive experiments have been performed on both synthetic and real-world datasets. \n\n\n## Weaknesses\n\n- The description about \"subgraph GNN\" is a bit confusing. First, a closely related work, SHADOW-GNN [a], is missing. SHADOW-GNN is a recently proposed subgraph GNN for node-level and link-level tasks. It also serves as the backbone architecture for Zhang & Li (2021) and also provably achieves expressivity beyond 1- & 2-WL tests. Since the proposed work is evaluated on both node-level and graph-level tasks, SHADOW-GNN should be properly discussed and compared. Second, the operations / architecture of subgraph GNN have not been clearly defined in the paper. It is hard to tell from Fig 3 what exactly subgraph GNNs do. \n- Theoretical analysis seems problematic. First, the example in Fig 2 is wrong. When the nodes have identical initial features (as assumed by the paper), the two 4-node 2-regular graphs are actually isomorphic (the first graph can be transferred to the second by permuting nodes (2,3) to (3,2)). Thus, subgraph GNNs do not fail in this case. Second, the proof of Theorem 2 is at best not rigid. The proof only vaguely says that a long enough RW can return different node features for different subgraph structures. It is not obvious to me why this is always the case for **all** possible subgraph structures. This is an important gap to be filled by the current proof. In addition, even if there do exist a long RW to satisfy the requirement, how long is \"long enough\"? The length of RW would play an important role in complexity analysis. \n- Complexity analysis is problematic. First, as discussed above, $L\\ll m$ may not hold since Theorem 2 does not specify the magnitude of $L$. Secondly, even if $L\\ll m$, we cannot simply say the complexity of $O(Lm)$ reduces to $O(m)$. For example, if $L=log(m)$, then apparently $O(m\\cdot log(m))\\neq O(m)$. \n- I don't understand the usage of Lemma 1. It seems that you want to address the performance bottleneck of computing $\\hat{A}_k$, but why is $\\hat{A}_k$ expensive to compute in the first place?\n- The experiments are not fully convincing. SOTA subgraph GNNs should be compared with. For example, for the node classification task, the authors should compare with SHADOW-GIN with depth=$L$ and scope=$(L-1)$-hop. For the graph classification task, the authors should compare against Zhang & Li (2021). \n\n\n## References\n\n[a] Zeng et al. Decoupling the depth and scope of graph neural networks. In NeurIPS 2021. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "P9pC1rkQ53l", "reviewer": "Reviewer_w5t6", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper deals with supervised machine learning for graphs via GNNs. Specifically, the authors propose a simple way of going beyond GNNs' limits in expressivity ($1$-WL). That is, during aggregation, the authors propose to not only consider direct neighbors but also neighbors $k$-hops away. To distinguish these from direct neighbors they are given unique labelings (for each $k$). To further enhance the expressivity the authors concatenate random walk self-landing probabiliies to the node features, e.g., following Dwivedi et al., 2021.\n\n\n\n", "summary_of_the_review": "This is an incremental paper. In its current form of presentation and its lack of formalization, it is not ready for a top-tier conference. ", "strength_and_weaknesses": "**Strong**\n- Simple approach that sometimes leads to an empirical boost\n\n**Weak**\n- Presentation and formalization is subpar\n- Proofs are of a hand-wavey nature and not formal enough to verify.\n- Related work section misses many papers \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "8h9P-KjKOrp", "reviewer": "Reviewer_xS7k", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a light-weighted plugin/algorithm to uplift the upper bound of the GNNs' expressive power, namely the 1-WL test. By constructing a multi-hop multi-color rooted subtree, the algorithm achieves or even exceeds the performance of the subgraph GNNs while using fewer computational resources.", "summary_of_the_review": "The paper presents an interesting alternative compared to the message-passing GNNs and the subgraph GNNs. However, the novelty is limited and the theoretical discussion is a little weak. Also, there are minor flaws in the experiment.", "strength_and_weaknesses": "Strength:\n1. Reduce the memory requirement by compressing the multi-layer structure of the message passing GNNs into one iteration.\n2. The idea of the multi-hop multi-color subtree is straightforward and easy to understand.\n\nWeaknesses:\n1. The theoretical analysis is a mostly intuitive discussion with no mathematical proof. \n2. In the method section, too much effort is spent on discussing the subgraph GNNs.\n3. The datasets in the experiments for Q1 are questionable. For a node classification problem, the training set and the test set are 1000 graphs each, indicating that the model trained is transferred from the training graph to the testing graphs. While for a node classification task, the norm is training on some nodes of a graph and testing on the other nodes of the same graph.\n4. The paper claims that the method is faster and more memory efficient. Memory efficiency is indeed significant, while the run time doesn't improve significantly in the experiment, and hasn't been discussed theoretically.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "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": "7b8R9kiOkN", "reviewer": "Reviewer_8LVG", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a simple model to improve the GNN expressiveness by encoding a multi-hop multi-color rooted subtree. It is shown that the proposed method is more expressive than 1-WL GNNs and is efficient in terms of running time and memory usage. Experiments on several benchmarks are performed to support the claim.", "summary_of_the_review": "Overall, I think this work lacks novelty and experimental support for the main claim. I highly recommend the authors to improve this work by considering the above concerns.", "strength_and_weaknesses": "Strengths:\n\n1. The motivation of encoding multi-hop subtree with multiple colors is technically sound.\n2. This manuscript is clearly written and organized.\n\nWeakness:\n\n1. The novelty of the proposed method is limited. This method simply encoding multi-hop subtree to improve the expressiveness of GNNs. However, this idea has been extensively used by previous works, such as SIGN [1] and Neighbor2Seq [2]. Both methods consider encoding multi-hop neighbors as this work (See Eq. (4)). The key difference and novelty compared to them should be clarified.\n\n2. This method is proved to be at least as equivalent to the expressive power of subgraph GNNs with certain conditions. However, the second condition does not hold for most times. Hence, the expressiveness compared with subgraph GNNs is not convincing to me. In addition, there is no strong empirical results can verify that the proposed method is competitive with subgraph GNNs.\n\n3. Figure 2 is not clear to me. I am wondering if node 1, 2, 3, 4 have the same node features. If yes, then these two regular graphs are isomorphic. If no, then the rooted subgraphs (the middle in Figure 2) can distinguish these two graphs. Hence, I don’t understand why the proposed method is special in this case. Please correct me if I am understanding it wrongly.\n\n[1] Rossi, Emanuele, et al. \"Sign: Scalable inception graph neural networks.\" arXiv preprint arXiv:2004.11198 7 (2020): 15.\n[2] Liu, Meng, and Shuiwang Ji. \"Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences.\" Proceedings of the 2022 SIAM International Conference on Data Mining (SDM). Society for Industrial and Applied Mathematics, 2022.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject