Introduction
SubGNN在学习子图representation时保留子图的三种属性：Position，Neighborhood，Structure，每种属性包含Internal 和Border两方面，并且要精心设计不同的anchor patch，所以过于复杂。通过分析SubGNN和普通GNN，作者发现子图表示的核心可能是区分子图内部和外部节点。基于此发现，本文提出了一种labeling trick, 即max-zero-one，来提升子图GNN的表达能力和可拓展性。
Subgraph representation task 如上图所示，目标子图$\mathbb{S}$被嵌入在整个图中，并且可能拥有多个连通分量，目标是学习子图的表示向量，使其可以预测子图的属性。NeurIPS2020文章SubGNN提出子图级message-passing来代替节点级的message passing，并且设计了三个message passing通道，每个通道分为内部和边界模块，分别捕获子图分量间的交互，以及子图与图的其他部分之间的交互。尽管取得了比普通GNN更好的效果，但是SubGNN需要繁琐的预计算，因为SubGNN通过不同采样规则的anchor patch来传递子图分量之间，以及子图分量与图其他部分之间的相关性，而三个通道共6个aspects需要不同的采样规则，以及各自的message passing，计算十分冗长（这里有解读）。另外 SubGNN对每个aspects需要使用不同的anchor patch随机采样策略，无法保证采样的anchor patch是最优的，因此效果的方差较大，使得鲁棒性堪忧。
通过对比SubGNN相较于普通GNN的优势，作者发现对于子图任务来说，区分子图内部节点和外部节点非常重要。基于这个发现，本文提出了一种labeling trick，即max-zero-one labeling trick，来标注每个节点是否在子图外或者子图内。
Labeling Trick [1]: 使用GNN生成multi-node representations （即，为一组节点，例如子图生成表示向量），该方法说明了为高阶结构生成有表达能力的representation，需要捕获结构内不同节点间的交互。在实现上，labeling trick通过一个专门设计的label来表示节点的结构特征，这个label与node feature 结合作为新的feature输入GNN中。
注： 本文只考虑诱导子图，即每个子图的每个连通分量保留原图中的所有边。
Plain GNN and SubGNN
如上图所示，$G$是一个regular graph, 所以在没有节点feature的情况下，每个节点的embedding相同，所以GNN无法区分子图$\mathcal{S}$和$\mathcal{S}^\prime$。如下图所示，Plain GNN 在message passing中子图$\mathcal{S}$内部节点1同时接收来自子图内和子图外的邻居信息，并不会加以区分。同样$\mathcal{S}^\prime$中节点3也同时接收子图内外节点，因此对于Plain GNN ，它无法区分节点1和3，因此无法区分两个子图。
而SubGNN引入了3个通道：position (P)，neighborhood (N), 和structure (S) 每个通道分别学习Internal 和Border两方面，共6个属性融入子图表示学习中。对于子图$\mathcal{S}$，为了捕获某个通道$i$的属性，SubGNN首先随机采样$n_A$个anchor patches： $\mathbb{A}_{i}=\left\{\mathcal{A}_{i}^{(1)}, \ldots, \mathcal{A}_{i}^{\left(n_{A}\right)}\right\}$，然后学习$\mathcal{S}$中的每个连通分量在这个属性$i$下的表示向量，通过子图内部连通分量和anchor patches之间的消息传递，来捕获子图内部连通分量的相对位置/邻域/结构信息，以及子图连通分量相对于子图外部分的位置/邻域/结构信息。如图2右边所示。对于通道$i$，它的Internal和border两方面采样的anchor patches表示为$\mathbb{A}_{i}=\left\{\mathcal{A}_{i}^{(1)}, \ldots, \mathcal{A}_{i}^{\left(n_{A}\right)}\right\}$，对于子图$\mathcal{S}$的一个连通分量$\mathcal{S}^{(c)}$，要学习该连通分量的表示，可使用一下subgraph-level message passing layer: $$ \begin{aligned} &\boldsymbol{a}_{i, \mathcal{S}^{(c)}}=\sum_{\mathcal{A}_{i} \in \mathbb{A}_{i}} \gamma_{i}\left(\mathcal{S}^{(c)}, \mathcal{A}_{i}\right) \boldsymbol{g}_{\mathcal{A}_{i}}, \\ &\boldsymbol{h}_{i, \mathcal{S}^{(c)}}^{(k)}=\sigma\left(W_{i} \cdot\left[\boldsymbol{a}_{i, \mathcal{S}^{(c)}}, \boldsymbol{h}_{i, \mathcal{S}^{(c)}}^{(k-1)}\right]\right) \end{aligned} $$ 其中$\gamma_{i}\left(\mathcal{S}^{(c)}, \mathcal{A}_{i}\right)$是子图分量$\mathcal{S}^{(c)}$和一个anchor patch $\mathcal{A}_{i}$的相似度。即每个子图分量依照与anchor patch 的相似度聚合来自anchor的信息。由于相似度函数的存在，SubGNN实际上是使用与子图分量$\mathcal{S}^{(c)}$接近或结构相似的anchor patch对$\mathcal{S}^{(c)}$的representation做平滑，即$\mathcal{S}^{(c)}$聚合更多与它结构相似的anchor patches的信息。通过精心设计的anchor和subgraph-level message passing，6个属性可以被各自保留，然后在融合。
Plain GNN 存在的问题在于不能很好的表示内部结构和外部结构，即Plain GNN在message passing过程中不能为子图中的节点判断它的邻居是在子图内还是子图外。 而SubGNN如Figure 2右边所示， 子图内节点1接收Internal消息和border消息在两个独立的message passing中，回味每个节点生成2个表示向量，分别表示内部MP和外部MP，因为节点1和3内外部节点不一样，所以SubGNN可以为这两个节点生成不同的representations。
GLASS：Gnns with LAbeling trickS for Subgraph
首先介绍zero-one label trick：
Definition 1 （zero-one label trick）: 给定一个图$\mathcal{G}$和它的一个子图$\mathcal{S}$，对与子图$\mathcal{S}$， 图$\mathcal{G}$中的任意一个节点$v$的zero-one标签为： $$ l_{v}^{(\mathcal{S})}= \begin{cases}1 & \text { if } v \in \mathbb{V}_{\mathcal{S}} \\ 0 & \text { if } v \notin \mathbb{V}_{\mathcal{S}}\end{cases} $$ 即对于一个子图$\mathcal{S}$，对图中所有节点赋予一个node label，用来区分节点在$\mathcal{S}$内外。
Max-Zero-One Labeling Trick
对每个节点做zero-one labeling trick可以区分一个子图的内外节点，因此zero-one labeling trick难以做batch training。因为为一个子图标记内部节点和外部节点，可以得到一个labeled graph （子图内节点为1，子图外节点为0），也就是对于一个graph $\mathcal{G}$，每个子图都需要专门生成一个该子图的labeled graph, 不同子图的labeled graph 也不同。如果要为每个子图都构造labeled graph, 再各自在每个labeled graph上做独立的message passing，得到每个labeled graph对应的子图embedding，这样过于耗时。
为了减轻上述每个组图对应一个特定的labeled graph 问题，本文认为可以为一个batch 子图生成一个labeled graph，这样的话，通过一次message passing就可以计算一个batch subgraphs的representations。为了结合一个batch 子图的zero-one labels，从而生成一个公共的labeled graph， 本文进一步提出了Max-Zero-One Labeling Trick。具体来说，一个batch的所有子图只生成一个labeled graph，其中，该batch内所有子图内节点都被赋予label 1, 所有子图外节点都被赋予label 0， 然后在labeled graph 上做GNN，就可以一次性学习一个batch子图的representations。
作者认为如果目标子图稀疏的分布在图中的话，一个子图外有其他节点被赋予1标签的影响是微不足道的，因为浅层GNN也不会聚合到远距离的节点。另外这么做还可以避免对一个子图的过拟合。
Implementation
Input: Graph $\mathcal{G}$ , 所有子图subG_node = [[subgraph 1], [subgraph 2], [subgraph 3], ...]， $z=[0,0,1,0,1,1,0,0,1, \cdots]$ 为batch subgraphs对应的labeled graph, 在batch subgraphs中的节点为1，不在的为0。
以下为一层GLASS：
对于每个节点特征，分别做两个线性变换
x1 = MLP_1(x) # 节点充当batch subgraphs内节点时的embedding x0 = MLP_0(x) # 节点充当batch subgraphs外节点时的embedding对于label=1的节点 （batch 子图内的节点）
特征 $x = \alpha x_1 + (1-\alpha)x_0$， 对于ppi_bp数据集，$\alpha = 0.95$为超参数，若节点是batch子图内的节点，保留更多$x_1$。
对于label=0的节点 （batch 子图外的节点）
$x = (1-\alpha)x_1 + \alpha x_0$，对于不在batch子图中的节点，保留更多$x_0$。
通过这种方式，子图内外的节点得以区分
Message Passing:
$x = (D^{-1}A)X$
GraphNorm:
$x = \mathrm{GraphNorm}(x)$
Residual:
$x = \mathrm{cat}(x_, x)$ //和初始特征拼接
再次区分batch subgraph 内外节点：
x1 = MLP_2(x) x0 = MLP_3(x)再对子图内外节点做不同的组合
$x = \alpha x_1 + (1-\alpha)x_0$： 子图内节点
$x = (1-\alpha)x_1 + \alpha x_0$： 子图外节点
可以发现，如果$\alpha = 1$，那么相当于子图内节点用$x_1$， 子图外节点用$x_0$，这样就彻底区别了子图内外的节点。即， 对于邻居聚合操作来说，如果聚合到了子图外邻居，那么子图外邻居使用$\mathrm{MLP}_0$变换过的特征，如果聚合到子图内的节点，使用$\mathrm{MLP}_1$变换过的特征。
一点理论
Proposition 1: 给定图$G$，$\mathcal{S}$和$\mathcal{S}^\prime$，如果Plain GNN可以区分的子图，GLASS也一定可以区分。但是存在Plain GNN不能区分但GLASS可以区分的子图。
Proof: 首先证明给定任意Plain GNN model $m_1$，存在一个GLASS模型$m_2$，使得对于目标子图$\mathcal{S}$，$m_1$和$m_2$的输出相同，也就是GLASS至少可以和Plain GNN一样expressive。
假设Plain GNN $m_1$ 的第$k$层 $\mathrm{AGGREGATE}$函数为$f^{(k)}_1$，$\mathrm{COMBINE}$函数为$g^{(k)}_1$， 第$k$层$\mathrm{READOUT}$函数为$\phi_1$，那么Plain GNN可以表达为： $$ \begin{aligned} &\boldsymbol{a}_{v}^{(k)}=\operatorname{AGGREGATE}^{(k)}\left(\left\{\boldsymbol{h}_{u}^{(k-1)} \mid u \in N(v)\right\}\right) = f^{(k)}_1 \left(\left\{\boldsymbol{h}_{u}^{(k-1)} \mid u \in N(v)\right\}\right) \\ &\boldsymbol{h}_{v}^{(k)}=\operatorname{COMBINE}^{(k)}\left(\boldsymbol{h}_{v}^{(k-1)}, \boldsymbol{a}_{v}^{(k)}\right) = g^{(k)}_1\left(\boldsymbol{h}_{v}^{(k-1)}, \boldsymbol{a}_{v}^{(k)}\right) \\ &\boldsymbol{h}_{\mathcal{S}}=\operatorname{READOUT}\left(\left\{\boldsymbol{h}_{u} \mid u \in \mathbb{V}_{\mathcal{S}}\right\}\right) = \phi_1\left(\left\{\boldsymbol{h}_{u} \mid u \in \mathbb{V}_{\mathcal{S}}\right\}\right) \end{aligned} $$ 接下来设计GLASS，将每层节点特征定义为$\operatorname{CONCATENATE}\left(\boldsymbol{h}_{u}^{(k-1)}, \boldsymbol{l}^{(\mathcal{S})}\right)$，即每层拼接该节点的label （是否在子图中），基于universal approximation theorem，一定存在一个函数$\theta$, 使得$\theta\left(\operatorname{CONCATENATE}\left(\boldsymbol{h}_{u}^{(k-1)}, \boldsymbol{l}^{(\mathcal{S})}\right)\right)=\boldsymbol{h}_{u}^{(k-1)}$，那么GLASS可以定义为： $$ \begin{aligned} \boldsymbol{h}_{u}^{\prime(k-1)} &=\operatorname{CONCATENATE}\left(\boldsymbol{h}_{u}^{(k-1)}, \boldsymbol{l}^{(\mathcal{S})}\right), \\ \boldsymbol{a}_{v}^{(k)} &=f_{1}^{(k)}\left(\left\{\theta \left(\boldsymbol{h}_{u}^{\prime (k-1)}\right) \mid u \in N(v)\right\}\right) \\ \boldsymbol{h}_{v}^{(k)} &=g_{1}^{(k)}\left(\boldsymbol{h}_{v}^{(k-1)}, \boldsymbol{a}_{v}^{(k)}\right) \end{aligned} $$ 因为$\theta \left(\boldsymbol{h}_{u}^{\prime (k-1)}\right) = \theta\left(\operatorname{CONCATENATE}\left(\boldsymbol{h}_{u}^{(k-1)}, \boldsymbol{l}^{(\mathcal{S})}\right)\right)=\boldsymbol{h}_{u}^{(k-1)}$， Plain GNN 是上述特定形式GLASS的特例，所以GLASS使得至少与Plain GNN 表达能力相同。
Figure 2给出了Plain GNN不能区分但GLASS可以区分的子图实例。
Theorem 1： 给定任意图$\mathcal{G}$，存在一个GLASS model，可以准确预测$\mathcal{G}$中任意子图的density 和cut ratio。
Proof: 一个图的Density定义为： $$ D = \frac{2 |E|}{|V| \cdot|V-1|} $$ 即图中实际存在的边数，占左右节点对可能构成的总边数的比例
一个子图$\mathcal{S}$的cut ratio定义为： $$ \mathrm{CR}(\mathcal{S}) = \frac{|B_{\mathcal{S}}|}{|\mathcal{S}| \cdot |\mathcal{G} \backslash \mathcal{S}|} $$ 为子图和其他部分之间的边数$|B_{\mathcal{S}}|$, 占子图和其他部分可能存在的总边数的比例。其中$B_{S}=\{(u, v) \in E \mid u \in S, v \in G \backslash S\}$。 $$ \begin{aligned} \boldsymbol{a}_{v}^{(1)} &=\sum_{u \in N(v)}\left(\boldsymbol{l}_{u}^{(\mathcal{S})}\left[\begin{array}{l} 1 \\ 0 \\ 0 \end{array}\right]+\left[\begin{array}{l} 0 \\ 1 \\ 0 \end{array}\right]\right) = \left[\begin{array}{l} N(v)中存在于\mathcal{S}的节点数量\quad m \\ N(v)中\mathcal{S}以外节点数量 \quad n\\ 0 \end{array}\right] \\ \boldsymbol{h}_{v}^{(1)} &=\left[\begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ 0 & 0 & 0 \end{array}\right] \boldsymbol{a}_{v}^{(1)}+\left[\begin{array}{l} 0 \\ 0 \\ 1 \end{array}\right] = \left[\begin{array}{l} m \\ n-m \\ 1 \end{array}\right] \\ \boldsymbol{h}_{\mathcal{S}} &=\sum_{v \in \mathbb{V}_{\mathcal{S}}} \boldsymbol{h}_{v}^{(1)} = \left[\begin{array}{l} 子图内边数 \\ 边界边数-子图内边数\\ 子图内节点数 \end{array}\right] \end{aligned} $$ 其中$l_{u}^{(\mathcal{S})}$为节点$u$的zero-one label，如果$u$在子图$\mathcal{S}$中，那么为1不在为0。 因此子图$\mathcal{S}$的Density $d$和 cut ratio $c$可以由上述定义的GLASS模型推导出： $$ \begin{aligned} &d\left(\boldsymbol{h}_{\mathcal{S}}\right)=\left(\left[\begin{array}{l} 1 \\ 0 \\ 0 \end{array}\right]^{T} \boldsymbol{h}_{\mathcal{S}}\right) /\left[\left(\left[\begin{array}{l} 0 \\ 0 \\ 1 \end{array}\right]^{T} \boldsymbol{h}_{\mathcal{S}}\right) \cdot\left(\left[\begin{array}{l} 0 \\ 0 \\ 1 \end{array}\right]^{T} \boldsymbol{h}_{\mathcal{S}}-1\right)\right] \\ &c\left(\boldsymbol{h}_{\mathcal{S}}\right)=\left(\left[\begin{array}{c} 0 \\ 0.5 \\ 0 \end{array}\right]^{T} \boldsymbol{h}_{\mathcal{S}}\right) /\left[\left(\left[\begin{array}{l} 0 \\ 0 \\ 1 \end{array}\right]^{T} \boldsymbol{h}_{\mathcal{S}}\right) \cdot\left(n-\left[\begin{array}{l} 0 \\ 0 \\ 1 \end{array}\right]^{T} \boldsymbol{h}_{\mathcal{S}}-1\right)\right] . \end{aligned} $$
Reference
[1] Labeling trick: A theory of using graph neural networks for multi-node representation learning. NeurIPS2021