Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control

# Geometry-Aware Graph Construction viaAdaptive Spectral Bandwidth Control
Source: [https://arxiv.org/html/2609.03306](https://arxiv.org/html/2609.03306)
## Geometry\-Aware Graph Construction via Adaptive Spectral Bandwidth ControlThanks:Accepted at IEEE MLSP 2026\. ©2026 IEEE\. Personal use of this material is permitted\. For any other use, permission must be obtained from the IEEE\.

###### Abstract

Kernelized graph methods — spectral clustering, diffusion maps, and sparse kernel\-regression graphs — that use Gaussian kernels depend on the choice of Gaussian bandwidthσ\\sigma, which governs the spectral character of the local kernel operator\. Whenσ\\sigmais too small, the kernel overestimates local complexity and treats each sample as an independent direction; whenσ\\sigmais too large, the kernel collapses multiple directions together, the condition number diverges, and all geometric discrimination is lost\. We propose a choice of scale to make the spectral complexity of the kernel consistent with the intrinsic complexity of the underlying manifold\. We propose a per\-node bandwidth criterion that operationalizes this principle by jointly matching the kernel’s effective rank to the local intrinsic dimension estimated via minimum spanning tree, anchoring the search in the manifold\-consistent log\-log scaling regime\. We evaluate SSL embeddings from six encoders on CIFAR\-100, showing that adaptive bandwidth consistently improves leave\-one\-out \(LOO\) classification and label propagation \(LP\) accuracy over fixed\-bandwidth methods and competing adaptive methods\.

Ecem Bozkurt, Antonio OrtegaDepartment of Electrical and Computer EngineeringUniversity of Southern California, Los Angeles, CA, USAbozkurt@usc\.edu, aortega@usc\.edu
Index Terms—Graph Signal Processing, Manifold Learning, Self\-Supervised Learning, Representation Geometry, Kernel Methods\.

## 1Introduction

Kernelized graphs as spectral operators\.Modern self\-supervised learning \(SSL\) encoders produce high\-dimensional embeddings that serve as the input to downstream tasks such as classification, retrieval, clustering, and graph\-based learning\. A large family of graph\-based signal processing and learning methods — spectral clustering\[[24](https://arxiv.org/html/2609.03306#bib.bib3)\], Laplacian eigenmaps\[[3](https://arxiv.org/html/2609.03306#bib.bib2)\], diffusion maps\[[7](https://arxiv.org/html/2609.03306#bib.bib6)\], and non\-negative kernel \(NNK\) graphs\[[21](https://arxiv.org/html/2609.03306#bib.bib15)\]— build a similarity graph by applying a Gaussian kernel to pairwise distances and then operating on the resulting matrix\. In all of these methods, the bandwidthσ\\sigmais the main hyperparameter\. We observe that without a careful choice ofσ\\sigma, the local characteristics in kernel space \(e\.g\., its geometric properties estimated by the kernel matrix rank\) can be completely different from the local properties of the linear space \(e\.g\., its local intrinsic dimension\)\. The local kernel matrix can exhibit distinct spectral properties depending on the choice ofσ\\sigma, which impacts downstream tasks\.

![Refer to caption](https://arxiv.org/html/2609.03306v1/gaussian_bandwidth_regimes.png)Fig\. 1:Spectral regimes of the local kernel operator𝐊S​S​\(σ\)\{\\bf K\}\_\{SS\}\(\\sigma\)\.*Left*:σ\\sigmatoo small — identity\-like, flat spectrum,reff≈\|S\|r\_\{\\mathrm\{eff\}\}\\approx\|S\|, graph fragments, no geometric information\.*Center*:σ⋆\\sigma^\{\\star\}— decaying spectrum,reff≈d^r\_\{\\mathrm\{eff\}\}\\approx\\hat\{d\}, well\-conditioned, geometrically informative\.*Right*:σ\\sigmatoo large — rank\-one,κ→∞\\kappa\\to\\infty, all directions collapsed, discrimination lost\.Two spectral failure modes\.Whenσ\\sigmais too small, the Gaussian kernel approaches the identity matrix: each data point appears orthogonal to every other, effective rank is artificially inflated, the graph becomes disconnected, and the spectral operator carries no useful structure\. Whenσ\\sigmais too large, the kernel collapses toward a rank\-one matrix: one eigenvalue dominates, the condition numberκ\\kappadiverges, and the graph becomes a dense clique in which all geometric discrimination is lost \(Fig\.[1](https://arxiv.org/html/2609.03306#S1.F1)\)\. Both regimes are useless for downstream tasks\. Thus, we are interested in identifying where, between those two regimes,σ\\sigmashould be chosen\.

The missing principle\.Existing bandwidth selection methods address parts of the problem but miss a unifying principle \(Table[1](https://arxiv.org/html/2609.03306#S2.T1)\)\. Distance\-driven methods\[[26](https://arxiv.org/html/2609.03306#bib.bib17)\]anchorσ\\sigmato local neighbor distances but do not consider the spectral character of the resulting kernel or distance unreliability at higher dimensions\. Density normalization\[[7](https://arxiv.org/html/2609.03306#bib.bib6)\]corrects sampling bias but does not target spectral stability\. Log\-log scaling methods\[[22](https://arxiv.org/html/2609.03306#bib.bib14),[17](https://arxiv.org/html/2609.03306#bib.bib13)\]exploit the fact that, for data sampled from a low\-dimensional manifold, the total kernel mass follows a predictable scaling law with respect to the bandwidth\. The slope of this relationship can be used to estimate the manifold dimension and to identify scales at which the kernel provides a faithful approximation of the underlying geometry\. Lindenbaum et al\.\[[17](https://arxiv.org/html/2609.03306#bib.bib13)\]further select a bandwidth whose implied dimension matches an external intrinsic\-dimension estimate\. However, these approaches estimate a single global scale for the entire dataset, without adapting to local variations in density or geometry\. None of these methods selectsσ\\sigmaby asking whether the*spectral complexity*— the effective number of independent directions the kernel operator resolves, measured by the effective rank of the resulting kernel, is consistent with the*geometric complexity*of the local neighborhood \(the intrinsic dimensionality of the local data manifold\)\.

A spectral\-complexity principle\.To avoid the spectral failure modes arising from poor choices ofσ\\sigma\(Fig\.[1](https://arxiv.org/html/2609.03306#S1.F1)\), we hypothesize that:*a kernel operates at the correct scale when the complexity revealed through its spectrum is comparable to the intrinsic complexity of the local data manifold*\.

Connection to recent observations\.Three recent results support this principle from different directions\. RankMe\[[11](https://arxiv.org/html/2609.03306#bib.bib10)\]establishes that effective rank — the entropy of the normalized eigenvalue distribution — quantifies the number of active spectral degrees of freedom in a representation\. IDEST\[[19](https://arxiv.org/html/2609.03306#bib.bib11)\]shows that minimum spanning tree \(MST\)\-based intrinsic dimension tracks geometric structure in the high\-dimensional, low\-sample regime where classical estimators break down\. T\-REGS\[[18](https://arxiv.org/html/2609.03306#bib.bib12)\]demonstrates that MST geometry is directly regularizable and prevents spectral collapse\. Together, these results indicate that both spectral complexity and intrinsic dimension carry meaningful information about representation geometry\. We therefore use effective rank as a measure of kernel\-visible complexity and intrinsic dimension as a measure of manifold complexity, and seek bandwidths for which the two are locally consistent\.

ContributionsWe propose \(i\) A per\-node bandwidth criterion to select the scale at which the kernel’s effective rank matches the local intrinsic dimension, placing the kernel operator in the informative scale, and \(ii\) Empirical evidence thatσ\\sigmaadaptation improves graph\-based inference for both sparse and dense graph construction, and that dimMST is the appropriate complexity target under distance concentration\.

## 2Related Work

Table 1:Bandwidth selection strategies\.Bandwidth selection for kernel graph operatorsClosest to our work is Lindenbaum et al\.\[[17](https://arxiv.org/html/2609.03306#bib.bib13)\], where a global bandwidth and a feature\-scaling matrix are selected to match a kernel\-implied dimension to an external estimate\. Our criterion shares the dimension\-matching spirit but differs in that \(i\) it is applied*per node*, \(ii\) it uses effective rank rather than kernel\-implied dimension as the spectral measure, and \(iii\) it estimates intrinsic dimension with dimMST\[[19](https://arxiv.org/html/2609.03306#bib.bib11)\], which is robust to the distance concentration that affects methods that operate on high\-dimensionalℓ2\\ell\_\{2\}\-normalized embeddings\.

Non\-negative kernel \(NNK\) graphsNNK graphs\[[21](https://arxiv.org/html/2609.03306#bib.bib15)\]remove redundant neighbors while preserving local structure through a non\-negative quadratic program in the kernel domain, which can be interpreted as a geometric condition in linear space\. In these methods, which have been used to study SSL and LLM geometry\[[8](https://arxiv.org/html/2609.03306#bib.bib4),[1](https://arxiv.org/html/2609.03306#bib.bib5),[14](https://arxiv.org/html/2609.03306#bib.bib7)\],σ\\sigmais treated as an external hyperparameter\. In contrast, we focus on selecting the bandwidth itself, leaving the NNK optimization unchanged\. While we test ourσ\\sigmaselection criterion to construct NNK graphs, the underlying idea is more general: selectingσ\\sigmaadjusts the relative importance of neighbors through the kernel weights, and is therefore a form of neighborhood selection if the neighborhood is defined explicitly \(as in NNK\) or implicitly through weight decay \(as inkk\-NN\)\.

Effective rank and intrinsic dimension\.We use effective rank\[[20](https://arxiv.org/html/2609.03306#bib.bib16)\]as the spectral complexity measure: it is continuous, entropy\-based, and captures how uniformly information is distributed across all eigenvalue directions — unlike the participation ratio, which relies only on second\-order statistics, or raw rank, which is sensitive to small eigenvalues\. Its recent adoption in RankMe\[[11](https://arxiv.org/html/2609.03306#bib.bib10)\]further confirms that effective rank is a reliable indicator of how many meaningful directions a kernel operator resolves\. Intrinsic dimension of the embedding, on the other hand, indicates how many geometrically relevant directions exist in linear space\. We use MST\-based intrinsic dimension\[[19](https://arxiv.org/html/2609.03306#bib.bib11)\], which is provably consistent under weaker assumptions than Levina–Bickel\[[16](https://arxiv.org/html/2609.03306#bib.bib8)\]or TwoNN\[[10](https://arxiv.org/html/2609.03306#bib.bib9)\], and remains informative under distance concentration\.

## 3Method

### 3\.1Spectral characterization of the bandwidth problem

For node𝐱j\{\\bf x\}\_\{j\}, with candidate neighborsSjS\_\{j\}and𝐱k∈Sj\{\\bf x\}\_\{k\}\\in S\_\{j\}, define the local Gaussian kernel matrix𝐊S​S​\(σ\)\{\\bf K\}\_\{SS\}\(\\sigma\)with entries𝐊j​k=exp\(−∥𝐱j−𝐱k∥2/\(2σ2\)\)\{\\bf K\}\_\{jk\}=\\exp\(\-\\\|\{\\bf x\}\_\{j\}\-\{\\bf x\}\_\{k\}\\\|^\{2\}/\(2\\sigma^\{2\}\)\)\. The intrinsic dimensiond^\\hat\{d\}characterizes how many independent directions exist in the local data manifold, working directly with the𝐱i\{\\bf x\}\_\{i\}, while the effective rankreff​\(𝐊S​S​\(σ\)\)r\_\{\\mathrm\{eff\}\}\(\{\\bf K\}\_\{SS\}\(\\sigma\)\)characterizes how many independent directions the kernel operator actually resolves at a givenσ\\sigma\.

When these two quantities disagree, the kernel is misspecified \(see Fig\.[1](https://arxiv.org/html/2609.03306#S1.F1)\): ifreff<d^r\_\{\\mathrm\{eff\}\}<\\hat\{d\}, the kernel collapses genuinely distinct manifold directions into a single component, neighbors that lie in different directions become indistinguishable, and the graph loses discriminative power\. Ifreff\>d^r\_\{\\mathrm\{eff\}\}\>\\hat\{d\}, the kernel resolves more directions than the manifold has, treating noise and ambient dimensions as genuine structure, causing the graph to fragment along spurious directions\. In both cases, the mismatch corrupts the graph’s geometric fidelity\.

Target regime\.We seek an operating point where the kernel sees a complexity consistent with what the manifold provides, i\.e\.,reff​\(KS​S​\(σ⋆\)\)≈d^r\_\{\\mathrm\{eff\}\}\(K\_\{SS\}\(\\sigma^\{\\star\}\)\)\\approx\\hat\{d\}, where𝐊S​S​\(σ\)\{\\bf K\}\_\{SS\}\(\\sigma\)resolves approximatelyd^i\\hat\{d\}\_\{i\}independent directions, matching the intrinsic dimensionality of the local neighborhood \(see Fig\.[1](https://arxiv.org/html/2609.03306#S1.F1)\(center\)\)\. In this regime, the condition numberκ\\kappais moderate, the graph is well\-conditioned, and the spectral operator captures the local geometry of the manifold\. Next, we introduce the local metrics we use to optimizeσ\\sigma\.

### 3\.2Local neighborhood metrics

Effective rankWe use the effective rank\[[20](https://arxiv.org/html/2609.03306#bib.bib16)\]of𝐊S​S​\(σ\)\{\\bf K\}\_\{SS\}\(\\sigma\):

reff\(𝐊\)=exp\(−∑jpjlogpj\),r\_\{\\mathrm\{eff\}\}\(\{\\bf K\}\)=\\exp\\\!\\Bigl\(\-\\textstyle\\sum\_\{j\}p\_\{j\}\\log p\_\{j\}\\Bigr\),\(1\)wherepj=λj/∑kλkp\_\{j\}=\\lambda\_\{j\}/\\sum\_\{k\}\\lambda\_\{k\}\. From a signal\-processing perspective,reffr\_\{\\mathrm\{eff\}\}quantifies the number ofactive spectral degrees of freedom represented by the kernel operator:reff=1r\_\{\\mathrm\{eff\}\}=1indicates a rank\-one operator \(all energy in one direction\);reff=\|S\|r\_\{\\mathrm\{eff\}\}=\|S\|indicates a uniform operator \(no dominant direction\)\. The target isreff≈d^ir\_\{\\mathrm\{eff\}\}\\approx\\hat\{d\}\_\{i\}: the kernel should resolve as many independent directions as the local manifold has\.

Intrinsic dimension and manifold complexity\.We estimate the local intrinsic dimensiond^i\\hat\{d\}\_\{i\}using the minimum spanning tree \(MST\)\-based estimator \(dimMST\)\[[19](https://arxiv.org/html/2609.03306#bib.bib11)\]on thekcandk\_\{\\mathrm\{cand\}\}neighborhood\. Nearest\-neighbor estimators such as Levina–Bickel\[[16](https://arxiv.org/html/2609.03306#bib.bib8)\]and TwoNN\[[10](https://arxiv.org/html/2609.03306#bib.bib9)\]rely on ratios of inter\-point distances; onℓ2\\ell\_\{2\}\-normalized embeddings, these ratios lose contrast, and the estimators become unstable at higher dimensions, as the distances concentrate\. The dimMST estimator depends on the growth rate of the spanning tree rather than on pairwise distance contrasts\. IDEST\[[19](https://arxiv.org/html/2609.03306#bib.bib11)\]shows that dimMST tracks SSL representation quality in then≈dn\\approx dregime where TwoNN and MLE fail\. Our results \(Fig\.[2](https://arxiv.org/html/2609.03306#S4.F2)\) confirm this empirically: dimMST aligns withreffr\_\{\\mathrm\{eff\}\}atσ⋆\\sigma^\{\\star\}substantially better than Levina–Bickel across all six encoders\.

Manifold scaling consistency and log\-log slope \.Following Singer\[[22](https://arxiv.org/html/2609.03306#bib.bib14)\]and Lindenbaum\[[17](https://arxiv.org/html/2609.03306#bib.bib13)\], on ad^\\hat\{d\}\-dimensional manifold the total kernel energyLi​\(σ\)=∑j,k∈Si𝐊j​k​\(σ\)L\_\{i\}\(\\sigma\)=\\sum\_\{j,k\\in S\_\{i\}\}\{\\bf K\}\_\{jk\}\(\\sigma\)satisfieslog⁡Li≈\(d^/2\)​log⁡σ\+C\\log L\_\{i\}\\approx\(\\hat\{d\}/2\)\\log\\sigma\+Cin the manifold\-consistent regime\.

Letℓi​\(σ\)=d​log⁡Li​\(σ\)/d​log⁡σ\\ell\_\{i\}\(\\sigma\)=d\\log L\_\{i\}\(\\sigma\)/d\\log\\sigmadenote the log\-log slope of the total kernel energy at nodeii, andℓmax=maxσ∈𝒢i⁡ℓi​\(σ\)\\ell\_\{\\max\}=\\max\_\{\\sigma\\in\\mathcal\{G\}\_\{i\}\}\\ell\_\{i\}\(\\sigma\)the peak slope over the local bandwidth grid\. We computeℓmax=maxσ⁡ℓi​\(σ\)\\ell\_\{\\max\}=\\max\_\{\\sigma\}\\ell\_\{i\}\(\\sigma\)to locate the peak of the consistent scaling region\. It penalizes bandwidths that fall outside this linear regime\.

### 3\.3Bandwidth optimization criterion

To achieve our desired bandwidth target, we combine the previously introduced metrics to define an optimality criterion:

Ji​\(σ\)=\|reff​\(KS​S​\(σ\)\)−d^i\|d^i⏟spectral↔manifold complexity\+ℓmax−ℓi​\(σ\)ℓmax⏟scaling consistency,J\_\{i\}\(\\sigma\)=\\underbrace\{\\frac\{\|r\_\{\\mathrm\{eff\}\}\(K\_\{SS\}\(\\sigma\)\)\-\\hat\{d\}\_\{i\}\|\}\{\\hat\{d\}\_\{i\}\}\}\_\{\\text\{spectral\}\\leftrightarrow\\text\{manifold complexity\}\}\+\\underbrace\{\\frac\{\\ell\_\{\\max\}\-\\ell\_\{i\}\(\\sigma\)\}\{\\ell\_\{\\max\}\}\}\_\{\\text\{scaling consistency\}\},\(2\)Both terms are dimensionless and expressed as fractional quantities, placing them on a common scale without requiring an additional balancing coefficient\. The first term drives the effective rank toward the local intrinsic dimension, penalizing both the identity limit \(reff≫d^r\_\{\\mathrm\{eff\}\}\\gg\\hat\{d\}\) and the rank\-one limit \(reff≪d^r\_\{\\mathrm\{eff\}\}\\ll\\hat\{d\}\)\. The second term selects the bandwidth at which the kernel’s energy scaling is most consistent with manifold geometry; note that it has no knowledge of the local intrinsic dimension — it defines a valid operating region, but cannot distinguish between a kernel that sees too few directions and one that sees too many within that region\. The effective\-rank term resolves this ambiguity\.

Our target bandwidth is then

σi⋆=arg​minσ∈𝒢i​Ji​\(σ\),\\sigma\_\{i\}^\{\\star\}=\{\\hbox\{arg\}\}\\min\_\{\\sigma\\in\\mathcal\{G\}\_\{i\}\}J\_\{i\}\(\\sigma\),\(3\)
which we find via a local log\-spaced grid search, with

𝒢i=logspace⁡\(0\.05​di,kmle,3\.0​di,kcand\)\\mathcal\{G\}\_\{i\}=\\mathrm\{logspace\}\(0\.05\\,d\_\{i,k\_\{\\mathrm\{mle\}\}\},\\,3\.0\\,d\_\{i,k\_\{\\mathrm\{cand\}\}\}\)where, in our experiments, we choose\|𝒢\|=12\|\\mathcal\{G\}\|=12\.

The per\-node cost of the bandwidth search isO⁡\(\|𝒢\|⋅kcand2\)O\(\|\\mathcal\{G\}\|\\cdot k\_\{\\mathrm\{cand\}\}^\{2\}\)for kernel matrix construction and energy summation, plusO⁡\(\|𝒢\|⋅kcand2\)O\(\|\\mathcal\{G\}\|\\cdot k\_\{\\mathrm\{cand\}\}^\{2\}\)for the eigenvalue computation, givingO⁡\(\|𝒢\|⋅kcand2\)O\(\|\\mathcal\{G\}\|\\cdot k\_\{\\mathrm\{cand\}\}^\{2\}\)overall sincekcand≪nk\_\{\\mathrm\{cand\}\}\\ll n\. Given the number of grid points,\|𝒢\|\|\\mathcal\{G\}\|, andkcandk\_\{\\mathrm\{cand\}\}, this is a constant\-time operation per node; the total graph construction cost isO⁡\(n⋅kcand2\)O\(n\\cdot k\_\{\\mathrm\{cand\}\}^\{2\}\), dominated in practice by thekk\-NN search\.

### 3\.4Weight sharpening: a secondary refinement

As a secondary refinement, we adjust the edge weights without changing the neighborhood support\. The intuition is that dense regions, where neighbors are close and distances are small, should place more weight on their strongest neighbors, whereas sparse regions should distribute weight more evenly to avoid relying on a single connection\.

The selected bandwidthσi⋆\\sigma\_\{i\}^\{\\star\}already reflects local density: small bandwidths typically occur in dense regions and large bandwidths in sparse ones\. We therefore define a per\-node exponent

pi=clip⁡\(\(σi⋆/σg\)−1,0\.2,2\.0\),p\_\{i\}=\\mathrm\{clip\}\\left\(\(\\sigma\_\{i\}^\{\\star\}/\\sigma\_\{g\}\)^\{\-1\},0\.2,2\.0\\right\),\(4\)whereσg=medianj,σj⋆\\sigma\_\{g\}=\\mathrm\{median\}\_\{j\},\\sigma\_\{j\}^\{\\star\}is the global reference bandwidth\. The clipping operation prevents extreme weight concentration or flattening\. The edge weights are then updated as

wj←wjpi∑kwkpi\.w\_\{j\}\\leftarrow\\frac\{w\_\{j\}^\{p\_\{i\}\}\}\{\\sum\_\{k\}w\_\{k\}^\{p\_\{i\}\}\}\.Whenpi\>1p\_\{i\}\>1, larger weights become more dominant, concentrating support on the strongest neighbors\. Whenpi<1p\_\{i\}<1, the weights become more uniform, distributing support across multiple neighbors\. This only redistributes weight among existing edges and does not modify the graph topology\.

## 4Experiments

### 4\.1Setup

The proposed bandwidth\-selection criterion is applied prior to the graph\-construction procedure and can therefore be used for both dense and sparse graph methods\. For NNK, we solve the standard non\-negative quadratic program at scaleσi⋆\\sigma\_\{i\}^\{\\star\}\. For dense graph baselines, we use Gaussian\-weightedkk\-NN with the same bandwidth\.

Ablation designThe following chain of baselines isolates the contribution of each component:

kNN⏟no​σ→kNN\-​σ⏟σ⋆→kNN\-​σ​\-​α⏟σ⋆\+sharpen→NNK\-fixed⏟global​σ→NNK\-​σ⏟σ⋆\+sparse\\underbrace\{\\text\{kNN\}\}\_\{\\text\{no \}\\sigma\}\\to\\underbrace\{\\text\{kNN\-\}\\sigma\}\_\{\\sigma^\{\\star\}\}\\to\\underbrace\{\\text\{kNN\-\}\\sigma\\text\{\-\}\\alpha\}\_\{\\sigma^\{\\star\}\+\\text\{sharpen\}\}\\to\\underbrace\{\\text\{NNK\-fixed\}\}\_\{\\text\{global \}\\sigma\}\\to\\underbrace\{\\text\{NNK\-\}\\sigma\}\_\{\\sigma^\{\\star\}\+\\text\{sparse\}\}kNN\-σ\\sigmausesσi⋆\\sigma\_\{i\}^\{\\star\}as a per\-node Gaussian bandwidth overkcandk\_\{\\mathrm\{cand\}\}neighbors without sparsification\. Each step adds exactly one component, enabling clean attribution in the LOO results\.

Datasets and embeddings\.Tests use six SSL encoders on CIFAR\-100\[[15](https://arxiv.org/html/2609.03306#bib.bib19)\]: SimCLR\[[5](https://arxiv.org/html/2609.03306#bib.bib20)\], MoCo v2\[[6](https://arxiv.org/html/2609.03306#bib.bib21)\], BYOL\[[12](https://arxiv.org/html/2609.03306#bib.bib22)\], Barlow Twins\[[25](https://arxiv.org/html/2609.03306#bib.bib23)\], VICReg\[[2](https://arxiv.org/html/2609.03306#bib.bib24)\], DINO\[[4](https://arxiv.org/html/2609.03306#bib.bib25)\], from\[[23](https://arxiv.org/html/2609.03306#bib.bib28)\]\. ResNet\-50\[[13](https://arxiv.org/html/2609.03306#bib.bib26)\]:d=512d=512; ViT\-S/16\[[9](https://arxiv.org/html/2609.03306#bib.bib27)\]\(DINO\):d=384d=384\. All embeddingsℓ2\\ell\_\{2\}\-normalized, 3,000 samples \(30 per class\)\.

Hyperparameters\(Table[2](https://arxiv.org/html/2609.03306#S4.T2)\)\. We chose a candidate pool size ofkcand=30k\_\{\\mathrm\{cand\}\}=30to balance neighborhood coverage and computational cost, as larger sizes improve dimMST accuracy but increase the per\-node eigenvalue cost atO⁡\(k3\)O\(k^\{3\}\)\. Using\|𝒢\|=12\|\\mathcal\{G\}\|=12provides sufficient log spacing to identify both the slope peak and the crossing ofreff=d^r\_\{\\mathrm\{eff\}\}=\\hat\{d\}, whilekmle=10k\_\{\\mathrm\{mle\}\}=10anchors the lower bound to the MLE\-implied scale\. To reduce variance in the per\-node dimension estimate, we performnrep=5n\_\{\\mathrm\{rep\}\}=5replications of dimMST, which adds a fixed number of MST computations per node\. In the LP method\[[27](https://arxiv.org/html/2609.03306#bib.bib18)\], we setα=0\.85\\alpha=0\.85, perform 200 iterations with early stopping, and adjust the labeled rows of the transition matrix to zero to ensure they act purely as sources without absorbing beliefs from neighbors\. In our LOO strategy, graphs are completely rebuilt at each sparsity level\. All results are averaged over five independent stratified trials\.

Table 2:Hyperparameter summary\.
### 4\.2Local neighborhood evaluation

We test whether aσ⋆\\sigma^\{\\star\}that optimizes \([2](https://arxiv.org/html/2609.03306#S3.E2)\) produces local kernel matrices whose effective rank is aligned with the local intrinsic dimension\. Fig\.[2](https://arxiv.org/html/2609.03306#S4.F2)plotsreff​\(KS​S\)r\_\{\\mathrm\{eff\}\}\(K\_\{SS\}\)atσ⋆\\sigma^\{\\star\}against the per\-node dimension estimate, comparing dimMST to Levina–Bickel \(LB\) for three encoders\.

Spearman correlations betweenreffr\_\{\\mathrm\{eff\}\}and dimMST range from 0\.88 to 0\.91 on CIFAR\-100 — consistently and substantially higher than the correlations with LB \(0\.43–0\.63\)\. This confirms thatdimMST is the appropriate target: LB intrinsic dimension estimators are degraded by distance concentration on theℓ2\\ell\_\{2\}sphere, while the MST\-based intrinsic dimension estimation remains informative\.

Thefit slopes\(0\.3–0\.5\) are below the idealreff=d^r\_\{\\mathrm\{eff\}\}=\\hat\{d\}line, due to finite\-sample saturation of dimMST forkcand=30k\_\{\\mathrm\{cand\}\}=30\. However, as shown in downstream task experiments, even without an exact matching, consistent*rank ordering*ofd^i\\hat\{d\}\_\{i\}across nodes leads to improved performance\.

![Refer to caption](https://arxiv.org/html/2609.03306v1/NEWfigSUMMARY_ERANK_DIM_CIFAR100.png)Fig\. 2:reff​\(KS​S\)r\_\{\\mathrm\{eff\}\}\(K\_\{SS\}\)atσ⋆\\sigma^\{\\star\}vs\. per\-node intrinsic dimension for 3 encoders \(rows\) for the LB estimator \(Left\) and dimMST \(Right\)\. dimMST aligns substantially better, confirming it as a better complexity target under distance concentration\.
### 4\.3Leave\-One\-Out \(LOO\) classification

LOO directly measures per\-node graph quality \(Fig\.[3](https://arxiv.org/html/2609.03306#S4.F3)\): each node is predicted by a weighted majority vote over its graph neighbors, testing whether the graph’s local spectral structure supports accurate inference\. Fordensegraphs, kNN\-σ\\sigma\-α\\alphaconsistently outperforms plain kNN across all encoders, with the largest gaps at lownpcn\_\{\\mathrm\{pc\}\}where bandwidth choice is most critical\. Forsparsegraphs, NNK\-σ\\sigmaoutperforms NNK\-fixed in all cases\. The gain from NNK\-fixed to NNK\-σ\\sigmashows that geometric sparsification at the correctσ⋆\\sigma^\{\\star\}retains only the geometrically relevant edges\. The ordering kNN<<kNN\-σ\\sigma\-α\\alpha<<NNK\-fixed<<NNK\-σ\\sigmaholds, sigma adaptation helps both dense and sparse graphs, and the sparse solve provides a consistent further gain on top of sigma adaptation\. NNK\-σ\\sigmaleads across all six encoders at all label fractions\.

![Refer to caption](https://arxiv.org/html/2609.03306v1/figSUMMARY_LOO_CIFAR100_afterrebuttal_LindenbaumG.png)Fig\. 3:LOO accuracy vs\. samples per class, CIFAR\-100, six encoders\. NNK\-σ\\sigma\(green\) leads consistently across all encoders\. Sigma adaptation improves both dense graphs \(kNN→\\tokNN\-σ\\sigma\-α\\alpha\) and sparse graphs \(NNK\-fixed→\\toNNK\-σ\\sigma\)\.Table 3:LOO accuracy vs\. dimension target scaleγ\\gamma\.The effective\-rank term targetsreff≈γ​d^r\_\{\\mathrm\{eff\}\}\\approx\\gamma\\hat\{d\}, whereγ=1\\gamma=1scales the dimMST estimate\. Table[3](https://arxiv.org/html/2609.03306#S4.T3)reports LOO accuracy and medianreffr\_\{\\mathrm\{eff\}\}on CIFAR100\-MoCoV2 \(npc=20\) asγ\\gammavaries\. Whenγ<0\.75\\gamma<0\.75, the criterion forcesreffr\_\{\\mathrm\{eff\}\}below the manifold dimension, selecting a bandwidth that is too small: the kernel sees fewer directions than the data has, and LOO accuracy drops\. Whenγ≥1\.0\\gamma\\geq 1\.0, the criterion is robust once the target is at or above the true dimension\. Atγ=2\.0\\gamma=2\.0LOO accuracy drops again\. This confirms the role of the effective\-rank term: it prevents the bandwidth from collapsing to the identity limit\.

### 4\.4Label Propagation \(LP\) accuracy

LP\[[28](https://arxiv.org/html/2609.03306#bib.bib1),[27](https://arxiv.org/html/2609.03306#bib.bib18)\]tests whether the graph’s spectral structure supports semi\-supervised inference over the full graph \(Fig\.[4](https://arxiv.org/html/2609.03306#S4.F4)\)\. On CIFAR\-100 \(100 classes, harder propagation\), NNK\-σ\\sigmaleads across all six encoders at all label fractions\. Gains are most pronounced at≥\\geq10 labels/class, where graph quality becomes the binding constraint rather than label sparsity\. NNK\-σ\\sigma\+α\\alphaprovides a further improvement over NNK\-σ\\sigmaat higher label fractions, suggesting that weight sharpening complements bandwidth selection when sufficient labels are available to propagate beyond immediate neighbors\.

![Refer to caption](https://arxiv.org/html/2609.03306v1/figSUMMARY_LP_CIFAR100_afterrebuttal_LindenbaumG.png)Fig\. 4:LP accuracy vs\. labels per class, six encoders\. NNK\-σ\\sigma\(green\) leads on CIFAR\-100 across all encoders, with gains over NNK\-fixed most pronounced at≥\\geq10 labels per class\.

## 5Conclusion

We have proposed a per\-node bandwidth criterion that matches the kernel’s active spectral degrees of freedom to the local intrinsic dimension of the data manifold consistently produces better\-conditioned graph operators and improves downstream performance\. Our results show thatσ\\sigmaadaptation helps regardless of whether the graph is sparse \(NNK\) or dense \(kk\-NN\): the spectral alignment atσ⋆\\sigma^\{\\star\}improves graph conditioning and inference accuracy for all encoders\. Additionally, geometric sparsification at the selectedσ⋆\\sigma^\{\\star\}provides a consistent additional gain over sigma\-adaptedkk\-NN, confirming that bandwidth selection and sparse graph construction are complementary\. The criterion \([2](https://arxiv.org/html/2609.03306#S3.E2)\) is not specific to NNK graphs\. It can be applied before any Gaussian\-kernel graph construction by running the per\-node grid search and passingσi⋆\\sigma\_\{i\}^\{\\star\}to the downstream method\. The key principle — that kernel effective rank should be consistent with local intrinsic dimension — connects spectral graph signal processing to the geometry of the underlying data manifold\.

## References

- \[1\]\(2024\)Characterizing large language model geometry helps solve toxicity detection and generation\.InProc\. ICML,Cited by:[§2](https://arxiv.org/html/2609.03306#S2.p2.1)\.
- \[2\]A\. Bardeset al\.\(2022\)VICReg: variance\-invariance\-covariance regularization for self\-supervised learning\.InProc\. ICLR,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[3\]M\. Belkin and P\. Niyogi\(2003\)Laplacian eigenmaps for dimensionality reduction and data representation\.Neural Comput\.15\(6\),pp\.1373–1396\.Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p1.1)\.
- \[4\]M\. Caronet al\.\(2021\)Emerging properties in self\-supervised vision transformers\.InProc\. ICCV,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[5\]T\. Chenet al\.\(2020\)A simple framework for contrastive learning of visual representations\.InProc\. ICML,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[6\]X\. Chenet al\.\(2020\)Improved baselines with momentum contrastive learning\.arXiv:2003\.04297\.Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[7\]R\. R\. Coifman and S\. Lafon\(2006\)Diffusion maps\.Appl\. Comput\. Harmon\. Anal\.21\(1\),pp\.5–30\.Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p1.1),[§1](https://arxiv.org/html/2609.03306#S1.p3.1),[Table 1](https://arxiv.org/html/2609.03306#S2.T1.6.3.1.1)\.
- \[8\]R\. Cosentinoet al\.\(2022\)The geometry of self\-supervised learning models and its impact on transfer learning\.arXiv:2209\.08622\.Cited by:[§2](https://arxiv.org/html/2609.03306#S2.p2.1)\.
- \[9\]A\. Dosovitskiyet al\.\(2021\)An image is worth 16x16 words: transformers for image recognition at scale\.InProc\. ICLR,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[10\]E\. Faccoet al\.\(2017\)Estimating the intrinsic dimension of datasets by a minimal neighborhood information\.Sci\. Rep\.7,pp\.12140\.Cited by:[§2](https://arxiv.org/html/2609.03306#S2.p3.1),[§3\.2](https://arxiv.org/html/2609.03306#S3.SS2.p2.1)\.
- \[11\]Q\. Garridoet al\.\(2023\)RankMe: assessing the downstream performance of pretrained self\-supervised representations by their rank\.InProc\. ICML,Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p5.1),[§2](https://arxiv.org/html/2609.03306#S2.p3.1)\.
- \[12\]J\.\-B\. Grillet al\.\(2020\)Bootstrap your own latent: a new approach to self\-supervised learning\.InProc\. NeurIPS,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[13\]K\. Heet al\.\(2016\)Deep residual learning for image recognition\.InProc\. CVPR,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[14\]C\. Hurtadoet al\.\(2022\)Study of manifold geometry using multiscale non\-negative kernel graphs\.arXiv:2210\.17475\.Cited by:[§2](https://arxiv.org/html/2609.03306#S2.p2.1)\.
- \[15\]A\. Krizhevsky\(2009\)Learning multiple layers of features from tiny images\.Technical reportUniv\. Toronto\.Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[16\]E\. Levina and P\. J\. Bickel\(2005\)Maximum likelihood estimation of intrinsic dimension\.InProc\. NeurIPS,Cited by:[§2](https://arxiv.org/html/2609.03306#S2.p3.1),[§3\.2](https://arxiv.org/html/2609.03306#S3.SS2.p2.1)\.
- \[17\]O\. Lindenbaumet al\.\(2020\)Gaussian bandwidth selection for manifold learning and classification\.Data Min\. Knowl\. Discov\.34,pp\.1676–1712\.Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p3.1),[Table 1](https://arxiv.org/html/2609.03306#S2.T1.6.5.1.1),[§2](https://arxiv.org/html/2609.03306#S2.p1.1),[§3\.2](https://arxiv.org/html/2609.03306#S3.SS2.p3.1)\.
- \[18\]J\. Mordacqet al\.\(2025\)T\-REGS: minimum spanning tree regularization for self\-supervised learning\.InProc\. NeurIPS,Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p5.1)\.
- \[19\]J\. Mordacqet al\.\(2026\)IDEST: assessing self\-supervised learning representations via intrinsic dimension\.InProc\. ICML,Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p5.1),[§2](https://arxiv.org/html/2609.03306#S2.p1.1),[§2](https://arxiv.org/html/2609.03306#S2.p3.1),[§3\.2](https://arxiv.org/html/2609.03306#S3.SS2.p2.1)\.
- \[20\]O\. Roy and M\. Vetterli\(2007\)The effective rank: a measure of effective dimensionality\.InProc\. EUSIPCO,pp\.606–610\.Cited by:[§2](https://arxiv.org/html/2609.03306#S2.p3.1),[§3\.2](https://arxiv.org/html/2609.03306#S3.SS2.p1.1)\.
- \[21\]S\. Shekkizhar and A\. Ortega\(2020\)Graph construction from data by non\-negative kernel regression\.InProc\. ICASSP,Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p1.1),[§2](https://arxiv.org/html/2609.03306#S2.p2.1)\.
- \[22\]A\. Singeret al\.\(2009\)Detecting intrinsic slow variables in stochastic dynamical systems by anisotropic diffusion maps\.Proc\. Natl\. Acad\. Sci\.106\(38\),pp\.16090–16095\.Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p3.1),[Table 1](https://arxiv.org/html/2609.03306#S2.T1.6.4.1.1),[§3\.2](https://arxiv.org/html/2609.03306#S3.SS2.p3.1)\.
- \[23\]V\. G\. Turrisi da Costaet al\.\(2022\)Solo\-learn: a library of self\-supervised methods for visual representation learning\.J\. Mach\. Learn\. Res\.23\(56\),pp\.1–6\.Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[24\]U\. von Luxburg\(2007\)A tutorial on spectral clustering\.Stat\. Comput\.17\(4\),pp\.395–416\.Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p1.1)\.
- \[25\]J\. Zbontaret al\.\(2021\)Barlow twins: self\-supervised learning via redundancy reduction\.InProc\. ICML,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p3.1)\.
- \[26\]L\. Zelnik\-Manor and P\. Perona\(2004\)Self\-tuning spectral clustering\.InProc\. NeurIPS,Cited by:[§1](https://arxiv.org/html/2609.03306#S1.p3.1),[Table 1](https://arxiv.org/html/2609.03306#S2.T1.6.2.1.1)\.
- \[27\]D\. Zhouet al\.\(2004\)Learning with local and global consistency\.InProc\. NeurIPS,Cited by:[§4\.1](https://arxiv.org/html/2609.03306#S4.SS1.p4.1),[§4\.4](https://arxiv.org/html/2609.03306#S4.SS4.p1.1)\.
- \[28\]X\. Zhuet al\.\(2003\)Semi\-supervised learning using Gaussian fields and harmonic functions\.InProc\. ICML,pp\.912–919\.Cited by:[§4\.4](https://arxiv.org/html/2609.03306#S4.SS4.p1.1)\.