论文链接：https://arxiv.org/abs/1905.05659

来源：IJCAI 2019

---

---

1 摘要

现有的异质网络嵌入方法(HNE)通常是无监督的，为了最大化利用HNEs中有价值的监督信息，作者提出ActiveHNE模型。

实验证明了ActiveHNE的有效性，以及在降低query成本方面的优势。

2 介绍

2.1 挑战

（1）异质性带来的普遍问题：如何处理不同类型的节点。

（2）大多数HNE方法都是无监督的，而适当地利用监督信息，可以提高HNE的效果。

（3）然而，标签的获取是很困难的，因为需要人为参与。

主动学习(active learning, AL)可以解决挑战（3），选择出最有价值的节点进行标注。然而HIN中的节点不是独立的单一的分布(non-i.i.d.)，是由边连接起来的，AL应该考虑到数据的依赖性，而且对不同类型的节点也应区别考虑。

2.2 作者提出

提出ActiveHNE模型解决上述挑战。

模型由两部分组成：DHNE(Discriminative Heterogeneous Network Embedding)和AQHN(Active Query in Heterogeneous
Networks )。

（1）DHNE

DHNE中引入了基于GCN的半监督HNE方法。先将HIN分解成同质的bipartite networks。在每层卷积，分别学习节点在每个network的语义信息，然后将它们拼接起来作为节点输出向量。

（2）AQHN

除了引入网络的中心性外，还引入了两种主动选择策略，即HIN在不确定性和代表性方面的卷积信息熵和卷积信息密度。

这些策略使用局部卷积实现了对HIN的异质性以及节点之间的依赖关系的利用，过滤器的参数是由节点重要程度决定的(由节点的度和邻居节点的类型数衡量)。

然后使用多臂老虎机机制，递归地向专家抛出query(unlabel data)，这些节点是最值得被标注的。

ActiveHNE旨在通过为DHNE输入AQHN得到的最优价值的监督信息，提升HNE的效果。

2.3 贡献

（1）形式化了主动的异质网络嵌入学习问题，目的是通过寻找最值得标注的节点，使用这些标注节点，从而提高HNE的效果。

（2）考虑到了网络的异质性和节点间的依赖关系，使用局部卷积和多臂老虎机机制解决上述问题。

3 The ActiveHNE Framework

3.1 Discriminative Heterogeneous Network Embedding (DHNE)

先将HIN分解成同质网和bipartite networks(只由两种类型的节点组成)。然后在每个卷积层，分别卷积每个network中节点的深层语义信息，然后将它们拼接起来作为节点输出向量。

${\{G_t|t=1,2,...,T\}}${Gt​∣t=1,2,...,T}表示分解出来的同质网络，${\{A_t|t=1,2,...,T\}}${At​∣t=1,2,...,T}表示${\{G_t\}}${Gt​}相对应的邻接矩阵。

频谱图卷积定理在归一化图的基础上定义了傅里叶域中的卷积
拉普拉斯算子：$L_t=I_t-D^{-\frac{1}{2}}_t A_t D^{-\frac{1}{2}}_t=D^{-\frac{1}{2}}_t(D_t-A_t)D^{-\frac{1}{2}}_t$Lt​=It​−Dt−21​​At​Dt−21​​=Dt−21​​(Dt​−At​)Dt−21​​。其中$I_t$It​是单位矩阵，$D_t=diag(\sum_i A_t(i,j))$Dt​=diag(∑i​At​(i,j))表示度矩阵。

由于节点间的连接可能是有向的，所以不对称的矩阵比对称矩阵$L_t$Lt​更适合傅里叶域。定义非对称的转移概率矩阵为：$P_t=D^{-1}_tA_t$Pt​=Dt−1​At​。

本文分别在分解得到的每个network上使用转移概率矩阵$P_t$Pt​作为傅里叶偏置。特别地。令$P_t=\Phi_t\Lambda_t\Phi^{-1}_t$Pt​=Φt​Λt​Φt−1​，其中$\Lambda_t$Λt​和$\Phi_t$Φt​分别是$P_t$Pt​的特征向量矩阵和特征值的对角矩阵。

卷积定义如下：

其中$X_t\in R^{N_t\times D}$Xt​∈RNt​×D是网络$G_t$Gt​的输入，$g_{\theta_t}$gθt​​是过滤器，$\Phi^{-1}_tX_t$Φt−1​Xt​是$X_t$Xt​的傅里叶变换。

为了对目标节点的局部邻域进行卷积，将$g_{\theta_t}(\Lambda_t)$gθt​​(Λt​)定义为K阶的多项式滤波器：

其中$\theta_t\in R^K$θt​∈RK是多项式系数组成的向量。（2）式代入（1）式可得下式：

从上式可知，在图$G_t$Gt​上的卷积，只依赖和目标节点最远距离是K的那些节点。也就是说，卷积操作之后的输出信号，由网络上局部谱滤波器的K阶近似定义。其中滤波器参数$\theta_{tk}$θtk​可在整个网络$G_t$Gt​上共享。

进一步将（3）式一般化成$D\times d$D×d的滤波器，将原始特征从D维转化为d维。因此，$G_t$Gt​上的卷积操作形式化为：

$\Theta_t\in R^{D\times d}$Θt​∈RD×d表示滤波器参数（要训练的权重矩阵），$H_t\in R^{N_t\times d}$Ht​∈RNt​×d表示卷积的输出信号。$\sigma(\cdot)$σ(⋅)是$ReLU(\cdot)$ReLU(⋅)**函数。

拼接节点在每个network中得到的向量表示，作为节点的最终输出信号。若节点不是某一network中的元素，则使用零向量代表节点在该network中的输出信号。使用$Z_t$Zt​定义拼接后的向量表示，在$G_t$Gt​上的第l层卷积操作定义如下：

在经过$\beta$β层的卷积和拼接操作后，得到所有节点的最终输出向量$E=Z^\beta \in R^{N\times Td^{(\beta)}}$E=Zβ∈RN×Td(β)（T表示networks的数量）。为了得到有区分度的embeddings，添加全连接层来预测节点的标签：

其中，$\Theta^{pre}\in R^{Td^{(\beta)}\times C}$Θpre∈RTd(β)×C是隐层到输出层的权重矩阵。$F\in R^{N\times C}$F∈RN×C，$F_{ic}$Fic​是第i个节点属于第c类的概率。最后一层的**函数$\sigma(\cdot)$σ(⋅)是softmax函数。

最终，有监督的基于交叉熵的损失函数定义如下：

若第i个节点属于第c类，则$Y_{ic}=1$Yic​=1，否则为0。（6）式和（7）式定义了半监督的node embedding模型。

3.2 Active Query in Heterogeneous Networks (AQHN)

DHNE是半监督的HNE，需要标签信息。为了训练出更有效的DHNE模型，提出了主动学习query(选择出unlabel data)的模型AQHN。AQHN的目的就是通过主动学习，筛选出最有价值的节点，进而让专家去标注这些节点用于DHNE模型中的监督。

**不确定性(uncertainty)和代表性(representativeness)**是AL中选择样本常使用的方法。

不确定性是选择在当前分类模型中，最不确定的样本；代表性是选择无标签数据中最能代表整体特征的样本。

接下来介绍基于不确定性和代表性，针对HIN的3个主动选择策略：网络中心性(Network Centrality)、卷积信息熵(Convolutional Information Entropy)和卷积信息密度(Convolutional Information Entropy)。然后，利用多臂老虎机机制，提出一种新方法将这些策略结合起来，自适应地、迭代地选择最有价值的一批节点送去标注。

3.2.1 选择策略

3.2.1.1 网络中心性(NC)

NC是衡量节点代表性的有效方法。本文使用度中心性(degree centrality)：$\phi_{nc}(v_i)=|N_i|$ϕnc​(vi​)=∣Ni​∣，来评估节点的中心性。其中，$|N_i|$∣Ni​∣表示节点$v_i$vi​的邻居。

受谱图卷积将卷积信号定义为相邻信号的线性加权和的思想启发，提出了两种新的基于相邻信号卷积的主动选择节点策略。

首先定义卷积参数，然后定义两种选择策略。

令$w_i=tanh(\frac{n_i}{N}+\frac{m_i}{V_T})\in [0,1)$wi​=tanh(Nni​​+VT​mi​​)∈[0,1)衡量节点$v_i$vi​的重要性。$n_i$ni​表示节点的邻居数，$m_i$mi​表示节点邻居的类型数。$N, V_T$N,VT​分别表示网络中的节点数和节点类型数。$n_i, m_i$ni​,mi​值越大，说明节点$v_i$vi​蕴含的信息越复杂，$v_i$vi​就对它的邻居节点越重要。

后面的操作中，使用$w_i$wi​作为对邻居进行卷积的权重参数。

3.1.1.2 卷积信息熵(CIE)

信息熵(IE)广泛用于不确定性的衡量，本文使用如下的CIE衡量节点$v_i$vi​的不确定性：

3.1.1.3 卷积信息密度(CID)

节点的代表性对于衡量节点价值也很重要。使用k-means聚合节点向量，从而计算节点的信息密度(ID)。聚合的簇数是标签类别数。节点$v_i$vi​的CID值计算如下：

其中$dis(\cdot)$dis(⋅)是距离度量函数(i.e., 欧式距离)，$\psi(v_i)$ψ(vi​)是节点$v_i$vi​所属簇的中心向量，$E_j$Ej​是第j个节点的向量表示。

CIE和CID都是基于节点自身和其邻居节点，衡量节点重要程度的。IE和ID只使用了节点自身的信息。由于网络中节点之间存在许多连边，所以使用CIE和CID更合适。

3.2.2 主动节点选择的多臂老虎机(Multi-Armed Bandit for Active Node Selection)

使用上述三个策略选取最优价值的节点。

首先根据$\phi_{nc}, \phi_{cie}, \phi_{cid}$ϕnc​,ϕcie​,ϕcid​选出值最高的b个节点，作为每次的初始候选节点。

为每个策略分配不同的权重，加权求和作为节点重要性的最终衡量标准。主动节点选择问题就被转换为了评估每个策略的重要性问题。

但每种策略的重要性都是时效性的，因此很难具体说明。所以提出一个新模型，基于多臂老虎机机制(MAB)，自适应地学习动态的权重参数。

MAB每次迭代只能play one arm，本文使用的是组合的多臂老虎机(CMAB)，即每次迭代可以play multiple arms。

基于CMAB的思想，将每个选择策略看成一个arm，通过评估对应arm的期望回报，估计每个策略的重要性。定义$C^\lambda_r$Crλ​为arm $\lambda$λ在第r次迭代的初始值，$Q_r$Qr​是迭代中实际query的节点集合。arm $\lambda$λ的实际回报值定义如下：

其中$L_r$Lr​是在第r次迭代中可用的已标注节点集合；$Q^\lambda_r=C^\lambda_r \cap Q_r$Qrλ​=Crλ​∩Qr​是第r次迭代中，被arm $\lambda$λ控制的query节点集合。$f_{L_r}$fLr​​是在$L_r$Lr​上训练的分类器，$\psi(f_{L_r})$ψ(fLr​​)是$f_{L_r}$fLr​​的分类结果。

然而当前迭代的$\mu_r(\lambda)$μr​(λ)值是不可计算的，因为$Q^\lambda_r$Qrλ​的真实值是未知的。通常使用经验回报来估计arms的预期回报，但是在每次迭代为每个arm计算经验$\mu_r(\lambda)$μr​(λ)值是非常耗时的。所以，使用arm带来的节点局部embedding变化，来估计每个arm的期望回报值。

首先定义在第r次迭代中，由arm $\lambda$λ引起的局部embedding变化如下：

其中$E^r_j$Ejr​是第r次迭代中节点$v_j$vj​的embedding，$N(v_i)$N(vi​)是节点$v_i$vi​的邻居。如上式所示，第r次迭代中arm $\lambda$λ的经验回报等于由arm $\lambda$λ控制的节点和其邻居的embedding变化。

AL策略的目的就是选择那些如果给定了标签值，则会对embeddings最大程度带来改变的节点。如果改变的不多，说明标签没有提供足够多的新信息。

为了更公平地比较避免偏差，用$\hat{\mu}_r(\lambda)=\frac{\Delta_r(\lambda)}{\Delta_r(\bigcup^{\Lambda}_{\lambda=1}\lambda)}$μ^​r​(λ)=Δr​(⋃λ=1Λ​λ)Δr​(λ)​来估计第r次迭代中arm $\lambda$λ的经验回报。其中，$\Delta_r(\bigcup^{\Lambda}_{\lambda=1}\lambda)$Δr​(⋃λ=1Λ​λ)表示所有arms带来的局部embedding的改变。另外，在第r次迭代中，$\Delta_r(\bigcup^{\Lambda}_{\lambda=1}\lambda) \leq \sum^{\Lambda}_{\lambda} \Delta_r(\lambda)$Δr​(⋃λ=1Λ​λ)≤∑λΛ​Δr​(λ)，因为不同的$Q^{\lambda}_r$Qrλ​可能有交集。

由于每个选择策略的重要程度是随时间变化的，使用前两次的经验回报平均值，作为对当前期望回报的估计：

然后作者又把$\bar{\mu}_r(\lambda)$μˉ​r​(λ)调整为了$\tilde{\mu}_r(\lambda)$μ~​r​(λ)（具体原因见论文）:

为了避免选择有争议的节点，使用weighted Borda count估计第r次迭代中un-queried nodes $v_i\in \bigcup^{\Lambda}_{\lambda=1} C^{\lambda}_r$vi​∈⋃λ=1Λ​Crλ​的期望回报：

最终从$\bigcup^{\Lambda}_{\lambda=1} C^{\lambda}_r$⋃λ=1Λ​Crλ​中选出top b个$\tilde(\mu)^*_r(v_i)$(~​μ)r∗​(vi​)最大的节点，作为第r次迭代中的query batch $Q_r$Qr​。

4 实验

数据集：DBLP、Cora、MovieLens

实验任务：节点分类任务，使用Accuracy衡量。

对比方法：

• GCN
• metapath2vec
• AGE和ANRMAB：active network embedding methods，没有考虑节点间依赖关系以及网络的异质性。
• DHNE：ActiveHNE的一种变体，它在初始AL设置中随机选择要query的节点。

实验结果：

（1）对比不同方法，在三个数据集上进行节点分类任务，准确率对比图如下：

（2）对ActiveHNE模型进行多种变形，以证明每个选择策略的有效性：

5 总结

本文研究了，如何通过获取最优的节点标签，实现主动判别异质网络嵌入。

提出ActiveHNE模型，将异质图分解成了多个同质图和bipartite sub-networks(二部图)，然后在这些networks上使用GCN。

提出了三种基于卷积的query策略，并将其结合，选择出最有价值的节点作为query，供专家打标签，然后反馈给下一轮判别性网络嵌入。

---

本文的目的是从异质图中选取出最有价值的节点，然后给这些节点打标签，以用于半监督的节点嵌入学习。利用了这些有价值的信息，可以更好地学习到节点的表示。

但是节点的数量很多，如何选取有价值的节点就成了问题。本文采用了网络中心性(IC)、卷积信息熵(CIE)、卷积密度熵(CIE)作为衡量节点重要性的标准。

如何合理结合这三个策略？

接着就结合了强化学习中的组合的多臂老虎机机制(CMAB)，自适应地学习动态的参数，为上述三个策略分配不同的权重。将每个选择策略看成一个arm，通过评估对应arm的期望回报，估计每个策略的重要性。

在节点分类任务中得到了很好的效果。