Uniform Convergence Rates for Lipschitz Learning on Graphs

• URL: http://arxiv.org/abs/2111.12370v1
• Date: Wed, 24 Nov 2021 09:44:14 GMT
• Title: Uniform Convergence Rates for Lipschitz Learning on Graphs
• Authors: Leon Bungert, Jeff Calder, Tim Roith
• Abstract summary: Lipschitz learning is a graph-based semi-supervised learning method. We prove uniform convergence rates for solutions of the graph infinity Laplace equation.
• Score: 1.9014535120129339
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Lipschitz learning is a graph-based semi-supervised learning method where one extends labels from a labeled to an unlabeled data set by solving the infinity Laplace equation on a weighted graph. In this work we prove uniform convergence rates for solutions of the graph infinity Laplace equation as the number of vertices grows to infinity. Their continuum limits are absolutely minimizing Lipschitz extensions with respect to the geodesic metric of the domain where the graph vertices are sampled from. We work under very general assumptions on the graph weights, the set of labeled vertices, and the continuum domain. Our main contribution is that we obtain quantitative convergence rates even for very sparsely connected graphs, as they typically appear in applications like semi-supervised learning. In particular, our framework allows for graph bandwidths down to the connectivity radius. For proving this we first show a quantitative convergence statement for graph distance functions to geodesic distance functions in the continuum. Using the "comparison with distance functions" principle, we can pass these convergence statements to infinity harmonic functions and absolutely minimizing Lipschitz extensions.

Related papers

• Improving embedding of graphs with missing data by soft manifolds [51.425411400683565]
  The reliability of graph embeddings depends on how much the geometry of the continuous space matches the graph structure. We introduce a new class of manifold, named soft manifold, that can solve this situation. Using soft manifold for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets.
  arXiv  Detail & Related papers  (2023-11-29T12:48:33Z)
• Generalized Graphon Process: Convergence of Graph Frequencies in Stretched Cut Distance [30.279435887366578]
  sparse graph sequences converge to the trivial graphon under the conventional definition of cut distance. We utilize the concepts of generalized graphons and stretched cut distance to describe the convergence of sparse graph sequences. Our results indicate the possibility of transfer learning between sparse graphs.
  arXiv  Detail & Related papers  (2023-09-11T06:34:46Z)
• Path convergence of Markov chains on large graphs [3.693375843298262]
  We show that as the size of a graph goes to infinity, the random trajectories of the processes converge to deterministic curves on the space of measure-valued graphons. A novel feature of this approach is that it provides a precise exponential convergence rate for the Metropolis chain in a certain limiting regime.
  arXiv  Detail & Related papers  (2023-08-18T00:13:59Z)
• Limits, approximation and size transferability for GNNs on sparse graphs via graphops [44.02161831977037]
  We take a perspective of taking limits of operators derived from graphs, such as the aggregation operation that makes up GNNs. Our results hold for dense and sparse graphs, and various notions of graph limits.
  arXiv  Detail & Related papers  (2023-06-07T15:04:58Z)
• Tight and fast generalization error bound of graph embedding in metric space [54.279425319381374]
  We show that graph embedding in non-Euclidean metric space can outperform that in Euclidean space with much smaller training data than the existing bound has suggested. Our new upper bound is significantly tighter and faster than the existing one, which can be exponential to $R$ and $O(frac1S)$ at the fastest.
  arXiv  Detail & Related papers  (2023-05-13T17:29:18Z)
• Graphon Pooling for Reducing Dimensionality of Signals and Convolutional Operators on Graphs [131.53471236405628]
  We present three methods that exploit the induced graphon representation of graphs and graph signals on partitions of [0, 1]2 in the graphon space. We prove that those low dimensional representations constitute a convergent sequence of graphs and graph signals. We observe that graphon pooling performs significantly better than other approaches proposed in the literature when dimensionality reduction ratios between layers are large.
  arXiv  Detail & Related papers  (2022-12-15T22:11:34Z)
• Gradient flows on graphons: existence, convergence, continuity equations [27.562307342062354]
  Wasserstein gradient flows on probability measures have found a host of applications in various optimization problems. We show that the Euclidean gradient flow of a suitable function of the edge-weights converges to a novel continuum limit given by a curve on the space of graphons.
  arXiv  Detail & Related papers  (2021-11-18T00:36:28Z)
• Continuum Limit of Lipschitz Learning on Graphs [0.0]
  We prove continuum limits of Lipschitz learning using $Gamma$-convergence. We show compactness of functionals which implies convergence of minimizers.
  arXiv  Detail & Related papers  (2020-12-07T15:10:35Z)
• Hamiltonian systems, Toda lattices, Solitons, Lax Pairs on weighted Z-graded graphs [62.997667081978825]
  We identify conditions which allow one to lift one dimensional solutions to solutions on graphs. We show that even for a simple example of a topologically interesting graph the corresponding non-trivial Lax pairs and associated unitary transformations do not lift to a Lax pair on the Z-graded graph.
  arXiv  Detail & Related papers  (2020-08-11T17:58:13Z)
• Graph Pooling with Node Proximity for Hierarchical Representation Learning [80.62181998314547]
  We propose a novel graph pooling strategy that leverages node proximity to improve the hierarchical representation learning of graph data with their multi-hop topology. Results show that the proposed graph pooling strategy is able to achieve state-of-the-art performance on a collection of public graph classification benchmark datasets.
  arXiv  Detail & Related papers  (2020-06-19T13:09:44Z)
• Wasserstein-based Graph Alignment [56.84964475441094]
  We cast a new formulation for the one-to-many graph alignment problem, which aims at matching a node in the smaller graph with one or more nodes in the larger graph. We show that our method leads to significant improvements with respect to the state-of-the-art algorithms for each of these tasks.
  arXiv  Detail & Related papers  (2020-03-12T22:31:59Z)

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.