Search

In the (special) smoothing spline problem one considers a variational problem with a quadratic data fidelity penalty and Laplacian regularisation. Higher order regularity can be obtained via replacing the Laplacian regulariser with a poly-Laplacian regulariser. The methodology is readily adapted to graphs and here we consider graph poly-Laplacian regularisation in a fully supervised, non-parametric, noise corrupted, regression problem. In particular, given a dataset $\{x_i\}_{i=1}^n$ and a set of noisy labels $\{y_i\}_{i=1}^n\subset\mathbb{R}$ we let $u_n:\{x_i\}_{i=1}^n\to\mathbb{R}$ be the minimiser of an energy which consists of a data fidelity term and an appropriately scaled graph poly-Laplacian term. When $y_i = g(x_i)+\xi_i$, for iid noise $\xi_i$, and using the geometric random graph, we identify (with high probability) the rate of convergence of $u_n$ to $g$ in the large data limit $n\to\infty$. Furthermore, our rate, up to logarithms, coincides with the known rate of convergence in the usual smoothing spline model.

Given an image $u_0$, the aim of minimising the Mumford-Shah functional is to find a decomposition of the image domain into sub-domains and a piecewise smooth approximation $u$ of $u_0$ such that $u$ varies smoothly within each sub-domain. Since the Mumford-Shah functional is highly non-smooth, regularizations such as the Ambrosio-Tortorelli approximation can be considered which is one of the most computationally efficient approximations of the Mumford-Shah functional for image segmentation. While very impressive numerical results have been achieved in a large range of applications when minimising the functional, no analytical results are currently available for minimizers of the functional in the piecewise smooth setting, and this is the goal of this work. Our main result is the $\Gamma$-convergence of the Ambrosio-Tortorelli approximation of the Mumford-Shah functional for piecewise smooth approximations. This requires the introduction of an appropriate function space. As a consequence of our $\Gamma$-convergence result, we can infer the convergence of minimizers of the respective functionals.

We propose a new framework, called Poisson learning, for graph based semi-supervised learning at very low label rates. Poisson learning is motivated by the need to address the degeneracy of Laplacian semi-supervised learning in this regime. The method replaces the assignment of label values at training points with the placement of sources and sinks, and solves the resulting Poisson equation on the graph. The outcomes are provably more stable and informative than those of Laplacian learning. Poisson learning is efficient and simple to implement, and we present numerical experiments showing the method is superior to other recent approaches to semi-supervised learning at low label rates on MNIST, FashionMNIST, and Cifar-10. We also propose a graph-cut enhancement of Poisson learning, called Poisson MBO, that gives higher accuracy and can incorporate prior knowledge of relative class sizes., Comment: Proceedings of the 37th International Conference on Machine Learning, Online, PMLR 119, 2020

In this work we study statistical properties of graph-based clustering algorithms that rely on the optimization of balanced graph cuts, the main example being the optimization of Cheeger cuts. We consider proximity graphs built from data sampled from an underlying distribution supported on a generic smooth compact manifold $M$. In this setting, we obtain high probability convergence rates for both the Cheeger constant and the associated Cheeger cuts towards their continuum counterparts. The key technical tools are careful estimates of interpolation operators which lift empirical Cheeger cuts to the continuum, as well as continuum stability estimates for isoperimetric problems. To our knowledge the quantitative estimates obtained here are the first of their kind.

Scalings in which the graph Laplacian approaches a differential operator in the large graph limit are used to develop understanding of a number of algorithms for semi-supervised learning; in particular the extension, to this graph setting, of the probit algorithm, level set and kriging methods, are studied. Both optimization and Bayesian approaches are considered, based around a regularizing quadratic form found from an affine transformation of the Laplacian, raised to a, possibly fractional, exponent. Conditions on the parameters defining this quadratic form are identified under which well-defined limiting continuum analogues of the optimization and Bayesian semi-supervised learning problems may be found, thereby shedding light on the design of algorithms in the large graph setting. The large graph limits of the optimization formulations are tackled through $\Gamma-$convergence, using the recently introduced $TL^p$ metric. The small labelling noise limits of the Bayesian formulations are also identified, and contrasted with pre-existing harmonic function approaches to the problem.

The consistency of a nonlocal anisotropic Ginzburg-Landau type functional for data classification and clustering is studied. The Ginzburg-Landau objective functional combines a double well potential, that favours indicator valued function, and the $p$-Laplacian, that enforces regularity. Under appropriate scaling between the two terms minimisers exhibit a phase transition on the order of $\epsilon=\epsilon_n$ where $n$ is the number of data points. We study the large data asymptotics, i.e. as $n\to \infty$, in the regime where $\epsilon_n\to 0$. The mathematical tool used to address this question is $\Gamma$-convergence. In particular, it is proved that the discrete model converges to a weighted anisotropic perimeter.

The Ginzburg-Landau functional is a phase transition model which is suitable for clustering or classification type problems. We study the asymptotics of a sequence of Ginzburg-Landau functionals with anisotropic interaction potentials on point clouds $\Psi_n$ where $n$ denotes the number data points. In particular we show the limiting problem, in the sense of $\Gamma$-convergence, is related to the total variation norm restricted to functions taking binary values; which can be understood as a surface energy. We generalize the result known for isotropic interaction potentials to the anisotropic case and add a result concerning the rate of convergence.