The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure

图学习方法有助于利用数据项之间的隐含关系，从而减少训练标签要求并提高任务性能。然而，确定特定学习任务的最佳图结构仍然是一个具有挑战性的研究问题。在这项工作中，我们引入了图彩票（GLT）假设——每个图都有一个极其稀疏的骨干，而且图学习算法在该子图上训练时可以达到与在完整图上训练时相当的性能。我们确定并系统研究了8个关键指标，这些指标直接影响图学习算法的性能。随后，我们定义了图结构的“中奖彩票”概念——一组极其稀疏的边缘，可以提供整个图的性能的强健近似。我们提出了一种简单高效的算法，用于在任意图中找到这些GLTs。实证结果表明，不同的图学习算法在平均度数低至5的图上的性能可以匹配甚至超过。

GLT假设的提出：每个图都有一个极度稀疏的骨干，图学习算法在该子图上的训练可以达到与完整图相当的性能。作者试图验证这个假设是否成立。

论文的关键思路是通过系统研究8个关键指标，定义“获胜彩票”来找到图结构的最优子集，从而实现在极度稀疏的子图上进行图学习。

论文提出了GLT假设，并提出了一种简单有效的算法来找到最优子集。实验结果表明，图学习算法在平均度数为5的图上的性能可以与完整图相媲美甚至超越。该论文的代码已经开源。

最近的相关研究包括：《Graph Neural Networks: A Review of Methods and Applications》、《Semi-Supervised Classification with Graph Convolutional Networks》等。