Higher-Order Label Homogeneity and Spreading in Graphs
  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.
