Scale up to million of nodes

[jthsieh]

Hi @tkipf, thank you so much for providing the code.

I'm wondering if it's possible to scale this implementation up to millions of nodes (obviously the number of edges must scale linearly), for example a grid. I'm not familiar with PyTorch's sparse matrix implementation, so I'm not sure if representing the adjacency matrix as a sparse matrix is enough to deal with large graphs?

[tkipf]

For large datasets, have a look at the sampling strategy from FastGCN: https://arxiv.org/abs/1801.10247 This should be relatively easy to implement. Essentially just sample an adjacency and feature matrix (with importance sampling) every training step.

…

On Tue 17. Jul 2018 at 17:34 Tim Hsieh ***@***.***> wrote: Hi @tkipf <https://github.com/tkipf>, thank you so much for providing the code. I'm wondering if it's possible to scale this implementation up to millions of nodes (obviously the number of edges must scale linearly), for example a grid. I'm not familiar with PyTorch's sparse matrix implementation, so I'm not sure if representing the adjacency matrix as a sparse matrix is enough to deal with large graphs? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#14>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AHAcYLWVbsbkYTlueGYii_udbg9hJ1Nnks5uHhISgaJpZM4VTLbI> .

[jthsieh]

Thank you! What if I want to use it on the entire graph?

I guess I just want to confirm:
Let's say I have a graph with N nodes and O(N) edges, and adj is the adjacency matrix of type torch.sparse.FloatTensor. Does torch.spmm(adj, x) run in O(N) time?

[tkipf]

It runs in O(E) time where E is the number of edges (assuming that E>N)

…

On Thu 19. Jul 2018 at 00:29 Tim Hsieh ***@***.***> wrote: Thank you! What if I want to use it on the entire graph? I guess I just want to confirm: Let's say I have a graph with N nodes and O(N) edges, and adj is the adjacency matrix of type torch.sparse.FloatTensor. Does torch.spmm(adj, x) run in O(N) time? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#14 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AHAcYMoIWkliouC9gazV1QqQ69cWq3Emks5uH8TVgaJpZM4VTLbI> .

[jthsieh]

Thank you!