图分析基准测试的更多冒险
让我们来看看 Louvain 算法的基准测试。
如果您阅读了我之前的两篇博客，《图分析性能测量》和《图分析基准测试的冒险》，您就会知道我最近一直在强调图分析基准测试。您也知道我使用了来自加州大学伯克利分校的 GAP Benchmark Suite，因为它易于运行，测试了多种图算法和拓扑，很好地覆盖了图分析的各个方面——最重要的是——它能提供全面、客观且可复现的结果。然而，GAP 并没有涵盖社交网络中的社区检测。
Louvain 算法[1] 用于在大规模网络中寻找社区，是填补这一空白（双关语）的一个潜在选择。首先，这是一个经过充分研究的方法。根据 Google Scholar* 的数据，描述该算法的文章截至 2019 年 11 月已获得超过 10,000 次引用。其次，它专为大规模图设计。最初的文章分析了一个拥有 1.18 亿个顶点和超过 10 亿条边的 Web 图。因此，让我们来看看 Louvain 算法的基准测试。
我最近偶然发现了一个关于 RAPIDS cuGraph* 和 NetworkX* 的 Louvain 性能比较（**图 1**）。NetworkX 是一个全面的网络分析库。它涵盖了网络研究中最晦涩的领域。需要三元组统计？NetworkX 可以满足您。如果您处理的是非常小的图，它是一个不错的库。NetworkX 是一个纯 Python* 库，因此其性能并不出色。为什么要将像 cuGraph 这样的优化库与未经优化的库进行比较，除非目标是报告夸大的加速比？但还有一个更大的缺陷：**图 1** 的源文章没有说明 cuGraph 和 NetworkX 是否给出了相同的输出。所以，我决定自己做比较。
我使用了 Louvain 算法的参考实现（2019 年 11 月下载）[2]，因为它用 C++ 编写，性能应该优于 Python。我按照如下方式编译了这个包：
这会创建我需要的三个可执行文件：convert（将原始边列表转换为更高效的二进制格式）、louvain（通过模块度优化对图进行社区划分[3]）和 hierarchy（显示社区结构）。我使用了标准的 GNU C++ 编译器构建，正如我在之前的 GAP 实验中所做的那样。源代码没有修改，并且我没有更改原始 Makefile 中的编译器选项。
我遵循了 README.txt 文件（包含在 louvain-generic.tar.gz 中）中的说明，以准备输入数据并运行 Louvain 参考实现。
**图 1** 中列出的图是从 SuiteSparse Matrix Collection 下载并转换为边列表的。值得重申的是，这些是小型图（**表 1**）。最大的图只有 170 万个顶点。
相比之下，GAP Benchmark Suite 中最小和最大的图分别有 2390 万和 1.342 亿个顶点，而 Louvain 算法最初是在一个 1.18 亿顶点的图上测试的。**图 1** 中的图很可能出于两个原因被选中。首先，它们必须足够小，能够容纳在单个 NVIDIA Tesla V100 的内存中，因为 cuGraph 中的 Louvain 实现无法使用多个 GPU 的聚合内存。其次，它是在与 NetworkX 进行比较，因此对于纯 Python 库来说，大型图的计算时间将是极其昂贵的。
在考虑相对性能之前，我们先来谈谈正确性。仅显示了**图 1** 中的性能数据，但没有考虑 NetworkX 和 cuGraph 是否给出了相同的输出。每个 Louvain 实现是否检测到了相同的社区？简单计算每个 Louvain 实现检测到的社区数量，会发现显著的差异（**表 2**）。社区数量的微小差异是可以预期的，因为每个实现中的内部启发式方法可能不同。然而，一些差异非常大，以至于性能比较变得可疑。例如，一个实现是否过早地收敛到了一组社区？对于这些图上的 Louvain 计算，什么才构成正确输出？GAP 或任何标准基准测试的主要优点之一是它们为给定的测试定义了正确的输出。没有这些定义，进行“苹果对苹果”式的性能比较就变得困难或不可能。
将 cuGraph 与 Louvain 算法的顺序 C++ 参考实现进行比较，显著缩小了性能差距（**图 2**）。我可能只需做一些简单的更改就能进一步缩小差距。例如，我可以切换到 Intel 编译器以启用积极的优化和向量化，或者尝试使用 OpenMP 并行化参考实现，但我直到能够确定基准之前都不愿这样做。目前，我满意地认为 cuGraph 的 1.4 倍到 10 倍的加速比与**图 1** 中报告的 200 倍到 2100 倍的加速比相去甚远。然而，我之所以满意，是因为我知道这些性能比较存在问题。与大多数**临时**的、未定义的基准测试一样，结果必须谨慎对待。
建立基准
为了尝试建立基准，我在著名的 Zachary[8]空手道俱乐部社交网络上运行了每个 Louvain 实现。这个图足够小（只有 34 个顶点和 78 条边），可以手动检查所有实现是否产生相同的社区。NetworkX、cuGraph 和 Louvain 参考实现都产生了略有不同的结果（差异已高亮显示）。
NetworkX
Louvain 参考实现
cuGraph
考虑到表 2 中的差异，每个软件包产生不同的社区并不奇怪。它们找到的社区在**主观上**是合理的，尽管与 Girvan 和 Newman (2002，见图 4b) 报告的不完全相同。
结论
我最初进行这些实验的目标是证明将 cuGraph 这样的优化库与 NetworkX 这样的纯 Python 库进行比较的愚蠢之处。C++ Louvain 参考实现显著缩小了性能差距，但社区数量的巨大差异意味着故事不仅仅是性能。每个输入图的正确社区是什么？是某个 Louvain 实现是正确的，而其他是错误的吗？
即使是对于广为人知的 Zachary 社交网络，建立基准的困难也凸显了**客观**、清晰定义的图分析基准的重要性。Louvain 算法可能会成为 GAP Benchmark Suite 的一个有益补充，因为它将把覆盖范围扩展到社区检测领域，而 GAP 目前缺乏这一功能，但**临时**的性能测量是不够的。一个合理且可复现的测试必须由图分析社区来定义。在此之前，如果社区检测性能对于决策很重要，我推荐 LDBC Graphalytics 基准测试。
[1] Blondel 等人 (2008)。“大规模网络中社区的快速展开，”J Stat Mech, P10008。
[2] 有关此软件包的更多信息，请参阅“Louvain 方法：在大规模网络中寻找社区”。值得注意的是，参考实现尚未并行化。
[3] Girvan 和 Newman (2002)。“社交和生物网络中的社区结构，”Proc Natl Acad Sci, 99(12), 7821-7826。
[4] cuGraph 代码改编自 https://github.com/rapidsai/notebooks/blob/branch-0.11/cugraph/community/Louvain.ipynb。
[5] GPU：NVIDIA Tesla V100，16 GB HBM；系统内存：480 GB；操作系统：Ubuntu Linux release 4.15.0-1054-aws，kernel 56.x86_64；软件：RAPIDS v0.1.0（2019 年 11 月下载并运行）。
[6] CPU：Intel® Xeon® Gold 6252（2.1 GHz，24 核），超线程已启用（每个插槽 48 个虚拟核心）；内存：384 GB Micron DDR4-2666；操作系统：Ubuntu Linux release 4.15.0-29，kernel 31.x86_64；软件：GNU g++ v7.4.0，NetworkX v2.3，community API v0.13，Louvain 参考实现（2019 年 11 月下载并运行）。
[7] 有关性能和基准测试结果的更完整信息，请访问 www.intel.com/benchmarks。
[8] Zachary (1977)。“小型群组冲突和分裂的信息流模型，”J Anthropol Res, 33(4), 452-473。