Publications (Ulrike von Luxburg)

Papers that did not (yet) go though a serious peer-review process are cited in grey font.


Christian Elbracht, Diego Fioravanti, Solveig Klepper, Jakob Kneip, Luca Rendsburg, Maximilian Teegen, Ulrike von Luxburg. Tangles: From Weak to Strong Clustering

Sebasitan Bordt, Ulrike von Luxburg: When Humans and Machines Make Joint Decisions: A Non-Symmetric Bandit Model

Ulrike von Luxburg: Wie funktioniert maschinelles Lernen? Eine Einführung für jedermann und -frau.

Siavash Haghiri, Leena Chennuru Vankadara, Ulrike von Luxburg: Large scale representation learning from triplet comparisons. 2019 link to arxiv

Sascha Meyen, Iris A. Zerweck, Catarina Amado, Ulrike von Luxburg, Volker H. Franz: The unconscious priming fallacy: When can scientists truly claim an indirect task advantage? pdf

Accepted / published papers

Luca Rendsburg, Holger Heidrich, Ulrike von Luxburg: NetGAN without GAN: From Random Walks to Low-Rank Approximations. ICML 2020. pdf.

Michael Lohaus, Michael Perrot, Ulrike von Luxburg: Too Relaxed to Be Fair. ICML 2020. pdf

Damien Garreau, Ulrike von Luxburg: Explaining the Explainer: A First Theoretical Analysis of LIME. AISTATS, 2020. pdf

Siavash Haghiri, Felix Wichmann, Ulrike von Luxburg: Estimation of perceptual scales using ordinal embedding. Accepted at Journal of Vision, 2020. Final pdf to come soon. Link to arxiv

Debarghya Ghoshdastidar, Michael Perrot, Ulrike von Luxburg: Foundations of Comparison-Based Hierarchical Clustering. NeurIPS, 2019. Link to arxiv version, final pdf

Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg: Two-sample Hypothesis Testing for Inhomogeneous Random Graphs. Accepted at the Annals of Statistics, 2019. Arxiv version.

Michael Perrot, Ulrike von Luxburg: Boosting for Comparison-Based Learning, IJCAI, 2019. short conference version and long arxiv version with all proofs. Link to Code.

(IJCAI distinguished paper award!)

Cheng Tang, Damien Garreau, Ulrike von Luxburg: When do random forests fail? NeurIPS 2018. pdf

Leena Chennuru Vankadara, Ulrike von Luxburg: Measures of distortion for machine learning. NeurIPS 2018. pdf

Debarghya Ghoshdastidar, Ulrike von Luxburg: Practical Methods for Graph Two-Sample Testing. NeuRIPS 2018. pdf. Link to the code.

Nihar Shaw, Behzad Tabibian, Krikamol Muandet, Isabelle Guyon, Ulrike von Luxburg: Design and Analysis of the NIPS 2016 Review Process. JMLR 19(49): 1--34, 2018. pdf

Siavash Haghiri, Damien Garreau, Ulrike von Luxburg: Comparison-Based Random Forests. ICML 2018. pdf. Link to code

G. Blanchard, F. Göbel, U. von Luxburg. Construction of Tight Frames on Graphs and Application to Denoising. In Handbook of Big Data Analytics, Springer, 2018. pdf

Matthäus Kleindessner, Ulrike von Luxburg: Kernel functions based on triplet comparisons. NIPS 2017. pdf.

Matthäus Kleindessner, Ulrike von Luxburg: Lens depth function and k-relative neighborhood graph: versatile tools for ordinal data analysis. JMLR 18(58):1−52, 2017 pdf

Debarghya Ghoshdastidar, Maurillio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg. Two-sample tests for large random graphs using network statistics. COLT 2017pdf

Siavash Haghiri, Debarghya Ghoshdastidar, Ulrike von Luxburg: Comparison based nearest neighbor search. AISTATS 2017. pdf Link to code.

Mehdi Sajjadi, Morteza Alamgir, Ulrike von Luxburg: Peer grading in a course on algorithms and data structures: machine learning algorithms do not improve over simple baselines. Proceedings of the third annual ACM conference on Learning at Scale, 2016. pdf Link to our data set. (An earlier version of this paper had been presented at the ICML 2015 workshop for Machine Learning for Education.)

Tobias Lang, Florian Flachsenberg, Ulrike von Luxburg, Matthias Rarey: Feasibility of Active Machine Learning for Multiclass Compound Classification. Journal of Chemical Information and Modeling, Jan 2016. doi

Volker Franz, Ulrike von Luxburg: No evidence for unconscious lie detection: A significant difference does not imply accurate classification. Psychological Science, 2015. official pdf   pdf of the published paper  pdf of an earlier preprint that contains more details  DOI  open materials (data, scripts) 

Matthäus Kleindessner, Ulrike von Luxburg: Dimensionality estimation without distances. AISTATS, 2015. pdf

Kamalika Chaudhuri, Sanjoy Dasgupta, Samory Kpotufe, Ulrike von Luxburg. Consistent procedures for cluster tree estimation and pruning. IEEE Transactions on Information Theory 60, 7900-7912, 2014 preprint   DOI

C. Hilgetag, U. von Luxburg. Brain network science needs to become predictive. Comment on “Understanding brain networks and brain organization” by Luiz Pessoa. Physics of Life Review 11 (3), pp. 446-447, 2014. pdf (preprint)   link

Y. Terada, U. von Luxburg. Local Ordinal Embedding. International Conference of Machine Learning (ICML), 2014. pdf. Link to the R-codecode.

M. Kleindessner, U. von Luxburg. Uniqueness of ordinal embedding. Conference of Learning Theory (COLT), 2014. pdf

(Runner-up for the best student paper award. )

M. Alamgir, U. von Luxburg, G. Lugosi. Density-preserving quantization with application to graph downsampling. Conference of Learning Theory (COLT), 2014 pdf

S. Kurras, U. von Luxburg, G. Blanchard. The f-adjusted graph Laplacian: a diagonal modification with a geometric interpretation. International Conference of Machine Learning (ICML), 2014 pdf (includes supplement)

U. von Luxburg, A. Radl, M. Hein. Hitting and commute times in large random neighborhood graphs. Journal of Machine Learning Research (JMLR) 15, pp. 1751−1798, 2014. pdf
(Note: an earlier version of this manuscript contained much more about the intuition why the results hold. All this intuition gradually had to vanish in a lengthy review process, which is a pitty. If you still want to get the intuitive arguments, you can still read them in the old arxiv version)

U. von Luxburg, M. Alamgir. Density estimation from unweighted kNN graphs: a roadmap. NIPS 2013. pdf

M. Maier, U. von Luxburg, M. Hein: How the result of graph clustering methods depends on the construction of the graph. ESAIM: Probability and Statistics, vol. 17, pp. 370-418, 2013.   pdf   link

K. Oschema, M. Helbling, U. von Luxburg (editors): Wissenschaft 2014: Ein Kalender der Ambivalenzen. Thorbecke Verlag, 2013. ISBN 978-3-7995-0425-6. link

M. Alamgir, U. von Luxburg. Shortest path distance in random k-nearest neighbor graphs. International Conference on Machine Learning (ICML), 2012. pdf

S. Bubeck, M. Meila, U. von Luxburg. How the initialization affects the stability of the k-means algorithm. ESAIM: Probability and Statistics 16, p. 436--452, 2012 pdf

M. Alamgir and U. von Luxburg. Phase transition in the family of p-resistances. NIPS, 2011. pdf (which includes supplement)   a typo

U. von Luxburg, R. Williamson, I. Guyon: Clustering: Science or Art? Workshop on Unsupervised Learning and Transfer Learning, JMLR Workshop and Conference Proceedings 27, p. 65-79, 2012. pdf

D. Garcia-Garcia and U. von Luxburg and R. Santos-Rodriguez. Risk-based generalizations of f-divergences. International Conference on Machine Learning (ICML), 2011 pdf

S. Kpotufe and U. von Luxburg. Pruning nearest neighbor cluster trees. International Conference on Machine Learning (ICML), 2011 pdf

U. von Luxburg and B. Schölkopf. Statistical Learning Theory: Models, Concepts, and Results. In: D. Gabbay, S. Hartmann and J. Woods (Eds). Handbook of the History of Logic, vol 10, pp. 751-706, 2011. pdf

M. Alamgir and U. von Luxburg: Multi-agent random walks for local clustering. International Conference on Data Minig (ICDM), 2010. pdf

U. von Luxburg and A. Radl and M. Hein: Getting lost in space: Large sample analysis of the commute distance. Neural Information Processing Systems (NIPS), 2010. pdf (paper with supplement)   An annoying typo

U. von Luxburg. Clustering stability: an overview. Foundations and Trends in Machine Learning 2 (3), 235-274, 2010. pdf

U. von Luxburg. Evidenzkriterien in der Informatik (in German). In: E. Engelen and C. Fleischhack and G. Galizia and K. Landfester (Eds): Heureka: Evidenzkriterien in den Wissenschaften. Springer, Berlin, 2010. pdf and link to the book

S. Bubeck and U. von Luxburg. Nearest Neighbor Clustering: A Baseline Method for Consistent Clustering with Arbitrary Objective Functions. Journal of Machine Learning Research (JMLR) 10, 657-698, 2009. pdf
(Note: a previous version of this manuscript was called "Overfitting of clustering and how to avoid it").

M. Maier, U. von Luxburg, M. Hein: Influence of graph construction on graph-based clustering measures. In: D. Koller and D. Schuurmans and Y. Bengio and L. Bottou (Eds.): Advances in Neural Information Processing Systems (NIPS) 22, 2009. paper (pdf) and supplement (pdf)

(NIPS best student paper award.).

M. Maier and M. Hein and U. von Luxburg. Optimal construction of k-nearest neighbor graphs for identifying noisy clusters. Theoretical Computer Science 410, p. 1749-1764, 2009. preprint as pdf

U. von Luxburg and V. Franz. A Geometric Approach to Confidence Sets for Ratios: Fieller's Theorem, Generalizations, and Bootstrap. Statistica Sinica 19 (3), pp. 1095 - 1117, 2009
preprint of the paper (pdf) and supplement (pdf)

U. von Luxburg, S. Bubeck, S. Jegelka, M. Kaufmann: Consistent Minimization of Clustering Objective Functions. In: J. Platt and D. Koller and Y. Singer and S. Roweis (editors): Advances in Neural Information Processing Systems (NIPS) 21, MIT Press, Cambridge, MA. 2008
paper (pdf) and supplement (pdf).

S. Ben-David and U. von Luxburg: Relating clustering stability to properties of cluster boundaries. In: R. Servedio and T. Zhang (Eds.): Proceedings of the 21st Annual Conference on Learning Theory (COLT), pp. 379-390. Springer, Berlin, 2008. pdf

U. von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. Annals of Statistics, 36 (2), 555-586, 2008 pdf

M. Maier, M. Hein, U. von Luxburg. Cluster identification in nearest neighbor graphs. In: Marcus Hutter and Rocco A. Servedio and Eiji Takimoto (Eds): Algorithmic Learning Theory (ALT) 18, pp. 196--210. Springer, 2007. pdf (conference paper), pdf (technical report with proof details)

(ALT best student paper award.)

U. von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing 17(4): 395-416, 2007. paper (pdf) and some typos (txt).
There also exists a video lecture where I give a tutorial on spectral clustering (and other clustering algorithms). And here is a matlab demo which can be used to play with spectral clustering (written by Matthias Hein and me).

Matthias Hein, Jean-Yves Audibert, Ulrike von Luxburg. Graph Laplacians and their Convergence on Random Neighborhood Graphs. Journal of Machine Learning Research (JMLR) 8:1325--1370, 2007. pdf

S. Ben-David, U.von Luxburg, D. Pal: A Sober Look on Clustering Stability. In: G. Lugosi and H. Simon, editors, Proceedings of the 19th Annual Conference on Learning Theory (COLT), pages 5 - 19, Springer, 2006. pdf

(COLT best student paper award)

M. Hein, J.-Y. Audibert, and U. von Luxburg. From Graphs to Manifolds - Weak and Strong Pointwise Consistency of Graph Laplacians. In: P. Auer and Ron Meir, editors, Proceedings of the 18th Annual Conferecnce on Learning Theory (COLT), pages 470-485. Springer, 2005. pdf

(COLT best student paper award)

U. von Luxburg, S. Ben-David. Towards a statistical theory for clustering. Presented at the PASCAL Workshop on Statistics and Optimization of Clustering Workshop 4-5 July 2005, London, U.K. pdf.
[This opinion paper suggested some kind of "research program". Note that in the meantime, some of the questions have already been solved, while some of the other questions turned out to be not so useful after all...]

U. von Luxburg, O. Bousquet, and M. Belkin. Limits of spectral clustering. In Lawrence K. Saul, Yair Weiss, and Leon Bottou, editors, Advances in Neural Information Processing Systems (NIPS) 17. MIT Press, Cambridge, MA, 2005. pdf

(NIPS outstanding student paper award)

U. von Luxburg, O. Bousquet, and M. Belkin. On the convergence of spectral clustering on random samples: the normalized case. In J. Shawe-Taylor and Y. Singer, editors, Proceedings of the 17th Annual Conference on Learning Theory (COLT), pages 457-471. Springer, 2004. pdf

U. von Luxburg and O. Bousquet. Distance-based classification with Lipschitz functions. Journal for Machine Learning Research (JMLR), 5:669-695, 2004. pdf

U. von Luxburg, O.Bousquet, and B.Schölkopf. A compression approach to support vector model selection. Journal for Machine Learning Research (JMLR), 5:293-323, 2004. pdf

U.von Luxburg and O.Bousquet. Distance-based classification with Lipschitz functions. In B.Schölkopf and M.K. Warmuth, editors, Proceedings of the 16th Annual Conference on Learning Theory (COLT), pages 314-328. Springer, 2003. pdf

(COLT Mark Fulk best student paper award).

Edited Books

S. Kakade and U. von Luxburg Proceedings of the 24th Annual Conference on Learning Theory link June 9-11, 2011, Budapest, Hungary. JMLR Workshop and Conference Series, volume 19, 2011.

O. Bousquet, U. von Luxburg, and G.Rätsch, editors. Advanced Lectures on Machine Learning, volume 3176 of Springer Lecture Notes in Artificial Intelligence. Springer Verlag, Heidelberg, 2004. link

PhD Thesis

U. von Luxburg. Statistical Learning with Similarity and Dissimilarity Functions. PhD thesis, Technical University of Berlin, 2004. pdf