论文链接：https://dl.acm.org/doi/10.1145/3178876.3186106

代码链接：https://github.com/zyz282994112/GraphInception

来源：WWW 2018

本文要解决的是HIN中的集体分类(collective classfication)问题：一组实例中的标签是相关的，应该对这个集体进行分类推断。
传统的集体分类方法主要是利用简单的关系特征(如: 计数，相邻节点上存在的聚合器)。然而真实世界的应用包含实例间复杂的依赖关系，这些关系是隐含在网络中的。
为了获得这些依赖关系，不能只得到简单的关系特征，还需要从实例中挖掘到更深层次的依赖关系。

---

---

1 摘要

本文研究HIN中的深度集体分类问题(deep collective classification)，其中涉及到不同实例之间的自相关关系。

与传统的，由网络中的连接给出的自相关不同，复杂的自相关是隐藏在HIN中的，需要按照现有的层次顺序，从现存的连接中推断出来。

作者提出深度的卷积集体分类方法GraphInception，学习到HIN中的深层次的关系特征。该方法可自动生成具有不同复杂程度的关系特征层次。

在4个真实数据集上进行了集体分类(collective classification)实验，证明了模型效果。

2 介绍

集体分类(collective classfication)指的是：使用一组内部相关的实例中的标签自相关信息，然后统一预测它们的类别标签。

2.1 已有的方法

先前的集体分类方法过度依赖于专家设计的关系特征。一方面，传统的关系特征通常定义为节点邻居的简单聚合。另一方面，近期的基于深度学习的方法主要关注于上下文特征(如图像中的视觉特征)。

它们都没有抽取出和集体分类有关的深层次关系特征，以捕获到实例中复杂的自相关信息。

2.2 挑战

在许多关系型数据中，不同实例之间的标签可能是相关的。例如，在引文网络中，一个作者写的多篇文章有相似主题的可能性较大。

对于这种关系型数据，有效的模型应该可以捕获不同实例之间的依赖关系，然后实现整体分类。

（1）深层关系特征

HIN涉及不同类型的自相关信息构成的有层次的结构（从简单到复杂）。

复杂的关系不是由网络中的显式连接给出的，而是通过有层次结构的关系特征给出的。

例如下图所示，作者之间有co-author relations(简单关系)、advisor-advisee relations(隐藏关系)、share-adviser relations(复杂关系)。

图1

图1展示了一个深层关系学习任务：在引文网络中预测一个作者的研究领域(label)。不同的作者不仅通过共同作者的关系显式连接在一起，还通过隐层的关系相连，比如：adviser-advisee，share-advisor，colleague。图1中的虚线就表示了作者之间的隐式连接。

复杂关系，例如share-advisor，不能直接从浅层的关系特征(例如 co-author)中得出。但是可以由浅入深，从有层次结构的深层关系特征中一步步推断得出。如下图所示，从简单关系(co-authors)，中层关系(advisor-advisee)到复杂关系(share-advisor)。

图2

例如，为了推断出advisor-advisee关系，可以找到两个有相似邻居的作者节点(这些邻居很有可能是他们的adviser或者研究组里的其他学生)。

HIN中的实例之间存在复杂模糊的关系，所以需要一个深层的关系学习模型，以从这些实例中抽取出有结构层次的深度依赖关系。

（2）关系特征中的混合复杂性

如图1所示，实例中通常混有简单的和复杂的依赖关系，而且都和集体分类任务有关。

在这种网络中，若使用简单的关系模型，则只能捕获到简单的关系，在复杂关系的处理上欠拟合；若使用传统的深度学习模型，则只能捕获到复杂的关系，在简单关系的处理上过拟合。

所以，理想的模型应具有自动平衡模型复杂度的能力。

（3）异质的依赖关系

HIN中节点类别和边类别的多样性。不同类型的节点和边具有不同的属性，难以直接利用深度学习模型。

例如，GCN假定网络中的所有节点共享同样的卷积核，这在HIN中是说不通的。

也有一些研究在HIN上的集体分类的工作，但是大多数都是用的浅层模型，忽视了网络中的深层关系特征。

2.3 作者提出

本文研究了HIN中的深层集体分类问题，涉及到实例之间的不同类型自相关的层次结构。

为了解决上述问题，作者提出GraphInception模型用于HIN中的集体分类。图3对比了本文模型与其他传统方法的不同。

考虑到关系特征复杂程度的多样性(简单的，复杂的)，为了更有效地学习到关系特征，受inception module(一个高效深层的CNN模型)启发，作者提出graph inception module来平衡不同复杂度的关系特征。

3 问题定义

一些符号定义如下：

HIN的定义不再赘述。

3.1 HIN中的集体分类

本文只在一种类型的节点上研究集体分类问题，而不是在HIN中的所有节点上进行集体分类。因为不同类型节点的标签空间是不同的，假设所有类型的节点共享同一套标签是不合理的。

而且对于特定的推断任务，我们只关心在特定类型节点上的推断结果。

假设HIN $G$G中的类型为$V_1$V1​的节点是需要推断的目标节点集合，$V_1$V1​中有$n$n个节点，每个节点$v_{1i}\in V_1$v1i​∈V1​都有一个特征向量$x_i\in R^d$xi​∈Rd。标签变量$Y_i\in {\{1,...,C\}}$Yi​∈{1,...,C}表示接地那$v_{1i}$v1i​的标签。

接着，$V_1$V1​中的实例被分为训练集$L$L和测试集$U$U，$Y_L$YL​代表训练集中的节点标签集合，$Y_U$YU​表示测试集中的节点标签集合。

令，$N_i(N_i\subseteq V_1)$Ni​(Ni​⊆V1​)表示和$v_{1i}$v1i​有关的节点集合，$Y_{N_i}={\{Y_i|v_{1i}\in N_i\}}$YNi​​={Yi​∣v1i​∈Ni​} 表示标签集合。则，HIN中的集体分类任务就是估计如下的概率：

学习和推断上述概率是很难的，需要学习到HIN中节点的复杂关系特征。下一节将提出模型解决这个问题。

4 基于图卷积的深度关系特征学习

为了学习到HIN中的深层关系特征，提出了基于图卷积的关系特征学习模型。迷行由两部分组成（1）多通道网络转换(multichannel
network translation)：将HIN转换成了多通道网络，从而在上面进行卷积操作；（2）基于图卷积的关系特征学习：使用图卷积，从多通道网络中学习到深层的关系特征。

4.1 多通道网络转换

HIN中节点类型多样，这给卷积操作带来了难度。作者提出多通道网络，每一个通道都是一个同质图(只有一种类型的节点)，边是从HIN中抽取的，有着不同的语义信息。

定义二元关系$R$R，$R(v_{ip},v_{jq})$R(vip​,vjq​)表示节点$v_{ip}, v_{jq}$vip​,vjq​是否通过$R$R类型的边相连。

每个元路径都定义了节点之间的一种复合关系，可被用作多通道网络(multi-channel network)中与特定通道相连的边类型。为了有效学习到实例之间的依赖关系，作者将HIN转换为多通道网络，网络中的每个通道都通过一个特定类型的元路径相连。

给定元路径的集合$S={\{P_1,...,P_{|S|}\}}$S={P1​,...,P∣S∣​}，转换后的多通道网络$G^{'}$G′定义如下：

其中$E_{1l}\subseteq V_1\times V_1$E1l​⊆V1​×V1​表示遵循元路径$P_l$Pl​模式的连边，且两端节点都属于$V_1$V1​集合。

本文采用宽度优先搜索(BFS)的方法构建元路径。

4.2 基于图卷积的关系特征学习

基于图卷积从同质图(HON)中学习到关系特征，并将其用于HIN。

传统的GCN主要关注于上下文的特征学习。传统的GCN和本文模型对比如下：

接着解释一下同质图$G_{homo}$Ghomo​上的图卷积：

卷积被定义为在傅里叶基对角化的线性算子。用图的转换概率矩阵$P$P的特征向量作为傅里叶基。然后，在$G_{homo}$Ghomo​上的卷积就被定义成信号$X\in R^{n\times C}$X∈Rn×C和$P$P上的滤波器$g_{\theta}$gθ​在傅里叶域上的乘积：

其中，$U$U是$P$P的特征向量矩阵，$\Lambda$Λ是$P$P特征值的对角阵，$g_{\theta}(\Lambda)$gθ​(Λ)是傅里叶系数向量，$U^{\top}X$U⊤X是$X$X的图傅里叶转换。注意，这里的$U,\Lambda$U,Λ都是非常复杂的矩阵，因为$P$P是非对称矩阵。本文的模型与$U$U是否是复杂矩阵无关。

为了选择出给定节点的局部邻居，定义$g_{\theta}$gθ​为多项式参数过滤器：

将（4）式代入（3）式可得：

上式是转移概率矩阵的K阶多项式，表示的是K阶的邻居信息，也就是说聚合的信息最远来自和目标节点距离为K步的节点。

接下来将（5）式扩展到HIN。

首先介绍如何将HIN $G$G转换到多通道网络$G^{''}$G′′，其中每个通道都表示了连接$V_1$V1​中节点的特定关系。

然后在每个通道上进行卷积，学习到HIN中的关系特征：

其中$P_l(l=1,...,|S|)$Pl​(l=1,...,∣S∣)表示$G^{'}_l$Gl′​的转移概率矩阵。在不同的通道使用不同的卷积核，最终将这些卷积得到的结果拼接起来。因为节点在每个通道都有不同的邻居，在所有通道都用一个卷积核显然是不合适的。

接着，将（6）式一般化到F个卷积核，就有了如下的形式：

其中，$\Theta_{lk}\in R^{C\times F} (l=1,...,|S|)$Θlk​∈RC×F(l=1,...,∣S∣)是滤波器参数的矩阵。$r(x)=(r(x_1),...,r(x_n)), r(x_i)=max(0,x_i)$r(x)=(r(x1​),...,r(xn​)),r(xi​)=max(0,xi​)，是Relu函数。$H$H的第$i$i行向量表示学习得到的节点$v_{1i}$v1i​的关系特征。

传统的图卷积模型和本文的模型区别如下：

1. 传统的模型解决的是图分类问题，本文模型解决的是集体分类问题；
2. 大多数GCN模型都是学习上下文特征向量的，使用拉普拉斯矩阵$L$L的特征向量作为傅里叶基。本文的模型是学习关系特征的，使用概率转移矩阵$P$P的特征向量作为傅里叶基。
3. 本文的模型关注关系特征的学习，所以不需要节点自身的属性信息，也就是在（5）式中不需要考虑$k=0$k=0的情况。
4. 本文卷积模型输出的是关系特征，大多数传统模型输出的是上下文特征。
5. 本文的模型可处理HIN，传统的图卷积模型不能做到。

5 基于深度关系特征学习的Graph Inception模型

为了平衡关系特征的复杂程度，提出graph inception model，自动生成从简单到复杂的关系特征的层次结构。

传统的inception模型只能处理欧式的网格数据，例如图像数据，不能处理图结构的数据。所以提出graph inception module，以更有效地学习网络中的关系特征。

如图3(a)所示，graph inception module由不同规格的卷积核组成，并且通过堆叠多层，生成了从简单到复杂的关系特征的层次结构。图3(b)是一个小例子。

例如，在每层的每个通道使用两个卷积核，并分别将卷积核大小设为1和2。Graph inception module的第$t$t层定义如下：

为了减少参数，将$C^t_{l_2}$Cl2​t​替换为：

我们可以通过堆叠多层抽取出复杂的关系特征，并通过调整层数控制学习到的关系特征的复杂程度。

和（7）式相比，基于graph inception的模型有以下三个优势：

1. 当$K$K的值很大时，可以显著减少存储空间。（式（7）需要存储$K$K个矩阵，式（8）需要存储$P$P和$P^2$P2）
2. 当网络很深的时候，需要的参数比（7）式少。
3. 可提高模型抽取关系特征的能力。

6 提出的方法

在学习到所有节点的关系特征后，使用关系特征$H^T_i$HiT​和局部特征$x_i$xi​，通过softmax层，预测节点的标签$Y_i$Yi​：

其中$T$T表示（8）式中的最顶层。$vec(·)$vec(⋅)是将输入矩阵缩放为向量的函数。

GraphInception算法流程如下所示：

7 实验

数据集：DBLP, IMDB, SLAP(生物信息学数据集), ACM会议

实验任务：多类分类，多标签分类

对比方法：

实验结果：（详见论文）

8 总结

本文为了学习HIN中的深层关系特征，解决集体分类问题，提出基于图卷积的模型。

还进一步提出了GraphInception模型，混合实例中的复杂和简单的依赖关系。

实验证明了有效性。

---

（个人感觉这篇文章的结构和排版略微有点乱乱的）