Semi-supervised learning (SSL) is effectively used for numerous
classification problems, thanks to its ability to make use of abundant
unlabeled data. The main assumption of various SSL algorithms is that the
nearby points on the data manifold are likely to share a label. Graph-based SSL
constructs a graph from point-cloud data as an approximation to the underlying
manifold, followed by label inference. It is no surprise that the quality of
the constructed graph in capturing the essential structure of the data is
critical to the accuracy of the subsequent inference step [6]. How should one
construct a graph from the input point-cloud data for graph-based SSL? In this
work we introduce a new, parallel graph learning framework (called PG-learn)
for the graph construction step of SSL. Our solution has two main ingredients:
(1) a gradient-based optimization of the edge weights (more specifically,
different kernel bandwidths in each dimension) based on a validation loss
function, and (2) a parallel hyperparameter search algorithm with an adaptive
resource allocation scheme. In essence, (1) allows us to search around a
(random) initial hyperparameter configuration for a better one with lower
validation loss. Since the search space of hyperparameters is huge for
high-dimensional problems, (2) empowers our gradient-based search to go through
as many different initial configurations as possible, where runs for relatively
unpromising starting configurations are terminated early to allocate the time
for others. As such, PG-learn is a carefully-designed hybrid of random and
adaptive search. Through experiments on multi-class classification problems, we
show that PG-learn significantly outperforms a variety of existing graph
construction schemes in accuracy (per fixed time budget for hyperparameter
tuning), and scales more effectively to high dimensional problems.

本文提出了一种新的并行图学习框架 (PG-learn)，具有基于梯度的优化边缘权重和自适应资源分配方案的并行超参数搜索算法，能显著提高图构建的准确性和高效扩展到高维问题。