CS Paper Radar

Fast Graph Laplacian Estimation using Effective Resistance

Christoffer Kjellson, Claudio Altafini, Emma Tegling

eess.SP cs.LG ·submitted 2026-09-20 14:23 UTC · v2
published

Abstract

Inferring network topology from noisy node observations is a central problem in graph signal processing. In this paper, we consider Laplacian-constrained graph estimation for Gaussian Markov random fields, focusing on the underdetermined regime in which the number of samples is smaller than the number of graph nodes. Existing approaches often formulate the problem as a sparsity-regularized maximum-likelihood estimation problem. While effective, such methods typically require iterative optimization and are often computationally demanding, particularly under Laplacian constraints. Instead, we propose a non-iterative estimator of graph Laplacians that uses effective resistance for regularization, and evaluate the method using a simple sparsification procedure. Experiments show that with some trade-off in edge and weight recovery on the considered dataset, computational cost for moderately sized graphs can be substantially reduced.

Journal ref
IEEE Signal Processing Letters, 2026
DOI
10.1109/LSP.2026.3737400

Closest papers

Nearest neighbours by meaning across the whole index.

Graph Learning with Spectral Connectivity Priors for Scarce Data

cs.LG eess.SP ·2026-09-23 ·Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao +1 more
similarity 0.68
Abstract · 5 pages, 1 figure. Submitted to IEEE ICASSP 2027

Learning a sparse graph from scarce data is practically important but challenging. Motivated by the desirable combination of local sparsity and strong global connectivity exhibited by expander-like graphs, we propose spectral connectivity-regularized graph learning (SCoGL), a framework that incorporates a family of Laplacian spectral priors to explicitly promote global connectivity. Specifically, SCoGL augments a combinatorial-Laplacian-constrained graphical lasso (GLASSO) objective over a target adjacency matrix $\mathbf{W}$ with a general connectivity prior computed from Laplacian eigenvalues. We derive gradients for several representative connectivity priors and develop a projected gradient descent (PGD) algorithm with Armijo backtracking to efficiently optimize $\mathbf{W}$. Experiments show that the proposed SCoGL variants improve graph recovery and enhance downstream tasks such as graph signal denoising when signal observations are scarce.

0.24

Scalable Subgraph Sampling via Resistance Curvature

cs.LG cs.AI ·2026-09-23 ·Chaoqun Fei, Tinglve Zhou, Tianyong Hao, Yangyang Li
similarity 0.67
Abstract

Subgraph sampling reduces the training cost of large-scale graph neural networks, but sampling criteria may overlook the geometric roles of edges. We propose a resistance-curvature-guided sampling framework built on ERC-LG, a curvature approximation method for large-scale graphs. ERC-LG combines Johnson-Lindenstrauss projections with regularized multi-GPU batched conjugate gradient solvers, avoiding explicit Laplacian pseudoinverse computation and full embedding storage. The resulting curvature informs node- and edge-sampling probabilities for constructing GNN training subgraphs. Experiments show numerical agreement with pseudoinverse-based curvature and reduced runtime compared with CG-only computation. ERC-LG-based sampling variants achieve the highest mean accuracy on six of seven real-world datasets in downstream node classification.

0.24

Difference-of-Convex Regularization for Graph Learning by Differentiable Programming

cs.LG math.OC ·2026-08-13 ·Liping Tao, Chee Wei Tan
similarity 0.64
Abstract

Laplacian-regularized minimization is fundamental in signal processing and machine learning, but explicit construction of the dense graph Laplacian pseudoinverse can be computationally expensive. To address this issue, we consider the setting where the graph Laplacian is given and propose a Difference-of-Convex Regularizer (DCR) graph learning framework that learns a reusable approximation of the pseudoinverse action through regularized Maximum Likelihood Estimation (MLE) and shrinkage-regularized Convex--Concave Procedure (CCCP) iterations. For Laplacian-Regularized Nonnegative Least Squares (LR-NNLS), dual and Karush-Kuhn-Tucker (KKT) analysis motivates separating graph-dependent pseudoinverse learning from instance-specific optimization. The learned pseudoinverse is embedded into a differentiable primal optimization procedure as a graph-aware preconditioner for nonnegative reconstruction and can be reused across LR-NNLS instances sharing the same graph. We establish stability and fixed-point existence guarantees for the proposed pseudoinverse-learning iteration. Experiments across different graph topologies and scales demonstrate near-reference accuracy, competitive time-to-moderate-accuracy behavior, and effective cross-instance reuse across independently generated problem instances sharing the same graph.

0.04

Feature-Aware Edge Sampling for Approximate One-Step Laplacian Propagation

cs.LG ·2026-11-12 ·Jonathan Z. Sun, Zheng Wang, Kebin Xu
similarity 0.63
Abstract

This paper studies how to approximate one-step combinatorial Laplacian messages in graph neural networks using edge sampling. We propose a spanning tree based hybrid sampler that combines feature-conditioned message scores and effective-resistance leverage scores, derive the expected one-step message error and obtain the optimal sampling probabilities and error frontier for a given expected edge budget. Preliminary experiments on synthetic community graphs show that message error decreases, while classification accuracy increases slightly, as the edge budget grows, and performance of the hybrid sampler is in between of optimal selection uniform random sampling. We leave multi-step propagation and evaluation on larger and real graphs for future work.

0.17

Graph Signal Estimation With Unknown Topology

eess.SP ·2026-10-25 ·Tirza Routtenberg
similarity 0.62
Abstract

Graph-signal estimation is commonly designed assuming that the underlying topology is known. In this paper, we consider estimation from general nonlinear measurements when the active topology is latent but is known to belong to a given family of candidate graphs. We first develop a class of topology-blind graph-spectral estimators that jointly exploit the candidate graphs, and characterize the performance loss compared to unconstrained linear estimation. We derive the minimum-mean-squared-error (MSE) multi-basis estimator and show that its optimal operator is the weighted projection of the topology-blind linear MMSE (LMMSE) operator onto the multi-graph filter space. This characterization provides exact expressions for the excess MSE and conditions for attaining the topology-blind LMMSE. To reduce the number of parameters, we develop estimators based on shared spectral responses and low-rank representations, and consider data-dependent estimators that infer the topology from the measurements, by maximum a-posteriori probability (MAP) selection or posterior weighting (multiple-model). We further extend the framework to networks of different sizes by jointly optimizing a common spectral function. We derive its MSE-optimal coefficients and decompose the resulting estimation loss into graph-filter approximation error and the additional cost of sharing a spectral response across networks. The proposed estimators admit sample-based implementations, while the shared spectral function can be applied to unseen graphs without retraining its coefficients. Simulations on IEEE power networks demonstrate the benefits of the proposed graph-spectral estimators under topology uncertainty and cross- network transfer.

0.42

Multi-Source Wasserstein Distributionally Robust Graph Learning

cs.LG ·2026-08-20 ·Chuansen Peng, Yifan Xia, Jinshan Zhong, Xiaojing Shen
theory similarity 0.60
Abstract

Reconstructing complex network topologies from data is a fundamental challenge in cybernetics and graph signal processing, with applications in neuroscience, sensor, and social networks. In practice, target-domain samples are scarce while heterogeneous source-domain data are abundant. Fusing these sources is challenging: Euclidean averaging works for homogeneous sources but degrades sharply as inter-source divergence grows, collapsing distinct geometries into an inflated, biased consensus. We exploit the Wasserstein metric's distribution-preserving properties to counter heterogeneity while preserving each source's intrinsic geometry. We propose MS-WDRO, a multi-source Wasserstein distributionally robust graph learning framework that fuses heterogeneous sources via their weighted Wasserstein barycenter, a geometrically principled nominal distribution, then builds an ambiguity ball around it to hedge residual uncertainty. Minimizing worst-case risk yields a tractable regularized Laplacian estimator solved efficiently via a provably convergent ADMM scheme. We establish non-asymptotic guarantees: a finite-sample concentration bound for the empirical barycenter, a pooling bias lower bound proving naive aggregation is suboptimal, and an out-of-sample excess risk bound decaying at a parametric rate with only logarithmic dependence on source count. To calibrate hyperparameters governing robustness, sparsity, and source fusion, we unroll the solver into a differentiable architecture trained end-to-end, achieving data-adaptive calibration beyond cross-validation while retaining interpretability. Experiments on synthetic benchmarks and the multi-site ABIDE~I neuroimaging dataset show MS-WDRO consistently outperforms seven baselines in graph recovery, sample efficiency, and downstream diagnostic utility, with the largest gains in the sample-scarce regime.

0.11

Provable Guarantees for Spectral Structured Prediction

cs.LG ·2026-09-16 ·Violet Zheng, Jean Honorio
similarity 0.60
Abstract

Structured prediction is the simultaneous prediction of multiple labels, and is widely used in various fields, such as natural language processing and computer vision. In this paper, we study binary node label recovery on signed graphs with edge-flip noise, a model introduced by (Globerson et al., 2015), via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix. We develop graph structure-agnostic theoretical guarantees for approximate inference of node labels as well as guarantees for maximum angle deviation with respect to the ground truth node labels. By leveraging tools from matrix concentration theory and eigenvector perturbation analysis, we derive new concentration inequalities that explicitly quantify the effect of the spectral gap of the adjacency matrix, number of nodes, degree distribution, and noise level. As a corollary, we relate our general results to the Cheeger constant and provide results for different classes of graphs. We perform several synthetic experiments to validate our theory. To the best of our knowledge, we are the first to provide theoretical guarantees for the spectral-based approach. As a byproduct of our analysis, we derive technical results that might be of independent interest and useful for other machine learning problems.

0.31

GraCo: A Unified Toolkit of Graph Coarsening Algorithms and Metrics

cs.LG ·2026-10-31 ·Antonin Joly
code/data similarity 0.60
Abstract · Code: https://github.com/Antonin-J/graco

Graph coarsening aims to reduce a graph to a smaller one that preserves chosen properties of the original. It is increasingly used to scale graph learning to large graphs, as a non-differentiable step applied once before training. Many coarsening methods have been proposed in recent years, each with its own implementation, notation and evaluation. In this work, we introduce GraCo, a unified toolkit of graph coarsening methods. It relies on a single definition: a coarsening is fixed by a partition of the nodes and by the Laplacian the coarsened graph is consistent with. The coarsened graph, and the reduction and lifting matrices that map signals from the original graph to the coarsened one and back, follow from these two choices. We implement 17 methods from the literature and a random baseline, grouped into five families, with the same notation, inputs and outputs. We also build a collection of metrics from different papers, applicable to any coarsening. We check the implementations on a synthetic stochastic block model, then we report the runtime and peak memory of each method on Cora, PubMed, ogbn-arxiv and ogbn-products. GraCo is open-source and available at https://github.com/Antonin-J/graco.

0.42