I.14.X09

Averaging over sampled neighbours

probability▲▲△

A node has $100$ neighbours whose features have mean $\mu$ and variance $\sigma^2=1$ around it. A sampled layer averages $s$ of them, drawn without replacement. Show that the sampled mean is unbiased, find its variance, and evaluate it for $s=10$ , $25$ and $100$ .

Hint

Each neighbour is included with probability $s/100$ . For sampling without replacement from a finite population of size $N$ , the variance of the sample mean is $(\sigma^2/s)(N-s)/(N-1)$ .

Solution

Write the sampled mean as $\tfrac1s\sum_uI_ux_u$ , where $I_u$ is $1$ if neighbour $u$ is drawn. Each $I_u$ has mean $s/N$ , so the expectation is $\tfrac1s\cdot\tfrac sN\sum_ux_u=\mu$ : unbiased.

The draws are not independent, since choosing one neighbour makes the others slightly less likely. The covariance of two indicators is $-\tfrac sN\cdot\tfrac{N-s}{N(N-1)}$ , and summing gives the finite-population variance

\operatorname{Var}=\frac{\sigma^2}{s}\cdot\frac{N-s}{N-1}.

With $N=100$ and $\sigma^2=1$ : $0.090909$ at $s=10$ , $0.030303$ at $s=25$ , and $0$ at $s=100$ , where every neighbour is used and the mean is exact. Independent draws would have given $0.1$ and $0.04$ ; the factor $(N-s)/(N-1)$ is what sampling without replacement saves.

The layer stays unbiased in expectation, but a nonlinearity applied after it does not average out the noise exactly, and stacking sampled layers compounds it. Sampling buys a fixed cost per node at the price of a noisy, slightly biased deep network, a trade Hamilton, Ying and Leskovec (2017) found worth making on large graphs.

Draws on

I.14.P02 — A graph convolution is a degree-weighted average, and it cannot tell its neighbours apart.