当前位置: 首页 > 科技观察

使用图机器学习的特征传播重建缺失数据

时间:2023-03-13 07:49:52 科技观察

特征传播,如本文所示,是处理图机器学习应用程序中缺失特征的有效且可扩展的方法。它很简单,但效果出奇的好。图神经网络(GNN)模型通常假设每个节点都有一个完整的特征向量。以一个2层的GCN模型[1]为例,它有如下形式:Z=Aσ(AXW?)W?模型的两个输入是编码图结构(归一化)邻接矩阵A和节点特征作为行的特征矩阵X,输出为节点嵌入Z。GCN的每一层都进行节点特征变换(参数化可学习矩阵W?和W?),然后将变换后的特征向量传播到相邻节点。这里的一个重要概念是:GCN假设X中的所有条目都被观察到。但在现实场景中,经常会看到一些节点特征可能缺失。例如,年龄、性别等人口统计信息可能只对一小部分社交网络用户可用,而内容特征通常只呈现给最活跃的用户。例如,在推荐系统中,并非所有产品都有与之关联的完整描述,这使得情况变得更加严重,因为数字隐私意识不断增强,越来越多的数据只有在用户明确同意的情况下才能获得。根据上面的描述,特征矩阵存在缺失值,现有的大部分GNN模型都不能直接应用。最近的几项工作衍生出了能够处理缺失特征的GNN模型(例如[2-3]),但这些模型的特征缺失率很高(>90%),并且不能扩展到具有超过几百万个图的模型边缘。在MariaGorinova、BenChamberlain(推特)、HenryKenlay和XiaowenDong(牛津大学)的一篇新论文[4]中,特征传播(FP)[4]被提议作为一种简单但高效且效果??惊人的解决方案。简而言之,FP通过在图上传播已知特征来重建缺失的特征。然后可以将重构的特征输入到任何GNN中,以解决节点分类或链路预测等下游任务。特征传播框架。输入是缺少节点特征的图(左)。在初始步骤中,特征传播通过迭代扩散图中的已知特征来重建缺失的特征(中间)。随后,图形和重构的节点特征被输入下游GNN模型,然后生成预测(右)。传播步骤非常简单:首先,用任意值初始化未知特征[5]。通过应用(归一化的)邻接矩阵传播特征,然后将已知特征重置为其真实值。我们重复这两个操作,直到特征向量收敛[6]。特征传播是一种简单而强大的方法,用于学习缺少特征的图。特征的每个坐标都被单独处理(x表示X的列)。FP可以从数据同质性(“平滑度”)的假设中推导出来,即邻居往往具有相似的特征向量。同质性水平可以使用Dirichlet能量进行量化,Dirichlet能量是一种二次形式,用于测量节点特征与其邻居的均值之间的平方差。Dirichlet能量的梯度流[7]是一个以已知特征为边界条件的图形热扩散方程。FP是使用具有单位步长的显式正向欧拉方案作为该扩散方程的离散化获得的[8]。动画展示了标量节点特征演变为特征传播的更多迭代应用的示例。未知特征被初始化为零,但很快收敛到最小化给定图上Dirichlet能量的值。特征传播类似于标签传播(LP)[9]。关键区别在于LP是一种独立于特征的方法,它通过传播图中的已知标签直接预测每个节点的类别,而FP用于首先重建缺失的节点特征,然后将其馈送到下游GNN。这使FP能够利用观察到的特征并在所有基准测试中优于LP。实践中经常会出现标记节点集和特征节点集不一定完全重叠的情况,因此这两种方法并不总是可以直接比较的。在本文中,FP使用七个标准节点分类基准进行了广泛的实验验证,其中随机删除了节点特征的可变部分(独立于每个通道)。FP后跟一个2层GCN显着优于简单的基线以及最近最先进的重建特征方法[2-3]。FP在高(>90%)缺失特征的情况下尤为突出,而所有其他方法往往会受到影响。例如,即使有99%的特征缺失,与所有特征都存在的相同模型相比,FP平均只损失大约4%的相对准确度。Cora数据集上不同特征缺失率的节点分类准确率(从大多数GNN的标准0%到极端情况的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当前的局限性之一是它不能很好地处理异嗜图,即邻居具有不同特征的图。这并不奇怪,因为FP源自同质性假设(通过扩散方程最小化Dirichlet能量)。FP假设不同的特征通道是不相关的,这在现实生活中是很少见的。但是可以通过替换更复杂的扩散机制来满足这两个约束。当99%的特征缺失时(0是极端异质性,1是极端同质性),具有不同同质性水平的合成图的节点分类精度。虽然在高同质性设置中FP的表现几乎与完整特征一样好,但在低同质性设置中两者之间的差距很大并且FP的性能退化为简单的基线,其中缺失的特征被零替换。尽管在实际应用中无处不在,但在缺乏节点特征的图上进行学习仍然是一个鲜为人知的研究领域。特征传播模型是朝着提高在缺乏节点特征的图上学习的能力迈出的重要一步,它们也对这种情况下的学习理论能力提出了深刻的问题。FP的简单性和可扩展性,以及与更复杂的方法相比令人惊讶的好结果,即使在极端缺失特征的状态下,也使其成为大规模工业应用的良好候选者。