基于网络控制理论与排序编码的图神经网络特征构造方法及其在社会网络分类中的应用

《IEEE Open Journal of Control Systems》：Feature Construction Using Network Control Theory and Rank Encoding for Graph Machine Learning

本研究针对社会网络中节点特征缺失导致图神经网络（GNN）性能受限的问题，提出结合平均可控性（Average Controllability）等网络控制理论（NCT）指标与新型排序编码方法，构建表达性节点特征。通过六种GNN模型在四个社会网络数据集上的实验验证，该方法显著提升分类性能（如GraphSAGE在GitHub Stargazers数据集上ROC AUC从68.7%提升至73.9%），为特征稀缺场景下的图学习提供了新思路。

　　

在当今数据驱动的社会中，社会网络分析已成为理解信息传播、群体行为和社会动态的关键工具。图神经网络（GNN）作为处理图结构数据的强大工具，通过学习节点及其邻居之间的复杂关系，在社交网络分类、推荐系统和生物信息学等领域展现出巨大潜力。然而，GNN的性能高度依赖于节点特征的表达性。在实际应用中，尤其是在社会网络中，节点特征往往由于隐私限制或固有属性的缺失而不可用，这严重限制了GNN的性能。传统的解决方案，如使用节点度数的独热编码，虽然简单，但往往产生高维稀疏表示，特别是在幂律网络中，导致计算复杂度增加和性能下降。此外，独热编码仅限于离散值，无法很好地泛化到连续值的结构度量。这些挑战凸显了需要一种更表达性强且计算高效的特征初始化方案。

为了解决这一局限性，本研究提出利用平均可控性（Average Controllability）——网络控制理论（NCT）中的一个关键度量——作为有意义的节点特征。平均可控性量化了节点在响应外部输入时影响系统整体动态的能力，有效刻画了其在网络中信息流治理的角色。该度量提供了控制能量如何在网络中传播的宝贵见解，并为特征初始化提供了原则性基础。与仅依赖频谱信息的拉普拉斯位置编码不同，平均可控性捕捉了线性动态影响下的可达性。它使得构建的节点特征不仅反映拓扑结构，还反映节点对网络状态施加控制的潜力。这可能包括节点促进信息扩散或重新配置网络以实现期望结果的能力。包含此类信息对于建模任务尤为重要，如在之前的研究中所示，控制感知特征显著增强了学习性能。

除了平均可控性，网络科学还提供了一系列中心性度量，捕捉图的关键结构特征。紧密度中心性识别由于与其他节点接近而能有效传播影响的节点。特征向量中心性强调连接到高度有影响力邻居的节点，而介数中心性突出经常介导最短路径的桥接节点，强调其在控制信息流中的作用。这些度量封装了基本的结构属性，已在网络系统建模中被广泛采用。

通过将平均可控性与这些中心性度量结合，本研究引入了一种原则性的节点特征构建方法，增强了GNN的表达能力，特别是在传统节点特征不可用的场景中。基于之前会议工作的基础，本研究系统评估了控制理论度量在增强GNN性能方面的有效性，并引入了一种新颖的编码方案将这些度量集成到学习管道中。本研究在三个关键方面扩展了会议论文的评估：首先，它通过改变分箱数量检查了排序编码的影响，这是特征维度的关键参数；其次，它将提出的基于排序的编码方案扩展到额外的中心性度量，包括度数、紧密度中心性、介数中心性和特征向量中心性以及平均可控性；第三，它通过纳入两个额外的社会网络数据集（Twitch Ego Net和Deezer Ego Net）扩展了实验设置。

为了验证所提方法的有效性，研究团队进行了广泛的数值评估。他们使用了四个广泛使用的社会网络基准数据集：Reddit Threads、GitHub Stargazers、Twitch Egos和Deezer Egos。这些数据集涵盖了不同类型的社交互动，如讨论线程、开发者星标网络和用户好友网络，分类任务包括区分讨论与非讨论线程、识别仓库类型、预测用户游戏单多性和性别。数据集统计显示，图的大小、密度和直径各不相同，提供了多样化的测试平台。

研究比较了六种著名的GNN模型：k-GNN（GraphConv）、GraphSAGE、GCN、Transformer Convolution（UniMP）、Residual Gated Graph Convolution（ResGatedGCN）和Graph Attention Network（GAT）。所有模型采用三层GNN结构，每层64个隐藏单元，之后应用排序聚合（Sort Aggregation），接着是两层一维卷积和最大池化，最后是一个具有两层32个隐藏神经元的多层感知机。模型使用10折交叉验证评估，训练100轮，学习率设为10^-4，权重衰减为5×10^-2。

在特征构造方面，研究提出了两种主要方法：一是直接使用网络控制理论度量（包括平均可控性、紧密度中心性、介数中心性和特征向量中心性）作为节点特征，记为NCT-EFA；二是新型的排序编码方法，它将任何图论度量（如平均可控性）转换为结构化的固定维节点特征向量。排序编码通过基于直方图的策略与反向排名映射结合，将标量节点级度量值映射到对应的直方图分箱，生成独热编码特征向量。分箱数量k和值范围控制编码的分辨率和稀疏性。例如，给定平均可控性向量，构造一个具有k个分箱的直方图覆盖所有值，每个节点根据其值落入的分箱分配一个独热向量。这种方法本质上是类型无关的：它可以编码任何标量节点属性，包括连续度量（如平均可控性）或离散度量（如节点度数），而不要求特征维度d与数据集中的最大值匹配。

实验结果令人鼓舞。首先，在完整特征集（NCT-EFA）与独热度数编码的对比中，NCT-EFA在大多数数据集和架构上表现出优越性能，特别是在GitHub Stargazers数据集上提升显著。例如，使用k-GNN时ROC AUC提高了6.54%，GraphSAGE提高了7.66%，ResGatedGCN提高了5.53%。在Reddit Threads上，虽然提升相对温和，但NCT-EFA一致优于度数编码，提升范围在0.15%到0.90%之间，表明该方法在不过度改变数据集固有分类属性的情况下增强了特征表示。然而，在Deezer Egos数据集上，度数编码在大多数情况下优于NCT-EFA，ROC AUC下降高达3.47%，这可能源于性别预测任务中基于度数的信息比NCT-EFA提供的特征转换更具决定性。在Twitch Egos上，NCT-EFA在所有架构上一致优于度数编码，提升范围在0.11%到0.59%之间，表明该方法能有效捕捉用户互动模式。

其次，在排序编码实验中，比较了仅平均可控性编码（AC）和多个中心性度量结合编码（Concat）与度数编码。结果显示，在节点特征对分类至关重要的数据集上，AC和Concat编码一致优于度数编码。在GitHub Stargazers上，仅AC就带来显著增益，GCN的ROC AUC提升4.19%，GraphSAGE提升5.78%，UniMP提升5.94%。而Concat编码进一步提升了性能，分别达到5.66%、6.21%和6.83%的提升，表明虽然平均可控性单独提供了有价值的结构信息，但纳入额外中心性度量能细化特征表示，带来更强的分类性能。在Reddit Threads上，提升相对温和但仍一致，AC编码提升0.15%到0.90%，Concat编码提供略高的增益，强化了结构排序能在不剧烈改变数据集固有分类属性的情况下增强特征表示的观点。在Deezer Egos上，度数编码仍是更优方法，但所有编码策略的整体性能接近随机（ROC AUC约51%到55%），表明该社交网络的性别预测本质具挑战性，可能源于网络拓扑中性别信号弱或嘈杂。度数编码的 modest 提升暗示绝对度数可能捕捉了弱的人口统计相关性（如用户活动水平或连接倾向的差异），但所有方法较低判别力指向数据中缺乏用于性别预测任务的信息性结构。

排序编码中还比较了不同分箱大小（k=10,20,30）对模型性能的影响。结果显示模型性能随k值和数据集不同而变化，没有单一配置一致优于其他。但在Reddit数据集上，k=30在6例中5例取得最佳结果；在GitHub Stargazers上，k=30在6例中4例最佳；在其他数据集上，不同k值对整体模型性能影响差异不显著。

本研究的主要技术方法包括：利用网络控制理论计算平均可控性等节点级度量；提出排序编码方法将标量图度量转换为固定维特征向量；在六种GNN架构上基于四个社会网络数据集（Reddit Threads、GitHub Stargazers、Twitch Egos、Deezer Egos）进行系统评估；采用10折交叉验证和ROC AUC作为评价指标。

研究结果部分通过多个图表展示了不同特征构造方法在不同GNN模型和数据集上的性能对比。例如，表2显示了NCT-EFA相对度数编码的全面优势，尤其在GitHub Stargazers数据集上提升显著。表3进一步比较了度数编码、平均可控性编码和结合编码的效果，凸显了排序编码的优越性。图3和图4展示了不同分箱大小对排序编码性能的影响，表明k=30在多数情况下表现最佳。

研究的结论与讨论部分强调，通过将平均可控性等图论度量作为节点特征并结合新型排序编码方案，能显著提升GNN在社会网络分类任务中的性能。该方法尤其适用于节点特征稀缺的场景，为图机器学习提供了更表达性强且计算高效的特征初始化方法。未来研究方向包括整合多种可控性度量进一步丰富节点特征、将可控性信息直接嵌入GNN消息传递机制、以及利用可控性度量构建表达性图级嵌入等。尽管可控性计算存在O(n³)复杂度，但通过并行化在中等规模图上具可行性，未来可通过低秩近似等方法加速。总体而言，该研究为网络控制理论与图机器学习的融合奠定了坚实基础，推动了更表达性强、原则性的图学习方法发展。