Large-scale semi-supervised learning with online spectral graph sparsification
Daniele Calandriello, Alessandro Lazaric, Michal Valko · 2026
Read Large-scale semi-supervised learning with online spectral graph sparsification by Daniele Calandriello, Alessandro Lazaric, Michal Valko (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26550.txt.
Introduction
Calandriello, Lazaric, and Valko introduced Sparse-HFS, a scalable algorithm for large-scale semi-supervised learning, where few labeled examples join many unlabeled ones. It solves such problems using only near-linear space and time, with polylogarithmic overhead factors. The method makes massive graph-based learning tractable without storing or processing the full dense graph. Its efficiency opens semi-supervised learning to web-scale problems.
Catalog record
| CREATOR | Daniele Calandriello, Alessandro Lazaric, Michal Valko |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24216 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.26550
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Large-scale semi-supervised learning with online spectral graph sparsification Daniele Calandriello, Alessandro Lazaric, Michal Valko Abstract 1 Introduction In many classification and regression tasks, obtaining many good-quality labeled examples may be expensive. When the number of labeled examples is very small, traditional supervised learning algorithms fail in learning accurate predictors. Semi-supervised learning ( 3 , SSL,) deals with this problem by integrating the labeled examples with an additional set of unsupervised samples to make use of an underlying structure (e.g., a manifold) and reduced the need for labeling. In this paper we consider data whose similarity can be encoded in a graph , and the similarity between nodes is much easier to obtain than their label. Given the graph, SSL methods leverage the assumption that nodes which are similar according to the graph are more likely to be labeled similarly. Graph-based SSL propagates the labels from the labeled nodes to the unlabeled ones. For instance, the objective of harmonic function solution ( 10 ; 1 , HFS,) is to find a solution where each node’s value is the weighted average of its neighbors. The HFS solution can be found solving a linear system involving the graph Laplacian, but for dense graphs on n nodes this amounts to \mathcal{O}(n^{3}) time complexity and a \mathcal{O}(n^{2}) space complexity, which is infeasible for large n . In this paper, we consider a more realistic setting when space and computational budgets are limited . In particular, we only allow \mathcal{O}(n\polylog(n)) space for storing the graph structure and an amortized computational cost of \mathcal{O}(\polylog(n)) for each of the edges in the original graph. Notice that these constraints make it even impossible to store the full similarity matrix in memory. To this end we employ efficient online spectral graph sparsification techniques ( 7 ) to incrementally process the stream. This, coupled with specific solvers for symmetric diagonally dominant (SDD) matrices ( 8 ) , allow us to never store the whole graph in memory and to control the computational complexity as the number of nodes grows. Using the approximation properties of spectral sparsifiers and with results from algorithmic stability theory ( 2 ; 4 ) we will provide theoretical guarantees for the generalization error for this approximation. 2 SSL with Spectral Sparsification Notation. We denote with lowercase letter a a scalar, with bold lowercase letter \mathbf{a} a vector and with uppercase letters A a matrix. We consider the general transductive setting, where we assume that there exists a dictionary of labeled nodes \mathcal{D}=\{(x_{i},y_{i})\}_{i=1}^{n} , where the nodes are organized over an undirected graph \mathcal{G}=(\mathcal{V},\mathcal{E}) with n vertices \mathcal{V}=\{1,\ldots,n\} and m edges, and the labels are y_{i}\in\mathbb{R} . Given graphs \mathcal{G},\mathcal{A} defined on the same vertex set, the graph \mathcal{G}+\mathcal{A} is obtained by adding the weights on the edges of \mathcal{A} to \mathcal{G} . In a similar manner we define \mathcal{G}+e for edge e . For i\in\mathcal{V} , we denote with \chi_{i} the indicator vector, and with \mathbf{b}_{e} the vector \chi_{i}-\chi_{j} . While the algorithm receives information on the features x_{i} of all nodes, only a limited (random) subset \mathcal{S} of l nodes is actually labeled. The objective of the learning algorithm is to minimize the error on the complementary unlabeled set \mathcal{T}=\mathcal{D}\backslash\mathcal{S} . More precisely, the objective is to learn a function \mathbf{f}:\mathcal{V}\rightarrow\mathbb{R} that minimizes the generalization error R(\mathbf{f})=\tfrac{1}{u}\sum_{i=1}^{u}(\mathbf{f}(x_{i})-\mathbf{y}(x_{i}))^{2} , where u=|\mathcal{T}|=n-l is the number of unlabeled nodes. We indicate with \mathbf{f} and \mathbf{y}\in\mathbb{R}^{n} the vectors that contain the function and the labels evaluated at the n points x_{i} . Stable-HFS. HFS exploits the graph structure to learn functions that predict similar values y for similar nodes. Given a weighted adjacency matrix A_{\mathcal{G}} , with edge weights a_{e} , and the degree matrix D_{\mathcal{G}} , the Laplacian is defined as L_{\mathcal{G}}=D_{\mathcal{G}}-A_{\mathcal{G}} . We assume the graph is connected. In this case, L_{\mathcal{G}} is semi-definite positive (SDP) with \Ker(L_{\mathcal{G}})~=~\mathbf{1} . Let L_{\mathcal{G}}^{+} be the pseudoinverse of L_{\mathcal{G}} , and L_{\mathcal{G}}^{-1/2}=(L_{\mathcal{G}}^{+})^{1/2} . The original HFS method ( 10 ) , when we allow the label of already labeled nodes to change, can be formulated as the Laplacian-regularized least-squares problem \displaystyle\widehat{\mathbf{f}} \displaystyle=\argmin_{\mathbf{f}\in\mathbb{R}^{n}}\tfrac{1}{l}(\mathbf{f}-\mathbf{y})^{\mathsf{T}}I_{\mathcal{S}}(\mathbf{f}-\mathbf{y})+\gamma\mathbf{f}^{\mathsf{T}}L_{\mathcal{G}}\mathbf{f} \displaystyle=(\gamma lL_{\mathcal{G}}+I_{\mathcal{S}})^{+}(\mathbf{y}), (1) where I_{\mathcal{S}} is the identity matrix with zeros corresponding to the nodes not in \mathcal{S} , and \gamma is a regularizer. While HFS achieves interesting empirical results, it is not easy to provide theoretical guarantees for it due to the singularity of the Laplacian matrix. For this reason, we focus on the stable-HFS algorithm proposed by 1 where an additional regularization term is introduced to restrict the space of admissible hypothesis, so that \mathcal{F}=\left\{\mathbf{f}:\langle\mathbf{f},\mathbf{1}\rangle=0\right\} . This restriction can be enforced introducing an additional \mu regularization term, that can be computed in closed form as \displaystyle\mu=(\gamma lL_{\mathcal{G}}+I_{\mathcal{S}})^{+}\mathbf{y}/(\gamma lL_{\mathcal{G}}+I_{\mathcal{S}})^{+}\mathbf{1}, (2) and subtracting \mu\mathbf{1} from the unconstrained solution. It can be shown that this is equivalent to projecting the unregularized solution using the projection matrix P_{\mathcal{F}}=L_{\mathcal{G}}L_{\mathcal{G}}^{+} . While stable-HFS is more suited for theoretical analysis, its computational and space requirements remain polynomial. If the graph \mathcal{G} has no particular property, solving the linear system takes \mathcal{O}(n^{2}) space and \mathcal{O}(n^{3}) time. To satisfy our resource constraints, we include spectral sparsification in stable-HFS. Computing the solution on a sparse graph \mathcal{H} that approximates \mathcal{G} removes the polynomial complexity. 0: \{x_{i}:i\in\mathcal{D}\},\{y_{i}:i\in\mathcal{S}\} , a stream of m edges \mathcal{E} 0: \widehat{\mathbf{f}},\mathcal{H} Initialize \mathcal{H}=\emptyset,\mathcal{A}=\emptyset,t=1 while t\leq m do for |\mathcal{A}|\leq n\log^{2}(n)/\varepsilon^{2} do Receive edge e_{t} and add it to \mathcal{A} t=t+1 end for Compute a new graph \mathcal{H} using Alg. 2 on \mathcal{H}+\mathcal{A} Build Laplacian L_{\mathcal{H}} and diag. matrix \{I_{\mathcal{S}}(i,i)=1:i\in\mathcal{S}\} Compute HFS \widetilde{\mathbf{f}} using Eq. 1 and L_{\mathcal{H}} \widetilde{\mathbf{f}}=\widetilde{\mathbf{f}}-\mu\mathbf{1} where \mu is computed using Eq. 2 end while Algorithm 1 Sparse-HFS 0: \mathcal{H},\mathcal{A} , the previous probabilities \widetilde{p}_{e} for all edges in \mathcal{H} and the weights of the edges a_{e} . 0: \mathcal{H}^{\prime} , a 1\pm\varepsilon sparsifier of \mathcal{G}^{\prime}=\mathcal{G}+\mathcal{A} and new prob. \{\widetilde{p}^{\prime}_{e}:e\in\mathcal{H}^{\prime}\} . \alpha^{2}=1/(1-\varepsilon)^{2},N=\alpha^{2}n\log^{2}(n)/\varepsilon^{2} Obtain estimates \{\widetilde{R}^{\prime}_{e}:e\in\mathcal{H}+\mathcal{A}\} such that 1/\alpha\leq\widetilde{R}^{\prime}_{e}/R^{\prime}_{e}\leq\alpha with an SDD solver ( 8 ) Compute prob. \widetilde{p}^{\prime}_{e}=(a_{e}\widetilde{R}^{\prime}_{e})/(\alpha(n-1)) and w_{e}=a_{e}/(N\widetilde{p}^{\prime}_{e}) for all edges e\in\mathcal{H} do \widetilde{p}^{\prime}_{e}\leftarrow\min\{\widetilde{p}_{e},\widetilde{p}^{\prime}_{e}\} end for Initialize \mathcal{H}^{\prime}=\emptyset for all edges e\in\mathcal{H} do with probability \widetilde{p}^{\prime}_{e}/\widetilde{p}_{e} add edge e to \mathcal{H}^{\prime} with weight w_{e} end for for all edges e\in\mathcal{A} do /*The inner loop is run implicitly by sampling a binomial*/ for i=1 to N do with probability \widetilde{p}^{\prime}_{e} add edge e to \mathcal{H}^{\prime} with weight w_{e} end for end for Algorithm 2 Kelner-Levin Sparsification Algorithm Sparse-HFS. Spectral sparsifiers have been central in the development of efficient linear solvers ( 8 ) . Since their introduction by 9 , they were extended to insertion-only streams ( 7 ) . Definition 1 . A 1\pm\varepsilon spectral sparsifier of \mathcal{G} is a graph \mathcal{H}\subseteq\mathcal{G} such that for all \mathbf{x} \displaystyle(1-\varepsilon)\mathbf{x}^{\mathsf{T}}L_{\mathcal{G}}\mathbf{x}\leq\mathbf{x}^{\mathsf{T}}L_{\mathcal{H}}\mathbf{x}\leq(1+\varepsilon)\mathbf{x}^{\mathsf{T}}L_{\mathcal{G}}\mathbf{x} In this paper, we propose to spectral sparsify \mathcal{G} to reduce the complexity of HFS. A sparse graph \mathcal{H} can be stored efficiently, but if the construction of the sparsifier requires access to the whole \mathcal{G} graph at every moment, just storing the original graph in memory can be impossible. Moreover, traditional linear solvers for an n\times n matrix with m nonzero entries have a time complexity of \mathcal{O}(mn) , which is already infeasible for m=n . To meet our space and time requirements, we propose to build the sparsifier incrementally