定义在图数据上的节点分类问题广泛存在于许多现实应用中^[1-3]，比如电信系统异常检测^[4]和文件类别判断^[5]. 该问题的难点在于深度挖掘节点间的关联关系以实现更准确的节点表征学习.

近年来，基于卷积的图神经网络方法（graph neural networks, GNNs）在节点分类任务上取得了突出的效果^[6]，这些方法大多是利用图结构（邻接矩阵中显式存在的边）进行特征聚合. 不过，给定的图结构通常难以囊括节点间的所有关联关系，因此这类方法会导致部分节点无法通过邻域聚合获取足够多的特征信息. 以引文图为例，在该图中，节点表示论文，边表示2节点之间的引用关系. 显然，一篇论文最有可能引用与它主题相同的文献，这就解释了为什么现有GNNs利用显式的边连接关系能够取得突出成果. 然而，一篇文章不可能引用与它主题相同的所有论文，并且一些具有相同主题的文章在引用图中可能相隔较远. 因此，为了从其他节点聚合得到更丰富的特征信息，必须挖掘节点之间的隐式边.

受到上述思路的启发，为了实现了节点间隐藏连接关系的挖掘并从隐含连接关系中进行信息提取，本研究提出可微的相似度模型（differentiable similarity module, DSM）进行节点表征增强，使得所学到的节点表征在携带更多的节点类别信息的同时具有更高的鲁棒性和辨识性. 为了提高DSM的可用性与通用性，将DSM设计为可微分的形式，使其在与任意GNNs模型相结合后仍能进行端到端的训练。为了验证DSM的有效性，在多个开源数据集上进行实验.

根据图卷积操作的作用域，基于GNNs的节点分类方法可以分为2类：基于频域的GNNs方法^[7-9]和基于空间域的GNNs方法^[10-14].

基于频域的GNNs方法从图谱角度解决节点分类问题，此类方法的代表性工作主要有以下几种：1）对图的拉普拉斯变换进行特征分解^[15]；2）设计具有平滑系数的参数化频域滤波器^[16]；3）采用切比雪夫表达式近似频域滤波器^[4,17]；4）使用节点的一阶邻域滤波来简化计算^[9,18].

基于空间域的GNNs方法在空间域上定义图卷积运算，其主要难点是如何对具有不同邻接节点数的节点进行卷积运算. 目前学术界提出了许多解决方案：1）使得具有相同邻接节点数的节点共享相同的卷积核^[12]；2）为每个节点选择固定数量的邻接节点进行卷积^[10,13]；3）引入注意力机制直接基于具有不同邻接节点数量的邻域进行卷积^[11]. 与上述基于频域的方法相同，基于空间域的方法仅利用显式的边连接关系进行特征聚合，这将导致部分节点无法从其他节点聚合到足够的特征信息.

本研究所提出的可微分相似度模型DSM与上述2类方法不同，DSM基于节点表征的相似度，在学习节点表征时引入相似节点的特征信息，使得最终学到的节点表征包含更多的节点类别信息且具有更高的鲁棒性和辨识性. 在某种程度上，DSM模型在特征提取时考虑了节点之间隐式的边连接关系. 此外，DSM可以作为插件与任意现有的基于频域和空间域的方法进行组合并且可以实现端到端的训练.

考虑到给定图结构通常难以囊括节点间实际存在的所有关联关系，当前仅根据给定图结构进行特征聚合的GNNs^[9-11]模型会导致一些节点无法从其他节点聚合得到充足的特征. 为了解决这一问题，提出DSM模型挖掘节点之间隐式连接关系. DSM主要由2部分组成：相似节点选择和相似节点的信息纳入. 受到Gumbel Softmax的启发^[19]，设计了可微分的top-K相似节点选择算法，使得已有GNNs在与DSM相结合后仍然可以实现端到端的训练.

DSM的基本思路如下. 给定图 $G$，首先通过GNNs得到各节点的基本表征 ${{\boldsymbol{H}}'} = [{\boldsymbol{h}}_1',{\boldsymbol{h}}_2',\cdots , {\boldsymbol{h}}_N'] \in {{\bf{R}}^{F \times N}}$， ${\boldsymbol{h}}_i'$为节点 $i $的基本表征. 其次，根据节点基本表征计算节点相似度 $ {s_{i,j}} = - ||{\boldsymbol{h}}_i' - {\boldsymbol{h}}_j'||_2^2 $, $i,j \in \{ 1,\cdots , N\} $. 在此基础上，选出与节点 $i$相似度最高的 $K$个节点，并利用这些节点的基本表征得到聚合表征. 对于 $k = 1,\cdots ,K$，令 ${i_k}$表示与节点 $i$相似度最高的第 $k$个节点，即 ${s_{i,{i_1}}},\cdots ,{s_{i,{i_K}}}$为 ${s_{i,1}},\cdots ,{s_{i,N}}$中最大的 $K$个值，则根据这 $K$个节点的节点表征 ${\boldsymbol{h}}_{{i_1}}',\cdots , {\boldsymbol{h}}_{{i_K}}'$即可得到节点 $i$的增强表征.

为了使相似节点选择过程可微，将相似节点的选取过程分为 $K$个阶段，在第 $k$阶段得到节点表征 ${\boldsymbol{h}}_i^{(k)}$，使得 ${\boldsymbol{h}}_i^{(k)} \approx {\boldsymbol{h}}_{{i_k}}'$. 为了方便后续介绍可微分节点表征 ${\boldsymbol{h}}_i^{(k)}$的计算方法，定义在阶段 $k$时节点 $j$相对节点 $i$的权重变量表达式如下：

(1) $ \beta _{ij}^{(k)} = \frac{{\exp\; (\lambda s_{ij}^{(k)})}}{{\displaystyle \sum\limits_{l = 1}^N {\exp\; (s_{il}^{(k)})} }}. $

式中： $\lambda > 0$为超参数； $s_{ij}^{(k)}$为节点 $j$在阶段 $k$相对节点 $i$的泛化相似度.

(2) $ s_{ij}^{(k)} = \left\{ \begin{gathered} s_{ij}^{(k - 1)}+\lg \;(1 - \beta _{ij}^{(k - 1)}),\;k \geqslant 2 ; \\ {s_{ij}^{(k-1)}},\;\qquad \qquad \qquad \;\; k = 1. \\ \end{gathered} \right. $

在此基础上，可微分节点表征 ${\boldsymbol{h}}_i^{(k)}$的表达式如下：

(3) $ {\boldsymbol{h}}_i^{(k)} = \sum\limits_{j = 1}^N {\beta _{ij}^{(k)}{\boldsymbol{h}}_j'} . $

接下来，将证明 $ {\boldsymbol{h}}_i^{(k)} \approx {\boldsymbol{h}}_{{i_k}}' $. 将在阶段 $k$时与节点 $i$具有最大泛化相似度的节点记为 ${i_{(k)}}$，即 $s_{i{i_{(k)}}}^{(k)}$为相似度集合 $\{ s_{i1}^{(k)},\cdots ,s_{iN}^{(k)}\} $中取值最大的元素. 当λ足够大时，根据式(2)、(3)可以观察到如下规律.

规律1.　　对于任意节点 $j \in \{ 1,\cdots ,N\} $，若 $j \ne {i_{(k)}}$，则 $\;\beta _{ij}^{(k)} \approx 0$；若 $j = {i_{(k)}}$，则 $\;\beta _{ij}^{(k)} \approx 1$.

规律2.　　对于任意节点 $j \in \{ 1,\cdots,N\} $，若 $j \ne {i_{(k)}}$，则 $s_{ij}^{(k+1)} \approx s_{ij}^{(k)}$；若 $j = {i_{(k)}}$，则 $s_{ij}^{(k+1)} \to - \infty $.

根据式（1）~（3），显然有 ${i_{(1)}} = {i_1}$. 进一步地，由式（3）和规律1可知，若 ${i_{(k)}} = {i_k}$，则 ${\boldsymbol{h}}_i^{(k)} \approx {\boldsymbol{h}}_{{i_k}}'$. 此外，由规律2可知 $\;\beta _{i{i_{(k)}}}^{(k+1)} \approx 0$，即可以近似认为节点 ${i_{(k)}}$在第 $k+1$次迭代中对 ${\boldsymbol{h}}_i^{(k+1)}$的贡献基本为0，因而可以推导出 ${i_{(k+1)}} = {i_{k+1}}$. 综上所述， ${\boldsymbol{h}}_i^{(k)} \approx {\boldsymbol{h}}_{{i_k}}'$证毕.

在此基础上，对 $K$个相似节点的基本表征 ${\boldsymbol{h}}_i^{(1)},\cdots ,{\boldsymbol{h}}_i^{(K)}$进行逐元素的最大池化操作，从而得到聚合表征 ${\boldsymbol{h}}_i''$；再将聚合表征 ${\boldsymbol{h}}_i''$和节点基本表征 ${\boldsymbol{h}}_i'$进行拼接，最终得到增强表征 ${\hat {\boldsymbol{h}}_i}$. 其中， ${\boldsymbol{h}}_i''$和 ${\hat {\boldsymbol{h}}_i}$的计算过程可以用如下2个公式进行形式化描述：

(4) $ {{\boldsymbol{h}}}_i'' = {{\rm{MaxPool}}} \;\{ {{\boldsymbol{h}}}_i^{(1)},{{\boldsymbol{h}}}_i^{(2)},\cdots ,{{\boldsymbol{h}}}_i^{(K)}\} , $

(5) $ {\hat {\boldsymbol{h}}_i} = {{\rm{Concat}}} \;({\boldsymbol{h}}_i',{\boldsymbol{h}}_i '') . $

DSM的计算开销主要来自节点相似度的计算，其算法复杂度为 $O({N^2})$，能够适用于大多数情况下的图节点分类场景. 当图的规模较大时，则可以通过适当地缩减搜索区域来提升计算效率，比如，在以目标节点为中心的某一区域中寻找相似节点而不是在整个图中寻找.

DSM作为插件与GNNs结合的整体结构如图1所示. 该框架主要包含3个部分：GNN、DSM和分类器. 首先，采用GNN用于提取节点的基本表征；其次，对于每一个节点，DSM选取 $K$个与其相似度最高的节点并进行表征聚合；在此基础上，拼接相似节点聚合表征和目标节点的基本表征得到目标节点的增强表征；最后，将所得到的增强表征输入到分类器中进行节点分类.

为了保证节点基本表征具备一定表征能力，整个网络的损失函数L包含2部分：1）采用节点增强表征进行分类的损失函数 $ {L_{{\text{final}}}} $；2）采用节点基本表征进行分类时的损失 $ {L_{{\text{basic}}}} $.

(6) $ \begin{split} L =\;& {L_{{\text{final}}}}+\gamma {L_{{\text{basic}}}} = \\ \;&- \frac{1}{V}\sum\limits_{i = 1}^V {\sum\limits_{j = 1}^C {I({y_i} = j){{\log }_{\text{2}}}\;({\text{Soft}}\max \;({v_{i,j}}))} } - \\ \;&\gamma \frac{1}{V}\sum\limits_{i = 1}^V {\sum\limits_{j = 1}^C {I({y_i} = j)} } {\log _{\text{2}}}\;({\text{Soft}}\max\; ({u_{i,j}})) . \end{split} $

式中： $\gamma \in [0,1.0]$为损失平衡因子； $C$为节点类别数； $I(P)$为指示函数，当 $P$为真时该函数等于1，反之为0； $V$为参与训练的节点个数； ${y_i}$为节点 $i$的真实标签； ${v_{i,j}}$和 ${u_{i,j}}$分别为节点 $i$使用增强表征和基本表征预测时属于第 $j$类的概率； $ {\text{Soft}}\max \;( \cdot ) $为归一化指数函数， $ {\text{Soft}}\max \;({v_{i,j}}) = {{\exp \;({v_{i,j}})} \mathord{\left/ {\vphantom {{\exp ({v_{i,j}})} {\sum\limits_{l = 1}^C {\exp ({v_{i,l}})} }}} \right. } {\displaystyle \sum\nolimits_{l = 1}^C {\exp\; ({v_{i,l}})} }} $， $ {\text{Soft}}\max\; ({u_{i,j}}) = {{\exp \;({u_{i,j}})} \mathord{\left/ {\vphantom {{\exp ({u_{i,j}})} {\sum\limits_{l = 1}^C {\exp ({u_{i,l}})} }}} \right. } {\displaystyle \sum\nolimits_{l = 1}^C {\exp \;({u_{i,l}})} }} $.

本研究实验所使用的数据集为开源的引文网络Cora、Citeseer和Pubmed^[20]. 在这3个引文网络中，每个节点表示一篇论文，节点初始特征为该论文对应的词袋特征向量；每条边均为无向边，表示所连接的2篇论文之间具有引用关系；节点的标签代表论文的主题. 如表1所示为3个数据集的重要信息. 表中， $ N 、 M 、 D 、C $分别为节点数、边数、初始特征维度和类别数.

参照GCN^[18]和GAT^[11]的默认参数设置： GCN-DSM的隐藏层神经元个数设置为16，GAT-DSM的注意力头数和每个注意头中的隐藏层神经元个数均为8；学习率分别置为0.010和0.005，每一层的dropout比率分别为0.5和0.6，实验中 ${L_2}$正则化系数统一设置为0.000 5. 此外，DSM中默认超参数设置为： $\lambda = 1.0 \times {10^9}$， $K = 5$， $\gamma = 0.1$.

与文献[9]相同，实验数据被随机划分为训练集、测试集和验证集. 为了保证实验的可信度，每组实验均重复50次且每次实验使用不同的随机种子，列出重复实验结果的平均值和标准差. 此外，为了评估不同方法相对训练样本数目的鲁棒性，除了常规的每类20个训练节点的测试条件^[18]以外，同时测评各模型在更少的训练样本（每类5个节点和每类10个节点）条件下的表现. 在整个实验过程中，验证集和测试集的样本数分别为500和1 000.

实验中所有方法的代码都基于Tensorflow框架实现^[21]. 所有的实验均在具有32 G RAM和4块NVIDIA Tesla V100 GPU的X86_64设备上进行.

参照已有的节点分类工作，采用准确度作为性能评价指标，主要与以下2类方法进行对比和评估. 1）传统方法：直接使用每个节点的特征向量训练一个逻辑回归分类器的原始特征法（Raw）、采用由2层神经网络构成的多层感知机MLP以及DeepWalk^[22]. 其中，MLP中的节点表征维度为16，DeepWalk采用文献[22]中的默认参数设置. 2）基于GNNs的方法：ChebyNet^[17]、GCN^[18]和GAT^[11]. GCN和ChebyNet的参数设置与文献[18]中GCN的训练参数设置相同，GAT的参数设置与文献[11]中的相同.

如表2所示记录了各方法在Cora数据集上的平均准确率. 表中，黑体表示对应数据集上准确率最高的实验结果. 可以看出，将DSM作为插件与GNNs相结合的模型的节点分类表现优于已有方法的. 以“5节点/类”（即每个类别有5个训练节点）为例，DeepWalk的准确率仅为53.6%，GCN-DSM和GAT-DSM在“5节点/类”情况下准确度分别为69.4%和75.1%，而GCN与GAT在在同样的条件下的准确度分别为68.2%和72.2%，即GCN和GAT在与DSM结合后，准确率分别提升了1.2%和2.9%，说明DSM实现了节点表征增强. 还可以看出GAT-DSM的表现优于GCN-DSM，说明GNNs的种类对分类结果也有较大的影响. 此外，ChebyNet、GCN和GAT显著优于传统方法.

如表3、4所示分别为在数据集Citeseer和Pubmed上的实验结果. 与在Cora数据集上的结果类似，在数据集Citeseer和Pubmed上的结果进一步证明了DSM的有效性. 在不同规模的训练数据集下结果均具有一致性，体现了DSM的鲁棒性.

由表2~4可知，相较于“10 节点/类”和“20 节点/类”的实验条件，在训练样本数较小（即“5 节点/类”）时DSM对GNNs的性能有更为显著的提升. 这是因为在训练节点数量较少时有标签的节点不能充分反映每一类节点的特征，而DSM可以利用相似节点进一步丰富各节点所能获取到的类别信息从而提升节点分类准确度. 因此，随着训练样本数量的增加，DSM对于准确度提升程度逐渐减少.

为了验证GNNs-DSM与常规的GNNs之间是否存在显著的性能差异，在实验中使用 $p$值阈值 $\alpha $=0.05的Wilcoxon符号秩检验，如表2~4所示. 表中，对于GCN-DSM和GAT-DSM，标有星号的数据表示，经由Wilcoxon符号秩检验判断，采用DSM后方法有显著的性能提升（比较对象为相对应的常规GNNs）. 可以看出，9组GCN-DSM实验中有7组的性能相比于对应的常规GCN有显著的提升. 同时，9组GAT-DSM 实验都对 GAT 的性能有显著提升，进一步证明了DSM能给GNNs带来显著的性能提升.

如图2所示为不同方法在“5 节点/类”实验条件下的t-SNE图^[23]. t-SNE图中一个点表示一个节点，具有相同颜色的点属于同一类. 可以看出，从原始特征法到GAT-DSM，t-SNE图中的聚类效果逐渐明显. 具体来说，原始特征法的t-SNE图中不同颜色的点混杂在一起难以区分，而GCN和GAT的t-SNE图中各种颜色的点簇聚类效果更佳. 进一步地，在GCN-DSM和GAT-DSM的t-SNE图中，相同颜色的节点更为集中，不同颜色的节点可区分性更强. 上述结果表明在将GNNs与DSM相结合后，可以学习到更有辨识性的节点表征从而提高节点分类准确度.

如图3(a)所示为GNNs-DSM在超参数 $K$取不同值的情况下在Cora数据集上的节点分类准确率Acc变化趋势. 由于GCN和GAT的实验结果与 $K$无关，因此将两者作为对照组. 如图3(a)所示，当 $K$从1逐步增加至15时，GCN-DSM和GAT-DSM的准确率变化曲线为“^”形. 以GAT-DSM为例，当 $K$从1逐步增加至5时，此时由于所学到的节点表征包含了更多的同类别信息因而准确率有所提升；在 $K = 5$时GAT-DSM的准确度达到最大值；当 $K > 5$时，由于所学的节点表征可能会包含过多其他不同类别节点的信息，准确率会逐渐下降. 另外，在 $K$从1变化到15的整个过程，GAT-DSM和GCN-DSM的准确率均要高于GAT和GCN，说明DSM模型不仅可以提高节点分类准确率，还具有一定的鲁棒性

如图3(b)所示为GNNs-DSM在不同超参数 $\lambda $的实验条件下在Cora数据集上的节点分类准确率变化趋势. 可以看出，随着 $\lambda $的增加，准确率先上升，然后再逐渐趋于稳定. 当 $\lambda $较小时，不满足2.1节的规律1的前提条件，因此在DSM迭代过程中每一阶段选择的可能不是当前阶段相似度最高的节点，这无疑会将噪声引入到节点增强表征中，从而影响最终的分类准确率. 当 $\lambda $足够大时，2.1节的规律1和规律2的前提条件得以满足，上述问题得到显著改善.

如图3(c)所示为GNNs-DSM在不同损失平衡因子 $\gamma $的实验条件下在Cora数据集上的节点分类准确率变化趋势. 在 $\gamma $从0逐渐增加至1.0的过程中，GCN-DSM和GAT-DSM的准确率变化曲线呈“^”形. 当 $\gamma = 0$时，GCN-DSM的准确率甚至要低于GCN. 这一现象出现的主要原因如下：当 $\gamma = 0$时，GCN-DSM的GCN部分因为没有较强的损失约束而无法得到有效的训练，致使DSM的输入（即GCN输出的节点基本表征）无法准确反映节点之间的相似关系，导致GCN-DSM整体表现不佳. 当 $0 < \gamma < 1.0$时，GCN-DSM和GAT-DSM相较于常规GCN和GAT性能有显著提升. 以上实验结果反映了对GNN-DSM整体与GNN部分进行联合训练的重要性. 此外，当 $\gamma = 1.0$时，GCN-DSM和GAT-DSM的性能提升并不明显，这是因为 $\gamma = 1.0$会导致整个学习过程给予基本表征学习过多关注而相对忽略了增强表征的优化. 综上所述，对于具体的GNNs-DSM，选择一个合适的损失平衡因子 $\gamma $是至关重要的.

提出可微分相似度模型DSM，该模型利用相似节点的信息挖掘节点之间隐式的边连接关系并且可以作为插件与任意GNNs相结合. 从实验测评和理论分析2个方面证明了将DSM作为插件与GNNs相结合不仅可以显著提高GNNs的节点分类准确率同时也保留了可以进行端到端训练的特性. 此外，在多个真实数据集上的实验结果也充分证明了DSM的有效性和鲁棒性. 除了GCN和GAT这2大最为主流的GNNs模型外，近年来众多学者设计出了多种多样的GNNs模型^{[19, 24-25]}，取得了显著的效果. 由于篇幅限制，本研究未对DSM与这些最新的优秀GNNs相结合的效果进行测试. 在未来的工作中，计划将DSM与目前最新的优秀GNNs模型相结合进一步测试DSM的有效性. 此外，还将探究如何将DSM拓展应用于异质图神经网络.