From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness
Authors: Lingxiao Zhao
Wei Jin
Leman Akoglu
Neil Shah
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
Expressiveness
Message Passing Neural Network
Graph Classification

Abstract: Message Passing Neural Networks (MPNNs) are a common type of Graph Neural Network (GNN), in which each node’s representation is computed recursively by aggregating representations (“messages”) from its immediate neighbors akin to a star-shaped pattern. MPNNs are appealing for being efficient and scalable, however their expressiveness is upper-bounded by the 1st-order Weisfeiler-Lehman isomorphism test (1-WL). In response, prior works propose highly expressive models at the cost of scalability and sometimes generalization performance. Our work stands between these two regimes: we introduce a general framework to uplift any MPNN to be more expressive, with limited scalability overhead and greatly improved practical performance. We achieve this by extending local aggregation in MPNNs from star patterns to general subgraph patterns (e.g., k-egonets): in our framework, each node representation is computed as the encoding of a surrounding induced subgraph rather than encoding of immediate neighbors only (i.e. a star). We choose the subgraph encoder to be a GNN (mainly MPNNs, considering scalability) to design a general framework that serves as a wrapper to uplift any GNN. We call our proposed method GNN-AK (GNN As Kernel), as the framework resembles a convolutional neural network by replacing the kernel with
GNNs. Theoretically, we show that our framework is strictly more powerful than 1&2-WL, and is not less powerful than 3-WL. We also design subgraph sampling strategies which greatly reduce memory footprint and improve speed while maintaining performance. Our method sets new state-of-the-art performance by large margins for several well-known graph ML tasks; specifically, 0.08 MAE on ZINC,
74.79% and 86.887% accuracy on CIFAR10 and PATTERN respectively.

Published as a conference paper at ICLR 2022
FROM STARS TO SUBGRAPHS: UPLIFTING ANY GNN WITH LOCAL STRUCTURE AWARENESS
Lingxiao Zhao
Wei Jin
Leman Akoglu
Neil Shah Snap Inc.
Carnegie Mellon Uni.
Michigan State Uni.
Carnegie Mellon Uni.
dingxiaodccm edu
j mwe 20msu. edu
cmw. edu
nshahEsnap.com
ABSTRACT
Message Passing Neural Networks (MPNNs) are a common type of Graph Neural Network (GNN), in which each node's s representation is computed recursively by aggregating representations ( ("messages") from its immediate neighbors akin to a star-shaped pattern. MPNNs are appealing for being efficient and scalable, how- ever their expressiveness is boouer- by the Ist-order Weisfeiler-Lentn iso- morphism test (1-WL). In response, prior works propose highly expressive mod- els at the cost of scalability and sometimes generalization performance. Our work stands between these regimes: introduce general framework uplift any MPNN to be more expressive, with limited scalability overhead and greatly improved practical performance. We achieve this by extending local aggregation in MPNNs from star patterns to general subgraph patterns (c.g., k-egonets): in our framework, each node representation is computed as the encoding of a sur- rounding induced subgraph rather than encoding of immediate neighbors only (i.e. a star). We choose the subgraph encoder to be a GNN (mainly MPNNs, considering scalability) to design general framework that serves as wrapper to uplift any GNN. We call our proposed method GNN-AK (GNN As Kernel), as the framework resembles convolutional neural network by replacing the kernel with GNNs. Theoretically, we show that our framework is strictly more powerful than 1 1,, and is not less powerful than 3-WI.. We also design subgraph sam- pling strategies which greatly reduce memory footprint and improve speed while maintaining performance. Our method sets new state-of-the-ard performance by large margins for several well-known graph ML tasks; specifically, 0.08 MAE on ZINC, 74.79% and 86.887% accuracy on CIFAR1O and PATTERN respectively.
INTRODUCTION
Graphs are permutation invariant, combinatorial structures used to represent relational data, with wide applications ranging from drug discovery. social network analysis, image analysis to bioin- formatics (Duvenaud et al.) 2015) Fan et al. 2019: Shi et al.] 2019 [w et al. (020). In recent years, Graph Neural Networks (GNNs) have rapidly surpassed traditional methods like heuristically defined features and graph kernels become the dominant approach for graph MI. tasks.
Message Passing Neural Networks (MPNNs) (Gilmer et al.) 2017) are the most common type of GNNs owing to their intuitiveness, effectiveness and efficiency. They follow recursive aggregation mechanism where each node aggregates information from its immediate neighbors repeatedly, How- ever, unlike simple multi-layer feedforward networks (MLPs) which are universal approximators of continuous functions (Hornik et al. 1989), MPNNs cannot approximate all cormuutationinvariinn graph functions (Maron et al. 2019b). In fact, their expressiveness is upper bounded by the first order Weisfeiler-Leman (1-WL) isomorphism test (Xu et al.. 2018). Importantly, researchers have shown that such 1- equivalent GNNs are not expressive, or powerful, enough to capture basic structural concepts, i.c., counting motifs such cycles or triangles (Zhengdao et al. 2020 Arvind cet al. 2020) that are shown to be informative for bio- and chemo-informatics (Elton et al. 2019).
The weakness of MPNNs urges researchers to design more expressive GNNs, which are able to discriminate graphs from an isomorphism test perspective; Chen et al. (2019) prove the equivalence between such tests and universal permutation invariant function approximation. which theoretically justifies it. As k-WL is strictly more expressive than 1-WL, many works (Moriis et al.) 2019 2020b) try to incorporate k- in the design of more powerful GNNs, while others approach k-

---

Published as a conference paper at ICLR 2022
Cocoding
Encoding
Cecoding
B000 (4 Aggopp
TUM (EViEgS Aeripe E4
SUV (DVAEE Aqripn OI
(neo) 3D
unggee- All
Base GAR
Greogaeeggpp 3D
SUM Siritttt----ggg
SUu Banitgg Suugrasi
g
f
every
Dync7teaguu 7)
Figure 1: Shown: one GNN-AK+ layer. For each layer, GNN-AK first extracts ni (# nodes)
rooted subgraphs, and convolves all subgraphs with a base GNN as kemel,, producing multiple rich subgraph-not embeddings of the form Emb(i Sub[i]) (node i's embedding when applying a GNN kernel on subgraph j). From these, we extract and concatenate three encodings for a given node j: (i) centroid Emb(j Sub(il), (ii) subgraph Σ, Emb(i Sub(j]), and (iii) context Σ, Emb(j Sub(i))- GNN-AK+ repeats the process for L layers, then sums all resulting node embeddings to compute the final graph embedding. As weaker version, GNN-AK only contains encodings (i) and (ii).
expressiveness indirectly from matrix invariant operations (Maron al. 2019a b Keriven & Peyré, 2019) and matrix language perspectives (Balcilar et al.] (021). However, they require Ork)-rrder tensors to achieve k-WL expressiveness, and thus are not scalable or feasible for application on large, practical graphs. Besides, the bias-variance tradeoff between complexity and generalization
(Neal et al. 2018) and the fact that almost all graphs (i.e. O(2(i)) graphs on n vertices, Babai et al. (9800)) can be distinguished by 1-WL challenge the necessity of developing such extremely expressive models. In complementary line of work, [Loukas| (2020a) sheds light on developing more powerful GNNs while maintaining linear scalability, finding that MPNNs can be universal approximators provided that nodes are sufficiently distinguishable. Relatedly, several works propose to add features to make nodes more distinguishable, such identifiers (Loukas) 2020a), subgraph counts (Bouritsas et al. 2020), distance encoding (Li et al., 2020), and random features (Sato et al.] 2021 Abbboud et al. 2021). However, these methods either focus handcrafted features which lose the premise of automatic learning, or create permutation sensitive features that hurt generalization.
Present Work. Our work stands between the two regimes of extremely expressive but unscalable k- order GNNs, and the limited expressiveness yet high scalability of MPNNs. Specifically, we propose general framework that serves as "wrapper" to uplift any GNN. We observe that MPNNs' local neighbor aggregation follows a star pattern, where the representation of a node is characterized by applying an injective aggregator function as an encoder the star subgraph (comprised of the central node and edges to neighbors). We propose design which naturally generalizes from encoding the star to encoding a more flexibly defined subgraph, and we replace the standard injective aggregator with a GNN: in short, we characterize the new representation of a node by using GNN to encode a locally induced encompassing subgraph, as shown Fig T This uplifts GNN as a base model in effect by applying it on each subgraph instead of the whole input graph. This generalization is close to Convolutional Neural Networks (CNN) in computer vision: like the CNN that convolves image patches with kernel to compute new pixel embeddings, our designed wrapper convolves subgraphs with a GNN to generate new node embeddings. Hence, we name our approach GNN-AK AK (GNN As Kernel). We show theoretically that GNN-AK is strietly more powerful than 1 &&2- WL with any MPNN as base model, and is not less powerful than 3-WL with PPGN (Maron et al. 2019a) used. We also give sufficient conditions under which GNN-AK can successfully distinguish two non-isomorphic graphs. Given this increase in expressive power, we discuss careful implementa- tion strategies for GNN-AK. which allow us to carefully leverage multiple modalities of information from subgraph encoding. and resulting in an empirically more expressive version GNN-AK As a result, GNN-AK and GNN-AK* induce a constant factor overhead in memory. To amplify our method's practicality, we further develop subgraph sampling strategy inspired by Dropout (Srivas-) tava et al. 2014) to drastically reduce this overhead (1-3x in practice) without hurting performance. We conduct extensive experiments on 4 simulation datasets and 5 well-known real-world graph clas- sification & regression benchmarks (Dwivedi et al.] 2020 Hu et al. 2020), to show sigmificant and consistent practical benefits of our approach across different MPNNs and datasets. Specifically, GNN-AK+ sets new of-te-of-the-rr performance on ZINC, CIFAR10. and PATTERN - for exam- ple, on ZINC we see relative error reduction of 60.3%, 50.5%, and 39.4% for base model being
2

---

Published as a conference paper at ICLR 2022
GCN (Kiff & Welling 2017). GIN (Xu et al., 2018), and (a variant of) PNA (Corso et al. 2020)
respectively. To summarize, our contributions are listed as follows:
A General GNN-AK Framework. We propose GNN-AK (and enhanced GNN-AK*), general
framework which uplifts any GNN by encoding local subgraph structure with GNN.
Theoretical Findings. We show that GNN-AK's expressiveness is strictly better than 1&2-WL,
and is not less powerful than 3-WL. We analyze sufficient conditions for successful discrimination. Effective and Efficient Realization. We present effective implementations for GNN-AK and GNN-AK* to fully exploit all node embeddings within a subgraph. We design efficient online subgraph sampling to mitigate memory and runtime overhead while maintaining performance. Experimental Results. We show strong empirical results, demonstrating both expressivity im- provements as well as practical performance gains where we achieve new state-of-the-art perfor- mance on several graph-level benchmarks.
Our implementation is easy-to-use, and directly accepts any GNN from PyG Fey & Lenssen 2019 for plug-and- play use. See code at htttps:: /ttttps///gthub... httpa/////cc.aeaeeeeeeeaaaa..a..
RELATED WORK
Exploiting subgraph information in GNNs is not new; in fact, k-WL considers all it node sub- graphs. Monti et al. (2018); Lee et al. (2019) exploit motif information within aggregation, and others (Bouritsas et al., 20200 Barceló et al. 2021) augment MPNN features with handcrafted sub- graph based features. MixHop (Abu-El-Haija et 2019) directly aggregates k-hop information by using adjacency matrix powers, ignoring neighbor connections. Towards a meta-learning goal, p
G-meta (Huang & Zitnik 2020) applies GNNs rooted subgraphs around each node to help trans-
ferring ability. TTahmasebi & Jegelka 2020) only theoretically justifies subgraph convolution with GNN by showing its ability in counting substructures. [Zenndao et al. (2020) also represent node by encoding its local subgraph, however using non-scalable relational pooling. k-hop GNN (Niko- lentzos et al. 2020) uses k-egonet in a specially designed way: it encodes rooted subgraph via sequentially passing messages from k-th hops in the subgraph to k- - hops, until it reaches the root node, and use the root node encoding of the subgraph. Ego-GNNs (Sandfelder et al. 2021) computes a context encoding with SGC (Wu et al. 2019) as the subgraph encoder, and only be studied on node-level tasks. Both h-hop GNN and Ego-GNNs can be viewed as special case of GNN-AK. You et al.] (2021) designs ID-GNNs which inject node identity during message passing with the help of k-egonet, with being the number of layers GNN (Hamilton et al., 2017). Un- like GNN-AK which uses rooted subgraphs, Fey et al. (2020); "Thiede et al. (2021): [Bodnar et al. 2221aa) design GNNs to use certain subgraph patterns (like cycles and paths) in message passing, however their preprocessing requires solving the subgraph isomorphism problem. Cotta et al. (2021) explores reconstructing a graph from its subgraphs. A contemporary work (Zhang & Li (021) also encodes rooted subgraphs with base GNN but it essentially views graph bag of subgraphs while GNN-AK modifies the 1-WL color refinement and has many iterations. Viewing graph as a bag of subgraphs also explored in another contemporary work (Bevilacqua al. (0022). To sum- marize, our work differs by (i) proposing a general subgraph encoding framework motivated from theoretical Subgraph-1-Ve WL for uplifting GNNs, and (ii) addressing scalability issues involved with using subgraphs. which poses significant challenges for subgraph- methods in practice. See additional related work in Appendix/A.1
3 GENERAL FRAMEWORK AND THEORY
We first introduce our setting and formalisms. Let G E) be a graph with node features x, E IRd, Vi E V. We consider geaph problems where the goal to classify/regress target Ya by learning graph-level representation hę. Let (v) be the set of nodes in the k-hop egonet rooted at node v. A(v) = Ni (v){rr denotes the immediate neighbors of node v. For S C V. let G[S] be the induced subgraph: G[S] (S, (i. E Eli e S.j E S)). Then (v)) denotes the k-hop egonet rooted at node v. We also define Star(e) = (N1 ((v.j) E Elj E ((()))
}) be the induced star-like subgraph around We use {.) denotes multiset, i.e. set that allows repetition.
Before presenting GNN-AK, we highlight the insights in designing GNN-AK and driving the expres- siveness boost. Insight 1: Generalizing star to subgraph. In MPNNs, every node aggregates information from its immediate neighbors following a star pattern. Consequently, MPNNs fail to distinguish any non-isomorphic regular graphs where all stars are the same, since all nodes have the same degree. Even simply generalizing star to the induced, 1-hop egonet considers connec-
3

---

Published as a conference paper at ICLR 2022
tions among neighbors, enabling distinguishing regular graphs. Insight 2: Divide and conquer. When two graphs are non-isomorphic, there exists a subgraph where this difference is captured (see Figure 3). Although ixeedexxrresiveenss GNN may not distinguish the two original graphs, it may distinguish the two smaller subgraphs, given that the required expressiveness for successful discrimination is proportional to graph size (Loukas) 20206). As such, GNN-AK divides the harder problem of encoding the whole graph to smaller and easier problems of encoding its subgraphs, and "conquers" the encoding with the base GNN.
3.1 FROM STARS TO SUBGRAPHS
We first take a close look MPNNS, identifying their limitations and expressiveness bottleneck. MPNNs repeatedly update each node's embedding by aggregating embeddings from their neighbors
a fixed number of times (layers) and computing a graph-level embedding be by global pooling. Let
(1) h denote the 1-th layer embedding of node v. Then, MPNNs compute hy by
h (++1) = 00 (B) ) ((u.) E e((o)))) 1= 0..,.., 11; 1; he = -POOL( (1 E vy) (1)
where h. x; is the original features. L is the number of layers, and tt and f() are the 1-th layer update and aggregation functions. "i0), f() and POOL vary among different MPNNs and influence their expressiveness and performance. MPNNs achieve maximum expressiveness (1-WL)
when all three functions are injective (Xu et al. 2018).
MPNNs' expressiveness upper bound follows from its close relation to the 1-WL isomorphism test (Moriis et al., 2019). Similar to MPNNs which repeatedly aggregate self and neighbor representa- tions, at f-th iteration, for each node 1-WL test aggregates the node's 's own label (or color) cy and
its neighbors' labels {cli) |u E (u))). and hashes this multi-set of labels { f (1) , (cl Iu E ((O)
into a new, compressed label de (t+1) 1-WL outputs the set of all node labels {ce // E V} as G's fingerprint, and decides two graphs to be non-isomorphic as soon as their fingerprints differ.
(cST))
The hash process in 1-WL outputs new label c (t+1) that uniquely characterizes the star graph Star(u) around v. i.e. two nodes v are assigned different compressed labels only if Star(u) and Star(v) differ. Hence, it is easy see that when two -somooooeepiic unlabeled (i.e., all nodes have the same label) d-regular graphs have the same number of nodes, 1-WI. cannot distinguish them. This failure limits the expressiveness of 1-WL., but also identifies its bottleneck: the star not distinguishing enough. Instead, we propose generalize the star Star(v) to subgraphs, such as the egonet G[M] (v)] and more generally k-hop egonet (.)). This results in an improved version of 1-WL which we call Subgraph-I-WL. Formally,
Definition 3.1 (Subgraph-1-WLL. Subgraph- generalizes the 1-WL graph isomorphism test (Star(S(a(())))) with
algorithm by replacing color refinement (at iteration 1) by c (t+1) Co
(t+1) (N)) Vu E V where HASH(.) is an injective function on graphs.
Note that injective hash function for star graphs is equivalent to that for multi-sets, which is easy to derive (Zaheer et al.] 2017). In contrast, Subgraph-I-WL must hash a general subgraph. where an injective hash function for graphs is non-trivial (as hard as graph isomorphism). Thus, we derive a variant called Subgraph-I-WL." by using a weaker choice for HASH(-) specifically, 1-WL. Effectivly, we nest 1-WL inside Subgraph- 1-WL. Formally,
Definition 3.2 (Subgraph-1-WLL)) Subgraph-1-WL. is less expressive variant of Subgraph-1-
WI. where ( (l+1)_ 1-WI,
We further transfer Subgraph-1-We 1-WL to neural networks, resulting in GNN-AK whose expressiveness is upper bounded by Subgraph-1-WL The natural transformation with maximum expressiveness is to replace the hash function with a universal subgraph encoder of G+)(())), which is non-trivial as it implies solving the challenging graph isomorphism problem in the worst case. Analogous to using 1-WL a weaker choice for HASH(-) inside Subgraph-I-WL', we can use use any GNN (most practically, MPNN) as an encoder for subgraph (v)) Let (((N) the attributed subgraph with hidden features (()) at the (-th layer. Then, GNN-AK computes hGg by h ((+1)) ( (c() (Ne(v)) 1= 0,
G)N be
he POOL((( V))
(2)
Notice that GNN-AK acts as a "wrapper" for any base GNN (mainly MPNN). This uplifts its ex- pressiveness well practical performance as we demonstrate in the following sections.
4

---

Published as a conference paper at ICLR 2022
3.2 THEORY: EXPRESSIVENESS ANALYSIS
We next theoretically study the expressiveness of GNN-AK. by investigating the expressiveness of Subgraph-I-WL. We first establish that GNN-AK and Subgraph- 1-WL have the same expressiveness under certain conditions. GNN is able to distinguish two graphs if its embeddings for two graphs not identical. A GNN is said to have the same expressiveness as graph isomorphism test when for any two graphs the GNN outputs different embeddings and only (iff) the isomorphism test deems them non-isomorphic. We give following theorems with proof in Appendix.
Theorem 1. When the base model is MPNN with sufficient number of layers and injective o, f and POOL functions shown in Eq. ( and MPNN-AK has an injective POOL function shown in Eq. then MPNN-AK as powerful Subgraph-I-WL"
See Appendix A.3 for proof. A more general version of Theorem T is that GNN-AK is as powerful as Subgraph- 1 iff base GNN of GNN-AK is as powerful as the HASH function of Subgraph-1- WL in distinguishing subgraphs, following the same proof logic. The Theorem implies that we can characterize expressiveness of GNN-AK through studying Subgraph-1-WL. and Subgraph-1-WL..
Theorem 2. Subgraph-I-Wy is strictly more powerful than 1&2-W4]
A direct corollary from Theorem
T as follows, which empirically verified in Table II
Corollary 2.1. When MPNN is I-WI. expressive, MPNN-AK is strictly more powerful than &
Theorem 3. When (-SH(.) is 3-WL expressive, Subgraph-I-WF is less powerful than 3- W-W that is, it can discriminate some graphs for which f-ilssails.
direct corollary from Theorem
+ as follows, which empirically verified in Table I
Corollary 3.1. PPGN-AK can distinguish some 3- 3-WL-failed non-isomorphic graphs.
Theorem 4. For any 3, there exists a pair of k- L-WL-failed graphs that cannot be distinguished by Subgraph-I-WL even with injective HASH(.) when t-hop egonets are used with S 4.
Theorem is proven (Appendix,)) (..6) A.6 by observing that with limited t all rooted subgraphs of two non-isomorphic graphs from CFT(k) family (Cai et al. 1992] are isomorphic, i.e. local rooted sub- graph is not enough to capture the "global" difference. This opens a future direction of generalizing rooted subgraph general subgraph (as in k-WL) while keeping number of subgraphs in O(V)).
Proposition 1 (sufficient conditions). For non-isomorphic graphs G, H, Subgraph-I-We --WL with k-egonet can successfully distinguish them if: 1) for any node reordering uf,,.., Dicl and of ...., vff Vun' Ji [1, max(al)) [VH) that GoN)(v() and ((NN }} are non-isomorphie and 2) (.SH(.) is discriminative enough that HASH(G(N& # (A
This implies subgraph size should be large enough to capture difference, but not larger which re- quires more expressive base model (Loukas 2020a). We empirically verify Prop. in Table 2
CONCRETE REALIZATION
We first realize GNN-AK with two type of encodings, and then present an empirically more expres- sive version, GNN-AK+, with (i) an additional context encoding, and (ii) subgraph pooling design readily computed during subgraph extraction. Next, we discuss aandm-walk based rooted subgraph extraction for graphs with small diameter to reduce memory footprint of k-hop egonets. We conclude this section with time and space complexity analysis.
to incorporate iistance-to-centron
Notation. Let G = E) be the graph with 1/) G (v)] the k-hop egonet rooted at node E V in which (1())) denotes node u's hidden representation for E N2(v)) at the (-th layer of GNN-AK. To simplify notation, we use (ub [c] instead of GO) [N(() to indicate the the attribute- enriched induced subgraph for v. We consider all intermediate node embeddings across rooted
subgraphs. Specifically, let Emb(i (D)) denote node i's embedding when applying base GN on Sub") we consider node embeddings for every j V and every i Sub [). Note
11-WI and 2-WL. are known to be equally powerful, see Azizian & Lelarge 2021 and Maron et al. When VVll= < (Vrl, Vi E ([Vol. [Vel+ 1,., (Vrl} let G[Nx(o (x()) denote empty subgraph.
2019a
5

---

Published as a conference paper at ICLR 2022
that the base GNN can have multiple convolutional layers, and Emb refers to the node embeddings at the last layer before global pooling POOLoNN that generates subgraph-level encoding.
Realization of GNN-AK. We can formally rewrite Eq. (2) as h (S)hhhhhhh
GNN" (Sub (Slb := aON ((Ebb(i Sub"([]) live Nx(o))
(3)
We refer to the encoding of the rooted subgraph [uj in Eq. 3 as the subgraph encoding. Typical choices of POOL-NN are SUM and MEAN. As each rooted subgraph has a root node, POOL-GNN' can additionally be realized to differentiate the root node by self-concatenating its own representation, resulting in the following realization as each layer of GNN-AK:
h h(+1)= FUSE h (+1)mmmmmid h 11Shbgrahh)
where h [C]D)eeenttidd == Emb( Sub"+*(o)) (4)
where FUSE is concatenation or sum, and h ())[Centroid is referred to as the centroid encoding. The realization of GNN-AK in closely follows the theory in Sec
Realization of GNN-AK*. We further develop GNN-AK*, which is more expressive than GNN-AK, based on two observations. First, observe that Eg
E does not fully exploit all information inside
the rich intermediate embeddings generated for Eq and propose an additional context encoding.
he (++1) Contest POOLCsetest (Emb(y
(D) VVj s.t. E (N.(i)))
(S)
Different from subgraph and centroid encodings, the context encoding captures views of node from different subgraph contexts, or points-of-view. Second, GNN-AK extracts the rooted subgraph for every node with efficient k-hopp propagation (complexity O(}{E)), along which the distance-to- centroid (D2CF) within each subgraph is readily recorded at no additional cost and can be used to augment node features; (Li et al. 2020) shows this theoretically improves expressiveness. There- fore, we propose to uses the D2C by default in two ways in GNN-AK*:: (i) augmenting hidden
representation h by concatenating it with the encoding of D2C; (ii) using it to gate the subgraph and context encodings before Subgraph and Contexts with the intuition that embeddings of nodes far from v contribute differently from those close to c.
be the encoding of distance from node i To formalize the gate mechanism guided by D2C, let d
to at 1-th laye Applying gating changes Eq. 5 to
(++1) Connest
== POOL (Sigmoid( .1n) @ Emb(v Sub (Sb Vjj s.t. u U N.G))
(6)
where @ denotes element-wist multiplication. Similar changes apply to Eq. 3 to get h (U)Suurrrahh gated,
Formally, each layer of GNN-AK* + is defined as bg+D FUSE (((++1)) h 1+1+
h (++1) Subgraph gaate
h (L+ (CCmmes goted
where FUSE is concatenation or sum. We illustrate in Figure Proposition 2. GNN-AK* is at least as powerful as GNN-AK.
I the I-th layer of GNN-AK(*).
See Proof in Appendix.A
Beyond k-eegnet Subgraphs. The h-hop egonet (or k-egonet) a natural choice in our framework, but can be too large when the input graph's 's diameter is small, as in social networks (Kleinberg, 2000). or when the graph is dense. To limit subgraph size, we also design a random-walk based subgraph extractor. Specifically, to extract a subgraph rooted at node we perform fixed-length random walk starting at e, resulting visited nodes Nr.. (v) and their induced subgraph G\N In practice, we use multiple truncated random walks and union the visited nodes as Nrw Moreover, we employ online subgraph extraction during training that re-extracts subgraphs at every epoch, which further alleviates the effect of randomness via regularization.
adaptive random walks as in Grover & Leskovee (2016). To reduce randomness,
Complexity Analysis. Assuming k-egonets as rooted subgraphs, and an MPNN base model. For each graph G = EV, the subgraph extraction takes (k(EE) runtime complexity, and outputs |V] subgraphs, which collectively can be represented as union graph Gu = (Vu, Eu) with | disconnected components, where [Vul= Evev (Na (v) and | Evey ( (n]]l- GNN-AK(
can be viewed as applying base GNN on the union graph. Assuming base GNN has O(DV + [&l)
runtime and memory complexity, GNN-AK(*) has O(Vull + (ELl) runtime and memory cost. For rooted subgraphs of size 8, GNN-AK(()) induces an (s)) factor overhead over the base model.
We record D2C value for every node in every subgraph, and the value is categorical instead of continuous.
"The categorical D2C. does not change across layers, but is encoded with di different parameters in each layer.

---

Published as a conference paper at ICLR 2022
5 IMPROVING SCALABILITY: SUBGRAPHDROP
The complexity analysis reveals that GNN-AK(*) introduce constant factor overhead (subgraph size) in runtime and memory over the base GNN. Subgraph size can be naturally reduced by choos- ing smaller k for k-egonet, or by ranking and truncating visited nodes in a random walk setting. However limiting to very small subgraphs tends to hurt performance as we empirically show in Ta- ble T Here, we present different subsampling-bast -ased approach that carefully selects only a subset of the [V] rooted subgraphs. Further more, inspired from Dropout (Srivastava et al. 2014), we only drop subgraphs during training while still use all subgraphs when evaluation. Novel strategies are designed specifically for three type of encodings to eliminate the estimation bias between training and evaluation. We name SubgraphDrop for dropping subgraphs during training. SubgraphDrop significantly reduces memory overhead while keeping performance nearly the same as training with all subgraphs. We first present subgraph sampling strategies, then introduce the designs of aligning training and evaluation. Fig. in Appendix A.2 provides pictorial illustration.
5.1 SUBGRAPH SAMPLING STRATEGIES
Intuitively, if u, V are directly connected in G. subgraphs ([) and G[N+(e)] share a large overlap and may contain redundancy. With this intuition, we aim to sample only m< V minimally redundant subgraphs
reduce memory overhead. We propose three fast sampling strategies (See Appendix A.2 that select subgraphs to evenly cover the whole graph, where each node is covered by = (redundancy factor) selected subgraphs: R is hyperparameter used as sampling stopping condition. Then, GNN-AK(t)-S (with Sampling) has roughly R times the overhead of base model (R$3 in practice). We remark that our subsampling strategies are randomized and fast, which both desired characteristics for an online Dropout- like sampling in training.
5.2 TRAINING WITH SUBGRAPHDROP
Although dropping redundant subgraphs greatly reduces overhead, it still loses information. Thus, as in Dropout (Srivastava al. 2014), we only "drop" subgraphs during training while still using all of them during evaluation. Randomness in sampling strategies enforces that selected subgraphs differ across training epochs, preserving most information due amortization. On the other hand, it makes it difficult for the three encodings during training to align with full-mode evaluation. Next, we propose an alignment procedure for each type of encoding.
Subgraph and Centroid Encoding in Training. Let S C V be the set of root nodes of the se- lected subgraphs. When sampling during training, subgraph and centroid encoding can only be computed for nodes v S. following Eq. (3) and Eq. (4), resulting incomplete subgraph en- codings (h (Sbbgrrga Iu E S} and centroid encodings (h! ["Toonoooid I E S). To estimate uncom- puted encodings of u E V S, we propose to propagate encodings from S to V \ S. Formally, let kmaa = max Dist(u, u, S) where Dist(u, S) S)=minges ShortestPatDDisanncee/ u, v). Then we partition 24 = V\ S into (4,,..,,u Memaer with = {u E U Dist( S) = d). We propose to spread vector encodings of S out iteratively, i.e. compute vectors of Ua from Ma- Formally, we have Mean (h (Subgmmeh vo U4-11, (u, v) E E))
h (Sbbrrph
for d 1,2 kmazi Vu Udd.
(8)
h (1) Centoid Mcan (lh (b. ())conoood E Ua-1, (u, v) E E))
for 1,2.... kman, Vu E Uhs
Context Encoding in Training. Following Eq. (5), context encodings can be computed for every node V as each node is covered at least R times during training with SubgraphDrop. However
when POOLContext is SUM(-). the scale of h (T))Context is smaller than the one in full-mode evaluation. Thus, we scale the context encodings up to align with full-mode evaluation. Formally,
Hjj E VJN++()) M HH 10 E (i) 3 v)
h (oettntt
x SUM (Emb(u) (ab(() [D) Vjj E S s.t. v E (N()))
(10)
When POOL is MEAN(-), the context encoding is computed without any modification.
EXPERIMENTS
In this section we (1) empirically verify the expressiveness benefit of GNN-AK(*) on 4 simulation datasets: (2) show GNN-AK(+) boosts practical performance significantly on 5 real-world datasets; (3) demonstrate the effectiveness of SubgraphDrop: (4) conduct ablation studies of concrete designs. We mainly report the performance of GNN-AK+, while still keep the performance of GNN-AK with GIN as base model for reference, as it is fully explained by our theory.
7

---

Published as a conference paper at ICLR 2022
Simulation Datasets: 1) EXP (Abboud et al. 2021 contains 600 pairs of 1&:2-L failed graphs that are splited into two classes where each graph of a pair is assigned to two different classes. 2) SR25 (Balcilar al. 202I) has 15 strongly regular graphs (3-WL failed) with 25 nodes each. SR25 is translated to a 15 way classification problem with the goal of mapping each graph into a different class. 3) Substructure counting (i.e. triangle, tailed triangle, star and 4-cycle) problems on random graph dataset (Zhengdao et al., (020). 4) Graph property regression (i.e. connectedness, diame- ter, radius) tasks on random graph dataset (Corso al.) 2020). All simulation datasets are used to empirically verify the expressiveness of GNN-AK("). ) Large Real-world Datasets: ZINC-12K, CI PATTER from Benchmarking GNNs (Dwivedi et al. 2020) and MolHIV, and MolPCBA from Open Graph Benchmark (Hu et al., 2020). Small Real-world Datasets: MUTAG, PTC, PRO- TEINS, NCI1, IMDB, and REDDIT from TUDatset (Morris et al. (0020a) (their results are presented
in Appendix 121.p. See Table 5 in Appendix for all dataset statistics.
Baselines. We use GCN (Kipf & Welling 2017). GIN (Xu et al. 2018 PNA (Corso et al. 2020). and 3-WL powerful PPGN (Maron al. (019a) directly, which also server as base model of GNN- AK to see its general uplift effect. GatedGCN (Dwivedi et al. 2020). DGN (Beani et al. 202T), PNA (Corso et al., 2020), GSN(Bourissas et al. 2020), HIMP (Fey et al. 2020), and CIN (Bodnar et al.,
2021a) are referenced directly from literature for real-world datasets comparison. Hyperparameter and model configuration are described in Appendix/A.10)
6.1 EMPIRICAL. VERIFICATION OF EXPRESSIVENESS
Table 1: Simulation dataset performance: GNN-AK(() boosts base GNN across tasks, empirically verifying expressiveness lift. (ACC: accuracy, MAE: mean absolute error, OOM: out of memory)
Counting Substructures (MAE)
Graph Properties (MAE))
Method
EXP
SR25
(ACC)
(ACC)
Triangle
Tailed Tri.
Star
4-Cycle
IsConnected
Diameter
Radius
GCN
50%
6.67%
0.4186
0.3248
0.1798
0.2822
-1.7057
-2.4705
13,3166
GCN-AK+
100%
6.67%
0.0137
0.0134
0.0174
0.0183
-2.6705
-3,9102
-5.1136
GIN
50%
6.67%
0.3569
0.2373
0.0224
0.2185
-1.9239
-3.3079
4,7584
GIN-AK
100%
6.67%
0.0934
0.0751
0.0168
0.0726
-1.9934
-3.7573
-50100
GIN-AK+
100%
6.67%
0.0123
0.0112
0.0150
0.0126
-2.7513
-3.9687
-5.1846
PNA"
50%
6.67%
0.3532
0.2648
0.1278
0.2430
-1.9395
-3,4382
4,9470
PNA--AK+
100%
6.67%
0.0118
0.0138
0.0166
0,0132
-2.6189
-3.9011
-5,2026
PPGN
100%
6.67%
0.0089
0.0096
0.0148
0.0090
-1.9804
-3.6147
-5.0878
PPGN-AK+
100%
100
00M
O0M
00M
OOM
00M
0OM
0OM
Table presents the results on simulation datasets. To save space we present GNN-AK* with dif-
ferent base models but only one one version of GNN-AK: GIN-AK. All GNN-AK(+)) variants perform perfectly on EXP, while only PPGN alone do so previously. Moreover, PPGN-AK* reaches perfect accuracy on SR25, while PPGN fails. Similarly, GNN-AK(+) consistently boosts all MPNNs for substructure and graph property prediction (PPGN-AK+ + is OOM as it quadratic in input size).
In Table 2 we look into PPGN-AK's per- formance on SR25 as a function of k- egonets (1:(1,, 2), as well as the num- ber of PPGN (inner) layers and (outer) iterations for PPGN-AK. We find that at least 2 inner layers is needed with 1- egonet subgraphs achieve top performance. With 2-egonets more inner layers helps, although performance is sub-par, attributed to PPGN's disability to distinguish larger (sub)graphs, aligning
Table 2: PPGN-AK expressiveness on SR25.
Base PPGN's AT.
1-hop egonet
2-hop egonet
PPGN-AK's AL
2
2
3
26.67%
100%
100%
26.67%
26.67%
46.67%
33.33%
100%
100%
26.67% 26.67%
53.33%
26.67%
100%
100%
33.33% 26.67% 53.33%
with Proposition ( 3.2).
6.2 COMPARING WITH SOTA AND GENERALITY
Having studied expressiveness tasks, turn to performance real-world datasets, as shown in Table 3 We observe similar performance lifts across all datasets and base GNNs (we omit PPGN due scalability), demonstrating our framework's 's generality. Remarkably, GNN-AK* sets new SOTA performance for several benchmarks - ZINC, CIFAR 10, and PATTERN- - with relative error reduction of 60.3%, 50.5%, and 39.4% for base model being GCN, GIN, and PNA* respectively.
$ 'PNA* is variant of PNA that changes from using degree to scale embeddings to encoding degree and concatenate to node embeddings. This eliminates the need of computing average degree of datasets in PNA.
8

---

Published as a conference paper at ICLR 2022
Table 3: Real-world dataset performance: GNN-AK* achieves SOTA performance for ZINC-12K,
CIFARIO, and PATTERN. (OOM: out of memory, -: missing values from literature)
Method
7INC-12K (MAF)
CIFARIO (ACC)
PATTERN (ACC)
MolHTV (ROC)
MolPCBA (AP)
GatedGCN
0,363 0.009
69.37 1 0.48
84.480 0.122
HIMP
0.151 0.006
0.7880 0.0082
PNA
0.183 + 0.004
70.47 + 0.72 72.84 0.42
86.567 + 0.075
0.7905 + 0.0132
0,2838 = 0.0035 0.2885 0.0030
DGN
0.168 0.003
86.680
0.034
0.7970 0.0097
GSN
0.115 + 0.012
0.7799 0.0100
CTN
0.079 0.006
0.8094 0.0057
GCN
0.321 = 0.009
58,39
0.73 72.70
85.602 0.046
0.7422 + 0.0175
0,2385 + 0.0019
GCN-AK*
0.127 0.004
0.29
86.887 0.009
0.7928 0.0101
0.2846 + 0.0002
0.163 0.004
59.82
0.33
85.732
0.023
0.7881
0.0119
0,2682 + 0.0006
GIN-AK
0.094 0.005
67.51
0.21
86,803
0.044
0,7829
0.0121
0,2740 0.0032
GIN-AK
0,080 0.001
0.13 72.19
86.850 + 0.057
0.7961 + 0.0119
0.2930 + 0.0044
PNA
0.140 0.006
73.11 0.11 0OM
85.441 0.009 0OM
0.7905 0.0102
0.2737 + 0.0009
AK*+
0.085 0.003
0.7880 0.0153
0.2885 + 0.0006
GCN-AK+-S
0.127 0.001
71.93 0.47
86 805 0.046
0.7825
0.0098
0.2840 + 0.0036
GIN-AK+-S
0.083 0.001
72.39
0.38
86.811 0.013
0.7822 0.0075
0,2916 + 0.0029
PNA--AK-
0.082 0.000
74.79
0.18
86.676 0.022
0.7821 0.0143
0.2880 0.0012
6.3 SCALING BY SUBSAMPLING
In cases, GNN-AK (+)'s overhead leads OOM, especially for complex models like PNA* that are resource-demanding. Sampling with SubgraphDrop enables training using practical resources. Notably, GNN-AK* -S models, shown the end of Table 3 do not compromise and can even im- prove performance as compared to their sampled counterpart, in alignment with Dropout's 's ben- efits (Srivastava al.] (2014). Next we evaluate resource resource-savings, specifically on ZINC-12K and CIFARIO. Table shows that GIN-AK*-S -S with varying R provides an effective handle to trade off resources with performance. Importantly, the rate which performance decays with smaller R much lower than the rates which runtime and memory decrease.
Table 4: Resource analysis of SubgraphDropp
GIN-AK n=3
Dataset
R=1
R=2
R=4
π=5
GIN-AK+
GIN
MAR
0.1216
0.0929
0,0846
0,0852
0.0854
0.0806
0.1630
ZINC-12K
Runtime (S/Epoch)
10.8
11.2
12.0
12.4
12.5
Memory (MB)
392
811
1392
1722
1861
1911
124
ACC Runtime (S/Epoch)
71.68
72.07
72.39
72,20
72.32
72.19
59.82
CIFARIO
80.7
89.1
100.5
110.9
119.7
241.1
55.0
Memory (MB)
2576
4578
6359
8716
10805
30296
801
6.4
ABLATION STUDY
We present ablation results various structural components of GNN-AK(+) in Appendix A.11 Table 6 shows the performance of GIN-AK- for varying size egonets with k. Table 7 illustrates the added benefit of various encodings and D2C feature. Taable BabbeeBjextensiielly studies the effect of context encoding and D2C GNN-AK+. as they are not explained by Subgraph-I-WL.* Table 9 studies the effect of base model's depth (or expressiveness) for GNN-AK+ with and without D2C.
CONCLUSION
Our work introduces new, general-purpose framework called GNN-As- (GNN-AK) to uplift the expressiveness of any GNN, with the key idea of employing base GNN as kernel on induced subgraphs of the imput graph, generalizing from the star-pattern aggregation of classical MPNNs. Our approach provides an expressiveness and performance boost, while retaining practical scala- bility of MPNNs-a highly sought-after middle ground between the two regimes scalable yet less-expressive MPNNs and high-expressive yet practically infeasible and poorly-generalizing k- order designs. We theoretically studied the expressiveness of GNN-AK, provided concrete design and the more powerful GNN-AK+, introducing SubgraphDrop for shrinking runtime and memory footprint. Extensive experiments on both simulated and real-world benchmark datasets empirically justified that GNN-AK(" (i) uplifts base GNN expressiveness for multiple base GNN choices (e.g. over 1&22 for MPNNs, and over 3-WL for PPGN), (ii) which translates to performance gains with SOTA results on geaph- benchmarks, (iii) while retaining scalability to practical graphs.

---

Published as a conference paper at ICLR 2022
REFERENCES
Ralph Abboud, Ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The surprising power of graph neural networks with random node initialization. In Proceedings of the Thirtieth Inter- national Joint Conference on Artifical Intelligence (IJCAI), 2021.
Sami Abu-EI-Haija, Bryan Perozzi, 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 on machine learn- ing. pp. 21-2911999 PMLR, 2019.
Vikraman Arvind, Frank Fuhlbrücc,, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: subgraph counts and related graph properties. Journal of Computer and System Sci- ences, 113:42-55 59, 2020.
Waiss Azizian and Mare Lelarge. Expressive power of invariant and equivariant graph neural networks. In International Conference on Learning Representations, 2021. URL https:
//openzeview.
gepenneview.nnt//oommiiico wasss///orrmmii-xxxxgX.X...
László Babai, Paul Erdos, and Stanley M Selkow. Random graph isomorphism. SlaM Journal on computing, 9(3):628-66 635, 1980.
Muhammet Balcilar, Pierre Héroux, Benoit Gaüizère Pascal Vasseur, Sébastien Adam, and Paul Honeine. Breaking the limits of message passing graph neural networks. In Proceedings of the 38th International Conference on Machine Learning (ICML). 2021.
Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters. 2021.
Dominique Beani, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Lió. Directional graph networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 748-758, 2021.
Beatrice Bevilacqua, Fabrizio Frasca, Derek Lim, Balasubramaniam Srinivasan, Chen Cai, Gopinath Balamurugan, Michael M. Bronstein, and Haggai Maron. Equivariant subgraph aggregation networks. In International Conference on Learning Representations, 2022. URL https:
//openzeview. wttp://wwwweeeeeoum.eeeeom http://orrmmmm.aaaaxxxRRAR
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and lehman go cellular: Cw networks. In Advances in Neural Information Processing Systems, volume 34, 2021a.
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lió, and Michael Bronstein. Weisfeiler and lehman go topological: Message passing simplicial networks. In Proceedings of the 38th International Conference on Machine Learning (ICML), pp. 1026-
Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006. 09252, 2020.
Jin-Yi Cai, Martin Fürer, and Neil Immerman. An optimal lower bound on the number of variables for graph identification. Combinatorica, 12(4):3894400, 1992.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, 2019.
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. In Advances in Neural Information Processing Sys- tems, volume 33, pp. 13260, 2020.
Leonardo Cotta, Christopher Morris, and Bruno Ribeiro. Reconstruction for powerful graph repre- sentations. Advances in Neural Information Processing Systems, 34, 2021.
10

---

Published as a conference paper at ICLR 2022
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. Proceedings of the Twenty-Ninth International Joint Con- ference Artificial Intelligence. 1JCAI-20, pp. 2126-2132. International Joint Conferences Artificial Intelligence Organization, 2020.
David K Duvenaud, Dougal Maclaurin, Jorge Aguilera-lparraguirre Rafael Gömez-Bonbarelli, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, 2015.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.0080 2020.
Daniel C Elton, Zois Boukouvalas, Mark D Fuge, and Peter W Chung. Deep learning for molecular design-2 a review of the state of the Molecular Systems Design & Engineering. 4(4):828-849, 2019.
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.
M. Fey, J. G. Yuen, and Weichert. Hierarchical inter-message passing for learning on molecular graphs. In ICML Graph Representation Learning and Beyond (GRL+) Workhop, 2020.
Matthias Fey and Jan Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263-1272. PMLR, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855 864, 2016.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 1025-1035, 2017.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural networks, 2(5): -36,, 1989.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint w=Xiv:2005.0068) 2020.
Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. Advances in Neural Information Processing Systems, 33, 2020.
Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks. Advances in Neural Information Processing Systems, 32:7092-7101, 2019.
Thomas N. Kipf and Max Welling- Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Jon Kleinberg, The small-world phenomenon: An algorithmic perspective. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 163-170, 2000.
John Boaz Lee, Ryan A Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. Graph convolutional networks with motif-basee attention. In Proceedings of the 28th ACM International Conference Information and Knowledge Management, pp. 499-508, 2019.
Pan Li, Yanbang Wang. Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. 2020.

---

Published as a conference paper at ICLR 2022
Andreas Loukas.
What graph neural networks cannot learn: depth vs width. In International Con- ference on Learning Representations, 2020a. URL
net forum?
id=B112bp4y Yws)
Andreas Loukas.
How hard is to distinguish graphs with graph neural networks? In Advances in Neural Information Processing Systems, 2020b.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pp. 2156-2167, 2019a.
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019b.
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 5115-5124, 2017.
Federico Monti, Karl Otness, and Michael Bronstein. Motifnet: motif-based graph convolu- tional network for directed graphs. In 2018 IEEE Data Science Workshop (DSW), pp. 225-228.
IEEE, 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, 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 In ICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020a. URL Www. www.graphlearning..k
Christopher Morris, Gaurav Rattan, and Petra Mutzel. Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. Advances in Neural Information Processing Systems, 33, 2020b.
Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pp. 4663-4673. PMLR, 2019.
Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste- Julien, and Ioannis Mitliagkas. A modern take on the bias-variance tradcoff in neural networks. arXiv preprint arXiv:/800.0000 (i1::881000099 2018.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023. PMLR, 2016.
Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130:195-205. 2020.
Dylan Sandfelder, Priyesh Vijayan, and William L Hamilton. Ego-gnns: Exploiting ego structures in graph neural networks. In ICASSP 2021-2021 IEEE International Conference on Acousties, Speech and Signal Processing (ICASSP), pp.
IEEE, 2021.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. In Proceedings of the 202/ SIAM International Conference on Data Mining (SDM), pp. 333-341. SIAM, 2021.
Lei Shi, Yifan Zhang. Jian Cheng, and Hanqing Lu. Skeleton-based action recognition with directed graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7912-7921, 2019.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):122-11953 2014.
12

---

Published as a conference paper at ICLR 2022
Behrooz Tahmasebi and Stefanie Jegelka. Counting substructures with higher-order graph neural networks: Possibility and impossibility results. arXiv preprint arXiv:2012.03174, 2020.
Erik Henning Thiede, Wenda Zhou, and Risi Kondor. Autobahn: Automorphism-based graph neural nets. 2021.
Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. In Advances in Neural Information Processing Systems, 2020.
Boris Weisfeiler. On construction and identification of graphs. In LECTURE NOTES IN MATHE- MATICS. Citeseer, 1976.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International conference on machine learning, pp- 6861-6871. PMLR, 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Yu Philip. A comprehensive survey graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform bad for graph representation? 2021.
Jiaxuan You, Jonathan M Gomes-Selman Rex Ying, and Jure Leskovec. Identity-awar graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 10737-10745, 2021.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. Advances in Neural Information Processing Systems, 30, 2017.
Muhan Zhang and Pan Li. Nested graph neural networks. Advances in Neural Information Process- ing Systems, 34, 2021.
Chen Zhengdao, Chen Lei, Villar Soledad, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 2020.
13

---

Published as a conference paper at ICLR 2022
A APPENDIX
A.1 ADDITIONAL RELATED WORK
Improving Expressiveness of GNNs: Several works other than those mentioned in Sec tackle ex- pressive GNNs. Murphy et al. 2019 achieve universality by summing cermutation-sensstivv func- tions across a combinatorial number of permutations, limiting feasibility. Dasoulas et al. (2020) adds node indicators make them distinguishable, but at the cost of invariant model, while Vignac et al. (2020) further addresses the invariance problem, but at the cost of quadratic time complexity. Corso 2020) generalizes MPNN's default sum aggregator, but is still limited by 1-WL. Beani et al. (2021) generalizes spatial and spectral aggregation with >1-WL expressiveness, but using expensive eigendecomposition. Recently, [Bodnar et al. (202b) introduce MPNNs over simplicial complexes that shares similar expressiveness as GNN-AK, Ying et al. (202T) studies transformer with
above I-WL expressiveness. Azizian & Lelarge (2221) surveys GNN expressiveness work.
Connections to CNN and W-:L: GNN-AK has a similar convolutional structure as CNN, and in fact historically many spatial GNNs are inspired by CNN; see Wu et al. (2020) for a detailed survey. The non-Euclidean nature of graphs makes such generalizations non-trivial. MoNet (Monti et al. 2017) introduces pscudo-coordinates for nodes, while PatchySAN (Niepert et al., 2016) learns to order and truncate neighboring nodes for convolution purposes. However, both methods aim to mimic the formulation of the CNN without admitting the inherent difference between graphs and images. In contrast, GNN-AK, generalizes CNN graphs with base GNN kernel, similar to how a CNN kernel encodes image patches. GNN-AK also shares connections with two variants of k- WL test algorithms: depth-k 1-dim WL. (Cai et al. 1992 Weisfeiler (976) and deep WL (Arvind) et al. 2020p. The former recursively applies 1-WL to all size-k subgraphs, with slightly weaker expressiveness than k-WL, and the latter reduces the number of such subgraphs for the k-WL test. Instead of working on all O(n²*) size-k subgraphs, we keep linear scalability by only applying 1- WL-equivvaent MPNNs to O(n) rooted subgraphs.
A.2 SAMPLING BY SUBGRAPHDROP
Farthes:
[ (3
Sampling
(2 (147
500
Dino Salignahh
Duse SNN
Dare SHA
Figure 2: GNN-AK-S with Subgraphrrop used in training. GNN-AK-S first extracts subgraphs and subsamples m< | subgraphs to cover each node at least R times with multiple strategies. The base GNN is applied to compute all intermediate node embeddings in selected subgraphs. Context encodings are scaled to match evaluation. Subgraph and centroid encodings initially only cxist for root nodes of selected subgraphs. and propagated to estimate those of other nodes.
The descriptions of subgraph sampling strategies are follows. Fig. 2 shows an overview of SubgraphDrop.
Random sampling selects subgraphs randomly until every node is covered R times.
Farthest sampling selects subgraphs iteratively, starting at a random one and greedily selecting each subsequent one whose root node is farthest w.r.t. shortest path distance from those of already selected subgraphs, until every node is covered 2 R times.
Min-set-cover sampling initially selects subgraph randomly, and follows the greedy minimum set cover algorithm to iteratively select the subgraph containing the maximum number of uncov- ered nodes, until every node covered 2 R times.
14

---

Published as a conference paper at ICLR 2022
A.3 PROOF OF THEOREM
Proof. (Xu et al. 2018) proved that with sufficient number of layers and all injective functions, MPNN is powerful 1-WL. Then Eq outputs different vectors for two graphs iff Subgraph- 1-WL" encodes different labels with Co ((+ I-WL(G'ONNG()))) With POOL in 2q also to be injective, MPNN-AK outputs different vectors iff Subgraph-1-WL. outputs different fingerprints for two graphs. Then MPNN-AK is as powerful as Sobgraph-I-WL"
A.4 PROOF OF THEOREM 2
Proof. We first prove that if two graphs are identified as isomorphic by 1-igrapp---WI:: they are also determined as isomorphic by 1-WL.. Then we present a pair of non-isomorphic graphs that can be distinguished by Subgraph-1-WI 1-W but not by 1-WI.. Together these two imply that Subgraph-1- WL is strictly more powerful than 1-WL. Comparing with 2-WL can be concluded from the fact that 1-WL and 2-WL equivalent in expressiveness (Maron et al. 2019a). In the proof we use 1-hop egonet subgraphs for Subgraph-1-WL..
Assume graphs G and H have the same number of nodes (otherwise easily determined as non- isomorphic) and are two non-isomorphic graphs but Subgraph-I-WL determines them as iso- morphie. Then for any iteration t, set ( [IWLLGG E Ve} is the same as set Va). Then there existing an ordering of nodes of ..... og and off .... oN with N = VVll MHrl such that for any node order i l,..., N. (i
{ [I
(N ))). This implies that structure ( and H[N (vff)) are not dis- tinguishable by 1-WL. Hence Star(v?) and Star(u;") are hashed to the same label other- wise the I-WL that includes the hashed result Star(o and Star(y!) can also distin- guish ( and (v")( Then for any iteration and any node with order HASH (Star(u )) HASH (Sarr((("))) implies that 1-WL fails in distinguishing G and H. In fact if we replace the 1-WL hashing function in Sabgraph-1-WL- to a stronger version HASH (HASH( Star (()))) [-W)()))))))))))) this directly implies the above statement.
Subgraph
A
Subgraph
D' Subgraph
Sungraph
Figure 3: Two 4-regular graphs that cannot be distinguished by 1-WL. Colored edges are the dif- ference between two graphs. Two 1-hop egonets are visualized while all other rooted egonets are ignored as they are same across graph and graph B.
In Figure two 4-regular graphs are presented that cannot be distinguished by 1-WL. but can be distinguished by Subgraph-I-WL... We visualize the 1-hop egonets that are structurally different among graphs A and B. It's easy that A's egonet ([) and B's egonet B[N (1)] can be distinguished by 1-WL, as degree distribution is not the same. Hence, and can be distinguished by Subgraph---WL".
A.5 PROOF OF THEOREM 3
Proof. We prove by showing a pair 3-WL failed non-isomorphic graphs can be distinguished by Subgraph-I-WL (see definition of "no less powerful" in Zhengdao et al. (2020): we call A is no/not less powerful than B if there exists pair of non-isomorppic graphs that cannot be distinguished by B but can be distinguished by A.), assuming HASH(-) is 3-WL discriminative. Figure 4 shows two strongly regular graphs that can not be distinguished by 3-WL (any strongly regular graphs are not distinguishable by 3- (Arvind al. 2020)), along with their 1-hop egonet rooted subgraphs.
15

---

Published as a conference paper at ICLR 2022
A's subgraph
B's subgraph
Figure Two non-isomorphic strongly regular graphs that cannot be distinguished by 3- WL.
Notice that all 1-hop egonet rooted subgraphs in A (also in B) are the same, resulting that Subgraph- 1-WL can successfully distinguish A and B if HASH can distinguish the showed two 1-hop egonets. Now we prove that 3-WL can distinguish these two subgraphs. 3-WL constructs coloring of 3- tuples of all vertices the graph. Then, different 3-tuples correspond to different colors or bins in the histogram. As triangle is a unique type of 3-tuple, at iteration 0 of 3-W,. the histogram of all 3-tuples counts the number of triangles in the graph. Notice that A's subgraph has 2 x (2)
graph, and uses the histogram of colors of all k-tuples fingerprint of
8 triangles, and B's subgraph contains 6 triangles. This implies that even at iteration 0, 3-WL can distinguish these two subgraphs. Hence, when HASH(-) is 3-WL expressive, Subgraph- 1-WL can distinguish and B.
Therefore there exists a pair of 3-WI. failed non-isomorphic graphs that can be distinguished by Subgraph-I-WI.
A.6 PROOF OF THEOREM 4
Proof. For any 2 3. Cai et (1992) provided scheme to construct pair of k-WL-ffiled non- isomorphic graphs based on base graph G with separator size k + 1 (more specifically, G can be chosen 3 regular graph with separator size
see Corollary 6.5 in Cai et al. (1992).
We describe the proposed scheme of constructing the two graphs A and B briefly, for details see Section 6 Cai al. (1992). high level, this scheme first constructs by replacing every node (with degree d) in G by carefully designed graph Xa, and then rewires two edges in A to its non-isomorphic counter graph B. Specifically, the small graph X. = (Va, Ed) defined as follows. V4 =A Bg U Ma, where Aa {a.l1 S S d}, Ba [b.11 S i dd.
and Ma = {ms[S S (L...., d}, [S] is even]
(11)
Ea E ai)li E 5) {(ms, b, S}
Hence each vertex v with degree d in G is replaced by graph ( = Xa of size 2d-1 + 2d, including "middle" section Ma of size 2d-1 and pairs of vertices (a;, bx) representing "end- points" of each edge incident with in the original graph G. Let (u, E E(G), then two small graphs (()) and X (u) in are connected by the following. Let (au,v, bu,w), (av,u, be.u) be the pair of vertices associated with (u, v) in X(u) and ((v) respectively, then au,v is connected to daass and bu, connected to by,a. After constructing A, is modified from by rewiring a single edge (u, v) in the original graph G. Specifically, now in B, au,v is connected to be.a and b is connected to a,,a- Cai et al. (1992) proved that and are non-isomorphic, and when base graph G' is degree-3 regular graph with separator size k + 1, A and B are not distinguishable by kLW See a visualization in Figure
We provide several useful lemmas related to graph Xa in the following, which are then used in proving Theorem
Lemma 5 Cai et al. 1992)). X. has exactly 2d-1 automorphisms, and each automorphism is determined by interchanging a; and by for each in some subset S S (1,.....0 d) of even cardinality:
16

---

Published as a conference paper at ICLR 2022
ms
ag
bj
X(u)
X(v)
au
bu.
by.
A
X(u)
X(V)
au.v
Ovu.u
bw.
b
B
Figure 5: A pair of CFI graphs (A and B) zoomed at the (rewired) edge (u, v) of a base graph. The base graph is a d regular graph with separator size k + for k- f--lled case.
Lemma is directly taken from Lemma 6.1 Cai (992)..
Lemma 6. The shortest path distance between and b; in Xa any is exactly 4, and diameter of Xa
Proof. Based on the construction shown Eq 11 for any i, a, and b, are not directly connected, and any middle nodes share no connection. This implies the shortest path between and b, is larger than 3. Let m, be one middle node connected with a;- We construct a new set S' {p, {p.g), with p * i.p E S and $ S. then m. connects with b; based on Eq 11 Additionally, ap connects to both ms and mss which implies the shortest path distance between a; and b, I 4. Hence, the shortest path distance between a, and b; is exactly 4. To show the diameter of X, is 4, it's easy to observe that distance(a;; (a;; by) only decreases when replacing a, with other nodes in Xa (or reverse, replacing b; with other nodes in X.).
Lemma 7. For any 1, k-egonets of az and b; in Xa isomorphic.
Proof. When & 2 Xa(Na(a;)) Xx(N((b.)) X based on Lemma 6 Now for 1 < 3, we analyze the k-hop egonets of a, and b, sequentially. First, Xa(N((a;) and X.(N( are two depth-1 trees with equal number of leaves (middle nodes in Xa), and of course isomorphic.
17

---

Published as a conference paper at ICLR 2022
Similarly, Xa)) and (b)) are two 2 trees with equal number of depth-1 nodes and equal number of leaves, which are also isomorphic. Last, Xa[Ns(a)) and (b)) are the graphs by removing by from Xa and a, from Xd, respectively. It's trivial to observe that they also isomorphic. Combining all cases proves the Lemma.
To prove the main theorem, we visualize the two graphs A and B zoomed at edge (u, u) of base graph in Figure [5 to help understanding. To prove that Subgraph- I-WL with I 4-egonet (we use to prevent notation conflict) cannot distinguish A and B, we mainly analyze the subgraph around du," for both graph A and B. For other subgraphs with different root nodes within / shortest-pathi path-distance around nodes eu av.ux Du,e, bu they follow exactly the same argument. For all subgraphs with other root nodes, it's trivial to observe that there is no difference among two subgraphs in A and B.
We introduce some notation first. Let A[Na(au.)) oI and BiN be the two t-egonet subgraphs around du in A and B respectively. Let Alest Aleft (N((aw,) be the "left" part graph (visualized in be the "right" part graph (visualized in Figure 5) the right side of an,ss excluding au.e) of A(Na(au,.)) Then (a.,(a is reconstructed by connecting (eefeNN(auss
Figure 5 the left side of du,.. include au,e) of A[N and Arisht
and (righ([W with a single and Bright[Ne [N((a, are defined in the same way, such that B [(,)(du.))] is reconstructed by connecting (au,vs b..u) in B.
edge (Au,os a.
When t S 4, we show that there exists an isomorphism that maps A[AG(au.)) )1 to B[Ne(am.e)] We construct this isomorphism by constructing an isomorphism between Ale (N and (o and an isomorphism between (Nighe(Ne ially, the current node ordering in (( and (N, already defines an iso- morphism among them, that is, mapping any os (bi, ms) in ( to as (be, ms) in ( To find an isomorphism between (Nighe[N can easily observe that for t S 3. [Ni ing mapped to a.) to [a[Ni-1(a.]] and Brigh([NG(a,,)) can be 1-to-1 mapped (with by in A being mapped b.) to (bb)] for some i. When t 4, Aright (N.( is mapped to (a]))(a;) with additional 2 nodes and Bright (aG(e,))) is mapped to X3 (ag with addi- tional 2 nodes. Then applying Lemma 7 when t S 4 we can construct an isomorphism between Aright (NG and Nright (N, with a,. in A being mapped bas. in B. We remark that when & = 4, the two additional nodes outside Xz(Na(a;)] and Xa(Na(b:) does not affect- ing applying Lemma 7 Last, the combination of the isomorphism between A (Nee,N))( and Blef"(NN and the isomorphism between (righe(N and Bright[ (a. is actually new isomorphism between (l
and Bright (a first. Triv-
and Bright (a,, one can be 1-to-1 mapped (with au,u in A be-
)] and B[N )], as the edge (uu, (n..) is mapped to edge (du..: by.u). Thus, when 1 S 4, Aa,.(a..)) and B [N((dw.)) are isomorphic and (a,, = (ASH(B(NG(a...)))
no matter what HASH(-) function is used. Applying the same argument to all other pairs of subgraphs in A and B implics that the histogram encodings of A and B are the same. Hence Subgraph-1-Wi with < cannot distinguish the two graphs A and B that are h WL-falleed for any h 2 3.
We remark that the theorem doesn't 't imply that Subgraph---WL. with t 2 5-egonet can distinguish A and B. This should depend on the base graph. We give an informal sketch. Suppose that for & 2 5, the left part (lefe[N (i) and right part Aright (right(N. (a...)) are only connected through (Am. (w,u); and A Aright[N (au..v)) that is, removing (Ru,v: ).,,)) from A (a,,(au. resulting in A mulliple times with mapping some ap.a in A to being disconnected. Then we can apply Lemma multiple
by. in B and by.,. in A to an in B. until this kind of switches reach the boundary of A[Ne(au,w)) resulting in an isomorphism between A[M (a.,,)) and [[N)(a..))] We refer the reader to Lemma 6.2 in Cai et al. 1992), which also uses this line of argument.
A.7 PROOF OF PROPOSITION !
Proof. The proof is by contradiction. Let G and H be two non-isomorphic graphs and |Va |Vrr (if graph sizes are different then Subgraph- Prop. is incorrect, i.e. Subgraph-1-Wi 1-WL cannot distinguish G and H even provided that the two conditions (1) and (2) are satisfied. Then, for any iteration of Subgraph-1- WLL G and H would have the same histogram of subgraph colors. Now we focus iteration O. Formally, let color
can trivially distinguish them). Now suppose that
18

---

Published as a conference paper at ICLR 2022
C HASH( and ch, = (AASH(HNN(o))) for node order (u,² maps index i node in G). According to Condition (1): for any node reordering off ...., UN and of ,..,,, " Nx* Bi E [1, max(Ng. NH) that G[N and H[Nx(uf)) are non-isomorphic, then we know that li that G[N((u()) and (( )] are non-isomorphic, hence ب * c since by Condition (2) HASH can distinguish these two subgraphs. However as two graphs have the same histogram of subgraph colors, there must be a j & such that c = cHf Cej and cC
new node order m by swapping "f and of. resulting <,, = alf c.j = el Then we can create a
Cm. and cm.j Cm.... This process
can be repeated until having new node order such that Vi 1,... |Val, GH, Gur. As HASH
discriminative enough according to Condition (2), this implies Vi 1,.... [Val. G[A& (wff) and H [Ne( )] are isomorphic, which contradicts with Condition (I). Thus, Prop. | must true. C
A.8 PROOF OF PROPOSITION 2
Proof. When pair of non-isomorphic graphs and H cannot be distinguished by GNN-AK+, for any layer 1, the histogram of h in G and H in Eq. should be the same. Which implies that for any layer (, the histogram of (1)) in G and H in Eq. should be the same. Then GNN-AK cannot distinguish G and H. So for any pair of non-isomorphic graphs, GNN-AK cannot distinguish them
if GNN-AK* cannot distinguish them. Thus GNN-AK is more powerful than GNN-AK.
A.9 DATASET DESCRIPTION & STATISTICS
Table 5: Dataset statistics.
Dataset
Task Semantic
# Cls./Tasks
Gruphs
Ave. Nodes Ave. Edges
EXP
Distinguish 1-WL failed graphs
2
1200
44.4
110.2
SR25
Distinguish 3-WL failed graphs
15
15
25
300
CountingSuh. Regress num, of substructures
1500 / 1000 / 2500
18.8
62.6
GraphProp. Regress global gruph properties
5120 640 / 1280
19.5
101.1
ZINC-12K
Regress molecular property
10000 / 1000 1000
23.1
49.8
CIFAR10
10-class classification
10
4,5000/ / 5000 / 10000
117.6
1129.8
PATTERN
Recognize certain subgraphs
2
10000 / 2000 2000
118.9
6079.8
MolHIV
1- 1-way binary classification
32901 4113 4113
25.5
54.1
MolPCBA
128-way binary classification
128
350343
43793 43793
25.6
55.4
MUTAG
Recognize mutagenic compounds
2
188
17.93
19.79
PTC-MR
Classify chemical compounds
2
344
14.29
14.69
PROTEINS
Classify Enzyme & Non-enzyme
2
1113
39.06
72.82
NCI1
Classify molecular
2
4110
29.87
32.30
IMDB-B
Classify movie
2
1000
19.77
96.53
RDT-B
Classify reddit thread
2
2000
429.63
497.75
A.10
EXPERIMENTAL SETUP DETAILS
To reduce the search space, we search hyperparameters in a two-phase approach: First, we search common ones (hidden size from [64, 128], number of layers L from [2,4.5,6], (sub)graph pooling from [SUM, MEAN] for each dataset using GIN based on validation performance, and fix it for any other GNN and GNN-AK(+). While hyperparameters may not be optimal for other GNN models, the evaluation is fair as there is no benefit for GNN-AK(+). Next, we search GNN-AK(+) exclusive ones (encoding types) over validation set using GIN-AK(+)) and keep them fixed for other GNN-AK(+). We use a l-layer base model for GNN-AK(*) ), with exceptions that we tune number of layers of base model (while keeping total number of layers fixed) for GNN-AK in simulation datasets (presented in Table [). We use 3-hop egonets for GNN-AK(*)) ), with exceptions that CIFAR10 10 uses 2-hop egonet due to memory constraint; PATTERN and RDT-B use random walk based subgraph with walk length=10 and repeat times=5 as their graphs are dense. For GNN-AK(*)-SS It = 3 is set as default. We use farthest sampling for molecular datasets ZINC, MolHIV, and MolPCBA; to speed up further, random sampling is used for CIFAR10 whose graphs are K--N graphs; min-set-cover sampling is used for PATTERN to adapt random walk based subgraph. We use Batch Normalization Adam with learning rate 0.001 and
and ReL.U activation in all models. For optimization
19

---

Published as a conference paper at ICLR 2022
weight decay 0. All experiments are repeated 3 times to calculate mean and standard derivation. All experiments are conducted on RTX-A6000 GPUs.
A.11 ABLATION STUDY
We present ablation results on various structural components of GNN-AK. Table shows the perfor- mance of GIN-AK for varying size egonets with k. We find that larger subgraphs tend to yield im- provement, although runtime-perte nuntine-performacce performance trade-off may vary by dataset. Notably, simply 1-egonets enough for CIFARIO to uplift performance of the base GIN considerably.
Table 6: Effect of various k-egonet size.
Table Effect of various encodings
Ablation of GIN-AK ZINC-12K
CIFARIO
& of GIN-AK+
ZINC-12K
CIFARIO
Full
0.080 + 0.001
72.19 + 0.13
GIN
0.163 1 0.004
59.82 0.33
w/o Subgraph encoding
0.086 i 0.001
67.76 1: 0.29
k == 1
0.147 + 0.006
71.37 +: 0.28
w/o Centroid encoding
0.084 1 0.003
72.20 1 0.96
& ==2 2
0.120 + 0.005
72.19 :: 0.13
w/o Context encoding
0.088 + 0.003
69.25 + 0.30
== 3
0.080 + 0.001
0OM
w/o Distance-to-Cennne
0.085 + 0.001
71.91 + 0.22
Next Table 7 illlstraats the added benefit of various node encodings. Compared to the full design, eliminating any of the subgraph, centroid, or context encodings (Equs (3) (5) yields notably inferior results. Encoding without distance awareness is also subpar. These justify the design choices in our framework and verify the practical benefits of our design.
As GNN-AK* is not directly explained by Subgraph- 1-WI" (though D2C is supported by Subgraph- 1-WL, by strengthening HASH), we conduct additional ablation studies over GNN-AK* with differ- ent combinations of removing context encoding and D2C, shown in Table g Note that all experi- ments in Table are using a I-layer base GIN model. We summarize the observations as follows.
For real-world datasets (2I,C-12K, CIFARIO), We observe that the largest performance improve- ment over base model comes from wrapping base GNN with 2 (the performance of GIN-AK), while adding context encoding and D2C monotonically improves performance of GNN-AK*. For substructure counting and graph property regression tasks, we observe D2C significantly in- creases the performance of GIN-AK+ w/o Ctx (supported by the theory of Subgraph-1-W where the HASH is required to be injective). Specifically, the cost-free D2C feature enhances the expres- siveness of the base I-layer GIN model (similar to the benefit of distance encoding shown in Li lt al. (2020)) resulting in a more expressive GNN-AK*, which lies between Subgraph-1-Wi and We leave the exact theoretical analysis of D2C's expressiveness benefit in fu- ture work. Notice that GIN-AK improves the performance over the base model but not in a large margin, we next show this is due the insufficiency of the number of layers of base GIN.
Subgraph-I-Wi
Table 8: Study GNN-AK without context encoding (Ctx) and without distance-to-centrood (D2C). Base model is 1-layer GIN for all methods.
Z2KC-12K CIFARIO EXP SR25 Counting Substructures (MAE) (MAE)
Graph Properties (MAg))(MEE)
Method
(ACC)
(ACC) (ACO) Triangle Tailed Tri.
Star 4-Cycle
IsConnected Diameter
Radius
GIN
0.163
59.82
50%
6.67%|
0.3569
0.2373
0.0224 0.2185
-1.9239
-3.3079
-4.7584
GIN-AK
0.094
67.51
100%
6.67%
0.2311
0.1805
0.0207 0.1911
-1.9574
-3.6925
-5,0574
GIN-AK+ + wio Cix
0.088
69.25
100%
6.67%
0.0130
0.0108
0.0177
0.0131
-2,7083
-3.9257
-5.2784
GIN-AK+ w/o D2C
0.085
71.91
100%
6.67%
0.1746
0.1449
0.0193
0.1467
-2.0521
-3.6980
-5.0984
GIN-AK
0.080
72.19
100%
6.67%
0.0123
0.0112
0.0150 0.0126 -2.7513
-3.9687
-5.1846
I the base model must be discriminative enough such that for bubgraph-I-Wi with k-egonet to enjoy expres- siveness benefits. In addition to using D2C to increase the expressiveness of base model, another way is to practically increase the number of layers of the base model (akin to increasing the number of iterations of 1-WL, as in the definition of Subgraph-1-Wi number of layers in GNN-AK+, with and without D2C in Table
According to Prop.
HASH(GIN (c()) # HASH(H(N,
We study the effect of base model's
Firstly, GNN-AK+ with D2C is insensitive to the depth of base model, with 1-layer base model being enough to achieve great performance in counting substructures and the best performance
20

---

Published as a conference paper at ICLR 2022
Table 9: Study the effect of base model's number of layers while keeping total number of layers in GNN-AK fixed. Different effect is observed for GNN-AK and GNN-AK without D2C.
Method
GIN-AK's #Layers
Base GIN's
Counting Substructures (MAE)
Graph Properties (0
#Layers
Triangle Tailed Tri.
Star
4-Cycle
IsConnected Diameter Radius
GIN
0
6
0.3569
0.2373
0.0224
0.2185
-1,9239
-3.3079
-4.7584
6
1
0.2311
0.1805
0.0207
0.1911
-1.954
-3.6925
-5.0574
GIN-AK
3
2
0,1556
0.1275
0.0172
0.1419
-1,9134
-3,7573
-5.0100
2
3
0.1064
0.0819
0.0168
0.1071
-1.9259
-3,7243
-4.9257
6
0.0934
0.0751
0.0216
0.0726
-1.9916
-3,6555
-4.9249
6
1
0,1746
0,1449
0.0193
0.1467
-2.0521
-3,6980
-5.0984
2
0.1244
0.1052
0.0219
0.1121
-2.1538
-3,7305
-4,9250
GIN-AK w/o D2C
2
3
0.1021
0.0830
0.0162
0.0986
-2,2268
+3,7585
-5.1044
0.0885 6
0.0696
0.0174
0.0668
-2,0541
-3.6834
.4.8428
0.0123
0.0112
0.0150
-2.7513
-3,96877
-5.1846
3
2
0.0116
0.0100
0.0168
0.0122
-2.6827
-3,8407
-5.1034
GIN-AK+ with D2C
0.0119
0.0102
0.0146
0.0127
-2.6197
+3,8745
-5.1177
0.0131
0.0123
0.0174
0.0162
-255938
-3.7978
-5.0492
in regressing graph properties. We hypothesize that D2C-enhanced 1-layer GIN base model is discriminative enough for subgraphs in the dataset, and without expressiveness bottleneck of base model, increasing GNN-AK*'s depth benefits expressiveness, akin increasing iterations of Subgraph-I-WL. Besides, unlike counting substructure that needs local information within subgraphs, regressing graph properties needs the graph's ' global information which can only be accessed with increasing GNN-AK**S 's (outer) depth.
Secondly, GNN-AK(*) without D2C suffers from a trade-off between the base model's expressive- ness (depth of base model) and the number of GNN-AK(+) layers (outer depth). which is clearly observed in regressing graph properties. We hypothesize that without D2C the I-layer GIN base model is not discriminative enough for subgraphs in the dataset, and with this bottleneck of base model, GNN-AK ONN-AK((*) cannot benefit from increasing the outer depth. Hence the number of layers of the base model are important for the expressiveness of GNN-AK(") when D2C is not used.
21

---

Published as a conference paper at ICLR 2022
A.12 ADDITIONAL RESULTS ON TU DATASETS
We also report additional results on several smaller datasets from TUDataset (Morris et al. 2020a), with their statistics reported in last block of Table 5 The training setting and evaluation procedure follows Xu ct al. (2018) exactly, where we perform 10-fold cross-validation and report the average and standard deviation of validation accuracy across the 10 folds within the cross-validation. We take results existing baselines directly from Bodnar et al. (2021a) with their method labeled as CIN, for references all baselines see [Bddnar al. (202 The result is shown in Table I0
Table 10: Results TU Datasets. First section contains methods of graph kemelss, second section has GNNs, and third is the method in Bodnar et al. (2021a). The top two are highlighted by First, Second, Third.
Dataset
MUTAG
PTC
PROTEINS
NCII
IMDB-B
RDT-B
RWK
79.2+2.1
55.9:0.3
59.6:0.11
day
N/A
GK (A:
81.41.7
55.7:10.5
71.410.31
62.510.33
N/A
PK
76.0+2.7
59.5+2.4
73.7+0.77
82.5+0.5
N/A
N/A
WL kernel
90.41...7
59.914433
75.0.1..1
86.0
73.8.13.9
81.033.1
DCNN
N/A
N/A
61.31116
56,6#1.0
49.1
N/A
DGCNN
85.8+1.8
58.6+2.55
75.5++0.9
74.4+0.5
70.0+0..
N/A
IGN
13.9
58.5+6.99
76.6+55.5
74.3+2.7
72.0+5.5
N/A
GIN
89.4
64.6.17.00
76.2112.8
82.711.7
75.115..1
9.5
PPGNs
9.06
66.2466.6
77.2+14.7
83.2+1.11
73.0+-5.8
N/A
Natural GN
8..421.6
66.811.77
71.71100
82,41133
73.5+2.00
N/A
GSN
92.2 = 7.5
68.2 1 7.2
5.0
8..
77.8 3.3
N/A
SIN
N/A
N/A
76.4 3.3
8.1
75.6 3.2
92.2 1.0
CIN
92.7 6.1
68.2 = 5.6
77.0 + 4.3
83.6 1.4
75.6 3.7
92.4 + 2.1
GIN-AK
91.3 7.0 67.7 = 8.8
77.1 + 5.7
85.0 2.0
75.0 4.2
94.8 0.8
We mark that the performance of GIN-AK* over IMDB-B is not improved because each graph in the dataset is egonet, hence all nodes have the same rooted subgraph the whole graph. The performance of MUTAG and PTC is very unstable, given these datasets are too small: 188 and 344, respectively, and the evaluation method is based average 10 validation curves 10 folds.
22


Reviews:
[{"review_id": "nYU2SkD8eMs", "reviewer": "Reviewer_KytV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "**Strengths**\n1. Simple approach\n2. Good experimental results \n3. Good cover of related work \n\n**Weaknesses**\n1. Limited selection of benchmark datasets used, e.g., large-scale graphs from OGB and graphlearning.io missing\n2. Theoretical statements for 2-WL are misleading. They simply consider the weaker version of the 2-WL, which is known to be equivalent to the 1-WL (see, e.g., https://arxiv.org/abs/2104.14624). This should be clearly stated in the main paper.  \n3. Proof of Theorem 3 is not sufficient.\n\n**Remark for Theorem 3**\nThe prove seems to show that there exist pairs of graphs 3-WL cannot distinguish but their architecture can. The proof is not rigorous enough and of a very handwavey nature. **However**, it does not show that their architecture is always at least as powerful. This also has implications for Corollary 3.1. \n\n**Remarks**\n1. \"Leman\" is the preferred spelling, see https://www.iti.zcu.cz/wl2018/pdf/leman.pdf\n2. You might also want to cite (Morris et al., 2019) when mentioning the relationship of 1-WL and GNN, see also https://arxiv.org/abs/2104.14624 for a comparison of the results  \n3. The statement that 1-WL can distinguish almost all graphs needs more context. The result depends on the sizes of the graphs. \n4. In  Section 2 you might want to discuss \n- https://arxiv.org/abs/2010.01179\n- https://arxiv.org/pdf/2101.10320.pdf (also extracting k-hops subgraphs)\n5. In Section 3.1 you should use notation for multisets, e.g., {{ ...}}\n6. In Section 3.2, you should state the k needed for the results. \n7. In Section 4, the description of Emb is clumsy and hard to parse\n8. The complexity analysis is not very meaningful. You must derive the cardinality V_U and E_U, which, in general, will depend exponentially on k. \n\n", "summary_of_the_paper": "The paper deals with supervised learning with graphs, specifically graph-level tasks. The paper proposes an algorithm to overcome the expressive limits of the standard GNNs, which are upper-bounded by the 1-WL. The main idea of the paper is to, for each node v, extract the subgraph induced by nodes of at most distance k to node v, and then deploy a GNN on top of each of these subgraphs. Further, the authors study the gains of the expressive power of this architecture compared to the 1-, 2-, 3-WL, and k-WL.  \n\nMoreover, the authors propose a subgraph sampling strategy to speed up the computation. \n\nThe proposed method is evaluated on large benchmark datasets, mostly stemming from the molecular domain, reporting good performance boosts compared to standard GNN architectures.", "summary_of_the_review": "The paper proposes a simple and meaningful architecture to enhance the expressive power of most standard GNN architecture. \nThe experimental results are promising, however, the authors only consider a limited set of benchmark datasets. \n\nHowever, there are some problems with the theoretical contributions, see above. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "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": "d12BUjEDGoI", "reviewer": "Reviewer_oHnh", "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": "# Strengths \n\n- The motivation behind the proposed method is very clearly described in the introduction. \n- The high-level insights described at the beginning of Section 3 give a good overview of the paper before describing the details. \n- The proposed subgraph 1-WL procedures are a nice tool for analyzing the expressive power of the proposed models. In particular, I like the idea of defining an isomorphism test that relies on WL as a subroutine (i.e. the 1-Subgraph-1-WL*) and thus \"uplifting\" the expressive power of WL.\n - The theoretical analysis performed on top of these newly proposed isomorphism tests contains useful results. Although some of the results are relatively obvious, they help provide a description of the capabilities of the proposed framework. \n- In particular, I think Theorem 4 is the most original since it manages to establish a connection with all the tests in the k-WL hierarchy for $k \\geq 3$.  \n- The complexity analysis section is compact and clear. Like other recent papers, the proposed method manages to benefit from cutting through the k-WL hierarchy by achieving more advantageous complexity tradeoffs compared to k-WL based approaches. \n- I like that the authors have taken a careful approach with the subgraph sampling rather than simply implementing a naive sampling approach. The proposed sampling takes into account how the nodes are covered by different subgraphs and the method itself is adapted to avoid potential complications at testing time when no sampling is used.\n- The experiment in Table 1 is very nice and clearly demonstrates the claimed capacity of the framework to \"uplift\" existing GNNs. It is also encouraging that the framework brings improvements irrespective of the base GNN that was tried. \n- The results for the real-world experiments are good. Although, some stronger baselines could have been included (see the next section) \n- The ablation study in Table 4 provides a useful overview of the tradeoff between computational expenses and performance. \n\n# Weaknesses \n\n- There seems to be a discrepancy between the high-level view of the GNN-AK model provided in Equation (2) and the actual implementation in Equation (6). The context representation from Equation (6) is based on subgraphs rooted at neighbours of node v and therefore it might be based on information that is outside the subgraph of v, thus becoming misaligned with Eq(2) and the proposed subgraph WL equations. \n- The subgraph sampling strategy is often referred to as a sort of Dropout for GNNs. However, the evidence that this subgraph sampling strategy improves generalisation in any way is weak. Table 4, which is studying this does not provide any standard errors around the provided scores. This is particularly important as more subsampling induces more noise into these measurements. It is therefore very difficult to assess the statistical significance of these scores. Even ignoring the lack of error bars, on ZINC no level of subgraph sampling produces improvements in the reported MAE compared to the full GIN-AK and in the case of CIFAR-10, the differences are far from being scientifically significant. \n- While I understand the positives that subgraph sampling brings, training-time computationally improvements are generally not so useful. Ideally, one would like to move as much of the processing from inference time to training time because that is the main setting where latency and computational constraints start to matter. However, the model does need to use all the subgraphs at inference time. \n- A stronger baseline for ZINC and MOLHIV exists: *Weisfeiler and Lehman Go Cellular: CW Networks (NeurIPS 2021)* (https://arxiv.org/abs/2106.12575). In fact, this work is also particularly relevant for this paper since it is also relying on induced subgraphs for \"uplifting\" existing GNNs, but it does so in a different way. \n\n# Minor weaknesses \n\n- In the introduction (last paragraph of page 2), the paper claims that sufficient conditions are derived under which GNN-AK can distinguish two graphs. This is misleading because these sufficiency conditions are only conjectured on page 1. While some empirical evidence is provided in favour of this conjecture, it does not represent a definitive result. \n- It is unclear to me why Conjecture 1 is a conjecture and not an actual result. On a first look, it seems rather immediate that the assumptions of the Conjecture imply distinguishability (which doesn't mean that is indeed the case). What I am trying to say is that there should be at least a brief description of the difficulties surrounding the proof of the result and what the main impediments are. \n- Nit: In Table 2 it is not immediately clear which numbers correspond to the outer vs inner loop. I suggest reformatting the table to make this more clear. ", "summary_of_the_paper": "The paper introduces a framework that can extend the expressive power and empirical performance of a base GNN by using an induced subgraph-based local aggregation method that substitutes the conventional multiset aggregation GNNs typically perform. The authors provide theoretical analysis for this framework, study its scalability for practical applications, and presents good empirical results. ", "summary_of_the_review": "The strengths of the paper outlined above generally outweigh the weaknesses, so I am therefore recommending the paper for weak acceptance for now. I am looking forward to the discussion period and I am willing to change my score once my points are addressed. \n\nEDIT: I have raised my score to 8. ", "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": "MLEnXVk3VTO", "reviewer": "Reviewer_MkR2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "**Strengths**:\n-\tThe paper is nicely written, has a good flow and is easy to follow.\n-\tThe idea of ego-nets is simple and straightforward to implement. Contrary to other GNNs that improve expressivity using some kind of structural property (e.g., Bouritsas et al., arxiv’20,  Thiede et al., NeurIPS’21, Barceló et al., NeurIPS’21 and others), GNN-AK requires fewer hyperparameters to be selected by the user (mainly the size $k$ of the ego-net).\n-\tPractical solutions that improve scalability without sacrificing performance are proposed.\n-\tThe experimental section is extensive and the method obtains competitive results in many datasets, which is a good indication that the proposed architecture will work well in practice.\n\n**Weaknesses**:\nMy main concerns about this paper have to do with (1) its novelty, (2) the fact that the practical instantiation contains multiple choices that are not justified from the theory and obfuscate the actual underlying reason for the good empirical performance. In more detail:\n\n1. **Novelty**: The idea of using ego-nets to improve the expressive power of GNNs is not completely new. As the authors also mention, this idea has been used several times in the past. For example, a reference that the authors have missed, “Identity-aware Graph Neural Networks”, You et al., AAAI’21, is also closely related and it goes one step further in terms of the theoretical results, showing that by identifying the root note in each ego-net (implicitly present in this work – via the distance to centroid), one can also count cycles. Other examples are e.g., k-hop GNNs, Nikolentzos et al., ’20 with also theoretical results orthogonal to this work (showing that their GNN can regress certain graph properties)  and Ego-GNNs, Sandfelder et al.’20. Although there are differences between the above, the main idea is similar, therefore I would like to ask the authors to explain what makes their method significantly different. This brings me to my second concern.\n2. **Architecture instantiation**: \n    -   The current arguments the authors used to differentiate their work from other related mainly boil down to architecture/implementation details (e.g., they write “unlike GNN-AK, they only propose to use a final root node embedding” and “can be viewed as a special case of GNN-AK, which only computes a context embedding (one of three types of embeddings GNN-AK uses)”), but their theoretical results do not seem to advocate for the necessity of these architectural choices. \n    -  Further, more ad hoc choices that do not seem to result from the theory are presented later in the paper (3 types of embeddings, gating mechanism with the distance to centroid, etc.). This begs the following question: What is the actual reason for the arguably good empirical results? Is it due to the improved expressivity or due to engineering?\n    -\tAlso, note that some of the choices of the authors (random-walks to extract the subgraphs, dropout on the ego-nets) introduce randomness in the algorithm which (1) sacrifices permutation equivariance (which is not necessarily bad), but (2) improves expressivity (e.g., see related works that use random features or other randomized algorithms for GNNs), which might be also a confounding factor.\n\n3. **Theory**: \n   - The theoretical results up to Corollary 3.1 are similar to previous work (e.g., Bouritsas et al., arxiv’20, Bodnar, Frasca, Wang et al., ICML'21, Bodnar, Frasca et al., NeurIPS'21 and others). Unfortunately, the bar has been set higher in research on GNN expressivity, since currently, most architectures that are proposed enjoy these properties (more expressive than 1-WL, no less expressive than 3-WL – shown by counterexample), hence in order for the theoretical evidence to be convincing, in my opinion, further arguments are required (e.g., substructure counting, or graph property prediction - possibility/impossibility results). \n   - The authors do provide a novel theoretical argument in Theorem 4, which is good, however, its practical consequences are not clear to me (I don’t understand the following sentence: “This opens a future direction of generalizing rooted subgraph to general subgraph (as in k-WL) while keeping number of subgraphs in $O(|\\mathcal{V}|)$.”). \n   - More clarity is needed in Conjecture 1 with respect to the magnitude of $k$. If it is $O(n)$, then this resembles the reconstruction conjecture (Kelly, 1957), if it is $O(1)$, then this would imply a polynomial-time solution to isomorphism, hence it is unlikely to hold. \n   - Can you theoretically compare ego-net enabled GNNs with other modern GNNs, such as the ones that use substructures or other structural properties to improve expressivity? Note that these methods can also distinguish 3-WL failed graphs, without necessarily resorting to an algorithm of higher computational complexity during training, which is the condition of your Theorem 3. \n\n**Other comments**:\n- **Experiments**:\n   - What version of GNN-AK do you use in Tables 1 and 2? Is it the vanilla GNN-AK or it contains the instantiation details mentioned in the previous sections?\n   - Minor: I suspect that this method might suffer from scalability issues when dealing with denser graphs than those you tested on (e.g., social networks) since its complexity might grow with $O(n^2)$. Have the authors considered testing on this domain?\n- The following claim in the intro should be relaxed:  “We also give sufficient conditions under which GNN-AK can successfully distinguish two non-isomorphic graphs.”. As far as I understood, this is based on a conjecture rather than a proven fact.\n-  Theorem 4: (1) Notation clash ($k$ is now used for k-WL and $d$ for the num of hops of the ego-net) and (2) there are clarity issues in the proof.  I am not sure I follow the claim “and the rewiring of constructing its non-isomorphic counter graph has picked two edges that cannot be included by any k-hop ego-nets with k ≤ 4”. Is that a known fact from the original CFI paper? Maybe the authors would like to expand their explanations. Does this proof imply that with $k\\geq4$ you might be able to distinguish two CFI graphs?\n\n### --------------------- After rebuttal ---------------------\nI have increased my score slightly, this time voting for weak acceptance. Please see my final comment for a justification, as well as the discussion with the authors for a detailed explanation of the remaining concerns.\n\n\n", "summary_of_the_paper": "This manuscript presents a general-purpose technique to improve GNN expressivity, dubbed as GNN-AK, that replaces the conventional neighbourhood/star-like aggregation (multi-set of neighbour embeddings) with an ego-net level aggregation. In particular, at each layer of GNN-AK, the authors first extract all $|\\mathcal{V}|$ ego-nets of the original graph, then they apply a GNN on each one of them, and finally, they collect their outputs into node-wise representations.  The expressive power of different variants of their model is theoretically analysed (more expressive than 1-WL when the ego-net aggregation is as expressive as 1-WL, and no less powerful than 3-WL, when the ego-net aggregation is as expressive as 3-WL) and a series of design choices for a practical instantiation is provided. The authors extensively evaluate their method on both synthetic and real-world datasets and ablate the influence of some of the moving parts in the overall performance.", "summary_of_the_review": "The main idea in this paper is simple, easy to implement and the empirical results are good. However, (1) this very idea is not that novel since ego-nets have been used in the past,  (2) most theoretical results are similar to prior work and do not make a particularly compelling case, while other works on ego-nets have gone further in that respect and (3) the multitude of engineering choices obscures the root causes for the improved empirical performance. Therefore, I am leaning towards rejection, but I would encourage the authors to clarify their position w.r.t. the above and make their statements more clear since it seems that ego-nets have good potential in terms of practical performance", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-oWAXgOitY3", "reviewer": "Reviewer_LzXw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "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": "Strengths:\n1. The proposed GNN-AK framework is novel for uplifting the expressiveness of GNN. It is an interesting idea to use GNN as a kernel on the induced subgraph. The design for both the GNN-AK layer and subgraph sampling are reasonable. \n2. The proofs of theorems appear to be correct.\n3. This paper provides a comprehensive experimental study, including both qualitative analysis and quantitative results, to show the effectiveness of GNN-AK framework. The ablation study shows that each component in the framework works well.\n\nWeaknesses:\n1. This paper didn’t explain how it gets d_{i|j}^{(l)} from distance-to-centroid. The Sigmoid function was used to combine the D2C feature.  It is counter-intuitive if a node with a larger D2C gets a higher weight during aggregation. It would be better to provide more details on this.\n2. The dataset statistics are missing.\n3. What would be the performance of the proposed method when a different way of combining the centroid, subgraph, and context encoding is used? \n4. Some recent SOTA methods are missing:\nBodnar, Cristian, et al. \"Weisfeiler and lehman go cellular: Cw networks.\" arXiv preprint arXiv:2106.12575 (2021).\nYing, Chengxuan, et al. \"Do Transformers Really Perform Bad for Graph Representation?.\" arXiv preprint arXiv:2106.05234 (2021).\n", "summary_of_the_paper": "The paper proposes GNN-AK, a framework that can use GNN as a kernel to encode local features. It generalizes the local neighbour aggregation in Massage Passing Neural Networks (MPNN) from a star-like pattern to a more flexibly defined subgraph. The paper also provides theoretical support that shows the superiority of the proposed method to 1&2-WL in terms of expressiveness.  The experimental results demonstrate that the proposed method outperforms other SOTA baselines on 7 different datasets.", "summary_of_the_review": "This paper puts forward a novel framework that can easily plug different kinds of GNN and improve the expressiveness. The proofs and experimental results well support the proposed method. Some concerns are listed above.", "strength_and_weaknesses": "", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: In standard message-passing GNNs (MPNNs), one step at any node u involves receiving state/embedding information from all of u’s neighbors, and then updating u’s state as a function of these messages and of u’s own current state. Thus, the communication pattern at every step is that of a star topology (a graph with u at its “center”, and with u connected to all its neighbors, and with no other edges). However, it is well-known that the expressive power here is bounded by that of the 1st order Weisfeiler-Leman isomorphism test (1-WL). This paper then takes the natural step of generalizing the star topology to more general ones (e.g., k-hop egonets, the subgraph induced by the nodes of distance at most k from u). It is shown that this framework is strictly more powerful than 1-WL and 2-WL (however, as pointed out by a referee, this is actually a weaker version of 2-WL that is equivalent to 1-WL), and is at least as powerful as 3-WL. Subgraph-sampling approaches that improve efficiency are also introduced. It is shown that this method beats the SOTA for some number of well-known graph-ML problems.

It looks like this paper has a very strong overlap with the NeurIPS 2021 paper "Nested Graph Neural Networks" (https://openreview.net/forum?id=7_eLEvFjCi3). Both papers use rooted subgraphs (k-hop ego-nets) to replace the k-hop rooted subtrees in traditional GNNs, and both use a base GNN over the rooted subgraph to compute a subgraph representation as the node representation while pooling the node representations into a graph representation. Both papers claim to outperform 1-WL in expressive power; both use distance to center node in order to enhance subgraph node features. The authors are urged to compare and contrast the two papers in the camera-ready version.
Decision: Accept (Poster)