{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,30]],"date-time":"2026-05-30T16:26:39Z","timestamp":1780158399870,"version":"3.54.0"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T00:00:00Z","timestamp":1642723200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Found Comput Math"],"published-print":{"date-parts":[[2023,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Tackling semi-supervised learning problems with graph-based methods has become a trend in recent years since graphs can represent all kinds of data and provide a suitable framework for studying continuum limits, for example, of differential operators. A popular strategy here is <jats:italic>p<\/jats:italic>-Laplacian learning, which poses a smoothness condition on the sought inference function on the set of unlabeled data. For <jats:inline-formula><jats:alternatives><jats:tex-math>$$p&lt;\\infty $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>p<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mi>\u221e<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> continuum limits of this approach were studied using tools from <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varGamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0393<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-convergence. For the case <jats:inline-formula><jats:alternatives><jats:tex-math>$$p=\\infty $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>p<\/mml:mi>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mi>\u221e<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is referred to as Lipschitz learning, continuum limits of the related infinity Laplacian equation were studied using the concept of viscosity solutions. In this work, we prove continuum limits of Lipschitz learning using <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varGamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0393<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-convergence. In particular, we define a sequence of functionals which approximate the largest local Lipschitz constant of a graph function and prove <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varGamma $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u0393<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-convergence in the <jats:inline-formula><jats:alternatives><jats:tex-math>$$L^{\\infty }$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mi>\u221e<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-topology to the supremum norm of the gradient as the graph becomes denser. Furthermore, we show compactness of the functionals which implies convergence of minimizers. In our analysis we allow a varying set of labeled data which converges to a general closed set in the Hausdorff distance. We apply our results to nonlinear ground states, i.e., minimizers with constrained <jats:inline-formula><jats:alternatives><jats:tex-math>$$L^p$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:msup>\n                    <mml:mi>L<\/mml:mi>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:msup>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-norm, and, as a by-product, prove convergence of graph distance functions to geodesic distance functions.<\/jats:p>","DOI":"10.1007\/s10208-022-09557-9","type":"journal-article","created":{"date-parts":[[2022,1,21]],"date-time":"2022-01-21T20:00:43Z","timestamp":1642795243000},"page":"393-431","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Continuum Limit of Lipschitz Learning on Graphs"],"prefix":"10.1007","volume":"23","author":[{"given":"Tim","family":"Roith","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Leon","family":"Bungert","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,1,21]]},"reference":[{"key":"9557_CR1","unstructured":"Robert A. Adams and John Fournier. Sobolev Spaces, Volume 140 (Pure and Applied Mathematics). Academic Press, New York, 2003."},{"key":"9557_CR2","unstructured":"Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J. Wainwright, and Michael I. Jordan. Asymptotic behavior of $$l_{p}$$-based Laplacian regularization in semi-supervised learning. 2016. arxiv: 1603.00564."},{"key":"9557_CR3","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/bf02591326","volume":"6.1","author":"Gunnar Aronsson","year":"1965","unstructured":"Gunnar Aronsson. Minimization problems for the functional $${{\\rm sup}}_{x} F(x, f(x), f^{\\prime } (x))$$. In: Arkiv f\u00f6r Matematik 6.1 (1965), pp. 33\u201353. https:\/\/doi.org\/10.1007\/bf02591326.","journal-title":"Arkiv f\u00f6r Matematik"},{"key":"9557_CR4","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/bf02590989","volume":"7.5","author":"Gunnar Aronsson","year":"1968","unstructured":"Gunnar Aronsson. On the partial differential equation $$u^{2} _{x}u_{xx}+2u_{x}u_{y}u_{xy}+ u ^{2}_{y}u_{yy} = 0$$. In: Arkiv f\u00f6r Matematik 7.5 (1968), pp. 395\u2013425. https:\/\/doi.org\/10.1007\/bf02590989.","journal-title":"Arkiv f\u00f6r Matematik"},{"key":"9557_CR5","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1090\/S0273-0979-04-01035-3","volume":"41.4","author":"Gunnar Aronsson","year":"2004","unstructured":"Gunnar Aronsson, Michael Crandall, and Petri Juutinen. A tour of the theory of absolutely minimizing functions. In: Bulletin of the American Mathematical Society 41.4 (2004), pp. 439\u2013505.","journal-title":"Bulletin of the American Mathematical Society"},{"key":"9557_CR6","doi-asserted-by":"publisher","unstructured":"Vladimir I. Bogachev. Measure Theory. Springer, Berlin, Heidelberg, 2007. https:\/\/doi.org\/10.1007\/978-3-540-34514-5.","DOI":"10.1007\/978-3-540-34514-5"},{"key":"9557_CR7","unstructured":"Farid Bozorgnia, Leon Bungert, and Daniel Tenbrinck. The Infinity Laplacian eigenvalue problem: reformulation and a numerical scheme. 2020. arXiv: 2004.08127 [math.NA]."},{"key":"9557_CR8","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198507840.001.0001","volume-title":"Gamma-convergence for Beginners","author":"Andrea Braides","year":"2002","unstructured":"Andrea Braides. Gamma-convergence for Beginners. Vol. 22. Oxford University Press, Oxford, 2002."},{"key":"9557_CR9","doi-asserted-by":"publisher","unstructured":"Haim Brezis. Functional Analysis, Sobolev Spaces and Partial Differential Equations. Springer, New York, 2010. https:\/\/doi.org\/10.1007\/978-0-387-70914-7.","DOI":"10.1007\/978-0-387-70914-7"},{"key":"9557_CR10","doi-asserted-by":"publisher","unstructured":"Martin R. Bridson and Andr\u00e9 Haefliger. Metric Spaces of Non-Positive Curvature. Springer, Berlin, Heidelberg, 1999. https:\/\/doi.org\/10.1007\/978-3-662-12494-9.","DOI":"10.1007\/978-3-662-12494-9"},{"key":"9557_CR11","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1007\/s00028-019-00545-1","volume":"20.3","author":"Leon Bungert","year":"2020","unstructured":"Leon Bungert and Martin Burger. Asymptotic profiles of nonlinear homogeneous evolution equations of gradient flow type. In: Journal of Evolution Equations 20.3 (2020), pp. 1061\u20131092. https:\/\/doi.org\/10.1007\/s00028-019-00545-1.","journal-title":"Journal of Evolution Equations"},{"key":"9557_CR12","doi-asserted-by":"crossref","unstructured":"Leon Bungert, Jeff Calder, and Tim Roith. Uniform Convergence Rates for Lipschitz Learning on Graphs. 2021. arXiv: 2111.12370 [math.NA].","DOI":"10.1093\/imanum\/drac048"},{"key":"9557_CR13","doi-asserted-by":"publisher","first-page":"703","DOI":"10.2140\/paa.2020.2.703","volume":"2.3","author":"Leon Bungert","year":"2020","unstructured":"Leon Bungert, Yury Korolev, and Martin Burger. Structural analysis of an $$L$$-infinity variational problem and relations to distance functions. Pure and Applied Analysis 2.3 (2020), pp. 703\u2013738. https:\/\/doi.org\/10.2140\/paa.2020.2.703.","journal-title":"Pure and Applied Analysis"},{"key":"9557_CR14","doi-asserted-by":"publisher","first-page":"780","DOI":"10.1137\/18m1199241","volume":"1.4","author":"Jeff Calder","year":"2019","unstructured":"Jeff Calder. Consistency of Lipschitz Learning with Infinite Unlabeled Data and Finite Labeled Data. In: SIAM Journal on Mathematics of Data Science 1.4 (2019), pp. 780\u2013812. https:\/\/doi.org\/10.1137\/18m1199241.","journal-title":"SIAM Journal on Mathematics of Data Science"},{"key":"9557_CR15","unstructured":"Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slep\u010dev. Poisson Learning: Graph Based semi-supervised learning at very low label rates. In: International Conference on Machine Learning. PMLR. 2020, pp. 1306\u20131316."},{"key":"9557_CR16","unstructured":"Jeff Calder, Dejan Slep\u010dev, and Matthew Thorpe. Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates. 2020. arXiv: 2006.02765 [math.ST]."},{"key":"9557_CR17","volume-title":"Semi-Supervised Learning","author":"Olivier Chapelle","year":"2010","unstructured":"Olivier Chapelle, Bernhard Sch\u00f6lkopf, and Alexander Zien. Semi-Supervised Learning. Cambridge, MA: The MIT Press, 2010."},{"key":"9557_CR18","doi-asserted-by":"publisher","first-page":"199","DOI":"10.2307\/2308567","volume":"67","author":"Paul Civin","year":"1960","unstructured":"Paul Civin, Nelson Dunford, and Jacob T. Schwartz. Linear Operators. Part I: General Theory. American Mathematical Monthly 67 (1960), p. 199.","journal-title":"American Mathematical Monthly"},{"key":"9557_CR19","doi-asserted-by":"publisher","unstructured":"Abderrahim Elmoataz, Matthieu Toutain, and Daniel Tenbrinck. On the $$p$$-Laplacian and $$\\infty $$-Laplacian on Graphs with Applications in Image and Data Processing. In: SIAM Journal on Imaging Sciences 8.4 (2015), pp. 2412\u20132451. https:\/\/doi.org\/10.1137\/15m1022793.","DOI":"10.1137\/15m1022793"},{"key":"9557_CR20","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1007\/s00526-010-0388-1","volume":"42.1\u20132","author":"Lawrence C Evans","year":"2011","unstructured":"Lawrence C Evans and Charles K Smart. Everywhere differentiability of infinity harmonic functions. Calculus of Variations and Partial Differential Equations 42.1-2 (2011), pp. 289\u2013299.","journal-title":"Calculus of Variations and Partial Differential Equations"},{"key":"9557_CR21","doi-asserted-by":"publisher","first-page":"064003","DOI":"10.1088\/1361-6420\/ab0cb2","volume":"35.6","author":"Tal Feld","year":"2019","unstructured":"Tal Feld, Jean-Fran\u00e7ois Aujol, Guy Gilboa, and Nicolas Papadakis. Rayleigh quotient minimization for absolutely one-homogeneous functionals. Inverse Problems 35.6 (2019), p. 064003.","journal-title":"Inverse Problems"},{"key":"9557_CR22","doi-asserted-by":"publisher","unstructured":"Nicol\u00e1s Garc\u00eda Trillos and Dejan Slep\u010dev. Continuum Limit of Total Variation on Point Clouds. In: Archive for Rational Mechanics and Analysis 220.1 (2015), pp. 193\u2013241. https:\/\/doi.org\/10.1007\/s00205-015-0929-z.","DOI":"10.1007\/s00205-015-0929-z"},{"key":"9557_CR23","first-page":"1115","volume":"17.11\/12","author":"Yves van Gennip","year":"2012","unstructured":"Yves van Gennip and Andrea L. Bertozzi. Gamma-convergence of graph Ginzburg\u2013Landau functionals. In: Advances in Differential Equations 17.11\/12 (2012), pp. 1115\u20131180.","journal-title":"Advances in Differential Equations"},{"key":"9557_CR24","doi-asserted-by":"publisher","unstructured":"Ryan Hynd and Erik Lindgren. Inverse iteration for $$p$$-ground states. In: Proceedings of the American Mathematical Society 144.5 (2016), pp. 2121\u2013 2131. https:\/\/doi.org\/10.1090\/proc\/12860.","DOI":"10.1090\/proc\/12860"},{"key":"9557_CR25","doi-asserted-by":"publisher","unstructured":"Ryan Hynd and Erik Lindgren. Approximation of the least Rayleigh quotient for degree $$p$$ homogeneous functionals. In: Journal of Functional Analysis 272.12 (2017), pp. 4873\u20134918. https:\/\/doi.org\/10.1016\/j.jfa.2017.02.024.","DOI":"10.1016\/j.jfa.2017.02.024"},{"key":"9557_CR26","doi-asserted-by":"publisher","first-page":"1721","DOI":"10.1007\/s00208-018-1775-8","volume":"375.3\u20134","author":"Ryan Hynd","year":"2019","unstructured":"Ryan Hynd and Erik Lindgren. Extremal functions for Morrey\u2019s inequality in convex domains. In: Mathematische Annalen 375.3-4 (2019), pp. 1721\u20131743. https:\/\/doi.org\/10.1007\/s00208-018-1775-8.","journal-title":"Mathematische Annalen"},{"key":"9557_CR27","first-page":"57","volume":"27","author":"Petri Juutinen","year":"2002","unstructured":"Petri Juutinen. Absolutely minimizing Lipschitz extensions on a metric space. In: Annales Academiae Scientiarum Fennicae Mathematica Volumen 27 (Jan. 2002), pp. 57\u201367.","journal-title":"Annales Academiae Scientiarum Fennicae Mathematica Volumen"},{"key":"9557_CR28","unstructured":"Petri Juutinen, Peter Lindqvist, and Juan J Manfredi. The infinity Laplacian: examples and observations. Institut Mittag-Leffler, 1999."},{"key":"9557_CR29","doi-asserted-by":"publisher","unstructured":"Peter Knabner and Lutz Angermann. Numerical Methods for Elliptic and Parabolic Partial Differential Equations. Springer, Berlin, Heidelberg, 2003. https:\/\/doi.org\/10.1007\/b97419.","DOI":"10.1007\/b97419"},{"key":"9557_CR30","unstructured":"Rasmus Kyng, Anup Rao, Sushant Sachdeva, and Daniel A Spielman. Algorithms for Lipschitz learning on graphs. In: Conference on Learning Theory. PMLR. 2015, pp. 1190\u20131223."},{"key":"9557_CR31","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/s00030-006-4030-z","volume":"14.1","author":"Erwan Le Gruyer","year":"2007","unstructured":"Erwan Le Gruyer. On absolutely minimizing Lipschitz extensions and PDE $$\\Delta _{\\infty }(u) = 0$$. In: Nonlinear Differential Equations and Applications NoDEA 14.1 (2007), pp. 29\u201355.","journal-title":"Nonlinear Differential Equations and Applications NoDEA"},{"key":"9557_CR32","doi-asserted-by":"publisher","first-page":"555","DOI":"10.1214\/009053607000000640","volume":"36.2","author":"Ulrike von Luxburg","year":"2008","unstructured":"Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. In: The Annals of Statistics 36.2 (2008), pp. 555\u2013586. https:\/\/doi.org\/10.1214\/009053607000000640.","journal-title":"The Annals of Statistics"},{"key":"9557_CR33","doi-asserted-by":"publisher","unstructured":"David Pollard. Strong Consistency of $$k$$-Means Clustering. In: The Annals of Statistics 9.1 (1981), pp. 135\u2013140. https:\/\/doi.org\/10.1214\/aos\/1176345339.","DOI":"10.1214\/aos\/1176345339"},{"key":"9557_CR34","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1002\/cpa.20391","volume":"65.1","author":"Scott Sheffield","year":"2012","unstructured":"Scott Sheffield and Charles K. Smart. Vector-valued optimal Lipschitz extensions. In: Communications on Pure and Applied Mathematics 65.1 (2012), pp. 128\u2013154.","journal-title":"Communications on Pure and Applied Mathematics"},{"key":"9557_CR35","doi-asserted-by":"publisher","unstructured":"Dejan Slep\u010dev and Matthew Thorpe. Analysis of $$p$$-Laplacian Regularization in Semisupervised Learning. In: SIAM Journal on Mathematical Analysis 51.3 (2019), pp. 2085\u20132120. https:\/\/doi.org\/10.1137\/17m115222x.","DOI":"10.1137\/17m115222x"},{"key":"9557_CR36","first-page":"6268","volume":"17.1","author":"Nicol\u00e1s Garc\u00eda Trillos","year":"2016","unstructured":"Nicol\u00e1s Garc\u00eda Trillos, Dejan Slep\u010dev, James von Brecht, Thomas Laurent, and Xavier Bresson. Consistency of Cheeger and Ratio Graph Cuts. In: J. Mach. Learn. Res. 17.1 (2016), pp. 6268\u20136313.","journal-title":"J. Mach. Learn. Res."},{"key":"9557_CR37","doi-asserted-by":"crossref","unstructured":"Yifeng Yu. Some properties of the ground states of the infinity Laplacian. In: Indiana University Mathematics Journal (2007), pp. 947\u2013964.","DOI":"10.1512\/iumj.2007.56.2935"},{"key":"9557_CR38","unstructured":"Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. In: ICML\u201903 (2003), pp. 912\u2013919."},{"key":"9557_CR39","first-page":"1","volume":"3.1","author":"Xiaojin Zhu","year":"2009","unstructured":"Xiaojin Zhu and Andrew B. Goldberg. Introduction to semi-supervised learning. In: Synthesis lectures on artificial intelligence and machine learning 3.1 (2009), pp. 1\u2013130.","journal-title":"Synthesis lectures on artificial intelligence and machine learning"},{"key":"9557_CR40","unstructured":"Xiaojin Zhu, John Lafferty, and Ronald Rosenfeld. Semi-supervised learning with graphs. PhD thesis. Carnegie Mellon University, language technologies institute, school of computer science, 2005."},{"key":"9557_CR41","unstructured":"Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Tech. rep. University of Wisconsin-Madison Department of Computer Sciences, 2005."}],"container-title":["Foundations of Computational Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-022-09557-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10208-022-09557-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10208-022-09557-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,3,29]],"date-time":"2023-03-29T15:09:12Z","timestamp":1680102552000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10208-022-09557-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,21]]},"references-count":41,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4]]}},"alternative-id":["9557"],"URL":"https:\/\/doi.org\/10.1007\/s10208-022-09557-9","relation":{},"ISSN":["1615-3375","1615-3383"],"issn-type":[{"value":"1615-3375","type":"print"},{"value":"1615-3383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,21]]},"assertion":[{"value":"14 January 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 November 2021","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 December 2021","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 January 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}