[GraphBolt] Weighted sampling without replacement is biased
- Dominant language
- Python
- Stars
- 14.3k
- Forks
- 3.1k
- PR merge metrics
- No merged PRs in 30d
Description
## 🔨Work Item
**IMPORTANT:**
* This template is only for dev team to track project progress. For feature request or bug report, please use the corresponding issue templates.
* DO NOT create a new work item if the purpose is to fix an existing issue or feature request. We will directly use the issue in the project tracker.
Project tracker: https://github.com/orgs/dmlc/projects/2
## Description
Consider edge weights `w=[0.7, 0.2, 0.1]`. If we want to sample 2 edges without replacement in a probability proportional to weight (pps) manner, then the probabilities of sampling the edges should be proportional to `w`. Since we want to sample 2 edges, we can multiply the numbers by 2 to get: `2w=[1.4, 0.4, 0.2]`. However as one can see, we can not sample an edge with a probability greater than `1`, so we need to clip it to `1`. Since the probabilities need to sum to `2` (we want 2 edges), we distribute the `1.4-1=0.4` between the other two elements of `w` to get: `w'=[1.0, 0.6666, 0.3333]`. However, these probabilities are not proportional to the probabilities we started with, making the sampling process biased. We should provide a mechanism to the users to make their weighted sampling without replacement unbiased, as also discussed in section A.7 in https://openreview.net/pdf?id=Kd5W4JRsfV.
In the case above, we need to return edge weights to be used during the forward-backward pass with values proportional to the following values: `w/w'=[0.7/1.0, 0.2/0.6666, 0.1/0.3333]` = `[0.7, 0.3, 0.3]`. These values can be preprocessed for each given fanout value and `probs_or_mask` array, which can then be used as edge weights during training.
With this unbiasing scheme, there is no reason left to use sampling with replacement at all as pps sampling without replacement with this unbiasing trick is going to outperform it in every scenario.
@peizhou001 We can discuss this more in detail. https://colab.research.google.com/drive/1Tpq58GIcIX-FMnWaRV7bEtg9yZQ8a-qt?usp=sharing
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.