Followup
1. We will revise our paper to include details of the difference between our proposed PLADIES algorithm and [1]. Let us talk about some of those
differences in the following 2 paragraphs:
Authors of [1] noticed the same
bias issue as us, and propose a way to "de-bias" sampling without replacement by computing actual sampling probabilities in quadratic time
(Mentioned in [1] Section 5.5). However, PLADIES simply takes linear time because we use Poisson sampling, and with
Poisson sampling the end probability of being sampled is simply the probability of the Bernoulli trial of success, simply $\pi_t$. When one uses
weighted sampling without replacement as in [1], the sampling probability is actually not the weights provided initially and [1] proposes a way to
compute the actual probabilities and a way to de-bias them in quadratic time. There is no convergence difference when it comes to PLADIES and the
de-bias procedure proposed in [1], only the computational complexity of sampling is different. They also propose a way to flatten the
probabilities and these flattened probabilities can be fed to PLADIES as well. So the flattening approach [1] proposes is orthogonal to our work.
To give an example of why weighted sampling without replacement is biased, consider the probabilities [0.7, 0.2, 0.1]. Now, if we want to sample 2
items without replacement, then notice that the probability of the first item, 0.7, is more than 2 times the rest of the items (0.3). Thus, the first
item needs to be sampled always. But even if we always sample the first item, the second item is going to be either 0.2 or 0.1, the probability
of which one it is going to be is [2/3, 1/3]. Thus, in the end, the probability of sampling individual items is [1, 2/3, 1/3]. However, these
resulting probabilities are not linearly proportional to the probabilities we started with. [1] fixes this in quadratic time. We propose to use
Poisson Sampling instead. With Poisson sampling, we can have a constant $c$ to adjust how many items we want to sample. We want 2 items in
expectation, so $0.7c + 0.2c + 0.1c = 2$. But the solution is $c=2$, and the
probability of sampling the first item becomes 1.4, which is not possible. So, we need to solve for $c$ in the following equation:
$\min(0.7c, 1) + \min(0.2c, 1) + \min(0.1c, 1) = 2$. The solution is $c=10/3$, and this can be found in linear time. The resulting probabilities
become: $\min(0.7c, 1) = 1$, $\min(0.2c, 1) = 2/3$, $\min(0.1c, 1) = 1/3$. Because we use these adjusted probabilities during GNN aggregation, our
method is unbiased, and faster than [1] due to computational complexity difference.
2. Note that GNN training runtime depends on how many vertices or edges are processed. Thus, Figure 1 portrays time to convergence in a
hardware-agnostic way by scaling the x-axis by the number of processed vertices or edges. All sampling algorithms compared have linear time
complexity in our paper. We will add a version of Figure 1 where the x-axis is the wall time.
3. We will improve the clarity of Algorithm 1 by adding more details about variables and how they are computed in the camera-ready version.
Section 3.2.2 and Equations 15, 16, and 17 describe one way of solving Equation 14 in linear time.
The output is the sampled set of edges $E'$ along with any computed edge weights $A'$
derived from the importance sampling probabilities to be used as edge weights during aggregation (Equation 4a or 4b) to make the estimation unbiased.
Table 4 in [1] compares two different configurations of LADIES, "LADIES" uses a fixed number of sampled vertices per layer (512, 512, 512)
and "LADIES (2)" when sampling 2 times more than the previous layer (512, 1024, 2048). When we look at their results, it is clear to see that
LADIES (2) outperforms LADIES on all datasets. This means that LADIES doesn't work well with fixed numbers of vertices per layer and it doesn't solve
the neighborhood explosion issue by doing that because it performs poorly as we mentioned in our paper.
What we do in our experiments instead is to follow LABOR-* , when choosing the LADIES variants' number of sampled vertices per layer, as can be seen in
Table 2 of our paper. As a result, it is clear to see that LADIES (PLADIES especially because it is unbiased) performs reliably well,
matching LABOR and NS variants in accuracy on all datasets. Thus, our work
suggests how one should pick the hyperparameters of LADIES variants in a suitable manner, and that is by looking at LABOR-* rather than simply
doubling the number of sampled vertices per layer. We think this is important because the graph topology can be very different for various
applications. Before our work, how to choose the hyperparameters of LADIES in a manner that is robust to changing the underlying graph did not exist.
[1] Yifan Chen, Tianning Xu, Dilek Hakkani-Tur, Di Jin, Yun Yang, Ruoqing Zhu, "Calibrate and Debias Layer-wise Sampling for Graph Convolutional Networks", TMLR 2023