How Community Detection Using the Leiden Algorithm Works in code-review-graph

The code-review-graph library clusters code-knowledge graph nodes into tightly-coupled communities using the Leiden algorithm via igraph, with deterministic seeding, adaptive resolution scaling, and post-processing steps that reassign test nodes and split oversized clusters.

The code-review-graph repository transforms repository analysis into a navigable knowledge graph by grouping related code units into communities. When the optional igraph library is available, the system employs the Leiden algorithm to partition the graph based on dependency patterns, edge weights, and structural cohesion.

Prerequisites and Environment Setup

The detection engine first attempts to import the high-performance igraph library at code_review_graph/communities.py line 33. If unavailable, the system transparently falls back to a pure-Python directory-based detector without requiring code changes.

# From communities.py - the optional import pattern

try:
    import igraph
    HAS_IGRAPH = True
except ImportError:
    HAS_IGRAPH = False

The Leiden Detection Pipeline

The core implementation in code_review_graph/communities.py follows a multi-stage pipeline to convert raw graph data into meaningful code communities.

Node Indexing and Edge Assembly

Before running the algorithm, the system builds translation dictionaries to map between graph objects and integer indices required by igraph. The qn_to_idx dictionary maps qualified node names to integer indices, while idx_to_node provides the reverse lookup (line 68).

The edge construction phase traverses all GraphEdge objects, converting each to (src_idx, tgt_idx) pairs. Undirected edges are deduplicated, and weights are assigned based on edge kind—such as CALLS or IMPORTS_FROM—to reflect different dependency strengths (line 84).

Adaptive Resolution and Deterministic Seeding

To ensure consistent results across runs, the system respects the CRG_LEIDEN_SEED environment variable (defaulting to 42) when initializing igraph’s random number generator (line 110). The resolution parameter scales inversely with the logarithm of the node count (line 100), producing coarser clusters for larger repositories to maintain interpretability.

Algorithm Execution

The actual clustering occurs through a call to g.community_leiden with objective_function="modularity", passing the computed edge weights and resolution. To prevent exponential runtime growth on large codebases, the implementation fixes the iteration count at 2, which the authors determined sufficient for code-dependency graphs (line 116).

Post-Processing and Test Node Handling

After partitioning, the _reassign_test_nodes function (line 61) moves test-only nodes to the community containing the largest number of unique subjects they test. This preserves deterministic results while ensuring tests remain logically grouped with their target code.

Optimization and Refinement Strategies

Beyond basic clustering, the system implements several refinement stages to improve community quality.

Batch Cohesion Calculation

Rather than scanning edges repeatedly for each community, the _compute_cohesion_batch function (line 87) computes cohesion scores—defined as internal edges divided by total edges—in a single O(edges) pass across the entire graph.

Recursive Splitting of Oversized Communities

Communities exceeding 25% of the total node count trigger the _split_oversized mechanism (line 66). This recursively applies the Leiden algorithm to the sub-graph, creating a hierarchy of sub-communities that prevents monolithic clusters in large monorepos.

Community Naming and Deduplication

After detection, communities smaller than min_size are discarded. For each remaining cluster, the algorithm determines the dominant language and generates a readable name. The _dedupe_community_names function (line 332) resolves naming collisions by appending distinctive keywords or numeric suffixes to ensure each community has a unique identifier.

File-Based Fallback Detection

When igraph is unavailable, the _detect_file_based function (line 73) groups nodes by directory depth, then applies the same cohesion calculation and naming logic to provide consistent API behavior across environments.

Practical Usage Example

The public entry point detect_communities(store, min_size=2) orchestrates the entire workflow, automatically selecting the Leiden or file-based path based on library availability.

from code_review_graph.graph import GraphStore
from code_review_graph.communities import detect_communities, get_architecture_overview

# 1️⃣ Load your graph (the store is built elsewhere in the library)

store = GraphStore(path="my_repo_graph.db")

# 2️⃣ Detect communities – Leiden will be used if igraph is installed

communities = detect_communities(store, min_size=5)

for c in communities:
    print(f"Community {c['name']!r}: {c['size']} nodes, cohesion={c['cohesion']}")

# 3️⃣ Get a higher‑level architecture overview (cross‑community coupling warnings)

overview = get_architecture_overview(store)
print("Warnings:")
for w in overview["warnings"]:
    print(" •", w)

Summary

• Optional igraph dependency: The system attempts to import igraph for Leiden algorithm support, falling back to directory-based detection if unavailable.
• Deterministic clustering: The CRG_LEIDEN_SEED environment variable (default 42) ensures reproducible community IDs across runs.
• Adaptive resolution: The resolution parameter scales inversely with the logarithm of node count to handle large repositories.
• Fixed iterations: The Leiden algorithm runs with exactly 2 iterations to balance accuracy and performance.
• Test-aware post-processing: The _reassign_test_nodes function moves test files to communities containing the code they test.
• Oversized handling: Communities exceeding 25% of total nodes are recursively split using _split_oversized.
• Efficient cohesion: Batch computation calculates all community cohesion scores in a single O(edges) pass.

Frequently Asked Questions

What happens if igraph is not installed?

If the igraph library is unavailable, the detect_communities function automatically delegates to _detect_file_based (line 73), which groups nodes by directory depth while preserving the same cohesion calculation and naming logic. No code changes are required to handle the fallback.

How does the system handle test files during community detection?

After the initial Leiden partition, the _reassign_test_nodes function (line 61) identifies test-only nodes and moves them to the community containing the largest number of unique subjects they test. This ensures tests remain grouped with their corresponding implementation code while maintaining deterministic results.

Why is the Leiden iteration count fixed at 2?

The implementation calls g.community_leiden with a fixed iteration count of 2 (line 116) because this provides sufficient convergence for code-dependency graphs while avoiding exponential runtime blow-up on large repositories. This trade-off prioritizes practical analysis speed over marginal modularity gains.

How does code-review-graph prevent a single community from becoming too large?

The system monitors community sizes during post-processing. Any community exceeding 25% of the total node count triggers the _split_oversized function (line 66), which recursively applies the Leiden algorithm to that sub-graph. This hierarchical splitting prevents monolithic clusters in large monorepos while preserving the modular structure of the codebase.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}