Nonlinear Higher-Order Label Spreading
This work addresses the limitation of linear models in label spreading for semi-supervised learning with graph data, offering a novel nonlinear approach that is incremental in improving accuracy and efficiency.
The paper tackled the problem of linear label spreading in semi-supervised learning by introducing nonlinearity through higher-order graph structures like triangles, proving convergence to a global solution and showing favorable performance on various datasets compared to classical methods, hypergraph models, and graph neural networks.
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.