Buffer overflow in cpu/rw.cpp

[darabos]

      cur = col_d[cum_deg_d[cur] +
                  int64_t(rand_d[n * walk_length + (l - 1)] * deg_d[cur])];

If deg_d[cur] is 0, this will give the wrong result. (It will follow an edge that belongs to another node.) If additionally this is the last vertex, it will overflow col_d. If walk_length is 1, it will just give you walks with very high vertex IDs. With longer walks it will segfault.

>>> torch_cluster.rw_cpu.rw(torch.tensor([0, 0, 2, 1]), torch.tensor([1, 2, 3, 3]), torch.tensor([0, 1, 2, 3]), 1, 1, 1, 4) 
tensor([[              0,               1],
        [              1,               3],
        [              2,               3],
        [              3, 140686418058400]])

The CUDA implementation is different, but I think it also generates incorrect walks:

      out[l * numel + n] = col[row[cur] + int64_t(rand[i] * deg[cur])];

How is the algorithm supposed to handle nodes with no outgoing edges? Producing shorter walks when we hit such a node is probably out of the question. Maybe we could just keep repeating the same node then? That would be easy to implement at least.

[rusty1s]

Sorry for missing this issue. This was resolved long time ago :)