Improved convergence rate of kNN graph Laplacians: differentiable self-tuned affinity
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918512096706560 |
|---|---|
| author | Cheng, Xiuyuan Tan, Yixuan Wu, Nan |
| author_facet | Cheng, Xiuyuan Tan, Yixuan Wu, Nan |
| contents | In graph-based data analysis, $k$-nearest neighbor ($k$NN) graphs are widely used due to their adaptivity to local data densities. Allowing weighted edges in the graph, the kernelized graph affinity provides a more general type of $k$NN graph where the $k$NN distance is used to set the kernel bandwidth adaptively. In this work, we consider a general class of $k$NN graph where the graph affinity is $W_{ij} = ε^{-d/2} k_0 ( \| x_i - x_j \|^2 / εϕ( \hat ρ(x_i), \hat ρ(x_j) )^2 ) $, with $\hatρ(x)$ being the (rescaled) $k$NN distance at the point $x$, $ϕ$ a symmetric bi-variate function, and $k_0$ a non-negative function on $[0,\infty)$. Under the manifold data setting, where $N$ i.i.d. samples $x_i$ are drawn from a density $p$ on a $d$-dimensional unknown manifold embedded in a high dimensional Euclidean space, we prove the operator pointwise convergence of the $k$NN graph Laplacian to the limiting manifold operator (depending on $p$) at the rate of $O(N^{-2/(d+6)})$, up to a log factor, when $k_0$ and $ϕ$ have $C^3$ regularity and satisfy other technical conditions. This is obtained when $ε\sim N^{-2/(d+6)}$ and $k \sim N^{6/(d+6)}$, both at the optimal order to balance the theoretical bias and variance errors. Our improved convergence rate is based on a refined analysis of the $k$NN estimator, which can be of independent interest. We validate our theory by numerical experiments on simulated data. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23212 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Improved convergence rate of kNN graph Laplacians: differentiable self-tuned affinity Cheng, Xiuyuan Tan, Yixuan Wu, Nan Machine Learning Statistics Theory In graph-based data analysis, $k$-nearest neighbor ($k$NN) graphs are widely used due to their adaptivity to local data densities. Allowing weighted edges in the graph, the kernelized graph affinity provides a more general type of $k$NN graph where the $k$NN distance is used to set the kernel bandwidth adaptively. In this work, we consider a general class of $k$NN graph where the graph affinity is $W_{ij} = ε^{-d/2} k_0 ( \| x_i - x_j \|^2 / εϕ( \hat ρ(x_i), \hat ρ(x_j) )^2 ) $, with $\hatρ(x)$ being the (rescaled) $k$NN distance at the point $x$, $ϕ$ a symmetric bi-variate function, and $k_0$ a non-negative function on $[0,\infty)$. Under the manifold data setting, where $N$ i.i.d. samples $x_i$ are drawn from a density $p$ on a $d$-dimensional unknown manifold embedded in a high dimensional Euclidean space, we prove the operator pointwise convergence of the $k$NN graph Laplacian to the limiting manifold operator (depending on $p$) at the rate of $O(N^{-2/(d+6)})$, up to a log factor, when $k_0$ and $ϕ$ have $C^3$ regularity and satisfy other technical conditions. This is obtained when $ε\sim N^{-2/(d+6)}$ and $k \sim N^{6/(d+6)}$, both at the optimal order to balance the theoretical bias and variance errors. Our improved convergence rate is based on a refined analysis of the $k$NN estimator, which can be of independent interest. We validate our theory by numerical experiments on simulated data. |
| title | Improved convergence rate of kNN graph Laplacians: differentiable self-tuned affinity |
| topic | Machine Learning Statistics Theory |
| url | https://arxiv.org/abs/2410.23212 |