Year: 2021

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-Leman 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.

heading: 1 INTRODUCTION
text: Graphs are permutation invariant, combinatorial structures used to represent relational data, with wide applications ranging from drug discovery, social network analysis, image analysis to bioinformatics (Duvenaud et al., 2015; Fan et al., 2019; Shi et al., 2019; Wu et al., 2020). In recent years, Graph Neural Networks (GNNs) have rapidly surpassed traditional methods like heuristically defined features and graph kernels to become the dominant approach for graph ML 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 a recursive aggregation mechanism where each node aggregates information from its immediate neighbors repeatedly. However, unlike simple multi-layer feedforward networks (MLPs) which are universal approximators of continuous functions (Hornik et al., 1989), MPNNs cannot approximate all permutation-invariant 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-WL equivalent GNNs are not expressive, or powerful, enough to capture basic structural concepts, i.e., counting motifs such as cycles or triangles (Zhengdao et al., 2020; Arvind et 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 (Morris et al., 2019; 2020b) try to incorporate k-WL in the design of more powerful GNNs, while others approach k-WL
expressiveness indirectly from matrix invariant operations (Maron et al., 2019a;b; Keriven & Peyré, 2019) and matrix language perspectives (Balcilar et al., 2021). However, they require O(k)-order 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( n 2)) graphs on n vertices, Babai et al. (1980)) can be distinguished by 1-WL challenge the necessity of developing such extremely expressive models. In a 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 as identifiers (Loukas, 2020a), subgraph counts (Bouritsas et al., 2020), distance encoding (Li et al., 2020), and random features (Sato et al., 2021; Abboud et al., 2021). However, these methods either focus on 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 korder GNNs, and the limited expressiveness yet high scalability of MPNNs. Specifically, we propose a general framework that serves as a “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 to the star subgraph (comprised of the central node and edges to neighbors). We propose a 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 a GNN to encode a locally induced encompassing subgraph, as shown in Fig.1. 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 a 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 (GNN As Kernel). We show theoretically that GNN-AK is strictly 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 implementation 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 a subgraph sampling strategy inspired by Dropout (Srivastava et al., 2014) to drastically reduce this overhead (1-3× in practice) without hurting performance. We conduct extensive experiments on 4 simulation datasets and 5 well-known real-world graph classification & regression benchmarks (Dwivedi et al., 2020; Hu et al., 2020), to show significant and consistent practical benefits of our approach across different MPNNs and datasets. Specifically, GNN-AK+ sets new state-of-the-art performance on ZINC, CIFAR10, and PATTERN – for example, on ZINC we see a relative error reduction of 60.3%, 50.5%, and 39.4% for base model being
GCN (Kipf & 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+), a general
framework which uplifts any GNN by encoding local subgraph structure with a 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 improvements as well as practical performance gains where we achieve new state-of-the-art performance 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 https://github.com/GNNAsKernel/GNNAsKernel.

heading: 2 RELATED WORK
text: Improving Expressiveness of GNNs: Several works other than those mentioned in Sec.1 tackle expressive GNNs. Murphy et al. (2019) achieve universality by summing permutation-sensitive functions across a combinatorial number of permutations, limiting feasibility. Dasoulas et al. (2020) adds node indicators to make them distinguishable, but at the cost of an invariant model, while Vignac et al. (2020) further addresses the invariance problem, but at the cost of quadratic time complexity. Corso et al. (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. (2021b) introduce MPNNs over simplicial complexes that shares similar expressiveness as GNN-AK. Ying et al. (2021) studies transformer with above 1-WL expressiveness. Azizian & Lelarge (2021) surveys GNN expressiveness work.
Leveraging Substructures in Learning: Exploiting subgraph information in GNNs is not new; in fact, k-WL considers all k node subgraphs. Monti et al. (2018); Lee et al. (2019) exploit motif information within aggregation, and others (Bouritsas et al., 2020; Barceló et al., 2021) augment MPNN features with handcrafted subgraph based features. MixHop (Abu-El-Haija et al., 2019) directly aggregates k-hop information by using adjacency matrix powers, ignoring neighbor connections. Towards a meta-learning goal, G-meta (Huang & Zitnik, 2020) applies GNNs on rooted subgraphs around each node to help transferring ability. Tahmasebi & Jegelka (2020) only theoretically justifies subgraph convolution with GNN by showing its ability in counting substructures. Zhengdao et al. (2020) also represent a node by encoding its local subgraph, however using non-scalable relational pooling. k-hop GNN (Nikolentzos et al., 2020) uses k-egonet in a specially designed way: it encodes a rooted subgraph via sequentially passing messages from k-th hops in the subgraph to k−1 hops, until it reaches the root node, and use the root node as 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 k-hop GNN and Ego-GNNs can be viewed as a 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, which is the receptive field of each node in k-layer GNN (Hamilton et al., 2017) – this differs from GNN-AK, which encodes each node by encoding its rooted subgraph. Unlike GNN-AK which uses rooted subgraphs, Fey et al. (2020); Thiede et al. (2021); Bodnar et al. (2021a) design GNNs to use certain subgraph patterns (like cycles and paths) in message passing, however their preprocessing requires solving the subgraph isomorphism problem. To summarize, our work differs by (i) proposing a general subgraph encoding framework for uplifting GNNs, and (ii) addressing scalability issues involved with using subgraphs, which poses significant challenges for subgraph-based methods in practice.

heading: 3 GENERAL FRAMEWORK AND THEORY
text: We first introduce our setting and formalisms. Let G = (V, E) be a graph with node features xi ∈ Rd, ∀i ∈ V . We consider graph-level problems where the goal is to classify/regress a target yG by learning a graph-level representation hG. Let Nk(v) be the set of nodes in the k-hop egonet rooted at node v. N (v) = N1(v)\v denotes the immediate neighbors of node v. For S ⊆ V , let G[S] be the induced subgraph: G[S] = (S, {(i, j) ∈ E|i ∈ S, j ∈ S}). Then G[Nk(v)] denotes the
k-hop egonet rooted at node v. We also define Star(v) = (N1(v), {(v, j) ∈ E|j ∈ N (v)}) be the induced star-like subgraph around v. 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 expressiveness 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 connections 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 2). Although a fixed-expressiveness 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, 2020b). 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.

heading: 3.1 FROM STARS TO SUBGRAPHS
text: We first take a close look at 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 hG by global pooling. Let h (l) v denote the l-th layer embedding of node v. Then, MPNNs compute hG by
h(l+1)v = φ (l) ( h(l)v , f (l) ({ h(l)u |u ∈ N (v) })) l = 0, ..., L− 1 ; hG = POOL({h(L)v |v ∈ V}) (1)
where h(0)i = xi is the original features, L is the number of layers, and φ (l) and f (l) are the l-th layer update and aggregation functions. φ(l), f (l) 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 (Morris et al., 2019). Similar to MPNNs which repeatedly aggregate self and neighbor representations, at t-th iteration, for each node v, 1-WL test aggregates the node’s own label (or color) c(t)v and its neighbors’ labels {c(t)u |u ∈ N (v)}, and hashes this multi-set of labels { c (t) v , {c(t)u |u ∈ N (v)}
} into a new, compressed label c(t+1)v . 1-WL outputs the set of all node labels { c (T ) v |v ∈ V } as G’s fingerprint, and decides two graphs to be non-isomorphic as soon as their fingerprints differ.
The hash process in 1-WL outputs a new label c(t+1)v that uniquely characterizes the star graph Star(v) around v, i.e. two nodes u, v are assigned different compressed labels only if Star(u) and Star(v) differ. Hence, it is easy to see that when two non-isomorphic unlabeled (i.e., all nodes have the same label) d-regular graphs have the same number of nodes, 1-WL cannot distinguish them. This failure limits the expressiveness of 1-WL, but also identifies its bottleneck: the star is not distinguishing enough. Instead, we propose to generalize the star Star(v) to subgraphs, such as the egonet G[N1(v)] and more generally k-hop egonet G[Nk(v)]. This results in an improved version of 1-WL which we call Subgraph-1-WL. Formally, Definition 3.1 (Subgraph-1-WL). Subgraph-1-WL generalizes the 1-WL graph isomorphism test algorithm by replacing color refinement (at iteration t) by c(t+1)v = HASH(Star(t)(v)) with c (t+1) v = HASH(G(t)[Nk(v)]), ∀v ∈ V where HASH(·) is an injective function on graphs.
Note that an 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-1-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-1-WL∗ by using a weaker choice for HASH(·) – specifically, 1-WL. Effectively, we nest 1-WL inside Subgraph-1-WL. Formally, Definition 3.2 (Subgraph-1-WL∗). Subgraph-1-WL∗ is a less expressive variant of Subgraph-1WL where c(t+1)v = 1-WL(G(t)[Nk(v)]).
We further transfer Subgraph-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 ofG[Nk(v)], which is non-trivial as it
implies solving the challenging graph isomorphism problem in the worst case. Analogous to using 1-WL as a weaker choice for HASH(·) inside Subgraph-1-WL∗, we can use use any GNN (most practically, MPNN) as an encoder for subgraph G[Nk(v)]. Let G(l)[Nk(v)] = G[Nk(v)|H(l)] be the attributed subgraph with hidden features H(l) at the l-th layer. Then, GNN-AK computes hG by
h(l+1)v = GNN (l) ( G(l)[Nk(v)] ) l = 0, ..., L− 1 ; hG = POOL({h(L)v |v ∈ V}) (2)
Notice that GNN-AK acts as a “wrapper” for any base GNN (mainly MPNN). This uplifts its expressiveness as well as practical performance as we demonstrate in the following sections.

heading: 3.2 THEORY: EXPRESSIVENESS ANALYSIS
text: We next theoretically study the expressiveness of GNN-AK, by investigating the expressiveness of Subgraph-1-WL. We first establish that GNN-AK and Subgraph-1-WL have the same expressiveness under certain conditions. A GNN is able to distinguish two graphs if its embeddings for two graphs are not identical. A GNN is said to have the same expressiveness as a graph isomorphism test when for any two graphs the GNN outputs different embeddings if and only if (iff) the isomorphism test deems them non-isomorphic. We give following theorems with proof in Appendix. Theorem 1. When the base model is an MPNN with sufficient number of layers and injective φ, f and POOL functions shown in Eq. (1), and MPNN-AK has an injective POOL function shown in Eq. (2), then MPNN-AK is as powerful as Subgraph-1-WL∗.
See Appendix.A.2 for proof. A more general version of Theorem 1 is that GNN-AK is as powerful as Subgraph-1-WL iff base GNN of GNN-AK is as powerful as the HASH function of Subgraph-1WL 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-1-WL∗ is strictly more powerful than 1&2-WL1.
A direct corollary from Theorem 1&2 is as follows, which is empirically verified in Table 1. Corollary 2.1. When MPNN is 1-WL expressive, MPNN-AK is strictly more powerful than 1&2-WL. Theorem 3. When HASH(·) is 3-WL expressive, Subgraph-1-WL is no less powerful than 3-WL, that is, it can discriminate some graphs for which 3-WL fails.
A direct corollary from Theorem 1&3 is as follows, which is empirically verified in Table 1. Corollary 3.1. PPGN-AK can distinguish some 3-WL-failed non-isomorphic graphs. Theorem 4. For any k ≥ 3, there exists a pair of k-WL-failed graphs that cannot be distinguished by Subgraph-1-WL even with injective HASH(·) when t-hop egonets are used with t ≤ 4.
Theorem 4 is proven (Appendix.A.5) by observing that with limited t all rooted subgraphs of two non-isomorphic graphs from CFI(k) family (Cai et al., 1992) are isomorphic, i.e. local rooted subgraph is not enough to capture the “global” difference. This opens a future direction of generalizing rooted subgraph to general subgraph (as in k-WL) while keeping number of subgraphs in O(|V|). Proposition 1 (sufficient conditions). For two non-isomorphic graphs G,H , Subgraph-1-WL with k-egonet can successfully distinguish them if: 1) for any node reordering vG1 , ..., v G |VG| and vH1 , ..., v H |VH |, ∃i ∈ [1,max(|VG|, |VH |)] that G[Nk(v G i )] and H[Nk(vHi )] are non-isomorphic2; and 2) HASH(·) is discriminative enough that HASH(G[Nk(vGi )]) 6= HASH(H[Nk(vHi )]).
This implies subgraph size should be large enough to capture difference, but not larger which requires more expressive base model (Loukas, 2020a). We empirically verify Prop. 1 in Table 2.

heading: 4 CONCRETE REALIZATION
text: We first realize GNN-AK with two type of encodings, and then present an empirically more expressive version, GNN-AK+, with (i) an additional context encoding, and (ii) a subgraph pooling design to incorporate distance-to-centroid, readily computed during subgraph extraction. Next, we discuss a random-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.
11-WL and 2-WL are known to be equally powerful, see Azizian & Lelarge (2021) and Maron et al. (2019a). 2When |VG| < |VH | , ∀i ∈ {|VG|, |VG|+ 1, ..., |VH |}, let G[Nk(vGi )] denote an empty subgraph.
Notation. Let G = (V, E) be the graph with N = |V|, G(l)[Nk(v)] be the k-hop egonet rooted at node v ∈ V in which h(l)u denotes node u’s hidden representation for u ∈ Nk(v) at the l-th layer of GNN-AK. To simplify notation, we use Sub(l)[v] instead of G(l)[Nk(v)] to indicate the the attributeenriched induced subgraph for v. We consider all intermediate node embeddings across rooted subgraphs. Specifically, let Emb(i | Sub(l)[j]) denote node i’s embedding when applying base GNN(l) on Sub(l)[j]; we consider node embeddings for every j ∈ V and every i ∈ Sub(l)[j]. Note that the base GNN can have multiple convolutional layers, and Emb refers to the node embeddings at the last layer before global pooling POOLGNN that generates subgraph-level encoding.
Realization of GNN-AK. We can formally rewrite Eq. (2) as h(l+1)|Subgraphv = GNN (l) ( Sub(l)[v] ) := POOLGNN(l) ({ Emb(i | Sub(l)[v]) | i ∈ Nk(v) }) (3)
We refer to the encoding of the rooted subgraph Sub(l)[v] in Eq. (3) as the subgraph encoding. Typical choices of POOLGNN(l) are SUM and MEAN. As each rooted subgraph has a root node, POOLGNN(l) 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(l+1)v = FUSE ( h(l+1)|Centroidv , h (l+1)|Subgraph v ) where h(l+1)|Centroidv := Emb(v | Sub(l+1)[v]) (4)
where FUSE is concatenation or sum, and h(l)|Centroidv is referred to as the centroid encoding. The realization of GNN-AK in Eq.4 closely follows the theory in Sec.3.
Realization of GNN-AK+. We further develop GNN-AK+, which is more expressive than GNN-AK, based on two observations. First, we observe that Eq.4 does not fully exploit all information inside the rich intermediate embeddings generated for Eq.4, and propose an additional context encoding.
h(l+1)|Contextv := POOLContext ({ Emb(v | Sub(l)[j]) | ∀j s.t. v ∈ Nk(j) })
(5)
Different from subgraph and centroid encodings, the context encoding captures views of node v from different subgraph contexts, or points-of-view. Second, GNN-AK extracts the rooted subgraph for every node with efficient k-hop propagation (complexity O(k|E|)), along which the distance-tocentroid (D2C) 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. Therefore, we propose to uses the D2C by default in two ways in GNN-AK+: (i) augmenting hidden representation h(l)v by concatenating it with the encoding of D2C; (ii) using it to gate the subgraph and context encodings before POOLSubgraph and POOLContext, with the intuition that embeddings of nodes far from v contribute differently than those close to v.
To formalize the gate mechanism guided by D2C, let d(l)i|j be the encoding of distance from node i to j at l-th layer3. Applying gating changes Eq. (5) to
h (l+1)|Context gated,v := POOLContext ({ Sigmoid(d(l)v|j) Emb(v | Sub (l)[j]) | ∀j s.t. v ∈ Nk(j) })
(6)
where denotes element-wise multiplication. Similar changes apply to Eq. (3) to get h(l)|Subgraphgated,v .
Formally, each layer of GNN-AK+ is defined as h(l+1)v = FUSE ( d (l+1) i|j , h (l+1)|Centroid v , h (l+1)|Subgraph gated,v , h (l+1)|Context gated,v ) (7)
Proposition 2. GNN-AK+ is more powerful than GNN-AK. See Proof in Appendix.A.A.7.
Beyond k-egonet Subgraphs. The k-hop egonet (or k-egonet) is a natural choice in our framework, but can be too large when the input graph’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 v, we perform a fixed-length random walk starting at v, resulting in visited nodesNrw(v) and their induced subgraphG[Nrw(v)]. In practice, we use adaptive random walks as in Grover & Leskovec (2016). To reduce randomness, we use multiple truncated random walks and union the visited nodes as Nrw(v). Moreover, we employ online subgraph extraction during training that re-extracts subgraphs at every epoch, which further alleviates the effect of randomness via regularization.
Complexity Analysis. Assuming k-egonets as rooted subgraphs, and an MPNN as base model. For each graph G = (V, E), the subgraph extraction takes O(k|E|) runtime complexity, and outputs
3D2C does not change across layers, but is encoded but is encoded with different parameters in each layer.
|V| subgraphs, which collectively can be represented as a union graph G∪ = (V∪, E∪) with |V| disconnected components, where |V∪| = ∑ v∈V |Nk(v)| and |E∪| = ∑ v∈V |EG[Nk(v)]|. GNN-AK(+) can be viewed as applying base GNN on the union graph. Assuming base GNN has O(|V| + |E|) runtime and memory complexity, GNN-AK(+) has O(|V∪| + |E∪|) runtime and memory cost. For rooted subgraphs of size s, GNN-AK(+) induces an O(s) factor overhead over the base model.

heading: 5 IMPROVING SCALABILITY: SUBGRAPHDROP
text: The complexity analysis reveals that GNN-AK(+) introduce a constant factor overhead (subgraph size) in runtime and memory over the base GNN. Subgraph size can be naturally reduced by choosing 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 Table 6. Here, we present a different subsampling-based 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 it 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. 5 in Appendix.A.8 provides a pictorial illustration.
Subgraph Sampling. Intuitively, if u, v are directly connected in G, subgraphs G[Nk(u)] and G[Nk(v)] share a large overlap and may contain redundancy. With this intuition, we aim to sample only m |V| minimally redundant subgraphs to reduce memory overhead. We study three fast sampling strategies (See Appendix.A.8) that select subgraphs to evenly cover the whole graph, where each node is covered by ≈R (redundancy factor) selected subgraphs; R is a hyperparameter used as a sampling stopping condition. Then, GNN-AK(+)-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 are both desired characteristics for an online Dropout-like sampling in training.
Training with SubgraphDrop. Although dropping redundant subgraphs greatly reduces overhead, it still loses information. Thus, as in Dropout (Srivastava et 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 to 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.
1. Subgraph and Centroid Encoding in Training: Let S ⊆ V be the set of root nodes of the selected 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 encodings {h(l)|Subgraphv |v ∈ S} and centroid encodings {h(l)|Centroidv |v ∈ S}. To estimate uncomputed encodings of u ∈ V \ S , we propose to propagate encodings from S to V \ S . Formally, let kmax = maxu∈V\S Dist(u,S) where Dist(u,S)=minv∈S ShortestPathDistance(u, v). Then we partition U = V \S into {U1, ...,Ukmax} with Ud = {u ∈ U|Dist(u,S) = d}. We propose to spread vector encodings of S out iteratively, i.e. compute vectors of Ud from Ud−1. Formally, we have
h(l)|Subgraphu = Mean ( {h(l)|Subgraphv |v ∈ Ud−1, (u, v) ∈ E} ) for d = 1, 2 . . . kmax, ∀u ∈ Ud, (8)
h(l)|Centroidu = Mean ( {h(l)|Centroidv |v ∈ Ud−1, (u, v) ∈ E} ) for d = 1, 2 . . . kmax, ∀u ∈ Ud, (9)
2. Context Encoding in Training: Following Eq. (5), context encodings can be computed for every node v ∈ V as each node is covered at least R times during training with SubgraphDrop. However when POOLContext is SUM(·), the scale of h(l)|Contextv is smaller than the one in full-mode evaluation. Thus, we scale the context encodings up to align with full-mode evaluation. Formally,
h(l)|Contextv = |{j ∈ V|Nk(j) 3 v}| |{j ∈ S|Nk(j) 3 v}|
× SUM ({ Emb(v | Sub(l)[j]) | ∀j ∈ S s.t. v ∈ Nk(j) })
(10)
When POOLContext is MEAN(·), the context encoding is computed without any modification.

heading: 6 EXPERIMENTS
text: 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.
Simulation Datasets: 1) EXP (Abboud et al., 2021) contains 600 pairs of 1&2-WL failed graphs that are splited into two classes where each graph of a pair is assigned to two different classes. 2) SR25 (Balcilar et al., 2021) 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., 2020). 4) Graph property regression (i.e. connectedness, diameter, radius) tasks on random graph dataset (Corso et al., 2020). All simulation datasets are used to empirically verify the expressiveness of GNN-AK(+). Real-world Datasets: ZINC-12K, CIFAR10, PATTER from Benchmarking GNNs (Dwivedi et al., 2020) and MolHIV, and MolPCBA from Open Graph Benchmark (Hu et al., 2020). See Table 5 for all dataset statistics.
Baselines. We use GCN (Kipf & Welling, 2017), GIN (Xu et al., 2018), PNA∗ 4 (Corso et al., 2020), and 3-WL powerful PPGN (Maron et al., 2019a) directly, which also server as base model of GNNAK to see its general uplift effect. GatedGCN (Dwivedi et al., 2020), DGN (Beani et al., 2021), PNA (Corso et al., 2020), GSN(Bouritsas 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.

heading: 6.1 EMPIRICAL VERIFICATION OF EXPRESSIVENESS
text: Table 1 presents the results on simulation datasets. To save space we present GNN-AK+ with different 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 is quadratic in input size).
Table 2: PPGN-AK expressiveness on SR25.
Base PPGN’s #L 1-hop egonet 2-hop egonet
PPGN-AK’s #L 1 2 3 1 2 3
1 26.67% 100% 100% 26.67% 26.67% 46.67% 2 33.33% 100% 100% 26.67% 26.67% 53.33% 3 26.67% 100% 100% 33.33% 26.67% 53.33%
In Table 2 we look into PPGN-AK’s performance on SR25 as a function of kegonets (k∈[1, 2]), as well as the number of PPGN (inner) layers and (outer) iterations for PPGN-AK. We find that at least 2 inner layers is needed with 1-
egonet subgraphs to 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 with Conjecture 1 (Sec. 3.2).

heading: 6.2 COMPARING WITH SOTA AND GENERALITY
text: Having studied expressiveness tasks, we turn to performance on real-world datasets, as shown in Table 3. We observe similar performance lifts across all datasets and base GNNs (we omit PPGN due to scalability), demonstrating our framework’s generality. Remarkably, GNN-AK+ sets new SOTA performance for several benchmarks – ZINC, CIFAR10, and PATTERN – with a relative error reduction of 60.3%, 50.5%, and 39.4% for base model being GCN, GIN, and PNA∗ respectively.
4PNA∗ is a 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.

heading: 6.3 SCALING UP BY SUBSAMPLING
text: In some cases, GNN-AK (+)’s overhead leads to 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 at the end of Table 3, do not compromise and can even improve performance as compared to their non-sampled counterpart, in alignment with Dropout’s benefits Srivastava et al. (2014). Next we evaluate resource-savings, specifically on ZINC-12K and CIFAR10. Table 4 shows that GIN-AK+-S with varying R provides an effective handle to trade off resources with performance. Importantly, the rate in which performance decays with smaller R is much lower than the rates at which runtime and memory decrease.
Ablation Study. We present ablation results on 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. Table 8 extensively studies the effect of context encoding and D2C, as they are not explained by Subgraph-1-WL∗. Table 9 studies the effect of base model’s depth (or expressiveness) for GNN-AK+ with and without D2C.

heading: 7 CONCLUSION
text: Our work introduces a new, general-purpose framework called GNN-As-Kernel (GNN-AK) to uplift the expressiveness of any GNN, with the key idea of employing a base GNN as a kernel on induced subgraphs of the input graph, generalizing from the star-pattern aggregation of classical MPNNs. Our approach provides an expressiveness and performance boost, while retaining practical scalability of MPNNs—a highly sought-after middle ground between the two regimes of scalable yet less-expressive MPNNs and high-expressive yet practically infeasible and poorly-generalizing korder designs. We theoretically studied the expressiveness of GNN-AK, provided a 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&2-WL for MPNNs, and over 3-WL for PPGN), (ii) which translates to performance gains with SOTA results on graph-level benchmarks, (iii) while retaining scalability to practical graphs.

heading: A APPENDIX
text: A.1 SURVEY OF CONNECTIONS TO CNN AND k-WL
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 pseudo-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 to graphs with a 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, 1976) and deep WL (Arvind et al., 2020). 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(nk) size-k subgraphs, we keep linear scalability by only applying 1-WL-equivalent MPNNs to O(n) rooted subgraphs.

heading: A.2 PROOF OF THEOREM 1
text: Proof. (Xu et al., 2018) proved that with sufficient number of layers and all injective functions, MPNN is as powerful as 1-WL. Then Eq.2 outputs different vectors for two graphs iff Subgraph1-WL∗ encodes different labels with c(t+1)v = 1-WL(G(t)[Nk(v)]). With POOL in Eq.2 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 Subgraph-1-WL∗.

heading: A.3 PROOF OF THEOREM 2
text: Proof. We first prove that if two graphs are identified as isomorphic by Subgraph-1-WL∗, 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-WL∗ but not by 1-WL. Together these two imply that Subgraph-1WL∗ is strictly more powerful than 1-WL. Comparing with 2-WL can be concluded from the fact that 1-WL and 2-WL are 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 nonisomorphic) and are two non-isomorphic graphs but Subgraph-1-WL∗ determines them as isomorphic. Then for any iteration t, set { 1-WL(G(t)[N1(v)])|v ∈ VG } is the same as set{
1-WL(H(t)[N1(v)])|v ∈ VH } . Then there existing an ordering of nodes vG1 , ..., v G n and v H 1 , ..., v H N
with N = |VG| = |VH |, such that for any node order i = 1, ..., N , 1-WL(G(t)[N1(vGi )]) = 1-WL(H(t)[N1(vHi )]). This implies that structure G[N1(vGi )] and H[N1(vHi )] are not distinguishable by 1-WL. Hence Star(vGi ) and Star(v H i ) are hashed to the same label otherwise the 1-WL that includes the hashed result of Star(vGi ) and Star(v H i ) can also distinguish G[N1(vGi )] and H[N1(vHi )]. Then for any iteration t and any node with order i, HASH ( Star(vG (t) i ) ) = HASH ( Star(vH (t) i ) )
implies that 1-WL fails in distinguishing G and H . In fact if we replace the 1-WL hashing function in Subgraph-1-WL∗ to a stronger version HASH ({ HASH(Star(vG (t) )), 1-WL(G(t)[N1(v)]) }) , this directly implies the above statement.
In Figure 2, two 4-regular graphs are presented that cannot be distinguished by 1-WL but can be distinguished by Subgraph-1-WL∗. We visualize the 1-hop egonets that are structurally different among graphs A and B. It’s easy to see that A’s egonet A[N1(1)] and B’s egonet B[N1(1)] can be distinguished by 1-WL, as degree distribution is not the same. Hence, A and B can be distinguished by Subgraph-1-WL∗.

heading: A.4 PROOF OF THEOREM 3
text: Proof. We prove by showing a pair of 3-WL failed non-isomorphic graphs can be distinguished by Subgraph-1-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 a pair of non-isomorphic graphs that cannot be distinguished by B but can be distinguished by A.), assuming HASH(·) is 3-WL discriminative. Figure 3 shows two strongly regular graphs that can not be distinguished by 3-WL (any strongly regular graphs are not distinguishable by 3-WL (Arvind et al., 2020)), along with their 1-hop egonet rooted subgraphs. Notice that all 1-hop egonet rooted subgraphs inA (also inB) are the same, resulting that Subgraph1-WL can successfully distinguishA andB if HASH can distinguish the showed two 1-hop egonets. Now we prove that 3-WL can distinguish these two subgraphs. 3-WL constructs a coloring of 3- tuples of all vertices in a graph, and uses the histogram of colors of all k-tuples as fingerprint of the graph. Then, different 3-tuples correspond to different colors or bins in the histogram. As a triangle is a unique type of 3-tuple, at iteration 0 of 3-WL, the histogram of all 3-tuples counts the number of triangles in the graph. Notice that A’s subgraph has 2 × ( 4 3 ) = 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 A and B. Therefore there exists a pair of 3-WL failed non-isomorphic graphs that can be distinguished by Subgraph-1-WL.

heading: A.5 PROOF OF THEOREM 4
text: Proof. For any k ≥ 3, Cai et al. (1992) provided a scheme to construct a pair of k-WL-failed nonisomorphic graphs based on a base graph G with separator size k + 1 (more specifically, G can be chosen as a degree-3 regular graph with separator size k + 1, 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 in Cai et al. (1992). At high level, this scheme first constructs A by replacing every node (with degree d) in G by a carefully designed graph Xd, and then rewires two edges in A to its
non-isomorphic counter graph B. Specifically, the small graph Xd = (Vd, Ed) is defined as follows. Vd =Ad ∪Bd ∪Md,where Ad = {ai|1 ≤ i ≤ d}, Bd = {bi|1 ≤ i ≤ d},
and Md = {mS |S ⊆ {1, ..., d}, |S| is even} (11) Ed ={(mS , ai)|i ∈ S} ∪ {(mS , bi)|i /∈ S}
Hence each vertex v with degree d in G is replaced by a graph X(v) = Xd of size 2d−1 + 2d, including a “middle” section Md of size 2d−1 and d pairs of vertices (ai, bi) representing “endpoints” of each edge incident with v in the original graph G. Let (u, v) ∈ E(G), then two small graphsX(v) andX(u) inA are connected by the following. Let (au,v, bu,v), (av,u, bv,u) be the pair of vertices associated with (u, v) in X(u) and X(v) respectively, then au,v is connected to av,u, and bu,v is connected to bv,u. After constructing A, B is modified from A by rewiring a single edge (u, v) in the original graph G. Specifically, now in B, au,v is connected to bv,u and bu,v is connected to av,u. Cai et al. (1992) proved that A and B are non-isomorphic, and when base graph G is a degree-3 regular graph with separator size k + 1, A and B are not distinguishable by k-WL. See a visualization in Figure 4.
We provide several useful lemmas related to graph Xd in the following, which are then used in proving Theorem 4.
Lemma 5 (Cai et al. (1992)). Xd has exactly 2d−1 automorphisms, and each automorphism is determined by interchanging ai and bi for each i in some subset S ⊆ {1, ..., d} of even cardinality.
Lemma 5 is directly taken from Lemma 6.1 in Cai et al. (1992).
Lemma 6. The shortest path distance between ai and bi in Xd for any i is exactly 4, and diameter of Xd is 4.
Proof. Based on the construction shown in Eq.11, for any i, ai and bi are not directly connected, and any middle nodes share no connection. This implies the shortest path between ai and bi is larger than 3. Let mS be one middle node connected with ai. We construct a new set S′ = {p, q}, with p 6= i, p ∈ S and q /∈ S, then mS′ connects with bi based on Eq.11. Additionally, ap connects to both mS and mS′ , which implies the shortest path distance between ai and bi ≤ 4. Hence, the shortest path distance between ai and bi is exactly 4. To show the diameter of Xd is 4, it’s easy to observe that distance(ai, bi) only decreases when replacing ai with other nodes in Xd (or reverse, replacing bi with other nodes in Xd).
Lemma 7. For any k ≥ 1, k-egonets of ai and bi in Xd are isomorphic.
Proof. When k ≥ 4, Xd[Nk(ai)] = Xd[Nk(bi)] = Xd based on Lemma 6. Now for 1 ≤ k ≤ 3, we analyze the k-hop egonets of ai and bi sequentially. First, Xd[N1(ai)] and Xd[N1(bi)] are two depth-1 trees with equal number of leaves (middle nodes in Xd), and of course are isomorphic. Similarly, Xd[N2(ai)] and Xd[N2(bi)] are two depth-2 trees with equal number of depth-1 nodes and equal number of leaves, which are also isomorphic. Last, Xd[N3(ai)] and Xd[N3(bi)] are the graphs by removing bi from Xd and ai from Xd, respectively. It’s trivial to observe that they are 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, v) of base graph in Figure 4 to help understanding. To prove that Subgraph-1-WL with t ≤ 4-egonet (we use t to prevent notation conflict) cannot distinguish A and B, we mainly analyze the subgraph around au,v for both graphA andB. For other subgraphs with different root nodes within t shortest-path-distance around nodes au,v, av,u, bu,v, bv,u, 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[Nt(au,v)] and B[Nt(au,v)] be the two t-egonet subgraphs around au,v in A and B respectively. Let Aleft[Nt(au,v)] be the “left” part graph (visualized in Figure 4, the left side of au,v , include au,v) of A[Nt(au,v)], and Aright[Nt(au,v)] be the “right” part graph (visualized in Figure 4, the right side of au,v , excluding au,v) of A[Nt(au,v)]. Then A[Nt(au,v)] is reconstructed by connecting Aleft[Nt(au,v)] and Aright[Nt(au,v)] with a single edge (au,v, av,u). Bleft[Nt(au,v)] and Bright[Nt(au,v)] are defined in the same way, such that B[Nt(au,v)] is reconstructed by connecting (au,v, bv,u) in B. When t ≤ 4, we show that there exists an isomorphism that maps A[Nt(au,v)] to B[Nt(au,v)]. We construct this isomorphism by constructing an isomorphism between Aleft[Nt(au,v)] and Bleft[Nt(au,v)] and an isomorphism between Aright[Nt(au,v)] and Bright[Nt(au,v)] first. Trivially, the current node ordering in Aleft[Nt(au,v)] and Bleft[Nt(au,v)] already defines an isomorphism among them, that is, mapping any ai (bi,mS) in Aleft[Nt(au,v)] to ai (bi,mS) in Bleft[Nt(au,v)]. To find an isomorphism between Aright[Nt(au,v)] and Bright[Nt(au,v)], one can easily observe that for t ≤ 3, Aright[Nt(au,v)] can be 1-to-1 mapped (with av,u in A being mapped to ai) to X3[Nt−1(ai)] and Bright[Nt(au,v)] can be 1-to-1 mapped (with bv,u in A being mapped to bi) to X3[Nt−1(bi)] for some i. When t = 4, Aright[Nt(au,v)] is mapped to X3[N3(ai)] with additional 2 nodes and Bright[Nt(au,v)] is mapped to X3[N3(bi)] with additional 2 nodes. Then applying Lemma 7, when t ≤ 4 we can construct an isomorphism between Aright[Nt(au,v)] and Nright[Nt(au,v)] with av,u in A being mapped to bv,u in B. We remark that when t = 4, the two additional nodes outside X3[N3(ai)] and X3[N3(bi)] does not affecting applying Lemma 7. Last, the combination of the isomorphism between Aleft[Nt(au,v)] and Bleft[Nt(au,v)] and the isomorphism between Aright[Nt(au,v)] and Bright[Nt(au,v)] is actually a new isomorphism between A[Nt(au,v)] and B[Nt(au,v)], as the edge (au,v, av,u) is mapped
to edge (au,v, bv,u). Thus, when t ≤ 4, A[Nt(au,v)] and B[Nt(au,v)] are isomorphic and HASH(A[Nt(au,v)]) = HASH(B[Nt(au,v)]) no matter what HASH(·) function is used. Applying the same argument to all other pairs of subgraphs in A and B implies that the histogram encodings of A and B are the same. Hence Subgraph-1-WL with t ≤ 4 cannot distinguish the two graphs A and B that are k-WL-failed for any k ≥ 3.
We remark that the theorem doesn’t imply that Subgraph-1-WL with t ≥ 5-egonet can distinguishA and B. This should depend on the base graph. We give an informal sketch. Suppose that for t ≥ 5, the left partAleft[Nt(au,v)] and right partAright[Nt(au,v)] are only connected through (au,v, av,u), that is, removing (au,v, av,u) from A[Nt(au,v)] resulting in Aleft[Nt(au,v)] and Aright[Nt(au,v)] being disconnected. Then we can apply Lemma 5 multiple times with mapping some av,u in A to bv,u in B and bv,u in A to av,u in B, until this kind of switches reach the boundary of A[Nt(au,v)], resulting in an isomorphism between A[Nt(au,v)] and B[Nt(au,v)]. We refer the reader to Lemma 6.2 in Cai et al. (1992), which also uses this line of argument.

heading: A.6 PROOF OF PROPOSITION 1
text: Proof. The proof is by contradiction. Let G and H be two non-isomorphic graphs and |VG| = |VH | (if graph sizes are different then Subgraph-1-WL can trivially distinguish them). Now suppose that Prop. 1 is incorrect, i.e. Subgraph-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-WL, G and H would have the same histogram of subgraph colors. Now we focus on iteration 0. Formally, let color cGv,i = HASH(G[Nk(vGi )]) and cHv,i = HASH(H[Nk(vHi )]) for a node order v (vGi maps index i to a node in G). According to Condition (1): for any node reordering vG1 , ..., v G NG and vH1 , ..., v H NH
, ∃i ∈ [1,max(NG, NH)] that G[Nk(vGi )] and H[Nk(vGi )] are non-isomorphic, then we know that ∃i that G[Nk(vGi )] and H[Nk(vHi )] are non-isomorphic, hence cGv,i 6= cHv,i 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 6= i such that cGv,i = cHv,j and cGv,j = cHv,i. Then we can create a new node order m by swapping vGi and v G j , resulting c G m,i = c H m,i and c G m,j = c H m,j . This process can be repeated until having a new node order w such that ∀i ∈ 1, ..., |VG|, cGw,i = cHw,i. As HASH is discriminative enough according to Condition (2), this implies ∀i ∈ 1, ..., |VG|, G[Nk(wGi )] and H[Nk(wHi )] are isomorphic, which contradicts with Condition (1). Thus, Prop. 1 must be true.

heading: A.7 PROOF OF PROPOSITION 2
text: Proof. When a pair of non-isomorphic graphs G and H cannot be distinguished by GNN-AK+, for any layer l, the histogram of h(l))v in G and H in Eq. 7 should be the same. Which implies that for any layer l, the histogram of h(l))v in G and H in Eq. 4 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.

heading: A.8 SAMPLING BY SUBGRAPHDROP
text: The descriptions of subgraph sampling strategies are as follows. Fig. 5 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 ≥R times. • Min-set-cover sampling initially selects a subgraph randomly, and follows the greedy minimum set cover algorithm to iteratively select the subgraph containing the maximum number of uncovered nodes, until every node is covered ≥R times.

heading: A.9 DATASET DESCRIPTION & STATISTICS

heading: A.10 EXPERIMENTAL SETUP DETAILS
text: 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 1-layer base model, 3-hop egonets for GNN-AK, with excpetions that CIFAR10 uses 2-hop egonet due to memory constraint; PATTERN uses random walk based subgraph with walk length=10 and repeat times=5 as its graphs are dense. For GNN-AK-S, R = 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-NN graphs; min-set-cover sampling is used for PATTERN to adapt random walk based subgraph. We use Batch Normalization and ReLU activation in all models. For optimization we use Adam with learning rate 0.001 and weight decay 0. All experiments are repeated 3 times to calculate mean and standard derivation. All experiments are conducted on RTX-A6000 GPUs.

heading: A.11 ABLATION STUDY
text: We present ablation results on various structural components of GNN-AK. Table 6 shows the performance of GIN-AK for varying size egonets with k. We find that larger subgraphs tend to yield improvement, although runtime-performance trade-off may vary by dataset. Notably, simply 1-egonets are enough for CIFAR10 to uplift performance of the base GIN considerably.
Next Table 7 illustrates the added benefit of various node encodings. Compared to the full design, eliminating any of the subgraph, centroid, or context encodings (Eq.s (3)–(5)) yields notably inferior
Table 6: Effect of various k-egonet size.
k of GIN-AK+ ZINC-12K CIFAR10
GIN 0.163 ± 0.004 59.82 ± 0.33
k = 1 0.147 ± 0.006 71.37 ± 0.28 k = 2 0.120 ± 0.005 72.19 ± 0.13 k = 3 0.080 ± 0.001 OOM
Table 7: Effect of various encodings
Ablation of GIN-AK+ ZINC-12K CIFAR10
Full 0.080 ± 0.001 72.19 ± 0.13
w/o Subgraph encoding 0.086 ± 0.001 67.76 ± 0.29 w/o Centroid encoding 0.084 ± 0.003 72.20 ± 0.96 w/o Context encoding 0.088 ± 0.003 69.25 ± 0.30 w/o Distance-to-Centroid 0.085 ± 0.001 71.91 ± 0.22
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-WL∗ (though D2C is supported by Subgraph1-WL, by strengthening HASH), we conduct additional ablation studies over GNN-AK+ with different combinations of removing context encoding and D2C, shown in Table 8. Note that all experiments in Table 8 are using a 1-layer base GIN model. We summarize the observations as follows.
• For real-world datasets (ZINC-12K, CIFAR10), We observe that the largest performance improvement over base model comes from wrapping base GNN with Eq.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 increases the performance of GIN-AK+ w/o Ctx (supported by the theory of Subgraph-1-WL where the HASH is required to be injective). Specifically, the cost-free D2C feature enhances the expressiveness of the base 1-layer GIN model (similar to the benefit of distance encoding shown in Li et al. (2020)), resulting in a more expressive GNN-AK+, which lies between Subgraph-1-WL and Subgraph-1-WL∗. We leave the exact theoretical analysis of D2C’s expressiveness benefit in future work. Notice that GIN-AK improves the performance over the base model but not in a large margin, we next show this is due to the insufficiency of the number of layers of base GIN.
According to Prop. 1, the base model must be discriminative enough such that HASH(G[Nk(vGi )]) 6= HASH(H[Nk(vHi )]), for Subgraph-1-WL with k-egonet to enjoy expressiveness 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-WL∗). We study the effect of base model’s number of layers in GNN-AK+, with and without D2C in Table 9.
• 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 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 to increasing iterations of Subgraph-1-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 (outer) depth. • Secondly, GNN-AK(+) without D2C suffers from a trade-off between the base model’s expressiveness (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 1-layer GIN base model is not discriminative enough for subgraphs in the dataset, and with this bottleneck of base model, GNN-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.

heading: A.12 ADDITIONAL RESULTS ON TU DATASETS
text: 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 et 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 of existing baselines directly from Bodnar et al. (2021a) with their method labeled as CIN, for references to all baselines see Bodnar et al. (2021a). The result is shown in Table 10.

Review summaries:
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.

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.    Moreover, the authors propose a subgraph sampling strategy to speed up the computation.   The proposed method is evaluated on large benchmark datasets, mostly stemming from the molecular domain, reporting good performance boosts compared to standard GNN architectures.

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.