Dynamically computing `edge_index` with k-hop neighbours

Question

Given that I have a torch_geometric graph with a given connectivity, e.g.

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

I would like to implement a function that computes K-th order neighbors from the given graph and returns a new graph with an updated connectivity. In this case for example, considering 2-hop neighbors I would end up with a new graph whose connectivity looks like this:

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

I'm wondering how this function could be implemented.

Answer 1

To create a new graph where two vertices have a link if and only if those two vertices are separated in the old graph by a shortest path that has exactly two hops, the algorithm is:

• LOOP V over vertices in G1
  • Use the Depth First Search ( DFS ) algorithm to calculate the shortest path from V to every other vertex. You can save time by aborting the DFS whenever it gets K hops away from V
  • LOOP over output from DFS and add to G2 a link between V and every vertex K hops away

I know nothing about pytorch but any decent graph-theory library ( e.g. networkx ) will allow this to be easily implemented, though for greatest efficiency you will probably need to recode DFS.

Here is some C++ code to implement this algorithm using the PathFinder graph theory library.

#include <string>
#include <sstream>
#include <iostream>
#include <vector>
#include "cGraph.h" // https://github.com/JamesBremner/PathFinder

class cArten
{
    raven::graph::cGraph g1;
    raven::graph::cGraph g2;
    std::vector<bool> visited;
    int myHops;
    int myStart;

    void recbfs(int vi, int dist);
    void clear();

    ///////////////////////////////////
public:
    void genExample();

    void setHops(int h)
    {
        myHops = h;
    }

    void solve();

    void display();
};

void cArten::genExample()
{
    g1.add("0", "1");
    g1.add("2", "3");
    g1.add("2", "0");
}

void cArten::recbfs(int vi, int dist)
{
    // check we have not been here before
    if (visited[vi])
        return;
    visited[vi] = true;

    // check is we have travelled far enough
    if (dist == myHops)
    {
        // add to output graph
        g2.add(
            g1.userName(myStart),
            g1.userName(vi));

        // abort search, not interested in going any further
        return;
    }
    dist++;

    // recursive search of adjacent nodes ( BFS )
    for (int ui : g1.adjacentOut(vi))
        recbfs(ui, dist);
}

void cArten::display()
{
    for (auto &l : g2.edgeList())
        std::cout << g2.userName(l.first) 
            << " " << g2.userName(l.second) 
            << "\n";
}

void cArten::clear()
{
    visited.clear();
    visited.resize(g1.vertexCount(), false);
}

void cArten::solve()
{
    // start from every input vertex
    for (myStart = 0; myStart < g1.vertexCount(); myStart++)
    {
        // start new search
        clear();

        // run recursive BFS from start vertex to myHops depth
        recbfs(myStart, 0);
    }
}
main()
{
    cArten a;           // construct
    a.genExample();     // generate input for example
    a.setHops(2);       // set number of hops we want
    a.solve();          // generate output graph
    a.display();        // display output graph

    return 0;
}

The output is

0 3
1 2

Note that 1,3 is absent because vertices 1 and 3 are 3 hops apart.