text: We consider point clouds obtained as random samples of a measure on a Euclidean domain. A graph representing the point cloud is obtained by assigning weights to edges based on the distance between the points they connect. Our goal is to develop mathematical tools needed to study the consistency, as the number of available data points increases, of graph-based machine learning algorithms for tasks such as clustering. In particular, we study when the cut capacity, and more generally total variation, on these graphs is a good approximation of the perimeter (total variation) in the continuum setting. We address this question in the setting of Γ-convergence. We obtain almost optimal conditions on the scaling, as the number of points increases, of the size of the neighborhood over which the points are connected by an edge for the Γ-convergence to hold. Taking of the limit is enabled by a transportation based metric which allows us to suitably compare functionals defined on different point clouds.
  @cite_44: We investigate the limiting description for a finite-difference approximation of a singularly perturbed Allen--Cahn type energy functional. The key issue is to understand the interaction between two small length-scales: the interfacial thickness @math and the mesh size of spatial discretization @math . Depending on their relative sizes, we obtain results in the framework of @math -convergence for the (i) subcritical ( @math ), (ii) critical ( @math ), and (iii) supercritical ( @math ) cases. The first case leads to the same area functional as the spatially continuous case while the third gives the same result as that coming from a ferromagnetic spin energy. The critical case can be regarded as an interpolation between the two.
  @cite_55: Author(s): Gennip, YV; Bertozzi, AL | Abstract: We study Γ-convergence of graph-based Ginzburg–Landau functionals, both the limit for zero diffusive interface parameter e → 0 and the limit for infinite nodes in the graph m → ∞. For general graphs we prove that in the limit e → 0 the graph cut objective function is recovered. We show that the continuum limit of this objective function on 4-regular graphs is related to the total variation seminorm and compare it with the limit of the discretized Ginzburg–Landau functional. For both functionals we also study the simultaneous limit e → 0 and m → ∞, by expressing e as a power of m and taking m → ∞. Finally we investigate the continuum limit for a nonlocal means-type functional on a completely connected graph
  @cite_36: We consider a class of discrete convex functionals which satisfy a (generalized) coarea formula. These functionals, based on submodular interactions, arise in discrete optimization and are known as a large class of problems which can be solved in polynomial time. In particular, some of them can be solved very efficiently by maximal flow algorithms and are quite popular in the image processing community. We study the limit in the continuum of these functionals, show that they always converge to some "crystalline" perimeter total variation, and provide an almost explicit formula for the limiting functional.
summary: In the discrete setting, works related to the @math -convergence of functionals to continuous functionals involving perimeter include @cite_44 , @cite_55 and @cite_36 . The results by Braides and Yip @cite_44 , can be interpreted as the analogous results in a discrete setting to the ones obtained by Modica and Mortola. They give the description of the limiting functional (in the sense of @math -convergence) after appropriately rescaling the energies. In the discretized version considered, they work on a regular grid and the gradient term gets replaced by a finite-difference approximation that depends on the mesh size @math . Van Gennip and Bertozzi @cite_55 consider a similar problem and obtain analogous results. In @cite_36 , Chambolle, Giacomini and Lussardi consider a very general class of anisotropic perimeters defined on discrete subsets of a finite lattice of the form @math . They prove the @math -convergence of the functionals as @math to an anisotropic perimeter defined on a given domain in @math .