OpenWGL: Open-World Graph Learning
OpenWGL: Open-World Graph Learning
复制标题
DOI：
10.1109/icdm50108.2020.00077
复制
发表时间：
2020-11
期刊：
影响因子：
--
通讯作者：
Man Wu;Shirui Pan;Xingquan Zhu
中科院分区：
文献类型：
--
作者：
Man Wu;Shirui Pan;Xingquan Zhu
在传统的图学习任务中，例如节点分类，学习是在一个封闭世界的设定下进行的，其中类别数量及其训练样本被提供以帮助训练模型，学习目标是将未标记的节点正确分类到已知的类别中。实际上，由于标记能力有限以及网络的动态演变，网络中的一些节点可能不属于任何现有的/已见过的类别，因此无法被封闭世界学习算法正确分类。在本文中，我们提出了一种新的开放世界图学习范式，其中学习目标不仅是将属于已见过类别的节点分类到正确的组中，而且要将不属于现有类别的节点分类到一个未见过的类别中。开放世界图学习的核心挑战在于：（1）未见过的类别没有标记样本，并且可能以与现有已见过类别不同的任意形式存在；（2）图特征学习和预测都应该区分一个节点可能属于现有/已见过的类别还是未见过的类别。为了应对这些挑战，我们提出了一种不确定节点表示学习方法，使用受约束的变分图自动编码器网络，其中标签损失和类别不确定性损失约束被用于确保节点表示学习对未见过的类别敏感。因此，节点嵌入特征由分布表示，而不是确定性的特征向量。通过使用采样过程生成多个版本的特征向量，我们能够测试一个节点属于已见过类别的确定性，并自动确定一个阈值，将不属于已见过类别的节点作为未见过类别节点拒绝。在真实世界网络上的实验证明了该算法的性能，并与基线方法进行了比较。案例研究和消融分析也展示了我们针对开放世界图学习设计的合理性。
In traditional graph learning tasks, such as node classification, learning is carried out in a closed-world setting where the number of classes and their training samples are provided to help train models, and the learning goal is to correctly classify unlabeled nodes into classes already known. In reality, due to limited labeling capability and dynamic evolving of networks, some nodes in the networks may not belong to any existing/seen classes, and therefore cannot be correctly classified by closed-world learning algorithms. In this paper, we propose a new open-world graph learning paradigm, where the learning goal is to not only classify nodes belonging to seen classes into correct groups, but also classify nodes not belonging to existing classes to an unseen class. The essential challenge of the open-world graph learning is that (1) unseen class has no labeled samples, and may exist in an arbitrary form different from existing seen classes; and (2) both graph feature learning and prediction should differentiate whether a node may belong to an existing/seen class or an unseen class. To tackle the challenges, we propose an uncertain node representation learning approach, using constrained variational graph autoencoder networks, where the label loss and class uncertainty loss constraints are used to ensure that the node representation learning are sensitive to unseen class. As a result, node embedding features are denoted by distributions, instead of deterministic feature vectors. By using a sampling process to generate multiple versions of feature vectors, we are able to test the certainty of a node belonging to seen classes, and automatically determine a threshold to reject nodes not belonging to seen classes as unseen class nodes. Experiments on real-world networks demonstrate the algorithm performance, comparing to baselines. Case studies and ablation analysis also show the rationale of our design for open-world graph learning.