$H{S}^2$: Active Learning over Hypergraphs

Abstract

We propose a hypergraph-based active learning scheme which we term $H{S}^2$, $H{S}^2$ generalizes the previously reported algorithm $S^2$ originally proposed for graph-based active learning with pointwise queries [Dasarathy et al., COLT 2015]. Our $H{S}^2$ method can accommodate hypergraph structures and allows one to ask both pointwise queries and pairwise queries. Based on a novel parametric system particularly designed for hypergraphs, we derive theoretical results on the query complexity of $H{S}^2$ for the above described generalized settings. Both the theoretical and empirical results show that $H{S}^2$ requires a significantly fewer number of queries than $S^2$ when one uses $S^2$ over a graph obtained from the corresponding hypergraph via clique expansion.

References in corpus (9)

• Higher-order organization of complex networks
• Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
• Clustering with Same-Cluster Queries
• Hypergeometric tail inequalities: ending the insanity
• Active Learning on Trees and Graphs
• Active Semi-Supervised Learning using Submodular Functions
• Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approach
• Query Complexity of Clustering with Side Information
• On the Minimax Misclassification Ratio of Hypergraph Community Detection