text:
\subsection{From Stars to Subgraphs}
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 ${\mathbf{h}}_G$ by global pooling. Let ${\mathbf{h}}_v^{(l)}$ denote the $l$-th layer embedding of node $v$.  Then, MPNNs compute ${\mathbf{h}}_G$ by
{\small
\begin{align}
    {\mathbf{h}}_v^{(l+1)} &= \phi^{(l)} \bigg( {\mathbf{h}}_v^{(l)}, f^{(l)}\Big( \big\{{\mathbf{h}}_u^{(l)} | u\in {\mathcal{N}}(v)  \big\} \Big)  \bigg) \quad l=0,...,L-1 \;; \quad
     {\mathbf{h}}_G &= \text{POOL} (\{ {\mathbf{h}}_v^{(L)} | v \in {\mathcal{V}}  \})  \label{eq:mpnn}
\end{align}}
\noindent where $ {\mathbf{h}}_i^{(0)}={\mathbf{x}}_i$ is the original features, $L$ is the number of layers, and $\phi^{(l)}$ and $f^{(l)}$ are the $l$-th layer update and aggregation functions. $\phi^{(l)}$, $f^{(l)}$ and $\text{POOL}$ vary among different MPNNs and influence their expressiveness and performance.
MPNNs achieve maximum expressiveness ($1$-WL) when all three functions are injective \citep{xu2018powerful}.

MPNNs' expressiveness upper bound  follows from its  close relation to the 1-WL isomorphism test \revise{\citep{morris2019weisfeiler}}.
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\in {\mathcal{N}}(v) \}$, and hashes this multi-set of labels $\Big\{c^{(t)}_v, \{c^{(t)}_u|u\in {\mathcal{N}}(v) \} \Big\}$ into a new, compressed label $c^{(t+1)}_v$. 1-WL outputs the set of all node labels $\big\{c^{(T)}_v | v\in {\mathcal{V}} \big\}$ 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[{\mathcal{N}}_1(v)]$ and more generally $k$-hop egonet $G[{\mathcal{N}}_k(v)]$. This results in an improved version of 1-WL which we call \textit{Subgraph-1-WL}.
Formally,
\begin{definition} [\textbf{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 = \text{HASH} (Star^{(t)}(v))$ with $c^{(t+1)}_v = \text{HASH} (G^{(t)}[{\mathcal{N}}_k(v)])$, $\forall v\in \mathcal{V}$ where $\text{HASH}(\cdot)$ is an injective function on graphs.
\end{definition}

\vspace{-2mm}
Note that an injective hash function for star graphs is equivalent to that for multi-sets, which is easy to derive \citep{deepset}. 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$^\ast$ by using
 a weaker choice for $\text{HASH}(\cdot)$ -- specifically, $1$-WL. Effectively, we \textit{nest} $1$-WL inside Subgraph-1-WL. Formally,
\begin{definition} [\textbf{Subgraph-1-WL}$^{\bm\ast}$]
Subgraph-1-WL$^\ast$ is a less expressive variant of Subgraph-1-WL where
$c^{(t+1)}_v = \text{1-WL} (G^{(t)}[{\mathcal{N}}_k(v)])$.
\end{definition}

We further transfer Subgraph-1-WL to neural networks, resulting in {\small\textsf{GNN-AK}}\xspace 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[{\mathcal{N}}_k(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 $\text{HASH}(\cdot)$ inside Subgraph-1-WL$^\ast$, we can use use any GNN (most practically, MPNN) as an encoder for subgraph $G[{\mathcal{N}}_k(v)]$. Let $G^{(l)}[{\mathcal{N}}_k(v)] = G[{\mathcal{N}}_k(v) | {\mathbf{H}}^{(l)}]$ be the attributed subgraph with hidden features ${\mathbf{H}}^{(l)}$ at the $l$-th layer.  Then, {\small\textsf{GNN-AK}}\xspace computes ${\mathbf{h}}_G$ by
{\small
\begin{align}
 {\mathbf{h}}_v^{(l+1)} = \text{GNN}^{(l)} \Big(G^{(l)}[{\mathcal{N}}_k(v)]\Big) \quad l=0,...,L-1  \quad \;; \quad
{\mathbf{h}}_G = \text{POOL} (\{ {\mathbf{h}}_v^{(L)} | v \in {\mathcal{V}}  \})  \label{eq:gnn-ak}
\end{align}}
Notice that {\small\textsf{GNN-AK}}\xspace 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.

\subsection{Theory: Expressiveness Analysis} \label{ssec:theory}
We next theoretically study the expressiveness of {\small\textsf{GNN-AK}}\xspace, by investigating the expressiveness of Subgraph-1-WL. We first establish that {\small\textsf{GNN-AK}}\xspace 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.

\begin{theorem} \label{thm:equivalence}
When the base model is an MPNN with sufficient number of layers and injective $\phi, f$ and \text{POOL} functions shown in Eq. (\ref{eq:mpnn}), and \mtd{MPNN} has an injective $\text{POOL}$ function shown in Eq. (\ref{eq:gnn-ak}),  then \mtd{MPNN} is as powerful as Subgraph-1-WL$^*$.
\end{theorem}
See Appendix.\ref{apdx:proof-of-equi} for proof. A more general version of Theorem \ref{thm:equivalence} is that {\small\textsf{GNN-AK}}\xspace is as powerful as Subgraph-1-WL iff base GNN of {\small\textsf{GNN-AK}}\xspace 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 {\small\textsf{GNN-AK}}\xspace through studying Subgraph-1-WL and Subgraph-1-WL$^*$.

\begin{theorem} \label{thm:above-1WL}
Subgraph-1-WL$^*$ is strictly more powerful than 1\&2-WL\footnote{\revise{1-WL and 2-WL are known to be equally powerful, see \cite{azizian2021expressive} and \cite{maron2019provably}.} }.
\end{theorem}
A direct corollary from Theorem \ref{thm:equivalence}\&\ref{thm:above-1WL} is as follows, which is empirically verified in Table \ref{tab:simulation}.
\begin{corollary}When MPNN is 1-WL expressive, \mtd{MPNN} is strictly more powerful than 1\&2-WL.
\end{corollary}

\begin{theorem} \label{thm:not-worse-3WL}
When $\text{HASH}(\cdot)$ is $3$-WL expressive, Subgraph-1-WL is no less powerful than $3$-WL, \revise{ that is,} it can discriminate some graphs for which $3$-WL fails.
\end{theorem}
A direct corollary from Theorem \ref{thm:equivalence}\&\ref{thm:not-worse-3WL} is as follows, which is empirically verified in Table \ref{tab:simulation}.
\begin{corollary}
\mtd{PPGN} can distinguish some 3-WL-failed non-isomorphic graphs.
\end{corollary}

\begin{theorem} \label{thm:upper-bound}
For any $k \ge 3$, there exists a pair of $k$-WL-failed graphs that \textbf{cannot} be distinguished by Subgraph-1-WL even with injective $\text{HASH}(\cdot)$ when $t$-hop egonets are used with $t\le4$.
\end{theorem}

Theorem \ref{thm:upper-bound} is proven (Appendix.\ref{apdx:proof-upperbound}) by observing that with limited $t$ all rooted subgraphs of two non-isomorphic graphs from $CFI(k)$ family \citep{cai1992optimal}  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($|{\mathcal{V}}|$).

\begin{conj} [sufficient conditions] \label{conj:suffi}
For two non-isomorphic graphs $G,H$, Subgraph-1-WL \revise{with $k$-egonet} can successfully distinguish them if: 1) for any node reordering \revise{$v^G_1,..., v^G_{|{\mathcal{V}}_G|}$ and $v^H_1,..., v^H_{|{\mathcal{V}}_H|}$, $\exists i\in [1,\max(|{\mathcal{V}}_G|,|{\mathcal{V}}_H|)]$ that $G[{\mathcal{N}}_k(v^G_i)]$ and $H[{\mathcal{N}}_k(v^H_i)]$
are non-isomorphic\footnote{\revise{When $|{\mathcal{V}}_G| < |{\mathcal{V}}_H|$ , $\forall i \in \{|{\mathcal{V}}_G|,|{\mathcal{V}}_G|+1,...,|{\mathcal{V}}_H|\}$, let $G[{\mathcal{N}}_k(v^G_i)]$ denote an empty subgraph.}}; } and 2) $\text{HASH}(\cdot)$ is discriminative enough that $\text{HASH}(G[{\mathcal{N}}_k(v^G_i)]) \neq \text{HASH}(H[{\mathcal{N}}_k(v^H_i)])$.
\end{conj}

This implies subgraph size should be large enough to capture difference, but not larger which requires more expressive base model \citep{Loukas2020What}. We empirically verify \revise{Prop}. \ref{conj:suffi} in Table \ref{tab:ppgn-ak-sr25}.

\subsection{Design and Realization}\label{ssec:realize}
{\bf Notation.} Let $G=({\mathcal{V}},{\mathcal{E}})$ be the graph with $N=|{\mathcal{V}}|$,
 $G^{(l)}[{\mathcal{N}}_k(v)]$ be the $k$-hop egonet
rooted at node $v\in{\mathcal{V}}$ in which
${\mathbf{h}}^{(l)}_u$ denotes node $u$'s hidden representation for $u\in {\mathcal{N}}_k(v)$ at the $l$-th layer of {\small\textsf{GNN-AK}}\xspace.
To simplify notation, we use
$\mathrm{Sub}^{(l)}[v]$ instead of $G^{(l)}[{\mathcal{N}}_k(v)]$ to indicate the the attribute-enriched induced subgraph for $v$.
We consider all intermediate node embeddings across rooted subgraphs. Specifically, \revise{let $\small\textsf{Emb}(i\mid \mathrm{Sub}^{(l)}[j])$ denote node $i$'s embedding when applying base GNN$^{(l)}$ on $\mathrm{Sub}^{(l)}[j]$; we consider node embeddings for every $j\in {\mathcal{V}}$ and every $i\in \mathrm{Sub}^{(l)}[j]$.} Note that the base GNN can have multiple convolutional layers, and $\small\textsf{Emb}$ refers to the node embeddings at the last layer before global pooling $\text{POOL}_{\text{GNN}}$ that generates subgraph-level encoding.

\revise{{\bf Realization of {\small\textsf{GNN-AK}}\xspace.}} We can formally rewrite Eq. (\ref{eq:gnn-ak}) as
{\small\begin{align}
    {\mathbf{h}}_v^{(l+1)|\text{Subgraph}} &= \text{GNN}^{(l)} \Big(\mathrm{Sub}^{(l)}[v]\Big) := \text{POOL}_{\text{GNN}^{(l)}} \Big( \big\{ \textsf{Emb}(i \mid \mathrm{Sub}^{(l)}[v]) \mid i \in {\mathcal{N}}_k(v) \big\} \Big) \label{eq:subgraph-emb-0}
\end{align}}
We refer to the encoding of the rooted subgraph  $\mathrm{Sub}^{(l)}[v]$ in Eq. (\ref{eq:subgraph-emb-0}) as the \textit{subgraph encoding}. Typical choices of $\text{POOL}_{\text{GNN}^{(l)}}$ are SUM and MEAN. \revise{As each rooted subgraph has a root node, $\text{POOL}_{\text{GNN}^{(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 {\small\textsf{GNN-AK}}\xspace:
{\small
\begin{align}
{\mathbf{h}}_v^{(l+1)} = \text{FUSE}\Big({\mathbf{h}}_v^{(l+1)|\text{Centroid}}, \; {\mathbf{h}}_v^{(l+1)|\text{Subgraph}} \Big) \quad \text{  where  }{\mathbf{h}}_v^{(l+1)|\text{Centroid}} &:= \textsf{Emb}(v\mid \mathrm{Sub}^{(l+1)}[v])  \label{eq:gnn-ak-realization}
\end{align}}
where FUSE is concatenation or sum, and ${\mathbf{h}}_v^{(l)|\text{Centroid}}$ is referred to as the \textit{centroid encoding}.
The realization of {\small\textsf{GNN-AK}}\xspace in Eq.\ref{eq:gnn-ak-realization} closely follows the theory in Sec.\ref{sec:model-general}.}

\revise{{\bf Realization of {\small\textsf{GNN-AK$^+$}}\xspace.} We further develop {\small\textsf{GNN-AK$^+$}}\xspace, which is more expressive than {\small\textsf{GNN-AK}}\xspace, based on two observations. \textbf{First}, we observe that Eq.\ref{eq:gnn-ak-realization} does not fully exploit all information inside the rich intermediate embeddings generated for Eq.\ref{eq:gnn-ak-realization}, and propose an additional \textit{context encoding}.
{\small
\begin{align}
{\mathbf{h}}_v^{(l+1)|\text{Context}} &:= \text{POOL}_{\text{Context}} \Big( \big\{ \textsf{Emb}(v\mid \mathrm{Sub}^{(l)}[j]) \mid \forall j \text{ s.t. }  v \in {\mathcal{N}}_k(j) \big\} \Big) \label{eq:context-emb}
\end{align}}
Different from subgraph and centroid encodings, the context encoding captures views of node $v$ from different subgraph contexts, or points-of-view.
\textbf{Second}, {\small\textsf{GNN-AK}}\xspace extracts the rooted subgraph for every node with efficient $k$-hop propagation (complexity $O(k|{\mathcal{E}}|)$), along which the distance-to-centroid (D2C)\footnote{We record D2C value for every node in every subgraph, and the value is categorical instead of continuous.} within each subgraph is readily recorded at no additional cost and can be used to augment node features; \citep{li2020distance} shows this theoretically improves expressiveness.
Therefore, we propose to uses the D2C by default in two ways in {\small\textsf{GNN-AK$^+$}}\xspace: (i) augmenting hidden representation ${\mathbf{h}}_v^{(l)}$ by concatenating it with the encoding of D2C; (ii) using it to gate the subgraph and context encodings before $\text{POOL}_{\text{Subgraph}}$ and $\text{POOL}_{\text{Context}}$, with the intuition that embeddings of nodes far from $v$ contribute differently from those close to $v$.

To formalize the gate mechanism guided by D2C, let ${\mathbf{d}}^{(l)}_{i|j}$ be the encoding of distance from node $i$ to $j$ at $l$-th layer\footnote{The categorical D2C does not change across layers, but is encoded with different parameters in each layer.}. Applying gating changes Eq. (\ref{eq:context-emb}) to
{\small \begin{align}
    {\mathbf{h}}_{\text{gated,}v}^{(l+1)|\text{Context}} &:= \text{POOL}_{\text{Context}} \Big( \big\{  \text{Sigmoid}({\mathbf{d}}^{(l)}_{v|j}) \odot \textsf{Emb}(v\mid \mathrm{Sub}^{(l)}[j]) \mid \forall j \text{ s.t. }  v \in {\mathcal{N}}_k(j) \big\} \Big)
\end{align}}
where $\odot$ denotes element-wise multiplication. Similar changes apply to Eq. (\ref{eq:subgraph-emb-0}) to get ${\mathbf{h}}_{\text{gated,}v}^{(l)|\text{Subgraph}}$.

Formally, each layer of {\small\textsf{GNN-AK$^+$}}\xspace is defined as
{\small\begin{align}
{\mathbf{h}}_v^{(l+1)} = \text{FUSE}\Big({\mathbf{d}}^{(l+1)}_{i|j}, \; {\mathbf{h}}_v^{(l+1)|\text{Centroid}}, \; {\mathbf{h}}_{\text{gated,}v}^{(l+1)|\text{Subgraph}} , \; {\mathbf{h}}_{\text{gated,}v}^{(l+1)|\text{Context}}\Big)  \label{eq:gnn-ak-plus-realization}
\end{align}}
where FUSE is concatenation or sum. We illustrate in Figure \ref{fig:GNN-AK} the $l$-th layer of {\small\textsf{GNN-AK$(^+)$}}\xspace.

\begin{conj}\label{conj:plus}
{\small\textsf{GNN-AK$^+$}}\xspace is at least as powerful as {\small\textsf{GNN-AK}}\xspace. \quad {\normalfont See Proof in Appendix.A.\ref{apdx:plus}.}
\end{conj}

}
{\bf 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 \citep{kleinberg2000small}, 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 nodes ${\mathcal{N}}_{rw}(v)$ and their induced subgraph $G[{\mathcal{N}}_{rw}(v)]$. In practice, we use adaptive random walks as in \citet{grover2016node2vec}. To reduce randomness, we use multiple truncated random walks and union the visited nodes as ${\mathcal{N}}_{rw}(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.

\textbf{Complexity Analysis.~}
Assuming $k$-egonets as rooted subgraphs, and an MPNN as base model. For each graph $G=({\mathcal{V}},{\mathcal{E}})$, the subgraph extraction takes $O(k|{\mathcal{E}}|)$ runtime complexity, and outputs $|{\mathcal{V}}|$ subgraphs, which collectively can be represented as a union graph $\mathcal{G}_{\cup}=(\mathcal{V}_{\cup}, \mathcal{E}_{\cup})$ with $|{\mathcal{V}}|$ disconnected components, where $|\mathcal{V}_{\cup}| = \sum_{v \in {\mathcal{V}}} |{\mathcal{N}}_k(v)|$ and $|\mathcal{E}_{\cup}| = \sum_{v \in {\mathcal{V}}} |{\mathcal{E}}_{  G[{\mathcal{N}}_k(v)] } |$. {\small\textsf{GNN-AK$(^+)$}}\xspace  can be viewed as applying base GNN on the union graph.
 Assuming base GNN has $O(|{\mathcal{V}}| + |{\mathcal{E}}| )$ runtime and memory complexity, {\small\textsf{GNN-AK$(^+)$}}\xspace has $O(|\mathcal{V}_{\cup}| + |\mathcal{E}_{\cup}| )$ runtime and memory cost. For rooted subgraphs of size $s$, {\small\textsf{GNN-AK$(^+)$}}\xspace induces an $O(s)$ factor overhead over the base model.

\subsection{Subgraph Sampling Strategies}
Intuitively, if $u,v$ are directly connected in $G$,  subgraphs $G[{\mathcal{N}}_k(u)]$ and $G[{\mathcal{N}}_k(v)]$ share a large overlap and may contain redundancy.
With this intuition, we aim to sample only $m{\ll}|{\mathcal{V}}|$ minimally redundant subgraphs to reduce memory overhead.
We propose three fast sampling strategies (See Appendix.\ref{apdx:subgraphdrop}) that
select subgraphs to evenly cover the whole graph, where each node is covered by ${\approx}R$ (redundancy factor) selected subgraphs; $R$ is a hyperparameter used as a sampling stopping condition. Then, {\small\textsf{GNN-AK$(^+)$-S}}\xspace (with Sampling) has roughly $R$ times the overhead of base model ($R{\le}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.

\subsection{Training with SubgraphDrop}
Although dropping redundant subgraphs greatly reduces overhead, it still loses information. Thus, as in Dropout \citep{srivastava2014dropout}, 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.

{\bf Subgraph and Centroid Encoding in Training.}
Let ${\mathcal{S}} \subseteq {\mathcal{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 \in {\mathcal{S}}$, following Eq. (\ref{eq:subgraph-emb-0}) and Eq. (\ref{eq:gnn-ak-realization}), resulting incomplete subgraph encodings $ \{{\mathbf{h}}_v^{(l)|\text{Subgraph}}| v\in {\mathcal{S}} \}$ and centroid encodings $ \{{\mathbf{h}}_v^{(l)|\text{Centroid}}| v\in {\mathcal{S}}\}$.
To estimate uncomputed encodings of $u\in {\mathcal{V}} \setminus {\mathcal{S}}$, we propose to \textit{propagate} encodings from ${\mathcal{S}}$ to ${\mathcal{V}} \setminus {\mathcal{S}}$. Formally, let $k_{max}=\max_{u\in {\mathcal{V}} \setminus {\mathcal{S}}} \text{Dist}(u, {\mathcal{S}})$ where $\text{Dist}(u, {\mathcal{S}})$=$\min_{v\in{\mathcal{S}}}  \text{ShortestPathDistance}(u,v)$. Then we partition ${\mathcal{U}} = {\mathcal{V}} \setminus {\mathcal{S}}$ into $\{{\mathcal{U}}_1,...,{\mathcal{U}}_{k_{max}}\}$ with ${\mathcal{U}}_d=\{u \in {\mathcal{U}}| \text{Dist}(u, {\mathcal{S}})=d \}$. We propose to spread vector encodings of ${\mathcal{S}}$ out iteratively, i.e. compute vectors of ${\mathcal{U}}_d$ from ${\mathcal{U}}_{d-1}$.
Formally, we have
{\small
\begin{align}
 {\mathbf{h}}_u^{(l)|\text{Subgraph}} &= \text{Mean} \big(\{ {\mathbf{h}}_v^{(l)|\text{Subgraph}} | v \in {\mathcal{U}}_{d-1}, (u,v) \in {\mathcal{E}} \}\big) \quad \text{for} \quad d=1,2 \ldots k_{max},  \forall u \in {\mathcal{U}}_d, \\
 {\mathbf{h}}_u^{(l)|\text{Centroid}} &= \text{Mean} \big(\{ {\mathbf{h}}_v^{(l)|\text{Centroid}} | v \in {\mathcal{U}}_{d-1}, (u,v) \in {\mathcal{E}} \}\big) \quad \text{for} \quad d=1,2 \ldots k_{max},  \forall u \in {\mathcal{U}}_d,
\end{align}
}

{\bf Context Encoding in Training.} Following Eq. (\ref{eq:context-emb}), context encodings can be computed for every node $v \in {\mathcal{V}}$ as each node is covered at least $R$ times during training with SubgraphDrop. However when $\text{POOL}_{\text{Context}}$ is $\text{SUM}(\cdot)$,  the scale of ${\mathbf{h}}_v^{(l)|\text{Context}}$ is smaller than the one in full-mode evaluation. Thus, we scale the context encodings up to align with full-mode evaluation. Formally,
{\small
\begin{align}
    {\mathbf{h}}_v^{(l)|\text{Context}} = \frac{|\{j\in {\mathcal{V}} |{\mathcal{N}}_k(j) \ni v\}|} {|\{j\in {\mathcal{S}} | {\mathcal{N}}_k(j) \ni v \}|}\times\text{SUM} \Big( \big\{ \textsf{Emb}(v\mid \mathrm{Sub}^{(l)}[j]) \mid \forall j \in {\mathcal{S}} \text{ s.t. }  v \in {\mathcal{N}}_k(j) \big\} \Big)
\end{align}
}
When $\text{POOL}_{\text{Context}}$ is $\text{MEAN}(\cdot)$, the context encoding is computed without any modification.
\subsection{Empirical Verification of Expressiveness}
\begin{table}[h]
\setlength{\tabcolsep}{4pt}
\setlength\extrarowheight{-5pt}
\vspace{-0.15in}
\fontsize{8}{8}\selectfont
    \caption{Simulation dataset performance:

    \textit{{\small\textsf{GNN-AK$(^+)$}}\xspace boosts base GNN across tasks, empirically verifying expressiveness lift}. (ACC: accuracy, MAE: mean absolute error, OOM: out of memory) }\label{tab:simulation}
    \vspace{-0.1in}
    \centering
    \begin{tabular}{l r r cccc  ccc}
    \toprule
     \multirow{2}{*}{Method} & \multirow{2}{*}[-0mm]{\makecell{EXP \\ (ACC)}} & \multirow{2}{*}[-0mm]{\makecell{SR25 \\ (ACC)}} & \multicolumn{4}{c}{Counting Substructures (MAE)} & \multicolumn{3}{c}{Graph Properties ($\log_{10}$(MAE))} \\
     \cmidrule(l{2pt}r{2pt}){4-7} \cmidrule(l{2pt}r{2pt}){8-10}
                             &      &       & Triangle & Tailed Tri. & Star & 4-Cycle          &  IsConnected & Diameter & Radius  \\
    \midrule
     GCN      &  50\%& 6.67\%& 0.4186 & 0.3248 & 0.1798 & 0.2822 & -1.7057 & -2.4705 & -3.9316 \\
    \textsf{GCN-AK$^+$} & \BFSERIES100\%& 6.67\%& 0.0137 & 0.0134 & 0.0174 & 0.0183 & -2.6705 & -3.9102 & -5.1136\\
    \midrule
     GIN       &  50\%& 6.67\%& 0.3569 & 0.2373 & 0.0224 & 0.2185 & -1.9239 & -3.3079 & -4.7584 \\
    \revise{\textsf{GIN-AK}}&  \revise{\BFSERIES100\%} & \revise{6.67\%} & 0.0934 & 0.0751 & 0.0168 & 0.0726 & -1.9934 & -3.7573 & -5.0100 \\
    \textsf{GIN-AK$^+$}  & \BFSERIES100\%& 6.67\%& 0.0123 & 0.0112 & 0.0150 & 0.0126 & -2.7513 & -3.9687 & -5.1846\\
    \midrule
     PNA$^*$        &  50\%& 6.67\%& 0.3532 & 0.2648 & 0.1278 & 0.2430 &-1.9395 &-3.4382 &-4.9470 \\
    \textsf{PNA$^*$-AK$^+$}   & \BFSERIES100\%& 6.67\%& 0.0118 & 0.0138 & 0.0166 & 0.0132 &-2.6189 & -3.9011& -5.2026\\
    \midrule
     PPGN        & 100\%& 6.67\%&0.0089 &0.0096  &0.0148  &0.0090  & -1.9804 & -3.6147 & -5.0878 \\
    \textsf{PPGN-AK$^+$}   & 100\%&  \BFSERIES100\%& OOM & OOM& OOM& OOM& OOM& OOM& OOM\\
    \bottomrule
    \end{tabular}
    \vspace{-0.1in}
\end{table}

Table \ref{tab:simulation} presents the results on simulation datasets. To save space we present {\small\textsf{GNN-AK$^+$}}\xspace with different base models but only one one version of {\small\textsf{GNN-AK}}\xspace: \mtd{GIN}. All {\small\textsf{GNN-AK$(^+)$}}\xspace variants perform perfectly on EXP, while only PPGN alone do so previously.
Moreover, \mtdp{PPGN} reaches perfect accuracy on SR25, while PPGN fails. Similarly, {\small\textsf{GNN-AK$(^+)$}}\xspace consistently boosts all MPNNs for substructure and graph property prediction (\mtdp{PPGN} is OOM as it is quadratic in input size).

\begin{wraptable}{l}{8cm}
\fontsize{8}{8}\selectfont
\vspace{-0.22in}
\setlength{\tabcolsep}{3pt}
\setlength\extrarowheight{-5pt}
 {
    \caption{\mtd{PPGN} expressiveness on SR25.}\label{tab:ppgn-ak-sr25}
    \vspace{-0.1in}
    \begin{tabular}{c ccc ccc}
    \toprule
     \revise{Base PPGN's \#L } & \multicolumn{3}{c}{1-hop egonet} & \multicolumn{3}{c}{2-hop egonet} \\
     \cmidrule(l{2pt}r{2pt}){2-4} \cmidrule(l{2pt}r{2pt}){5-7}
    \revise{PPGN-AK's \#L}  & 1 & 2 & 3 & 1 & 2 & 3 \\
    \midrule
    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\%\\
    \bottomrule
    \end{tabular}
    }
\vspace{-0.18in}
\end{wraptable}
In Table \ref{tab:ppgn-ak-sr25} we look into \mtd{PPGN}'s performance on SR25
 as a function of $k$-egonets ($k{\in}[1,2]$), as well as the number of PPGN (inner) layers and (outer) iterations for \mtd{PPGN}. 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 Proposition \ref{conj:suffi} (Sec. \ref{ssec:theory}).

\subsection{Comparing with SOTA and Generality}
Having studied expressiveness tasks, we turn to performance on real-world datasets, as shown in Table \ref{tab:real-world}. We observe similar performance lifts across all datasets and base GNNs (we omit PPGN due to scalability), demonstrating our framework's generality. Remarkably, {\small\textsf{GNN-AK$^+$}}\xspace 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.
\begin{table}[htb]
\vspace{-0.1in}
\setlength\extrarowheight{-5pt}
\fontsize{8}{8}\selectfont
    \caption{Real-world dataset performance: \textit{{\small\textsf{GNN-AK$^+$}}\xspace achieves SOTA performance for {ZINC-12K, CIFAR10, and PATTERN}.} (OOM: out of memory, $-$: missing values from literature)}\label{tab:real-world}
    \vspace{-0.1in}
    \centering
    \begin{tabular}{lccccc}
    \toprule
    Method & ZINC-12K (MAE) & CIFAR10 (ACC) & PATTERN (ACC)  & MolHIV (ROC) & MolPCBA (AP)  \\
    \midrule
    GatedGCN   & 0.363 $\pm$ 0.009& 69.37 $\pm$ 0.48& 84.480 $\pm$ 0.122& $-$& $-$\\
    HIMP       & 0.151 $\pm$ 0.006&                $-$&                  $-$& 0.7880 $\pm$ 0.0082& $-$\\
    PNA        & 0.188 $\pm$ 0.004& 70.47 $\pm$ 0.72& 86.567 $\pm$ 0.075& 0.7905 $\pm$ 0.0132& 0.2838 $\pm$ 0.0035\\
    DGN        & 0.168 $\pm$ 0.003& 72.84 $\pm$ 0.42& 86.680 $\pm$ 0.034& 0.7970 $\pm$ 0.0097& 0.2885 $\pm$ 0.0030\\
    GSN        & 0.115 $\pm$ 0.012&                $-$ &                   $-$& 0.7799 $\pm$ 0.0100&  $-$\\
    \revise{CIN} & \revise{\fontseries{b}\selectfont 0.079 $\pm$ 0.006} & $-$ & $-$ &\revise{\fontseries{b}\selectfont 0.8094 $\pm$ 0.0057} & $-$\\
    \midrule
    GCN        & 0.321 $\pm$ 0.009& 58.39 $\pm$ 0.73& 85.602 $\pm$ 0.046& 0.7422 $\pm$ 0.0175& 0.2385 $\pm$ 0.0019\\
    \textsf{GCN-AK$^+$}  & 0.127 $\pm$ 0.004& 72.70 $\pm$ 0.29& \BFSERIES86.887 $\pm$ 0.009& 0.7928 $\pm$ 0.0101& 0.2846 $\pm$ 0.0002\\
    \midrule
    GIN        & 0.163 $\pm$ 0.004& 59.82 $\pm$ 0.33& 85.732 $\pm$ 0.023& 0.7881 $\pm$ 0.0119& 0.2682 $\pm$ 0.0006\\
    \textsf{GIN-AK} & 0.094 $\pm$ 0.005 & 67.51 $\pm$ 0.21 & 86.803 $\pm$ 0.044 & 0.7829 $\pm$ 0.0121 & 0.2740 $\pm$ 0.0032 \\

    \textsf{GIN-AK$^+$}  & \BFSERIES0.080 $\pm$ 0.001& 72.19 $\pm$ 0.13& 86.850 $\pm$ 0.057& 0.7961 $\pm$ 0.0119& \BFSERIES0.2930 $\pm$ 0.0044\\
    \midrule
    PNA$^*$         & 0.140 $\pm$ 0.006& 73.11 $\pm$ 0.11& 85.441 $\pm$ 0.009& 0.7905 $\pm$ 0.0102& 0.2737 $\pm$ 0.0009\\
    \textsf{PNA$^*$-AK$^+$}  & 0.085 $\pm$ 0.003&                 OOM&             OOM& 0.7880 $\pm$ 0.0153& 0.2885 $\pm$ 0.0006\\
    \midrule
    \midrule
    \textsf{GCN-AK$^+$-S}     & 0.127 $\pm$ 0.001& 71.93 $\pm$ 0.47& 86.805 $\pm$ 0.046& 0.7825 $\pm$ 0.0098& 0.2840 $\pm$ 0.0036\\
    \textsf{GIN-AK$^+$-S}      & 0.083 $\pm$ 0.001& 72.39 $\pm$ 0.38& 86.811 $\pm$ 0.013& 0.7822 $\pm$ 0.0075& 0.2916 $\pm$ 0.0029\\
    \textsf{PNA$^*$-AK$^+$-S}  & 0.082 $\pm$ 0.000& \BFSERIES74.79 $\pm$ 0.18& 86.676 $\pm$ 0.022& 0.7821 $\pm$ 0.0143& 0.2880 $\pm$ 0.0012\\
    \bottomrule
    \end{tabular}
    \vspace{-0.15in}
\end{table}

\subsection{Scaling up by Subsampling}
In some cases, \revise{{\small\textsf{GNN-AK}}\xspace($^+$)}'s overhead leads to OOM, especially for complex models like PNA$^*$ that are resource-demanding. Sampling with SubgraphDrop enables training using practical resources. Notably, {\small\textsf{GNN-AK$^+$}}\xspace-S models, shown at the end of Table \ref{tab:real-world},  do not compromise and can \textit{even improve} performance as compared to their non-sampled counterpart, in alignment with Dropout's benefits \cite{srivastava2014dropout}.
Next we evaluate resource-savings, specifically on ZINC-12K and CIFAR10.
Table \ref{tab:subgraphdrop} shows that \mtdsp{GIN} 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
\begin{table}[h]
\vspace{-0.1in}
\setlength\extrarowheight{-5pt}
\fontsize{8}{8}\selectfont
    \caption{Resource analysis of SubgraphDrop. }\label{tab:subgraphdrop}
    \vspace{-0.1in}
    \centering
    \begin{tabular}{ll|ccccc|c|c}
    \toprule
    \multirow{2}{*}{Dataset}& & \multicolumn{5}{c|}{\textsf{GIN-AK$^+$-S}} & \multirow{2}{*}{\textsf{GIN-AK$^+$}} & \multirow{2}{*}{GIN} \\
                            & & $R$=1 &  $R$=2 &  $R$=3 &  $R$=4 &  $R$=5 &  &  \\
    \midrule
    \multirow{3}{*}{ZINC-12K}  &MAE &0.1216  &0.0929  &0.0846  &0.0852  &0.0854  &0.0806   &0.1630 \\
       &Runtime (S/Epoch) &10.8 &11.2 &12.0 &12.4 &12.5 &9.4  &6.0\\
       &Memory (MB) &392 &811 &1392 &1722 &1861 &1911  &124\\
    \midrule
    \multirow{3}{*}{CIFAR10}  &ACC &71.68 &72.07 &72.39 &72.20 &72.32 & 72.19 &59.82\\
       &Runtime (S/Epoch) &80.7 &89.1 &100.5 &110.9 &119.7 &241.1  &55.0\\
       &Memory (MB) &2576 &4578 &6359 &8716 &10805 &30296  &801\\
    \bottomrule
    \end{tabular}
     \vspace{-0.15in}
\end{table}

\subsection{Ablation Study}

We present ablation results on various structural components of {\small\textsf{GNN-AK$(^+)$}}\xspace in Appendix \ref{apdx:ablation}.
Table \ref{tab:subgraphs-size} shows the performance of \mtdp{GIN} for varying size egonets with $k$. Table \ref{tab:encoding} illustrates the added benefit of various encodings and D2C feature.
Table \ref{tab:ctx_d2c} extensively studies the effect of context encoding and D2C in {\small\textsf{GNN-AK$^+$}}\xspace, as they are not explained by Subgraph-1-WL$^*$. Table 9 studies the effect of base model's depth (or expressiveness) for {\small\textsf{GNN-AK$^+$}}\xspace with and without D2C.

\subsection{Additional Related Work}
\label{apdx:related}
{\bf Improving Expressiveness of GNNs:} Several works other than those mentioned in Sec.\ref{sec:intro} tackle expressive GNNs. \citet{murphy2019relational} achieve universality by summing permutation-sensitive functions across a combinatorial number of permutations, limiting feasibility.
\citet{coloring} adds node indicators to make them distinguishable, but at the cost of an invariant model, while \citet{NEURIPS2020_a32d7eea} further addresses the invariance problem, but at the cost of quadratic time complexity. \citet{pna} generalizes MPNN's default sum aggregator, but is still limited by $1$-WL.  \citet{dgn_icml21} generalizes spatial and spectral aggregation with ${>}1$-WL expressiveness, but using expensive eigendecomposition.  Recently, \cite{mpsn_icml21} introduce MPNNs over simplicial complexes that shares similar expressiveness as {\small\textsf{GNN-AK}}\xspace. \revise{\cite{ying2021transformers} studies transformer with above 1-WL expressiveness.} \cite{azizian2021expressive} surveys GNN expressiveness work.

\textbf{Connections to CNN and $k$-WL:}
{\small\textsf{GNN-AK}}\xspace has a similar convolutional structure as CNN, and in fact historically many spatial GNNs are inspired by CNN; see \citet{wu2020comprehensive} for a detailed survey. The non-Euclidean nature of graphs makes such generalizations non-trivial.
MoNet \citep{monet} introduces pseudo-coordinates for nodes, while PatchySAN \citep{patchy} 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, {\small\textsf{GNN-AK}}\xspace, generalizes CNN to graphs with a base GNN kernel, similar to how a CNN kernel encodes image patches. {\small\textsf{GNN-AK}}\xspace also shares connections with two variants of $k$-WL test algorithms: depth-$k$ $1$-dim WL \citep{cai1992optimal, weisfeiler1976construction} and deep WL \citep{arvind2020weisfeiler}.  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^k)$ size-$k$ subgraphs, we keep linear scalability by only applying 1-WL-equivalent MPNNs to O($n$) rooted subgraphs.

\subsection{Sampling by SubgraphDrop}
\label{apdx:subgraphdrop}

\begin{figure}[h]
    \centering
    \includegraphics{figs/GNN-AK-S.pdf}
    \vspace{-0.15in}
    \caption{{\small\textsf{GNN-AK}}\xspace-S with SubgraphDrop used in training. {\small\textsf{GNN-AK}}\xspace-S first extracts subgraphs and subsamples $m{\ll}|{\mathcal{V}}|$ 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 exist for  root nodes of selected subgraphs, and are propagated to estimate those of other nodes.}
    \label{fig:sampling}
\end{figure}

The descriptions of subgraph sampling strategies are as follows. Fig. \ref{fig:sampling} shows an overview of \textsf{\small{SubgraphDrop}}.
\begin{compactitem}[\textbullet]
    \item {\bf Random sampling} selects subgraphs randomly until every node is covered ${\ge}R$ times.
    \item {\bf 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 ${\ge}R$ times.
    \item {\bf 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 ${\ge}R$ times.
\end{compactitem}

\subsection{Proof of Theorem \ref{thm:equivalence}}\label{apdx:proof-of-equi}
\begin{proof}
\citep{xu2018powerful} proved that with sufficient number of layers and all injective functions, MPNN is as powerful as 1-WL. Then Eq.\ref{eq:gnn-ak} outputs different vectors for two graphs iff Subgraph-1-WL$^*$ encodes different labels with $c^{(t+1)}_v = \text{1-WL} (G^{(t)}[{\mathcal{N}}_k(v)])$. With \text{POOL} in Eq.\ref{eq:gnn-ak} also to be injective, \mtd{MPNN} outputs different vectors iff Subgraph-1-WL$^*$ outputs different fingerprints for two graphs. Then \mtd{MPNN} is as powerful as Subgraph-1-WL$^*$.
\end{proof}

\subsection{Proof of Theorem \ref{thm:above-1WL}}\label{apdx:proof-of-above-1WL}
\begin{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-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 are equivalent in expressiveness \citep{maron2019provably}. 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-1-WL$^*$ determines them as isomorphic. Then for any iteration $t$, set $\Big\{ \text{1-WL} (G^{(t)}[{\mathcal{N}}_1(v)]) | v \in {\mathcal{V}}_G \Big\}$ is the same as set $\Big\{ \text{1-WL} (H^{(t)}[{\mathcal{N}}_1(v)]) | v \in {\mathcal{V}}_H \Big\}$. Then there existing an ordering of nodes $v^G_1,..., v^G_n$ and $v^H_1,..., v^H_N$ with $N=|{\mathcal{V}}_G|=|{\mathcal{V}}_H|$, such that for any node order $i=1,...,N$, $\text{1-WL} (G^{(t)}[{\mathcal{N}}_1(v^G_i)]) = \text{1-WL} (H^{(t)}[{\mathcal{N}}_1(v^H_i)])$. This implies that structure $G[{\mathcal{N}}_1(v^G_i)]$ and $H[{\mathcal{N}}_1(v^H_i)]$ are not distinguishable by 1-WL. Hence $Star(v^G_i)$ and $Star(v^H_i)$ are hashed to the same label otherwise the 1-WL that includes the hashed result of $Star(v^G_i)$ and $Star(v^H_i)$ can also distinguish $G[{\mathcal{N}}_1(v^G_i)]$ and $H[{\mathcal{N}}_1(v^H_i)]$. Then for any iteration $t$ and any node with order $i$, $\text{HASH}\Big(Star(v_i^{G^{(t)}} )\Big) = \text{HASH}\Big( Star(v_i^{H^{(t)}}) \Big)$ 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 $\text{HASH} \Big( \big\{\text{HASH} (Star(v^{G^{(t)}})) , \text{1-WL} (G^{(t)}[{\mathcal{N}}_1(v)]) \big\}  \Big) $, this directly implies the above statement.

\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{figs/4-regular-graphs.pdf}
    \caption{Two 4-regular graphs that cannot be distinguished by 1-WL. Colored edges are the difference between two graphs. Two 1-hop egonets are visualized while all other rooted egonets are ignored as they are same across graph $A$ and graph $B$. }\label{fig:regular-graphs}
    \label{fig:my_label}
\end{figure}

In Figure \ref{fig:regular-graphs}, 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[{\mathcal{N}}_1(1)]$ and $B$'s egonet $B[{\mathcal{N}}_1(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$^*$.
\end{proof}

\subsection{Proof of Theorem \ref{thm:not-worse-3WL}}\label{apdx:proof-3WL}
\begin{figure}[h]
    \centering
    \includegraphics[width=\textwidth]{figs/3-wl-failed.pdf}
    \caption{Two non-isomorphic strongly regular graphs that cannot be distinguished by 3-WL. }
    \label{fig:3-wl-failed}
\end{figure}
\begin{proof}
We prove by showing a pair of 3-WL failed non-isomorphic graphs can be distinguished by Subgraph-1-WL \revise{(see definition of ``no less powerful'' in \cite{zhengdao2020can}: 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 $\text{HASH}(\cdot)$ is 3-WL discriminative. Figure \ref{fig:3-wl-failed} shows two strongly regular graphs that can not be distinguished by 3-WL (any strongly regular graphs are not distinguishable by 3-WL \citep{arvind2020weisfeiler}), along with their 1-hop egonet rooted subgraphs.
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 $\text{HASH}$ can distinguish the showed two 1-hop egonets.
\revise{Now we prove that 3-WL can distinguish these two \emph{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\times {4 \choose 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 $\text{HASH}(\cdot)$ 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.
\end{proof}

\subsection{Proof of Theorem \ref{thm:upper-bound}} \label{apdx:proof-upperbound}
\begin{proof}
For any $k\ge 3$, \cite{cai1992optimal} provided a scheme to construct a pair of $k$-WL-failed non-isomorphic 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 \cite{cai1992optimal}).

\revise{
We describe the proposed scheme of constructing the two graphs $A$ and $B$ briefly, for details see Section 6 in \cite{cai1992optimal}. At high level, this scheme first constructs $A$ by replacing every node (with degree $d$) in $G$ by a carefully designed graph $X_d$, and then rewires two edges in $A$ to its non-isomorphic counter graph $B$. Specifically, the small graph $X_d = ({\mathcal{V}}_d, {\mathcal{E}}_d)$ is defined as follows.
\begin{align}
   {\mathcal{V}}_d = &A_d \cup B_d \cup M_d, \text{where } A_d = \{a_i | 1 \le i \le d\}, B_d = \{b_i | 1 \le i \le d\}, \nonumber\\
        & \text{ and } M_d = \{m_S | S \subseteq\{1,...,d\}, |S| \text{ is even}  \} \label{eq:cfi}\\
    {\mathcal{E}}_d =& \{(m_S, a_i) | i \in S \} \cup \{(m_S,b_i ) | i \notin S \} \nonumber
\end{align}
Hence each vertex $v$ with degree $d$ in $G$ is replaced by a graph $X(v)=X_d$ of size $2^{d-1}+2d$, including a ``middle'' section $M_d$ of size $2^{d-1}$ and $d$ pairs of vertices $(a_i, b_i)$ representing ``end-points'' of each edge incident with $v$ in the original graph $G$. Let $(u,v) \in {\mathcal{E}}(G)$, then two small graphs $X(v)$ and $X(u)$ in $A$ are connected by the following. Let $(a_{u,v}, b_{u,v})$, $(a_{v,u}, b_{v,u})$ be the pair of vertices associated with $(u,v)$ in $X(u)$ and $X(v)$ respectively, then $a_{u,v}$ is connected to $a_{v,u}$, and $b_{u,v}$ is connected to $b_{v,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$, $a_{u,v}$ is connected to $b_{v,u}$ and $b_{u,v}$ is connected to $a_{v,u}$. \cite{cai1992optimal} 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 \ref{fig:CFI}.

\begin{figure}[ht]
    \centering
    \includegraphics[width=\textwidth]{figs/CFI.png}
    \caption{A pair of CFI graphs ($A$ and $B$) zoomed at the (rewired) edge $(u,v)$ of a base graph. The base graph is a degree-3 regular graph with separator size $k+1$ for $k$-WL-failed case. }
    \label{fig:CFI}
\end{figure}

We provide several useful lemmas related to graph $X_d$ in the following, which are then used in proving Theorem \ref{thm:upper-bound}.

\begin{lemma}[\cite{cai1992optimal}]\label{lm:autom}
$X_d$ has exactly $2^{d-1}$ automorphisms, and each automorphism is determined by interchanging $a_i$ and $b_i$ for each $i$ in some subset $S\subseteq \{1,...,d\}$ of even cardinality.
\end{lemma}
Lemma \ref{lm:autom} is directly taken from  Lemma 6.1 in \cite{cai1992optimal}.

\begin{lemma}\label{lm:diameter}
The shortest path distance between $a_i$ and $b_i$ in $X_d$ for any $i$ is exactly 4, and diameter of $X_d$ is 4.
\end{lemma}
\begin{proof}
Based on the construction shown in Eq.\ref{eq:cfi}, for any $i$, $a_i$ and $b_i$ are not directly connected, and any middle nodes share no connection. This implies the shortest path between $a_i$ and $b_i$ is larger than 3. Let $m_{S}$ be one middle node connected with $a_i$. We construct a new set $S'=\{p, q\}$, with $p\neq i,p \in S$ and $q\notin S$, then $m_{S'}$ connects with $b_i$ based on Eq.\ref{eq:cfi}. Additionally, $a_p$ connects to both $m_{S}$ and $m_{S'}$, which implies the shortest path distance between $a_i$ and $b_i$ $\le 4$. Hence, the shortest path distance between $a_i$ and $b_i$ is exactly 4.  To show the diameter of $X_d$ is 4, it's easy to observe that distance($a_i, b_i$) only decreases when replacing $a_i$ with other nodes in $X_d$ (or reverse, replacing $b_i$ with other nodes in $X_d$).
\end{proof}

\begin{lemma}\label{lm:ego}
For any $k\ge 1$, $k$-egonets of $a_i$ and $b_i$ in $X_d$ are isomorphic.
\end{lemma}
\begin{proof}
When $k\ge 4$, $X_d[{\mathcal{N}}_k(a_i)] = X_d[{\mathcal{N}}_k(b_i)] = X_d$ based on Lemma \ref{lm:diameter}. Now for $1\le k\le 3$, we analyze the $k$-hop egonets of $a_i$ and $b_i$ sequentially. First, $X_d[{\mathcal{N}}_1(a_i)]$ and $X_d[{\mathcal{N}}_1(b_i)]$ are two depth-1 trees with equal number of leaves (middle nodes in $X_d$), and of course are isomorphic. Similarly, $X_d[{\mathcal{N}}_2(a_i)]$ and $X_d[{\mathcal{N}}_2(b_i)]$ are two depth-2 trees with equal number of depth-1 nodes and equal number of leaves, which are also isomorphic. Last, $X_d[{\mathcal{N}}_3(a_i)]$ and $X_d[{\mathcal{N}}_3(b_i)]$ are the graphs by removing $b_i$ from $X_d$ and $a_i$ from $X_d$, respectively. It's trivial to observe that they are also isomorphic. Combining all cases proves the Lemma.
\end{proof}

To prove the main theorem,  we visualize the two graphs A and B zoomed at edge $(u,v)$ of base graph in Figure \ref{fig:CFI} to help understanding. To prove that Subgraph-1-WL with $t\leq 4$-egonet (we use $t$ to prevent notation conflict) cannot distinguish $A$ and $B$, we mainly analyze the subgraph around $a_{u,v}$ for both graph $A$ and $B$. For other subgraphs with different root nodes within $t$ shortest-path-distance around nodes $a_{u,v}, a_{v,u}, b_{u,v}, b_{v,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[{\mathcal{N}}_t(a_{u,v})]$ and $B[{\mathcal{N}}_t(a_{u,v})]$ be the two $t$-egonet subgraphs around $a_{u,v}$ in $A$ and $B$ respectively. Let $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ be the ``left'' part graph (visualized in Figure \ref{fig:CFI}, the left side of $a_{u,v}$, include $a_{u,v}$) of $A[{\mathcal{N}}_t(a_{u,v})]$, and $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ be the ``right'' part graph (visualized in Figure \ref{fig:CFI}, the right side of $a_{u,v}$, excluding $a_{u,v}$) of $A[{\mathcal{N}}_t(a_{u,v})]$. Then $A[{\mathcal{N}}_t(a_{u,v})]$ is reconstructed by connecting $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ and $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ with a single edge $(a_{u,v}, a_{v,u})$. $B^{left}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{right}[{\mathcal{N}}_t(a_{u,v})]$ are defined in the same way, such that $B[{\mathcal{N}}_t(a_{u,v})]$ is reconstructed by connecting $(a_{u,v}, b_{v,u})$ in $B$.

When $t\leq4$, we show that there exists an isomorphism that maps $A[{\mathcal{N}}_t(a_{u,v})]$ to $B[{\mathcal{N}}_t(a_{u,v})]$. We construct this isomorphism by constructing an isomorphism between $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{left}[{\mathcal{N}}_t(a_{u,v})]$ and an isomorphism between $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{right}[{\mathcal{N}}_t(a_{u,v})]$ first. Trivially, the current node ordering in $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{left}[{\mathcal{N}}_t(a_{u,v})]$ already defines an isomorphism among them, that is, mapping any $a_i$ ($b_i, m_S$) in $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ to $a_i$ ($b_i, m_S$) in $B^{left}[{\mathcal{N}}_t(a_{u,v})]$. To find an isomorphism between $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{right}[{\mathcal{N}}_t(a_{u,v})]$, one can easily observe that for $t\le 3$, $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ can be 1-to-1 mapped (with $a_{v,u}$ in $A$ being mapped to $a_i$) to $X_3[{\mathcal{N}}_{t-1}(a_i)]$ and $B^{right}[{\mathcal{N}}_t(a_{u,v})]$ can be 1-to-1 mapped (with $b_{v,u}$ in $A$ being mapped to $b_i$) to $X_3[{\mathcal{N}}_{t-1}(b_i)]$ for some $i$. When $t=4$, $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ is mapped to $X_3[{\mathcal{N}}_{3}(a_i)]$ with additional 2 nodes and $B^{right}[{\mathcal{N}}_t(a_{u,v})]$ is mapped to $X_3[{\mathcal{N}}_{3}(b_i)]$ with additional 2 nodes. Then applying Lemma \ref{lm:ego}, when $t\le 4$ we can construct an isomorphism between $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ and $N^{right}[{\mathcal{N}}_t(a_{u,v})]$ with $a_{v,u}$ in $A$ being mapped to $b_{v,u}$ in $B$. We remark that when $t=4$, the two additional nodes outside $X_3[{\mathcal{N}}_{3}(a_i)]$ and $X_3[{\mathcal{N}}_{3}(b_i)]$ does not affecting applying Lemma \ref{lm:ego}. Last, the combination of the isomorphism between $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{left}[{\mathcal{N}}_t(a_{u,v})]$ and the isomorphism between $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ and $B^{right}[{\mathcal{N}}_t(a_{u,v})]$ is actually a new isomorphism between $A[{\mathcal{N}}_t(a_{u,v})]$ and $B[{\mathcal{N}}_t(a_{u,v})]$, as the edge $(a_{u,v}, a_{v,u})$ is mapped to edge $(a_{u,v}, b_{v,u})$. Thus, when $t\le 4$, $A[{\mathcal{N}}_t(a_{u,v})]$ and $B[{\mathcal{N}}_t(a_{u,v})]$ are isomorphic and $\text{HASH}(A[{\mathcal{N}}_t(a_{u,v})])= \text{HASH}(B[{\mathcal{N}}_t(a_{u,v})])$ no matter what $\text{HASH}(\cdot)$ 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\le 4$ cannot distinguish the two graphs $A$ and $B$ that are $k$-WL-failed for any $k\ge 3$.
}
\end{proof}

\revise{
We remark that the theorem doesn't imply that Subgraph-1-WL with $t\ge5$-egonet can distinguish $A$ and $B$. This should depend on the base graph. We give an informal sketch. Suppose that for $t\ge 5$,  the left part $A^{left}[{\mathcal{N}}_t(a_{u,v})]$ and right part $A^{right}[{\mathcal{N}}_t(a_{u,v})]$ are only connected through $(a_{u,v}, a_{v,u})$, that is, removing $(a_{u,v}, a_{v,u})$ from $A[{\mathcal{N}}_t(a_{u,v})]$ resulting in $A^{left}[{\mathcal{N}}_t(a_{u,v})]$  and $A^{right}[{\mathcal{N}}_t(a_{u,v})]$  being disconnected. Then we can apply Lemma \ref{lm:autom} multiple times with mapping some $a_{v,u}$ in A to $b_{v,u}$ in B and $b_{v,u}$ in A to $a_{v,u}$ in B, until this kind of switches reach the boundary of $A[{\mathcal{N}}_t(a_{u,v})]$, resulting in an isomorphism between $A[{\mathcal{N}}_t(a_{u,v})]$  and $B[{\mathcal{N}}_t(a_{u,v})]$. We refer the reader to Lemma 6.2 in \cite{cai1992optimal}, which also uses this line of argument.
}

\subsection{Proof of Proposition \ref{conj:suffi}} \label{apdx:sufficient-condition}
\revise{
\begin{proof}
The proof is by contradiction. Let $G$ and $H$ be two non-isomorphic graphs and $|V_G|=|V_H|$ (if graph sizes are different then  Subgraph-1-WL can trivially distinguish them). Now suppose that Prop. \ref{conj:suffi} 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 \textit{same} histogram of subgraph colors. Now we focus on iteration 0. Formally, let color $c^G_{v,i}=\text{HASH}(G[{\mathcal{N}}_k(v^G_i)])$ and $c^H_{v,i}=\text{HASH}(H[{\mathcal{N}}_k(v^H_i)])$ for a node order $v$ ($v^G_i$ maps index $i$ to a node in $G$). According to Condition (1): for any node reordering $v^G_1,..., v^G_{N_{G}}$ and $v^H_1,..., v^H_{N_{H}}$, $\exists i\in [1,\max(N_{G},N_{H})]$ that $G[{\mathcal{N}}_k(v^G_i)]$ and $H[{\mathcal{N}}_k(v^G_i)]$ are non-isomorphic, then we know that $\exists i$ that $G[{\mathcal{N}}_k(v^G_i)]$ and $H[{\mathcal{N}}_k(v^H_i)]$ are non-isomorphic, hence $c^G_{v,i}\neq c^H_{v,i}$ since by Condition (2) $\text{HASH}$ can distinguish these two subgraphs. However as two graphs have the same histogram of subgraph colors, there must be a $j\neq i$ such that $c^G_{v,i}= c^H_{v,j}$ and $c^G_{v,j}= c^H_{v,i}$. Then we can create a new node order $m$ by swapping $v^G_i$ 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 $\forall i \in 1,...,|V_G|$, $c^G_{w,i}= c^H_{w,i}$. As $\text{HASH}$ is discriminative enough according to Condition (2), this implies $\forall i \in 1,...,|V_G|$, $G[{\mathcal{N}}_k(w^G_i)]$ and $H[{\mathcal{N}}_k(w^H_i)]$ are isomorphic, which contradicts with Condition (1). Thus, Prop. \ref{conj:suffi} must be true.
\end{proof}
}

\subsection{Proof of Proposition \ref{conj:plus}}\label{apdx:plus}
\revise{
\begin{proof}
When a pair of non-isomorphic graphs $G$ and $H$ cannot be distinguished by {\small\textsf{GNN-AK$^+$}}\xspace, for any layer $l$, the histogram of $h_v^{(l))}$ in $G$ and $H$ in Eq. \ref{eq:gnn-ak-plus-realization} should be the same. Which implies that for any layer $l$, the histogram of $h_v^{(l))}$ in $G$ and $H$ in Eq. \ref{eq:gnn-ak-realization} should be the same. Then {\small\textsf{GNN-AK}}\xspace cannot distinguish $G$ and $H$. So for any pair of non-isomorphic graphs, {\small\textsf{GNN-AK}}\xspace cannot distinguish them if {\small\textsf{GNN-AK$^+$}}\xspace cannot distinguish them. Thus {\small\textsf{GNN-AK$^+$}}\xspace is more powerful than {\small\textsf{GNN-AK}}\xspace.
\end{proof}
}

\subsection{Dataset Description \& Statistics}

\begin{table}[h!]
\fontsize{8.7}{9.2}\selectfont
 \setlength{\tabcolsep}{1pt}
    \caption{Dataset statistics.}\label{tab:data-semantics}
    \centering
    \begin{tabular}{llcccc}
    \toprule
    Dataset & Task Semantic & \# Cls./Tasks & \# Graphs & Ave. \# Nodes & Ave. \# Edges  \\
    \midrule
    EXP  & Distinguish 1-WL failed graphs & 2  & 1200 & 44.4 & 110.2\\
    SR25 & Distinguish 3-WL failed graphs & 15 & 15   & 25   & 300\\
    \midrule
    CountingSub. & Regress num. of substructures   & 4& 1500 / 1000 / 2500& 18.8 & 62.6\\
    GraphProp.   & Regress global graph properties & 3& 5120 / 640 / 1280 & 19.5 & 101.1 \\
    \midrule
    ZINC-12K  & Regress molecular property    & 1  & 10000 / 1000 / 1000& 23.1 & 49.8\\
    CIFAR10   & 10-class classification          & 10 & 45000 / 5000 / 10000& 117.6 & 1129.8 \\
    PATTERN   & Recognize certain subgraphs   & 2  & 10000 / 2000 / 2000& 118.9 & 6079.8\\
    \midrule
    MolHIV    & 1-way binary classification   & 1  & 32901 / 4113 / 4113& 25.5 & 54.1\\
    MolPCBA   & 128-way binary classification & 128 & 350343 / 43793 / 43793 & 25.6 & 55.4 \\
    \midrule
    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 \\
    \bottomrule
    \end{tabular}
\end{table}

\subsection{Experimental Setup Details}
\label{apdx:experimental-setup}
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 {\small\textsf{GNN-AK$(^+)$}}\xspace. While hyperparameters may not be optimal for other GNN models, the evaluation is fair as there is no benefit for {\small\textsf{GNN-AK$(^+)$}}\xspace. Next, we search {\small\textsf{GNN-AK$(^+)$}}\xspace exclusive ones (encoding types) over validation set using \mtdall{GIN} and keep them fixed for other \mtdall{GNN}.
We use a $1$-layer base model for \mtdall{GNN}, with exceptions that we tune  number of layers of base model (while keeping total number of layers fixed) for \mtd{GNN}  in simulation datasets (presented in Table \ref{tab:simulation}).
We use $3$-hop egonets for \mtdall{GNN}, with exceptions that CIFAR10 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 {\small\textsf{GNN-AK$(^+)$}}\xspace-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.

\subsection{Ablation Study}
\label{apdx:ablation}

We present ablation results on various structural components of {\small\textsf{GNN-AK}}\xspace.
Table \ref{tab:subgraphs-size} shows the performance of \mtd{GIN} 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.

\begin{table}[!htb]
\fontsize{8}{9.2}\selectfont

    \begin{minipage}{.4\linewidth}
      \caption{Effect of various $k$-egonet size.}\label{tab:subgraphs-size}

        \centering
        \begin{tabular}{l|cc}
        \toprule
         $k$ of \textsf{GIN-AK$^+$} & ZINC-12K & CIFAR10 \\
        \midrule
        GIN & 0.163 $\pm$ 0.004 & 59.82 $\pm$ 0.33\\
        \midrule
        $k = 1$    & 0.147 $\pm$ 0.006 & 71.37 $\pm$ 0.28\\
        $k = 2$     & 0.120 $\pm$ 0.005 & 72.19 $\pm$ 0.13\\
        $k = 3$ & 0.080 $\pm$ 0.001 & OOM\\
        \bottomrule
        \end{tabular}
    \end{minipage}
    $\;$
    \begin{minipage}{.6\linewidth}
      \caption{Effect of various encodings }\label{tab:encoding}
        \vspace{-0.1in}
        \centering
        \begin{tabular}{l|cc}
        \toprule
        Ablation of \textsf{GIN-AK$^+$} & ZINC-12K & CIFAR10 \\
        \midrule
        Full & 0.080 $\pm$ 0.001 & 72.19 $\pm$ 0.13\\
        \midrule
        w/o Subgraph encoding    & 0.086 $\pm$ 0.001 & 67.76 $\pm$ 0.29\\
        w/o Centroid encoding    & 0.084 $\pm$ 0.003 & 72.20 $\pm$ 0.96\\
        w/o Context encoding     & 0.088 $\pm$ 0.003 & 69.25 $\pm$ 0.30\\
        w/o Distance-to-Centroid & 0.085 $\pm$ 0.001 & 71.91 $\pm$ 0.22\\
        \bottomrule
        \end{tabular}
    \end{minipage}
\end{table}

Next Table \ref{tab:encoding} illustrates the added benefit of various node encodings. Compared to the full design, eliminating any of the subgraph, centroid, or context encodings (Eq.s (\ref{eq:subgraph-emb-0})--(\ref{eq:context-emb}))  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.

\revise{
As {\small\textsf{GNN-AK$^+$}}\xspace is not directly explained by Subgraph-1-WL$^*$ (though D2C is supported by Subgraph-1-WL, by strengthening $\text{HASH}$), we conduct additional ablation studies over {\small\textsf{GNN-AK$^+$}}\xspace with different combinations of removing context encoding and D2C, shown in Table \ref{tab:ctx_d2c}.  Note that all experiments in Table \ref{tab:ctx_d2c} are using a 1-layer base GIN model. We summarize the observations as follows.

\begin{compactitem}[\textbullet]
\item For real-world datasets (ZINC-12K, CIFAR10), We observe that the largest performance improvement over base model comes from wrapping base GNN with Eq.\ref{eq:gnn-ak} (the performance of \textsf{GIN-AK}), while adding context encoding and D2C monotonically improves performance of {\small\textsf{GNN-AK$^+$}}\xspace.

\item For substructure counting and graph property regression tasks, we observe D2C significantly increases the performance of \textsf{GIN-AK$^+$ w/o Ctx} (supported by the theory of Subgraph-1-WL where the $\text{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 \cite{li2020distance}), resulting in a more expressive {\small\textsf{GNN-AK$^+$}}\xspace, 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 \textsf{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.
\end{compactitem}
\begin{table}[h]
\setlength{\tabcolsep}{1pt}
\vspace{-0.05in}
\fontsize{7.5}{9.2}\selectfont
    \caption{Study {\small\textsf{GNN-AK}}\xspace without context encoding (Ctx) and without distance-to-centroid (D2C). Base model is \textbf{1-layer} GIN for all methods.}\label{tab:ctx_d2c}
    \vspace{-0.1in}
    \centering
    \begin{tabular}{l| c c| cc| cccc | ccc}
    \toprule
     \multirow{2}{*}{Method} &\multirow{2}{*}[-1mm]{\makecell{ZINC-12K \\ (MAE)}} & \multirow{2}{*}[-1mm]{\makecell{CIFAR10 \\ (ACC)}} & \multirow{2}{*}[-1mm]{\makecell{EXP \\ (ACC)}} & \multirow{2}{*}[-1mm]{\makecell{SR25 \\ (ACC)}} & \multicolumn{4}{c|}{Counting Substructures (MAE)} & \multicolumn{3}{c}{Graph Properties ($\log_{10}$(MAE))} \\
     \cmidrule(l{2pt}r{2pt}){6-9} \cmidrule(l{2pt}r{2pt}){10-12}
                             &      &   & &   & Triangle & Tailed Tri. & Star & 4-Cycle          &  IsConnected & Diameter & Radius \\
    \midrule
     GIN      & 0.163 & 59.82 &  50\%& 6.67\%& 0.3569 & 0.2373 & 0.0224 & 0.2185 & -1.9239 & -3.3079 & -4.7584 \\
    \midrule
    GIN-AK & 0.094 & 67.51 &  100\%& 6.67\%& 0.2311 & 0.1805 & 0.0207 & 0.1911 & -1.9574 & -3.6925& -5.0574\\
    \midrule
    GIN-AK$^+$ w/o Ctx      & 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 \\
    \midrule
    \textsf{GIN-AK$^+$}  & 0.080 & 72.19 & 100\%& 6.67\%& 0.0123 & 0.0112 & 0.0150 & 0.0126 & -2.7513 & -3.9687 & -5.1846 \\
    \bottomrule
    \end{tabular}
    \vspace{-0.1in}
\end{table}

\begin{table}[h]
\setlength{\tabcolsep}{2pt}
\vspace{-0.05in}
\fontsize{7.7}{9.2}\selectfont
    \caption{Study the effect of base model's number of layers while keeping total number of layers in {\small\textsf{GNN-AK}}\xspace fixed. Different effect is observed for {\small\textsf{GNN-AK}}\xspace and {\small\textsf{GNN-AK}}\xspace without D2C. }\label{tab:d2c_inner}
    \vspace{-0.1in}
    \centering
    \begin{tabular}{l|c c| cccc | ccc}
    \toprule
     \multirow{2}{*}{Method} & \multirow{2}{*}[-1mm]{\makecell{GIN-AK's\\ \#Layers}} & \multirow{2}{*}[-1mm]{\makecell{Base GIN's\\ \#Layers}} & \multicolumn{4}{c|}{Counting Substructures (MAE)} & \multicolumn{3}{c}{Graph Properties ($\log_{10}$(MAE))}\\
     \cmidrule(l{2pt}r{2pt}){4-7} \cmidrule(l{2pt}r{2pt}){8-10}
         & & & Triangle & Tailed Tri. & Star & 4-Cycle          &  IsConnected & Diameter & Radius \\
     \midrule
     GIN & 0 & 6 & 0.3569 & 0.2373 & 0.0224 & 0.2185 & -1.9239 & -3.3079 & -4.7584\\
     \midrule
    \multirow{2}{*}{GIN-AK}
    & 6 & 1& 0.2311 & 0.1805 & 0.0207 & 0.1911 & -1.9574 & -3.6925& -5.0574\\
    & 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\\
    & 1 & 6& 0.0934 & 0.0751 & 0.0216 & 0.0726 & -1.9916 & -3.6555 &-4.9249 \\
     \midrule
     \midrule
     \multirow{4}{*}{GIN-AK$^+$ w/o D2C} & 6 & 1 & 0.1746 & 0.1449 & 0.0193 & 0.1467 & -2.0521 & -3.6980& -5.0984\\
       & 3 & 2 & 0.1244 & 0.1052 & 0.0219 & 0.1121 & -2.1538 & -3.7305 & -4.9250 \\
       & 2 & 3 & 0.1021 & 0.0830 & \fontseries{b}\selectfont 0.0162 & 0.0986 & \fontseries{b}\selectfont -2.2268 & \fontseries{b}\selectfont -3.7585 & \fontseries{b}\selectfont-5.1044\ \\
       & 1 & 6 & \fontseries{b}\selectfont 0.0885 & \fontseries{b}\selectfont 0.0696 & 0.0174 & \fontseries{b}\selectfont 0.0668 & -2.0541 & -3.6834 & -4.8428 \\
      \midrule
     \multirow{4}{*}{GIN-AK$^+$ with D2C} & 6 & 1 & 0.0123 & 0.0112 & 0.0150 & 0.0126 & \fontseries{b}\selectfont -2.7513 & \fontseries{b}\selectfont -3.9687 & \fontseries{b}\selectfont -5.1846\\
       & 3 & 2 & 0.0116 & 0.0100 & 0.0168 & 0.0122 & -2.6827 & -3.8407 & -5.1034\\
       & 2 & 3 & 0.0119 & 0.0102 & 0.0146 & 0.0127 & -2.6197 & -3.8745 & -5.1177\\
       & 1 & 6 & 0.0131 & 0.0123 & 0.0174 & 0.0162 & -2.5938 & -3.7978 & -5.0492\\
     \bottomrule
    \end{tabular}
    \vspace{-0.1in}
\end{table}

According to Prop. \ref{conj:suffi}, the base model must be discriminative enough such that $\text{HASH}(G[{\mathcal{N}}_k(v^G_i)]) \neq \text{HASH}(H[{\mathcal{N}}_k(v^H_i)])$, 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 {\small\textsf{GNN-AK$^+$}}\xspace, with and without D2C in Table \ref{tab:d2c_inner}.
\begin{compactitem}[\textbullet]
\item Firstly, {\small\textsf{GNN-AK$^+$}}\xspace 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 {\small\textsf{GNN-AK$^+$}}\xspace'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 {\small\textsf{GNN-AK$^+$}}\xspace's (outer) depth.

\item Secondly, {\small\textsf{GNN-AK$(^+)$}}\xspace without D2C suffers from a trade-off between the base model's expressiveness (depth of base model) and the number of {\small\textsf{GNN-AK$(^+)$}}\xspace 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, {\small\textsf{GNN-AK$(^+)$}}\xspace cannot benefit from increasing the outer depth. Hence the number of layers of the base model are important for the expressiveness of {\small\textsf{GNN-AK$(^+)$}}\xspace when D2C is not used.
\end{compactitem}
}

\clearpage
\subsection{Additional Results on TU Datasets}\label{apdx:tu}
We also report additional results on several smaller datasets from TUDataset \citep{Morris+2020}, with their statistics reported in last block of Table \ref{tab:data-semantics}. The training setting and evaluation procedure follows \cite{xu2018powerful} 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 \cite{bodnar2021b} with their method labeled as CIN, for references to all baselines see \cite{bodnar2021b}. The result is shown in Table \ref{tab:tud_datasets}.

\begin{table}[!h]
\fontsize{9}{9.2}\selectfont
    \centering
    \caption{Results on TU Datasets. First section contains methods of graph kernels, second section has GNNs, and third is the method in \cite{bodnar2021b}. The top two are highlighted by \first{First}, \second{Second}, \third{Third}.}
    \label{tab:tud_datasets}
    \begin{tabular}{l|llllll}
        \toprule
        Dataset & MUTAG &PTC &PROTEINS &NCI1 & IMDB-B & RDT-B \\
        \midrule

        RWK  & 79.2$\pm$2.1 &  55.9$\pm$0.3 & 59.6$\pm$0.1 & $>$3 days & N/A & N/A \\

        GK ($k=3$) &81.4$\pm$1.7 & 55.7$\pm$0.5 &71.4$\pm$0.31 & 62.5$\pm$0.3 &N/A &N/A \\

        PK & 76.0$\pm$2.7&  59.5$\pm$2.4 & 73.7$\pm$0.7 &  82.5$\pm$0.5 & N/A & N/A \\

        WL kernel &
        90.4$\pm$5.7 &
        59.9$\pm$4.3 &
        75.0$\pm$3.1 &
        \first{86.0$\pm$1.8} &
        73.8$\pm$3.9 &
        81.0$\pm$3.1 \\
        \midrule

        DCNN & N/A&  N/A &61.3$\pm$1.6 &56.6$\pm$1.0  & 49.1$\pm$1.4 &N/A \\

        DGCNN & 85.8$\pm$1.8 & 58.6$\pm$2.5 &  75.5$\pm$0.9 & 74.4$\pm$0.5 &70.0$\pm$0.9  &N/A \\

        IGN &83.9$\pm$13.0 & 58.5$\pm$6.9 &76.6$\pm$5.5 &74.3$\pm$2.7  &  72.0$\pm$5.5 &N/A \\

        GIN & 89.4$\pm$5.6 & 64.6$\pm$7.0& 76.2$\pm$2.8 &82.7$\pm$1.7  & 75.1$\pm$5.1 &
        \third{92.4$\pm$2.5} \\

        PPGNs  &9
        0.6$\pm$8.7 &
        66.2$\pm$6.6 &
        \first{77.2$\pm$4.7} &
        83.2$\pm$1.1 &
        73.0$\pm$5.8 & N/A \\

        Natural GN  &
        89.4$\pm$1.6 &
        66.8$\pm$1.7 &
        71.7$\pm$1.0 &
        82.4$\pm$1.3 &
        73.5$\pm$2.0 &
        N/A\\

        GSN &
        \second{92.2 $\pm$ 7.5} &
        \second{68.2 $\pm$ 7.2} &
        76.6 $\pm$ 5.0 &
        83.5 $\pm$ 2.0 &
        \first{77.8 $\pm$ 3.3} &
        N/A \\

        SIN &
        N/A  &
        N/A &
        76.4 $\pm$ 3.3 &
        82.7 $\pm$ 2.1 &
        \second{75.6 $\pm$ 3.2} &
        92.2 $\pm$ 1.0 \\

        \midrule

        CIN &
        \first{92.7 $\pm$ 6.1} &
        \first{68.2 $\pm$ 5.6} &
        \third{77.0 $\pm$ 4.3} &
        \third{83.6 $\pm$ 1.4} &
        \third{75.6 $\pm$ 3.7} &
        \second{92.4 $\pm$ 2.1} \\
        \midrule
        \mtdp{GIN} &
        \third{91.3 $\pm$ 7.0} &
        \third{67.7 $\pm$ 8.8} &
        \second{77.1 $\pm$ 5.7} &
        \second{85.0 $\pm$ 2.0} &
        75.0 $\pm$ 4.2 &
        \first{94.8 $\pm$ 0.8}\\

        \bottomrule

    \end{tabular}
\end{table}

We mark that the performance of \mtdp{GIN} over IMDB-B is not improved because each graph in the dataset is an 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 on average 10 validation curves over 10 folds.

\section{Introduction}\label{sec:intro}
\input{01-intro}

\section{Related work}\label{sec:related}
\input{02-related}

\section{General Framework and Theory}\label{sec:model-general}
\input{03-model-general}

\section{Concrete Realization}\label{sec:model-concrete}
\input{04-model-concrete}

\section{Improving Scalability: SubgraphDrop}\label{sec:sampling}
\input{05-sampling}

\section{Experiments}\label{sec:exp}
\input{06-experiments}
\section{Conclusion}
\input{07-conclusion}

\clearpage

redpajama_set_name: RedPajamaArXiv


Parents are enjoying a growing number of policies and programs that give them more power to choose how their children are educated. Private school voucher and tax-credit scholarship programs, charter schools, public school choice, and tax credit and deduction programs are all helping give hundreds of thousands of parents across the country more and better educational options.
Education savings accounts (ESAs) are the latest parental choice innovation. ESAs let parents withdraw their children from public school and instead receive a portion of the funding that would have gone to that public school for their child in a designated savings account. Parents can then use those funds to pay for authorized education expenses, including private school tuition, tutoring, test preparation, and online courses. Any leftover funds remain in the child's designated ESA and can be used to pay for future education expenses, such as college.
Currently, ESA programs in Arizona and Florida are helping parents of students with unique needs personalize their children's educational experience, and early research shows that ESAs are working for students. In recent years, Arizona lawmakers have expanded the program to include students in or assigned to failing public schools, students from the foster care system, and students whose parents serve in the military. However, every child is unique, and therefore all states should explore moving toward an ESA system to allow for more personalizing learning for all students.


text:
Mon, 03 Jun 2019 04:03:25 GMT
6.3: Enzymatic catalysis - the basic ideas
[ "article:topic", "authorname:soderberg", "authorname:soderbergt", "showtoc:no" ]
https://chem.libretexts.org/@app/auth/3/login?returnto=https%3A%2F%2Fchem.libretexts.org%2FUnder_Construction%2FPurgatory%2FBook%253A_Organic_Chemistry_with_a_Biological_Emphasis_(Soderberg)%2FChapter_06%253A_Introduction_to_organic_reactivity_and_catalysis%2F6.3%253A_Enzymatic_catalysis_-_the_basic_ideas
Book: Organic Chemistry with a Biological Emphasis (Soderberg)
6: Introduction to Organic Reactivity and Catalysis
Contributed by Tim Soderberg
Emeritus Associate Professor of Chemistry at University of Minnesota Morris
We come now to the subject of catalysis. Our hypothetical bowl of sugar (from section 6.2) is still stubbornly refusing to turn into carbon dioxide and water, even though by doing so it would reach a much more stable energy state. There are, in fact, two ways that we could speed up the process so as to avoid waiting several millennia for the reaction to reach completion. We could supply enough energy, in the form of heat from a flame, to push some of the sugar molecules over the high energy hill. Heat would be released from the resulting exothermic reaction, and this energy would push more molecules over their energy hills, and so on - the sugar would literally burn up.
A second way to make the reaction go faster is to employ a catalyst. You probably already know that a catalyst is an agent that causes a chemical reaction to go faster by lowering its activation energy.
How might you catalyze the conversion of sugar to carbon dioxide and water? It's not too hard – just eat the sugar, and let your digestive enzymes go to work catalyzing the many biochemical reactions involved in breaking it down. Enzymes are proteins, and are very effective catalysts. 'Very effective' in this context means very specific, and very fast. Most enzymes are very selective with respect to reactant molecules: they have evolved over millions of years to catalyze their specific reactions. An enzyme that attaches a phosphate group to glucose, for example, will not do anything at all to fructose (the details of these reactions are discussed in section 10.2B).
Glucose kinase is able to find and recognize glucose out of all of the other molecules floating around in the 'chemical soup' of a cell. A different enzyme, fructokinase, specifically catalyzes the phosphorylation of fructose.
We have already learned (section 3.9) that enzymes are very specific in terms of the stereochemistry of the reactions that they catalyze . Enzymes are also highly regiospecific, acting at only one specific part of a molecule. Notice that in the glucose kinase reaction above only one of the alcohol groups is phosphorylated.
Finally, enzymes are capable of truly amazing rate acceleration. Typical enzymes will speed up a reaction by anywhere from a million to a billion times, and the most efficient enzyme currently known to scientists is believed to accelerate its reaction by a factor of about 1017 (see Chemical and Engineering News, March 13, 2000, p. 42 for an interesting discussion about this enzyme, orotidine monophosphate decarboxylase).
We will now begin an exploration of some of the basic ideas about how enzymes accomplish these amazing feats of catalysis, and these ideas will be revisited often throughout the rest of the text as we consider various examples of enzyme-catalyzed organic reactions. But in order to begin to understand how enzymes work, we will first need to learn (or review, as the case may be) a little bit about protein structure.
Organic Chemistry With a Biological Emphasis by Tim Soderberg (University of Minnesota, Morris)
α-Elimination
Tim Soderberg

redpajama_set_name: RedPajamaCommonCrawl


text:
Channels Channel 5 HD Jason Statham's Blitz Forum
Jason Statham's Blitz
Jason Statham's Blitz Crime thriller set in London starring Jason Statham and Paddy Considine. A maverick detective tries to track down a serial killer who has been targeting police officers. (2011)[S] Tue, Jul 9, 12:10 AM Channel 5 45 mins
Jason Statham's Blitz Crime thriller set in London starring Jason Statham and Paddy Considine. A maverick detective tries to track down a serial killer who has been targeting police officers. (2011)[S] Mon, Jul 8, 11:05 PM Channel 5 60 mins
Jason Statham's Blitz Crime thriller set in London starring Jason Statham and Paddy Considine. A maverick detective tries to track down a serial killer who has been targeting police officers. (2011)[S] Mon, Feb 25, 12:10 AM Channel 5 45 mins
Jason Statham's Blitz Crime thriller set in London starring Jason Statham and Paddy Considine. A maverick detective tries to track down a serial killer who has been targeting police officers. (2011)[S] Sun, Feb 24, 11:05 PM Channel 5 60 mins


Image Title: Slide Beds Shop Top Selling Bunks Lofts With Slides Maxtrix Pertaining To Girls Bunk Bed Ideas 6. Post Title: Girls Bunk Bed. Filename: slide-beds-shop-top-selling-bunks-lofts-with-slides-maxtrix-pertaining-to-girls-bunk-bed-ideas-6.jpg. Image Dimension: 800 x 544 pixels. Images Format: jpg/jpeg. Publisher/Author: Camryn Beer. Uploaded Date: Wednesday - October 03rd. 2018 20:59:15 PM. Category: Architecture. Image Source: houseandgarden.co.uk. Ana White Playhouse Loft Bed With Stairs DIY Projects For Girls Bunk Designs 13. Bunk Beds Kids Bunkbeds For Boys Girls Cuckooland Intended Bed Decor 17. White Girls Loft Bed With Desk To Throughout Bunk Ideas 11. Slide Beds Shop Top Selling Bunks Lofts With Slides Maxtrix Pertaining To Girls Bunk Bed Ideas 6. Bunk Beds For Girl Twin Over Full Ideas Of Girls With Bed Remodel 5. The Dollhouse Bunkbed By Imagine THAT Playhouses More B With Girls Bunk Bed Decor 9. Mermaid Bedding Girls Bedroom Ideas Pinterest In Bunk Bed Plan 0. Sleep Study Loft PBteen Intended For Girls Bunk Bed Designs 14. Beautiful Way To Personalize Bunk Beds In A Girls Room She Wants Throughout Bed Prepare 19. Alamak Twin Over Full Bunk Bed For Girls In White Xiorex Intended Ideas 2.


Lousy customer service. Delivers wrong pizza more often than not. This store could use some adult supervision!
I live a mile and a half away from the pizza hut store and they don't deliver to my area. Wtf?
From Business: Experience the Flavor Of Now from your neighborhood Pizza Hut in Kansas City.
Never keep enough Pepsi on hand and received cold pizza's on too many occasions even though I' less than 2 miles from the store.
From Business: Experience the Flavor Of Now from your neighborhood Pizza Hut in Olathe.
Spelling should be "Minsky"s. We have been dining at a Minsky's since the late 1970's and it's hard to believe that it keeps getting better!! Service at this location is amazing and there is no better pizza anywhere around.The restaurant is always clean & family friendly!!Our favorite has always been a large combo on original crust.Parking is terrific.
Victoria my server was so friendly, the food was great like always, and management came by to make sure we enjoyed our meal.
Minsky's never disappoints! The staff is friendly, service is great, and the food is excellent! Our server, Victoria, was wonderful, as always. She is personable, remembers us when we come in, and always takes great care of us.
Minsky's in Raymore, MO has the very best Margaritas in the area. The Manager (Melvin) and our server (Jasmine) make sure our every visit is perfect! The food is great and the people that work there are too..Count us as satisfied and regular customers.Peggy and Bill W.
Great atmosphere!!! Great food!!! Fast service!! Even had good iced tea. And our server, Chandra was awesome!!! She was just the right amount of professional and sassy that made it fun.
Minsky's has great pizza and calzones as well as fast and friendly service. Will visit this location again in the near future.
Each time we have been, the food and service has always been great. Whether it is pizza or the lasagna, it has come out hot and fresh.
awesome food and service !!


text:
Tag: video games
fivepaw – Point Taken
I hadn't thought about the video game Alex Kid in Miracle World for probably around 20 years, until the other day I saw it was getting a re-release: a fancy, updated version for modern hardware, and one of those games where you look at the new footage and think "Yeah, that's how I remember it looking" until you go back and look at original Master System / Megadrive footage and realise that actually what it looked like was a few dozen pixels thrown on a screen seemingly at random with barely any discernible detail and ordered to jump frantically around, the kind of thing that if you were forced to play now you wouldn't last five minutes. I'm not going to play the remake, as I don't want to be reminded of a) how old I am and b) how jaded I am, but knowing that it exists and is scratching a few people's itching nostalgia is comfort enough. In my head, the soundtrack is exactly like this new track from fivepaw which is taken from his latest album, and if it's not, I don't want to know.
https://fivepaw.bandcamp.com/releases
Tags chiptune, electronic, fivepaw, point taken, video games
Patricia Taxxon – Dandelion
I've come to realise just how much of an impact computer game soundtracks – specifically the 8 and 16-bit bleeps of my Master System and Megadrive-obsessed youth – has had on the music I've enjoyed for the rest of my life. I compared last year's brilliant Scacco Matto album by Lorenzo Senni to Lemmings, and now we have the outrageously prolific Patricia Taxxon back with yet another album including the wonderful Dandelions, which sounds like a cut from a modern version of a 90s Final Fantasy OST. As ever with Taxxon's music the entire album Sapphire Apts is available to stream on YouTube, and even though Dandelions is a definite highlight, there's plenty more nostalgic fun to be had throughout.
https://patriciataxxon.bandcamp.com
Tags dandelion, electronic, patricia taxxon, sapphire appts, video games
Olivier Deriviere – The Storm Boat
Like a lot of teenagers who discovered video games in the late 80s/early 90s, I played A LOT of Streets of Rage. The occasional out of control tantrum and smashed controller aside, I have very fond memories of that time, and especially of the soundtrack, so the newly released Streets of Rage 4 had a lot to live up to in that department. Happily they've delivered not only a fantastic game, but a brilliant OST which ropes in some of the original producers alongside newcomers like Olivier Deriviere who manage to preserve the frantic 8-bit rush of the 90s series while bringing the production bang up to date.
http://olivierderiviere.com
Tags electronic, Olivier Deriviere, ost, streets of rage, the storm boat, video games


text:
Thinking Ahead
Blog Post created by Barbara Wallraff on Jul 25, 2018
We're told that people who hope to have fulfilling careers now and in the coming decades must be adaptable. That's because technologies such as the internet and artificial intelligence are changing the kinds of jobs for which college is intended to prepare students and the skills they'll need to do a given job well.
Consider your own job: You probably use a course management system, though such things barely existed 20 years ago. No doubt you're also familiar with Wikipedia, Twitter, digital textbooks, blogs, Prezi, plagiarism detection systems, hyperlinking, and so on. Technology keeps shaking things up, and technologists warn that the pace of change can only increase.
Rapid change is expected in part because artificial intelligence has become capable of doing many things—identifying individuals in photos, driving and parking a car, and learning from experience, for instance—that once were the exclusive province of people. AI continues to encroach on, or assist with, many increasingly highly skilled kinds of work. So students must be prepared to have all kinds of innovations thrown at them throughout their careers. They will need to view change as a constant.
And then there's "correct English," which changes at a glacial pace. The fundamental structures of English change hardly at all. New nouns and verbs and adjectives may be coined every day, but they're still nouns and verbs and adjectives, doing the jobs they've always done. New prepositions and conjunctions, however, scarcely ever enter English—these are considered "closed" classes of words. Pronouns, too, had long been considered a closed class, though new gender-neutral forms like "ze," "nem," "vis," and the singular "they" are vying with one another to join the mainstream. Even a "glacial pace" of change is speeding up, figuratively as well as literally.
Of course, it's a good thing to be conversant with the norms of traditional prose, because these makes centuries' worth of writing accessible. We can, for example, read and enjoy Shakespeare. But contemporary literature is ever more inclusive, celebrating ever more registers of English. A few of many possible examples would be the fiction of Jesmyn Ward and Jhumpa Lahiri, and George Saunders's Lincoln in the Bardo, winner of the 2017 Man Booker Prize.
On the nonfiction side, traditional norms allow us to admire, for example, Charles Darwin's insights in On the Origin of Species—even as we might wish he'd been able to write it in blog form and post videos of species as he came across them on his travels. (The first edition of Origin had just one illustration, a simple branching diagram.)
The norms of scholarly writing by now have diverged far from those for literature—journal articles, for instance, intentionally rely on the passive voice and colorless, if precise, terminology. Further, the vocabularies of scholarly and technical literature are expanding as rapidly as the fields of research: nanotechnology, mesosociology, biomedical engineering, artificial neural networks, and so on. Most of the world's scientists and engineers and so on write in English—but often it's not an English that people outside a small circle can understand.
Even the range of genres available to us has broadened, largely thanks to the technology of the internet. Online, multimodal compositions are coming to be the norm, with text paired with photos, videos, interactive graphics, and so on.
I doubt we can even guess how advances in technology will change our language in the near future and how we use it. Will "it's" get folded into the spelling "its" because software has trouble distinguishing when to use each form, or will the software catch up with educated human understanding? Will the preferred pronunciations of words become the ones that Siri, Alexa, and Google Assistant recognize most readily? Will grammatically correct phrases that a grammar checker underlines come to be considered incorrect?
But those are just fine points. Taking a longer and wider view, I remember a U.K. ESL specialist explaining to me almost 20 years ago that speech to text automation was coming along, automated translation software was coming along, text to speech was coming along too—and pretty soon the three processes were likely to become one sequence and we'd be able to converse with almost anyone, each of us in our preferred language. That ability is now tantalizingly close. Once simultaneous translation becomes widely available, it's bound to shake many things up. And that's only an example of the kinds of technologies on the horizon that have the potential to profoundly affect our lives, our work, and our use of language.
What does all this suggest for the present and future of English comp? To me, it suggests that students need to know that there's no one correct way of writing anymore, if there ever was one. Certainly, there are better and worse ways—better and worse registers and tones—in different genres, for different audiences.
Would your students benefit from an assignment like the following? Let's imagine a surprising archaeological find was recently made near your campus. They might write it up in three to five different genres—maybe as a tweet; as if they had taken part in or watched the dig and are telling a friend about it; as a brief local news story; as a report for an archaeology wiki or blog; and as an academic paper based on firsthand sources or the outline for such a paper.
An assignment like this may not do much to get your students ready for changes to the language and technology yet to come. But this one might help them better understand how diverse is the range of registers and media and genres already available to them—and how adaptable they will probably need to be in their writing.
Do you have questions about language or grammar, or are there topics you would like me to address? If so, please email me at bwallraff@mac.com or comment below!
Image Credit: Pixabay Image 2228610 by Seanbatty, used under a CC0 Creative Commons License
rhetorical knowledge
Content tagged with rhetorical knowledge
grammar and style
Content tagged with grammar and style
writing conventions
Content tagged with writing conventions
Content tagged with teaching with technology
Content tagged with composition
Categories: Barbara Wallraff, Writing with Style