基于谱连通性先验的稀缺数据图学习

# Graph Learning with Spectral Connectivity Priors for Scarce Data
Source: [https://arxiv.org/html/2609.27278](https://arxiv.org/html/2609.27278)
Bahar OveisgharanBingyan Zou⋆Gene CheungH\. Vicky Zhao⋆Feifei Gao⋆

###### Abstract

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\.

###### Index Terms:

Graph learning, graph spectral theory

††address:⋆Tsinghua University, China†York University, Canada## 1Introduction

A crucial prerequisite forgraph signal processing\(GSP\)\[[20](https://arxiv.org/html/2609.27278#bib.bib14),[3](https://arxiv.org/html/2609.27278#bib.bib13),[15](https://arxiv.org/html/2609.27278#bib.bib28)\]—the study of mathematical tools such as transforms and wavelets that process discrete signals on finite graphs—is the construction of an underlying graph𝒢\{\\mathcal\{G\}\}that encodes pairwise relationships appropriately\. For asparsegraph𝒢\{\\mathcal\{G\}\}withNNnodes and𝒪⁡\(N\)\{\\mathcal\{O\}\}\(N\)edges specified by Laplacian𝐋∈ℝN×N\{\\mathbf\{L\}\}\\in\\mathbb\{R\}^\{N\\times N\}, filtering operations such as𝐋𝐱\{\\mathbf\{L\}\}\{\\mathbf\{x\}\}on graph signal𝐱∈ℝN\{\\mathbf\{x\}\}\\in\\mathbb\{R\}^\{N\}are linear time𝒪⁡\(N\)\{\\mathcal\{O\}\}\(N\)\. Inferring a graph structure from observed data, calledgraph learning, is extensively studied\[[6](https://arxiv.org/html/2609.27278#bib.bib15),[13](https://arxiv.org/html/2609.27278#bib.bib9),[5](https://arxiv.org/html/2609.27278#bib.bib8)\]\. Statistical approaches such as graphical lasso \(GLASSO\)\[[18](https://arxiv.org/html/2609.27278#bib.bib7)\]and CLIME\[[2](https://arxiv.org/html/2609.27278#bib.bib4)\]are popular, and have been extended to specified Laplacian structures\[[7](https://arxiv.org/html/2609.27278#bib.bib10),[28](https://arxiv.org/html/2609.27278#bib.bib16),[26](https://arxiv.org/html/2609.27278#bib.bib25),[19](https://arxiv.org/html/2609.27278#bib.bib26),[22](https://arxiv.org/html/2609.27278#bib.bib27),[27](https://arxiv.org/html/2609.27278#bib.bib19)\]\. Geometric graphs based on feature distances learned from training data are also possible\[[12](https://arxiv.org/html/2609.27278#bib.bib17),[25](https://arxiv.org/html/2609.27278#bib.bib18)\]\. Graphs can also be learned assuming a graph diffusion model over time\[[24](https://arxiv.org/html/2609.27278#bib.bib12)\]\.

However, learning a sparse graph from scarce data, where the signal dimensionNNfar exceeds the number of observationsKK,i\.e\.,K≪NK\\ll N, is severely ill\-posed and challenging\. In such settings, additional structural priors are necessary to regularize graph estimation\. This regime is common in biological and biomedical applications, where high\-dimensional measurements \(e\.g\., gene expression, proteomic, or neuroimaging data\) are often available for only a limited number of samples due to acquisition costs and experimental constraints\[[17](https://arxiv.org/html/2609.27278#bib.bib6)\]\.

To address data scarcity, we introduce a family of global connectivity priors based on Laplacian eigenvalues to provide an inductive bias for graph estimation\. Because graph filtering is information diffusion among connected nodes, sparse graphs with strong global connectivity are desirable in GSP\.Expander graphs111Expander graphs are sparse graphs with strong connectivity and no weak bottlenecks\. Their expansion properties are closely related to the Laplacian spectral gap and, in particular, the algebraic connectivityλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)\[[10](https://arxiv.org/html/2609.27278#bib.bib3)\]\.\[[10](https://arxiv.org/html/2609.27278#bib.bib3)\]provide a canonical example of such structures\. Inspired by expander graphs, to promote global connectivity, we augment the classical GLASSO formulation with a general spectral connectivity prior computed from Laplacian eigenvalues, including the algebraic connectivity \(Fiedler value, which is the second Laplacian eigenvalueλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)\)\[[4](https://arxiv.org/html/2609.27278#bib.bib21)\]and the total effective resistance\[[14](https://arxiv.org/html/2609.27278#bib.bib1)\]\.

Prior work has incorporated connectivity into graph learning\. Constraining a graph to be connected by imposing a positive lower bound onλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)was proposed in\[[23](https://arxiv.org/html/2609.27278#bib.bib11)\], but the resulting semi\-definite program \(SDP\) is computationally expensive\. Recently,\[[21](https://arxiv.org/html/2609.27278#bib.bib20)\]proposed to augment GLASSO with a Fiedler value maximization term,−λ2​\(𝐋\)\-\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\), for the scarce\-data regime and greedily select one edge at a time for weight reduction or removal\. This heuristic edge\-wise strategy does not jointly optimize all graph weights and requires many sequential updates, making it suboptimal and time\-consuming\.

In contrast, we proposespectral connectivity\-regularized graph learning\(SCoGL\), a framework that accommodates a family of global connectivity regularizers, where the Fiedler penalty is a special case\. The resulting optimization problems are convex, allowing SCoGL to obtain globally optimal solutions, where the entire adjacency matrix𝐖\{\\mathbf\{W\}\}is treated as a single optimization variable\. We derive the gradients for several representative regularizers, including the Fiedler value\[[4](https://arxiv.org/html/2609.27278#bib.bib21)\]and total effective resistance\[[14](https://arxiv.org/html/2609.27278#bib.bib1)\], and develop aprojected gradient descent\(PGD\) algorithm with Armijo backtracking\[[1](https://arxiv.org/html/2609.27278#bib.bib2)\]that jointly updates all admissible edge weights at each iteration\. Instead of sequential edge editing, these joint full\-matrix updates enable efficient optimization\.

Experimental results in theK≪NK\\ll Ndata regime show that the proposed SCoGL variants generally improve graph recovery in terms of relative error\. Moreover, when the learned graphs are used for downstream filtering tasks such as graph signal denoising, our proposed global connectivity prior enhances performance when signal observations are scarce\.

## 2Preliminaries

### 2\.1GSP Definitions

A positive graph𝒢⁡\(𝒱,ℰ,𝐖\)\{\\mathcal\{G\}\}\(\{\\mathcal\{V\}\},\{\\mathcal\{E\}\},\{\\mathbf\{W\}\}\)is defined by a node set𝒱=\{1,…,N\}\{\\mathcal\{V\}\}=\\\{1,\\ldots,N\\\}and an edge setℰ\{\\mathcal\{E\}\}, where\(i,j\)∈ℰ\(i,j\)\\in\{\\mathcal\{E\}\}means nodesi,j∈𝒱i,j\\in\{\\mathcal\{V\}\}are connected with positive weightwi,j=Wi,j∈ℝ\+w\_\{i,j\}=W\_\{i,j\}\\in\\mathbb\{R\}\_\{\+\}\. We assume edges are undirected, and thusadjacency matrix𝐖∈ℝN×N\{\\mathbf\{W\}\}\\in\\mathbb\{R\}^\{N\\times N\}is symmetric\. Thecombinatorial graph Laplacian \(CGL\)is defined as𝐋≜diag⁡\(𝐖𝟏\)−𝐖∈ℝN×N\.\{\\mathbf\{L\}\}\\triangleq\\mathrm\{diag\}\(\{\\mathbf\{W\}\}\{\\mathbf\{1\}\}\)\-\{\\mathbf\{W\}\}\\in\\mathbb\{R\}^\{N\\times N\}\.By construction,𝐋𝟏=𝟎\{\\mathbf\{L\}\}\{\\mathbf\{1\}\}=\{\\mathbf\{0\}\}, while𝐋\{\\mathbf\{L\}\}is real symmetric positive semidefinite \(PSD\)\[[3](https://arxiv.org/html/2609.27278#bib.bib13)\]and thus admits the eigen\-decomposition𝐋=𝐕​𝚲​𝐕⊤\{\\mathbf\{L\}\}=\{\\mathbf\{V\}\}\{\\boldsymbol\{\\Lambda\}\}\{\\mathbf\{V\}\}^\{\\top\}\[[11](https://arxiv.org/html/2609.27278#bib.bib5)\], where𝚲=diag⁡\(λ1,…,λN\)\{\\boldsymbol\{\\Lambda\}\}=\{\\mathrm\{diag\}\}\(\\lambda\_\{1\},\\ldots,\\lambda\_\{N\}\)with0=λ1≤λ2≤⋯≤λN0=\\lambda\_\{1\}\\leq\\lambda\_\{2\}\\leq\\cdots\\leq\\lambda\_\{N\}\. It is common in GSP to interpret thekk\-th eigenpair\(λk,𝐯k\)\(\\lambda\_\{k\},\{\\mathbf\{v\}\}\_\{k\}\)of𝐋\{\\mathbf\{L\}\}as thekk\-th graph frequency and graph Fourier mode for𝒢\{\\mathcal\{G\}\}\. Let𝐉≜1N​𝟏𝟏⊤\{\\mathbf\{J\}\}\\triangleq\\frac\{1\}\{N\}\{\\mathbf\{1\}\}\{\\mathbf\{1\}\}^\{\\top\}denote the orthogonal projector ontospan​\{𝟏\}\\text\{span\}\\\{\{\\mathbf\{1\}\}\\\}\.

### 2\.2Global Connectivity Measures

The combinatorial graph Laplacian’s second smallest eigenvalue,λ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\), is theFiedler value, also known as algebraic connectivity\[[4](https://arxiv.org/html/2609.27278#bib.bib21),[9](https://arxiv.org/html/2609.27278#bib.bib23)\]\. It satisfiesλ2​\(𝐋\)≥0\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)\\geq 0, with equality if and only if the graph is disconnected\. A unit\-norm eigenvector𝐯2\{\\mathbf\{v\}\}\_\{2\}associated withλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)is called aFiedler vector\. The eigen\-pair\(λ2,𝐯2\)\(\\lambda\_\{2\},\{\\mathbf\{v\}\}\_\{2\}\)characterizes the weakest nonconstant graph Fourier mode and indicates the presence of a global bottleneck of the graph through Cheeger\-type relations\[[4](https://arxiv.org/html/2609.27278#bib.bib21)\]\.

For a connected graph, the effective resistance between nodesiiandjjisri​j≜\(𝐞i−𝐞j\)⊤​𝐋†​\(𝐞i−𝐞j\)r\_\{ij\}\\triangleq\(\{\\mathbf\{e\}\}\_\{i\}\-\{\\mathbf\{e\}\}\_\{j\}\)^\{\\top\}\{\\mathbf\{L\}\}^\{\\dagger\}\(\{\\mathbf\{e\}\}\_\{i\}\-\{\\mathbf\{e\}\}\_\{j\}\), where𝐋†\{\\mathbf\{L\}\}^\{\\dagger\}is the Moore–Penrose pseudoinverse of𝐋\{\\mathbf\{L\}\}\. Thetotal effective resistanceis

Rtot​\(𝐋\)=N​tr​\(𝐋†\)=N​∑k=2N1λk​\(𝐋\)\.R\_\{\\mathrm\{tot\}\}\(\{\\mathbf\{L\}\}\)=N\{\\mathrm\{tr\}\}\(\{\\mathbf\{L\}\}^\{\\dagger\}\)=N\\sum\_\{k=2\}^\{N\}\\frac\{1\}\{\\lambda\_\{k\}\(\{\\mathbf\{L\}\}\)\}\.\(1\)It aggregates the entire nonzero Laplacian spectrum and is particularly sensitive to small eigenvalues\. Accordingly, it has been proposed and studied as a measure of network robustness\[[14](https://arxiv.org/html/2609.27278#bib.bib1),[8](https://arxiv.org/html/2609.27278#bib.bib22)\]\.

The two measures capture complementary aspects of global connectivity\. The Fiedler value quantifies the weakest global bottleneck, whereas the total effective resistance aggregates resistance across all node pairs, reflecting path length, edge strength, and path redundancy\. As observed in\[[8](https://arxiv.org/html/2609.27278#bib.bib22)\], maximizing the Fiedler value and minimizing the total effective resistance can yield different optimal graphs\. We therefore consider both views in our framework\.

## 3Problem Formulation

### 3\.1Spectral Connectivity Regularizers

Building on the global connectivity measures reviewed in Section[2\.2](https://arxiv.org/html/2609.27278#S2.SS2), we construct connectivity regularizers using two spectral scopes: theFiedler mode, i\.e\., theweakestnonconstant graph Fourier mode, characterized byλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\), and thefull spectrum\. The Fiedler\-mode regularizer depends only onλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\), whereas the full\-spectrum regularizer aggregates all nonzero Laplacian eigenvalues\.

For a connected graph Laplacian𝐋\{\\mathbf\{L\}\}, we define

Cρweak​\(𝐋\)≜ρ⁡\(λ2​\(𝐋\)\)andCρfull​\(𝐋\)≜∑k=2Nρ⁡\(λk​\(𝐋\)\)C\_\{\\rho\}^\{\\mathrm\{weak\}\}\(\{\\mathbf\{L\}\}\)\\triangleq\\rho\\bigl\(\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)\\bigr\)\\quad\\text\{and\}\\quad C\_\{\\rho\}^\{\\mathrm\{full\}\}\(\{\\mathbf\{L\}\}\)\\triangleq\\sum\_\{k=2\}^\{N\}\\rho\\bigl\(\\lambda\_\{k\}\(\{\\mathbf\{L\}\}\)\\bigr\)\(2\)as the Fiedler\-mode and the full\-spectrum regularizers, respectively\. In \([2](https://arxiv.org/html/2609.27278#S3.E2)\),ρ:ℝ\+⁣\+→ℝ\\rho:\\mathbb\{R\}\_\{\+\+\}\\rightarrow\\mathbb\{R\}is a convex and non\-increasing function\. The non\-increasing property makes minimization favor larger Laplacian eigenvalues, while convexity enables the resulting graph\-learning problem to remain convex\. As representative rather than exhaustive choices, we considerρlin​\(s\)=−s,ρlog​\(s\)=−log⁡s,ρinv​\(s\)=s−1\.\\rho\_\{\\mathrm\{lin\}\}\(s\)=\-s,\\rho\_\{\\log\}\(s\)=\-\\log s,\\rho\_\{\\mathrm\{inv\}\}\(s\)=s^\{\-1\}\.The linear function provides a constant marginal reward for increasing spectral values, whereas the logarithmic and the inverse functions act as barrier\-type penalties near zero with diminishing influence asssincreases\. Combining the two spectrum scopes in \([2](https://arxiv.org/html/2609.27278#S3.E2)\) with these three shaping functions yields the six representative regularizers summarized in Table[1](https://arxiv.org/html/2609.27278#S3.T1)\. The suffixes in Table[1](https://arxiv.org/html/2609.27278#S3.T1)are used throughout the paper\.

Table 1:Representative spectral regularizers and corresponding SCoGL suffixes \(in parentheses\)\.We next establish that regularizers of both spectrum scopes preserve convexity\.

Proposition 1\.Letρ:ℝ\+⁣\+→ℝ\\rho:\\mathbb\{R\}\_\{\+\+\}\\rightarrow\\mathbb\{R\}be convex and nonincreasing\. Then bothCρweakC\_\{\\rho\}^\{\\mathrm\{weak\}\}andCρfullC\_\{\\rho\}^\{\\mathrm\{full\}\}are convex on the set of connected graph Laplacians\.

Proof\.Let𝐔∈ℝN×\(N−1\)\{\\mathbf\{U\}\}\\in\\mathbb\{R\}^\{N\\times\(N\-1\)\}have orthonormal columns spanning𝟏⟂\{\\mathbf\{1\}\}^\{\\perp\}, and define the linear map𝐁⁡\(𝐋\)≜𝐔⊤​𝐋𝐔\.\{\\mathbf\{B\}\}\(\{\\mathbf\{L\}\}\)\\triangleq\{\\mathbf\{U\}\}^\{\\top\}\{\\mathbf\{L\}\}\{\\mathbf\{U\}\}\.For every connected graph Laplacian𝐋\{\\mathbf\{L\}\}, we have𝐁⁡\(𝐋\)≻0\.\{\\mathbf\{B\}\}\(\{\\mathbf\{L\}\}\)\\succ 0\.Let𝝀⁡\(𝐁\)≜\[λ1​\(𝐁\),…,λN−1​\(𝐁\)\]⊤\\boldsymbol\{\\lambda\}\(\{\\mathbf\{B\}\}\)\\triangleq\[\\lambda\_\{1\}\(\{\\mathbf\{B\}\}\),\\ldots,\\lambda\_\{N\-1\}\(\{\\mathbf\{B\}\}\)\]^\{\\top\}, where\{λk​\(𝐁\)\}k=1N−1\\\{\\lambda\_\{k\}\(\{\\mathbf\{B\}\}\)\\\}\_\{k=1\}^\{N\-1\}are eigenvalues of𝐁\{\\mathbf\{B\}\}in non\-decreasing order\.

For the Fiedler\-mode regularizers, we haveλ2​\(𝐋\)=λmin​\(𝐁⁡\(𝐋\)\)\.\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)=\\lambda\_\{\\min\}\\allowbreak\\bigl\(\{\\mathbf\{B\}\}\(\{\\mathbf\{L\}\}\)\\bigr\)\.The minimum eigenvalue is concave sinceλmin​\(𝐁\)=min‖𝐱‖2=1⁡𝐱⊤​𝐁𝐱\\lambda\_\{\\min\}\(\{\\mathbf\{B\}\}\)=\\min\_\{\\\|\{\\mathbf\{x\}\}\\\|\_\{2\}=1\}\\allowbreak\{\\mathbf\{x\}\}^\{\\top\}\{\\mathbf\{B\}\}\{\\mathbf\{x\}\}is the pointwise minimum of linear functions in𝐁\{\\mathbf\{B\}\}\. Since𝐁⁡\(𝐋\)\{\\mathbf\{B\}\}\(\{\\mathbf\{L\}\}\)is linear in𝐋\{\\mathbf\{L\}\},λ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)is concave in𝐋\{\\mathbf\{L\}\}\. Becauseρ\\rhois convex and nonincreasing,Cρweak​\(𝐋\)=ρ⁡\(λ2​\(𝐋\)\)C\_\{\\rho\}^\{\\mathrm\{weak\}\}\(\{\\mathbf\{L\}\}\)=\\rho\(\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)\)is convex by the composition rule\.

For the full\-spectrum regularizers, defineh⁡\(𝐱\)≜∑i=1N−1ρ⁡\(xi\),𝐱∈ℝ\+⁣\+N−1\.h\(\{\\mathbf\{x\}\}\)\\triangleq\\sum\_\{i=1\}^\{N\-1\}\\rho\(x\_\{i\}\),\\allowbreak\{\\mathbf\{x\}\}\\in\\mathbb\{R\}\_\{\+\+\}^\{N\-1\}\.Becauseρ\\rhois convex,hhis convex; moreover,hhis invariant under permutations of its arguments\. From the standard convexity theorem for spectral functions\[[16](https://arxiv.org/html/2609.27278#bib.bib24)\],g⁡\(𝐁\)≜h⁡\(𝝀⁡\(𝐁\)\)=∑i=1N−1ρ⁡\(λi​\(𝐁\)\)g\(\{\\mathbf\{B\}\}\)\\triangleq h\\bigl\(\\boldsymbol\{\\lambda\}\(\{\\mathbf\{B\}\}\)\\bigr\)=\\sum\_\{i=1\}^\{N\-1\}\\rho\\bigl\(\\lambda\_\{i\}\(\{\\mathbf\{B\}\}\)\\bigr\)is convex on the positive definite cone𝕊\+⁣\+N−1\\mathbb\{S\}\_\{\+\+\}^\{N\-1\}\. Consequently,Cρfull​\(𝐋\)=g⁡\(𝐔⊤​𝐋𝐔\)C\_\{\\rho\}^\{\\mathrm\{full\}\}\(\{\\mathbf\{L\}\}\)=g\\bigl\(\{\\mathbf\{U\}\}^\{\\top\}\{\\mathbf\{L\}\}\{\\mathbf\{U\}\}\\bigr\)is convex because it is the composition of a convex function with a linear map\.□\\square

Proposition 1 shows that all six choices in Table[1](https://arxiv.org/html/2609.27278#S3.T1)define convex spectral regularizers on the set of connected graph Laplacians\. We next incorporate a spectral regularizer from this family into the graph\-learning objective\.

### 3\.2Connectivity\-Regularized Graph Learning Objective

To formulate the graph learning objective, we define aHilbert spaceℋ⊂ℝN×N\{\\mathcal\{H\}\}\\subset\\mathbb\{R\}^\{N\\times N\}of real symmetric matrices endowed with the standard inner product⟨𝐀,𝐁⟩=tr​\(𝐀𝐁\)=∑i,jAi,j​Bi,j\\langle\{\\mathbf\{A\}\},\{\\mathbf\{B\}\}\\rangle=\\text\{tr\}\(\{\\mathbf\{A\}\}\{\\mathbf\{B\}\}\)=\\sum\_\{i,j\}A\_\{i,j\}B\_\{i,j\}, for𝐀,𝐁∈ℋ\{\\mathbf\{A\}\},\{\\mathbf\{B\}\}\\in\{\\mathcal\{H\}\}\. For positive and undirected graphs, define theconvex conesinℋ\{\\mathcal\{H\}\}of adjacency and CGL matrices as

𝒲\\displaystyle\{\\mathcal\{W\}\}≜\{𝐖∈ℋ∣Wi​j≥0,i≠j,Wi​i=0\}\\displaystyle\\triangleq\\\{\{\\mathbf\{W\}\}\\in\{\\mathcal\{H\}\}\\mid W\_\{ij\}\\geq 0,\\ i\\neq j,\\ W\_\{ii\}=0\\\}\(3\)andℒ\\displaystyle\\text\{and\}\\quad\{\\mathcal\{L\}\}≜\{𝐋∈ℋ∣𝐋𝟏=𝟎,Li​j≤0,i≠j\},\\displaystyle\\triangleq\\\{\{\\mathbf\{L\}\}\\in\{\\mathcal\{H\}\}\\mid\{\\mathbf\{L\}\}\{\\mathbf\{1\}\}=\{\\mathbf\{0\}\},\\ L\_\{ij\}\\leq 0,\\ i\\neq j\\\},respectively\. Define the linear transformation𝒯:ℋ→ℋ\{\\mathcal\{T\}\}:\{\\mathcal\{H\}\}\\to\{\\mathcal\{H\}\}by𝒯⁡\(𝐖\)≜diag⁡\(𝐖𝟏\)−𝐖\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}\)\\triangleq\{\\mathrm\{diag\}\}\(\{\\mathbf\{W\}\}\{\\mathbf\{1\}\}\)\-\{\\mathbf\{W\}\}\. Since𝒯\{\\mathcal\{T\}\}maps𝒲\{\\mathcal\{W\}\}ontoℒ\{\\mathcal\{L\}\}, we parameterize𝐋=𝒯⁡\(𝐖\)\{\\mathbf\{L\}\}=\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}\)\.

To define the objective function, givenKKzero\-mean graph\-signal observations, let𝐗≜\[𝐱1,…,𝐱K\]∈ℝN×K\{\\mathbf\{X\}\}\\triangleq\[\{\\mathbf\{x\}\}\_\{1\},\\ldots,\{\\mathbf\{x\}\}\_\{K\}\]\\in\\mathbb\{R\}^\{N\\times K\}and𝐒≜𝐗𝐗⊤/K\{\\mathbf\{S\}\}\\triangleq\{\\mathbf\{X\}\}\{\\mathbf\{X\}\}^\{\\top\}/K\. We augment the CGL\-constrained GLASSO objective, which combines the Gaussian negative log\-likelihood andℓ1\\ell\_\{1\}penalty222We also tested concave sparsity penalties as in\[[26](https://arxiv.org/html/2609.27278#bib.bib25)\]\. Under scarce data, they tended to produce a few excessively large edge weights, resulting in worse recovery performance than theℓ1\\ell\_\{1\}penalty\.with a spectral connectivity regularizer:

min𝐖∈𝒲⁡⟨𝐒,𝐋⟩−logdet\(𝐋\+𝐉\)⏟data fidelity\+μ​‖𝐖‖1⏟sparsity\+γ​C​\(𝐋\)⏟global connectivity\\min\_\{\{\\mathbf\{W\}\}\\in\{\\mathcal\{W\}\}\}\\underbrace\{\\left\\langle\{\\mathbf\{S\}\},\{\\mathbf\{L\}\}\\right\\rangle\-\\log\\det\(\{\\mathbf\{L\}\}\+\{\\mathbf\{J\}\}\)\}\_\{\\text\{data fidelity\}\}\+\\underbrace\{\\mu\\\|\{\\mathbf\{W\}\}\\\|\_\{1\}\}\_\{\\text\{sparsity\}\}\+\\underbrace\{\\gamma C\(\{\\mathbf\{L\}\}\)\}\_\{\\text\{global connectivity\}\}\(4\)whereμ,γ≥0\\mu,\\gamma\\geq 0control the sparsity and connectivity strengths, respectively\. The functionCCdenotes the spectral regularizer defined in Section[3\.1](https://arxiv.org/html/2609.27278#S3.SS1)\. The constraint𝐖∈𝒲\{\\mathbf\{W\}\}\\in\{\\mathcal\{W\}\}ensures that𝐋=𝒯⁡\(𝐖\)∈ℒ\{\\mathbf\{L\}\}=\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}\)\\in\{\\mathcal\{L\}\}is a CGL\. By Proposition 1, all objective terms are convex on their effective domains, and the feasible set is convex\. Therefore, \([4](https://arxiv.org/html/2609.27278#S3.E4)\) is a convex optimization problem\.

In Table[1](https://arxiv.org/html/2609.27278#S3.T1), for𝐖∈𝒲\{\\mathbf\{W\}\}\\in\{\\mathcal\{W\}\}, the full\-spectrum linear regularizerClinfull​\(𝐋\)=−tr⁡\(𝐋\)=−‖𝐖‖1C\_\{\\mathrm\{lin\}\}^\{\\mathrm\{full\}\}\(\{\\mathbf\{L\}\}\)=\-\{\\mathrm\{tr\}\}\(\{\\mathbf\{L\}\}\)=\-\\\|\{\\mathbf\{W\}\}\\\|\_\{1\}has the same form as the sparsity term\. SubstitutingClinfull​\(𝐋\)C\_\{\\mathrm\{lin\}\}^\{\\mathrm\{full\}\}\(\{\\mathbf\{L\}\}\)into \([4](https://arxiv.org/html/2609.27278#S3.E4)\), we have

min𝐖∈𝒲⟨𝐒,𝐋⟩−logdet\(𝐋\+𝐉\)\+\(μ−γ\)∥𝐖∥1\.\\min\_\{\{\\mathbf\{W\}\}\\in\{\\mathcal\{W\}\}\}\\quad\\left\\langle\{\\mathbf\{S\}\},\{\\mathbf\{L\}\}\\right\\rangle\-\\log\\det\(\{\\mathbf\{L\}\}\+\{\\mathbf\{J\}\}\)\+\(\\mu\-\\gamma\)\\\|\{\\mathbf\{W\}\}\\\|\_\{1\}\.\(5\)Thus, this regularizer defaults to the connectivity\-free CGL\-constrained GLASSO problem and is not considered as a separate SCoGL variant\. In addition, the full\-spectrum inverse regularizerCinvfull​\(𝐋\)=tr⁡\(𝐋†\)=Rtot​\(𝐋\)/NC\_\{\\mathrm\{inv\}\}^\{\\mathrm\{full\}\}\(\{\\mathbf\{L\}\}\)=\{\\mathrm\{tr\}\}\(\{\\mathbf\{L\}\}^\{\\dagger\}\)=R\_\{\\mathrm\{tot\}\}\(\{\\mathbf\{L\}\}\)/Nis proportional to total effective resistance and is denoted by SCoGL\-R\.

### 3\.3Projected\-Gradient Optimization

We solve \([4](https://arxiv.org/html/2609.27278#S3.E4)\) usingprojected gradient descent\(PGD\) with the adjacency matrix𝐖\{\\mathbf\{W\}\}as the optimization variable\. This choice is motivated by the projection step: projection onto the CGL coneℒ\{\\mathcal\{L\}\}does not have a simple elementwise closed form, whereas projection onto the adjacency cone𝒲\{\\mathcal\{W\}\}is available in closed form\. Since the data\-fidelity and spectral\-regularization terms, together with their gradients, are naturally expressed in terms of the Laplacian𝐋\{\\mathbf\{L\}\}, we use the adjoint of𝒯\{\\mathcal\{T\}\}to map𝐋\{\\mathbf\{L\}\}\-domain gradients to the𝐖\{\\mathbf\{W\}\}\-domain\.

The adjoint𝒯∗:ℋ→ℋ\{\\mathcal\{T\}\}^\{\*\}:\{\\mathcal\{H\}\}\\rightarrow\{\\mathcal\{H\}\}is characterized by⟨𝒯⁡\(𝐖\),𝐀⟩=⟨𝐖,𝒯∗​\(𝐀\)⟩\\langle\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}\),\{\\mathbf\{A\}\}\\rangle=\\langle\{\\mathbf\{W\}\},\{\\mathcal\{T\}\}^\{\*\}\(\{\\mathbf\{A\}\}\)\\rangleand is given entrywise by\[𝒯∗​\(𝐀\)\]i​j=12​\(Ai​i\+Aj​j\)−Ai​j\.\[\{\\mathcal\{T\}\}^\{\*\}\(\{\\mathbf\{A\}\}\)\]\_\{ij\}=\\frac\{1\}\{2\}\(A\_\{ii\}\+A\_\{jj\}\)\-A\_\{ij\}\.Hence, for a differentiable functionffof𝐋=𝒯⁡\(𝐖\)\{\\mathbf\{L\}\}=\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}\),∇𝐖f​\(𝒯⁡\(𝐖\)\)=𝒯∗​\(∇𝐋f​\(𝐋\)\)\.\\nabla\_\{\{\\mathbf\{W\}\}\}f\(\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}\)\)=\{\\mathcal\{T\}\}^\{\*\}\(\\nabla\_\{\{\\mathbf\{L\}\}\}f\(\{\\mathbf\{L\}\}\)\)\.

We next derive a unified gradient representation for the spectral connectivity regularizers in Section[3\.1](https://arxiv.org/html/2609.27278#S3.SS1)\. For the Fiedler\-mode regularizers, assumingλ2​\(𝐋\)\\lambda\_\{2\}\(\{\\mathbf\{L\}\}\)is simple with unit\-norm eigenvector𝐯2\{\\mathbf\{v\}\}\_\{2\}, we have

∇𝐋Cρweak​\(𝐋\)=ρ′​\(λ2\)​𝐯2​𝐯2⊤\.\\nabla\_\{\{\\mathbf\{L\}\}\}C\_\{\\rho\}^\{\\mathrm\{weak\}\}\(\{\\mathbf\{L\}\}\)=\\rho^\{\\prime\}\(\\lambda\_\{2\}\)\{\\mathbf\{v\}\}\_\{2\}\{\\mathbf\{v\}\}\_\{2\}^\{\\top\}\.\(6\)Ifλ2\\lambda\_\{2\}has multiplicitym\>1m\>1,CρweakC\_\{\\rho\}^\{\\mathrm\{weak\}\}is generally non\-differentiable\. A valid subgradient isρ′​\(λ2\)​𝐄𝐑𝐄⊤\\rho^\{\\prime\}\(\\lambda\_\{2\}\)\{\\mathbf\{E\}\}\{\\mathbf\{R\}\}\{\\mathbf\{E\}\}^\{\\top\}, where the columns of𝐄∈ℝN×m\{\\mathbf\{E\}\}\\in\\mathbb\{R\}^\{N\\times m\}span the Fiedler eigenspace,𝐑⪰𝟎\{\\mathbf\{R\}\}\\succeq\{\\mathbf\{0\}\}, andtr⁡\(𝐑\)=1\{\\mathrm\{tr\}\}\(\{\\mathbf\{R\}\}\)=1\. The rank\-one form in \([6](https://arxiv.org/html/2609.27278#S3.E6)\) is recovered by setting𝐑=𝐚𝐚⊤\{\\mathbf\{R\}\}=\{\\mathbf\{a\}\}\{\\mathbf\{a\}\}^\{\\top\}and𝐯2=𝐄𝐚\{\\mathbf\{v\}\}\_\{2\}=\{\\mathbf\{E\}\}\{\\mathbf\{a\}\}for any unit\-norm vector𝐚\{\\mathbf\{a\}\}\.

For the full\-spectrum regularizers, we have

∇𝐋Cρfull​\(𝐋\)=∑k=2Nρ′​\(λk\)​𝐯k​𝐯k⊤\.\\nabla\_\{\{\\mathbf\{L\}\}\}C\_\{\\rho\}^\{\\mathrm\{full\}\}\(\{\\mathbf\{L\}\}\)=\\sum\_\{k=2\}^\{N\}\\rho^\{\\prime\}\(\\lambda\_\{k\}\)\{\\mathbf\{v\}\}\_\{k\}\{\\mathbf\{v\}\}\_\{k\}^\{\\top\}\.\(7\)
Equations \([6](https://arxiv.org/html/2609.27278#S3.E6)\) and \([7](https://arxiv.org/html/2609.27278#S3.E7)\) provide the \(sub\)gradient of connectivity regularizers needed to form the objective update\. At iterationtt, let𝐋t=𝒯⁡\(𝐖\(t\)\)\{\\mathbf\{L\}\}\_\{t\}=\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}^\{\(t\)\}\),𝐀t=𝐋t\+𝐉\{\\mathbf\{A\}\}\_\{t\}=\{\\mathbf\{L\}\}\_\{t\}\+\{\\mathbf\{J\}\},𝐄off≜𝟏𝟏⊤−𝐈\{\\mathbf\{E\}\}\_\{\\mathrm\{off\}\}\\triangleq\{\\mathbf\{1\}\}\{\\mathbf\{1\}\}^\{\\top\}\-\{\\mathbf\{I\}\}, and𝐇t∈∂𝐋C⁡\(𝐋t\)\{\\mathbf\{H\}\}\_\{t\}\\in\\partial\_\{\\mathbf\{L\}\}C\(\{\\mathbf\{L\}\}\_\{t\}\)\. A \(sub\)gradient of the objective function in \([4](https://arxiv.org/html/2609.27278#S3.E4)\) is

𝐆t=𝒯∗​\(𝐒−𝐀t−1\+γ​𝐇t\)\+μ​𝐄off\.\{\\mathbf\{G\}\}\_\{t\}=\{\\mathcal\{T\}\}^\{\*\}\\\!\\left\(\{\\mathbf\{S\}\}\-\{\\mathbf\{A\}\}\_\{t\}^\{\-1\}\+\\gamma\{\\mathbf\{H\}\}\_\{t\}\\right\)\+\\mu\{\\mathbf\{E\}\}\_\{\\mathrm\{off\}\}\.\(8\)
Here,𝒯∗​\(𝐒−𝐀t−1\)\{\\mathcal\{T\}\}^\{\*\}\(\{\\mathbf\{S\}\}\-\{\\mathbf\{A\}\}\_\{t\}^\{\-1\}\),γ​𝒯∗​\(𝐇t\)\\gamma\{\\mathcal\{T\}\}^\{\*\}\(\{\\mathbf\{H\}\}\_\{t\}\), andμ​𝐄off\\mu\{\\mathbf\{E\}\}\_\{\\mathrm\{off\}\}are gradients of the data fidelity, connectivity, and sparsity terms, respectively\. We update the entire matrix𝐖\{\\mathbf\{W\}\}via the PGD step

𝐖~t​\(η\)=Π𝒲​\(𝐖\(t\)−η​𝐆t\),\\widetilde\{\{\\mathbf\{W\}\}\}\_\{t\}\(\\eta\)=\\Pi\_\{\{\\mathcal\{W\}\}\}\\left\(\{\\mathbf\{W\}\}^\{\(t\)\}\-\\eta\{\\mathbf\{G\}\}\_\{t\}\\right\),\(9\)where the projectionΠ𝒲\\Pi\_\{\{\\mathcal\{W\}\}\}sets the diagonal to zero and clips negative off\-diagonal entries to zero, thereby ensuring𝐖~t​\(η\)∈𝒲\\widetilde\{\{\\mathbf\{W\}\}\}\_\{t\}\(\\eta\)\\in\{\\mathcal\{W\}\}, andη\>0\\eta\>0is the step size\. Armijo backtracking\[[1](https://arxiv.org/html/2609.27278#bib.bib2)\]is used to select a step sizeηt\>0\\eta\_\{t\}\>0satisfying the sufficient\-decrease condition, after which𝐖\(t\+1\)=𝐖~t​\(ηt\)\{\\mathbf\{W\}\}^\{\(t\+1\)\}=\\widetilde\{\{\\mathbf\{W\}\}\}\_\{t\}\(\\eta\_\{t\}\)\. Iterations terminate when the projected\-gradient residual and relative objective change fall below prescribed tolerances\. The complete procedure of the proposed SCoGL algorithm is summarized in Algorithm[1](https://arxiv.org/html/2609.27278#alg1)\.

Algorithm 1Spectral Connectivity\-Regularized Graph Learning0:Sample covariance

𝐒\{\\mathbf\{S\}\}, parameters

μ,γ\\mu,\\gamma, connectivity regularizer

CC, initialization

𝐖\(0\)∈𝒲\{\\mathbf\{W\}\}^\{\(0\)\}\\in\{\\mathcal\{W\}\}, max iteration

TPGT\_\{\\mathrm\{PG\}\}
0:Estimated adjacency matrix

𝐖^\\widehat\{\{\\mathbf\{W\}\}\}
1:

t←0t\\leftarrow 0
2:while

t<TPGt<T\_\{\\mathrm\{PG\}\}and not convergeddo

3:

𝐋t←𝒯⁡\(𝐖\(t\)\)\{\\mathbf\{L\}\}\_\{t\}\\leftarrow\{\\mathcal\{T\}\}\(\{\\mathbf\{W\}\}^\{\(t\)\}\),

𝐀t←𝐋t\+𝐉\{\\mathbf\{A\}\}\_\{t\}\\leftarrow\{\\mathbf\{L\}\}\_\{t\}\+\{\\mathbf\{J\}\}
4:Compute

𝐇t∈∂𝐋C⁡\(𝐋t\)\{\\mathbf\{H\}\}\_\{t\}\\in\\partial\_\{\\mathbf\{L\}\}C\(\{\\mathbf\{L\}\}\_\{t\}\)
5:Compute

𝐆t←𝒯∗​\(𝐒−𝐀t−1\+γ​𝐇t\)\+μ​𝐄off\{\\mathbf\{G\}\}\_\{t\}\\leftarrow\{\\mathcal\{T\}\}^\{\*\}\\\!\\left\(\{\\mathbf\{S\}\}\-\{\\mathbf\{A\}\}\_\{t\}^\{\-1\}\+\\gamma\{\\mathbf\{H\}\}\_\{t\}\\right\)\+\\mu\{\\mathbf\{E\}\}\_\{\\mathrm\{off\}\}
6:Select

ηt\\eta\_\{t\}by Armijo backtracking

7:Update

𝐖\(t\+1\)←Π𝒲​\(𝐖\(t\)−ηt​𝐆t\),t←t\+1\{\\mathbf\{W\}\}^\{\(t\+1\)\}\\leftarrow\\Pi\_\{\{\\mathcal\{W\}\}\}\\\!\\left\(\{\\mathbf\{W\}\}^\{\(t\)\}\-\\eta\_\{t\}\{\\mathbf\{G\}\}\_\{t\}\\right\),\\quad t\\leftarrow t\+1
8:endwhile

9:return

𝐖^←𝐖\(t\)\\widehat\{\{\\mathbf\{W\}\}\}\\leftarrow\{\\mathbf\{W\}\}^\{\(t\)\}

Complexity:Computing𝐒\{\\mathbf\{S\}\}requires𝒪⁡\(K​N2\)\\mathcal\{O\}\(KN^\{2\}\)operations once before the iterations begin\. Each iteration is dominated by the factorization of𝐀t∈ℝN×N\{\\mathbf\{A\}\}\_\{t\}\\in\\mathbb\{R\}^\{N\\times N\}and the required spectral computation, giving the worst\-case complexity of𝒪⁡\(N3\)\\mathcal\{O\}\(N^\{3\}\)in a dense implementation, while𝒯\{\\mathcal\{T\}\},𝒯∗\{\\mathcal\{T\}\}^\{\*\}, andΠ𝒲\\Pi\_\{\{\\mathcal\{W\}\}\}require only𝒪⁡\(N2\)\\mathcal\{O\}\(N^\{2\}\)operations\. SinceK<NK<N, forTPGT\_\{\\mathrm\{PG\}\}iterations, the overall complexity is𝒪⁡\(TPG​N3\)\\mathcal\{O\}\(T\_\{\\mathrm\{PG\}\}N^\{3\}\)with𝒪⁡\(N2\)\\mathcal\{O\}\(N^\{2\}\)memory\. The𝒪⁡\(N3\)\\mathcal\{O\}\(N^\{3\}\)per\-iteration complexity of SCoGL is of the same order as or lower than those of\[[7](https://arxiv.org/html/2609.27278#bib.bib10),[28](https://arxiv.org/html/2609.27278#bib.bib16),[26](https://arxiv.org/html/2609.27278#bib.bib25),[18](https://arxiv.org/html/2609.27278#bib.bib7)\]that also address GLASSO\-type objectives\.

## 4Experiments

We evaluate SCoGL using weighted Erdős–Rényi graphs as a representative graph model and graph\-signal denoising as a representative downstream task\. We assess both graph recovery under different sample ratios and denoising performance in a severely undersampled setting\.

### 4\.1Experimental Setup

We test on weighted Erdős–Rényi graphs withN=100N=100nodes and edge probabilityp=0\.15p=0\.15\. Nonzero edge weights are independently sampled from𝒰⁡\[0\.5,1\.5\]\\mathcal\{U\}\[0\.5,1\.5\]\. For each ground\-truth Laplacian𝐋⋆\{\\mathbf\{L\}\}\_\{\\star\}, we generateKKi\.i\.d\. intrinsic Gaussian graph signals𝐱k∼𝒩⁡\(𝟎,𝐋⋆†\)\.\{\\mathbf\{x\}\}\_\{k\}\\sim\\mathcal\{N\}\(\\mathbf\{0\},\{\\mathbf\{L\}\}\_\{\\star\}^\{\\dagger\}\)\.To investigate the effect of sample scarcity, we consider sample ratioK/N∈\{0\.1,0\.2,0\.3,0\.5,0\.7,1\.0\}K/N\\in\\\{0\.1,0\.2,0\.3,0\.5,0\.7,1\.0\\\}\. The dataset contains 10 validation graphs and 10 test graphs\. The validation graphs are used exclusively for objective parameter selection, after which the selected parameters are fixed and evaluated on the test graphs\. At each sample ratio, all methods use the same graph and signal realizations\.

We compare SCoGL against two general precision\-matrix estimators, GLASSO\[[18](https://arxiv.org/html/2609.27278#bib.bib7)\]and CLIME\[[2](https://arxiv.org/html/2609.27278#bib.bib4)\], as well as five graph\-learning baselines: CGL\-BCD\[[7](https://arxiv.org/html/2609.27278#bib.bib10)\], GLENE\[[28](https://arxiv.org/html/2609.27278#bib.bib16)\], NGL\[[26](https://arxiv.org/html/2609.27278#bib.bib25)\], GL\-SigRep\[[5](https://arxiv.org/html/2609.27278#bib.bib8)\]and Kalofolias\[[13](https://arxiv.org/html/2609.27278#bib.bib9)\]\. We evaluate the five connectivity\-regularized instances retained from Section[3\.2](https://arxiv.org/html/2609.27278#S3.SS2): SCoGL\-F, SCoGL\-LogF, SCoGL\-InvF, SCoGL\-R, and SCoGL\-LogDet\.

To isolate the contribution of spectral connectivity regularization, we also include SCoGL\-0 as a within\-framework ablation\. SCoGL\-0 is obtained by settingγ=0\\gamma=0in \([4](https://arxiv.org/html/2609.27278#S3.E4)\)\. It retains the same CGL\-constrained GLASSO objective and PGD solver as the five regularized variants, but removes the connectivity term\. Consequently, comparisons between SCoGL\-0 and SCoGL\-F/LogF/InvF/R/LogDet measure the impact of the connectivity prior while holding the remaining model and optimization procedure fixed\.

### 4\.2Graph Recovery

Our primary recovery metric is the relative Laplacian errorRE≜‖𝐋^−𝐋⋆‖F/‖𝐋⋆‖F\\mathrm\{RE\}\\triangleq\\\|\\widehat\{\{\\mathbf\{L\}\}\}\-\{\\mathbf\{L\}\}\_\{\\star\}\\\|\_\{F\}/\\\|\{\\mathbf\{L\}\}\_\{\\star\}\\\|\_\{F\}, where𝐋^\\widehat\{\{\\mathbf\{L\}\}\}is the estimated Laplacian\.

For each method and sample ratio, we perform an exhaustive grid search on the validation graphs to find the optimal parameter combination\. We first discard parameter configurations whose mean edge density exceeds0\.250\.25, thereby restricting selection to sparse estimates, and then select the remaining configuration with the lowest mean validation RE\. The selected parameters are fixed and evaluated on the 10 test graphs, and the mean test results are reported\.

Figure 1:Mean test relative Laplacian error versus sample ratioK/NK/Nfor selected methods; lower is better\.Table 2:Graph recovery and denoising results atK/N=0\.1K/N=0\.1\. Boldface indicates the best non\-oracle result, and underlining indicates the second\- and third\-best results\.MethodRE↓\\penalty\\ \\downarrowDenoising NMSE↓\\penalty\\ \\downarrowσ=0\.2\\sigma=0\.2σ=0\.4\\sigma=0\.4GLASSO\[[18](https://arxiv.org/html/2609.27278#bib.bib7)\]0\.71850\.39780\.9209CLIME\[[2](https://arxiv.org/html/2609.27278#bib.bib4)\]0\.57180\.36690\.7558NGL\[[26](https://arxiv.org/html/2609.27278#bib.bib25)\]0\.91730\.47031\.4158CGL\-BCD\[[7](https://arxiv.org/html/2609.27278#bib.bib10)\]0\.46510\.35520\.7086GLENE\[[28](https://arxiv.org/html/2609.27278#bib.bib16)\]0\.40180\.34820\.6871GL\-SigRep\[[5](https://arxiv.org/html/2609.27278#bib.bib8)\]0\.37650\.34880\.6888Kalofolias\[[13](https://arxiv.org/html/2609.27278#bib.bib9)\]0\.39870\.35020\.6959SCoGL\-00\.44070\.35350\.7102SCoGL\-F0\.39260\.34860\.6917SCoGL\-LogF0\.38940\.34810\.6905SCoGL\-InvF0\.39090\.34860\.6916SCoGL\-R0\.37740\.34800\.6864SCoGL\-LogDet0\.37230\.34740\.6858Oracle0\.00000\.33300\.6552Fig\.[1](https://arxiv.org/html/2609.27278#S4.F1)compares RE across sample ratiosK/NK/Nfor selected baselines and representative SCoGL variants for visual clarity\. GLASSO, CLIME, and NGL are omitted because they yield substantially higher RE values\. The second column of Table[2](https://arxiv.org/html/2609.27278#S4.T2)reports the RE of all methods in the most undersampled settingK/N=0\.1K/N=0\.1\. Across the evaluated sample ratios, CGL\-BCD has the highest RE, while GL\-SigRep, Kalofolias, SCoGL\-R, and SCoGL\-LogDet achieve comparatively small RE\. AtK/N=0\.1K/N=0\.1, SCoGL\-LogDet achieves the lowest RE of0\.37230\.3723, followed by GL\-SigRep at0\.37650\.3765and SCoGL\-R at0\.37740\.3774\.

The comparison with SCoGL\-0 further demonstrates the effectiveness of connectivity regularization\. AtK/N=0\.1K/N=0\.1, SCoGL\-0 obtains an RE of0\.44070\.4407, whereas the five connectivity\-regularized variants achieve RE values between0\.37230\.3723and0\.39260\.3926, corresponding to reductions of10\.9%10\.9\\%–15\.5%15\.5\\%\. Moreover, the three representative SCoGL variants plotted in Fig\.[1](https://arxiv.org/html/2609.27278#S4.F1)consistently outperform SCoGL\-0 across all evaluated sample ratios\. These consistent gains demonstrate the effectiveness of the proposed spectral connectivity regularizers for graph recovery\.

### 4\.3Downstream Graph\-Signal Denoising

We next evaluate graph\-signal denoising using the graphs learned in Section[4\.2](https://arxiv.org/html/2609.27278#S4.SS2)under the most severely undersampled setting,K/N=0\.1K/N=0\.1\. For each test graph, we generateKdenoise=150K\_\{\\mathrm\{denoise\}\}=150additional clean signals independently of those used for graph learning\. Noisy observations are generated as𝐲=𝐱\+ϵ,ϵ∼𝒩⁡\(𝟎,σ2​𝐈\)\.\{\\mathbf\{y\}\}=\{\\mathbf\{x\}\}\+\\boldsymbol\{\\epsilon\},\\boldsymbol\{\\epsilon\}\\sim\\mathcal\{N\}\(\\mathbf\{0\},\\sigma^\{2\}\{\\mathbf\{I\}\}\)\.We considerσ∈\{0\.2,0\.4\}\\sigma\\in\\\{0\.2,0\.4\\\}\. Given a learned Laplacian𝐋^\\widehat\{\{\\mathbf\{L\}\}\}, denoising is performed using the graph MAP filter𝐱^=\(𝐈\+σ2​𝐋^\)−1​𝐲\.\\widehat\{\{\\mathbf\{x\}\}\}=\\left\(\{\\mathbf\{I\}\}\+\\sigma^\{2\}\\widehat\{\{\\mathbf\{L\}\}\}\\right\)^\{\-1\}\{\\mathbf\{y\}\}\.

To assess the improvement toward the theoretical optimum, we also evaluate the above filter using the ground\-truth Laplacian𝐋⋆\{\\mathbf\{L\}\}\_\{\\star\}, which we refer to as the oracle\. The performance gap between SCoGL and the oracle quantifies the impact of graph estimation on the downstream denoising task\. Performance is measured by the aggregate normalized mean\-squared errorNMSE≜∑k‖𝐱^k−𝐱k‖22/∑k‖𝐱k‖22\\mathrm\{NMSE\}\\triangleq\\sum\_\{k\}\\\|\\widehat\{\{\\mathbf\{x\}\}\}\_\{k\}\-\{\\mathbf\{x\}\}\_\{k\}\\\|\_\{2\}^\{2\}/\\sum\_\{k\}\\\|\{\\mathbf\{x\}\}\_\{k\}\\\|\_\{2\}^\{2\}\.

The last two columns of Table[2](https://arxiv.org/html/2609.27278#S4.T2)report the denoising results\. SCoGL\-LogDet attains the lowest non\-oracle NMSE at both noise levels, achieving0\.34740\.3474atσ=0\.2\\sigma=0\.2and0\.68580\.6858atσ=0\.4\\sigma=0\.4\. SCoGL\-R ranks second with NMSEs of0\.34800\.3480and0\.68640\.6864, respectively\. Both variants outperform all baselines, among which GLENE performs best with NMSEs of0\.34820\.3482and0\.68710\.6871, respectively\.

All five connectivity\-regularized variants improve upon SCoGL\-0 at both noise levels\. In particular, SCoGL\-LogDet reduces the NMSE of SCoGL\-0 from0\.35350\.3535to0\.34740\.3474atσ=0\.2\\sigma=0\.2and from0\.71020\.7102to0\.68580\.6858atσ=0\.4\\sigma=0\.4\. These improvements close29\.8%29\.8\\%and44\.4%44\.4\\%of the corresponding SCoGL\-0\-to\-oracle gaps\. The performance gains at both noise levels indicate that spectral connectivity regularization provides a useful inductive bias for graph filtering when the graph is learned from scarce observations\.

## 5Conclusion

In the data\-scarce regime where the signal dimensionNNfar exceeds the number of observationsKK,i\.e\.,K≪NK\\ll N, reliable graph estimation requires additional structural priors\. To this end, we proposed SCoGL, which augments a combinatorial\-Laplacian\-constrained GLASSO objective with a family of spectral connectivity priors derived from Laplacian eigenvalues, encompassing the Fiedler value and total effective resistance as special cases\. We derived the corresponding gradients and developed a projected gradient descent algorithm with Armijo backtracking that jointly optimizes the graph adjacency matrix𝐖\{\\mathbf\{W\}\}\. Experimental results show that spectral connectivity regularization provides an effective inductive bias under severe data scarcity, yielding both more accurate graph recovery and improved graph signal denoising performance\.

## ACKNOWLEDGMENT

The work of G\. Cheung was supported in part by the Natural Sciences and Engineering Research Council of Canada \(NSERC\) RGPIN\-2025\-06252\.

## COMPLIANCE WITH ETHICAL STANDARDS

This is a numerical simulation study for which no ethical approval was required\.

## References

- \[1\]S\. Boyd and L\. Vandenberghe\(2004\)Convex optimization\.Cambridge\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p5.1),[§3\.3](https://arxiv.org/html/2609.27278#S3.SS3.p6.2)\.
- \[2\]T\. Cai, W\. Liu, and X\. Luo\(2011\)A constrainedℓ1\\ell\_\{1\}minimization approach to sparse precision matrix estimation\.Journal of the American Statistical Association106\(494\),pp\. 594–607\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.4.1.1)\.
- \[3\]G\. Cheung, E\. Magli, Y\. Tanaka, and M\. Ng\(2018\)Graph spectral image processing\.InProceedings of the IEEE,Vol\.106, no\.5,pp\. 907–930\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§2\.1](https://arxiv.org/html/2609.27278#S2.SS1.p1.1)\.
- \[4\]F\. R\. K\. Chung\(1997\)Spectral graph theory\.CBMS Regional Conference Series in Mathematics, Vol\.92,American Mathematical Society\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p3.1),[§1](https://arxiv.org/html/2609.27278#S1.p5.1),[§2\.2](https://arxiv.org/html/2609.27278#S2.SS2.p1.1)\.
- \[5\]X\. Dong, D\. Thanou, P\. Frossard, and P\. Vandergheynst\(2016\)Learning laplacian matrix in smooth graph signal representations\.IEEE Transactions on Signal Processing64\(23\),pp\. 6160–6173\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2016.2602809)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.8.1.1)\.
- \[6\]X\. Dong, D\. Thanou, M\. Rabbat, and P\. Frossard\(2019\)Learning graphs from data: a signal representation perspective\.IEEE Signal Processing Magazine36\(3\),pp\. 44–63\.External Links:[Document](https://dx.doi.org/10.1109/MSP.2018.2887284)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[7\]H\. E\. Egilmez, E\. Pavez, and A\. Ortega\(2017\)Graph learning from data under laplacian and structural constraints\.IEEE Journal of Selected Topics in Signal Processing11\(6\),pp\. 825–841\.External Links:[Document](https://dx.doi.org/10.1109/JSTSP.2017.2726975)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§3\.3](https://arxiv.org/html/2609.27278#S3.SS3.p7.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.6.1.1)\.
- \[8\]W\. Ellens, F\.M\. Spieksma, P\. Van Mieghem, A\. Jamakovic, and R\.E\. Kooij\(2011\)Effective graph resistance\.Linear Algebra and its Applications435\(10\),pp\. 2491–2506\.External Links:ISSN 0024\-3795,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.laa.2011.02.024),[Link](https://www.sciencedirect.com/science/article/pii/S0024379511001443)Cited by:[§2\.2](https://arxiv.org/html/2609.27278#S2.SS2.p2.2),[§2\.2](https://arxiv.org/html/2609.27278#S2.SS2.p3.1)\.
- \[9\]M\. Fiedler\(1973\)Algebraic connectivity of graphs\.Czechoslovak Mathematical Journal23\(2\),pp\. 298–305\.External Links:[Document](https://dx.doi.org/10.21136/CMJ.1973.101168)Cited by:[§2\.2](https://arxiv.org/html/2609.27278#S2.SS2.p1.1)\.
- \[10\]S\. Hoory, N\. Linial, and A\. Wigderson\(2006\)Expander graphs and their applications\.Bulletin of the American Mathematical Society43\(4\),pp\. 439–562\.External Links:[Document](https://dx.doi.org/10.1090/s0273-0979-06-01126-8)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p3.1),[footnote 1](https://arxiv.org/html/2609.27278#footnote1)\.
- \[11\]R\. A\. Horn and C\. R\. Johnson\(2012\)Matrix analysis\.2nd edition,Cambridge University Press,Cambridge, UK\.External Links:ISBN 978\-0\-521\-54823\-6Cited by:[§2\.1](https://arxiv.org/html/2609.27278#S2.SS1.p1.1)\.
- \[12\]W\. Hu, X\. Gao, G\. Cheung, and Z\. Guo\(2020\)Feature graph learning for 3d point cloud denoising\.IEEE Transactions on Signal Processing68\(\),pp\. 2841–2856\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2020.2978617)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[13\]V\. Kalofolias\(2016\)How to learn a graph from smooth signals\.InProceedings of the 19th International Conference on Artificial Intelligence and Statistics,A\. Gretton and C\. C\. Robert \(Eds\.\),Proceedings of Machine Learning Research, Vol\.51,Cadiz, Spain,pp\. 920–929\.External Links:[Link](https://proceedings.mlr.press/v51/kalofolias16.html)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.9.1.1)\.
- \[14\]D\. J\. Klein and M\. Randić\(1993\)Resistance distance\.Journal of Mathematical Chemistry12\(1\),pp\. 81–95\.External Links:[Document](https://dx.doi.org/10.1007/BF01164627)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p3.1),[§1](https://arxiv.org/html/2609.27278#S1.p5.1),[§2\.2](https://arxiv.org/html/2609.27278#S2.SS2.p2.2)\.
- \[15\]G\. Leus, A\. G\. Marques, J\. M\.F\. Moura, A\. Ortega, and D\. I\. Shuman\(2023\)Graph signal processing: history, development, impact, and outlook\.IEEE Signal Processing Magazine40\(4\),pp\. 49–60\.External Links:ISSN 1558\-0792,[Link](http://dx.doi.org/10.1109/MSP.2023.3262906),[Document](https://dx.doi.org/10.1109/msp.2023.3262906)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[16\]A\. S\. Lewis\(1996\)Convex analysis on the hermitian matrices\.SIAM Journal on Optimization6\(1\),pp\. 164–177\.External Links:[Document](https://dx.doi.org/10.1137/0806009),[Link](https://doi.org/10.1137/0806009),https://doi\.org/10\.1137/0806009Cited by:[§3\.1](https://arxiv.org/html/2609.27278#S3.SS1.p7.1)\.
- \[17\]D\. Marbach, J\. C\. Costello, R\. Küffner,et al\.\(2012\)Wisdom of crowds for robust gene network inference\.Nature Methods9\(8\),pp\. 796–804\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p2.1)\.
- \[18\]R\. Mazumder and T\. Hastie\(2012\)The graphical lasso: New insights and alternatives\.Electronic Journal of Statistics6,pp\. 2125 – 2149\.External Links:[Document](https://dx.doi.org/10.1214/12-EJS740),[Link](https://doi.org/10.1214/12-EJS740)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§3\.3](https://arxiv.org/html/2609.27278#S3.SS3.p7.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.3.1.1)\.
- \[19\]Y\. Medvedovsky, E\. Treister, and T\. S Routtenberg\(2024\)Efficient graph Laplacian estimation by proximal Newton\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,Vol\.238,pp\. 1171–1179\.External Links:[Link](https://proceedings.mlr.press/v238/medvedovsky24a.html)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[20\]A\. Ortega, P\. Frossard, J\. Kovacevic, J\. M\. F\. Moura, and P\. Vandergheynst\(2018\)Graph signal processing: overview, challenges, and applications\.InProceedings of the IEEE,Vol\.106, no\. 5,pp\. 808–828\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[21\]B\. Oveisgharan, G\. Cheung, and A\. Eckford\(2026\)Sparse graph learning from sparse data via Fiedler number maximization\.arXiv preprint arXiv:2604\.26132\.Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p4.1)\.
- \[22\]C\. Shi and G\. Mishne\(2024\)Learning Cartesian product graphs with Laplacian constraints\.InProceedings of The 27th International Conference on Artificial Intelligence and Statistics,Vol\.238,pp\. 2521–2529\.External Links:[Link](https://proceedings.mlr.press/v238/shi24a.html)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[23\]M\. Sundin, A\. Venkitaraman, M\. Jansson, and S\. Chatterjee\(2017\)A connectedness constraint for learning sparse graphs\.In2017 25th European Signal Processing Conference \(EUSIPCO\),Vol\.,pp\. 151–155\.External Links:[Document](https://dx.doi.org/10.23919/EUSIPCO.2017.8081187)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p4.1)\.
- \[24\]D\. Thanou, X\. Dong, D\. Kressner, and P\. Frossard\(2017\)Learning heat diffusion graphs\.IEEE Transactions on Signal and Information Processing over Networks3\(3\),pp\. 484–499\.External Links:[Document](https://dx.doi.org/10.1109/TSIPN.2017.2731164)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[25\]C\. Yang, G\. Cheung, and W\. Hu\(2022\)Signed graph metric learning via Gershgorin disc perfect alignment\.IEEE Transactions on Pattern Analysis and Machine Intelligence44\(10\),pp\. 7219–7234\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.2021.3091682)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[26\]J\. Ying, J\. V\. de Miranda Cardoso, and D\. Palomar\(2020\)Nonconvex sparse graph learning under laplacian constrained graphical model\.InAdvances in Neural Information Processing Systems,Vol\.33,pp\. 7101–7113\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2020/file/4ef42b32bccc9485b10b8183507e5d82-Paper.pdf)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§3\.3](https://arxiv.org/html/2609.27278#S3.SS3.p7.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.5.1.1),[footnote 2](https://arxiv.org/html/2609.27278#footnote2)\.
- \[27\]H\. Yokota, H\. Higashi, Y\. Tanaka, and G\. Cheung\(2025\)Efficient learning of balanced signed graphs via iterative linear programming\.InICASSP 2025 \- 2025 IEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\),Vol\.,pp\. 1–5\.External Links:[Document](https://dx.doi.org/10.1109/ICASSP49660.2025.10889822)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1)\.
- \[28\]L\. Zhao, Y\. Wang, S\. Kumar, and D\. P\. Palomar\(2019\)Optimization algorithms for graph laplacian estimation via ADMM and MM\.IEEE Transactions on Signal Processing67\(16\),pp\. 4231–4244\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2019.2925602)Cited by:[§1](https://arxiv.org/html/2609.27278#S1.p1.1),[§3\.3](https://arxiv.org/html/2609.27278#S3.SS3.p7.1),[§4\.1](https://arxiv.org/html/2609.27278#S4.SS1.p2.1),[Table 2](https://arxiv.org/html/2609.27278#S4.T2.1.7.1.1)\.