{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T00:07:17Z","timestamp":1767917237661,"version":"3.49.0"},"reference-count":39,"publisher":"Springer Science and Business Media LLC","issue":"11","license":[{"start":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T00:00:00Z","timestamp":1595894400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T00:00:00Z","timestamp":1595894400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004063","name":"Knut och Alice Wallenbergs Stiftelse","doi-asserted-by":"publisher","award":["37200022"],"award-info":[{"award-number":["37200022"]}],"id":[{"id":"10.13039\/501100004063","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2020,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We investigate the use of Minimax distances to extract in a nonparametric way the features that capture the unknown underlying patterns and structures in the data. We develop a general-purpose and computationally efficient framework to employ Minimax distances with many machine learning methods that perform on numerical data. We study both computing the pairwise Minimax distances for all pairs of objects and as well as computing the Minimax distances of all the objects to\/from a fixed (test) object. We first efficiently compute the pairwise Minimax distances between the objects, using the equivalence of Minimax distances over a graph and over a minimum spanning tree constructed on that. Then, we perform an embedding of the pairwise Minimax distances into a new vector space, such that their squared Euclidean distances in the new space equal to the pairwise Minimax distances in the original space. We also study the case of having multiple pairwise Minimax matrices, instead of a single one. Thereby, we propose an embedding via first summing up the centered matrices and then performing an eigenvalue decomposition to obtain the relevant features. In the following, we study computing Minimax distances from a fixed (test) object which can be used for instance in<jats:italic>K<\/jats:italic>-nearest neighbor search. Similar to the case of all-pair pairwise Minimax distances, we develop an efficient and general-purpose algorithm that is applicable with any arbitrary base distance measure. Moreover, we investigate in detail the edges selected by the Minimax distances and thereby explore the ability of Minimax distances in detecting outlier objects. Finally, for each setting, we perform several experiments to demonstrate the effectiveness of our framework.<\/jats:p>","DOI":"10.1007\/s10994-020-05886-4","type":"journal-article","created":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T22:02:38Z","timestamp":1595973758000},"page":"2063-2097","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["Unsupervised representation learning with Minimax distance measures"],"prefix":"10.1007","volume":"109","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2912-7422","authenticated-orcid":false,"given":"Morteza","family":"Haghir Chehreghani","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,7,28]]},"reference":[{"key":"5886_CR1","volume-title":"The design and analysis of computer algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A. V., & Hopcroft, J. E. (1974). The design and analysis of computer algorithms (1st ed.). Boston, MA: Addison-Wesley Longman Publishing Co., Inc.","edition":"1"},{"issue":"1","key":"5886_CR2","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/j.patcog.2007.04.010","volume":"41","author":"H Chang","year":"2008","unstructured":"Chang, H., & Yeung, D.-Y. (2008). Robust path-based spectral clustering. Pattern Recognition, 41(1), 191\u2013203.","journal-title":"Pattern Recognition"},{"issue":"5","key":"5886_CR3","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1016\/j.dam.2010.11.017","volume":"159","author":"P Chebotarev","year":"2011","unstructured":"Chebotarev, P. (2011). A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Applied Mathematics, 159(5), 295\u2013302.","journal-title":"Discrete Applied Mathematics"},{"key":"5886_CR4","doi-asserted-by":"crossref","unstructured":"Chehreghani, M. H. (2017). Efficient computation of pairwise minimax distance measures. In 2017 IEEE international conference on data mining, ICDM (pp. 799\u2013804). IEEE Computer Society.","DOI":"10.1109\/ICDM.2017.95"},{"key":"5886_CR5","unstructured":"Chehreghani, M. H. (2020). Hierarchical correlation clustering and tree preserving embedding. CoRR, abs\/2002.07756."},{"issue":"2\u20133","key":"5886_CR6","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/s10994-016-5573-9","volume":"104","author":"MH Chehreghani","year":"2016","unstructured":"Chehreghani, M. H. (2016). Adaptive trajectory analysis of replicator dynamics for data clustering. Machine Learning, 104(2\u20133), 271\u2013289.","journal-title":"Machine Learning"},{"key":"5886_CR7","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T. H., Stein, C., Rivest, R. L., & Leiserson, C. E. (2001). Introduction to algorithms (2nd ed.). New York: McGraw-Hill Higher Education.","edition":"2"},{"key":"5886_CR8","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"EW Dijkstra","year":"1959","unstructured":"Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1, 269\u2013271.","journal-title":"Numerische Mathematik"},{"key":"5886_CR23","unstructured":"Dua, D., & Graff, C. (2019). UCI machine learning repository [http:\/\/archive.ics.uci.edu\/ml]. Irvine, CA: University of California, School of Information and Computer Science."},{"key":"5886_CR9","first-page":"23","volume":"3","author":"M Fiedler","year":"1998","unstructured":"Fiedler, M. (1998). Ultrametric sets in euclidean point spaces. ELA. The Electronic Journal of Linear Algebra, 3, 23\u201330.","journal-title":"ELA. The Electronic Journal of Linear Algebra"},{"issue":"4","key":"5886_CR10","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1109\/TPAMI.2003.1190577","volume":"25","author":"B Fischer","year":"2003","unstructured":"Fischer, B., & Buhmann, J. M. (2003). Path-based clustering for grouping of smooth curves and texture segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25(4), 513\u2013518.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"5886_CR11","doi-asserted-by":"publisher","first-page":"5372","DOI":"10.1016\/j.neunet.2012.03.001","volume":"31","author":"F Fouss","year":"2012","unstructured":"Fouss, F., Francoisse, K., Yen, L., Pirotte, A., & Saerens, M. (2012). An experimental investigation of kernels on graphs for collaborative recommendation and semisupervised classification. Neural Networks, 31, 5372.","journal-title":"Neural Networks"},{"issue":"3","key":"5886_CR12","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1109\/TKDE.2007.46","volume":"19","author":"F Fouss","year":"2007","unstructured":"Fouss, F., Pirotte, A., Renders, J.-M., & Saerens, M. (2007). Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering, 19(3), 355\u2013369.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"issue":"2","key":"5886_CR13","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1007\/BF02579168","volume":"6","author":"HN Gabow","year":"1986","unstructured":"Gabow, H. N., Galil, Z., Spencer, T., & Tarjan, R. E. (1986). Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6(2), 109\u2013122.","journal-title":"Combinatorica"},{"key":"5886_CR14","first-page":"2265","volume":"8","author":"A Globerson","year":"2007","unstructured":"Globerson, A., Chechik, G., Pereira, F., & Tishby, N. (2007). Euclidean embedding of co-occurrence data. Journal of Machine Learning Research, 8, 2265\u20132295.","journal-title":"Journal of Machine Learning Research"},{"issue":"3","key":"5886_CR15","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1214\/009053607000000677","volume":"36","author":"T Hofmann","year":"2008","unstructured":"Hofmann, T., Sch\u00f6lkopf, B., & Smola, A. J. (2008). Kernel methods in machine learning. Annals of Statistics, 36(3), 1171\u20131220.","journal-title":"Annals of Statistics"},{"key":"5886_CR16","volume-title":"Matrix analysis","year":"1990","unstructured":"Horn, R. A., & Johnson, C. R. (Eds.). (1990). Matrix analysis. Cambridge: Cambridge University Press."},{"key":"5886_CR17","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1287\/opre.9.6.898","volume":"9","author":"TC Hu","year":"1961","unstructured":"Hu, T. C. (1961). The maximum capacity route problem. Operations Research, 9, 898\u2013900.","journal-title":"Operations Research"},{"issue":"1","key":"5886_CR18","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1007\/BF01908075","volume":"2","author":"L Hubert","year":"1985","unstructured":"Hubert, L., & Arabie, P. (1985). Comparing partitions. Journal of Classification, 2(1), 193\u2013218.","journal-title":"Journal of Classification"},{"key":"5886_CR19","doi-asserted-by":"crossref","unstructured":"Khoshneshin, M., & Street, W. N. (2010). Collaborative filtering via euclidean embedding. In Proceedings of the 2010 ACM conference on recommender systems, RecSys 2010, Barcelona, Spain, 26\u201330 September 2010 (pp. 87\u201394).","DOI":"10.1145\/1864708.1864728"},{"key":"5886_CR20","doi-asserted-by":"crossref","unstructured":"Kim, K.-H., & Choi, S. (2007). Neighbor search with global geometry: A minimax message passing algorithm. In ICML (pp. 401\u2013408).","DOI":"10.1145\/1273496.1273547"},{"key":"5886_CR21","doi-asserted-by":"crossref","unstructured":"Kim, K.-H. & Choi, S. (2013). Walking on minimax paths for k-nn search. In AAAI.","DOI":"10.1609\/aaai.v27i1.8588"},{"issue":"2","key":"5886_CR22","doi-asserted-by":"publisher","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"FR Kschischang","year":"2006","unstructured":"Kschischang, F. R., Frey, B. J., & Loeliger, H. A. (2006). Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, 47(2), 498\u2013519.","journal-title":"IEEE Transactions on Information Theory"},{"issue":"4","key":"5886_CR24","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Luxburg","year":"2007","unstructured":"Luxburg, U. (2007). A tutorial on spectral clustering. Statistics and Computing, 17(4), 395\u2013416.","journal-title":"Statistics and Computing"},{"key":"5886_CR26","first-page":"1017","volume":"19","author":"B Nadler","year":"2007","unstructured":"Nadler, B., & Galun, M. (2007). Fundamental limitations of spectral clustering. Advanced in Neural Information Processing Systems, 19, 1017\u20131024.","journal-title":"Advanced in Neural Information Processing Systems"},{"issue":"1","key":"5886_CR27","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1109\/TPAMI.2007.250608","volume":"29","author":"M Pavan","year":"2007","unstructured":"Pavan, M., & Pelillo, M. (2007). Dominant sets and pairwise clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 29(1), 167\u2013172.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"issue":"6","key":"5886_CR28","doi-asserted-by":"publisher","first-page":"1389","DOI":"10.1002\/j.1538-7305.1957.tb01515.x","volume":"36","author":"RC Prim","year":"1957","unstructured":"Prim, R. C. (1957). Shortest connection networks and some generalizations. The Bell Systems Technical Journal, 36(6), 1389\u20131401.","journal-title":"The Bell Systems Technical Journal"},{"key":"5886_CR29","doi-asserted-by":"crossref","unstructured":"Quarteroni, A., Sacco, R., & Saleri, F. (2007). Approximation of eigenvalues and eigenvectors. Numerical Mathematics, 37, 183\u2013244.","DOI":"10.1007\/978-3-540-49809-4_5"},{"issue":"4","key":"5886_CR31","doi-asserted-by":"publisher","first-page":"787","DOI":"10.2307\/1968835","volume":"38","author":"IJ Schoenberg","year":"1937","unstructured":"Schoenberg, I. J. (1937). On certain metric spaces arising from euclidean spaces by a change of metric and their imbedding in hilbert space. Annals of Mathematics, 38(4), 787\u2013793.","journal-title":"Annals of Mathematics"},{"key":"5886_CR32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809682","volume-title":"Kernel methods for pattern analysis","author":"J Shawe-Taylor","year":"2004","unstructured":"Shawe-Taylor, J., & Cristianini, N. (2004). Kernel methods for pattern analysis. Cambridge: Cambridge University Press."},{"issue":"5500","key":"5886_CR33","doi-asserted-by":"publisher","first-page":"2319","DOI":"10.1126\/science.290.5500.2319","volume":"290","author":"JB Tenenbaum","year":"2000","unstructured":"Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science, 290(5500), 2319.","journal-title":"Science"},{"key":"5886_CR34","volume-title":"Theory and methods of scaling","author":"WS Torgerson","year":"1958","unstructured":"Torgerson, W. S. (1958). Theory and methods of scaling. Hoboken: Wiley."},{"key":"5886_CR30","doi-asserted-by":"crossref","unstructured":"Varga, R. S., & Nabben R. (1993). On symmetric ultrametric matrices. Numerical Linear Algebra, 193\u2013200.","DOI":"10.1515\/9783110857658.193"},{"key":"5886_CR35","doi-asserted-by":"publisher","first-page":"1273","DOI":"10.1109\/TPAMI.2002.1033218","volume":"24","author":"CJ Veenman","year":"2002","unstructured":"Veenman, C. J., Reinders, M. J. T., & Backer, E. (2002). A maximum variance cluster algorithm. IEEE Transactions on Pattern Analysis and Machine Intelligence, 24, 1273\u20131280.","journal-title":"IEEE Transactions on Pattern Analysis and Machine Intelligence"},{"key":"5886_CR36","first-page":"2837","volume":"11","author":"NX Vinh","year":"2010","unstructured":"Vinh, N. X., Epps, J., & Bailey, J. (2010). Information theoretic measures for clusterings comparison: Variants, properties, normalization and correction for chance. Journal of Machine Learning Research, 11, 2837\u20132854.","journal-title":"Journal of Machine Learning Research"},{"key":"5886_CR37","first-page":"207","volume":"10","author":"KQ Weinberger","year":"2009","unstructured":"Weinberger, K. Q., & Saul, L. K. (2009). Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10, 207\u2013244.","journal-title":"Journal of Machine Learning Research"},{"key":"5886_CR38","doi-asserted-by":"crossref","unstructured":"Yen, L., Saerens, M., Mantrach, A., & Shimbo, M. (2008). A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances. In KDD (pp. 785\u2013793).","DOI":"10.1145\/1401890.1401984"},{"issue":"1","key":"5886_CR39","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/BF02287916","volume":"3","author":"G Young","year":"1938","unstructured":"Young, G., & Householder, A. (1938). Discussion of a set of points in terms of their mutual distances. Psychometrika, 3(1), 19\u201322.","journal-title":"Psychometrika"},{"key":"5886_CR40","unstructured":"Zadeh, R., & Ben-David, S. (2009). A uniqueness theorem for clustering. In UAI (pp. 639\u2013646)."}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-020-05886-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10994-020-05886-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-020-05886-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,11,4]],"date-time":"2022-11-04T22:38:08Z","timestamp":1667601488000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10994-020-05886-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,7,28]]},"references-count":39,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2020,11]]}},"alternative-id":["5886"],"URL":"https:\/\/doi.org\/10.1007\/s10994-020-05886-4","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,7,28]]},"assertion":[{"value":"27 June 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 March 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 July 2020","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}