Centered kNN Graph for Semi-Supervised Learning
Centered kNN Graph for Semi-Supervised Learning
复制标题
DOI：
10.1145/3077136.3080662
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Ikumi Suzuki;Kazuo Hara
中科院分区：
文献类型：
--
作者：
Ikumi Suzuki;Kazuo Hara
图构建是基于图的半监督学习中的一个重要过程。目前，相互 kNN 图是最优选的，因为它减少了中心节点，而中心节点可能是标签传播过程中失败的原因。然而，相互 kNN 图通常非常稀疏，存在过度稀疏问题。也就是说，虽然在互kNN图中连接具有不同标签的节点的边的数量减少，但是连接具有相同标签的节点的边的数量也减少。此外，过度稀疏化会产生断开的图，这对于标签传播来说是不希望的。因此，我们提出了一种新的图构造方法，即中心kNN图，它不仅减少了中心节点，而且避免了过度稀疏问题。
Graph construction is an important process in graph-based semi-supervised learning. Presently, the mutual kNN graph is the most preferred as it reduces hub nodes which can be a cause of failure during the process of label propagation. However, the mutual kNN graph, which is usually very sparse, suffers from over sparsification problem. That is, although the number of edges connecting nodes that have different labels decreases in the mutual kNN graph, the number of edges connecting nodes that have the same labels also reduces. In addition, over sparsification can produce a disconnected graph, which is not desirable for label propagation. So we present a new graph construction method, the centered kNN graph, which not only reduces hub nodes but also avoids the over sparsification problem.