Community detection algorithms play a crucial role in understanding data by identifying hidden groups of related entities in networks. Social network evaluation, suggestion systems, GraphRAG, genomics, and more rely on community detection. But for data scientists working in Python, the power to efficiently analyze graph data because it grows in size and complexity can pose an issue when constructing responsive, scalable community detection systems.
While there are several community detection algorithms in use today, the Leiden algorithm has turn out to be a number one solution for data scientists. And for large-scale graphs in Python, this once-expensive task is now dramatically faster because of cuGraph and its GPU-accelerated Leiden implementation. Leiden from cuGraph delivers results as much as 47x faster than comparable CPU alternatives. This performance is well accessible in your Python workflows through the cuGraph Python library or the favored NetworkX library through the nx-cugraph backend.
This post demonstrates where the Leiden algorithm will be used and the best way to speed up it for real-world data sizes using cuGraph. Read on for a transient overview of Leiden and its many applications, benchmarks of cuGraph Leiden performance against others available in Python, and an example of GPU-accelerated Leiden on larger-scale genomics data.
What’s Leiden?
Leiden was developed as a modification to the favored Louvain algorithm, and like Louvain, it goals to partition a network into communities by optimizing a high quality function called modularity. Nonetheless, Leiden also addresses a major drawback of Louvain: the resulting communities returned by Louvain will be poorly connected, sometimes even disconnected. By adding an intermediate refinement phase, Leiden guarantees all resulting communities are well-connected, making it a preferred selection for a broad choice of applications. Leiden is quickly becoming the usual alternative to Louvain.
Where is Leiden used?
The next is only a sample of the fields that use community detection techniques resembling Leiden, all of that are subject to the impact of consistently growing real-world data sizes:
- Social network evaluation: Identifying communities can reveal groups of users with shared interests, facilitating targeted promoting, recommendations, and the study of knowledge diffusion.
- Advice systems: Clustering users or items into communities based on their interactions allows for suggestion systems to offer more accurate and personalized suggestions.
- Fraud detection: By identifying communities of fraudulent accounts or suspicious transactions in financial networks, institutions can quickly flag and investigate fraudulent activity.
- Graph-based retrieval-augmented generation (GraphRAG): GraphRAG retrieves relevant information from a knowledge graph—an online of interconnected facts—to offer an LLM higher context. Leiden is commonly used to create categories of data to help in matching probably the most applicable nodes within the knowledge graph to the user’s prompt.
- Genomics: Leiden is used when analyzing single-cell genomics data for identifying groups of cells with similar gene expression profiles.
How does GPU-powered Leiden from cuGraph compare?
Several Leiden implementations available to Python developers were benchmarked using a patent citation graph consisting of three.8 million nodes and 16.5 million edges, where the communities identified by Leiden represent related technologies. Figure 1 shows the runtime in seconds, together with the variety of unique communities identified.
Software: NetworkX 3.5, cugraph/nx-cugraph 25.10; CPU: Intel Xeon Platinum 8480CL 2TB RAM; GPU: NVIDIA H100 80GB RAM
Note that because Leiden implementations use a random number generator, the communities returned are non-deterministic and vary barely between runs. The variety of communities is shown to point that each one results are roughly equal. Most implementations, including cuGraph’s, provide parameters to tune for larger or smaller community sizes, amongst others. Each implementation was called with the default parameter values when possible. The source code for these benchmarks will be present in the rapidsai/cugraph GitHub repo.
As shown in Figure 1, the cuGraph GPU-accelerated Leiden implementation runs 8.8x faster than igraph’s and 47.5x faster than graspologic’s on the identical citation graph. Along with high performance, cuGraph also delivers ease of use, flexibility, and compatibility with existing Python data science workflows through multiple Python interfaces. To show you how to select the precise one on your project, Table 1 lists key features of every library. Leiden and plenty of other graph algorithms can be found in each.
| Speed | Ease-of-use | Dependencies | NetworkX advantages: CPU fallback, flexible graph object, popular API, a whole bunch of algos, graph visualization, more | Multi-GPU support | cuDF and Dask support | |
| NetworkX plus nx-cugraph | Fast | Easiest | Few | ✔ | ||
| cuGraph | Faster | Easy | More, including cuDF and Dask | ✔ | ✔ |
For detailed installation instructions, see the RAPIDS Installation guide. To start straight away with either pip or Conda, use the RAPIDS release selector.
The best way to use NetworkX and nx-cugraph with genomics data
Genomics datasets are massive, and growing at an explosive pace, largely because of the recent and dramatic drop in the associated fee of DNA sequencing. While NetworkX has an unlimited following amongst data scientists of all fields, its pure-Python implementation means that almost all genomic datasets are just too large for it, forcing scientists to learn and integrate a separate library for analytics. Fortunately, NetworkX will be GPU accelerated by enabling the nx-cugraph backend to enable data scientists to proceed using NetworkX even with large data.
To show the good thing about GPU accelerated NetworkX on larger-scale genomics data, a straightforward example was created that reads gene expression data, builds a graph of genes with edges connecting genes based on expression correlation values, runs Leiden to discover groups of functionally related genes, and plots the communities for visual inspection. The complete source code is obtainable within the rapidsai/nx-cugraph GitHub repo. Note that the instance represents a standard operation in genomics—community detection using Leiden or Louvain—on actual genomics data, but will not be intended to be representative of a typical genomics workflow.
The gene expression evaluation data used ends in a graph of 14.7K nodes and 83.8 million edges. The next code will run Leiden using nx-cugraph but will fall back to the NetworkX implementation of Louvain when nx-cugraph will not be available.
Leiden is currently the one algorithm provided by nx-cugraph that doesn’t have another implementation available through NetworkX. Because of this Leiden is obtainable to NetworkX users only through nx-cugraph. Because of this, this workflow uses Louvain from NetworkX on CPU, because it provides an affordable comparison for a user wishing to proceed using NetworkX when a GPU will not be present.
With nx-cugraph enabled, NetworkX identified 4 communities in lower than 4 seconds. Nonetheless, falling back to the NetworkX implementation of Louvain shows that the outcomes are nearly an identical (inside tolerance of the non-determinism of each Leiden and Louvain), but performance is dramatically slower, taking nearly 21 minutes. Moreover, since Louvain was used, the resulting communities will not be guaranteed to be well-connected.
This makes NetworkX with nx-cugraph 315x faster at delivering higher quality results than NetworkX Louvain on CPU.
To run Leiden or Louvain based on the presence of the Leiden implementation (currently available only through nx-cugraph) use the next code:
%%time
try:
communities = nx.community.leiden_communities(G)
except NotImplementedError:
print("leiden not available (is the cugraph backend enabled?), using louvain.")
communities = nx.community.louvain_communities(G)
num_communities = len(communities)
print(f"Variety of communities: {num_communities}")
Software: NetworkX 3.5, cugraph/nx-cugraph 25.10; CPU: Intel Xeon Gold 6128 CPU @ 3.40 GHz 48 GB RAM; GPU: NVIDIA Quadro RTX 8000 48 GB RAM
Coloring graph nodes by community and plotting is trivial in NetworkX (Figure 3).
When NetworkX does add CPU support for Leiden, either as a native Python implementation or as a separate CPU backend, users can make the most of zero-code-change functionality by having a single “portable” function call that works, albeit possibly slower, on platforms with out a GPU.
The previous example is meant to easily show how nx-cugraph can GPU speed up NetworkX algorithms commonly utilized in genomics on real-world genomics data. To explore more realistic, purpose-built examples, try the RAPIDS-singlecell project, which offers a library designed specifically for genomics problems.
RAPIDS-singlecell is an scverse core package based on the favored Scanpy library, supports an AnnData-compatible API, and is optimized for single-cell evaluation on large datasets. The impressive speed of RAPIDS-singlecell at scale comes from cuGraph and other CUDA-X DS libraries that provide GPU acceleration for its calls to Leiden and plenty of other algorithms. To learn more, see Driving Toward Billion-Cell Evaluation and Biological Breakthroughs with RAPIDS-singlecell.
Start running GPU-powered Leiden workflows
cuGraph provides best-in-class community detection performance through its GPU accelerated Leiden implementation, available to data scientists in Python from the cuGraph Python library or the favored and versatile NetworkX library through the nx-cugraph backend. Performance as much as 47x faster, possibly more, over comparable CPU implementations mean genomics and plenty of other applications counting on community detection can scale their data and solve larger problems in far less time.
To start, try the RAPIDS Installation guide or visit the rapidsai/cugraph or rapidsai/nx-cugraph GitHub repos to run your GPU-powered Leiden workflows.
