# Nonlinear Higher-Order Label Spreading

Francesco Tudisco,
Austin R. Benson,
Konstantin Prokopchik,

**In: Proceedings of The Web Conference**,
2402--2413
(2021)

### 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}
}
```

**Links:**
doi
arxiv
code

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