与k-hop邻居动态计算`edge_index`

Question

鉴于我有一个具有给定连接性的

torch_geometric

图，例如

edge_index = torch.tensor([[0, 1, 2, 3, 2, 0],
                           [1, 0, 3, 2, 0, 2]], dtype=torch.long)

我想实现一个函数，根据给定的图计算 K 阶邻居，并返回一个具有更新连接性的 new 图。例如，在这种情况下，考虑 2 跳邻居，我最终会得到一个新图，其连接如下所示：

edge_index = torch.tensor([[0, 3, 1, 2, 1, 3],
                           [3, 0, 2, 1, 3, 1]], dtype=torch.long)

我想知道这个功能如何实现。

Answer 1

假设：您想要创建一个新图，其中两个顶点具有链接，当且仅当这两个顶点在旧图中被一条恰好有两跳的最短路径分开时

那么算法就是：

• 在 G1 中的顶点上循环 V
  • 使用深度优先搜索（DFS）算法计算从 V 到每个其他顶点的最短路径。每当 DFS 远离 V 时，您可以通过中止 DFS 来节省时间
  • 循环 DFS 的输出，并向 G2 添加 V 和每个跳出的顶点 K 之间的链接

我对 pytorch 一无所知，但任何像样的图论库（例如 networkx ）都可以轻松实现这一点，尽管为了获得最大效率，您可能需要重新编码 DFS。