dmlc / dmlc/dgl

[GraphBolt] Weighted sampling without replacement is biased

Open
#6,917 1 comment 0 reactions 0 assignees View on GitHub
Work Item
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.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.