共计 3599 个字符，预计需要花费 9 分钟才能阅读完成。
大多数图神经网络通常在所有节点都可用的特色假如下运行。然而在事实世界的中，特色通常只有局部可用（例如，在社交网络中，只有一小部分用户能够晓得年龄和性别）。本文种展现的特色流传是一种用于解决图机器学习应用程序中缺失的特色的无效且可扩大的办法。它很简略，但成果出奇地好。
图神经网络 (GNN) 模型通常假如每个节点都有一个残缺的特征向量。以一个 2 层 GCN 模型 [1] 为例，它具备以下模式：
Z = A σ(AXW₁) W₂
该模型的两个输出是编码图构造（归一化的）邻接矩阵 A 和作为行的节点特色的特色矩阵 X，输入为节点嵌入 Z。GCN 的每一层执行节点特色变换（参数化可学习矩阵 W₁ 和 W₂），而后将转换后的特征向量流传到相邻节点。这外面一个重要的概念是：GCN 假如 X 中的所有条目都被察看到。
然而在事实世界的场景中，常常会看到一些节点特色可能会缺失。例如，年龄、性别等人口统计信息可能仅对一小部分社交网络用户可用，而内容特色通常仅对最沉闷的用户出现。例如在举荐零碎中并非所有产品都有与之相干的残缺形容，这使得状况变得更加重大，随着人们对数字隐衷的意识一直进步，越来越多的数据只有在用户明确批准的状况下能力取得。
依据下面的形容，特色矩阵都有缺失值的，大多数现有的 GNN 模型都不能间接利用。最近的几项工作派生了可能解决缺失特色的 GNN 模型（例如 [2-3]），然而这些模型在缺失特色率很高（>90%）的状况下受到影响，并且不能扩大到具备超过几百万条边的图.
在 Maria Gorinova、Ben Chamberlain (Twitter)、Henry Kenlay 和 Xiaowen Dong (Oxford) 合着的一篇新论文 [4] 中，提出了特色流传 (FP) [4] 作为一种简略但高效且令人诧异的无效解决方案。简而言之，FP 通过在图上流传已知特色来重构缺失的特色。而后能够将重建的特色输出任何 GNN 以解决上游工作，例如节点分类或链接预测。
特色流传框架。输出是短少节点特色的图（左）。在初始步骤中，特色流传通过迭代地扩散图中的已知特色来重构缺失的特色（中）。随后，图和重建的节点特色被输出到上游 GNN 模型中，而后产生预测（右）。
流传步骤非常简单：首先，未知特色用任意值初始化 [5]。通过利用（归一化的）邻接矩阵来流传特色，而后将已知特色重置为其实在值。咱们反复这两个操作，直到特征向量收敛 [6]。
特色流传是一种简略且令人诧异的弱小办法，用于在短少特色的图上进行学习。特色的每个坐标都被独自解决（x 示意 X 的一列）。
FP 能够从数据同质性（“平滑性”）的假如中推导进去，即街坊往往具备类似的特征向量。同质性的程度能够应用 Dirichlet energy 来量化，这是一种测量节点特色与其街坊平均值之间的平方差的二次模式。Dirichlet energy[7] 的梯度流是图热扩散方程，以已知特色作为边界条件。FP 是应用具备单位步长的显式前向 Euler 计划作为该扩散方程的离散化取得的 [8]。
动画展现了随着特色流传的更多迭代利用而标量节点特色的演变示例。未知特色被初始化为零，但很快收敛到使给定图上的 Dirichlet energy 最小化的值。
特色流传与标签流传（LP）[9] 类似。要害区别在于 LP 是一种与特色无关的办法，它通过在图中流传已知标签来间接预测每个节点的类，而 FP 用于首先重建缺失的节点特色，而后将其馈送到上游 GNN。这使得 FP 可能利用察看到的特色，并在所有基准测试中都优于 LP。在实践中常常产生带标签的节点集和具有特征的节点集不肯定齐全重叠，因而这两种办法并不总是能够间接比拟。
论文中应用七个规范节点分类基准对 FP 进行了宽泛的试验验证，其中随机删除了可变局部的节点特色（独立于每个通道）。FP 后跟一个 2 层 GCN 在重建特色上的体现显著优于简略的基线以及最新的最先进的办法 [2-3]。
FP 在特色缺失率高 (>90%) 的状况下尤为突出，而所有其余办法往往会受到影响。例如，即便失落了 99% 的特色，与所有特色都存在的雷同模型相比，FP 均匀仅损失约 4% 的绝对准确度。
Cora 数据集上不同特色缺失率的节点分类准确度（从 0% 是大多数 GNN 的标准状态到 99% 的极其状况）。
FP 的另一个要害特点是它的可扩展性：其余办法无奈扩大到具备几百万条边的图之外，但 FP 能够扩大到十亿条边的图。作者用了不到一小时的工夫在外部 Twitter 图表上运行它，应用单台机器大概有 10 亿个节点和 100 亿条边。
FP+GCN 和最新最先进的办法 GCNMF 和 PaGNN [2-3] 的运行工夫（以秒为单位）。FP+GCN 比其余两种办法快 3 倍。GCNMF 在 OGBN-Arxiv 上呈现内存不足 (OOM)，而 GCNMF 和 PaGNN 在 OGBN-Products（约 123M 边）上呈现 OOM，其中 FP 的重建局部（无需训练上游模型）仅需约 10 秒。
FP 的以后限度之一是它在 heterophilic graphs 上成果不佳，即街坊具备不同特色的图。这并不奇怪，因为 FP 源自同质假如（通过扩散方程最小化 Dirichlet energy）。FP 假如不同的特色通道是不相干的，这在现实生活中很少见。然而能够通过代替更简单的扩散机制，同时满足这两个限度。
当 99% 的特色缺失时，具备各种同质性程度的合成图上的节点分类准确度（0 是极度异质性，1 是极度同质性）。尽管在高度同质性设置中 FP 的体现简直与具备残缺特色的状况一样好，但在低同质性设置中，两者之间的差距很大，并且 FP 的性能好转到一个简略的基线，其中缺失的特色被替换为 零。
只管在理论利用中无处不在，但在短少节点特色的图上学习是一个简直未被摸索的钻研畛域。特色流传模型是进步在短少节点特色的图上学习能力的重要一步，它还提出了对于在这种状况下学习的实践能力的粗浅问题。FP 的简略性和可扩展性，以及与更简单的办法相比的惊人的好后果，即便在极其缺失的特色状态下，也使其成为大规模工业利用的良好候选者。
援用
[1] T. Kipf and M. Welling, Semi-Supervised Classification with Graph Convolutional Networks (2017), ICLR.
[2] H. Taguchi et al., Graph Convolutional Networks for Graphs Containing Missing Features (2020), Future Generation Computer Systems.
[3] X. Chen et al., Learning on Attribute-Missing Graphs (2020), arXiv:2011.01623
[4] E. Rossi et al., On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Features (2021), arXiv:2111.12128
[5] We show that the algorithm converges to the same solution, regardless of the initialisation of the unknown values. However, a different initialisation may lead to a different number of iterations necessary to converge. In our experiments we initialise the unknown values to zero.
[6] We found ~40 iterations to be sufficient for convergence on all datasets we experimented with.
[7] A gradient flow can be seen as a continuous analogy of gradient descent in variational problems. It arises from the optimality conditions (known in the calculus of variations as Euler-Lagrange equations) of a functional.
[8] B. Chamberlain et al., GRAND: Graph Neural Diffusion (2021), ICML. See also the accompanying blog post.
[9] X. Zhu and Z. Ghahramani, Learning from labeled and unlabeled data with label propagation (2002), Technical Report.
https://www.overfit.cn/post/f6b25ef08a94498f905c5ce69bf13f4d
作者：Michael Bronstein