Higher-Order Label Homogeneity and Spreading in Graphs
This addresses the limitation of existing methods in tasks like recommender systems and fraud detection by improving label prediction accuracy, though it is incremental as it builds on standard label spreading.
The paper tackles the problem of graph semi-supervised learning by proposing a method that leverages higher-order structures like triangles, rather than just edges, for label spreading, resulting in up to 4.7% accuracy improvement over traditional methods.
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.