Algebraic Multigrid Acceleration for Efficient Label Spreading

I. INTRODUCTION

• Label spreading propagates labels from a small labeled set through a similarity graph by iteratively exchanging information among neighboring data points.It assumes nearby points or points on the same manifold are likely to share a label.Source: §I · p. 1
• Graph construction scales quadratically with sample count, while matrix inversion scales cubically and requires quadratic memory, limiting label spreading on large datasets.Source: §I · p. 1
• Existing approximations, sparsification, and iterative solvers still fall short of large-scale needs, and no widely used efficient label-spreading implementation is available.Source: §I · p. 1

Our Contribution:

• AMELS constructs sparse k-nearest-neighbor graphs using low-dimensional image embeddings from vision-language models and efficient nearest-neighbor search [12].The framework uses GPU-accelerated FAISS for nearest-neighbor search on image embeddings such as CLIP [fig. 1].Source: Our Contribution · pp. 1–2, Figure 1 · p. 1
• AMELS uses algebraic multigrid solvers to approximate label spreading’s linear-system solution, with coarse levels accelerating label propagation across distant graph connections.The authors motivate AMG’s robustness by noting that practical diffusion strengths near α = 1 produce ill-conditioned graph Laplacians [14].Source: Our Contribution · p. 2
• On standard image-classification benchmarks, AMELS reduces runtime and iteration counts versus existing approaches while preserving classification accuracy.The framework also enables accurate labeling of large-scale image datasets at a fraction of the annotation cost.Source: Our Contribution · p. 2
• Hyperparameter studies show AMELS is more robust to parameter choices in both runtime and performance.Source: Our Contribution · p. 2

1) Label Propagation and Label Spreading:

• Label propagation fixes labeled nodes, whereas label spreading uses normalized-Laplacian regularization and soft clamping for greater stability and robustness.Both are graph-based methods with random-walk interpretations; label propagation also relates to methods in and.Source: 1) Label Propagation and Label Spreading · p. 2
• The standard label-spreading power method iteratively computes a truncated Neumann series, adding a term per iteration until convergence.The iterative update is proposed in and used by the implementation in.Source: 1) Label Propagation and Label Spreading · p. 2

2) Efficient Label Propagation and Label Spreading Methods.:

• Sparse k-NN graphs reduce edges from O(n^2) to O(kn), lowering Laplacian memory and matrix-vector costs, while Faiss [12] accelerates large-scale graph construction.Nearest-neighbor search can nevertheless remain expensive on large datasets.Source: 2) Efficient Label Propagation and… · p. 2
• Bipartite similarity graphs, enable low-rank approximations and iterative refinement but may lose graph structure and introduce errors; combining Laplacians increases model complexity.Source: 2) Efficient Label Propagation and… · p. 2
• Determining labels for unlabeled data in c classes costs O(n^3 + cn^2); Fujiwara et al. reduce power-method cost to O(cnt) while preserving the exact solution.Here, t is the average number of iterations per label, typically t ≪ n; their algorithm removes negligible entries in the system-matrix series representation.Source: 2) Efficient Label Propagation and… · p. 2
• CG is used for label spreading in neural-network feature space and with anchor-point graphs, but the paper reports that AMG handles ill-conditioned systems more robustly and scales better with GPU support.The paper compares against optimized CPU and GPU CG implementations and publicly available implementations.Source: 2) Efficient Label Propagation and… · p. 3

III. PRELIMINARIES

• The task predicts labels for n − a unlabeled samples from a labeled subset, representing pairwise sample relationships with a weighted similarity graph.Source: 1) Label Spreading · p. 3

1) Label Spreading.:

• The iteration converges to F* = (I − αS)^−1Y, reducing label spreading to c linear systems with the same SPD matrix A = I − αS.The diffusion parameter α controls information exchange, while known labels are preserved; the systems scale with dataset size n.Source: 1) Label Spreading · p. 3

2) Iterative Solvers and Krylov Subspace Methods.

• Krylov methods such as CG and GMRES are attractive for large sparse linear systems because of their scalability and low memory requirements.Convergence is rapid when BA≈I; these iterative methods quickly damp high-frequency error components, a process called smoothing.Source: 2) Iterative Solvers and Krylov… · p. 3
• At iteration t, Krylov methods choose the best approximation in K_t; for SPD matrices, CG minimizes the error in the A-norm.This is the method-specific criterion described for CG.Source: 2) Iterative Solvers and Krylov… · p. 3
• GMRES chooses iterates that minimize the Euclidean residual norm over the affine subspace K_t.This is GMRES’s residual-minimization criterion.Source: 2) Iterative Solvers and Krylov… · p. 3
• Krylov convergence depends strongly on A’s spectrum; for ill-conditioned systems with large ∥A^-1∥2, a small residual may not imply a small error.For SPD matrices, eigenvalues near zero can separate residual and error.Source: 2) Iterative Solvers and Krylov… · p. 3

3) Algebraic Multigrid (AMG) Methods.:

• AMG approximates the preconditioner M^-1 ≈ A^-1, combining local smoothing with coarse-grid corrections to improve spectral properties and convergence.The passage describes AMG as a hierarchical framework for solving large systems.Source: 3) Algebraic Multigrid (AMG) Methods · p. 3
• During setup, AMG constructs a hierarchy of coarse systems, using prolongation and restriction between levels and aggregating strongly connected variables into coarser representations.The fine-level operator is the original system, and coarse operators are recursively defined.Source: 3) Algebraic Multigrid (AMG) Methods · p. 4
• An AMG V-cycle pre-smooths to reduce high-frequency error, restricts residuals to coarser levels, solves the coarsest system, then interpolates corrections and post-smooths to reduce both frequency components efficiently.For large sparse systems, this multilevel structure often yields near-linear complexity.Source: 3) Algebraic Multigrid (AMG) Methods · p. 4
• In preconditioned GMRES, each iteration applies one AMG V-cycle to the current residual, while the method minimizes the residual norm over an affine Krylov subspace.The passage also defines the initial preconditioned residual as z(0) = M^-1r(0).Source: 3) Algebraic Multigrid (AMG) Methods · p. 4

IV. METHOD

• AMELS targets two label-spreading challenges: constructing the graph and determining the label-spreading solution.Figure 1 depicts an overview of the framework.Source: §IV · p. 4

1) Embedding.:

• Lower-dimensional feature extraction makes distances more informative for high-dimensional image inputs, supporting the local-smoothness assumption; the framework is agnostic to the dimensionality-reduction technique.A cited pipeline uses CLIP features followed by UMAP reduction [14] [32].Source: 1) Embedding · p. 4

2) Nearest neighbors.:

• The graph uses Gaussian-kernel affinities on a symmetrized, degree-normalized sparse k-NN graph, with Faiss GPU search accelerating large-scale neighbor construction.Edges are retained when either node is in the other’s k-nearest neighbors, and the bandwidth is the mean squared k-NN radius averaged across data points.Source: 2) Nearest neighbors · p. 4

B. Efficient Solution Approximation via AMG

• AMG leverages graph hierarchy and effective preconditioning to approximate the solution of the label-spreading system.The passage identifies this as the framework’s key contribution.Source: B. Efficient Solution Approximation… · p. 4
• For large datasets requiring α close to 1, the system becomes increasingly ill-conditioned, so residual stopping criteria can underestimate error and Krylov methods may converge slowly without preconditioning.Combining GMRES with AMG preconditioning shifts the spectrum away from zero, improves residual-error alignment, and accelerates convergence.Source: B. Efficient Solution Approximation… · p. 5
• Because all c class-score systems share coefficient matrix I − αS, AMELS constructs the AMG hierarchy once and reuses it for every right-hand side.The class-wise label-spreading solution is computed by solving the corresponding linear systems.Source: B. Efficient Solution Approximation… · p. 5
• AMG reduces unknowns on coarser levels, and coarse-grid correction propagates label information globally across the graph in one iteration, unlike the power method’s local propagation.The multilevel hierarchy reduces computational complexity for the resulting linear systems.Source: B. Efficient Solution Approximation… · p. 5

V. NUMERICAL RESULTS

• The evaluation asks whether AMELS improves computational efficiency, how hyperparameters affect its runtime relative to other implementations, and whether runtime efficiency affects classification accuracy.Source: §V · p. 5

A. Experimental Setup

• AMELS uses FGMRES with an AMG preconditioner and one V-cycle, with an initial Krylov subspace dimension t = 20.The setup uses Parallel Modified Independent Set with β = 0.25, extended+i interpolation, one post-smoothing step, and dense LU at the coarsest level.Source: 1) Implementation Details · p. 5

2) Baselines.:

• The power-method baseline is scikit-learn’s implementation.Source: 2) Baselines · p. 5
• The direct-solve baseline uses SciPy spsolve, while the SciPy iterative baseline uses Conjugate Gradient.Source: 2) Baselines · p. 5
• The AmgX baseline uses the library’s Conjugate Gradient implementation.Source: 2) Baselines · p. 5
• All methods use the same relative-residual tolerance; the power method’s stopping rule was changed to require a sufficiently small residual norm.Computing the residual adds one matrix-vector multiplication per iteration, described as negligible relative to overall runtime.Source: 2) Baselines · p. 5

3) Datasets.:

• The evaluation spans EMNIST-Digits (280,000 images), CIFAR-10 (50,000 images, 10 classes), and Tiny ImageNet (100,000 images, 200 classes).The passage identifies the datasets as image classification benchmarks and cites their original references,, and.Source: 3) Datasets · p. 5

4) Hardware Specifications.:

• CPU implementations used two 20-core CPUs, while AmgX-based AMG implementations used one GPU.Experiments used an NVIDIA Quadro P6000 GPU with 24 GB memory, two Intel Xeon Gold 6138 CPUs, and 502 GB RAM; CPU-based SciPy implementations and AMG implementations used these respective resources,.Source: 4) Hardware Specifications · p. 5

5) Parameter Configurations.:

• Experiments fixed k = 20 neighbors, α = 0.99, 100 randomly drawn labels, and a residual tolerance of 10−3.Graphs were constructed in a 20-dimensional UMAP embedding of CLIP ViT-B/32 image features, using default UMAP parameters.Source: 5) Parameter Configurations · p. 5

B. Computational Efficiency

• The efficiency comparison reports runtime in seconds and iteration counts averaged over 10 runs for varying EMNIST-Digits dataset sizes.The figure caption specifies these measures but provides no numerical values in the supplied passage.Source: Figure 4 · p. 6

1) Classification Accuracy versus Runtime.:

• AMELS consistently achieves high accuracy with minimal runtime, particularly on EMNIST-digits and CIFAR-10; the power method takes longer to reach high accuracy, while both CG implementations have high variance.The comparison varies the maximum iteration count and smooths performance over a 30-point moving-average window, reporting empirical standard deviation.Source: 1) Classification Accuracy versus… · p. 6, Figure 3 · p. 6
• Classification accuracy was measured as the maximum iteration count varied, with results smoothed over a 30-iteration moving-average window and empirical standard deviation computed.The number of iterations, runtime, and performance depend on the randomly selected initial labels.Source: 1) Classification Accuracy versus… · p. 6

2) Scalability Across Dataset Sizes.:

• On augmented EMNIST-digits datasets up to 1,000,000 points, AMELS outperforms direct solving, the power method, and CG in runtime, while iterative solvers require fewer iterations than the power method.The power method is fastest only on very small datasets; iteration counts are not directly comparable because the methods update and solve differently.Source: 2) Scalability Across Dataset Sizes · p. 6

D. Classification Accuracy

• AMELS is more robust to α for classification accuracy, with performance best near one and degradation less severe than for the power method; it also outperforms competitors at very small k.The passages describe robustness to both α and k choices.Source: Figure 5 · p. 7, D. Classification Accuracy · p. 7, Figure 6 · p. 7

1) Diffusion strength.:

• As α approaches 1, the power method runtime rises sharply and SciPy CG slows substantially, while AMELS runtime is minimally affected and can reduce runtime versus AmgX CG.The passage attributes this in part to preconditioning and AMELS's multilevel approximation of weak long-range interactions; direct solving was excluded due to runtime limits.Source: 1) Diffusion strength · p. 7, Figure 5 · p. 7

C. Impact of Hyperparameters on Runtime

• Runtime sensitivity to hyperparameters is limited: increasing k makes the graph denser and raises graph-construction and solve complexity, yet AMELS and baseline methods show limited runtime sensitivity to k.This supports using moderately dense graphs without significant runtime increases.Source: 2) Graph density · p. 7

VI. CONCLUSION

• AMELS combines sparse neighborhood graphs with AMG preconditioning to improve the system matrix's spectral properties and make label spreading applicable to large-scale image datasets.The conclusion states that this enables semiautomated annotation to reduce manual-labeling costs.Source: §VI · p. 7

C. Impact of Hyperparameters on Runtime

• AMELS reduces label-spreading runtime without sacrificing performance and is more robust to hyperparameter choices.This conclusion summarizes the reported runtime and accuracy findings.Source: §VI · p. 7

APPENDIX

• The appendix provides additional details on CG, GMRES, and the spectral properties of the system matrix used in label spreading.Source: APPENDIX · p. 9

A. CG and GMRES

• CG applies when A is symmetric positive definite: A^T = A and x^T A x > 0 for every nonzero x in R^n.Source: A. CG and GMRES · p. 9
• CG selects iterates from the initial guess plus a Krylov subspace to minimize the error in the A-norm.Source: A. CG and GMRES · p. 9
• GMRES computes iterates in the same affine Krylov space by minimizing the Euclidean norm of the residual.Source: A. CG and GMRES · p. 9
• GMRES typically uses Arnoldi iteration to form an orthonormal basis of the Krylov subspace.Source: A. CG and GMRES · p. 9
• The GMRES iterate uses a coefficient vector obtained from a small least-squares problem involving the corresponding Hessenberg matrix.Source: A. CG and GMRES · p. 9

• S is stochastic, with eigenvalues at most 1 and extreme eigenvalues μmax = 1 and μmin = −1.Source: B. Spectral Properties of the Graph… · p. 9
• For α∈(0,1), eigenvalues of αS lie in [−α, α], so I −αS has spectrum [1−α, 1+α] and is positive definite.Source: B. Spectral Properties of the Graph… · p. 9
• The condition number of I −αS is (1 + α)/(1 − α), from λmax = 1 + α and λmin = 1−α.Source: B. Spectral Properties of the Graph… · p. 9