↑↑↑关注后"星标"炼丹笔记
炼丹笔记·干货
图神经网络
ICLR (International Conference on Learning Representation) 国际表征学习大会是公认的深度学习领域国际顶级会议之一，关注有关深度学习各个方面的前沿研究，在人工智能、统计和数据科学领域以及机器视觉、语音识别、文本理解等重要应用领域中发布了众多极其有影响力的论文。
PKU-DAIR 实验室研究成果《Information Gain Propagation: A New Way To Graph Active Learning With Soft Labels》已被 ICLR 2022 录用并对外发布。论文提出，图神经网络在图上的各种任务都十分有效，但它的性能高度依赖于大量的有标签节点，而打标签通常需要大量的人力。因此有研究提出了基于图神经网络的主动学习方法，通过选择最有价值的节点进行标记来提高标记效率。现有方法假设预言机（oracle，标签的提供者）可以正确分类所有选定的节点，因此只关注节点选择。然而，这种精确的标记任务成本很高，尤其是当分类数量巨大、超出个人专家的领域时。
该论文提出了图神经网络上主动学习的软标签方法，有两个关键创新点：（1）领域专家只判断预测标签的正确性（二元问题）而不是识别确切的类别（多类问题）的轻松查询；（2）提出了轻松查询下软标签主动学习的信息增益传播衡量标准。此外，对公共数据集的实证研究表明，该论文方法的在准确性和标记成本方面明显优于最先进的基于图神经网络的主动学习方法。
论文标题：
Information Gain Propagation: A New Way To Graph Active Learning With Soft Labels
收录会议：
ICLR 2022
论文链接：
https://openreview.net/forum?id=USC0-nvGPK
代码链接：
https://github.com/PKU-DAIR/IGP
问题背景
传统的主动学习策略往往假定负责提供标签的一方具备完全的知识，但是在一些专业领域中，专家作为标签的提供者，往往只熟悉自己专精的领域，能判断需要标签的样本是否属于自己的专业，却无法指出如果不属于自身专业则应该属于其他哪个专业，换句话说，提供标签的专家只能回答“Yes or No”而不是“Which Class”。
举个具体的例子就是，在 arxiv 的论文分类中，金融的细分分类有计算金融、数学金融等，那么计算金融的专家只能知道某篇论文是否属于计算金融，但判定不出它具体的分类。这时，专家给出的标签就只能是软标签而不是传统的 one-hot 硬标签。如何设计在软标签下的图主动学习策略是该论文要解决的问题。
▲ 图1. 硬标签和软标签以及对应oracle的区别
相关工作
2.1 图神经网络（GNN）
与训练数据独立同分布的图像、文本或表格数据不同，图数据样本通过图中的边连接而互相影响。所以图神经网络通过聚合邻居的节点嵌入或特征以增强它们沿边的嵌入，以利用图数据特定的结构信息。图神经网络有许多变种，比如 GCN [1]、MVGRL [2] 等。
2.2 主动学习（AL）
主动学习通过更好的样本点选择来提高模型的效果和效率。常见的主动学习方法有如下几种：不确定性抽样方法通过考虑信息量选择模型预测最不确定的节点；Query-by-Committee [3] 方法训练一个模型委员会，并根据模型不同意的程度选择样本；基于密度、聚类和多样性的方法选取选择最具代表性的样本。此外，针对多标签分类问题和类不平衡问题也有相应的方法。
IGP方法
IGP 是第一个基于图的考虑了轻松查询和软标签的主动学习框架，可以在任何图神经网络模型上运行。该方法首先测量了选择单个节点的信息增益，然后通过估计图传播的影响大小并将其与信息增益相结合，将单个节点的信息增益扩展到全图，最后选择可以最大化信息增益传播的节点。整个框架的图示如下：
▲ 图2. IGP框架
3.1 信息增益
与之前的标注方式要求 oracle 直接提供标注不同，IGP 中的 oracle 只需要判断模型的预测是否正确即可。而正确和不正确的预测都将提供信息增益使节点标签的不确定性会降低，从而增强标签监督，如果丢弃不正确的预测，就会损失这一部分的信息。我们通过交叉熵来计算每一种可能的信息增益并将它们作加权平均。
▲ 图3. 信息增益公式
3.2 传播影响力估计
每个新标注的节点都会将其标签信息传播给 k 层图神经网络中的 k 跳邻居，并相应地影响这些节点的标签分布。由于节点对其不同邻居的影响可能是多种多样的，我们通过计算节点 i 的输入标签的变化对 k 步传播后节点 j 的传播标签的影响来衡量它，公式如下图：
▲ 图4. 影响力公式
3.3 全图信息增益
对于 k 层 GNN，一个节点的监督信号可以传播到其 k 跳邻域节点，然后影响这些邻域的标签分布。因此，在节点选择过程中只考虑节点自身的信息增益是不合适的。于是我们扩展了图 3 中定义的单个节点的信息增益到图中它的 k-hop 邻居，具体公式如下：
▲ 图5. 全图信息增益公式
3.4 最大化全图信息增益
在确定了每个点对于全图的信息增益后，我们在每一批选点中，都优先挑选信息增益最大的点来给 oracle 打标签，并将得到的软标签交给模型进行下一步的训练迭代，直至用完所有的打标签预算。具体优化目标的公式如下：
▲ 图6. 选点目标公式
实验
4.1 数据集与baseline
数据集使用了 3 个论文引用数据集：Cora、Citseer 和 PubMed。一个社区数据集 Reddit。一个 OGB 公开数据集 ogbn-arxiv，具体细节信息如表格所示。而对比的 baseline 里我们选择了 GRAIN [4] 和 ALG [5] 等最新的在图上做主动学习的方法。
▲ 表1. 数据集详细信息
4.2 端到端实验结果
我们将选点的预算设置为节点类目数量的二十倍，所得的结果如下，可以看出 IGP 显著优于其他方法。
▲ 表2. 端到端实验结果
4.3 选点预算实验结果
我们测试了所有方法随着选点预算增加时的准确率，结果如图，证明 IGP 方法在任何选点预算下都优于其他方法。
▲ 图7. 选点预算实验结果
4.4 可解释性实验
我们将有标签的点可视化投影至二维平面中，并用不同颜色分开标注了硬标签和软标签，从图中可以看出，相比于其他方法，IGP 所获得的硬标签和软标签都够多，这解释了 IGP 的有效性。
▲ 图8. 可解释性实验结果
总结
该论文提出了 IGP 方法，这是第一个考虑软标签情况下基于图神经网络的主动学习方法，具体来说，IGP 结合领域专家和图神经网络模型，在有限预算的情况下详尽地标记节点。IGP 允许使用轻松的查询，即领域专家（oracle）只判断预测标签的正确性而不是准确的分类，并且通过最大化信息增益传播来进行选点。对与真实世界数据集的实证研究表明，IGP 方法在很大程度上优于其他方法，尤其是在类数量很大的专家领域情况下。
参考文献
[1] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017b.
[2] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning on graphs. In International Conference on Machine Learning, pp. 4116–4126. PMLR, 2020.
[3] Robert Burbidge, Jem J Rowland, and Ross D King. Active learning for regression based on query by committee. In International conference on intelligent data engineering and automated learning, pp. 209–218. Springer, 2007.
[4] Wentao Zhang, Zhi Yang, Yexin Wang, Yu Shen, Yang Li, Liang Wang, and Bin Cui. Grain: Improving data efficiency of graph neural networks via diversified influence maximization. Proc. VLDB Endow., 14(11):2473–2482, 2021b.
[5] Wentao Zhang, Yu Shen, Yang Li, Lei Chen, Zhi Yang, and Bin Cui. ALG: fast and accurate active learning framework for graph convolutional networks. In SIGMOD ’21: International Conference on Management of Data, Virtual Event, China, June 20-25, 2021, pp. 2366–2374, 2021a.
编辑：王菁
校对：林亦霖
