PaperlayerView exact revision on arXiv

Source-linked AI summary

Graph Learning with Spectral Connectivity Priors for Scarce Data

Mingxiao Liu, Bahar Oveisgharan, Bingyan Zou, Gene Cheung, H. Vicky Zhao, Feifei Gao

arXiv:2609.27278v1cs.LGeess.SP

TL;DR

Estimating sparse graphs is challenging when observations are scarce. SCoGL adds Laplacian-eigenvalue connectivity priors to GLASSO and jointly optimizes graph weights; experiments report improved graph recovery and denoising in this regime.

  • Problem

    Learning a sparse graph is severely ill-posed when the signal dimension N far exceeds the number of observations K, making additional structural priors necessary.

    Source: §1 · p. 1

  • Method

    SCoGL augments a combinatorial-Laplacian-constrained GLASSO objective with Laplacian-spectral connectivity priors and jointly optimizes the adjacency matrix.

    Source: §1 · p. 1

  • Results

    SCoGL variants generally improve graph recovery in relative error and enhance graph-signal denoising when observations are scarce.

    Source: §1 · p. 1

  • Takeaways & Limitations

    Spectral connectivity regularization provides a useful inductive bias for graph filtering when the graph is learned from scarce observations.

    Source: §4.3 · p. 4

    Under scarce data, tested concave sparsity penalties tended to produce a few excessively large edge weights and worse recovery than the ℓ1 penalty.

    Source: §3.2 · p. 2

Abstract

from arXiv · show

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.

1. INTRODUCTION

Learning a sparse graph is ill-posed when observations are scarce, motivating structural priors that promote global connectivity. SCoGL adds Laplacian-spectral connectivity regularizers to GLASSO and jointly optimizes graph weights; experiments report gains in graph recovery and denoising.

  • When N far exceeds K, sparse-graph estimation is severely ill-posed and requires additional structural priors.The passage identifies limited biological and biomedical samples as an example of this regime.Source: §1 · p. 1
  • Expander-like graphs motivate promoting strong global connectivity alongside sparsity because graph filtering represents information diffusion among connected nodes.Source: §1 · p. 1
  • SCoGL augments GLASSO with global connectivity priors derived from Laplacian eigenvalues, including algebraic connectivity and total effective resistance.Source: §1 · p. 1
  • Earlier approaches either imposed a costly semidefinite connectivity constraint or greedily edited edges, requiring many sequential updates and potentially producing suboptimal results.Source: §1 · p. 1
  • Projected gradient descent with Armijo backtracking jointly updates all admissible edge weights, rather than editing edges sequentially.The framework treats the entire adjacency matrix as one optimization variable.Source: §1 · p. 1
  • SCoGL variants generally improve graph recovery in relative error and enhance graph-signal denoising when observations are scarce.Source: §1 · p. 1

2. PRELIMINARIES

The preliminaries define the weighted graph and Laplacian used for graph signal processing, then introduce two complementary spectral views of global connectivity: bottleneck strength and aggregate resistance.

2.1. GSP Definitions

  • An undirected positive-weight graph is represented by a symmetric adjacency matrix, and its combinatorial Laplacian is the degree matrix minus adjacency.Source: §2.1 · p. 1
  • Laplacian eigenpairs serve as graph frequencies and Fourier modes, while the projector J selects the constant-vector subspace.Source: §2.1 · p. 1

2.2. Global Connectivity Measures

  • The Fiedler value λ2(L) measures the weakest global bottleneck and equals zero exactly when the graph is disconnected.Source: §2.1 · p. 1, §2.2 · p. 2
  • Total effective resistance aggregates resistance across node pairs and the nonzero Laplacian spectrum, complementing the Fiedler value’s bottleneck focus.The two measures can favor different optimal graphs.Source: §2.2 · p. 2

3. PROBLEM FORMULATION

SCoGL formulates graph learning with spectral priors that promote connectivity while retaining sparse graph estimates. The section defines Fiedler-mode and full-spectrum regularizers and incorporates them into a convex GLASSO objective optimized over the adjacency matrix.

3.1. Spectral Connectivity Regularizers

  • Six representative priors combine Fiedler-mode or full-spectrum scope with linear, logarithmic, or inverse shaping of Laplacian eigenvalues.The Fiedler-mode prior uses λ2(L); the full-spectrum prior aggregates all nonzero eigenvalues.Source: §3.1 · p. 2
  • All six representative spectral regularizers are convex on the set of connected graph Laplacians.Source: §3.1 · p. 2

3.2. Connectivity-Regularized Graph Learning Objective

  • The objective combines graph-signal data fidelity, an ℓ1 sparsity penalty, and a spectral connectivity regularizer, with sparsity and connectivity strengths controlled by μ and γ.The feasible adjacency matrix W maps linearly to a combinatorial graph Laplacian.Source: §3.2 · pp. 2–3
  • Under scarce data, tested concave sparsity penalties tended to produce excessively large edge weights and worse recovery than the ℓ1 penalty.Source: §3.2 · p. 2
  • The full-spectrum linear regularizer duplicates the sparsity term and is excluded as a separate variant, while the full-spectrum inverse regularizer is proportional to total effective resistance.Source: §3.2 · p. 3

3.3. Projected-Gradient Optimization

  • PGD optimizes W because projection onto the adjacency cone has a closed form, and maps Laplacian-domain gradients into W-space using the adjoint of the Laplacian transformation.Source: §3.3 · p. 3
  • For Fiedler-mode priors, a simple λ2(L) gives a gradient using its unit-norm eigenvector; when ρ is nondifferentiable, an eigenspace-based subgradient is available.Source: §3.3 · p. 3
  • Each update combines data-fidelity, connectivity, and sparsity gradients, projects W back into the adjacency cone, and uses Armijo backtracking; dense iterations have O(N^3) complexity.The stated overall complexity is O(TPGN^3) with O(N^2) memory.Source: §3.3 · p. 3

4. EXPERIMENTS

The experiments evaluate SCoGL on weighted Erdős–Rényi graphs across sample ratios and on denoising in a severely undersampled setting. Connectivity-regularized variants improve graph recovery and denoising relative to the unregularized framework and baselines.

4.1. Experimental Setup

  • The study uses weighted Erdős–Rényi graphs with 100 nodes, edge probability 0.15, and sample ratios K/N from 0.1 to 1.0.It uses 10 validation graphs and 10 test graphs, with shared graph and signal realizations across methods at each ratio.Source: §4.1 · p. 3
  • The comparison includes GLASSO, CLIME, five graph-learning baselines, and five SCoGL variants, with SCoGL-0 removing only the connectivity term.SCoGL-0 retains the CGL-constrained GLASSO objective and PGD solver, so its comparison with regularized variants isolates the connectivity prior.Source: §4.1 · pp. 3–4

4.2. Graph Recovery

  • At K/N = 0.1, connectivity-regularized variants reduce RE by 10.9%–15.5% versus SCoGL-0, and plotted variants outperform it across all tested sample ratios.The graph-recovery comparison is reported alongside the Table 2 results at K/N = 0.1.Source: Table 2 · p. 4, §4.2 · p. 4

4.3. Downstream Graph-Signal Denoising

  • SCoGL-LogDet has the lowest non-oracle NMSE at both noise levels: 0.3474 at σ = 0.2 and 0.6858 at σ = 0.4.SCoGL-R is second, while GLENE is the strongest baseline at both noise levels.Source: Table 2 · p. 4, §4.3 · p. 4

4.2. Graph Recovery

  • Parameters are selected on validation graphs after excluding estimates with mean edge density above 0.25, using the lowest remaining mean validation RE.The primary recovery metric is relative Laplacian error, the Frobenius-norm difference between estimated and true Laplacians normalized by the true Laplacian norm.Source: §4.2 · p. 4

4.3. Downstream Graph-Signal Denoising

  • At both noise levels, SCoGL-LogDet improves on SCoGL-0, closing 29.8% and 44.4% of the corresponding unregularized-to-oracle NMSE gaps.The respective comparisons are 0.3535 to 0.3474 at σ = 0.2 and 0.7102 to 0.6858 at σ = 0.4.Source: §4.3 · p. 4

5. CONCLUSION

SCoGL addresses scarce-data graph learning by adding Laplacian spectral connectivity priors to a combinatorial-Laplacian-constrained GLASSO objective. Experiments report more accurate graph recovery and improved graph-signal denoising under severe data scarcity.

5. CONCLUSION

  • When observations are scarce relative to signal dimension, the paper motivates additional structural priors for reliable graph estimation.The regime is described as K ≪ N.Source: §5 · p. 4
  • SCoGL adds a family of Laplacian-eigenvalue connectivity priors, including Fiedler-value and total-effective-resistance cases, to a constrained GLASSO objective.The method derives gradients and jointly optimizes adjacency matrix W with projected gradient descent and Armijo backtracking.Source: §5 · p. 4
  • Experiments report that spectral connectivity regularization improves graph recovery and graph-signal denoising under severe data scarcity.Source: §5 · p. 4

COMPLIANCE WITH ETHICAL STANDARDS

The study is a numerical simulation and did not require ethical approval.

COMPLIANCE WITH ETHICAL STANDARDS

Loading 2609.27278v1…