Leiden Clustering

Preface

Many of the clustering methods you may already know work directly on coordinates or on distances between rows of a data matrix. K-means assigns each observation to its nearest centroid. DBSCAN counts how many observations fall inside a fixed radius of each other observation. Spectral clustering builds a similarity graph but then leaves it, building new coordinates from its eigenvectors before clustering those coordinates instead.

Leiden clustering takes a different approach. It builds a graph from the data, connecting each observation to a handful of its nearest neighbours, and then looks for communities: groups of nodes that are more strongly connected to each other than to the rest of the graph. It never leaves the graph to build new coordinates. The partition it returns is a property of the graph itself.

Leiden is one of the most widely used clustering methods in single-cell RNA sequencing analysis, where it groups cells into candidate types or states based on a neighbour graph built from principal component coordinates. It is also used far beyond biology, wherever observations can reasonably be represented as a network.

Start with the visual introduction.