-b-35 15 Figure 3:Test ROC-AUC curves on ogbn-proteins Method Accuracy(%)↑Time(s)↓ T1+T2(S) NS 78.84±0.32 1.1×10 3.6×10+7.4×10 VRGCN 78.26±0.64 1.9×104 8.0×103+1.1×10 LADIES 79.49±0.37 1.9×104 1.9×101+3.0×102 GraphSAINT 78.73±0.45 3.3×104 1.1×10+2.2×104 BNS (ours) 79.60±0.29 9.3×108.6×10+7.4×102 Table 3:Results on ogbn-proteins. steps.We can see that the stochastically blocking policy is P2=1 in Equation (3),Equation(5)is a plain Monte-Carlo helpful for BNS to preserve local information around central approximation of Equation (2).The results are presented in nodes Table 4.From Table 4.we can conclude that reweighted poli- Results on ogbn-proteins,a relative small graph,are sum- cy enhances the ability of BNS in utilizing the information of marized in Figure 3 and Table 3,from which we can draw blocked neighbors. the following conclusions.Firstly,BNS is faster than al- I other methods when achieving the same accuracy under Accuracy (%or ROC-AUC (% different settings.However,the gap of the time cost for Methods ogbn- ogbn- ogbn- achieving the same accuracy between BNS and other meth- products papers100M proteins ods is small.The main reason is that neighboring expan- BNS w/o rew 79.12±0.1962.54±0.1479.40±0.21 sions can easily cover the entire graph within a few layer- BNS 80.14±0.27 63.88±0.12 79.60±0.29 s or steps on small-scale graphs.Therefore,these methods have the same order of computation and memory complexity Table 4:Ablation study on reweighted policy.'w/o rew'means BNS O(Nsr Nr2).Secondly,BNS can achieve the best perfor- runs without reweighted policy. mance in terms of accuracy with the fastest speed.This point can be drawn from Table 3,which is consistent with results in Figure 3.Thirdly,once again,we observe that LADIES 5 Conclusions has a high time cost in preparing data.Finally,we observe On large-scale graphs(e.g.,graphs with hundreds of million- that GraphSAINT(non-sampling strategy)achieves lower ac- s of nodes),existing sampling strategies have deficiencies or curacy than NS,LADIES and BNS.This may be caused limitations in accuracy,time cost,or memory cost.Hence, by the over-smoothing problem of GNNs [Li et al.,2018; designing an effective sampling strategy for efficient training Xu et al.,2018;Oono and Suzuki,2020].This observation, of GNNs on large-scale graphs is still challenging.In this pa- in turn,shows that the stochasticity introduced by sampling per,we propose a novel neighbor sampling strategy,dubbed can alleviate the over-smoothing problem of GNNs. blocking-based neighbor sampling(BNS),for training GNNs Summary.First,on large-scale graphs,BNS is 2x ~5x on large-scale graphs.The main idea is to adopt a policy to faster than existing state-of-the-art methods when achieving stochastically block the ongoing expansion of neighbors,by the same accuracy.Compared with BNS,other methods have which computation and memory complexity can be signifi- some deficiencies or limitations.For example,NS needs a cantly reduced.Furthermore,reweighted graph convolution large number of sn to achieve high accuracy.VRGCN and is proposed to adjust the contribution of blocked and non- LADIES have a high time cost of preparing data,which are blocked neighbors to central nodes.Extensive experiments more expensive than performing forward and backward prop- on large-scale graphs show that,when achieving the same ac- agation.Second,even on the small-scale graph,BNS demon- curacy,BNS is 2x~5x faster than state-of-the-art method- strates the advantage of low time cost.Third,compared with s.Experiments on the small-scale graph also demonstrate the other methods.BNS can achieve the best performance in ac- advantage of BNS in terms of time cost. curacy with the minimum time cost. Acknowledgments 4.5 Ablation Study This work is supported by the NSFC-NRF Joint Re- We study the effectiveness of reweighted policy by setting search Project (No.61861146001)and NSFC Project (No. p=1 and p2 =1 in Equation (3).With p=1 and 61921006).0 0.5 1 1.5 2 time (s) 104 74 76 78 80 Test ROC-AUC (%) ogbn-proteins - b =25 BNS(ours) NS VRGCN LADIES GraphSAINT 0 0.5 1 1.5 2 time (s) 104 74 76 78 80 Test ROC-AUC (%) ogbn-proteins - b =35 BNS(ours) NS VRGCN LADIES GraphSAINT 0 0.5 1 1.5 2 time (s) 104 74 76 78 80 Test ROC-AUC (%) ogbn-proteins - b =45 BNS(ours) NS VRGCN LADIES GraphSAINT 0 0.5 1 1.5 2 time (s) 104 74 76 78 80 Test ROC-AUC (%) ogbn-proteins - minimum b BNS(ours) NS VRGCN LADIES GraphSAINT Figure 3: Test ROC-AUC curves on ogbn-proteins. Method Accuracy (%) ↑ Time (s) ↓ T1+T2 (s) NS 78.84 ± 0.32 1.1 × 104 3.6 × 103 + 7.4 × 103 VRGCN 78.26 ± 0.64 1.9 × 104 8.0 × 103 + 1.1 × 104 LADIES 79.49 ± 0.37 1.9 × 104 1.9 × 104 + 3.0 × 102 GraphSAINT 78.73 ± 0.45 3.3 × 104 1.1 × 104 + 2.2 × 104 BNS (ours) 79.60± 0.29 9.3 × 103 8.6 × 103 + 7.4 × 102 Table 3: Results on ogbn-proteins. steps. We can see that the stochastically blocking policy is helpful for BNS to preserve local information around central nodes. Results on ogbn-proteins, a relative small graph, are sum￾marized in Figure 3 and Table 3, from which we can draw the following conclusions. Firstly, BNS is faster than al￾l other methods when achieving the same accuracy under different settings. However, the gap of the time cost for achieving the same accuracy between BNS and other meth￾ods is small. The main reason is that neighboring expan￾sions can easily cover the entire graph within a few layer￾s or steps on small-scale graphs. Therefore, these methods have the same order of computation and memory complexity O(Nsr + Nr2 ). Secondly, BNS can achieve the best perfor￾mance in terms of accuracy with the fastest speed. This point can be drawn from Table 3, which is consistent with results in Figure 3. Thirdly, once again, we observe that LADIES has a high time cost in preparing data. Finally, we observe that GraphSAINT (non-sampling strategy) achieves lower ac￾curacy than NS, LADIES and BNS. This may be caused by the over-smoothing problem of GNNs [Li et al., 2018; Xu et al., 2018; Oono and Suzuki, 2020]. This observation, in turn, shows that the stochasticity introduced by sampling can alleviate the over-smoothing problem of GNNs. Summary. First, on large-scale graphs, BNS is 2× ∼ 5× faster than existing state-of-the-art methods when achieving the same accuracy. Compared with BNS, other methods have some deficiencies or limitations. For example, NS needs a large number of sn to achieve high accuracy. VRGCN and LADIES have a high time cost of preparing data, which are more expensive than performing forward and backward prop￾agation. Second, even on the small-scale graph, BNS demon￾strates the advantage of low time cost. Third, compared with other methods, BNS can achieve the best performance in ac￾curacy with the minimum time cost. 4.5 Ablation Study We study the effectiveness of reweighted policy by setting ρ ` i,1 = 1 and ρ ` i,2 = 1 in Equation (3). With ρ ` i,1 = 1 and ρ ` i,2 = 1 in Equation (3), Equation (5) is a plain Monte-Carlo approximation of Equation (2). The results are presented in Table 4. From Table 4, we can conclude that reweighted poli￾cy enhances the ability of BNS in utilizing the information of blocked neighbors. Methods Accuracy (%) or ROC-AUC (%) ogbn- ogbn- ogbn￾products papers100M proteins BNS w/o rew 79.12 ± 0.19 62.54 ± 0.14 79.40 ± 0.21 BNS 80.14 ± 0.27 63.88 ± 0.12 79.60 ± 0.29 Table 4: Ablation study on reweighted policy. ‘w/o rew’ means BNS runs without reweighted policy. 5 Conclusions On large-scale graphs (e.g., graphs with hundreds of million￾s of nodes), existing sampling strategies have deficiencies or limitations in accuracy, time cost, or memory cost. Hence, designing an effective sampling strategy for efficient training of GNNs on large-scale graphs is still challenging. In this pa￾per, we propose a novel neighbor sampling strategy, dubbed blocking-based neighbor sampling (BNS), for training GNNs on large-scale graphs. The main idea is to adopt a policy to stochastically block the ongoing expansion of neighbors, by which computation and memory complexity can be signifi- cantly reduced. Furthermore, reweighted graph convolution is proposed to adjust the contribution of blocked and non￾blocked neighbors to central nodes. Extensive experiments on large-scale graphs show that, when achieving the same ac￾curacy, BNS is 2× ∼ 5× faster than state-of-the-art method￾s. Experiments on the small-scale graph also demonstrate the advantage of BNS in terms of time cost. Acknowledgments This work is supported by the NSFC-NRF Joint Re￾search Project (No. 61861146001) and NSFC Project (No. 61921006)