{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,24]],"date-time":"2026-06-24T03:29:15Z","timestamp":1782271755356,"version":"3.54.5"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,4,1]],"date-time":"2021-04-01T00:00:00Z","timestamp":1617235200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T00:00:00Z","timestamp":1618185600000},"content-version":"vor","delay-in-days":11,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC 2064\/1 number 390727645"],"award-info":[{"award-number":["EXC 2064\/1 number 390727645"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["FKZ: 01IS18039A"],"award-info":[{"award-number":["FKZ: 01IS18039A"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Int J Data Sci Anal"],"published-print":{"date-parts":[[2021,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Recently, learning only from ordinal information of the type \u201citem<jats:italic>x<\/jats:italic>is closer to item<jats:italic>y<\/jats:italic>than to item<jats:italic>z<\/jats:italic>\u201d has received increasing attention in the machine learning community. Such triplet comparisons are particularly well suited for learning from crowdsourced human intelligence tasks, in which workers make statements about the relative distances in a triplet of items. In this paper, we systematically investigate comparison-based centrality measures on triplets and theoretically analyze their underlying Euclidean notion of centrality. Two such measures already appear in the literature under opposing approaches, and we propose a third measure, which is a natural compromise between these two. We further discuss their relation to statistical depth functions, which comprise desirable properties for centrality measures, and conclude with experiments on real and synthetic datasets for medoid estimation and outlier detection.<\/jats:p>","DOI":"10.1007\/s41060-021-00254-4","type":"journal-article","created":{"date-parts":[[2021,4,12]],"date-time":"2021-04-12T06:02:30Z","timestamp":1618207350000},"page":"243-259","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Comparison-based centrality measures"],"prefix":"10.1007","volume":"11","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6561-831X","authenticated-orcid":false,"given":"Luca","family":"Rendsburg","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Damien","family":"Garreau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2021,4,12]]},"reference":[{"key":"254_CR1","unstructured":"Agarwal, S., Wills, J., Cayton, L., Lanckriet, G., Kriegman, D., Belongie, S.: Generalized non-metric multidimensional scaling. In: AISTATS, pp. 11\u201318 (2007)"},{"key":"254_CR2","unstructured":"Amid, E., Ukkonen, A.: Multiview triplet embedding: learning attributes in multiple maps. In: ICML, pp. 1472\u20131480 (2015)"},{"issue":"3","key":"254_CR3","first-page":"1663","volume":"23","author":"E Arias-Castro","year":"2017","unstructured":"Arias-Castro, E.: Some theory for ordinal embedding. Bernoulli Soc. Math. Stat. Probab. 23(3), 1663\u20131693 (2017)","journal-title":"Bernoulli Soc. Math. Stat. Probab."},{"issue":"1","key":"254_CR4","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"key":"254_CR5","unstructured":"Bengio, Y.: Deep learning of representations for unsupervised and transfer learning. In: Proceedings of ICML Workshop on Unsupervised and Transfer Learning, pp. 17\u201336 (2012)"},{"key":"254_CR6","doi-asserted-by":"crossref","unstructured":"Deng, J., Dong, W., Socher, R., Li, L., Kai L., Li F.-F.: Imagenet: a large-scale hierarchical image database. In: CVPR, pp. 248\u2013255 (2009)","DOI":"10.1109\/CVPR.2009.5206848"},{"key":"254_CR7","doi-asserted-by":"crossref","unstructured":"Emamjomeh-Zadeh, E., Kempe, D.: Adaptive hierarchical clustering using ordinal queries. In: SODA, pp. 415\u2013429 (2018)","DOI":"10.1137\/1.9781611975031.28"},{"issue":"1","key":"254_CR8","first-page":"134","volume":"17","author":"R Fagin","year":"2003","unstructured":"Fagin, R., Kumar, R., Sivakumar, D.: Comparing top k lists. SODA 17(1), 134\u2013160 (2003)","journal-title":"SODA"},{"key":"254_CR9","unstructured":"Ghoshdastidar, D., Perrot, M., von Luxburg, U.: Foundations of comparison-based hierarchical clustering. In: NIPS, pp. 7456\u20137466 (2019)"},{"key":"254_CR10","unstructured":"Haghiri, S., Ghoshdastidar, D., von Luxburg, U.: Comparison-Based Nearest Neighbor Search. In: AISTATS, vol. 54, pp. 851\u2013859 (2017)"},{"key":"254_CR11","unstructured":"Haghiri, S., Garreau, D., von Luxburg, U.: Comparison-based random forests. In: ICML, vol. 80, pp. 1871\u20131880 (2018)"},{"key":"254_CR12","doi-asserted-by":"crossref","unstructured":"Heikinheimo, H., Ukkonen, A.: The crowd-median algorithm. In: HCOMP, pp. 69\u201377 (2013)","DOI":"10.1609\/hcomp.v1i1.13079"},{"key":"254_CR13","unstructured":"Jain, L., Jamieson, K.G., Nowak, R.: Finite sample prediction and recovery bounds for ordinal embedding. In: NIPS, pp. 2711\u20132719 (2016)"},{"key":"254_CR14","doi-asserted-by":"crossref","unstructured":"Jamieson, K.G., Nowak, R.D.: Low-dimensional embedding using adaptively selected ordinal data. In: 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 1077\u20131084 (2011)","DOI":"10.1109\/Allerton.2011.6120287"},{"key":"254_CR15","unstructured":"Kleindessner, M., Luxburg, U.: Uniqueness of ordinal embedding. In: COLT, pp. 40\u201367 (2014)"},{"key":"254_CR16","unstructured":"Kleindessner, M., Luxburg, U.: Dimensionality estimation without distances. In: AISTATS, pp. 471\u2013479 (2015)"},{"key":"254_CR17","unstructured":"Kleindessner, M., von Luxburg, U.: Kernel functions based on triplet comparisons. In: NIPS, pp. 6807\u20136817 (2017a)"},{"key":"254_CR18","unstructured":"Kleindessner, M., von Luxburg, U.: Lens depth function and k-relative neighborhood graph: versatile tools for ordinal data analysis. In: JMLR, pp. 1\u201352 (2017b)"},{"key":"254_CR19","unstructured":"Krizhevsky, A., Sutskever, I., Hinton, G.E.: Imagenet classification with deep convolutional neural networks. In: NIPS, pp. 1097\u20131105 (2012)"},{"issue":"11","key":"254_CR20","doi-asserted-by":"publisher","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86(11), 2278\u20132324 (1998)","journal-title":"Proc. IEEE"},{"issue":"4","key":"254_CR21","doi-asserted-by":"publisher","first-page":"1063","DOI":"10.1080\/10485252.2011.584621","volume":"23","author":"Z Liu","year":"2011","unstructured":"Liu, Z., Modarres, R.: Lens data depth and median. J. Nonparametric Stat. 23(4), 1063\u20131074 (2011)","journal-title":"J. Nonparametric Stat."},{"issue":"3","key":"254_CR22","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1023\/A:1011139631724","volume":"42","author":"A Oliva","year":"2001","unstructured":"Oliva, A., Torralba, A.: Modeling the shape of the scene: a holistic representation of the spatial envelope. IJCV 42(3), 145\u2013175 (2001)","journal-title":"IJCV"},{"key":"254_CR23","doi-asserted-by":"publisher","unstructured":"Perrot, M., von Luxburg, U.: Boosting for comparison-based learning. In: IJCAI-19, pp. 1844\u20131850 (2019). https:\/\/doi.org\/10.24963\/ijcai.2019\/255","DOI":"10.24963\/ijcai.2019\/255"},{"key":"254_CR24","unstructured":"Schultz, M., Joachims, T.: Learning a distance metric from relative comparisons. In: NIPS, pp. 41\u201348 (2004)"},{"key":"254_CR25","volume-title":"Support Vector Machines","author":"I Steinwart","year":"2008","unstructured":"Steinwart, I., Christmann, A.: Support Vector Machines. Springer, New York (2008)"},{"key":"254_CR26","unstructured":"Tamuz, O., Liu, C., Belongie, S., Shamir, O., Kalai, A.T.: Adaptively learning the crowd kernel. In: ICML, pp. 673\u2013680 (2011)"},{"key":"254_CR27","unstructured":"Terada, Y., Luxburg, U.: Local ordinal embedding. In: ICML, vol. 32, pp. 847\u2013855 (2014)"},{"key":"254_CR28","doi-asserted-by":"publisher","unstructured":"Ukkonen, A.: Crowdsourced correlation clustering with relative distance comparisons. In: ICDM, pp. 1117\u20131122 (2017). https:\/\/doi.org\/10.1109\/ICDM.2017.148","DOI":"10.1109\/ICDM.2017.148"},{"key":"254_CR29","doi-asserted-by":"crossref","unstructured":"Ukkonen, A., Derakhshan, B., Heikinheimo, H.: Crowdsourced nonparametric density estimation using relative distances. In: HCOMP (2015)","DOI":"10.1609\/hcomp.v3i1.13232"},{"key":"254_CR30","doi-asserted-by":"crossref","unstructured":"Van Der\u00a0Maaten, L., Weinberger, K.: Stochastic triplet embedding. In: MLSP, pp. 1\u20136 (2012)","DOI":"10.1109\/MLSP.2012.6349720"},{"key":"254_CR31","volume-title":"Statistical Learning Theory","author":"VN Vapnik","year":"1998","unstructured":"Vapnik, V.N.: Statistical Learning Theory. Wiley, New York (1998)"},{"key":"254_CR32","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596","volume-title":"High-Dimensional Probability: An Introduction with Applications in Data Science","author":"R Vershynin","year":"2018","unstructured":"Vershynin, R.: High-Dimensional Probability: An Introduction with Applications in Data Science, vol. 47. Cambridge University Press, Cambridge (2018)"},{"key":"254_CR33","unstructured":"Vikram, S., Dasgupta, S.: Interactive bayesian hierarchical clustering. In: ICML, pp. 2081\u20132090 (2016)"},{"key":"254_CR34","unstructured":"Yosinski, J., Clune, J., Bengio, Y., Lipson, H.: How transferable are features in deep neural networks? In: NIPS, pp. 3320\u20133328 (2014)"},{"key":"254_CR35","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1016218226","author":"Y Zuo","year":"2000","unstructured":"Zuo, Y., Sering, R.: General notions of statistical depth function. Ann. Stat. (2000). https:\/\/doi.org\/10.1214\/aos\/1016218226","journal-title":"Ann. Stat."}],"container-title":["International Journal of Data Science and Analytics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41060-021-00254-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s41060-021-00254-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s41060-021-00254-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,24]],"date-time":"2022-12-24T01:45:56Z","timestamp":1671846356000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s41060-021-00254-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["254"],"URL":"https:\/\/doi.org\/10.1007\/s41060-021-00254-4","relation":{},"ISSN":["2364-415X","2364-4168"],"issn-type":[{"value":"2364-415X","type":"print"},{"value":"2364-4168","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,4]]},"assertion":[{"value":"24 September 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"10 March 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 April 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"There is no code available.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}]}}