Active Learning On Weighted Graphs Using Adaptive And Non-adaptive Approaches
This work addresses active learning on weighted graphs for signal reconstruction, offering incremental improvements over existing methods by leveraging graph weights and hybrid strategies.
The paper tackles graph-based active learning for reconstructing binary signals on weighted graphs by proposing a new sampling algorithm that aggressively searches for signal boundaries, generalizing an unweighted method and improving performance using graph weights. It shows the algorithm requires fewer samples than the unweighted method and outperforms a spectral method for high-accuracy predictions, while a hybrid method combines both approaches for broader accuracy tolerances.
This paper studies graph-based active learning, where the goal is to reconstruct a binary signal defined on the nodes of a weighted graph, by sampling it on a small subset of the nodes. A new sampling algorithm is proposed, which sequentially selects the graph nodes to be sampled, based on an aggressive search for the boundary of the signal over the graph. The algorithm generalizes a recent method for sampling nodes in unweighted graphs. The generalization improves the sampling performance using the information gained from the available graph weights. An analysis of the number of samples required by the proposed algorithm is provided, and the gain over the unweighted method is further demonstrated in simulations. Additionally, the proposed method is compared with an alternative state of-the-art method, which is based on the graph's spectral properties. It is shown that the proposed method significantly outperforms the spectral sampling method, if the signal needs to be predicted with high accuracy. On the other hand, if a higher level of inaccuracy is tolerable, then the spectral method outperforms the proposed aggressive search method. Consequently, we propose a hybrid method, which is shown to combine the advantages of both approaches.