An official website of the United States government
Abstract Bi-stochastic normalization provides an alternative normalization of graph Laplacians in graph-based data analysis and can be computed efficiently by Sinkhorn–Knopp (SK) iterations. This paper proves the convergence of bi-stochastically normalized graph Laplacian to manifold (weighted-)Laplacian with rates, when $$n$$ data points are i.i.d. sampled from a general $$d$$-dimensional manifold embedded in a possibly high-dimensional space. Under certain joint limit of $$n \to \infty $$ and kernel bandwidth $$\epsilon \to 0$$, the point-wise convergence rate of the graph Laplacian operator (under 2-norm) is proved to be $$ O( n^{-1/(d/2+3)})$$ at finite large $$n$$ up to log factors, achieved at the scaling of $$\epsilon \sim n^{-1/(d/2+3)} $$. When the manifold data are corrupted by outlier noise, we theoretically prove the graph Laplacian point-wise consistency which matches the rate for clean manifold data plus an additional term proportional to the boundedness of the inner-products of the noise vectors among themselves and with data vectors. Motivated by our analysis, which suggests that not exact bi-stochastic normalization but an approximate one will achieve the same consistency rate, we propose an approximate and constrained matrix scaling problem that can be solved by SK iterations with early termination. Numerical experiments support our theoretical results and show the robustness of bi-stochastically normalized graph Laplacian to high-dimensional outlier noise.
more »
« less
Convergence of graph Laplacian with kNN self-tuned kernels
Abstract Kernelized Gram matrix $$W$$ constructed from data points $$\{x_i\}_{i=1}^N$$ as $$W_{ij}= k_0( \frac{ \| x_i - x_j \|^2} {\sigma ^2} ) $$ is widely used in graph-based geometric data analysis and unsupervised learning. An important question is how to choose the kernel bandwidth $$\sigma $$, and a common practice called self-tuned kernel adaptively sets a $$\sigma _i$$ at each point $$x_i$$ by the $$k$$-nearest neighbor (kNN) distance. When $$x_i$$s are sampled from a $$d$$-dimensional manifold embedded in a possibly high-dimensional space, unlike with fixed-bandwidth kernels, theoretical results of graph Laplacian convergence with self-tuned kernels have been incomplete. This paper proves the convergence of graph Laplacian operator $$L_N$$ to manifold (weighted-)Laplacian for a new family of kNN self-tuned kernels $$W^{(\alpha )}_{ij} = k_0( \frac{ \| x_i - x_j \|^2}{ \epsilon \hat{\rho }(x_i) \hat{\rho }(x_j)})/\hat{\rho }(x_i)^\alpha \hat{\rho }(x_j)^\alpha $$, where $$\hat{\rho }$$ is the estimated bandwidth function by kNN and the limiting operator is also parametrized by $$\alpha $$. When $$\alpha = 1$$, the limiting operator is the weighted manifold Laplacian $$\varDelta _p$$. Specifically, we prove the point-wise convergence of $$L_N f $$ and convergence of the graph Dirichlet form with rates. Our analysis is based on first establishing a $C^0$ consistency for $$\hat{\rho }$$ which bounds the relative estimation error $$|\hat{\rho } - \bar{\rho }|/\bar{\rho }$$ uniformly with high probability, where $$\bar{\rho } = p^{-1/d}$$ and $$p$$ is the data density function. Our theoretical results reveal the advantage of the self-tuned kernel over the fixed-bandwidth kernel via smaller variance error in low-density regions. In the algorithm, no prior knowledge of $$d$$ or data density is needed. The theoretical results are supported by numerical experiments on simulated data and hand-written digit image data.
more »
« less
- Award ID(s):
- 2007040
- PAR ID:
- 10335267
- Date Published:
- Journal Name:
- Information and Inference: A Journal of the IMA
- ISSN:
- 2049-8772
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract We study the statistical estimation problem of orthogonal group synchronization and rotation group synchronization. The model is $$Y_{ij} = Z_i^* Z_j^{*T} + \sigma W_{ij}\in{\mathbb{R}}^{d\times d}$$ where $$W_{ij}$$ is a Gaussian random matrix and $$Z_i^*$$ is either an orthogonal matrix or a rotation matrix, and each $$Y_{ij}$$ is observed independently with probability $$p$$. We analyze an iterative polar decomposition algorithm for the estimation of $Z^*$ and show it has an error of $$(1+o(1))\frac{\sigma ^2 d(d-1)}{2np}$$ when initialized by spectral methods. A matching minimax lower bound is further established that leads to the optimality of the proposed algorithm as it achieves the exact minimax risk.more » « less
-
Abstract We establish, as$$\rho \to 0$$, an asymptotic expansion for the minimal Dirichlet energy of$$\mathbb S^2$$-valued maps outside a finite number of particles of size$$\rho $$with fixed centers$$x_j\in {\mathbb R}^3$$, under general anchoring conditions at the particle boundaries. Up to a scaling factor, this expansion is of the form$$ \begin{align*} E_\rho = \sum_j \mu_j -4\pi\rho \sum_{i\neq j} \frac{\langle v_i,v_j\rangle}{|x_i-x_j|} +o(\rho)\,, \end{align*} $$ where$$\mu _j$$is the minimal energy after zooming in at scale$$\rho $$around each particle, and$$v_j\in {\mathbb R}^3$$is determined by the far-field behavior of the corresponding single-particle minimizer. The Coulomb-like interaction in this expansion agrees with theelectrostatic analogy: a linearized approximation commonly used in the physics literature for colloid interactions in nematic liquid crystal. We obtain here for the first time a precise estimate of the energy error introduced by that linearization, by developing new tools that address the lack of convergence rate when zooming in at scale$$\rho $$.more » « less
-
The third Painlevé equation in its generic form, often referred to as Painlevé-III($$D_6$$), is given by $$ \frac{{\rm d}^2u}{{\rm d}x^2} =\frac{1}{u}\left(\frac{{\rm d}u}{{\rm d}x} \right)^2-\frac{1}{x} \frac{{\rm d}u}{{\rm d}x} + \frac{\alpha u^2 + \beta}{x}+4u^3-\frac{4}{u}, \qquad \alpha,\beta \in \mathbb C. $$ Starting from a generic initial solution $$u_0(x)$$ corresponding to parameters $$\alpha$$, $$\beta$$, denoted as the triple $$(u_0(x),\alpha,\beta)$$, we apply an explicit Bäcklund transformation to generate a family of solutions $$(u_n(x),\alpha + 4n,\beta + 4n)$$ indexed by $$n \in \mathbb N$$. We study the large $$n$$ behavior of the solutions $$(u_n(x), \alpha + 4n, \beta + 4n)$$ under the scaling $x = z/n$ in two different ways: (a) analyzing the convergence properties of series solutions to the equation, and (b) using a Riemann-Hilbert representation of the solution $$u_n(z/n)$$. Our main result is a proof that the limit of solutions $$u_n(z/n)$$ exists and is given by a solution of the degenerate Painlevé-III equation, known as Painlevé-III($$D_8$$), $$ \frac{{\rm d}^2U}{{\rm d}z^2} =\frac{1}{U}\left(\frac{{\rm d}U}{{\rm d}z}\right)^2-\frac{1}{z} \frac{{\rm d}U}{{\rm d}z} + \frac{4U^2 + 4}{z}.$$ A notable application of our result is to rational solutions of Painlevé-III($$D_6$$), which are constructed using the seed solution $(1,4m,-4m)$ where $$m \in \mathbb C \setminus \big(\mathbb Z + \frac{1}{2}\big)$$ and can be written as a particular ratio of Umemura polynomials. We identify the limiting solution in terms of both its initial condition at $z = 0$ when it is well defined, and by its monodromy data in the general case. Furthermore, as a consequence of our analysis, we deduce the asymptotic behavior of generic solutions of Painlevé-III, both $$D_6$$ and $$D_8$$ at $z = 0$. We also deduce the large $$n$$ behavior of the Umemura polynomials in a neighborhood of $z = 0$.more » « less
-
Graph neural networks (GNNs) have demonstrated great success in representation learning for graph-structured data. The layer-wise graph convolution in GNNs is shown to be powerful at capturing graph topology. During this process, GNNs are usually guided by pre-defined kernels such as Laplacian matrix, adjacency matrix, or their variants. However, the adoptions of pre-defined kernels may restrain the generalities to different graphs: mismatch between graph and kernel would entail sub-optimal performance. For example, GNNs that focus on low-frequency information may not achieve satisfactory performance when high-frequency information is significant for the graphs, and vice versa. To solve this problem, in this paper, we propose a novel framework - i.e., namely Adaptive Kernel Graph Neural Network (AKGNN) - which learns to adapt to the optimal graph kernel in a unified manner at the first attempt. In the proposed AKGNN, we first design a data-driven graph kernel learning mechanism, which adaptively modulates the balance between all-pass and low-pass filters by modifying the maximal eigenvalue of the graph Laplacian. Through this process, AKGNN learns the optimal threshold between high and low frequency signals to relieve the generality problem. Later, we further reduce the number of parameters by a parameterization trick and enhance the expressive power by a global readout function. Extensive experiments are conducted on acknowledged benchmark datasets and promising results demonstrate the outstanding performance of our proposed AKGNN by comparison with state-of-the-art GNNs. The source code is publicly available at: https://github.com/jumxglhf/AKGNN.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript
- Journal Article:
- https://doi.org/10.1093/imaiai/iaab019
