For循环优化以创建邻接矩阵

青葱年少 2年前 pytorch 400

原文标题 ：For loop optimization to create an adjacency matrix

我目前正在处理带有标记边的图。原始邻接矩阵是一个形状为 [n_nodes, n_nodes, n_edges] 的矩阵，如果节点 i 和 j 通过边 k 连接，则每个单元 [i,j,k] 为 1。

我需要创建原始图的反转，其中节点成为边，边成为节点，所以我需要一个形状为 [n_edges, n_edges, n_nodes] 的新矩阵，其中每个单元格 [i,j,k] 如果边为 1 i 和 j 有 k 作为公共顶点。

enter image description here

下面的代码正确地完成了任务，但是使用 5 个嵌套的 for 循环太慢了，处理我必须处理的大量图形似乎需要大约 700 小时。

有没有更好的方法来实现这一点？

n_nodes = extended_adj.shape[0]
n_edges = extended_adj.shape[2]
reversed_graph = torch.zeros(n_edges, n_edges, n_nodes, 1)
for i in range(n_nodes):
    for j in range(n_nodes):
        for k in range(n_edges):
            #If adj_mat[i][j][k] == 1 nodes i and j are connected with edge k
            #For this reason the edge k must be connected via node j to every outcoming edge of j
            if extended_adj[i][j][k] == 1:
                #Given node j, we need to loop through every other possible node (l)
                for l in range(n_nodes):
                    #For every other node, we need to check if they are connected by an edge (m)
                    for m in range(n_edges):
                        if extended_adj[j][l][m] == 1:
                            reversed_graph[k][m][j] = 1

谢谢是提前。

原文链接：https://stackoverflow.com//questions/71569202/for-loop-optimization-to-create-an-adjacency-matrix

我来回复

DerekG 评论
该回答已被采纳！

与上述评论相呼应，这种图形表示几乎可以肯定是繁琐且低效的。但尽管如此，让我们定义一个没有循环的矢量化解决方案，并尽可能使用张量视图，这对于计算更大的图应该是相当有效的。

为了清楚起见，让我们使用[i,j,k]索引G（原始图）和[i',j',k']索引G'（新图）。让我们缩短n_edges到e和n_nodes到n。

考虑二维矩阵slice = torch.max(G,dim = 1)。在该切片的每个坐标[a,b]处，1 表示节点a通过边b连接到其他某个节点（我们不关心哪个节点）。
```
slice = torch.max(G,dim = 1)                                     # dimension [n,e]
```
我们正在寻找解决方案的路上，但我们需要一个表达式来告诉我们a是否连接到边b和另一条边c，对于所有边c。我们可以通过扩展slice、复制和转置来映射所有组合b,c，并寻找两者之间的交集。
```
expanded_dim = [slice.shape[0],slice.shape[1],slice.shape[1]]    # value [n,e,e]

# two copies of slice, expanded on different dimensions
expanded_slice = slice.unsqueeze(1).expand(expanded_dim)         # dimension [n,e,e]
transpose_slice = slice.unsqueeze(2).expand(expanded_dim)        # dimension [n,e,e]

G = torch.bitwise_and(expanded_slice,transpose_slice).int()      # dimension [n,e,e]
```
G[i',j',k']现在等于1当且仅当节点i'通过边j'连接到其他节点，AND节点i'通过边k'连接到其他节点。如果j' = k'，只要该边的端点之一是i'，则值为 1。

最后，我们重新排序尺寸以获得您想要的形式。
```
G = torch.permute(G,(1,2,0))           # dimension [e,e,n]
```
2年前 0条评论
Yves Daoust 评论
1. 通过将边号直接分配给矩阵元素，将初始邻接矩阵从 [Nn, Nn, Ne] 压缩到 [Nn, Nn]。这需要对初始矩阵进行详尽的遍历，取 O(Nn²Ne)。
2. 对于每个节点 n，您知道具有相应边索引的相邻节点列表；因此您生成所有相邻节点对 ni, nj 并将节点索引 n 写入位置 (ei, ej)。这需要 O(Nn²+Ne²) 因为您需要初始化边数组。
3. 在 O(Ne²Nn) 时间内从 [Ne, Ne] 解压缩到 [Ne, Ne, Nn]。
因此，总时间以 O(NnNe(Nn+Ne)) 为界。
2年前 0条评论

For循环优化以创建邻接矩阵

回复

相关问题