Understanding the Leiden Algorithm

A Hands-On Appendix to GraphRAG’s Community Detection Method

5 min readMay 3, 2025

This post serves as an appendix to my “Understanding GraphRAG” article. If you haven’t already, I recommend reading that post to see how the Leiden algorithm is used within the GraphRAG framework. The content and code in this post were developed with help from ChatGPT. You can access my code here.

Get Pelin Balci’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

The Leiden algorithm is a community detection algorithm developed by Traag et al [1] at Leiden University. It was developed as a modification of the Louvain method. [1]

It improves upon the well-known Louvain algorithm by addressing some of its limitations, such as:

producing disconnected communities,
getting stuck in local optima,
and failing to refine communities after initial merging.

Purpose

It identifies groups of nodes (communities) in a graph that are more densely connected internally than with the rest of the graph. This is especially useful in social networks, biological networks, or document graphs — like in GraphRAG, where communities might represent clusters of semantically similar documents.

How It Works (Conceptual Steps)

Local Moving of Nodes:

Like Louvain, it moves nodes between communities to improve modularity or another objective function (e.g., Constant Potts Model).
But Leiden does so more carefully, ensuring well-connected communities.

Refinement Phase:

Unlike Louvain, Leiden includes an extra refinement step to split disconnected or weakly connected communities before aggregation.
This guarantees each community is internally connected.

Aggregation:

Communities are grouped into super-nodes, and the process is repeated recursively on the aggregated graph until convergence.

Example Usage (Numbers)

It is always easier to understand in numbers. Let’s create a simple undirected graph:

import igraph as ig
import leidenalg

# 1. Create a graph
# Let's build a simple undirected graph
edges = [(0, 1), (1, 2), (2, 3), (0, 3),  # Cluster 1
         (4, 5), (5, 6), (6, 7), (4, 7),  # Cluster 2
         (0, 4)]  # A weak connection between the clusters

g = ig.Graph(edges=edges, directed=False)

Find the communities:

import igraph as ig
import leidenalg

# 1. Create a graph
# Let's build a simple undirected graph
edges = [(0, 1), (1, 2), (2, 3), (0, 3),  # Cluster 1
         (4, 5), (5, 6), (6, 7), (4, 7),  # Cluster 2
         (0, 4)]  # A weak connection between the clusters

g = ig.Graph(edges=edges, directed=False)

# 2. Run the Leiden algorithm
partition = leidenalg.find_partition(g, leidenalg.ModularityVertexPartition)

# 3. Print communities
for i, community in enumerate(partition):
    print(f"\nCommunity {i + 1}:")
    for node_id in community:
        print(f" - Node {node_id}: {edges[node_id]}")

# Output 
Community 1:
 - Node 0: (0, 1)
 - Node 1: (1, 2)
 - Node 2: (2, 3)
 - Node 3: (0, 3)

Community 2:
 - Node 4: (4, 5)
 - Node 5: (5, 6)
 - Node 6: (6, 7)
 - Node 7: (4, 7)

As you see, the weak connection (0,4) is not shown in the communities. The Leiden algorithm is built to optimize modularity (or other quality functions like CPM), which prefers communities that:

Are densely connected internally
Have sparse connections to other communities

Adding 0 and 4 to the same community would decrease the modularity score. It would introduce a lot of weak intra-community edges. It breaks the tight internal structure of each cluster.

Example Usage (Text)

Our goal is to cluster semantically similar documents using:

Sentence embeddings (via sentence-transformers)
Cosine similarity to build a graph
Leiden algorithm to find communities

We will use SentenceTransformer(‘all-MiniLM-L6-v2’) model to find the embeddings of the documents. Let’s find the embeddings and cosine similarity.

from sentence_transformers import SentenceTransformer
from sklearn.metrics.pairwise import cosine_similarity
import numpy as np
import igraph as ig
import leidenalg

# Step 1: Sample documents
documents = [
    "How to train a neural network.",
    "Deep learning and AI applications.",
    "Graph theory and community detection.",
    "Shortest path algorithms in graphs.",
    "Transformers in NLP.",
    "Self-attention in transformers.",
    "Breadth-first search and DFS."
]

# Step 2: Embed documents
model = SentenceTransformer('all-MiniLM-L6-v2')
embeddings = model.encode(documents)

# Step 3: Build similarity graph
cos_sim = cosine_similarity(embeddings)

This is the heatmap of cosine similarity:

Then, we will create the graph using this cos_sim matrix:

threshold = 0.3  # Only connect nodes with similarity > 0.5

edges = []
weights = []

for i in range(len(cos_sim)):
    for j in range(i + 1, len(cos_sim)):
        if cos_sim[i][j] > threshold:
            edges.append((i, j))
            weights.append(cos_sim[i][j])

# Step 4: Create igraph graph
g2 = ig.Graph(edges=edges, directed=False)
g2.es['weight'] = weights

Now it is time for Leiden:

# Step 5: Run Leiden algorithm
partition2 = leidenalg.find_partition(g2, leidenalg.RBConfigurationVertexPartition, weights='weight')

# Step 6: Show results
for i, community in enumerate(partition2):
    print(f"\nCommunity {i + 1}:")
    for doc_id in community:
        print(f" - D{doc_id}: {documents[doc_id]}")


# Output
Community 1:
 - D0: How to train a neural network.
 - D1: Deep learning and AI applications.
 - D4: Transformers in NLP.
 - D5: Self-attention in transformers.

Community 2:
 - D2: Graph theory and community detection.
 - D3: Shortest path algorithms in graphs.
 - D6: Breadth-first search and DFS.

This is the visualization of the documents:

Questions

So it looks like clustering, right? Let’s define the differences between k-means clustering and the Leiden algorithm. (Thanks to ChatGPT.)

If you have:

1000 document embeddings → K-means can cluster them into K=10 groups.
A cosine similarity graph of those documents → Leiden can detect naturally occurring communities without specifying K.