A nonlinear diffusion method for semi-supervised learning on hypergraphs

Abstract

Hypergraphs are a common model for multiway relationships in data, and hypergraph semi-supervised learning is the problem of assigning labels to all nodes in a hypergraph, given labels on just a few nodes. Diffusions and label spreading are classical techniques for semi-supervised learning in the graph setting, and there are some standard ways to extend them to hypergraphs. However, these methods are linear models, and do not offer an obvious way of incorporating node features for making predictions. Here, we develop a nonlinear diffusion process on hypergraphs that spreads both features and labels following the hypergraph structure, which can be interpreted as a hypergraph equilibrium network. Even though the process is nonlinear, we show global convergence to a unique limiting point for a broad class of nonlinearities, which is the global optimum of a interpretable, regularized semi-supervised learning loss function. The limiting point serves as a node embedding from which we make predictions with a linear model. Our approach is much more accurate than several hypergraph neural networks, and also takes less time to train.

References in corpus (12)

• Assortative mixing in networks
• Higher-order organization of complex networks
• Simplicial Closure and higher-order link prediction
• Deep Equilibrium Models
• Combining Label Propagation and Simple Models Out-performs Graph Neural Networks
• The Total Variation on Hypergraphs - Learning on Hypergraphs Revisited
• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• HNHN: Hypergraph Networks with Hyperedge Neurons
• Algorithms for Lipschitz Learning on Graphs
• A framework for second order eigenvector centralities and clustering coefficients
• Monotone operator equilibrium networks
• Strongly Local Hypergraph Diffusions for Clustering and Semi-supervised Learning