Nonlinear Higher-Order Label Spreading

Abstract

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 through nonlinear functions of higher-order structure in the graph, 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 a constrained 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 compares favorably to classical label spreading, as well as hypergraph models and graph neural networks.

Please cite this paper as:

@inproceedings{tudisco2021nonlinear,
author = {Tudisco, Francesco and Benson, Austin R. and Prokopchik, Konstantin},
title = {Nonlinear Higher-Order Label Spreading},
year = {2021},
booktitle = {Proceedings of the Web Conference 2021},
pages = {2402--2413},
numpages = {12}
}

Keywords: semi-supervised learning networks Perron-Frobenius theory nonnegative tensors spectral clustering label spreading label propagation hypergraphs hypergraph Laplacian higher-order networks