论文笔记：A Simple yet Effective Method for Graph Classification

A Simple yet Effective Method for Graph Classification

Introduction

现在很多研究通过增加模型的复杂性来提高性能，比如增加深度，增加一个复杂的组件，或者而这并行，但是却很少有研究通过简化基本模型学习流程来提高性能的方法。

结构熵：这是一种用来评估图的结构信息的度量，图的基本结构可以被这个度量解码为其层次结构的复杂性的衡量标准。

因此，如图1所示，本文提出了一种算法，将图的数据样本转换为相应的编码树，反映了图的层次组织，其中图潜藏的关键结构信息可以以 最小结构熵 保留在编码树中。

image.png

在简化的编码树的基础上，提出了一种新的图分类特征组合方案，称为层次报告。在该方案中，我们基于编码树的层次结构，将特征从叶节点转移到根节点。针对两种基本的学习算法，基于核的方法和GNN，本文提出了相应的简化学习算法。

在树核和卷积网络上提出了本文方案的实现，以威斯费勒-莱曼编码树Weisfeiler-Lehman coding tree（WL-CT）和层次报告网络hierarchical reporting network (HRN)，进行图片分类。树核遵循Weisfeiler-Lehman (WL)子树核中的标签传播，但运行时复杂度较低，为 $O(n)$ 。 HRN是本文的树核在深度学习领域的实现。本文在多个图像分类数据集上验证了WL-CT核和HRN算法。本文的树核算法在核算法中达到了最佳性能，甚至在一些基准上超过了GNN。本文的HRN算法同样在大多数基准上达到了最佳性能。
本文的贡献如下：

提出了新的方向，在减少复杂度的情况下提高性能。
通过最小化结构熵，本文将给定的数据样本从图优化到是更简单的数据结构编码树，也保留了图形的关键结构信息。
提出了2个有效的学习算法，i.e.,WL-CT和HRN，并按经验展示其在图象分类基准上的鉴别能力。

Related Work

略GNN

图的结构熵被定义为在特定编码模式下随机游走得到的码字的平均长度。也就是说，当一个随机游走一步从节点 $u$ 到节点 $v$ ，编码树上节点 $u$ 和节点 $v$ 的最长公共祖先码字，也就是它们的最长公共前缀，会被省略。这能够缩短平均码字长度，随机游走的不确定性也有这个值来表达，这是结构熵一词的起源。一图的编码树实现最小结构熵，代表了最优的层次结构。
对于关于图的任务，结构熵可以用来解码基本结构，作为其层次结构的复杂性度量。

Methodology

Graph Simplification via Structural Entropy Minimization

给定 $G = (V,E)$ 和它的编码树 $T$ ，其中 $\vert V \vert = n$ ， $\vert E \vert = m$

图 $G$ 在 $T$ 上的结构熵：
$\mathcal{H}^T(G)=-\sum_{v_t \in T}{\frac{g_ {v_t}}{vol(V)}\log{\frac{vol(v_t)}{vol(v_t^+)}}},\qquad(1)$

$v_t$ 是 $T$ 中的一个非根节点，代表了一个节点子集 $\in V$

$v_t^+$ 代表 $v_t$ 的父母节点

$g_{v_t}$ 是以 $v_t$ 为一个顶点的边的数量

$vol(V)$ 和 $vol(v_t)$ 分别是 $V$ 和 $v_t$ 中节点的度的和

$G$ 的结构熵是所有编码树的最小熵，可以公式化表示为 $\mathcal{H}(G)=\min_T{\{\mathcal{H}^T(G)\}}, \qquad (2)$

为了构建一个具有一定高度的自然编码树，对任意正整数 $k$ ，图 $G$ 的 $k$ 维结构熵，是所有高度最大为 $k$ 的编码树的最小值。
$\mathcal{H}^{(k)}(G)=\min_{T:height(T)\leq k}{\{\mathcal{H}^T(G)\}}$

为了实现对有特定 $k$ 维结构熵的给定图的简化，本文在Algorithm 1中提出了一种计算具有最小结构熵的 $k$ 维编码树的贪心算法.

特别，我们首先从初始编码树构建一个full-height二进制编码树。在这个阶段，迭代合并两个非根节点，这样可以在每一步最小化结构熵。加下来，为了构成图 $G$ 的 $k$ 维编码树 $T$ ，不断在 $T$ 中删除一条边，最小化每一步结构熵的恢复。最后可以得到一个图 $G$ 的有特定高度 $k$ 的编码树， $T=(V_T,E_T)$ ， $V_T=(V_T^0,\dots,V_T^k)$ 以及 $V_t^0=V$

$k$ 维编码树的时间复杂度是 $O(h_{max}(m\log{n}+n))$ ，其中 $h_{max}$ 是编码树 $T$ full-height 二进制编码树生成过程中的最大高度。因为最小化结构熵，倾向于建立平衡编码树， $h_{max}$ 通常是 $O(\log{n})$ 阶。进一步来说，图中边的数目通常大于节点数，Algorithm 1的运行时间与边的数目接近线性关系。

A Tree Kernel for Graph Classfication

为了对编码树进行分类，在构建WL子树核之后，本文提出了一种新的树核—— $WL-CT$ 核来度量编码之间的相似性。这两个内核之间的区别是标签的传播方案，其中我们提出了一个分层报告模式，基于编码树的层次结构将标签从子节点传播到它们的父节点。最后，树核采用整个编码树的节点标签数量来作为原始图的特征向量。

层次报告：该方案的关键是通过将子节点上的标签聚合和分类来给非叶子节点分配标签，然后将这些分类的标签集压缩为新的短的标签。标签从叶节点迭代传播到根节点，这意味着该方案的迭代时间由编码树的高度决定，避免了曲线WL子树核的收敛问题。

image.png

Definitoin 1 ： $T_1$ 和 $T_2$ 是任意两个有相同高度 $k$ 的编码树。存在一组字母 $\Sigma _i∈\Sigma$ ，它们是 $T_1$ 和 $T_2$ 第 $i$ 层( $i<k$ )层的节点标签(也就是高度为 $i$ 的节点被分配了具有层次报告的标签)。 $\Sigma _0$ 是 $T_1$ 和 $T_2$ 的叶子节点标签集合。假设任意两个 $\Sigma ^i$ 不相交，每个 $\Sigma ^i= \{b^i_1,\dots,b^i_{\vert \Sigma ^i\vert}\}$ 不失一般性下排序，定义一个函数 $c^i:\{T_1,T_2\}\times \Sigma ^i \to \mathbb{B}$ ， $c^i(T_1,b_j^i)$ 是字母 $b_j^i$ 在编码树 $T_1$ 中的数量。

在根节点分配标签后，高度为 $k$ 的树( $T_1$ 和 $T_2$ )上的树核被定义为：
$WL-CT(T_1,T_2)=<\phi_{CT}(T_1),\phi_{CT}(T_2)> \qquad (3)$

其中，
$\begin{aligned} \phi_{CT}(T_1)=&(c^0(T_1,b^0_1),\dots,c^0(T_1,b^0_{\vert \Sigma^0\vert}),\dots,\\ &c^k(T_1,b_1^k),\dots,c^k(T_1,b^k_{\vert \Sigma^k\vert})) \end{aligned}$
$\begin{aligned} \phi_{CT}(T_2)=&(c^0(T_2,b^0_1),\dots,c^0(T_2,b^0_{\vert \Sigma^0\vert}),\dots,\\ &c^k(T_2,b_1^k),\dots,c^k(T_2,b^k_{\vert \Sigma^k\vert})) \end{aligned}$

根据 $WL$ 子树核中的标签计数过程，本文的树核也设计用来计算两个编码树中的公共标签的数量。

Theorem 1. 具有相同高度 $k$ 的两个编码树 $T_1$ 和 $T_2$ 的 $WL-CT$ 核可以在时间 $O(n)$ 计算出来，这比在 $m$ 条边上进行 $h$ 次迭代的 $WL$ 子树核( $O(hm)$ )要简单得多，据我们所知，这是时间复杂度最低的图分类方法。

Proof.给定一个图 $G$ ，对于 $h$ 次迭代， $WL$ 子树核的运行时为 $O(hm)$ ，因为在每个 $WL$ 测试迭代中，一个图的多元集合中都有 $O(m)$ 的元素。相应，给定图 $G$ 的编码树 $T$ ， $WL-CT$ 核的时间复杂度是编码树多元集合中的元素总数，因为类似的标签传播模式。此外，多元集合中元素的数量由标签传播发生的次数决定，即边数 $|E|=m$ 。因此， $WL-CT$ 核的时间复杂度有 $T$ 的边数决定。如Algorithm 1所示，边最多的编码树是full-height二进制编码树 $T_B$ ，i.e.， $O(T)\le O(T_B)$ ，full-height二进制编码树的复杂度可以计算为：
$\begin{aligned} O(T_B) &=O(\vert E_{T_B} \vert)\\ &=O(\vert V_{T_B}\vert -1)\\ &=O(\vert V^0_{T_B}\vert + \vert V^1_{T_B}\vert , \dots , \vert V^{h_{max}}_{T_B}\vert -1)\\ &<O(2\vert V^0_{T_B}\vert)\\ &=O(2\vert V\vert)\\ &=O(n). \end{aligned}$

A Convolutional Network for Graph Classification

基于树核开发了一种新的图卷积网络 $HRN$ ，它将层次报告推广到图像分类上，更新非叶节点的隐藏特征。HRN利用编码树和叶节点特征 $X_v$ 的层次结构来学习整个编码树 $r_T$ 的表示向量。 $HRN$ 遵循层次报告机制，其中一个非叶节点的表示向量通过聚合其子节点的隐藏特征来更新。在形式上， $HRN$ 的第 $i$ 层是
$r_v^i=MLP^i(\sum_{u\in C(v)}{r^{(i-1)}_u})，\qquad (4)$

$r_v^i$ 是编码树上高度为 $i$ 的节点 $v$ 的特征向量

$r_v^0=x_v$

$C(v)$ 是 $v$ 的孩子节点的集合

如公式4所示，我们使用求和以及多层感知器( $MLPs$ )在HRN中执行分层报告。求和聚合器在理论上被证明在多元集合上的单射，并且比平均、最大值聚合器更强大。由于通用近似定理， $MLPs$ 能够表示函数的组成。

对于图的分类，可以朴素地使用根节点向量 $r^k_v$ 作为整个编码树 $r_T$ 的表示。但是在早期迭代的特征中可以得到更好的结果。为了包含所有的层次信息，我们使用了模型的每个高度/迭代中的隐藏特征。这通过一个类似于GIN的架构来实现，用跨HRN结构的所有高度/层上的层向量表示来建模整个编码树：
$r_T = CONCAT(LAYERPOOL(\{r^i_v \vert v \in V^i_T\}) \vert i=0,1,\dots ,k),\qquad (5)$

$r_v^i$ 是在编码树 $T$ 上高度为 $i$ 的节点 $v$ 的特征向量

$k$ 是 $T$ 的高度

在 $HRN$ 中,公式5的 $LAYERPOOL$ 可以用在同一轮迭代中对所有节点向量求和或者求平均替代。

Experiments

Darasets.:

三个社交网络数据集 (IMDB-BINARY,IMDB-MULTI, and COLLAB)

两个生物信息学数据集(MUTAG和PTC)

不同点在于，生物信息学数据集有节点的分类标签。

因此，树核的初始节点标签组织如下：将节点度作为社交网络的节点标签，节点度和节点分类标签则根据每个生物信息学数据集。

相应地，HRN的初始输入节点特征在社交网络被设置为节点度的one-hot编码，在生物信息学图为和度和分类标签的one-hot编码的组合为。Table1总结了5个数据集的特征。

image.png

Configurations.
采用十折交叉验证，用平均精度

对于树核的配置，采用 $C-SVM$ 作为分类器，并调整了SVM的超参数C和编码树的高度 $∈[2,3,4,5]$ 。

使用Scikit-learn的SVM实现分类程序

$IMDB-BINARY$ and $IMDB-MULTI$ 超参数 $\gamma$ 为auto

$COLLAB$ ， $MUTAG$ and $PTC$ 中超参数 $\gamma$ 为scale

其他超参数取默认值

对于 $HRN$ 的配置， $HRN$ 迭代的次数与相关的编码树的高度一致，这也是 $∈[2,3,4,5]$ 。所有的 $MLPs$ 有2层。每一层，采用批归一化以防止过拟合。利用Adam优化器，初始学习率设置为0.01，学习率每50轮衰减一半。HRN的其他超参数调优包括隐藏维度数 $∈\{16,32,64\}$ ，minibatch大小 $∈\{32,128\}$ ，以及 $LAYERPOOL$ 后的dropout ratio $∈\{0,0.5\}$ 。每个数据集的epoch数量都是根据交叉验证结果中的最佳精度来选择的。对HRN应用相同的层级池化方法(等式5)；具体来说，对生物信息学数据集采取求和池化，并对社会数据集进行平均池化，确保能与 $GIN-0$ 进行直接比较。

Baselines.现在研究专注于注意力和图池化，在本文中，采用了没有注意机制或精心设计的图池化的模型来进行公平的比较。
（1）kernel-based methods, i.e., the WL subtree kernel and AWE [Ivanov and Burnaev, 2018];

（2）deep learning methods, i.e., DCNN , PATCHY-SAN ,DGCNN, GIN-0 and LP-GNN.

基线的精度都是从论文中取得，其中WL从[Xu et al., 2019]获得，其他从原论文得到。

Variants of HRN with different LAYERPOOL approaches.
HRN变式
不同的图池化方法和以根节点特征代表全树

image.png

The guidance of structural entropy.
实验不具有结构熵最小化的编码树，用随机编码树，比如高度维为2的随机平衡二叉树（RBBT）,对于数据集中的每个图，生成相应的RBBT，图节点为叶子节点，并使用WL-CT核和HRN来执行图的分类(即WL-CT-RBBT和HRN-RBBT)

image.png

The effectiveness of essential structure within graphs.
更深入地研究了图中基本结构的有效性。使用了那些经典的图核，Core Framework kernel, Neighborhood Hash kernel, ODD-STh kernel, Propagation kernel, Pyramid Match kernel, and Shortest Path kernel 进行图分类，由于编码树中的非叶节点是没有初始标签的虚拟节点；因此，我们将编码树中的所有非叶节点分配标签0。

image.png

Computational efficiency.

image.png

最后编辑于：2022.09.07 17:21:01

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

论文笔记：A Simple yet Effective Method for Graph Classification

论文笔记：A Simple yet Effective Method for Graph Classification

A Simple yet Effective Method for Graph Classification

Introduction

Related Work

Methodology

Graph Simplification via Structural Entropy Minimization

A Tree Kernel for Graph Classfication

A Convolutional Network for Graph Classification

Experiments

相关阅读更多精彩内容

友情链接更多精彩内容