NetworkX 的 CuGraph 实现 all_pairs_dijkstras

Question

我正在尝试将我必须的 cpu 绑定算法转换为 GPU 算法，但我在使用 cugraph 时遇到了各种麻烦。其中一部分是我的无知，另一部分只是 cugraph 的初期和不发达，最后一部分是我只是在搞清楚优雅的矢量化方法。

假设我有 m 个数据观察值，其中包含 n 个特征。我通过计算所有观测值的所有观测值的欧几里得距离来创建距离矩阵（注意：这不是我需要帮助的部分，也不是最佳的。只需添加这部分以获得易于理解、可重现的代码）

import numpy as np

def l1_distance(arr):
    return np.linalg.norm(arr, 1)

X = np.random.randint(low=0, high=255, size=(700,4096))

W = np.empty((700,700))

for i in range(700):
    for j in range(700):
        W[i,j] = l1_distance(X[i,:] - X[j,:])

第一次挑战

import networkx as nx

def build_weighted_graph(W):
    n = W.shape[0]
    Graph = nx.DiGraph()
        for i in range(n):
            for j in range(n):
                Graph.add_weighted_edges_from([(i,j,min(W[i,j], W[j,i]))])
    return Graph

其中输入 W 矩阵是欧几里德 space 中的方形距离矩阵（节点最初由 x 特征组成）。例如。第 1 行第 9 行是节点 1 和节点 9 之间的距离，第 20 行第 30 行是节点 20 和节点 30 之间的距离，依此类推。图形现在在连接的节点之间绘制边，边的权重是欧氏距离测量.

我花了大约 8 个小时试图弄清楚如何将其移动到 GPU，但即使在 NVIDIA 自己的文档中，他们也声称

The code block is perfectly fine for NetworkX. However, the process of iterating over the dataframe and adding one node at a time is problematic for GPUs and something that we try and avoid. cuGraph stores data in columns (i.e. arrays). Resizing an array requires allocating a new array one element larger, copying the data, and adding the new value. That is not very efficient.

If your code follows the above model of inserting one element at a time, the we suggest either rewriting that code or using it as is within NetworkX and just accelerating the algorithms with cuGraph.

所以我放弃了，让那部分保持原样。算法的下一部分使用dijkstra算法并计算所有节点到所有其他节点的最短路径

res = dict(nx.all_pairs_dijkstra_path_length(Graph))

在 cugraphs 实现中，它们只有单一源 dijkstra，它将图形和源节点作为参数。这与 networkx 的库形成对比，networkx 的库随附上述方法并在所有节点上无处不在地应用 dijkstra。这意味着我将不得不为每个节点（更多 for 循环）迭代调用 SSSP（cugraph 的 dijkstra 实现）。

在我通过连接节点获得距离后，我创建了另一个方距离矩阵，它现在基于通过连接节点的距离而不是最初采用欧氏距离。

D = np.zeros([n,n])
    for i in range(n):
        for j in range(n):
            D[i,j] = res[i][j]

我这辈子都想不出如何为 GPU 向量化其中的任何一个。在正确方向上的任何帮助将不胜感激。目前对于我的算法运行s 上的数据集，CPU 绑定算法需要大约 5 分钟才能达到运行 698 个节点。因此，为什么我要在 GPU 方面加快速度

Answer 1

您的第一个问题——欧几里得距离矩阵的初始化——的答案似乎已在中得到解答，但您当然可以使用 cuDF 优化图的创建和 Dijkstra 矩阵的计算和 cuGraph.

要有效地创建图形，您可以构建一个列出边及其权重的 cuDF 数据框。由于欧几里德距离矩阵的结构，这很简单。 cuGraph 将此数据框作为边列表和 returns 图形。然后您可以遍历节点以计算最短的适用顶点。如果问题规模增加，这可以在以后与 Dask 并行化或分发。

对于这个问题大小，下面的代码比使用 nx.all_pairs_dijkstra_path_length 快大约 40 倍，它还包括初始距离计算。

import cupy as cp
import cudf as cd
import cugraph as cg

def build_weighted_graph_gpu(X, n):
    X_d = cp.array(X)
    G_d = cp.zeros([n, n])
    for i in range(n):
        G_d[i,:] = cp.abs(cp.broadcast_to(X_d[i,:], X_d.shape) - X_d).sum(axis=1)
    return G_d

def dijkstras_matrix_gpu(W_d):
    n = np.shape(W_d)[0]
    
    # Create a columnar dataframe describing edges
    df_g = cd.DataFrame({
        'source':      cp.array([x // n for x in range(n*n)]),
        'destination': cp.array([x % n for x in range(n*n)]),
        'weight':      cp.minimum(W_d, cp.transpose(W_d)).ravel()})
    
    graph_d = cg.Graph()
    
    graph_d.from_cudf_edgelist(df_g, source='source', destination='destination', edge_attr='weight', renumber=False)
    
    dist_d = cp.empty_like(W_d)

    for i in range(n):
        dist_d[i,:] = cp.asarray(cg.traversal.shortest_path(graph_d, i)['distance'])
    
    return dist_d

distance_matrix = dijkstras_matrix_gpu(build_weighted_graph_gpu(X))

NetworkX 的 CuGraph 实现 all_pairs_dijkstras

CuGraph implementation of NetworkX all_pairs_dijkstras

gpu

networkx

dijkstra

cupy

rapids