Andrew Draganov

SODA Conference 2025 Conference Paper

A Tight VC-Dimension Analysis of Clustering Coresets with Applications

• Vincent Cohen-Addad
• Andrew Draganov
• Matteo Russo 0002
• David Saulpic
• Chris Schwiegelshohn

TMLR Journal 2025 Journal Article

Node Embeddings via Neighbor Embeddings

• Jan Niklas Böhm
• Marius Keute
• Alica Guzmán
• Sebastian Damrich
• Andrew Draganov
• Dmitry Kobak

Node embeddings are a paradigm in non-parametric graph representation learning, where graph nodes are embedded into a given vector space to enable downstream processing. State-of-the-art node-embedding algorithms, such as DeepWalk and node2vec, are based on random-walk notions of node similarity and on contrastive learning. In this work, we introduce the graph neighbor-embedding (graph NE) framework that directly pulls together embedding vectors of adjacent nodes without relying on any random walks. We show that graph NE strongly outperforms state-of-the-art node-embedding algorithms in terms of local structure preservation. Furthermore, we apply graph NE to the 2D node-embedding problem, obtaining graph t-SNE layouts that also outperform existing graph-layout algorithms.

ICML Conference 2025 Conference Paper

On the Importance of Embedding Norms in Self-Supervised Learning

• Andrew Draganov
• Sharvaree Vadgama
• Sebastian Damrich
• Jan Niklas Böhm
• Lucas Maes
• Dmitry Kobak
• Erik J. Bekkers

Self-supervised learning (SSL) allows training data representations without a supervised signal and has become an important paradigm in machine learning. Most SSL methods employ the cosine similarity between embedding vectors and hence effectively embed data on a hypersphere. While this seemingly implies that embedding norms cannot play any role in SSL, a few recent works have suggested that embedding norms have properties related to network convergence and confidence. In this paper, we resolve this apparent contradiction and systematically establish the embedding norm’s role in SSL training. Using theoretical analysis, simulations, and experiments, we show that embedding norms (i) govern SSL convergence rates and (ii) encode network confidence, with smaller norms corresponding to unexpected samples. Additionally, we show that manipulating embedding norms can have large effects on convergence speed. Our findings demonstrate that SSL embedding norms are integral to understanding and optimizing network behavior.

NeurIPS Conference 2025 Conference Paper

Ultrametric Cluster Hierarchies: I Want ‘em All!

• Andrew Draganov
• Pascal Weber
• Rasmus Jørgensen
• Anna Beer
• Claudia Plant
• Ira Assent

Hierarchical clustering is a powerful tool for exploratory data analysis, organizing data into a tree of clusterings from which a partition can be chosen. This paper generalizes these ideas by proving that, for any reasonable hierarchy, one can optimally solve any center-based clustering objective over it (such as $k$-means). Moreover, these solutions can be found exceedingly quickly and are *themselves* necessarily hierarchical. Thus, given a cluster tree, we show that one can quickly access a plethora of new, equally meaningful hierarchies. Just as in standard hierarchical clustering, one can then choose any desired partition from these new hierarchies. We conclude by verifying the utility of our proposed techniques across datasets, hierarchies, and partitioning schemes.

IJCAI Conference 2023 Conference Paper

ActUp: Analyzing and Consolidating tSNE and UMAP

• Andrew Draganov
• Jakob Jørgensen
• Katrine Scheel
• Davide Mottin
• Ira Assent
• Tyrus Berry
• Cigdem Aslay

TSNE and UMAP are popular dimensionality reduction algorithms due to their speed and interpretable low-dimensional embeddings. Despite their popularity, however, little work has been done to study their full span of differences. We theoretically and experimentally evaluate the space of parameters in the TSNE and UMAP algorithms and observe that a single one -- the normalization -- is responsible for switching between them. This, in turn, implies that a majority of the algorithmic differences can be toggled without affecting the embeddings. We discuss the implications this has on several theoretic claims behind UMAP, as well as how to reconcile them with existing TSNE interpretations. Based on our analysis, we provide a method (GDR) that combines previously incompatible techniques from TSNE and UMAP and can replicate the results of either algorithm. This allows our method to incorporate further improvements, such as an acceleration that obtains either method's outputs faster than UMAP. We release improved versions of TSNE, UMAP, and GDR that are fully plug-and-play with the traditional libraries.