Nonlinear Higher-Order Label Spreading
Nonlinear Higher-Order Label Spreading
复制标题
DOI：
10.1145/3442381.3450035
复制
发表时间：
2020-06
期刊：
影响因子：
--
通讯作者：
Francesco Tudisco;Austin R. Benson;Konstantin Prokopchik
中科院分区：
文献类型：
--
作者：
Francesco Tudisco;Austin R. Benson;Konstantin Prokopchik
标签扩散是利用点云或网络数据进行半监督学习的一种通用技术，可以被解释为图上标签的扩散。虽然标签传播有许多变体，但几乎所有的都是线性模型，其中进入节点的信息是来自相邻节点的信息的加权和。这里，我们通过涉及高阶网络结构的非线性函数，即图中的三角形，将非线性添加到标记扩散中。对于一类广泛的非线性函数，我们证明了我们的非线性高阶标签扩展算法收敛于一个可解释的半监督损失函数的整体解。我们在不同的点云和网络数据集上展示了我们的方法的有效性和有效性，其中非线性高阶模型的性能优于经典的标签扩散、超图聚类和图神经网络。
Label spreading is a general technique for semi-supervised learning with point cloud or network data, which can be interpreted as a diffusion of labels on a graph. While there are many variants of label spreading, nearly all of them are linear models, where the incoming information to a node is a weighted sum of information from neighboring nodes. Here, we add nonlinearity to label spreading via nonlinear functions involving higher-order network structure, namely triangles in the graph. For a broad class of nonlinear functions, we prove convergence of our nonlinear higher-order label spreading algorithm to the global solution of an interpretable semi-supervised loss function. We demonstrate the efficiency and efficacy of our approach on a variety of point cloud and network datasets, where the nonlinear higher-order model outperforms classical label spreading, hypergraph clustering, and graph neural networks.