Nonlinear Feature Diffusion on Hypergraphs

Konstantin Prokopchik, Austin R. Benson, Francesco TudiscoICML 2022 · OpenReview

HyperND (Nonlinear Hypergraph Diffusion) is a novel framework for semi-supervised learning that propagates both labels and node features across hypergraphs using nonlinear diffusion. It offers the best of both worlds: the modeling flexibility of Graph Neural Networks (GNNs) and the speed and theoretical rigor of classical label spreading. By decoupling the diffusion process from the classification task, HyperND achieves state-of-the-art accuracy while training up to 100x faster than GNN baselines.

The Challenge of Hypergraph Learning

Many real-world datasets are best represented as hypergraphs, where edges (hyperedges) can connect any number of nodes—such as a research paper with five authors or a group email thread. In semi-supervised learning (SSL) on these structures, we have labels for only a few nodes and need to predict the rest.

Existing approaches generally fall into two camps:

  1. Diffusion/Label Spreading: These methods are fast and theoretically well-understood but are usually linear and struggle to incorporate rich node features (like the text of a research paper).
  2. Hypergraph Neural Networks (HNNs): These models are powerful and utilize features effectively, but they are computationally expensive to train and often lack clear theoretical guarantees regarding convergence.

HyperND bridges this gap by creating a nonlinear diffusion process that is both feature-aware and mathematically well-behaved.

The HyperND Framework

HyperND treats SSL as a regularization problem, proposing a new loss function that minimizes a "generalized variance" of node embeddings across hyperedges. Key technical components include:

  • Nonlinear Diffusion Operator: Unlike standard linear diffusion, HyperND uses nonlinear mappings (specifically $p$-power means) to aggregate information. This allows the model to capture more complex relationships than simple averages.
  • Simultaneous Propagation: The model diffuses the initial labels and the node features together into a joint embedding space. Treating node features exactly like labels—spreading them through the hypergraph structure—creates highly informative embeddings.
  • Decoupled Training: The diffusion process runs until it reaches a unique fixed point. Only then is a simple linear classifier (like multinomial logistic regression) trained on these embeddings. This separation of "structural smoothing" from "parameter learning" bypasses the expensive backpropagation cycles required by GNNs.
  • Theoretical Guarantees: The authors prove that despite the nonlinearity, the process is guaranteed to converge to a unique global minimum for a broad class of $p$-homogenous mappings.

Key Results and Robustness

The model was evaluated on several real-world hypergraph benchmarks, including co-citation and co-authorship networks (DBLP, Pubmed, Cora, Citeseer) and biological networks.

  • Accuracy and Speed: HyperND consistently outperformed or matched top-tier baselines like HGNN and HyperGCN. On large datasets like DBLP, HyperND was roughly two orders of magnitude faster to train than neural network-based competitors.
  • Hyperparameter Robustness: The model's performance remains highly stable across a wide range of hyperparameters, specifically the nonlinearity parameter ($p$) and the regularization parameter ($\alpha$).
Performance of HyperND across different values of p and α. The model shows high accuracy and stability across a broad parameter space on multiple datasets.

Limitations and Future Work

While highly effective, HyperND has a few limitations that present opportunities for future research:

  • Homophily Assumption: Like most diffusion methods, HyperND assumes connected nodes likely share the same label. It may struggle with "heterophilic" networks where connected nodes are intentionally different.
  • Positivity Requirement: The current theoretical proof requires input embeddings to be entrywise positive. While the authors use "label smoothing" to circumvent this practically, a more general theory for signed features is needed.
  • Directed Hyperedges: The current model treats hyperedges as undirected sets. Extending this to directed higher-order relationships remains an open challenge.

Summary updated

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 fe...
BibTeX
@inproceedings{prokopchik2022nonlinear,
  author = {Konstantin Prokopchik and Austin R. Benson and Francesco Tudisco},
  title = {{Nonlinear Feature Diffusion on Hypergraphs}},
  booktitle = {International Conference on Machine Learning},
  year = {2022},
  url = {https://openreview.net/forum?id=LHMDvrpOlz},
}
Figure