Structural Optimization Makes Graph Classification Simpler and Better

About This Paper

Junran Wu, Jianhao Li, Yicheng Pan, Ke Xu

State Key Lab of Software Development Environment, Beihang University

http://arxiv.org/abs/2109.02027

Preliminary

我们要做的是 图分类任务 (Graph Classification).

主要有两种范式：核方法以及神经网络方法。

针对这两种范式，作者提出了两种新的算法：

核方法：WL-ET kernel, 对标之前的 WL subtree kernel

神经网络方法：ETL, 对标之前的 GNN

ET=Encoding Tree, WL=Weisfeiler-Lehman, ETL=Encoding Tree Learning

Structural Optimization

在进行 WL-ET kernel 的计算以及 ETL 之前，首先得有 ET, 即 Encoding Tree.

在介绍 ET 前，先介绍结构熵。

给定 Graph G G G, 我们可以找到它的一个划分，划分的每个元素都是一棵 Tree，基于 Tree 可以计算一个熵值：结构熵。

关于划分以及结构熵，可以参考 My Blog.

对于图 G = ( V , E , w ) G=(V,E,w) G=(V,E,w) , 它的一棵 Tree (记作 T \mathcal{T} T) 的结构熵为:

H T ( G ) = − ∑ α ∈ T , α ≠ λ g α vol ⁡ ( V ) log ⁡ vol ⁡ ( α ) vol ⁡ ( α − ) \mathcal{H}^{\mathcal{T}}(G)=-\sum_{\alpha \in \mathcal{T}, \alpha \neq \lambda} \frac{g_{\alpha}}{\operatorname{vol}(V)} \log \frac{\operatorname{vol}(\alpha)}{\operatorname{vol}\left(\alpha^{-}\right)} HT(G)=−∑α∈T,α​=λ​vol(V)gα​​logvol(α−)vol(α)​

其中， α ∈ T \alpha \in \mathcal{T} α∈T 并且 α ≠ λ \alpha \neq \lambda α​=λ, λ \lambda λ 表示树的根部， α − \alpha^- α− 表示 α \alpha α 的 predecessor.

规定， T α = ∪ β − = α T β T_{\alpha}=\cup_{\beta^{-}=\alpha} T_{\beta} Tα​=∪β−=α​Tβ​ ( β \beta β 表示节点)， T β T_{\beta} Tβ​ 表示和 β \beta β 有关联的 V V V 的子集。那么这里的：

v o l ( α ) vol(\alpha) vol(α) 表示 T α T_{\alpha} Tα​ 的 Volume. g α g_{\alpha} gα​ 表示从 T α T_{\alpha} Tα​ 内节点到 T α T_{\alpha} Tα​ 外节点的边的数量。

关于此式的推导，参见 My Blog.

记图的维度为 K K K, 那么图 G G G 的结构熵为： H K ( G ) = min ⁡ T { H T ( G ) } \mathcal{H}^{K}(G)=\min _{\mathcal{T}}\left\{\mathcal{H}^{\mathcal{T}}(G)\right\} HK(G)=minT​{HT(G)}.

如果规定我们的 Tree 的高度为 k k k, 那么： H ( k ) ( G ) = min ⁡ T : height ⁡ ( T ) ≤ k { H T ( G ) } \mathcal{H}^{(k)}(G)=\min _{T: \operatorname{height}(T) \leq k}\left\{\mathcal{H}^{T}(G)\right\} H(k)(G)=minT:height(T)≤k​{HT(G)}

有了结构熵之后，我们基于此设计一个算法，它能根据图生成相应的 Encoding Tree

这里使用的是 这篇论文 中提出的 Clustering 算法，详细可以参见论文，这里简要介绍一下。

这个算法可以类比决策树，决策树通过信息增益(比)等去判断是否添加或者合并某一个分支，这里也是类似的，只不过使用的是信息熵，并且希望它尽可能地小。

还是类比决策树，决策树生成这里对应的是 Stretch, 决策树剪枝这里对应的是 Compress.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-yq39M7fU-1632212467781)(https://static01.imgkr.com/temp/ec74d0f419164c9db0a76e38c0ac9bf1.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-qFMMuAAW-1632212467794)(https://static01.imgkr.com/temp/39509fc9b3814058a54418b4bf67487f.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DIg7yLaF-1632212467795)(https://static01.imgkr.com/temp/bc81f43788a4494989d927b01bb160e0.png)]

完整的算法 k-HCSE 如下：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-chz8mJrX-1632212467798)(https://static01.imgkr.com/temp/a749611c96f84d06bd494dce479efb57.png)]

就这样，我们生成了一棵 Tree，就是 Encoding Tree.

Tree Kernel

对标之前的 WL subtree kernel 方法，这里的新算法是 WL-ET kernel 方法，主要是两点不同：

1. Hierarchical Reporting Scheme
2. 特征向量的表示不同：使用的是节点标签的计数

首先介绍 Hierarchical Reporting Scheme.

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-zSjFw90G-1632212467801)(https://static01.imgkr.com/temp/b9d62afdc2e74854811f39ac3cd57d76.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-anebwkwY-1632212467802)(https://static01.imgkr.com/temp/ccfc3452a1fd408ca91d50dad0f18c7c.png)]

然后计算 kernel :

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cwM3a84u-1632212467804)(https://static01.imgkr.com/temp/e2af07b1e0fe43b8b4004d622e4566b0.png)]

有了 kernel 之后，我们可以使用它计算两张图的相似度，当然，我们也可以使用基于 kernel 的机器学习算法进行图分类，典型的算法就是大家熟知的 SVM. 本文采用的是 C-SVM，参见 Libsvm: a library for support vector machines.

ETL

这里对标的是 GNN 方法。

框架还是 Hierarchical Reporting Scheme，但是做一个泛化。

首先是特征的向上传播，之前用的是 multiset-label determination and sorting, 这里使用 MLP 对 hidden state 进行传播，具体地：

r v i = M L P i ( ∑ u ∈ C ( v ) r u ( i − 1 ) ) r_{v}^{i}=\mathbf{M L P}^{i}\left(\sum_{u \in \mathcal{C}(v)} r_{u}^{(i-1)}\right) rvi​=MLPi(∑u∈C(v)​ru(i−1)​) ，其中， C ( ⋅ ) \mathcal{C}(·) C(⋅) 表示 ⋅ · ⋅ 的 successor； r u r_u ru​ 表示 hidden state, 初始为 X v X_v Xv​.

这个特征的更新比起 GNN 来说，简单了不少。

最后用于分类的话，很自然地想法是使用最终层的表示。但实验发现，一些初始层的表示对于分类更加有效，因此采用下面的方法获得整棵树的表示：

r T = C O N C A T ( LAYERPOOL ⁡ ( { r v i ∣ v ∈ T i } ) ∣ i = 0 , 1 , … , h ) r_{T}= CONCAT \left(\operatorname{LAYERPOOL}\left(\left\{r_{v}^{i} \mid v \in T^{i}\right\}\right) \mid i=0,1, \ldots, h\right) rT​=CONCAT(LAYERPOOL({rvi​∣v∈Ti})∣i=0,1,…,h)

其中， L A Y E R P O O L LAYERPOOL LAYERPOOL 可以是求和，也可以是平均，因此，可以看作是 kernel 方法的一个泛化。

Analysis

无论是 WL-ET kernel，还是 ETL，都大大地简化了复杂度。

设 tree 的高度为 h h h, 边的数量为 m m m, 节点数量为 n n n, 那么：

WL subtree kernel : O ( h m ) O(hm) O(hm), while WL-ET kernel : O ( n ) O(n) O(n).

对于 SVM 来说，需要计算所有 tree 两两之间的 kernel, 对于这两个算法，都是 O(N^2)

GNN : O ( h m ) O(hm) O(hm), while ETL : O ( n ) O(n) O(n)

因此，论文标题中我们说 Simpler.

那么 Better 呢？从实验的结果数据中我们不难发现，性能确实有些许提升。

Conclusion

总之，分为两步，Feature Extraction 和 Feature Combination

Feature Extraction 通过求解使得结构熵最小的 ET 来解决，即 Structural Optimization.

Feature Combination 通过 Hierarchical Reporting Scheme 来解决，主要是两种形式：

• 一般形式：即 multiset-label determination and sorting + label compression + relabeling
• 泛化形式：即 MLP 进行 hidden state 的向上传播

最后对于图分类任务，

• 一般形式的话：通过 WL-ET kernel + C-SVM 去进行图分类
• 泛化形式的话：通过特征向量去进行图分类

特征向量：即 r T = C O N C A T ( LAYERPOOL ⁡ ( { r v i ∣ v ∈ T i } ) ∣ i = 0 , 1 , … , h ) r_{T}= CONCAT \left(\operatorname{LAYERPOOL}\left(\left\{r_{v}^{i} \mid v \in T^{i}\right\}\right) \mid i=0,1, \ldots, h\right) rT​=CONCAT(LAYERPOOL({rvi​∣v∈Ti})∣i=0,1,…,h)

其中， L A Y E R P O O L LAYERPOOL LAYERPOOL 又可以看作 kernel 的泛化。

泛化形式的这一套就是 ETL 方法。

More

Structural Entropy

Structural Optimization : k-HCSE

Kernel Method : WL subtree kernel

GNN Method : GIN for example

About Me

ZenMoore