【PaperReading】Unifying Node Labels, Features, and Distances for Deep Network Completion
Integrating node attributes, features, and distance metrics into deep network reconstruction.
-
协调统一节点标签、特征和距离的三者关系，旨在通过深度学习模型完成网络数据的补充。
-
摘要
-
引言部分
-
研究背景
-
相关研究
-
本文的主要工作
- 2. 方法
-
- 2.1 问题形式化
- 2.2 LFD-NC总体架构
-
-
3. 实验
-
3.1 数据集分析
- 3.2 性能基准与评价指标
- 3.3 性能对比分析
- 3.4 标签特征对结果的影响研究
- 3.5 距离约束条件下的系统行为研究
- 3.6 消融实验的深入探讨
-
4. 结论与展望
-
参考资料
-
统一节点标签、特征和距离以实现深层网络补全
论文链接
摘要
在实际应用中，网络数据往往会存在缺失现象，在这种情况下既有节点缺失也有边缺失的问题。基于此，在无法直接观测到某些部分的情况下进行合理的推测，并对整个网络进行修复工作对于后续的任务具有重要意义。已有相关研究提供了丰富的理论基础，并在此基础上提出了许多有效的分析方法；然而这些潜在信息尚未得到充分挖掘和应用。
在本文中，作者提出了一种全新的统一深度图卷积网络模型。该模型通过整合节点标签信息、节点特征向量以及节点间距离信息来推断缺失的连接。具体而言，在模型构建阶段，作者首先基于节点标签信息构建了一个初步的估计网络拓扑结构；接着，在模型训练过程中，系统会综合考虑节点标签信息、节点特征向量以及连接距离信息来优化网络拓扑结构并更新边权重的似然估计。
通过一系列真实-world的数据集进行大规模实验，验证了在性能方面优于现有方案。
关键词：网络补全，图卷积网络，节点标签，节点特征，节点距离。
1. Introduction
1.1 背景
Network reconstruction problem definition: Network completion, referred to as NC, is defined as: given a partially observed network structure H originating from an underlying network G, the aim is to reconstruct the unobserved portion Z.
网络重构能够显著影响我们对聚合层次指标和个体节点特征的估计。
we addressed the specific network completion issue where node information was available but edges were absent in $Z. The availability of node information, including attributes such as labels, features, and distances, was a key aspect of our approach.
1.2 相关工作
- Model-Based NC（基于模型的网络补全）：KronEM
- Node-Similarity-Based NC（基于节点相似性的网络补全）：Matrix completion with decoupled transduction (MC-DT) 、joint node clustering and similarity learning (JCSL)
- Network Structure Learning（网络结构学习）：Graph neural networks (GNNs)
- Franceschi et al. 从可学习的全连接结构中采样图结构，并采用双层优化设置来同时学习 GNN 参数和结构。
- Chen et al. 提出了一种迭代方法来搜索隐藏图结构，该方法将初始图结构增强为（半）监督预测任务的最佳图。
- Yu et al. 引入了基于 GCN 的图修正模块，用于通过联合优化预测缺失边和修正边权重。
- Hao et al. 将图节点嵌入到潜在空间中，然后为未观察到的节点计算一个嵌入向量，并将属性与另一个节点的嵌入进行比较以进行链接预测。
- Shin et al. 通过利用基于节点属性相似性的 k-最近邻图，提出了 Edgeless-GNN 用于具有无边节点的属性网络嵌入。
- Franceschi, L.; Niepert, M.; Pontil, M.; He, X. Discovering discrete structures for graph neural networks learning. In Proceedings of the The 36th International Conference on Machine Learning (PMLR), Long Beach, CA, USA, 9–15 June 2019; pp. 1972–1982.
- Chen, Y.; Wu, L.; Zaki, M.J. A deep iterative learning framework for enhancing graph neural network performance. arXiv 2019, arXiv:1912.07832.
- Yu, D.; Zhang, R.; Jiang, Z.; Wu, Y.; Yang, Y. Enhanced graph convolutional networks based on structural refinements. arXiv 2020, arXiv:1911.07123.
- Hao, Y.; Cao, X.; Fang, Y.; Xie, X.; Wang, S. Inductive link prediction methods with limited node attribute information. In Proceedings of the the 29th International Joint Conference on Artificial Intelligence (IJCAI), Yokohama, Japan, 7–15 January 2021; pp. 1209–1215.
- Deep Generative Graph Models(深度生成图模型)：
- DeepNC：该方法首先采用基于RNN的生成式图模型，在由结构相似性构造的图数据集上学习边的存在概率，并结合插补策略解决缺失数据问题。与KronEM类似的是DeepNC方法不依赖节点间的边信息特性。值得注意的是该方法在训练过程中需要依赖于结构相似性的图数据，在现实应用中这往往面临挑战例如在自治系统环境下难以获取路由级网络拓扑作为隐私保护措施。
- Graphite：该框架基于GNN架构构建了一个变分自动编码器，并结合了一种迭代优化的方法以实现解码过程。
- G-GCN：本研究提出了一种统一的生成图卷积架构通过从构建好的图中采样生成序列来学习各节点的一致嵌入表示。
- 值得注意的是Graphite和G-GCN均为无边非凸优化（无边NC）任务专门设计的方法它们虽然具有较好的性能表现但目前仍未充分考虑节点标签信息及其拓扑关系这一留白空间值得进一步探索。
1.3 本文的工作
作者开发了一种网络补全技术（LFD-NC）。该技术依赖于节点标签、特征以及距离信息来进行预测。
- 首先，使用随机块模型（stochastic block model）通过节点标签构建Z的初始网络拓扑；
- 然后，采用GNN通过使用节点特征，获得Z的refined estimation；
- 其次，距离约束用于微调refined网络;
- 最后，通过迭代执行改进和微调来学习Z上的联合分布。
本文的贡献主要有：
- 将带有侧面信息的节点特征抽象为图细化问题的一种形式化处理方式；
- 提出了一种基于深度图卷积网络的新补全方法：LFD-NC。该方法通过整合节点间的拓扑关系、属性信息以及距离表示等关键要素实现了对缺失数据的有效填补。
- 通过一系列真实世界网络上的实验研究表明：LFD-NC表现出显著的性能优势。
2. 方法
2.1 问题形式化
图1展示了具有节点侧信息的网络补全问题NC（Network Completion）。具体来说，在一个包含9个顶点{v₁,v₂,…,v₉}的图中（如图1所示），每个顶点都有明确的特征描述（用特征矩阵X表示）以及对应的标签信息（用标签向量Y表示）。其中O为观测到的诱导子图G中的所有连接关系（以黑色实线表示），而Z则代表那些尚未被观测到的关键连接关系（以黑色虚线表示）。此外，在O与Z之间还存在一些未被直接观测到但可通过最短路径推断的距离信息（以红色实线标示）。通过分析这些可推断的距离信息，我们能够恢复缺失的部分Z中的潜在连接关系以及确定哪些顶点之间不存在连接。
2.2 LFD-NC总体架构
LFD-NC通过逐步优化网络拓扑结构进行建模。该系统由四个关键步骤构成：首先建立基于标签的初始拓扑结构；接着根据边的概率特性进行学习；随后对距离关系进行调整以提高准确性；最后通过进一步细化网络结构来优化模型性能。
图2展示了LFD-NC的结构图。其中用虚线框表示从学习过程中获得的边的概率，在该学习框架中的节点若拥有相同的颜色，则表明它们具有相同的标签。
在基于标签的拓扑初始化阶段中（即称为第一阶段），LFD-NC主要依赖于节点标签信息Y来估算Z对应的估计拓扑GL。然后，在边概率学习阶段中（即称为第二阶段），以GL、节点特征X以及节点标签Y为输入建立新的边概率模型P_X(u,v)，其中(u, v)∈M_Z集合中的元素对，则该模型能够成功地建立一个更优的拓扑结构G_X。值得注意的是，在构建P_X的过程中涉及到典型的链接预测问题。例如基于改进型标签传播的方法或者其他标准链接预测算法可以直接应用。
然后，遵循节点间距离约束D进行不应存在的边剪除操作。最终阶段中, 我们通过反复进行边概率学习与距离剪除相结合的方式, 不断优化并精确化目标拓扑结构\hat{G}_X.
基于node-embedding的方法中，首先在LFD-NC的前两个节点中将图G中的每个节点映射至一个低维空间；接着，构建了一个配对解码器，并在边概率学习阶段预测了图Z中的边与非边的存在情况；最终，在网络精细化阶段（即距离修剪阶段），我们对图的拓扑结构进行了优化，并根据拓扑细化后的结果相应地更新了节点嵌入。
算法伪代码如下：
时间复杂度和GCN一样。
3. 实验
3.1 数据集
我们对 LFD-NC 在八个真实网络数据集上的性能进行了测试。 这些数据集均来自真实应用场景，并包含多种复杂情况。
3.2基线和评估标准
基准模型基于五种不同的网络补全方法被选取：SBM、KronKM、MC-DT、MLP-NC和G-GCN。
- Karrer, B.; Newman, M.E.J. 网络中的随机块模型及其社区结构. 物理学报 2011, 83, 016107
- Kim, M.; Leskovec, J. 网络补全问题：从缺失节点与边重建网络结构. 在2011年SIAM数据挖掘会议论文集（Mesa, AZ, USA）中 pp. 47–58.
- Forsati, R.; Barjasteh, I.; Ross, D.; Esfahanian, A.H.; Radha, H. 利用节点间的相似性进行网络补全. 社交网络分析与采矿学 2016, 6, 1–22
- Wei, Q. 通过深度度量学习实现网络补全. 在第2020年国际大数据挖掘与信息处理会议（Qingdao, China）论文集中 pp. 012026.
- Xu, D.; Ruan, C.; Motwani, K.; Korpeoglu, E.; Kumar, S.; Achan, K. 生成式图卷积网络用于动态图分析. 在第2019年IEEE国际声学、语音与信号处理会议（Brighton, UK）论文集中 pp. 3167–3171.
将缺失边预测作为二分类任务进行建模，并通过两个关键指标——AUC值与平均精度——来评估LFD-NC的表现。在计算AUC值与平均精度时，请注意确保选取了相同数量的负样本与正样本。
3.3 性能比较
3.4 节点标签的影响分析
3.5 距离限制的影响分析
3.6 消融研究
经过四段连续的步骤进行有效应对；在此背景下，研究团队在 LFD-NC 中进行了基础性消融分析。
相较于基准版本 LFD-NC，在移除基于标签的拓扑初始化步骤时会导致 AUC 和 AP 指标的显著降低（6%）。进一步地，在去除非必要步骤时会显著影响模型性能；具体而言，在移除拓扑细化步骤时会导致 AUC 和 AP 降级最明显（11%），而在去除非必要步骤时则会带来更大的负面影响（>26%）。实验结果表明，在构建 LFD-NC 时必须包含所有提到的四个模块，并且其中最不可替代的是非必要步骤处理模块。
4. 结论与展望
我们开发了一种名为 LFD-NC 的统一深度图卷积网络（...），旨在专门用于网络补全任务。该模型基于图细化框架融合了节点标签、特征和距离信息，并在八个不同数据集上的实验结果表明，在所有测试指标上均显著优于现有的最佳基准方法。
我们的研究能够较为轻松地延伸至有向图及多重图领域。针对处理有向图的需求，在边概率学习阶段实施定向节点嵌入将是必要的步骤。在应对多重图时，我们将针对不同类型的边分别进行建模，并整合所有推断结果以达到预期效果。
我们注意到未来工作的三个可能方向。
首先，在基于节点标签Y和节点特征X的完全可获得性前提下提出了一种新的模型框架。该方法的一个创新点在于，在部分观测数据和噪声干扰存在的情况下仍能有效工作。
其次，在大规模网络数据下应用LFD-NC算法会导致显著的计算开销；因此优化算法的时间复杂度成为提升系统性能的重要方向。
最后，在原有距离约束的基础上引入了随机采样机制；这使得我们能够设计出一套更加科学的监视器部署方案从而进一步提升检测精度。