如何使用 GPU 驱动的 Leiden 在 Python 中加速社区检测

社区检测算法通过识别网络中隐藏的关联实体组，在理解数据方面发挥着重要作用。社交网络分析、推荐系统、GraphRAG、基因组学等领域均依赖于社区检测。然而，对于使用 Python 的数据科学家而言，随着图数据规模和复杂性的增加，在构建响应迅速、可扩展的社区检测系统时，高效分析图数据的能力可能面临挑战。

尽管目前有多种社区检测算法在使用，Leiden 算法已成为数据科学家广泛采用的领先方案。对于 Python 中的大规模图数据，得益于 cuGraph 及其基于 GPU 加速的 Leiden 算法实现，这项过去计算成本高昂的任务如今得以显著加速。cuGraph 的 Leiden 实现性能比同类 CPU 方案快 47 倍。您可以通过 cuGraph Python 库，或借助支持 nx-cugraph 后端的流行 NetworkX 库，轻松在 Python 工作流中访问这一高性能能力。

本文将介绍 Leiden 算法的适用场景，以及如何利用 cuGraph 加速该算法以应对真实规模的数据。继续阅读，了解 Leiden 算法及其广泛应用的简要概述、cuGraph Leiden 与其他 Python 实现的性能基准对比，以及 GPU 加速的 Leiden 算法在大规模基因组学数据中的应用示例。

什么是 Leiden？

Leiden 是对流行的 Louvain 算法的一种改进。与 Louvain 算法类似，它旨在通过优化名为模块化的质量函数，将网络划分为多个社区。然而，Louvain 算法存在一个显著缺陷：其划分出的社区可能连接不紧密，甚至出现断开的情况。Leiden 算法通过引入一个中间优化阶段，确保所有生成的社区都具有良好的连通性，从而解决了这一问题。正因如此，Leiden 在各类应用中广受欢迎，并正迅速成为 Louvain 算法的主流替代方案。

Leiden 在何处使用？

以下仅为应用 Leiden 等社区检测技术的领域示例，所有这些技术均会受到现实世界数据规模持续增长的影响：

• 社交网络分析： 识别社区可以揭示具有共同兴趣的用户组，促进定向广告、推荐和信息传播研究。
• 推荐系统： 根据用户或物品的交互将其聚类到社区，从而使推荐系统能够提供更准确、更个性化的建议。
• 欺诈检测： 通过识别金融网络中的欺诈账户或可疑交易群体，机构可以快速标记和调查欺诈活动。
• 基于图形的检索增强生成 (GraphRAG)： GraphRAG 从知识图形 (一个由相互关联的事实组成的网络) 中检索相关信息，为 LLM 提供更好的环境。Leiden 通常用于创建知识类别，以帮助将知识图形中最适用的节点与用户提示进行匹配。
• 基因组学： Leiden 用于分析单细胞基因组学数据，以识别具有相似基因表达谱的细胞组。

如何比较 cuGraph 中搭载 GPU 的 Leiden？

对由 380 万个节点和 1650 万个边构成的专利引用图进行了基准测试，评估了 Python 开发者可用的几种 Leiden 算法实现，其中 Leiden 识别出的社区代表了相关技术领域。图 1 展示了各实现的运行时间（以秒为单位）以及所识别出的唯一社区数量。

软件：NetworkX 3.5，cugraph/nx-cugraph 25.10；CPU：英特尔至强 Platinum 8480CL 2TB RAM；GPU：NVIDIA H100 80GB RAM

请注意，由于 Leiden 算法采用随机数生成器，因此返回的社区划分具有非确定性，不同运行之间会略有差异。社区数量在所有结果中大致相等。包括 cuGraph 在内的大多数实现均提供参数，可用于调整以获得更大或更小的社区规模。应尽可能使用默认参数值调用各实现。这些基准测试的源代码可在 rapidsai/cugraph GitHub 仓库中找到。

如图1所示，在同一引文图中，cuGraph 基于 GPU 加速的 Leiden 算法实现比 graph 快 88 倍，比graphologic 快 47.5倍。除了高性能之外，cuGraph 还通过多个Python接口提供了良好的易用性、灵活性，以及与现有 Python 数据科学工作流程的兼容性。为帮助您选择适合项目的库，表1列出了各库的关键特性。Leiden 算法以及许多其他图算法均可在 cuGraph 中使用。

有关详细安装说明，请参阅 RAPIDS 安装指南。如需立即通过 pip 或 Conda 开始使用，请使用 RAPIDS 版本选择器。

如何将 NetworkX 和 nx-cugraph 与基因组学数据结合使用

基因组学数据集规模庞大，且正以爆炸性的速度增长，这在很大程度上得益于近年来 DNA 测序成本的显著下降。尽管 NetworkX 在各个领域的数据科学家中拥有众多用户，但其纯 Python 实现使得大多数基因组数据集的处理变得过于低效，迫使研究人员不得不学习并集成其他专用分析库。幸运的是，NetworkX 可通过启用 Nx-Graph GPU 后端实现加速，使数据科学家能够在处理大规模数据时依然沿用熟悉的 NetworkX 接口。

为了展示 GPU 加速的 NetworkX 在更大规模基因组学数据上的优势，我们创建了一个简单示例，用于读取基因表达数据，基于基因表达的相关性构建包含基因间连接边的基因网络图，运行 Leiden 算法以识别功能相关的基因模块，并对检测到的社区结构进行可视化绘制以便直观评估。完整的源代码可在 rapidsai/nx-cugraph GitHub 仓库中获取。需要注意的是，该示例展示了基因组学中常见的操作（如使用 Leiden 或 Louvain 算法进行社区检测），并采用了真实基因组学数据，但并不代表典型的基因组学完整工作流程。

生成的基因表达分析数据构建了一个包含 14.7 K 个节点和 8380 万个边的图。以下代码将使用 nx-cugraph 运行 Leiden 算法；当 nx-cugraph 不可用时，将回退至 NetworkX 中的 Louvain 实现。

目前，Leiden 是 nx-cugraph 提供的唯一一种未通过 NetworkX 提供替代实现的算法。这意味着 NetworkX 用户只能借助 nx-cugraph 来使用 Leiden。因此，该工作流在 CPU 上采用了 NetworkX 中的 Louvain 算法，以便为那些在缺乏 GPU 时仍希望继续使用 NetworkX 的用户提供一个合理的对比方案。

启用 nx-cuGraph 后，NetworkX 在不到 4 秒的时间内识别出四个社区。然而，使用 NetworkX 自带的 Louvain 算法实现时，尽管结果几乎相同（在 Leiden 和 Louvain 算法固有的非确定性允许范围内），性能却明显更慢，耗时接近 21 分钟。此外，由于采用的是 Louvain 算法，生成的社区无法保证具有良好的连通性。

这使得使用 nx-cugraph 的 NetworkX 比在 CPU 上运行的 NetworkX Louvain 速度快 315 倍，并能提供更高质量的结果。

要基于 Leiden 实现（目前只能通过 nx-cugraph 获取）运行 Leiden 或 Louvain，请使用以下代码：

软件：NetworkX 3.5，cugraph/nx-cugraph 25.10；CPU：英特尔至强金牌 6128 CPU@ 3.40 GHz 48 GB RAM；GPU：NVIDIA Quadro RTX 8000 48 GB RAM

在 NetworkX 中，根据社区对图的节点进行着色并绘图非常简单（图 3）。

当 NetworkX 为 Leiden 算法添加 CPU 支持（无论是作为原生 Python 实现，还是作为独立的 CPU 后端）时，用户便可以通过单个“可移植”函数调用来实现零代码更改的跨平台使用，该调用在无 GPU 的平台上依然有效（尽管速度可能较慢）。

使用 GPU 加速的 Leiden 基因组学专用工具

上一个示例旨在简要展示 nx-cugraph 如何利用 GPU 加速基因组学中常用的 NetworkX 算法，以处理真实的基因组学数据。如需探索更具实际应用价值的专用示例，可参考 RAPIDS 单细胞 项目，该项目提供了一个专为基因组学问题设计的库。

RAPIDS-singlecell 是基于广受欢迎的 Scanpy 库的 Scverse Core 软件包，支持与 AnnData 兼容的 API，并针对大型数据集的单细胞分析进行了优化。cuGraph 及其他 CUDA-X DS 库 可为其调用 Leiden 和多种算法提供 GPU 加速，从而在大规模分析中实现 RAPIDS 单细胞的卓越性能。如需了解更多信息，请参阅 借助 RAPIDS 单细胞推动十亿细胞分析和生物学突破。

开始运行 GPU 驱动的 Leiden 工作流程

cuGraph 通过其 GPU 加速的 Leiden 算法实现，提供了卓越的社区检测性能。Python 数据科学家可通过 cuGraph Python 库，或通过 nx-cugraph 后端调用广受欢迎且灵活的 NetworkX 库来使用该功能。相较于同类 CPU 实现，性能提升可达 47 倍甚至更高，这意味着基因组学及众多依赖社区检测的应用能够在更短时间内处理更大规模的数据，解决更复杂的问题。

要开始使用，请查看 RAPIDS 安装指南 或访问 rapidsai/cugraph 或 rapidsai/nx-cugraph GitHub 仓库，以运行 GPU 加速的 Leiden 工作流程。