Improved large-scale graph learning through ridge spectral sparsification

• URL: http://arxiv.org/abs/2604.20078v1
• Date: Wed, 22 Apr 2026 00:49:31 GMT
• Title: Improved large-scale graph learning through ridge spectral sparsification
• Abstract summary: We consider the problem of learning over the Laplacian L in a distributed streaming setting.<n>In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L.<n>We present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances.
• Score: 65.84577791298442
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.

Related papers

• Advection-Diffusion on Graphs: A Bakry-Emery Laplacian for Spectral Graph Neural Networks [2.6124895681424323]
  Graph Neural Networks (GNNs) often struggle to propagate information across long distances due to oversmoothing and oversquashing.<n>We introduce a Bakry-Emery graph Laplacian that integrates diffusion and advection through a learnable node-wise potential.<n>We develop mu-ChebNet, a spectral architecture that jointly learns the potential and Chebyshev filters.
  arXiv  Detail & Related papers  (2026-02-20T11:01:12Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification [81.06278257153835]
  We propose a graph rewiring method that balances structural bottleneck reduction and graph property preservation.<n>Our method generates graphs with enhanced connectivity while maintaining sparsity and largely preserving the original graph spectrum.
  arXiv  Detail & Related papers  (2025-06-19T08:01:00Z)
• Mitigating the Impact of Noisy Edges on Graph-Based Algorithms via Adversarial Robustness Evaluation [1.8569481432894677]
  We propose to use a spectral adversarial evaluation method to mitigate the impact of noisy edges on the performance of graph-based algorithms. Our method identifies the points that are less vulnerable to noisy edges and leverages only these robust points to perform graph-based algorithms.
  arXiv  Detail & Related papers  (2024-01-28T10:03:37Z)
• Pointspectrum: Equivariance Meets Laplacian Filtering for Graph Representation Learning [3.7875603451557063]
  Graph Representation Learning (GRL) has become essential for modern graph data mining and learning tasks. While Graph Neural Networks (GNNs) have been used in state-of-the-art GRL architectures, they have been shown to suffer from over smoothing. We propose PointSpectrum, a spectral method that incorporates a set equivariant network to account for a graph's structure.
  arXiv  Detail & Related papers  (2021-09-06T10:59:11Z)
• Multilayer Clustered Graph Learning [66.94201299553336]
  We use contrastive loss as a data fidelity term, in order to properly aggregate the observed layers into a representative graph. Experiments show that our method leads to a clustered clusters w.r.t. We learn a clustering algorithm for solving clustering problems.
  arXiv  Detail & Related papers  (2020-10-29T09:58:02Z)
• Understanding Coarsening for Embedding Large-Scale Graphs [3.6739949215165164]
  Proper analysis of graphs with Machine Learning (ML) algorithms has the potential to yield far-reaching insights into many areas of research and industry. The irregular structure of graph data constitutes an obstacle for running ML tasks on graphs. We analyze the impact of the coarsening quality on the embedding performance both in terms of speed and accuracy.
  arXiv  Detail & Related papers  (2020-09-10T15:06:33Z)
• SF-GRASS: Solver-Free Graph Spectral Sparsification [16.313489255657203]
  This work introduces a solver-free approach (SF-GRASS) for spectral graph sparsification by leveraging emerging spectral graph coarsening and graph signal processing techniques. We show that the proposed method can produce a hierarchy of high-quality spectral sparsifiers in nearly-linear time for a variety of real-world, large-scale graphs and circuit networks.
  arXiv  Detail & Related papers  (2020-08-17T21:37:19Z)
• Fast Graph Attention Networks Using Effective Resistance Based Graph Sparsification [70.50751397870972]
  FastGAT is a method to make attention based GNNs lightweight by using spectral sparsification to generate an optimal pruning of the input graph. We experimentally evaluate FastGAT on several large real world graph datasets for node classification tasks.
  arXiv  Detail & Related papers  (2020-06-15T22:07:54Z)
• Spectral Graph Attention Network with Fast Eigen-approximation [103.93113062682633]
  Spectral Graph Attention Network (SpGAT) learns representations for different frequency components regarding weighted filters and graph wavelets bases. Fast approximation variant SpGAT-Cheby is proposed to reduce the computational cost brought by the eigen-decomposition. We thoroughly evaluate the performance of SpGAT and SpGAT-Cheby in semi-supervised node classification tasks.
  arXiv  Detail & Related papers  (2020-03-16T21:49:34Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.