dmlc / dmlc/dgl

[GRAPHBOLT] Implement Random Walk Neighbor Sampling

Open
#7,881 1 comment 2 reactions 0 assignees View on GitHub
stale-issue
Dominant language
Python
Stars
14.3k
Forks
3.1k
PR merge metrics
No merged PRs in 30d

Description

## 🚀 Feature
[GRAPHBOLT] Implement Random Walk Neighbor Sampling

## Motivation

The PinSage paper ([https://arxiv.org/abs/1806.01973](https://arxiv.org/abs/1806.01973)) demonstrates the effectiveness of using random walks for neighbor sampling in large-scale graph neural networks, particularly for recommendation tasks. They argue that random walks, compared to standard fixed-size neighbor sampling (fanout), can capture more relevant neighborhood structures and node importance by simulating how information might propagate or how users might explore the graph.

Currently, the GraphBolt framework primarily supports uniform neighbor sampling with fixed fanouts. Implementing random walk-based neighbor sampling would allow users to leverage the techniques proposed in PinSage and potentially achieve better model performance on certain graph structures and tasks. Users wishing to implement PinSage-like models currently need to implement this complex sampling logic outside of GraphBolt, hindering ease of use and potentially performance optimization within the framework.

## Alternatives

1. **Continue using existing fanout neighbor sampling:** This is the current approach but doesn't leverage the benefits described in the PinSage paper for capturing neighborhood influence via walks.
2. **Implement random walk sampling outside GraphBolt:** Users can write their own sampling logic, but this adds complexity to their pipelines, requires separate optimization, and doesn't benefit from potential integration and performance tuning within the GraphBolt core.

## Pitch

Introduce a new neighbor sampling mechanism within GraphBolt that performs random walks starting from a given set of seed nodes.

This sampler should allow users to specify parameters relevant to random walks, such as:
* `walk_length`: The number of steps in each random walk.
* `num_walks`: The number of random walks to start from each seed node.
* Optionally, parameters related to walk termination or restart probabilities if more advanced walk strategies are considered.

The output should ideally be compatible with GraphBolt's existing data structures (e.g., `MiniBatch` or similar graph representations) to allow seamless integration into training loops that already use GraphBolt's data loading and processing capabilities. The goal is to provide an efficient, well-integrated implementation of random walk neighbor sampling, inspired by PinSage, within the GraphBolt framework.

## Additional context

* **PinSage Paper:** Hamilton, W. L., Ying, R., & Leskovec, J. (2018). Inductive Representation Learning on Large Graphs. arXiv preprint arXiv:1706.02216. ([https://arxiv.org/abs/1806.01973](https://arxiv.org/abs/1806.01973))
* The PinSage algorithm specifically uses random walks to define a neighborhood and then aggregates features from the *nodes visited* during these walks, often employing importance pooling based on visit counts. The requested feature should ideally facilitate this process.
* It is acknowledged that random walks typically proceed along *outbound* edges, while GraphBolt's sampling infrastructure might be primarily optimized for efficiently accessing *inbound* neighbors (predecessors). However, this potential implementation challenge can often be addressed. In graph datasets where reverse edges are explicitly stored (or can be easily generated), the random walk sampler could be designed to traverse these reverse edges, effectively simulating the desired outbound walk pattern while potentially aligning better with existing optimizations.
* Consideration should be given to the performance implications of running potentially many random walks on large graphs during data loading.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.