# Higher-Order Label Homogeneity and Spreading in Graphs

arXiv: https://arxiv.org/abs/2002.07833 · HTML: https://mlsanity.com/paper/2002.07833/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Feb 2020.

## Built on by (most cited first, 9 of 9)

- [Higher-order Clustering and Pooling for Graph Neural Networks](https://mlsanity.com/paper/2209.03473/) (2022)
- [Anomaly Detection in Dynamic Graphs: A Comprehensive Survey](https://mlsanity.com/paper/2406.00134/) (2024)
- [A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations](https://mlsanity.com/paper/2101.07730/) (2021)
- [Training-Free Message Passing for Learning on Hypergraphs](https://mlsanity.com/paper/2402.05569/) (2024)
- [NetInfoF Framework: Measuring and Exploiting Network Usable Information](https://mlsanity.com/paper/2402.07999/) (2024)
- [Network Report: A Structured Description for Network Datasets](https://mlsanity.com/paper/2206.03635/) (2022)
- [NetEffect: Discovery and Exploitation of Generalized Network Effects](https://mlsanity.com/paper/2301.00270/) (2022)
- [Probabilistic Label Spreading: Efficient and Consistent Estimation of Soft Labels with Epistemic Uncertainty on Graphs](https://mlsanity.com/paper/2602.04574/) (2026)
- [Nonlinear Correct and Smooth for Semi-Supervised Learning](https://mlsanity.com/paper/2310.05757/) (2023)

## Abstract (arXiv)

Do higher-order network structures aid graph semi-supervised learning? Given a graph and a few labeled vertices, labeling the remaining vertices is a high-impact problem with applications in several tasks, such as recommender systems, fraud detection and protein identification. However, traditional methods rely on edges for spreading labels, which is limited as all edges are not equal. Vertices with stronger connections participate in higher-order structures in graphs, which calls for methods that can leverage these structures in the semi-supervised learning tasks. To this end, we propose Higher-Order Label Spreading (HOLS) to spread labels using higher-order structures. HOLS has strong theoretical guarantees and reduces to standard label spreading in the base case. Via extensive experiments, we show that higher-order label spreading using triangles in addition to edges is up to 4.7% better than label spreading using edges alone. Compared to prior traditional and state-of-the-art methods, the proposed method leads to statistically significant accuracy gains in all-but-one cases, while remaining fast and scalable to large graphs.