Abstract:

In essence, existing graph based semi-supervised learning methods belong to label propagation ones by simulating various propagation mechanics. In this study, different from the existing propagation mechanics, it attempts to exploit a novel elastic-force based propagation method to realize semi-supervised learning. The basic idea is to imagine that each node in a graph accepts elastic forces in an elastic coefficient from its neighbors and transmits elastic forces to its neighbors in another elastic coefficient. As a result, the difference between two types of elastic forces measures the propagation quantity of each node. Based on this novel idea, this paper derives the corresponding update equations of all nodes in the graph, which will further induce an analytical solution by expressing these equations in a matrix. In other words, the proposed method has its reliable foundation from the philosophy of physics. Besides, it also demonstrates the rationale of the proposed method from the perspective of optimizing the corresponding objective function, which guarantees the convergence of the proposed method. The extensive experimental results verify the effectiveness of the proposed method in semi-supervised learning.

Key words: semi-supervised learning, label propagation, elastic-force, convergence

摘要：

现有的基于图的半监督学习方法在本质上是属于模拟各种传播机制的标签传播方法。与现有的传播机制不同，尝试采用一种新的基于弹力的传播方法来实现半监督学习。基本思想是假设图中的每个节点以一定的弹性系数都接受其相邻节点的弹性力，并以另一个弹性系数将弹性力传递给相邻的节点。因此，两种类型的弹性力之间的差异可以度量每个节点的传播量。在此想法基础上，推导出图中所有节点的更新方程，并将这些方程表示为矩阵形式，进一步推导出其解析解。换句话说，该方法具有可靠的物理学基础。并从优化相应的目标函数角度出发，论证了该方法的基本原理，从而保证了该方法的收敛性。大量的实验结果验证了该方法在半监督学习中的有效性。

关键词: 半监督学习, 标签传播, 弹力理论, 收敛