Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Agueh M.: Finsler structure in the p-Wasserstein space and gradient flows. C. R. Math. Acad. Sci. Paris. 350, 35–40 (2012)
Ajtai M., Komlós J., Tusnády G.: On optimal matchings. Combinatorica. 4, 259–264 (1984)
Alberti G., Bellettini G.: A non-local anisotropic model for phase transitions: asymptotic behaviour of rescaled energies. European J. Appl. Math. 9, 261–284 (1998)
Ambrosio L., Fusco N., Pallara D.: Functions of bounded variation and free discontinuity problems. Oxford Mathematical Monographs. The Clarendon Press Oxford University Press, New York (2000)
Ambrosio, L., Gigli, N., Savaré, G.: Gradient Flows: In: Metric Spaces and in the Space of Probability Measures. Lectures in Mathematics, Birkhäuser Basel (2008)
Andreev K., Racke H.: Balanced graph partitioning. Theory Comput. Syst. 39, 929–939 (2006)
Arias-Castro E., Pelletier B., Pudlo P.: The normalized graph cut and Cheeger constant: from discrete to continuous. Adv. Appl. Probab. 44, 907–937 (2012)
Arora S., Rao S., Vazirani U.: Expander flows, geometric embeddings and graph partitioning. J. ACM (JACM). 56, 5 (2009)
Baldi A.: Weighted BV functions. Houston J. Math. 27, 683–705 (2001)
Ball, J.M., Zarnescu, A.: Partial regularity and smooth topology-preserving approximations of rough domains. arXiv:1312.5156 (2013) (arXiv preprint)
Belkin M., Niyogi P.: Convergence of Laplacian eigenmaps. Adv. Neural Inf. Process. Syst. (NIPS) 19, 129 (2007)
Belkin M., Niyogi P.: Towards a theoretical foundation for Laplacian-based manifold methods. J. Comput. Syst. Sci. 74, 1289–1308 (2008)
Bertozzi A.L., Flenner A.: Diffuse interface models on graphs for classification of high dimensional data. Multiscale Model. Simul. 10, 1090–1118 (2012)
Bourgain J., Brezis H., Mironescu P. et al.: Another look at sobolev spaces. In: Optimal control and partial differential equations, A volume in honour of A. Benssoussans 60th birthday, pp. 439455. IOS Press, Amsterdam (2001)
Boykov Y., Veksler O., Zabih R.: Fast approximate energy minimization via graph cuts. Pattern Anal. Mach. Intell. IEEE Trans. 23, 1222–1239 (2001)
Braides A.: Gamma-Convergence for Beginners. Oxford Lecture Series in Mathematics and Its Applications Series. Oxford University Press. Incorporated, Oxford (2002)
Braides A., Yip N.K.: A quantitative description of mesh dependence for the discretization of singularly perturbed nonconvex problems. SIAM J. Numer. Anal. 50, 1883–1898 (2012)
Bresson, X., Laurent, T.: Asymmetric cheeger cut and application to multi-class unsupervised clustering. CAM Report, pp. 1–8 (2012)
Bresson, X., Laurent, T., Uminsky, D., von Brecht, J.: Multiclass total variation clustering. In: Burges, C., Bottou, L., Welling, M., Ghahramani, Z., Weinberger, K. (eds.) Advances in Neural Information Processing Systems, vol. 26, pp. 1421–1429 (2013)
Bresson, X., Laurent, T., Uminsky, D., von Brecht, J. H.: Convergence and energy landscape for cheeger cut clustering. In: P. L. Bartlett, F. C. N. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, (eds.) Advances in Neural Information Processing Systems (NIPS), pp. 1394–1402 (2012)
Bresson, X., Laurent, T., Uminsky, D., von Brecht, J. H.: An adaptive total variation algorithm for computing the balanced cut of a graph. arXiv preprint arXiv:1302.2717. (2013)
Bresson, X., Tai, X.-C., Chan, T. F., Szlam, A.: Multi-class transductive learning based on l1 relaxations of cheeger cut and mumford-shah-potts model. UCLA CAM Rep. 12–03 (2012)
Castaing, C., Raynaud de Fitte, P., Valadier, M.: Young measures on topological spaces of Mathematics and its Applications, vol. 571, Kluwer Academic Publishers, Dordrecht, 2004
Chambolle A., Giacomini A., Lussardi L.: Continuous limits of discrete perimeters. M2AN Math. Model. Numer. Anal. 44, 207–230 (2010)
Dal Maso G.: An Introduction to Γ-convergence. Springer, New York (1993)
Delling, D., Fleischman, D., Goldberg, A., Razenshteyn, I., Werneck, R.: An exact combinatorial algorithm for minimum graph bisection. Math. Program. 152(2), 417–458 (2014)
Esedōglu S., Otto F.: Threshold dynamics for networks with arbitrary surface tensions. Commun. Pure Appl. Math. 68, 808–864 (2015)
Feige U., Krauthgamer R.: A polylogarithmic approximation of the minimum bisection. SIAM Rev. 48, 99–130 (2006)
García Trillos, N., Slepčev, D.: On the rate of convergence of empirical measures in ∞-transportation distance. Can. J. Math.(2015) (online first)
Giné, E., Koltchinskii, V.: Empirical graph Laplacian approximation of Laplace-Beltrami operators: large sample results. In: High dimensional probability, of IMS Lecture Notes Monogr. Ser., Inst. Math. Statist., Beachwood, OH, vol. 51, pp. 238–259 (2006)
Gobbino M.: Finite difference approximation of the Mumford-Shah functional. Comm. Pure Appl. Math. 51, 197–228 (1998)
Gobbino M., Mora M.G.: Finite-difference approximation of free-discontinuity problems. Proc. Roy. Soc. Edinburgh Sect. A. 131, 567–595 (2001)
Goel A., Rai S., Krishnamachari B.: Sharp thresholds for monotone properties in random geometric graphs. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, pp. 580–586. ACM, New York (2004)
Gupta, P., Kumar, P.R.: Critical power for asymptotic connectivity in wireless networks. In: Stochastic analysis, control, optimization and applications, Systems Control Found. Appl., Birkhäuser Boston, Boston, MA, pp. 547–566 (1999)
Hein, M., Audibert, J.-Y., Von Luxburg, U.: From graphs to manifolds–weak and strong pointwise consistency of graph Laplacians. In: Learning theory, pp. 470–485. Springer, New York, 2005
Hein, M., Bühler, T.: An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse PCA. In: Advances in Neural Information Processing Systems (NIPS), pp. 847–855, 2010
Hein, M., Setzer, S.: Beyond spectral clustering - tight relaxations of balanced graph cuts. In: Advances in Neural Information Processing Systems (NIPS) (Eds. J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K. Weinberger) pp. 2366–2374, 2011
Leighton T., Shor P.: Tight bounds for minimax grid matching with applications to the average case analysis of algorithms. Combinatorica 9, 161–187 (1989)
Leoni, G.: A first course in Sobolev spaces of Graduate Studies in Mathematics. vol. 105, American Mathematical Society, Providence, 2009
Maier M., von Luxburg U., Hein M.: How the result of graph clustering methods depends on the construction of the graph. ESAIM Probab. Stat., 17, 370–418 (2013)
Merkurjev E., Kostić T., Bertozzi A.L.: An mbo scheme on graphs for classification and image processing. SIAM J. Imaging Sci. 6, 1903–1930 (2013)
Modica L., Mortola S.: Un esempio di Γ-convergenza. Boll. Un. Mat. Ital. B (5) 14, 285–299 (1977)
Otto F.: The geometry of dissipative evolution equations: the porous medium equation. Comm. Partial Differ. Equ. 26, 101–174 (2001)
Pedregal, P.: Parametrized measures and variational principles. Progress in Nonlinear Differential Equations and their Applications, 30, Birkhäuser Verlag, Basel (1997)
Penrose M.: A strong law for the longest edge of the minimal spanning tree. Ann. Probab. 27, 246–260 (1999)
Ponce A.C.: A new approach to Sobolev spaces and connections to Γ-convergence. Calc. Var. Partial Differ. Equ. 19, 229–255 (2004)
Rangapuram, S.S., Hein, M.: Constrained 1-spectral clustering. In: International conference on Artificial Intelligence and Statistics (AISTATS), pp. 1143–1151, 2012
Savin O., Valdinoci E.: Γ-convergence for nonlocal phase transitions. Ann. Inst. H. Poincaré Anal. Non Linéaire. 29, 479–500 (2012)
Shi J., Malik J.: Normalized cuts and image segmentation. Pattern Anal. Mach. Intell. IEEE Trans. 22, 888–905 (2000)
Shor P.W., Yukich J.E.: Minimax grid matching and empirical measures. Ann. Probab. 19, 1338–1348 (1991)
Singer A.: From graph to manifold Laplacian: the convergence rate. Appl. Comput. Harmon. Anal. 21, 128–134 (2006)
Szlam, A., Bresson, X.: A total variation-based graph clustering algorithm for cheeger ratio cuts. UCLA CAM Report, pp. 1–12 (2009)
Szlam, A., Bresson, X.: Total variation and cheeger cuts., In: ICML (Eds. J. Frnkranz and T. Joachims) Omnipress pp. 1039–1046 (2010)
Talagrand M.: The transportation cost from the uniform measure to the empirical measure in dimension ≥ 3. Ann. Probab. 22, 919–959 (1994)
Talagrand, M.: The generic chaining. Springer Monographs in Mathematics Springer-Verlag, Berlin, 2005
Talagrand, M.: Upper and lower bounds of stochastic processes of Modern Surveys in Mathematics. vol. 60. Springer-Verlag, Berlin Heidelberg, 2014
Talagrand M., Yukich J.E.: The integrability of the square exponential transportation cost. Ann. Appl. Probab. 3, 1100–1111 (1993)
Ting, D., Huang, L., Jordan, M.I.: An analysis of the convergence of graph Laplacians. In: Proceedings of the 27th International Conference on Machine Learning, 2010
van Gennip Y., Bertozzi A.L.: Γ-convergence of graph Ginzburg-Landau functionals. Adv. Differential Equations 17, 1115–1180 (2012)
Villani, C.: Topics in Optimal Transportation, Graduate Studies in Mathematics. American Mathematical Society, Providence, US (2003)
von Luxburg U., Belkin M., Bousquet O.: Consistency of spectral clustering. Ann. Statist. 36, 555–586 (2008)
Weyl H.: On the Volume of Tubes. Amer. J. Math. 61, 461–472 (1939)
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by F. Otto
Rights and permissions
About this article
Cite this article
García Trillos, N., Slepčev, D. Continuum Limit of Total Variation on Point Clouds. Arch Rational Mech Anal 220, 193–241 (2016). https://doi.org/10.1007/s00205-015-0929-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00205-015-0929-z