论文地址：On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphs

一.论文概述

图神经网络（Graph Neural Networks, GNNs）在众多图相关的问题上都取得了优越的性能，而这成功的背后离不开图节点丰富的特征的支持。但是，事实上并不是所有的图节点都有特征，那么无属性图（no-attributed graphs）图神经网络又该如何处理呢？其输入该如何设计？本文便是对现有各种无属性图进行人工节点特征构造的总结。

二.两种人工节点特征

人工节点特征可以分为两大类：位置节点特征（Positional Node Features）和结构节点特征（Structural Node Features）。以图1为例，位置节点特征可以帮助GNNs将节点A和节点B在嵌入空间中放置的更近（二者在空间位置更接近），而结构节点特征将有助于将节点A和节点C放置的更近（因为A和C在图中的结构更相似，尽管两者离的很远）。

2.1 位置节点特征

位置节点特征能帮助GNNs捕获节点在图中相对位置的距离信息。位置节点特征适用于根据节点的位置对节点进行分类的任务。举个例子，在论文引用网络中两个相互引用并被其他类似作者引用的作者通常具有相似的研究兴趣，位置节点特征能很好的表达这种距离关系。

位置节点特征初始化方法包括：

• random：利用随机分布来为节点生成特征。随机特征本身并不反映图节点的相对位置，但它能记录每个节点的高维身份（identity），这可以间接帮助GNNs学习相对节点位置。
• one-hot：独热码，当GNNs的第一线性层中的参数被随机初始化时，该特征基本等同于随机特征。这种方法对于大图非常不合适，大图节点多，生成的one-hot矩阵非常大且稀疏。
• eigen：对正则化后的邻接矩阵进行特征分解，然后使用前$k$个特征向量为每个节点生成$k$为特征向量，其中$k$的最佳值可以通过网格搜索确定。
• deepwalk：通过DeepWalk算法来生成节点的初始特征。

2.2 结构节点特征

结构节点特征能帮助GNNs捕获节点的结构信息，如度信息和邻域连接模式。在图节点分类中，存在一些数据集，尽管其位置彼此远离，但是其具有相似的结构，其类别是相同的，这种情况是位置节点特征解决不了的。

结构节点特征初始化方法包括：

• shard：所有节点特征初始化为相同的向量，例如所有节点特征全部为1。
• degree：根据度为每个节点生成一个one-hot向量，这种方法对于高度节点的图也不合适，因为高度节点会导致生成的所有节点的one-hot矩阵非常大且稀疏。
• pagerank：计算给定节点的原始PageRank得分，然后将其展平（flatten）为一个向量，以充分利用神经网络的嵌入维数，其中嵌入的维数通过网格搜索来进行选择。
• degree+：degree的改良版，由于degree方法可能导致非常大且稀疏的特征矩阵，因此degree+提出将度值进行分桶，然后将每个桶范围内的度值映射到同一个类，并为每个类构造一个one-hot向量。（有点类似Role2Vec里面最开始的log binning，这样相对于根据图节点的结构模式对节点进行角色划分）

三.实验

作者在节点分类、图分类任务上对各种人工节点特征方法进行了对比分析，其中节点分类作者又细分为了位置节点分类和结构节点分类，两者都各自精挑细选了适合相应任务的数据集来进行实验。

图神经网络选择的是GraphSAGE，下面依次为不同任务上各种人工特征初始化的对比结果，其中Aggr表示邻域节点的聚合方式，Type中$\mathcal{P}$表示位置节点特征，$\mathcal{S}$表示结构节点特征。

从结果可以看出来，位置节点特征和结构节点特征都适用于特定的图节点分类数据集，因此在无属性图上，最好先对图数据集进行分析，然后选择合适的人工节点特征。