# Publications (Ulrike von Luxburg)

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

## Preprints

Debarghya Ghoshdastidar, Maurilio Gutzeit, Alexandra Carpentier, Ulrike von Luxburg: Two-sample Hypothesis Testing for Inhomogeneous Random Graphs. Arxiv, 2017.

## Accepted / published papers

Matthäus Kleindessner, Ulrike von Luxburg: Kernel functions based on triplet comparisons. Accepted at NIPS 2017. pdf to come soon.

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

D. Ghoshdastidar, M. Gutzeit, A. Carpentier, U. von Luxburg. Two-sample tests for large random graphs using network statistics. COLT 2017pdf

S. Haghiri, D. Ghoshdastidar, U. von Luxburg: Comparison based nearest neighbor search. AISTATS 2017. pdf

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, preprint of the published paper pdf, 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 (includes supplement)

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

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

This is a calendar that we edited in the context of the German Young Academy (it is in German language). For each week of 2014, it presents a scientific question and explains why the answer to this question can't simply be "yes" or "no".

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

This is a high level overview paper on statistical learning theory. We try to convey the major ideas and insights of SLT, rather than to dive into technical details. It is intended for a broader audience - we do not assume that the reader is particularly familiar with machine learning.

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

This article has been written for a book that compares how different scientific disciplines establish their results and what kind of evidence one has to give before a result is considered to be true. 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)

(For this paper Markus Maier received the 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)

(For this paper Markus Maier received the 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

(For this paper David Pal received a 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

(For this paper Matthias Hein received a 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

(For this paper I received the 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

(For this paper I received the 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