Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control

• URL: http://arxiv.org/abs/2609.03306v1
• Date: Thu, 03 Sep 2026 02:57:28 GMT
• Title: Geometry-Aware Graph Construction via Adaptive Spectral Bandwidth Control
• Abstract summary: We propose a choice of scale to make the spectral complexity of the kernel consistent with the intrinsic complexity of the underlying manifold.<n>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.
• Score: 21.938486689664856
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• 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 sigma is too small, the kernel overestimates local complexity and treats each sample as an independent direction; when sigma is 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.

Related papers

• Core-KAN: Continuous Vision Kernels with Kolmogorov-Arnold Networks [7.056931885879462]
  Continuous Relative-scale KAN (Core-KAN) is a relative-scale-conditioned continuous convolution operator.<n>A KAN-based generator represents depth-wise kernel bases as continuous coordinate functions.<n>It constructs a compact bank of scale-conditioned kernel responses and interpolates them according to the predicted local scale map.
  arXiv  Detail & Related papers  (2026-08-20T09:12:42Z)
• Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery [5.506184984859199]
  Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales.<n>We address this issue through a multi- kernel formulation that aggregates kernels with different bandwidths.<n>We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model.
  arXiv  Detail & Related papers  (2026-08-09T13:34:27Z)
• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification [52.452902154360565]
  CuBAS is an information-geometric framework for adaptive data selection in supervised classification.<n>A labeled dataset can be viewed as a statistical manifold, on which local curvature, estimated via the ratio of second to first-order observed Fisher information, faithfully encodes the geometric complexity of the data distribution.
  arXiv  Detail & Related papers  (2026-07-03T09:36:02Z)
• Faster 3D Gaussian Splatting Convergence via Structure-Aware Densification [52.517763621139956]
  3D Gaussian Splatting has emerged as a powerful scene representation for real-time novel-view synthesis.<n>Standard adaptive density control relies on screen-space positional gradients.<n>We present a structure-aware densification framework for 3D Gaussian Splatting.
  arXiv  Detail & Related papers  (2026-04-30T15:37:20Z)
• Adaptive Kernel Selection for Kernelized Diffusion Maps [1.7499351967216341]
  We introduce two complementary approaches to adaptive kernel selection for Diffusion Maps.<n>First, we develop a variational outer loop that learns continuous kernel parameters, including bandwidths and mixture weights.<n>Second, we propose an unsupervised cross-validation pipeline that selects kernel families and bandwidths using an eigenvalue-sum.
  arXiv  Detail & Related papers  (2026-04-20T15:22:46Z)
• Consequences of Kernel Regularity for Bandit Optimization [4.655159257282135]
  We show that kernel-based and locally adaptive algorithms can be analyzed within a unified framework.<n>This allows us to derive explicit regret bounds for each kernel family, obtaining novel results in several cases and providing improved analysis for others.
  arXiv  Detail & Related papers  (2025-12-05T18:54:09Z)
• Adaptive Annealed Importance Sampling with Constant Rate Progress [68.8204255655161]
  Annealed Importance Sampling (AIS) synthesizes weighted samples from an intractable distribution. We propose the Constant Rate AIS algorithm and its efficient implementation for $alpha$-divergences.
  arXiv  Detail & Related papers  (2023-06-27T08:15:28Z)
• Local Sample-weighted Multiple Kernel Clustering with Consensus Discriminative Graph [73.68184322526338]
  Multiple kernel clustering (MKC) is committed to achieving optimal information fusion from a set of base kernels. This paper proposes a novel local sample-weighted multiple kernel clustering model. Experimental results demonstrate that our LSWMKC possesses better local manifold representation and outperforms existing kernel or graph-based clustering algo-rithms.
  arXiv  Detail & Related papers  (2022-07-05T05:00:38Z)
• Scalable Variational Gaussian Processes via Harmonic Kernel Decomposition [54.07797071198249]
  We introduce a new scalable variational Gaussian process approximation which provides a high fidelity approximation while retaining general applicability. We demonstrate that, on a range of regression and classification problems, our approach can exploit input space symmetries such as translations and reflections. Notably, our approach achieves state-of-the-art results on CIFAR-10 among pure GP models.
  arXiv  Detail & Related papers  (2021-06-10T18:17:57Z)

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

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