{"action":"opened","issue":{"url":"https://api.github.com/repos/ixxi-dante/nw2vec/issues/11","repository_url":"https://api.github.com/repos/ixxi-dante/nw2vec","labels_url":"https://api.github.com/repos/ixxi-dante/nw2vec/issues/11/labels{/name}","comments_url":"https://api.github.com/repos/ixxi-dante/nw2vec/issues/11/comments","events_url":"https://api.github.com/repos/ixxi-dante/nw2vec/issues/11/events","html_url":"https://github.com/ixxi-dante/nw2vec/issues/11","id":313635254,"number":11,"title":"Use non-recursive importance sampling for mini-batches on dense graphs?","user":{"login":"wehlutyk","id":1823010,"avatar_url":"https://avatars3.githubusercontent.com/u/1823010?v=4","gravatar_id":"","url":"https://api.github.com/users/wehlutyk","html_url":"https://github.com/wehlutyk","followers_url":"https://api.github.com/users/wehlutyk/followers","following_url":"https://api.github.com/users/wehlutyk/following{/other_user}","gists_url":"https://api.github.com/users/wehlutyk/gists{/gist_id}","starred_url":"https://api.github.com/users/wehlutyk/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/wehlutyk/subscriptions","organizations_url":"https://api.github.com/users/wehlutyk/orgs","repos_url":"https://api.github.com/users/wehlutyk/repos","events_url":"https://api.github.com/users/wehlutyk/events{/privacy}","received_events_url":"https://api.github.com/users/wehlutyk/received_events","type":"User","site_admin":false},"labels":[{"id":752430790,"url":"https://api.github.com/repos/ixxi-dante/nw2vec/labels/question","name":"question","color":"cc317c","default":true}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":0,"created_at":"2018-04-12T08:57:18Z","updated_at":"2018-04-12T08:57:18Z","closed_at":null,"author_association":"COLLABORATOR","body":"### Problem\r\n\r\nIn the current mini-batch approach being worked on in #10, we sample the nodes that will be part of the mini-batch, then sample their neighbourhoods to define which nodes will be used in the last layer's convolution, then walk back the convolution layers to sample, for each convolution, the neighbourhoods of the nodes that are necessary at the layer after the current one. Therefore:\r\n* if our mini-batch computes a loss for `B` nodes,\r\n* and we sample `M` nodes at each layer,\r\n* and the network architecture is `L` convolutions deep,\r\n\r\nin the worst case we need `B * M^L` nodes to compute that mini-batch, which can be a lot if `L` grows.\r\n\r\n### Available solution\r\n\r\n[Chen, Ma, & Xiao, 2018, \"FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling\"](https://openreview.net/forum?id=rytstxWAW) show that for dense graphs, it may not be necessary to recursively sample this way. At any given convolution layer in the neural network, they estimate a node `u`'s value by sampling on the whole graph proportionally to `||A(u, :)||²` (where `A` is the (normalised?) adjacency matrix), irrespective of the nodes that are used in preceding and following layers in the neural network (this is the *importance sampling* part). With the notations above, the worst case then uses `B * M * L` nodes to compute a given mini-batch. Much better. And the authors show that this method achieves prediction accuracy equivalent to GraphSAGE on several well-tested data sets.\r\n\r\n### Caveat\r\n\r\nThis supposes that an importance sampling on the whole graph can provide enough nodes to estimate *any* node's value at a convolution layer. In other words, this works if the importance sampling provides enough nodes in the neighbourhood of any node in the graph.\r\n\r\n[Hamilton notes this](https://openreview.net/forum?id=rytstxWAW&noteId=rkOyV7wGf) in the review linked to above:\r\n> The idea of sampling vertices at each layer makes sense in small graphs or dense graphs. However, I think it might become problematic in massive, sparse graphs. For example, in industry applications with 1+ billion nodes (or sparse graphs with many disconnected components), I would think the odds of a node in a batch having a neighbor in the sampled set will get quite small, unless the sampled set grows proportionally large in size.\r\n\r\n### Resulting question\r\n\r\nThe question then becomes: how do we know when this can be useful, i.e. when our graph is dense enough to warrant this sampling method?\r\n\r\nPossible answers I see:\r\n* define a threshold on graph sparsity, and see if we need this for the Twitter data\r\n* discard this as a premature optimisation concern, or an engineering-level improvement that we don't wish to spend time on"}}
{"actor":{"display_login":"wehlutyk"}}