【SIGMOD2020】稀疏数据半监督学习的分解图表示，Factorized Graph Representations

节点分类是图数据管理中的一个重要问题。它通常由不同的标签传播方法来解决，这些方法从几个有标签的种子节点开始迭代地工作。对于具有类之间任意兼容性的图，这些方法主要依赖于了解必须由领域专家或启发式提供的兼容性矩阵。我们能否以一种有原则和可伸缩的方式，从一个稀疏标记的图中直接估计正确的兼容性?我们肯定地回答了这个问题，并提出了一种称为远程兼容性评估的方法，这种方法甚至可以在标记极为稀疏的图(例如，标记了10,000个节点中的1个)上工作，而这只是标记其余节点所需时间的一小部分。我们的方法首先创建多个因式图表示(大小与图无关)，然后对这些更小的图草图进行估计。我们将代数放大定义为利用算法更新方程的代数性质来放大稀疏信号的更一般的思想。我们证明了我们的估计器要比其他方法快几个数量级，并且端到端的分类精度与使用真实标准兼容性相当。这使得它对于任何现有的标签传播方法都是一个廉价的预处理步骤，并且消除了当前对启发式的依赖。