Source-linked AI summary
Active Semi-Supervised Learning Using Sampling Theory for Graph Signals
Akshay Gadde, Aamir Anis, Antonio Ortega
TL;DR
The paper studies offline, pool-based active semi-supervised learning on graphs when labeled data are scarce and expensive. It uses graph-signal sampling theory to select nodes that maximize the frequency range of recoverable signals and then performs semi-supervised prediction. Experiments on real data report strong performance relative to state-of-the-art methods.
Problem
The problem is to select a small, informative batch of labels from a large unlabeled graph and predict the remaining labels when labeling is scarce and expensive.
Method
The framework selects nodes by maximizing the cutoff frequency of uniquely recoverable graph signals, then uses bandlimited interpolation for semi-supervised learning.
Results
The two algorithms together perform very well compared to state-of-the-art methods on real data.
Takeaways & Limitations
Graph-signal sampling provides a theoretically grounded criterion for label selection alongside an efficient semi-supervised learning method.
Takeaways & Limitations
The sampling-set optimization is combinatorial, and the study leaves selection of later batches using labels from earlier batches for future work.
Abstract
from arXiv · showhide
We consider the problem of offline, pool-based active semi-supervised learning on graphs. This problem is important when the labeled data is scarce and expensive whereas unlabeled data is easily available. The data points are represented by the vertices of an undirected graph with the similarity between them captured by the edge weights. Given a target number of nodes to label, the goal is to choose those nodes that are most informative and then predict the unknown labels. We propose a novel framework for this problem based on our recent results on sampling theory for graph signals. A graph signal is a real-valued function defined on each node of the graph. A notion of frequency for such signals can be defined using the spectrum of the graph Laplacian matrix. The sampling theory for graph signals aims to extend the traditional Nyquist-Shannon sampling theory by allowing us to identify the class of graph signals that can be reconstructed from their values on a subset of vertices. This approach allows us to define a criterion for active learning based on sampling set selection which aims at maximizing the frequency of the signals that can be reconstructed from their samples on the set. Experiments show the effectiveness of our method.
1. INTRODUCTION
The paper addresses pool-based active semi-supervised learning when labels are scarce and costly but unlabeled data are abundant. It develops a graph-sampling framework to select informative labels, support signal recovery, and enable scalable semi-supervised learning.
- Motivation: Active semi-supervised learning selects informative and representative points to maximize learning gain from a small number of label queries.The approach also exploits clustering structure in unlabeled data.
- Problem setting: The study focuses on pool-based batch-mode learning, selecting a small batch from a static unlabeled collection without using label information.This setting reflects applications such as crowdsourcing, while sequentially incorporating newly acquired labels is left for future work.
- Graph formulation: Graph-based semi-supervised learning represents data points as nodes, similarities as weighted edges, and class membership as a graph signal that is typically smooth.Smoothness means neighboring nodes are unlikely to differ in class membership.
- Limitations of prior methods: Existing graph-based methods often require global matrix operations and generally lack conditions guaranteeing unique, perfect interpolation from selected samples.These issues create scalability challenges for distributed implementations.
- Contribution: The proposed framework uses graph-signal sampling theory to derive a greedy node-selection algorithm, an efficient semi-supervised learner, and scalable distributed implementations.The authors report that the method outperforms several state-of-the-art methods on multiple real datasets.
2. SAMPLING THEORY FOR GRAPH SIGNALS
The paper formulates graph-signal sampling through Laplacian spectral frequency and uses recoverability conditions to guide sampling-set selection and reconstruction. It develops approximate, computationally tractable procedures for selecting informative nodes and recovering bandlimited signals from their samples.
- 2.1 Notation: Graph signals assign scalar values to graph nodes, while Laplacian eigenvalues provide graph frequencies and eigenvectors provide the Graph Fourier basis.The Graph Fourier Transform is the projection of a signal onto the Laplacian eigenvectors.
- 2.2 Preliminaries: An ω-bandlimited graph signal has zero Graph Fourier coefficients above ω and belongs to the Paley-Wiener space PWω(G).This defines the low-pass signal class considered for exact sampling and reconstruction.
- 2.3 P1: Cut-off frequency: For a sampling set S, the cutoff-frequency problem seeks the largest ω for which every signal in PWω(G) can be exactly recovered from its samples on S.The complementary reconstruction problem estimates values on Sc from samples on S; unlike regular sampling, these graph-sampling problems are not reciprocal.
- 2.3 P1: Cut-off frequency: The sampling theorem states that exact recovery is possible precisely when the signal bandwidth is below the cutoff determined by the smoothest nonzero signal supported on the unsampled nodes.A signal supported on Sc leaves sampled values unchanged, so such a signal determines the obstruction to unique recovery.
- 2.3 P1: Cut-off frequency: The method estimates cutoff frequencies with Ω_k(S) using powers of the Laplacian, trading accuracy against complexity and numerical stability without complete eigendecomposition.The estimate is guaranteed to remain below the actual cutoff, preserving the sampling-theorem guarantee for the selected set.
- 2.4 P2: Sampling set: Optimal sampling seeks the smallest set supporting recovery at a target cutoff, while a greedy heuristic adds nodes that maximize the increase in the estimated cutoff.The exact optimization is combinatorial because Ω_k(S) must be evaluated for every possible subset.
- 2.5 P3: Reconstruction: Given samples of a bandlimited signal, its spectral coefficients and full signal can be recovered by least squares when the unique-recovery conditions hold.The iterative alternative avoids expensive eigendecomposition by repeatedly enforcing the observed samples and projecting onto the low-pass space; polynomial filters implement this projection using Laplacian matrix-vector products.
3. GRAPH SAMPLING BASED ACTIVE SEMI-SUPERVISED LEARNING
The paper frames active semi-supervised learning as graph-signal sampling: select a fixed-size labeled set maximizing the recoverable bandwidth, then reconstruct class membership signals from labeled values. A greedy procedure selects nodes by increasing a sampling objective, with graph connectivity guiding the choice and prediction error tied to signal energy beyond the selected cut-off frequency.
- Framework: Class membership functions are treated as graph signals, and active learning selects a fixed-size sampling set with maximum cut-off frequency.Because the signals are generally non-bandlimited, the selected set determines the bandwidth used for approximation and reconstruction.
- Algorithm: The method finds a labeled set by greedily adding the node that maximizes the increase in Ω_k(S), then queries its labels and reconstructs predicted membership functions.The predictions assign each node the class with the largest predicted membership value.
- Graph Theoretic Interpretation: The sampling objective has a graph-theoretic interpretation: selecting nodes removes unlabeled vertices that are weakly connected to the labeled set.The relevant connectivity is captured by the ratio of partial degree to actual degree for unlabeled nodes.
- Graph Theoretic Interpretation: Higher powers k incorporate higher-order interactions and can capture more global connectivity beyond local graph relationships.The paper associates this extension with the underlying manifold structure of the data.
- Prediction Error and Number of Labels: The reconstruction error roughly equals the signal energy above ω_c(S), so maximizing the sampling cut-off seeks to reduce the prediction error.If the true signal lies in the corresponding bandlimited space, reconstruction is perfect; otherwise, energy beyond the cut-off contributes to error.
- Prediction Error and Number of Labels: Theorem 2 states that achieving error at most δ requires at least p labels, where p is the number of Laplacian eigenvalues below γ(f).The lower bound follows from the rank requirement for unique reconstruction and the bandwidth needed to meet the error tolerance.
4. RELATED WORK
Related graph-based active learning methods select samples using manifold coverage, connectivity, generalization-error bounds, or submodular objectives. The paper distinguishes its approach by maximizing connectivity from the unlabeled set toward the labeled set while targeting recoverable signal bandwidth.
- Related Work: Prior pool-based batch-mode methods include optimal experiment design, generalization-error-bound minimization, and submodular optimization.These approaches provide several graph-based alternatives for choosing labeled subsets.
- Related Work: Selecting nodes that maximize recoverable bandwidth aims to capture as many manifold dimensions as possible with few samples.The connection follows from the relationship between graph Fourier frequency and variation on the Laplacian-eigenmap manifold.
- Related Work: The LLGC-related method seeks a well-connected labeled set, whereas the proposed method seeks an unlabeled set well-connected to the labeled set.The distinction is expressed through different spectral connectivity objectives.
- Related Work: Submodular graph methods maximize an objective intended to prevent any subset of unlabeled nodes from being weakly connected to the labeled set.They also provide prediction-error bounds involving a graph smoothness function and motivate cluster-based sampling heuristics.
5. EXPERIMENTS
Experiments compare the proposed sampling-based method with established active semi-supervised learning approaches on toy, handwritten-digit, text, and spoken-letter tasks. The method generally performs strongly, especially with few labels, while parameter sensitivity depends on the dataset.
- Experimental setup: The proposed method is compared with LLR, LLGC error-bound minimization, METIS partitioning, Ψ-max, and random sampling.Ψ-max is excluded from the three application experiments because its O(N^6) complexity is considered non-scalable.
- Toy example: In the two-circles toy example, all methods select four points from each circle, while the proposed method spaces points evenly within and across circles.The selection is intended to identify representative points in the data.
- Handwritten digits classification: On USPS handwritten digits, the proposed method outperforms the other methods and achieves good classification with very few labeled samples.The authors attribute this behavior to selecting points that maximize recoverable signal dimensions.
- Text classification: On 20 Newsgroups, the proposed method performs very well relative to the alternatives, although absolute error rates remain high because groups have similar documents.The experiment uses cosine-similarity graphs built from document feature vectors.
- Effect of parameter k: Classification accuracy is largely insensitive to k on USPS and Isolet but improves slightly for higher k on 20 Newsgroups.The authors relate this difference to whether class-membership signals concentrate in low frequencies or retain substantial high-frequency energy.
6. CONCLUSION
The paper introduces a graph-signal sampling framework for batch active semi-supervised learning, combining node selection with bandlimited interpolation. Experiments report strong performance against state-of-the-art methods, while future work targets prediction-error and label-count bounds.
- The framework selects nodes to maximize the dimension of the space of uniquely recoverable graph signals.
- Selecting the subset with maximum cut-off frequency yields an efficient greedy algorithm, paired with semi-supervised learning through bandlimited interpolation.
- Experiments on real data show that the node-selection and interpolation algorithms perform very well compared to state-of-the-art methods.
- Future work will bound prediction error when true signals are not exactly bandlimited and tighten bounds on labels required for desired accuracy.