一种面向图神经网络的节点特征升维分析方法

A Node Feature Dimension Augmentation Analysis Method for Graph Neural Networks

摘要

现有针对图神经网络节点特征重要性的研究方法主要基于图结构特征，难以针对每个节点特征的重要性进行分析。为解决这一问题，提出一种面向图神经网络的节点特征升维分析方法。首先，在高维空间中对节点特征进行升维表示，并针对高维节点特征数据稀疏的特点构建适配数据结构；然后，扩展定义高维空间图神经网络计算规则并对高维节点特征进行计算；最后，对高维空间中的计算结果分析得出各个节点特征在图神经网络计算结果中的权重。实验中，大权重节点特征对模型准确率影响最大为62.88%，验证了该权重能够有效反应输入节点特征的重要性。

Abstract

Existing research methods for analyzing the importance of node features in graph neural networks are primarily based on structural features, making the analysis of each node feature’s importance difficult. To address this issue, a node feature dimension augmentation analysis method for graph neural networks is proposed. Firstly, node features are represented in a high-dimensional space, and a data structure adapted for the sparse characteristics of high-dimensional node feature data is constructed. Then, the computational rules of graph neural networks are extended and defined in high-dimensional space, with high-dimensional node features being calculated accordingly. Finally, the calculation results in high-dimensional space are analyzed, and the weights of each node feature in the graph neural network calculation results are obtained. In experiments, it is found that node features with large weights have the greatest impact on model accuracy, accounting for 62.88%, which verifies that the weights can effectively reflect the importance of input node features.

Graphical abstract

关键词

图神经网络 / 节点特征 / 升维 / 权重分析

Key words

graph neural network / node feature / dimension augmentation / weight analysis

0 引言

图神经网络^[1-3]是一种面向图数据^[4]的深度神经网络模型。图数据是一种抽象的数据结构，能够把研究对象的属性以及对象间的关系进行抽象表示，包含结构特征与节点特征两类。结构特征表示节点之间的连边关系，用于抽象表示对象之间的相互关系；节点特征表示研究对象自身的属性特征。图神经网络通过图卷积层的计算将节点及其邻近节点的特征进行聚合，实现了对于结构特征与节点特征的同时学习。由于图神经网络模型具有“黑盒”属性^[5-6]，模型缺乏可解释性，难以解析模型的分类、决策机理。针对图神经网络模型节点特征重要性的研究也称为节点中心性^[7]，是研究模型内在机理与可解释性^[8]的重要内容之一。通过节点特征重要性的研究，能够将节点特征与结构特征对网络模型的影响力进行分解研究，聚焦模型对于不同节点特征的关注度，加强对模型分类、决策机理的理解，为改进设计、提升性能提供理论支撑。

现有针对图神经网络节点特征重要性的研究主要基于结构特征，即通过节点之间的连接关系来分析其重要性。典型方法包括度中心性方法^[9]通过图的结构特征计算节点的邻居节点个数得出节点的重要性，即节点连边越多，重要性越强。介数中心性方法^[10]通过图的结构特征，计算经过节点的最短路径次数、度量节点的重要性。K-壳分解法^[11]通过结构特征，对节点的外层结构剥离，增加内层节点的影响力并度量其重要性。PageRank方法^[12]是谷歌公司提出的网页排序方法，计算经过节点的连边次数与和连边对应节点的质量，得出节点的重要性。文献[13]提出的图注意力机制通过图神经网络模型为每个节点学习生成一个注意力系数，从而得到反应节点重要性的权重。然而，由于基于结构特征的研究方法不能针对节点特征在图神经网络模型中存在的线性关系进行表示与解析，因此无法进一步区分图神经网络模型对于每个节点特征的关注度，难以针对节点特征的重要性进行分析。

针对上述问题，通过对节点特征进行升维表示，在高维空间中为节点特征增加可用于分析其在模型计算结果中影响力的维度信息，提出一种面向图神经网络的节点特征升维分析方法。首先在高维空间中对节点特征进行升维表示，得到高维特征；其次在高维空间中对图神经网络计算进行扩展，并对高维特征进行计算；最后对高维空间中的计算结果分析得到节点特征的影响力，即为从图神经网络模型的计算结果中分析得到的节点特征的权重。实验验证了所提方法分析得出的权重数值能够有效反映节点特征对图神经网络的影响力，并对所提方法在实验中的计算复杂度进行讨论。

1 系统模型

令图数据集中含有M个节点，每个节点含有N个特征。在图神经网络的计算中，节点特征矩阵为\mathit{X}\in {\mathit{R}}^{M\times N}，对于其中每个特征数值x_{i,j}而言，与其相关的运算均为定义在实数域上的加法与数乘运算。以节点特征x_{\mathrm{1}}与x_{\mathrm{2}}为例，与其相关的运算可概括为式（1）所示形式：

a{x}_{\mathrm{1}}+b{x}_{\mathrm{2}}=c（1）

式中，a,b,c\in \mathbb{R}，在图神经网络中，除了激活函数外，其余运算均为线性运算。因此如式（1）中x_{\mathrm{1}}与x_{\mathrm{2}}，其在计算结果c中的权重分别为a与b，构成线性关系。

本文图神经网络模型使用的激活函数为ReLU函数^[14]，如式（2）所示：

（2）

虽然该函数在定义域上为非线性，但却为分段线性。当ReLU函数处于x\ge \mathrm{0}激活状态时，输出的x与输入的x意义相同，由于输入的x包含前序线性运算中各个特征之间的线性关系，则输出的x“隐含”前序线性运算中各个特征之间的线性关系。由于ReLU函数为非线性函数，不能够通过解析的方法分析出ReLU函数输出的x“隐含”的前序线性运算的信息。现有基于结构特征的方法不能对该线性关系进行解析，由此则不能对节点特征在图神经网络模型的计算结果中的影响力进行分析。

因此考虑设计一种方法，使得输入节点特征x_{i,j}在计算中“携带”更多的信息，进一步由ReLU函数输出的x仍然“携带”与输入节点特征相关的信息，使得输出的x“隐含”的前序线性运算信息能够进行“显式”表达。使用n维欧氏空间的标准正交基对节点特征进行升维，即为将节点特征矩阵\mathit{X}中的每个数值特征在欧氏空间中使用一个向量进行表示。定义一个标准正交向量集合A=\left\{{\mathit{\alpha }}_{\mathrm{0}},{\mathit{\alpha }}_{\mathrm{1}},\cdots ,{\mathit{\alpha }}_n,\cdots \right\}，各向量表示为：

\begin{array}{c}{\mathit{\alpha }}_{\mathrm{0}}:\left[\mathrm{1,0},\mathrm{0},\cdots ,\mathrm{0},\cdots \right]\\ {\mathit{\alpha }}_{\mathrm{1}}:\left[\mathrm{0,1},\mathrm{0},\cdots ,\mathrm{0},\cdots \right]\\ ⋮\\ {\mathit{\alpha }}_n:\left[\underset{n}{\underbrace{\mathrm{0,0},\mathrm{0},\cdots }},\mathrm{1},\cdots \right]\end{array}

其中，下标索引从0开始起算。为便于进行规范严谨论述，定义向量集合\mathit{E}，如式（3）所示：

\mathit{E}=\left\{\sum _i{c}_i{\mathit{\alpha }}_i\right\}（3）

式中：c_i\in \mathbb{R};i\in \mathbb{N};{\mathit{\alpha }}_i\in \mathit{A}。显然向量集合\mathit{E}满足：\forall a,b\in \mathbb{R}；{\mathit{e}}_{\mathrm{1}},{\mathit{e}}_{\mathrm{2}}\in \mathit{E}；a{\mathit{e}}_{\mathrm{1}}+b{\mathit{e}}_{\mathrm{2}}\in \mathit{E}；具有完备性。

对于升维后的特征向量，比原始特征增加一个计算维度。对于特征矩阵为\mathit{X}\in {\mathit{R}}^{M\times N}的数值矩阵，升维后记特征矩阵为\mathit{F}\in {\mathit{E}}^{M\times N}的向量矩阵，对于矩阵\mathit{X}中的第i行j列的数值x_{i,j}与矩阵\mathit{F}中的第i行j列的向量{\mathit{f}}_{i,j}，显然x_{i,j}=S({\mathit{f}}_{i,j})。其中S(\cdot )表示向量的元素和。本文讨论的“向量矩阵”与数学中对于矩阵的通用定义有所区别，该向量矩阵由向量排列组成，即为三维张量，称之为向量矩阵，目的在于建立节点特征在进行升维表示前后的对应关系，如x_{i,j}与{\mathit{f}}_{i,j}所示。

当升维以后的特征矩阵\mathit{F}\in {\mathit{E}}^{M\times N}进入图神经网络进行计算时，其运算超出图神经网络中矩阵内积乘法定义的范围，因此对相应运算进行扩展定义，主要包括稀疏数值矩阵\mathit{L}与稀疏向量矩阵\mathit{F}的内积乘法，稀疏向量矩阵\mathit{F}与数值矩阵\mathit{W}的内积乘法，以及稀疏向量矩阵\mathit{F}通过ReLU激活函数的计算。对于稀疏向量矩阵\mathit{F}在高维空间中由图神经网络进行计算输出的高维计算结果，可通过维度信息分析得到节点特征矩阵\mathit{X}中的每个特征在图神经网络计算结果中的权重。

因此，本文采用针对节点特征进行“升维”的研究思路，通过对节点特征进行升维表示，使其在高维空间中相互正交，并“携带”可用于分析其在计算结果中影响力的维度信息，最后实现在高维空间中由图神经网络的计算结果分析得到节点特征的权重。

2 节点特征升维分析方法

针对节点特征的升维分析方法主要包含以下步骤：首先，在高维空间中对节点特征进行升维表示；然后，在高维空间中对图神经网络的计算进行扩展，并对高维节点特征进行计算；最后，对图神经网络在高维空间中的计算结果进行分析，得到节点特征在计算结果中的权重。

2.1 节点特征的升维表示

针对节点特征进行升维表示，把特征矩阵\mathit{X}\in {\mathit{R}}^{M\times N}中的每个特征数值x_{i,j}分别分配到一个向量{\mathit{\alpha }}_{i\times N+j}\in \mathit{A}上，如式（4）所示：

{\mathit{f}}_{i,j}=x_{i,j}\cdot {\mathit{\alpha }}_{i\times N+j}（4）

式中，{\mathit{f}}_{i,j}为升维后的向量矩阵\mathit{F}的第i行j列的向量。从计算的角度来看，是把一个数值“升维”成了一个向量，因此将本文的研究方法归纳为“升维”方法。由于集合\mathit{A}中的向量互相正交，因此进行升维后的数值特征之间相互正交。

由于图数据的统计特性，其节点特征中包含大量0数值，在计算中用稀疏矩阵存储数据。稀疏矩阵具有较低的索引访问效率，进行升维之后的向量矩阵，实际上为三维稀疏张量，需构建与其数据特点适配的数据结构以保证本文方法的运算效率，数据结构的构成如图1所示，共构造4种数据类型，分别为非零数值、稀疏向量、向量行与向量矩阵。

2.2 图神经网络在高维空间中的运算

对节点特征进行升维表示后得到高维节点特征，需在高维空间中对图神经网络的计算扩展定义，用于支持对于高维节点特征的运算，主要包含以下3种运算。

2.2.1 向量矩阵左乘数值矩阵

该运算对应图神经网络中拉普拉斯矩阵与特征矩阵的内积乘法，如式（5）与式（6）所示：

{\mathit{Y}}_{i,j}^{}={\mathit{L}}_{i,:}\cdot {\mathit{F}}_{:,j}={\displaystyle \sum _{l=\mathrm{1}}^M}{\mathit{L}}_{i,l}\cdot {\mathit{F}}_{l,j}（5）

{\mathit{Y}}_{i,:}^{}={\displaystyle \sum _{l=\mathrm{1}}^M}{\mathit{L}}_{i,l}\cdot {\mathit{F}}_{l,:}（6）

式中：\mathit{L}表示拉普拉斯矩阵，为稀疏矩阵，其数据存储时包含坐标列表与值列表两部分；\mathit{F}为升维以后的特征矩阵；\mathit{Y}为内积乘法的计算结果。基本思路为：生成一个空结果向量矩阵，遍历拉普拉斯矩阵中的一组坐标与相应数值，由其列坐标索引访问向量矩阵中对应的向量行，其数值与向量行中所有稀疏向量相乘后生成的向量行，加法赋值到结果向量矩阵中的行坐标对应的向量行。该方法对于通过索引访问向量矩阵中的向量行提出了较高的效率要求，因此在数据类型的构造中专门设置了对于向量行的高效索引访问功能。

2.2.2 向量矩阵右乘数值矩阵

该运算对应图神经网络中的特征矩阵与参数矩阵的内积乘法，如式（7）与式（8）所示：

{\mathit{Y}}_{i,j}^{}={\mathit{F}}_{i,:}\cdot {\mathit{W}}_{:,j}={\displaystyle \sum _{l=\mathrm{1}}^N}{\mathit{F}}_{i,l}\cdot {\mathit{W}}_{l,j}（7）

{\mathit{Y}}_{i,:}^{}={\displaystyle \sum _{l=\mathrm{1}}^N}{\mathit{F}}_{i,l}\cdot {\mathit{W}}_{l,:}（8）

式中：\mathit{W}表示参数矩阵，为稠密矩阵；\mathit{F}为升维以后的特征矩阵；\mathit{Y}为内积乘法的计算结果。该方法的基本思路与上一节类似，生成一个空结果向量矩阵，遍历向量矩阵中的所有稀疏向量，由稀疏向量的列索引访问参数矩阵的一行参数，稀疏向量与该行参数数值分别相乘后生成的稀疏向量，列索引赋值为各个参数数值的列索引，行索引不变，生成的稀疏向量构成一个向量行，加法赋值到结果向量矩阵中的行坐标对应的向量行。

2.2.3 向量矩阵过ReLU激活函数

在构造向量矩阵的数据类型时，对于其中的稀疏向量类型设定了存储“元素和”的成员，在向量矩阵的计算中，当稀疏向量中的元素进行计算时，其元素和随计算自动更新。向量矩阵过ReLU激活函数的运算如式（9）所示：

\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}\left(\mathit{e}\right)=\left\{\begin{array}{c}\mathit{e},S(\mathit{e})>\mathrm{0};\\ \mathrm{0},S(\mathit{e})\le \mathrm{0}.\end{array}\right.（9）

式中：\mathit{e}\in \mathit{E}；S(\mathit{e})为稀疏向量的元素和，当稀疏向量的元素和小于等于0时，该向量赋值为0向量，则在向量矩阵的向量行中删除该向量。

2.3 权重分析

当升维后的节点特征矩阵经过训练好的图神经网络计算之后，仍然得到一个向量矩阵，转换为三维数值张量的角度进行分析，第1个维度为对应节点的索引，第2个维度为节点在经过图神经网络计算后的分类索引，第3个维度为在对特征进行升维时标准正交向量的索引，数值为标准正交向量对应的权重，由该标准正交向量与原始节点特征的对应关系，可进一步得出该数值即为原始节点特征在图神经网络计算结果中的权重。由上述计算可知，在每个节点的每个分类计算结果中，包含了对应所有原始节点特征的权重。

进一步由节点特征升维时与标准正交向量的对应关系，分析得到该权重对应的节点特征。k表示第3个维度的索引，N整除k为节点索引i，N对k求余即为节点的特征索引j，分别如式（10）与式（12）所示：

i=k\left|N\right.（10）

j=k\mathrm{m}\mathrm{o}\mathrm{d}N（11）

3 实验验证

本节通过在真实数据集上的实验，验证本文分析方法所得权重的有效性，即为节点特征权重与节点特征对于图神经网络模型的影响力是否对应。

3.1 实验设计

本实验中的图神经网络模型由两个图卷积层构成如式（12）和式（13）所示：

{\mathit{X}}^{\text{'}}=\mathrm{R}\mathrm{e}\mathrm{L}\mathrm{U}\left(\mathit{L}\mathit{X}{\mathit{W}}_{\mathrm{1}}\right)（12）

\mathit{Y}=\mathit{L}{\mathit{X}}^{\text{'}}{\mathit{W}}_{\mathrm{2}}（13）

式中：\mathit{X}为节点特征矩阵；\mathit{L}为拉普拉斯矩阵；{\mathit{W}}_{\mathrm{1}}、{\mathit{W}}_{\mathrm{2}}为全连接层的参数矩阵；第1个图卷积层由ReLU函数激活；\mathit{Y}为图神经网络的分类计算结果。

图数据集选用Cora^[15]、Cora-ML^[16]、Citeseer^[15]与Polblogs^[17]这4个数据集，数据集参数如表1所示。

通过两种方法对于该权重进行验证。方法1：对于测试集中的节点分析结果，按照权重由大到小依次累积删除80%的特征，并测试每次删除特征后模型的测试准确率；方法2：对于测试集中的节点分析结果，按照权重由小到大依次累积删除80%的特征，并测试每次删除特征后模型的测试准确率。

3.2 实验数据

图2为4个数据集上的测试数据，图中横坐标为删除特征的比例，纵坐标为删除特征后的测试准确率。

在实验设计的条件下，方法1对于准确率产生了巨大的影响，在4个数据集的准确率测试中，均出现了大幅度的下降，其中在Cora数据集上准确率最低为19.87%，降幅为62.88%；在Cora-ML数据集上准确率最低为25.58%，降幅为59.70%；在Citeseer数据集上准确率最低为33.23%，降幅为40.05%；在Polblogs数据集上准确率最低为62.07%，降幅为33.84%。方法2对于准确率的影响较小，在Cora-ML数据集、Citeseer数据集与Polblogs数据集上的测试对于准确率几乎无影响，数据曲线无明显向下波动趋势；在Cora数据集上，准确率曲线在后段出现了下降趋势，准确率最大降低至73.79%，降幅为8.95%。

3.3 讨论

通过实验数据中方法1与方法2的对比发现，当按照权重由大到小对应的特征进行累积删除时，对测试准确率明显受到了大幅影响，证明本文方法分析得出的大权重特征在图神经网络的计算中有较大的影响力，当数据集中缺少这些特征时，模型的分类性能会出现大幅度损失，特别是将这些大权重特征同时删除时，会使得模型性能急剧下降。特别注意到Citeseer数据集在特征删除比例小于0.1时曲线出现的陡峭下降，表明本文方法在该数据集上分析出的大权重特征能够准确契合数据集在图神经网络中的内在规律。

方法2中按照权重由小到大对应的特征进行累积删除时，在本文实验讨论的范围中对于测试准确率几乎未产生明显影响，表明本文方法分析得出的小权重特征在图神经网络的计算中的影响力极小，能够契合数据集在图神经网络模型中内在规律，特别是将小权重特征进行累积删除时，未对模型的分类性能造成影响。

4 计算复杂度分析

由于图数据的特点，其矩阵表示中存在大量零数值，因此相应计算均转换为稀疏数据类型及相应稀疏矩阵方法。本文方法考虑到升维之后产生的计算复杂度，设计定义适合该方法的向量矩阵的稀疏数据类型。由于稀疏数据类型方法的特点，不能用方法的计算复杂度求出解析表达式分别说明时间复杂度与空间复杂度，为此在表2中列出图神经网络中各个计算环节的非零数值数量与相应用时。

表2中列出的时间数据表明本文方法在实验采用的4个数据集上均能够快速完成计算，在Cora数据集上共用时12.75 s，在Cora-ML数据集上共用时142.184 s，在Citeseer数据集上共用时11.41 s，在Polblogs数据集上共用时8.544 s，除Cora-ML数据集用时超过1 min外，其余3个数据集均在13 s以内完成。

5 结束语

通过对节点特征进行升维表示，提出一种针对图神经网络的节点特征升维分析方法，该方法可对图神经网络的计算输出结果解耦原始输入特征的权值，通过实验验证该方法分析得到的权值能够契合图数据在图神经网络中的内在规律，并进一步结合该方法在图数据集上的计算复杂度讨论其运算效率，能够在常用真实数据集上进行高效计算，具有可行性。

本文实验分别从大权重特征与小权重特征两个角度验证了该方法分析得出的权值的有效性，这两个角度包含图数据中特征的一般规律，能够支撑进一步的研究讨论。如实验中通过删除大权重特征造成模型性能的大幅下降，可对该大权重特征进一步进行研究，基于该大权重特征研究图神经网络的脆弱性与对抗性攻击问题。

参考文献

[1] ZHOU J， CUI G Q， HU S D，et al. Graph neural networks： a review of methods and applications［J］. AI Open， 2020，1：57-81.

[2] ZHANG Z W， CUI P， ZHU W W. Deep learning on graphs： a survey［J］. IEEE Transactions on Knowledge and Data Engineering， 2022，34（1）：249-270.

[3] WU Z H， PAN S R， CHEN F W，et al. A comprehensive survey on graph neural networks［J］. IEEE Transactions on Neural Networks and Learning Systems， 2021，32（1）：4-24.

[4] GOYAL P， FERRARA E. Graph embedding techniques， applications， and performance： a survey［J］. Knowledge-based Systems， 2018，151：78-94.

[5] ADADI A， BERRADA M. Peeking inside the Black-Box：a survey on explainable artificial intelligence（XAI）［J］. IEEE Access， 2008，6：52138-52160.

[6] RICCARDO G， ANNA M， SALVATORE R， et al. A survey of methods for explaining black box models［J］. ACM Computing Surveys， 2018，51（5）：1-42.

[7] LYU L， CHEN D B， REN X L， et al. Vital nodes identification in complex networks［J］. Physics Reports， 2016，650：1-63.

[8] 赵延玉，赵晓永，王磊，可解释人工智能研究综述［J］.计算机工程与应用，2023，59（14）：1-14.

[9] BONACICH P. Factoring and weighting approaches to status scores and clique identification［J］. The Journal of Mathematical Sociology， 1972，2（1）：113-120.

[10] ESTRADA E， RODRÍGUEZ-VELÁZQUEZ J A. Subgraph centrality in complex networks［J］. Physical Review E， 2005，71（5）：No.056103.

[11] KITSAK M， GALLOS L K， HAVLIN S，et al. Identification of influential spreaders in complex networks［J］. Nature Physics， 2010，6：888-893.

[12] LU L， ZHOU T， ZHANG Q M，et al. The H-index of a network node and its relation to degree and coreness［J］. Nature Communications， 2016，7（1）：No.10168.

[13] VELIČKOVIĆ P， CUCURULL G， CASANOVA A，et al.Graph attention networks［EB/OL］. （2018-04-30）［2024-04-22］.

[14] NAIR V， HINTON G E. Rectified linear units improve restricted boltzmann machines［C］∥Proceedings of the 27th International Conference on International Conference on Machine Learning. Cambridge，USA：Omnipress， 2010：807-814.

[15] SEN P， NAMATA G， BILGIC M，et al. Collective classificationin network data［J］. AI Magazine， 2008，29（3）：93-106.

[16] MCCALLUM A K， NIGAM K， RENNIE J，et al. Automating the construction of Internet portals with machine learning［J］. Information Retrieval， 2000，3（2）：127-163.

[17] ROSSI R A， AHMED N K. The network data repository with interactive graph analytics and visualization［C］∥Proceedings of the 29th AAAI Conference on Artificial Intelligence. Washington， USA： AAAI， 2015：4292-4293.

基金资助

嵩山实验室项目（纳入河南省重大科技专项）(221100210700-3)