{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T13:17:11Z","timestamp":1787836631339,"version":"build-2784847793"},"reference-count":56,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T00:00:00Z","timestamp":1785715200000},"content-version":"vor","delay-in-days":2,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008131","name":"Rheinische Friedrich-Wilhelms-Universit\u00e4t Bonn","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008131","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2026,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    One of the central problems studied in the theory of machine learning is the question of whether, for a given class of hypotheses, it is possible to efficiently find a consistent hypothesis, i.e., one with zero training error. While problems involving\n                    <jats:italic>convex<\/jats:italic>\n                    hypotheses have been extensively studied, the question of whether efficient learning is possible for\n                    <jats:italic>non-convex<\/jats:italic>\n                    hypotheses composed of possibly several disconnected regions is still not well understood. Although it has been shown quite a while ago that efficient learning of weakly convex hypotheses, a parameterized relaxation of convex hypotheses, is possible for the special case of Boolean functions, the question of whether this idea can be developed into a\n                    <jats:italic>generic paradigm<\/jats:italic>\n                    has not yet been studied. In this paper, we provide a positive answer and show that the consistent hypothesis finding problem can indeed be solved in polynomial time for a broad class of weakly convex hypotheses over metric spaces. To this end, we propose a general domain-independent algorithm for finding consistent weakly convex hypotheses and prove sufficient conditions for its efficiency that characterize the corresponding hypothesis classes. To illustrate our general algorithm and its properties, we discuss several non-trivial learning examples to demonstrate how it can be used to efficiently solve the corresponding consistent hypothesis finding problem. Without the weak convexity constraint, these problems are known to be computationally intractable. We then show that the general idea of our algorithm even extends to the\n                    <jats:italic>extensional<\/jats:italic>\n                    case, enabling applications, such as vertex classification in graphs. We prove that using our extended algorithm, the problem can be solved in polynomial time provided the distances in the domain can be computed efficiently.\n                  <\/jats:p>","DOI":"10.1007\/s10994-026-07088-w","type":"journal-article","created":{"date-parts":[[2026,8,3]],"date-time":"2026-08-03T09:56:09Z","timestamp":1785750969000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Learning Weakly Convex Sets in Metric Spaces"],"prefix":"10.1007","volume":"115","author":[{"given":"Eike","family":"Stadtl\u00e4nder","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tam\u00e1s","family":"Horv\u00e1th","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Stefan","family":"Wrobel","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,8,3]]},"reference":[{"key":"7088_CR1","doi-asserted-by":"publisher","unstructured":"Abidha, V. P., & Ashok, P. (2024). Red blue set cover problem on axis-parallel hyperplanes and other objects. Information Processing Letters, 186, 106485. https:\/\/doi.org\/10.1016\/j.ipl.2024.106485","DOI":"10.1016\/j.ipl.2024.106485"},{"issue":"1","key":"7088_CR2","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1023\/A:1018960107028","volume":"23","author":"P Auer","year":"1998","unstructured":"Auer, P., & Cesa-Bianchi, N. (1998). On-line learning with malicious noise and the closure algorithm. Annals of Mathematics and Artificial Intelligence, 23(1), 83\u201399. https:\/\/doi.org\/10.1023\/A:1018960107028","journal-title":"Annals of Mathematics and Artificial Intelligence"},{"key":"7088_CR3","unstructured":"Bressan, M., Cesa-Bianchi, N., Lattanzi, S., & Paudice, A. (2021). Exact recovery of clusters in finite metric spaces using oracle queries. In M. Belkin & S. Kpotufe (Eds.), Proceedings of Thirty Fourth Conference on Learning Theory. Proceedings of Machine Learning Research (Vol. 134, pp. 775\u2013803). Boulder, Colorado, USA: PMLR."},{"issue":"7","key":"7088_CR4","doi-asserted-by":"publisher","first-page":"294","DOI":"10.1016\/j.comgeo.2012.01.014","volume":"45","author":"S Bereg","year":"2012","unstructured":"Bereg, S., Cabello, S., D\u00edaz-B\u00e1\u00f1ez, J. M., P\u00e9rez-Lantero, P., Seara, C., & Ventura, I. (2012). The class cover problem with boxes. Computational Geometry, 45(7), 294\u2013304. https:\/\/doi.org\/10.1016\/j.comgeo.2012.01.014","journal-title":"Computational Geometry"},{"issue":"4","key":"7088_CR5","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4), 929\u2013965. https:\/\/doi.org\/10.1145\/76359.76371","journal-title":"Journal of the ACM"},{"key":"7088_CR6","unstructured":"Bressan, M., Esposito, E., & Thiessen, M. (2024). Efficient algorithms for learning monophonic halfspaces in graphs. In: Agrawal, S., Roth, A. (eds.) Proceedings of Thirty Seventh Conference on Learning Theory. Proceedings of Machine Learning Research, vol. 247, pp. 669\u2013696. PMLR, ??? https:\/\/proceedings.mlr.press\/v247\/bressan24b.html"},{"key":"7088_CR7","doi-asserted-by":"publisher","unstructured":"Cannon, A. H., & Cowen, L. J. (2004). Approximation algorithms for the class cover problem. Annals of Mathematics and Artificial Intelligence, 40, 215\u2013223. https:\/\/doi.org\/10.1023\/B:AMAI.0000012867.03976.a5","DOI":"10.1023\/B:AMAI.0000012867.03976.a5"},{"key":"7088_CR8","doi-asserted-by":"publisher","unstructured":"Chalopin, J., Chepoi, V., Moran, S., & Warmuth, M. K. (2022). Unlabeled sample compression schemes and corner peelings for ample and maximum classes. Journal of Computer and System Sciences, 127, 1\u201328. https:\/\/doi.org\/10.1016\/j.jcss.2022.01.003","DOI":"10.1016\/j.jcss.2022.01.003"},{"key":"7088_CR9","doi-asserted-by":"publisher","unstructured":"Carr, R.D., Doddi, S., Konjevod, G., & Marathe, M. (2000). On the red-blue set cover problem. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. SODA \u201900, pp. 345\u2013353. Society for Industrial and Applied Mathematics, USA https:\/\/doi.org\/10.5555\/338219.338271","DOI":"10.5555\/338219.338271"},{"issue":"06","key":"7088_CR10","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1142\/S0218195905001865","volume":"15","author":"G C\u0103linescu","year":"2005","unstructured":"C\u0103linescu, G., Dumitrescu, A., Karloff, H., & Wan, P.-J. (2005). Separating points by axis-parallel lines. International Journal of Computational Geometry & Applications, 15(06), 575\u2013590. https:\/\/doi.org\/10.1142\/S0218195905001865","journal-title":"International Journal of Computational Geometry & Applications"},{"issue":"5","key":"7088_CR11","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1016\/j.comgeo.2014.12.005","volume":"48","author":"TM Chan","year":"2015","unstructured":"Chan, T. M., & Hu, N. (2015). Geometric red\u2013blue set cover for unit squares and related problems. Computational Geometry, 48(5), 380\u2013385. https:\/\/doi.org\/10.1016\/j.comgeo.2014.12.005","journal-title":"Computational Geometry"},{"key":"7088_CR12","first-page":"75","volume":"96","author":"V Chepoi","year":"1989","unstructured":"Chepoi, V. (1989). Classification of graphs by means of metric triangles. Metody Diskretnogo Analiza, 96, 75\u201393.","journal-title":"Metody Diskretnogo Analiza"},{"issue":"2","key":"7088_CR13","doi-asserted-by":"publisher","first-page":"175","DOI":"10.1016\/j.jctb.2006.05.003","volume":"97","author":"V Chepoi","year":"2007","unstructured":"Chepoi, V. (2007). Basis graphs of even delta-matroids. Journal of Combinatorial Theory, Series B, 97(2), 175\u2013192. https:\/\/doi.org\/10.1016\/j.jctb.2006.05.003","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"7088_CR14","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2019.111678","volume":"343","author":"V Chepoi","year":"2020","unstructured":"Chepoi, V., Knauer, K., & Marc, T. (2020). Hypercellular graphs: Partial cubes without Q3- as partial cube minor. Discrete Mathematics, 343(4), Article 111678. https:\/\/doi.org\/10.1016\/j.disc.2019.111678","journal-title":"Discrete Mathematics"},{"key":"7088_CR15","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.entcs.2019.08.007","volume":"346","author":"PHM de Ara\u00fajo","year":"2019","unstructured":"de Ara\u00fajo, P. H. M., Camp\u00ealo, M. B., Corr\u00eaa, R. C., & Labb\u00e9, M. (2019). The geodesic classification problem on graphs. Electronic Notes in Theoretical Computer Science, 346, 65\u201376. https:\/\/doi.org\/10.1016\/j.entcs.2019.08.007","journal-title":"Electronic Notes in Theoretical Computer Science"},{"key":"7088_CR16","first-page":"793","volume":"6","author":"BN Delaunay","year":"1934","unstructured":"Delaunay, B. N. (1934). Sur la sph\u00e9re vide. Bulletin de l\u2019Acad\u00e9mie des Sciences de l\u2019URSS, 6, 793\u2013800.","journal-title":"Bulletin de l\u2019Acad\u00e9mie des Sciences de l\u2019URSS"},{"issue":"3","key":"7088_CR17","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/0304-3975(82)90120-7","volume":"27","author":"DP Dobkin","year":"1983","unstructured":"Dobkin, D. P., & Kirkpatrick, D. G. (1983). Fast detection of polyhedral intersection. Theoretical Computer Science, 27(3), 241\u2013253. https:\/\/doi.org\/10.1016\/0304-3975(82)90120-7","journal-title":"Theoretical Computer Science"},{"key":"7088_CR18","doi-asserted-by":"publisher","unstructured":"Davey, B.A., & Priestley, H.A. (2002). Introduction to Lattices and Order, 2nd edn. Cambridge University Press, Cambridge, UK https:\/\/doi.org\/10.1017\/CBO9780511809088","DOI":"10.1017\/CBO9780511809088"},{"issue":"2","key":"7088_CR19","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0196-6774(85)90039-2","volume":"6","author":"H Edelsbrunner","year":"1985","unstructured":"Edelsbrunner, H. (1985). Computing the extreme distances between two convex polygons. Journal of Algorithms, 6(2), 213\u2013224. https:\/\/doi.org\/10.1016\/0196-6774(85)90039-2","journal-title":"Journal of Algorithms"},{"key":"7088_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1016\/S0166-218X(99)00098-0","volume":"96\u201397","author":"O Ekin","year":"1999","unstructured":"Ekin, O., Hammer, P. L., & Kogan, A. (1999). On connected boolean functions. Discrete Applied Mathematics, 96\u201397, 337\u2013362. https:\/\/doi.org\/10.1016\/S0166-218X(99)00098-0","journal-title":"Discrete Applied Mathematics"},{"issue":"1","key":"7088_CR21","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/S0304-3975(98)00337-5","volume":"244","author":"O Ekin","year":"2000","unstructured":"Ekin, O., Hammer, P. L., & Kogan, A. (2000). Convexity and logical analysis of data. Theoretical Computer Science, 244(1), 95\u2013116. https:\/\/doi.org\/10.1016\/S0304-3975(98)00337-5","journal-title":"Theoretical Computer Science"},{"issue":"3","key":"7088_CR22","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1137\/0607049","volume":"7","author":"M Farber","year":"1986","unstructured":"Farber, M., & Jamison, R. E. (1986). Convexity in graphs and hypergraphs. SIAM Journal on Algebraic Discrete Methods, 7(3), 433\u2013444. https:\/\/doi.org\/10.1137\/0607049","journal-title":"SIAM Journal on Algebraic Discrete Methods"},{"key":"7088_CR23","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/2076.001.0001","volume-title":"Conceptual Spaces: The Geometry of Thought","author":"P G\u00e4rdenfors","year":"2000","unstructured":"G\u00e4rdenfors, P. (2000). Conceptual Spaces: The Geometry of Thought. Cambridge, Massachusetts, USA: MIT Press."},{"key":"7088_CR24","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/9629.001.0001","volume-title":"The Geometry of Meaning: Semantics Based on Conceptual Spaces","author":"P G\u00e4rdenfors","year":"2014","unstructured":"G\u00e4rdenfors, P. (2014). The Geometry of Meaning: Semantics Based on Conceptual Spaces. Cambridge, Massachusetts, USA: MIT Press."},{"key":"7088_CR25","volume-title":"Deep Learning","author":"I Goodfellow","year":"2016","unstructured":"Goodfellow, I., Bengio, Y., & Courville, A. (2016). Deep Learning. Cambridge, MA, USA: MIT Press."},{"key":"7088_CR26","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York City, NY, USA: W.H. Freeman."},{"issue":"4","key":"7088_CR27","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"RL Graham","year":"1972","unstructured":"Graham, R. L. (1972). An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1(4), 132\u2013133. https:\/\/doi.org\/10.1016\/0020-0190(72)90045-2","journal-title":"Information Processing Letters"},{"key":"7088_CR28","doi-asserted-by":"publisher","unstructured":"Giesen, J., & Wagner, U. (2003). Shape dimension and intrinsic metric from samples of manifolds with high co-dimension. In: Fortune, S. (ed.) Proceedings of the 19th ACM Symposium on Computational Geometry, San Diego, CA, USA, June 8-10, 2003, pp. 329\u2013337. ACM, San Diego, CA, USA https:\/\/doi.org\/10.1145\/777792.777841","DOI":"10.1145\/777792.777841"},{"issue":"6","key":"7088_CR29","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1037\/h0071325","volume":"24","author":"H Hotelling","year":"1933","unstructured":"Hotelling, H. (1933). Analysis of a complex of statistical variables into principal components, 24(6), 417\u2013441. https:\/\/doi.org\/10.1037\/h0071325","journal-title":"Analysis of a complex of statistical variables into principal components"},{"issue":"2","key":"7088_CR30","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/BF00116036","volume":"5","author":"D Helmbold","year":"1990","unstructured":"Helmbold, D., Sloan, R., & Warmuth, M. K. (1990). Learning nested differences of intersection-closed concept classes. Machine Learning, 5(2), 165\u2013196. https:\/\/doi.org\/10.1007\/BF00116036","journal-title":"Machine Learning"},{"key":"7088_CR31","doi-asserted-by":"publisher","unstructured":"Jolliffe, I.T. (2002). Principal Component Analysis, 2nd edn. Springer Series in Statistics. Springer, New York https:\/\/doi.org\/10.1007\/b98835","DOI":"10.1007\/b98835"},{"key":"7088_CR32","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-2730-9","volume-title":"Percolation Theory for Mathematicians","author":"H Kesten","year":"1982","unstructured":"Kesten, H. (1982). Percolation Theory for Mathematicians. Boston, Massachusetts, USA: Progress in probability and statistics. Birkh\u00e4user."},{"key":"7088_CR33","doi-asserted-by":"publisher","first-page":"133","DOI":"10.4064\/sm-9-1-133-138","volume":"9","author":"M Krein","year":"1940","unstructured":"Krein, M., & Milman, D. (1940). On extreme points of regular convex sets. Studia Mathematica, 9, 133\u2013138.","journal-title":"Studia Mathematica"},{"key":"7088_CR34","unstructured":"Knuth, D. E. (1997). The Art of Computer Programming, Volume I: Fundamental Algorithms. Addison-Wesley. 3rd edn."},{"key":"7088_CR35","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"MJ Kearns","year":"1994","unstructured":"Kearns, M. J., & Vazirani, U. V. (1994). An Introduction to Computational Learning Theory. Cambridge, Massachusetts, USA: MIT Press."},{"key":"7088_CR36","unstructured":"Lundberg, S. M., & Lee, S.-I. (2017). A unified approach to interpreting model predictions. NIPS\u201917Advances in Neural Information Processing Systems (Vol. 30, pp. 4765\u20134774). Red Hook, NY, USA: Curran Associates Inc."},{"issue":"4","key":"7088_CR37","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/BF02187916","volume":"3","author":"N Megiddo","year":"1988","unstructured":"Megiddo, N. (1988). On the complexity of polyhedral separability. Discrete & Computational Geometry, 3(4), 325\u2013337. https:\/\/doi.org\/10.1007\/BF02187916","journal-title":"Discrete & Computational Geometry"},{"issue":"1","key":"7088_CR38","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1007\/BF01448840","volume":"100","author":"K Menger","year":"1928","unstructured":"Menger, K. (1928). Untersuchungen \u00fcber allgemeine Metrik. Mathematische Annalen, 100(1), 75\u2013163. https:\/\/doi.org\/10.1007\/BF01448840","journal-title":"Mathematische Annalen"},{"issue":"2","key":"7088_CR39","first-page":"203","volume":"18","author":"TM Mitchell","year":"1982","unstructured":"Mitchell, T. M. (1982). Generalization as search. Artificial intelligence, 18(2), 203\u2013226.","journal-title":"Generalization as search. Artificial intelligence"},{"key":"7088_CR40","doi-asserted-by":"publisher","unstructured":"M\u00fcller, S., Toborek, V., Stadtl\u00e4nder, E., Horv\u00e1th, T., Balcerak\u00a0Jackson, B., & Bauckhage, C. (2026) . Scientific Theory of a Black Box: A Life Cycle Scale XAI Framework based on Constructive Empiricism. CoRR https:\/\/doi.org\/10.48550\/arXiv.2602.02215","DOI":"10.48550\/arXiv.2602.02215"},{"key":"7088_CR41","first-page":"227","volume":"29","author":"S Nakajima","year":"1928","unstructured":"Nakajima, S. (1928). \u00dcber konvexe Kurven und Fl\u00e4chen. Tohoku Mathematical Journal, First Series, 29, 227\u2013230.","journal-title":"Tohoku Mathematical Journal, First Series"},{"key":"7088_CR42","doi-asserted-by":"publisher","unstructured":"Natarajan, B.K. (1987). On learning boolean functions. In: Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing. STOC \u201987, pp. 296\u2013304. Association for Computing Machinery, New York City, NY, USA https:\/\/doi.org\/10.1145\/28395.28427","DOI":"10.1145\/28395.28427"},{"key":"7088_CR43","doi-asserted-by":"publisher","unstructured":"Pelayo, I.M. (2013). Geodesic Convexity in Graphs. SpringerBriefs in Mathematics. Springer, New York City, NY, USA https:\/\/doi.org\/10.1007\/978-1-4614-8699-2","DOI":"10.1007\/978-1-4614-8699-2"},{"key":"7088_CR44","doi-asserted-by":"publisher","unstructured":"Preparata, F.P., & Shamos, M.I. (1985). Computational Geometry - An Introduction. Texts and Monographs in Computer Science. Springer, New York, NY https:\/\/doi.org\/10.1007\/978-1-4612-1098-6","DOI":"10.1007\/978-1-4612-1098-6"},{"issue":"4","key":"7088_CR45","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L Pitt","year":"1988","unstructured":"Pitt, L., & Valiant, L. G. (1988). Computational limitations on learning from examples. Journal of the ACM, 35(4), 965\u2013984. https:\/\/doi.org\/10.1145\/48014.63140","journal-title":"Journal of the ACM"},{"key":"7088_CR46","doi-asserted-by":"publisher","unstructured":"Ribeiro, M.T., Singh, S., & Guestrin, C. (2016). \u201cwhy should i trust you?\": Explaining the predictions of any classifier. In: Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. KDD \u201916, pp. 1135\u20131144. ACM, New York, NY, USA https:\/\/doi.org\/10.1145\/2939672.2939778","DOI":"10.1145\/2939672.2939778"},{"key":"7088_CR47","doi-asserted-by":"publisher","unstructured":"Stadtl\u00e4nder, E., Horv\u00e1th, T., & Wrobel, S. (2021). Learning weakly convex sets in metric spaces. In: Oliver, N., P\u00e9rez-Cruz, F., Kramer, S., Read, J., Lozano, J.A. (eds.) Machine Learning and Knowledge Discovery in Databases. Research Track. Lecture Notes in Computer Science, vol. 12976, pp. 200\u2013216. Springer, Cham https:\/\/doi.org\/10.1007\/978-3-030-86520-7_13","DOI":"10.1007\/978-3-030-86520-7_13"},{"key":"7088_CR48","doi-asserted-by":"publisher","unstructured":"Seiffarth, F., Horv\u00e1th, T., & Wrobel, S. (2023). Maximal closed set and half-space separations in finite closure systems. Theoretical Computer Science, 973, 114105. https:\/\/doi.org\/10.1016\/j.tcs.2023.114105","DOI":"10.1016\/j.tcs.2023.114105"},{"key":"7088_CR49","doi-asserted-by":"publisher","unstructured":"Stadtl\u00e4nder, E., Horv\u00e1th, T., & Wrobel, S. (2025). The local convexification method and its application to learning weakly convex boolean functions. In: Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2025, Porto, Portugal, September 15\u201319, 2025, Proceedings, Part IV, pp. 417\u2013435. Springer, Berlin, Heidelberg https:\/\/doi.org\/10.1007\/978-3-032-06078-5_24","DOI":"10.1007\/978-3-032-06078-5_24"},{"issue":"1","key":"7088_CR50","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1093\/comjnl\/16.1.30","volume":"16","author":"R Sibson","year":"1973","unstructured":"Sibson, R. (1973). SLINK: an optimally efficient algorithm for the single-link cluster method. The Computer Journal, 16(1), 30\u201334. https:\/\/doi.org\/10.1093\/comjnl\/16.1.30","journal-title":"The Computer Journal"},{"key":"7088_CR51","unstructured":"Sundararajan, M., Taly, A., & Yan, Q. (2017). Axiomatic attribution for deep networks. In: Proceedings of the 34th International Conference on Machine Learning. ICML\u201917, pp. 3319\u20133328. JMLR.org, Sydney, Australia"},{"key":"7088_CR52","first-page":"23413","volume-title":"Advances in Neural Information Processing Systems","author":"M Thiessen","year":"2021","unstructured":"Thiessen, M., & G\u00e4rtner, T. (2021). Active learning of convex halfspaces on graphs. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, & J. W. Vaughan (Eds.), Advances in Neural Information Processing Systems (Vol. 34, pp. 23413\u201323425). Red Hook, NY, USA: Curran Associates Inc."},{"key":"7088_CR53","doi-asserted-by":"publisher","unstructured":"Thiessen, M., & G\u00e4rtner, T. (2022). Online learning of convex sets on graphs. In: Amini, M.-R., Canu, S., Fischer, A., Guns, T., Kralj\u00a0Novak, P., Tsoumakas, G. (eds.) Machine Learning and Knowledge Discovery in Databases, pp. 349\u2013364. Springer, Cham https:\/\/doi.org\/10.1007\/978-3-031-26412-2_22","DOI":"10.1007\/978-3-031-26412-2_22"},{"issue":"1","key":"7088_CR54","doi-asserted-by":"publisher","first-page":"697","DOI":"10.1007\/BF01181191","volume":"28","author":"H Tietze","year":"1928","unstructured":"Tietze, H. (1928). \u00dcber konvexheit im kleinen und im gro\u00dfen und \u00fcber gewisse den punkten einer menge zugeordnete dimensionszahlen. Mathematische Zeitschrift, 28(1), 697\u2013707. https:\/\/doi.org\/10.1007\/BF01181191","journal-title":"Mathematische Zeitschrift"},{"issue":"11","key":"7088_CR55","doi-asserted-by":"publisher","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134\u20131142. https:\/\/doi.org\/10.1145\/1968.1972","journal-title":"Communications of the ACM"},{"key":"7088_CR56","unstructured":"van de Vel, M.L.J. (1993). Theory of Convex Structures. North-Holland Mathematical Library, vol. 50. North-Holland, Amsterdam"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-026-07088-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-026-07088-w","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-026-07088-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,27]],"date-time":"2026-08-27T12:19:17Z","timestamp":1787833157000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-026-07088-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":56,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["7088"],"URL":"https:\/\/doi.org\/10.1007\/s10994-026-07088-w","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8]]},"assertion":[{"value":"19 March 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 March 2026","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2026","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2026","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors have no other financial or proprietary interests in any material discussed in this article.","order":1,"name":"Ethics","label":"Conflict of interest","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors assure that all potential conflict of interest have been disclosed above. All research performed in this article was done in accordance with the ethical standard of Springer ethics code of conduct.","order":2,"name":"Ethics","label":"Ethical Approval","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"All listed authors have agreed to submitting the attached article to the Machine Learning Journal.","order":3,"name":"Ethics","label":"Consent to Participate","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable. The authors assure that no figures, tables, and text passages have been obtained from third-party authors.","order":4,"name":"Ethics","label":"Consent for Publication","group":{"name":"EthicsHeading","label":"Declarations"}}],"article-number":"196"}}