D$^2$-GCN: Data-Dependent GCNs for Boosting Both Efficiency and Scalability
Authors: Chaojian Li
Xu Ouyang
Yang Zhao
Haoran You
Yonggan Fu
Yuchen Gu
Haonan Liu
Siyuan Miao
Yingyan Lin
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Convolutional Networks
Efficient Networks

Abstract: Graph Convolutional Networks (GCNs) have gained an increasing attention thanks to their state-of-the-art (SOTA) performance in graph-based learning tasks. However, their sheer number of node features and large adjacency matrix limit their deployment into real-world applications, as they impose the following challenges: (1) prohibitive inference cost, especially for resource-constrained applications and (2) low trainability of deep GCNs. To this end, we aim to develop low-cost GCNs with improved trainability, as inspired by recent findings in deep neural network optimization which show that not all data/(model components) are equally important. Specifically, we propose a Data-Dependent GCN framework dubbed D$^2$-GCN which integrates data-dependent dynamic skipping at multiple granularities: (1) node-wise skipping to bypass aggregating features of unimportant neighbor nodes and their corresponding combinations; (2) edge-wise skipping to prune the unimportant edge connections of each node; and (3) bit-wise skipping to dynamically adapt the bit-precision of both the node features and weights. Our D$^2$-GCN is achieved by identifying the importance of node features via a low-cost indicator, and thus is simple and generally applicable to various graph-based learning tasks. Extensive experiments and ablation studies on 6 GCN model and dataset pairs consistently validate that the proposed D$^2$-GCN can (1) largely squeeze out unnecessary costs from both the aggregation and combination phases (e.g., reduce the inference FLOPs by $\downarrow$1.1$\times$ $\sim$ $\downarrow$37.0$\times$ and shrink the energy cost of GCN inference by $\downarrow$1.6$\times$ $\sim$ $\downarrow$8.4$\times$), while offering a comparable or an even better accuracy (e.g., $\downarrow$ 0.5% $\sim$ $\uparrow$ 5.6%); and (2) help GCNs to go deeper by boosting their trainability (e.g., providing a $\uparrow$ 0.8% $\sim$ $\uparrow$ 5.1% higher accuracy when increasing the model depth from 4 layers to 64 layers) and thus achieving a comparable or even better accuracy of GCNs with more layers over SOTA techniques (e.g., a $\downarrow$0.4% $\sim$ $\uparrow$38.6% higher accuracy for models with 64 layers). All the codes and pretrained models will be released upon acceptance.

Under review as a conference paper at ICLR 2022
D²-GCN: DATA-DEPENDENT GCNs FOR BOOSTING BOTH EFFICIENCY AND SCALABILITY
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Convolutional Networks (GCNs) have gained an increasing attention thanks their state-of-the-ar (SOTA) performance in graph-based learning tasks. However, their sheer number of node features and large adjacency matrix limit their deployment into real-world applications, as they impose the following chal- lenges: (1) prohibitive inference cost, especially for resource-constrained appli- cations and (2) low trainability of deep GCNs. To this end, we aim to develop low-cost GCNs with improved trainability, inspired by recent findings in deep neural network optimization which show that not all mata/ components) are equally important. Specifically, propose Data- Dete-Depnndent GCN framework dubbed D2-GCN which integrates data-dependent dynamic skipping at multiple granularities: (1) node-wise skipping bypass aggregating features of unimpor- tant neighbor nodes and their corresponding combinations; (2) edge-wise skipping to prune the unimportant edge connections of each node; and (3) bit-wise skipping to dynamically adapt the bit-precision of both the node features and weights. Our D2-GCN achieved by identifying the importance of node features via low-cost indicator, and thus is simple and generally applicable to various graph-based learn- ing tasks. Extensive experiments and ablation studies on 6 GCN model and dataset pairs consistently validate that the proposed D²-GCN can (1) largely squeeze out unnecessary costs from both the aggregation and combination phases (e.g., re- duce the inference FLOPs by (1.1X ~ J37.0x and shrink the energy cost of GCN inference by 11.6x ~ 18.4x), while offering a comparable or an even better ac- curacy (c.g.. 10.5% 15.6%); and (2) help GCNs to go deeper by boosting their trainability (e.g., providing a 10.8% ~ 15.1% 1% higher accuracy when increasing the model depth from 4 layers 64 layers) and thus achieving a comparable better accuracy of GCNs with more layers over SOTA techniques (c.g., a 40.4% ~ 138.6% higher accuracy for models with 64 layers). All the codes and pretrained models will be released upon acceptance.
INTRODUCTION
Graph Convolutional Networks (GCNs) have drawn increasing attention thanks their performance breakthroughs in graph-based learning tasks. In particular, the success of GCNs are attributed to their excellent capability to learn from non-Euclidean graph structures with irregular graph neigh- borhood connections via two execution phases: (1) aggregation, during which the features from the neighbor nodes are aggregated, and (2) combination, in which further updates of the features of each node are made via feed-forward layers to extract more useful features.
Despite their promising performance, the unique structure of GCNs imposes prohibitive challenges for applying them to more extensive real-world applications especially those with large-scale graphs First, GCNs' prohibitive inference cost limits their deployment into resource-constrained devices. For example, a 2-layer GCN model requires 19 Giga (G) Floating Point Operations (FLOPs) to process the Reddit graph (Tailor et al. 2021 and a latency of 2.94 10a milliseconds, when being executed an Intel Xeon E5-2680 CPU platform (Geng et al.) 2020), which is 2x and 5000 over that of a 50-layer powerful Convolutional Neural Network (CNN) (Awan et al. 2017). ResNet- 50, respectively; Second, while CNNs with more layers are known to consistently favor higher accuracy (Belkin et al. 2019). deeper GCNs suffer from accuracy drops compared with shallower ones (Kipf & Welling 2016), making difficult unleash their full potential.

---

Under review as a conference paper at ICLR 2022
Aiming at tackling both of the aforementioned challenges, draw inspirations from recent works.
First, previous CNN works (Katharopoulos & Fleuret 2018 Johnson & Guestrin 2018 Coleman et al. 2018) show that not all samples equally important during training and trainin more informative samples can improve the model accuracy, motivating us to consider allocating GCN computational budgets adapting the sample complexity. In addition, (Zhang al. 2019) finds that not all the CNN layers equally contribute to the final model accuracy and (Wang et al., 2018) demonstrates that skipping some of the layers even helps boost the accuracy while reducing the inference cost of CNNs. Meanwhile, recent GCN works show that not all the nodes contribute equally to the feature extraction (Veličković et al. 2018) and some neighbor nodes can be randomly abandoned without affecting the task performance (Hamilton et al. 2017).
The above prior arts motivate us to consider data-dependent dynamic GCNs for (1) pushing forward their achievable accuracy-effciency frontier and (2) improving the trainability of deeper GCNs. To this end, we adopt a new perspective as compared to existing GCN compression works and ex- plore data-dependent dynamic GCNs on top of SOTA GCNs. Specifically, we identify the potential data-dependent patterns that are unique to GCNs at different granularitis, and then leverage them to largely squeeze out unnecessary costs within GCNs to boost their inference efficiency and trainabil- ity. Specifically, we make the following contributions:
We propose a Data- eata-Dependent GCN framework dubbed D2-GCN, the first dynamic infer- ence framework dedicated to GCNs. D²-GCN integrates data-dependent dynamic skipping at multiple granularities: node-wise, edge-wise, and bit-wise, via low-cost indicator to no- tably reduce the GCN inference cost, while offering comparable or even better accuracy.
D2-GCN is found to naturally alleviate the over-smoothing issue in GCNs and thus im- proves the trainability of deeper GCNs, which we conjecture is because D2-GCN intro- duces more flexibility into the models. Hence, DC-GCN opens up a new knob to not only boost GCNs' inference efficiency but also provide a promising perspective towards deeper and more powerful GCNs.
Extensive experiments and ablation studies top of various SOTA GCNs and datasets consistently validate the effectiveness and advantages of the proposed D2-GCN. In particu- lar, D2-GCN can achieve [1.1 x ~ 137.0x inference FLOPs reduction and [1.6x 18.4x lower energy cost, while leading to a comparable or even better accuracy (10.5% ~ 15.6%).
2 RELATED WORKS
Graph Convolutional Networks. GCNs are one of the most widely adopted algorithms for non- Euclidean and irregular graph structures (Wu et al.) 2020) to categorize the nodes in the same graph (Sen al. 2008) or predict the class of graphs (Hu et al. 2020). They can mainly be divided into two categories: spectral-based (Kipf & Welling 2016) and spatial-based (Gao et al. 2019). For
the spectral-based GCNs, graph convolution which is based on the spectral graph theory CChnng & Graham| (197) is firstly proposed by (Bruna et al.) 2013) and improved in (Kipf & Welling 2010 Defferrard et al. [216 Li et al. (0018b) for wider applications and better accuracy. Meanwhile, the spatial-based GCNs (Hamilton et al. (017) directly perform the convolution in the graph domain by aggregating the neighbor nodes" features and recent works further improve their accuracy via clustering-baat based graph sampling (Chiang et al. 2019), more expressive aggregation scheme (Zeng) let al. (2019), and attention mechanism (Veličković et al. 2018). Orthogonal to those prior works, we explore and develop data-dependent dynamic GCNs on top of SOTA spatial-based GCNs for improving their efficiency and scalability.
Efficient GCNs. Motivated by the fact that the prohibitive computational cost and memory us- age of GCNs, which will even expeditiously increase with the graph size, limit the development of more powerful GCNs and their deployment into real-world applications, various compression techniques has been developed, which mainly fall into three categories: pruning graphs (i.e., sim- pler graphs), pruning weights (i.e., sparser weights), and quantization (i.c., lower bit-precision for hidden features and weights). For pruning graphs, (Li et al. 2020b) introduces a sparse regularizer for pruning the graph connections (i.e., the graph adjacency matrix) and leverages an alternating direction method of multipliers (ADMM) training method to make the regularization differentiable; for pruning weights, (Chen et al., (02T) prunes the graph adjacency matrix and the model weights simultaneouslyy generatizing the fottery ticket hypothesis (Frankle & Carbin 2018) to GCNs; for
2

---

Under review as a conference paper at ICLR 2022
quantization, (Talorr et al. 2021) for the first time trains GCNs with 8-bits integer arithmetic for- warding without sacrificing the classification accuracy. Our proposed D²-GCN considers an unex- plored and orthogonal perspective, and explores data deta-dependent dynamic GCNs on multiple granu- larity levels for achieving better accuracy- -fffciiceff trade-offs and improving GCNs' scalability.
Deeper GCNs. One challenge in designing GCNs is their scalablity of deeper GCNs for (1) han- dling real-world large graphs and (2) unleashing the potential of more sophisticated GCN architec- tures, motivating various techniques along this direction. A pioneering work (Kipf & Welling 2016) attempts to build deeper GCNs through a residual mechanism, and finds that such a design is only ef- fective for GCNs with no more than 2 layers. Then, (Li et al. (018a) argues that the over-smoothing issue (i.e., connected nodes in deeper layers have more similar hidden features) prevent GCN ar- chitectures from going deeper, and thus, several following works strive to design deeper GCNs by alleviating this issue. For example, (Rong et al. 2020) proposes to tackle the over-smoothing issue by randomly removing a certain number of edges from the input graph at each training epoch; (Li let al. (2019b]a a) further explore a generalized aggregation function and normalization layers to boost the performance of GCNs on large-scale graph learning tasks. Our proposed D2-GCN distinguishes itself as the first to explore deeper GCNs from the data data-dependent aspect by incorporating automated data-dependent gating functions to alleviate the over-smoothing issue and facilitate deeper GCNs.
Dynamic inference. Dynamic inference methods have been developed in the context of CNNs for adapting model complexity to input data for reducing overall average inference costs. Early works (Teerapittayanon et al.) (016)] Huang et al.] (017)) equip DNNs with extra branch classifiers to enforce portion of inputs to exit at earlier branches. Later works incorporate a finer-grained layer-wise skipping policy via selectively executing subset of layers conditioned on each input data. In particular, SkipNet (Wang et al.] 2018) adopts reinforcement learning to learn the layer- wise skipping policy and BlockDrop (Wu al. 2018) trains one global policy network to skip residual blocks. The following works extend this idea to even finer-grained granularity levels, e.g.. the filter level (Lin et al.] 2017 Chen et al. (018)) the bit level (Shen al. 2020 Fu al.) 2020). Different from previous works, our DC-GCN framework is the first attempt at dynamic inference in the context of GCNs. More importantly, D²-GCN leverages the unique structures of GCNs to exploit GCN-specific data data-dependent strategies from three different granularities, i.e., node-wise, edge-wise, and bit-wise, largely boost the accuracy-efffciency trade-offss frontiers of GCNs, and further makes these strategies to facilitate the development of deeper GCNs.
3 THE PROPOSED D2-GCN FRAMEWORK
In this section, first introduce the preliminaries of GCNs and the motivating analysis support our D2-GCN framework, and then present the detailed design of D2-GCN and its training pipeline.
3.1 PRELIMINARIES OF GCNS
GCN general formulation. For given graph G = E),E) with n nodes U; E V, yn edges (vi, vy) E E, and an adjacent matrix A E R N to represent the connectivity information, where the non-zero entries represent the existing connections among different nodes. Also, the node degree for each node Uy E V is defined as d4 = Σ; Ai and the diagonal degree matrix D is formed with D;, = dę- For each layer I of a GCN, the hidden features of the nodes are represented by the feature matrix I N where H denotes the hidden feature dimension of each node. Thus, GCN layer can be formulated as:
r1+1 ACT, (Am,Wi).
where Á is the normalized version of A: A- ADD ACT, represents the activation function of layer and W, represents the weights of layer 1. The inference process of one GCN layer can be viewed as two separated phases: Aggregation and Combination. Ar, represents the Aggregation phase which aggregates the 1-hop neighbors of each node into unified feature vector; after that, during the Combination phase, Az; is transformed to Ár via foed-forward layer. Meanwhile, there are also some works that define the combination phase inside the aggregation phase, thus merging the two phases into single message passing process with the self-loop (Hamilton) 2020
3

---

Under review as a conference paper at ICLR 2022
Complexity analysis of GCNs. The computational complexity of GCN inferences can be repre- sented as:
OLLmH + LnH
(2)
where L is the total number of GCN layers, n is the total number of nodes, m is the total number of edges, and H is hidden feature dimension of each node (Chiang et al. 2019).
3.2 DR-GCN: MOTIVATING ANALYSIS
Causes of GCNs' prohibitive inference cost. The inefficiency of GCNs mainly comes from two aspects:
First, graphs are often very large as exacerbated by their complex and irregular neighbor connections, which lead prohibitive amount of nodes and edges, i.e., and n in Eq. [2 re- spectively. For example, a graph dataset can come with as many as 169,343 nodes and 39,561,252 edges (Hu et al. 2020), which can cause both large computational and data movement costs. Sec- ond, the dimension of GCNs' node feature vectors, i.e., H in Eq. 2 can be very large, e.g., each node in the Citeseer graph has feature dimension of 3,703, leading to a high workload during the feed-forward computation in the combination step, especially when the computations are conducted with full precision (i.e.. 32-bits float point). Accordingly, a straightforward way to reduce the afore- mentioned costs associated with GCN inference is to reduce the number of (1) nodes, i.e., n in Eq. 2 (2) connections between nodes, i.e., edges, m in Eq. [ and (3) features of each node, i.e., H in Eq. whereas naively reducing these parameters can hurt GCNs' model capacity and thus their achievable task accuracy.
Causes of deeper GCNs' training difficulty. Deeper GCNs are consistently observed to suffer from accuracy drop as compared to their shallower counterparts, regardless of the adopted GCN designs (Kipf & Welling 2016; Pham et al., [017]] Rahimi et al. 2018 Xu et al. 2208)). (Li et al. 2018a Zhao & Akoglu 2019) propose that the accuracy drop is resulted from the GCN's over- smoothing issue, i.e., repeatedly applying GCN layers many times will make the hidden features of different nodes converge to similar values. Based on that, some regularizations are proposed to enable deeper GCN achieve higher accuracy, e.g., randomly drop out certain edges of the input graph during each training iteration in (Rong et al. 2020).
Not all data/(model components) are equally important. CNNs (Katharopoulos & Fleurei| 2018 Wang et al., 2018) and GCNs (Veličković et al.) 2018 Hamilton al.| (017)) show that not all data samples, e.g., imput images or graphs, and model com- ponents, e.g.. specific Convolutional or Graph Convolutional layers, for the same model are equally important for a given task in terms of the achievable accuracy vs. efficiency trade-offs. For example, some of data//model components) can be skipped without hurting even boosting the accuracy due to the increased model flexibility. These observations motivate us to consider boosting both GCNs' efficiency and scalability by processing the graphs in comprehensive data-dependent manner, i.e., for different data, only a fraction of the graph's 's components, e.g., parts of nodes, edges, or bit- width, involved into the computations based the corresponding features of the given graph. The resulting benefits come from two aspects: (1) such a data-dependent design can dynamically allocate more computational budgets difficult data samples and smaller budgets for simpler data samples to reduce the total inference cost while maintaining the accuracy; and (2) the increased model flexibility resulting from the dynamic inference models can naturally provide a certain reg- ularization effect since different components of graph may work together or independently in an data-dependent manner to alleviate GCNs" smoothin issue discussed in (Li et al., 2020a). As such, deeper GCNs can be more effectively trained thanks to the improved learning capacity enabled by the increased model flexibility.
Recent works in both
3.3 D2-GCN: SKIPPING STRATEGY DESIGN
Overview. Motivated by the analysis in the above subsection, we propose the D²-GCN framework that can dynamically process each graph with a complexity adapting to the data difficulty at three granularities, i.c., node/edge/bit-wwe wise,, as shown in Fig. [] We hypothesize that such a coarse-to- to-fine strategy can achieve more efficient GCN inference without hurting the accuracy, and maximize the flexibility of GCN structures to provide effective regularizations for training deeper GCNs. Based on the GCN layer formulation in Fq.
represent each layer of our proposed D2CG
4

---

Under review as a conference paper at ICLR 2022
r141
96 ④ of (1 -( om
(3)
Σ km1
9i
b.k
(Agt QB (z)) (wi))
(4)
og = (of)²²
(5)
where 21+1 and 3 RaxH denote the feature matrix of layer 1 and layer I, respectively, wi R is the weights for the Combination phase in layer I, Å R=x* is the normalized adjacency ma- trix, and represents the element-wise matrix mul- tiplication (broadcast will be performed if the ma- trix shapes do not match). All the variables above share the same definition Specif- ically, in Eq. se {0, 1]mx1 represents the output of the gating func- tion for node-wise skip- ping, and oet is the fea- ture matrix after enabling the gating function for bit- wise skipping in layer in Eq. 4 of E [0,
Node-wise Skipping
Edge-wise Skipping
Bit-wise Skipping
Gating Function
Xo
xo
X1
X1
X2
X2
X2
1009
X3
X3
as in Eq.
Figure An illustration of our proposed D2-GCN technique in one layer. Specially, X1 X4 are the 4 nodes in the graph. In this exam- ple, the aggregation and combination phases of Xo and X₂ are skipped (i.e., node-wise skipping tures of Xo and X₂ are also skipped in the aggregation phases their neighbors (i.e., edge-wise skipping as illustrated in Eq. 5 while the aggregation and combination phases X1 and X3 are processed with precision lower than 32-bits float point (i.e., bit-wise skipping as illustrated in Eq.
illustrated in Eq. 3 and the hidden fea-
(g) E 1).1)ax1 is the k-th entry of gf) represents the output of the gating function for bit-wise skipping, QB. the quantization function to quantize weights wy and feature matrix oi into Bg- bits following the pre-defined quantization bit-width options B = {Bi.... Bx). and Agr is the normalized adjacency matrix after enabling the gating function for edge-wise skipping in layer I; and in Eq. 5 of E {0, 1]nx1 represents the output of the gating function for edge-wise skipping. We elaborate more how they work in GCNs and how they tackle the causes of GCNs' inference cost below.
Node-wise skipping (i.e., Eq. 3). oe makes a binary decision for each node regarding whether to skip its aggregation and combination phases based on its hidden features. In this way, a set of less important nodes identified by of will not participate the feed-forward computation during each GCN inference and the corresponding hidden features in the feature matrix will be directly passed to the next layer to construct 71+11 so that the inference cost (FLOPs, latency, and energy) will be reduced thanks to the smaller n and m in the computational complexity, as analyzed in Eq. 2
Bit-wise skipping (i.e., 4). of determines the quantization precision in both the aggregation and combination phases for each node according to its hidden features. Since quantization reduces the feed-forward computation from the most fine-grained bit level, the computational cost for updating each feature can be aggressively reduced, making it feasible to deal with large node feature vectors even on resource constrained platforms.
Edge-wise skipping (i.e., Eq. 5). of determines whether the connection between two nodes will be removed based on the hidden features of the corresponding nodes. Specifically, the connection will be removed when the corresponding item is zero in Age. as defined in Eg. and thus result a smaller inference cost (FLOPs, latency, and energy) thanks the resulting smaller m in Eq.
5

---

Under review as a conference paper at ICLR 2022
Gating function design. Inspired by the gating function designs from dynamic CNNs (Wang al. 2018). we adopt a single feed-forward layer (i.e., fully-connected layer) to map each node s feature (a vector with the shape of 1 x H) the output of the gating functions. For the node-wise and edge-wise skipping, the output of the gating functions is only an element with the shape of 1 x 1. For the bit-wise skipping, the output of the gating functions is vector with the shape of K. K represents the number of bit-width options and we set K = 4 in our experiments. Additionally, we follow (Wang al. 2018) to make the training of the gating functions differentiable via straight through estimators (Bengio et al. 2013). After building the gate functions following the design described above, we surprisingly find that such simple design can effectively capture the dynamic patterns with very low computational overhead. In our design, it is less than 0.07% of the GCN model's s cost in terms of FL.OPs, while the gating functions CNNs can cause an overhead of as large as 12.5% (1179x) (Wang et al. 2020).
3.4 D²-GCN: TRAINING PIPELINE DESIGN
Learning objective. The learning objective of D2-GCN, LDa (W, We), can be formulated as:
Gpa- (W, Wa) = LGGN (W, Wa) + a Leomp
(6)
where W = [wo, W1, ).. is the total set of model weights, WG = [wag- Wag We W .... is the total set of the gating functions' weights, LGON is the commonly adopted loss function of graph- based learning tasks like node classification (Kipf & Welling, (016) or graph classification (Hu et al. 2020), a is trade-off parameter to balance task performance and efficiency, and Leomp is the computational cost determined by the gating functions. If we use FLOPS as its metric, can be written as:
(1 1oll Di a llo n + 19 1
EK l1 of of )2
commp
n
Els (mH + nH2)
The variables in Eq. 7 share the same definition as those in Eq. 0 and i.e., n is the total number of nodes, m is the total number of edges, / is the feature dimensions of each node, Agf
is the adjacency matrix after enabling the gating function for adge-wise skipping in layer 1, gi b.k is the k-th entry of of which is the output of the bit-wise skipping's s gating function, and of represents the output of the gating function for node-wise skipping. how our data-dependant dynamic skipping techniques reduce the inference cost. Specifically, the node-wise skipping will squeeze the cost via reducing the number of nodes (n) to || Ilo < n. The edge-wise skipping will shrink the the number of edges (m) to || -l m to reduce the inference cost. The bit-wise skipping will reduce the cost of each matrix multiplication/adddiio by using a smaller bit-width instead of full precision (32-bits), which can be regarded as further multiplying By factor to the inference cost (i.e., EK 1 6. [1o
worth noting that Eq. also indicates
"1oo ( By 1 and ΣK
n
Three-stage training pipeline. Jointly training the GCN and gating functions from scratch could lead to both lower task performance and inferior gating decisions since the gating functions with random initializations in the early training stages may harm the learning process via improper gating strategies. Therefore, we propose a three-stage training pipeline to stabilize the training of DCCGNN
Stage 1: We pretrain the GCN model with the gating functions fixed and unused. We find this step is indispensable for a decent DC-GCN design since the gating functions can hardly learn meaningful gating strategy on top of an under-performed GCN model.
Stage 2: We fix the GCN model and train the gating functions only maximize the task performance by setting the trade-off parameter in Eq. 66 to be O. Since randomly initialized gating functions may generate improper gating strategies which may deteriorate the pretrained GCN's performance, this step contributes to generate a decent initialization for the gating functions' weights.
Stage 3: We jointly train the GCN model and gating functions based on Eq. optimize both the task performance and computational cost. After this step, the D²-GCN trained model is ready to be delivered and deployed onto the target platform.

---

Under review as a conference paper at ICLR 2022
4 EXPERIMENTS RESULTS
In this section, first introduce the experiment setup and then verify our hypothesis that (1) D GCN can boost the efficiency, i.e., achieving better accuracy vs. efficiency trade-off' than both vanilla models and models with SOTA efficient GCN techniques; and (2) DC-GCN can boost the scalability, Le., achieving a higher accuracy when being applied to deeper GCNs than both vanilla models and models with SOTA scalable GCN techniques. Finally, perform ablation study on the effectiveness of skipping at different granularities, i.e., how the node-wise, edge-wise, and bit- wise skipping individually affect the achieved accuracy efficiency trade-offs, and visualize the skipping patterns to provide more insights.
4.1 EXPERIMENTS SETUP
Model, datasets, and training hyperparameters. We evaluate proposed D2-GCN 6 GCN model and dataset pairs (i.e., 3 GCNII (Chen et al. 2020 models on Cora, Citeseer,
and Pubmed (Sen et al.] 2008) and 3 DeeperGCN (Li al. 2020a) models on ogbg-molhiv,
ogbn-arxiv, and ogbn-proteins (Hu et al. 20200) as summarized in Table All the training hy- perparameters follow the original implementation in (Chen al. 2020 Li al. 2020ap, and we sweep which is described in Eq. 6 ranging from 0.1 to 10 in all experiments, and set K 4, B1 2, B2 B3 B₁ 16, which are defined in Eq.
Baselines and evaluation metries. We compare our proposed D²-GCN over two types baselines to verify its efficiency and scalability (to deeper GCNs), respectively.
Efficiency baselines: Degree- Qaaree-Quntttta (Tailor et al. 2021 QAT (Fan et al. 2021 and UGS (Chen 2021) are included into the benchmark verify that our proposed D²-GCN can boost the efficiency in terms of accuracy vs. FL.OP//latency/eeergy trade-offs.
Scalability baselines: We compare our proposed D2-GCN with DropEdge (Rong et al., 2020) and GCNII (Chen et al.] 2020). which are the SOTA method to improve the scalability of GCN, aiming at achieving better accuracy with more number of layers.
Specifically, the accuracy is reported as the average over 10 runs with different random seeds, the FLOPs metric follows the computation complexity analyzed in (Chiang et al. (209)) and the adapta- tion quantized models in (Fu et al. 2020), and lateney/energy is simulated using the architecture described in (Qin et al. 2020).
4.2 DC-GCN BOOSTS THE EFFICIENCY
By comparing our D2-GCN with SOTA efficient GCN techniques on different models and datasets in Table 2 we can observe the consistent effectiveness of DC- in boosting the efficiency of GCNs. Specifically,
proposed D2-GCN consistently surpasses all the competitors by achieving 11.1x ~ +37.0x FLOPs/LI.6x ~ 48.4x latency441.6x ~ 48.4x energy reduction, while achiev- ing comparable even higher accuracy (10.5% 15.6%). We conjecture that this is because (1) UGS (Chen et al.) 2021) only considers the redundancy from edge-wise and node-wise while Degree-Quant Taalor
2021) QAT' (Fan al. 2021) only considers the redundancy from bit-wise; In contrast, our proposed D2-GCN simultaneously squeezes out unnecessary costs of GCNs from the edge-wise, node-wise, and bit- level; and (2) UGS (Chen et al. (021). Degree- Quant (Tailor et al., 2021). and QAT (Fan et al.) (221)) do not leverage the assumption that not all data/model components are equally important, which has been verified by (Wang et al. 2020 Katharopoulos & Fleuret, 2018), thus they may only achieve sub-optimal accuracy vs. efficincyy trade-offs because hard/easy samples are assigned insufficientrredunaan computational resource,
Table 1: The statistics of the GCN models and datasets.
Model
#Layers
Dataset
Dataset Type
#Graphs
Avg. #Nodes
Avg. #Edges
64
Cora (Sen et
2008
2,708
5,429
GCNII
classification
3.327
4,732
16
Puhmed
Non el mi
200S
19,717
44,338
DecperGCN
ct 2020a
112
oghn- gehneinoteins
ogbi-arxiv
(Hi ct
(Hu
A170
2020
Nade classification
169,343
132,534
39,561,252
1,166.243
7
ogbg-molliv
2000
Graph classification
41,127
25.5
27.5
7

---

Under review as a conference paper at ICLR 2022
Table Comparison between D²-GCN and SOTA efficient GCN techniques in terms of accuracy efficiency trade-off's, where vanilla the original setting of the corresponding models and datasets without any efficient GCN techniques.
Normalized
Method
Accuracy (%)
FLOPs (G)
Latency (%)
Energy (%)
GCNIC Cora
Vanilla
85.5
0.74
100.0
100.0
UGS
82.4
0.59
99.9
99.9
QAT
85.1
0.06
20.0
20.0
Degree- Quant
81.0
0.12
20.0
20.0
D²-GCN
85.6
0.02
12.6
12.2
DCNGCN Improv.
10.1 14.6
13.0x x37.0x
1166
GCNI @ Citeseer
Vanilla
73.4
7.05
100.0
100.0
UGS QAT
72.1
5.65
99.9
99.8
73.4
0.48
22.0
22.0
Degree-Quant
69.5
1.13
22.0
22.0
D2-GCN
73.4
13.3
D2-GCN Improv.
10.0
13.9
J2.2x 4,3.0xx
41.7x L75x
J1.7% 47.5x
GCNI
Vanilla
80.2
20.86
100.0
100.0
UGS QAT
78.8
16.71
79.5
1.34
24.7
24.7
Degree- Quant
77.8
3.29
24.7
24.7
D2-GCN
79.7
1.13
14,9
14.8
D²-GCN Improv.
10.5 11.7
11.2x x
J1.7x
J6.7x
1177 16.8%
DeeperGCN@ogbgemeenn
Vanilla UGS QAT Degree- Quant
78.6
483.14
100.0
100.0
75.8
386.81
97.1
99,9
72.9
30.58
21.1
21.1
78.2
D2-GCN
78.5
28.73
12.3
12,4
Dº.GCN Improv.
10.1 ~ 15.6
J.LIX J1688
11.7x e 18.1X
41.7 ~ 18.1
DeeperGCN@ogbn-uuen
Vanilla UGS
71.9
81.87
100.0
100.0
71.4
66.
98.2
98.2
D2-GCN
72.2
12.37
14.7
14.5
D²-GCN Improv.
10.3 ~ 10.8
x ~ J6.6x
J6.7
J6.8x
16.8x x
Vanilla UGS
85.8
405.17
100.0
100.0
85.2
366.67
97.7
97.8
Degree Quant
85.1
111.16
23.4
D2-GCN
85,3
72.24
11.9
11.9
D²-GCN Improv.
10.5% ~ 70.2%
J1.5x ~ [5.6X
11.9x ~ [8.4
42.0x ~ 48.4x
whereas our proposed D2-GCN is a data-dependent framework that processes each data sample with adaptive model capacity/cost, maximizing the accuracy efficiency trade-offs.
Table 3: Comparison between DD-GCN and
4.3 D2-GCN BOOSTS THE SCALABILITY
SOTA scalable GCN techniques. where vanilla is the original setting used in (Kipf & Welling 2016) without any scalable GCN techniques. which achieves lower acccuracy when going deeper.
As summarized in Table by varying the num- ber of layers from 4 to 64 on different datasets, proposed D2-GCN (1) achieves higher accuracy as we increase the number of lay- ers (i.c., 10.8% 15.1% accuracy boost) and (2) is on par with SOTA techniques for bet- GCN scalability (i.e., GCNII (Chen et al.) 2020) and DropEdge (Rong et al.) 2020)) with a comparable or even better accuracy under the same number of layers, especially deeper models (L0.4% ~ 138.6% for models with 64 layers). This set of experiments indicates that with the proposed node-wise, edge-wise, and bit-wise skipping at different granularities, our
Datasct
Method
Accuracy (%) with Num. layers
16
64
Vanilla
80.4
64.9
28.7
DeopFlge
82.0
75.7
49.5
Curn
GÜNII
82.6
$4.2
85.5
DP-GUN
D2-GUN Improx.
119.3
Vanilla
Droplige
57.2
D2-GCN
68.7
73.1
73,0
D2-GCN Improv.
10. ~ 12.1
10,2 ~ 154.
10.4 *53.0
Vanill:
76.5
40.9
35.5
DeepEdge
79.8
78.5
61.5
Puhmedd
GUNII
78.8
80.2
79.7
DF-GCN
79.0
79,5
79.8
D*-GCN Improv.
10.4~ 1044-~125
J0.7 138.6
10.1 -44.5
8

---

Under review as a conference paper at ICLR 2022
proposed D2-GCN can alleviate the over smoothing issue, discussed in (Li et al. 2018a), and thus facilitate GCNs to achieve a higher accuracy when going deeper. This matches our hypothesis that such data-dependent skipping techniques can enforce regularization effect since different com- ponents of a graph may work together or independently in an data-dependent manner to facilitate the removal of the over-smoothing issue
4.4 ABLATION STUDY: EIFECTIVENESS OF SKIPPING AT DIFFERENT GRANULARITIES
As introduced in Figure I D²-GCN integrates node- wise, edge-wise, and bit- wise skipping, which tar- get different granularities. For a better understand- ing of the proposed D GCN, we conduct an abla- tion study on the effective- ness of each skipping tech- nique on both node classi- fication (Cora (Sen et al.) 2008) and graph clas- sification datasets (ogbn- molhiv (Hu al., (2000). i... disabling one skipping
Table 4: Comparison among mode-wise, adge-wise and bit-wise skip- ping at different granularities the proposed D²-GCN, where vanilla is the original setting of the corresponding models and datasets with- out any efficient GCN techniques.
Method
Accuracy (%)
FLOPs (G)
Normalized
Energy
Vanilla
85.5
0.71
100.0
100.0
D2-GCN node-wise skipping DE-GION edge-wise skipping DI-GCN wio bit-wise skipping
(106)
0.03 (124.7x))
13.6
13.7 (17.3x)
(10.))
0.03 (124.7x)
(17(()744))
13,6 (17.4x)
85.5 (10.0)
0.67 (LL.1))
88.2 (11.10
D2-GN
(7.61)
(J37.88
(U7.9))
(22.2)
Vanilla
78.6
484.14
1000
100.0
D²-GCN node-wise skipping
75.5
40,87 (L11.8))
(4.00)00)))
(17.0g)
-CNN wro edge-wise skipping
77.7 (10.9)
28.91 (11677))
130(7)7)))
13.2 (17.6x)
D--GON wio bit-wise skipping
77.5 (L1.))
338.2
(11.))
D2-CCN
78.5 (10.1)
28.7 (1169x))
12.3 (28.1)
1244((x))))
technique of our proposed D2-GCN each time, and summarize the results Table 4 We can make the following observations: (1) only incorporating one skipping technique corresponding to one granularity can still reduce the inference cost (e.g., FLOPs, energy, and latency) of GCN mod- els but leading to obviously lower accuracy (11.1x J24.7x less FLOPs//1.1x ~ 47.7x less latency/L1.1 1.11 x ~ J7.6x less energy, but 13.1% ~ 10.1% accuracy decrease) than the baselines; and (2) D²-GCN integrating node-wise, edge-wise, and bit-wise skipping simultaneously can achieve better accuracy vs. efficiency trade-offs than its vanilla basclines disabling one/two of the three (11.5x x less FLOPs/L1.Ix 7.4x less latency/1.Ix 7.4x less energy, and 10.0% ~ 13.0% higher accuracy), validating the importance of skipping at all the three different granularities, as described in Section 3.3
4.5 MORE INSIGHTS FROM VISUALIZATION OF THE SKIPPING PATTERNS
To better understand and illustrate why D2- surpasses all the efficient GCN competitors in terms of accuracy vs. efficienct trade-offs, as demonstrated Table we visualize the layer-wise FLOPs
FLOPs Remaining Ratio
GCNII@Cora
0.0
10
50
60
Layer
(a)
Remaining Ratio. Remaining Ratio
GCNil@Citeseer
FLOPs
10
Layer Index
20
25
GCNlI@Pubmed
FLOPs
0.2
0.1
0.0
Layor Index (c)
Figure 2: Visualization of the FLOPs remaining ratio (i.e., the ratio between FLOPS of GCNs w/ and w/o our proposed D2-GCN) of different layers when our proposed D2-GCN is added on top of GCNI model with the (a) Cora, (b) Citeseer, and (c) Pubmed datasets.

---

Under review as a conference paper at ICLR 2022
remaining ratio (the lower means the more FLOPs reduction is enabled by our proposed D²-GCN) in Figure We can extract the following insights: (1) the imbalance FLOPs remaining ratios among different layers verify that the hypothesis, not all data/model components are equally important, also holds for GCNs; (2) such imbalance FLOPPs remaining ratios play an important role in enabling the proposed D2-GCN to achieve SOTA accuracy vs. efficient trade-offs by dynamically allocating more computational budgets to difficult data samples and/or important model components and lower budgets for simple data samples and/or unnecessary model components to reduce the total inference cost while maintaining the accuracy, because the SOTA efficient GCN baseline techniques in Section 4.2 are using either the same node and edge relationships (i.e. adjacency matrix A in Eq. [T Tailor et al. 2021 Fan et al. 2021) or the same bit-widths (Chen et al. (022)) along all layers; and (3) the latter layers (i.e., closer to the final classifier) tend to maintain higher FLOPs remaining ratios, i.e., they are less redundant and more important than the former layers, which can provides insights for more efficient GCN architecture design.
CONCLUSION
In this paper, we propose a Data-Dependent GCN framework, D²-GCN, which is the first dynamic inference framework dedicated to GCNs. Specifically, three types of low-cost gating functions are integrated to realize data-dependent dynamic skipping at multiple granularities: node-wise, edge- wise, and bit-wise, targeting fewer nodes to combine, fewer edges to aggregate, and lower bit- precision to compute. Besides achieving SOTA accuracy vs. efficiency trade-offs to facilitate the deployment of GCNs onto resource-constrained applications, our proposed D2-GCN on alleviating the over-smoothing issue of GCNs to improve the accuracy of GCNs when they go deeper, thus removing the barriers of handling real-world large graphs and unleashing the potential of more sophisticated GCN architectures. As such, D²-GCN opens up new knob to not only boost GCNs' inference efficiency but also help to build deeper and more powerful GCNs in the data-dependant manner.
also help
6 REPRODUCIBILITY STATEMENT
Regarding our efforts that have been made to ensure reproducibility, we provide the implementation details in Appendix A
REFERENCES
Ammar Ahmad Awan, Hari Subramoni, and Dhabaleswar K. Panda. An in-depth performance char- acterization of cpu- and gpu-based dnn training on modern architectures. In Proceedings of the Machine Learning on HPC Environments, MLHPC' Association for Computing Machinery, 2017. ISBN 978 778145035137, doi:
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 1 116(32):15849-1555))
2019.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation. arXiv preprint arXiv: 1311.3383333 2013.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 131..16332..233 2013.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In International Conference Machine Learning, pp. 1725-1735. PMLR, 2020.
Tianlong Chen, Yongduo Sui, Xuxi Chen, Aston Zhang, and Zhangyang Wang. A unified lottery ticket hypothesis for graph neural networks. In International Conference on Machine Learning, pp. 1695-1706. PMLR, 2021.
Zhourong Chen, Yang Li, Samy Bengio, and Si Si. Gaternet: Dynamic filter selection in convolu- tional neural network via a dedicated global gating network. arXiv preprint arXiv: 11w.:111...11 1205, (7), 2018
10

---

Under review as a conference paper at ICLR 2022
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92. American Mathematical Soc., 1997.
Cody Coleman, Stephen Mussmann, Baharan Mirzasoleiman, Peter Bailis, Percy Liang, Jure Leskovec, and Matei Zaharia. Select via proxy: Efficient data selection for training deep net- works. 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29:3844 2016.
Angela Fan, Pierre Stock, Benjamin Graham, Edouard Grave, Rémi Gribonval, Herve Jegou, and Armand Joulin. Training with quantization noise for extreme model compression. In International Conference on Learning Representations, 2021.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint a w1..iv:1103....0 803.03635, 2018.
Yonggan Fu, Haoran You, Yang Zhao, Yue Wang, Chaojian Li, Kailash Gopalakrishnan, Zhangyang Wang, and Yingyan Lin. Fractrain: Fractionally squeezing bit savings both temporally and spa- tially for efficient dnn training. arXiv preprint 1tXiv:2012.13113. 2020.
Yang Gao, Hong Yang, Peng Zhang, Chuan Zhou, and Yue Hu. Graphnas: Graph neural architecture search with reinforcement learning. arXiv preprint arXiv: 1904. 09.999,,, 2019.
Tong Geng, Ang Li, Runbin Shi, Chunshu Wu, Tianqi Wang, Yanfei Li, Pouya Haghi, Antonino Tumeo, Shuai Che, Steve Reinhardt, et al. Awb-gen A graph convolutional network accelerator with runtime workload rebalancing. In 53rd IEEE/ACM Int. Symp. Microarchit((MIIRR)) pp- 1-15, 2020.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
William I. Hamilton. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning, 14(3):1-159, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint MtXiv:2005.006877 2020.
Gao Huang, Danlu Chen, Tianhong Li, Felix Wu, Laurens van der Maaten, and Kilian Q Wein- berger. Multi-scale dense networks for resource efficient image classification. arXiv preprint MtXiv:1703.09844, 2017.
Tyler B Johnson and Carlos Guestrin. Training deep models faster with robust, approximate impor- tance sampling. Advances in Neural Information Processing Systems, 31:7265-7275 2018.
Angelos Katharopoulos and François Fleuret. Not all samples are created equal: Deep learning with importance sampling. In International conference on machine learning, pp. 2525-2534. PMLR, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint NeX.iii66699000000 2016.
Guohao Li, Matthias Müller, Guocheng Qian, Itzel C. Delgadillo, Abdulellah Abualshour, Ali Tha- bet, and Bernard Ghanem. Deepgens: Making gens go as deep as cnns, 2019a.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cans? In The IEEE International Conference on Computer Vision (ICCV), 2019b.
11

---

Under review as a conference paper at ICLR 2022
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, arXiv preprint arXiv:2006.07739, 2020a.
Jiayu Li, Tianyun Zhang, Hao Tian, Shengmin Jin, Makan Fardad, and Reza Zafarani. Sgen: A graph sparsifier based on graph convolutional networks. In Pacific-Asis Conference on Knowledge Discovery and Data Mining, pp. 275-287. Springer, 2020b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAT Conference Artificial Intelligence, volume 32, 20.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 201 20.
Ji Lin, Yongming Rao, Jiwen Lu, and Jie Zhou. Runtime neural pruning. In Advances in neural information processing systems, pp. 2181-2191, 2017.
Trang Pham, Truyen Tran, Dinh Phung, and Svetha Venkatesh. Column networks for collective classification. In Thirty-first AAAI conference on artificial intelligence, 2017.
Eric Qin, Ananda Samajdar, Hyoukjun Kwon, Vineet Nadella, Sudarshan Srinivasan, Dipankar Das, Bharat Kaul, and Tushar Krishna. Sigma: A sparse and irregular gemm accelerator with flexible interconnects for dnn training. In 2020 IEEE International Symposium on High Performance Computer Architecture (HPCA), pp. 58-70. IEEE, 2020.
Afshin Rahimi, Trevor Cohn, and Timothy Baldwin. Semi-super user geolocation via graph convolutional networks, arXiv preprint arXiv: (80418804409)) 2018.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020. URL htt.l:ttt////ttttt http:::://///eereiieeee net/ feee//oormmidd=Hxxxl
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina CliassiRRad Collective classification in network data. Al magazine, 29(3):93 93, 2008
Jianghao Shen, Yue Wang, Pengfei Xu, Yonggan Fu, Zhangyang Wang, and Yingyan Lin. Fractional skipping: Towards finer-grained dynamic enn inference. In AAAI, pp. 5700-570% 2020.
Shyam Anil Tailor, Javier Fernande--Maqques and Nicholas Donald Lane. Degrec-quant: Quantization training for graph neural networks. International Conference on Learning Representations, 2021. URL
wwtp:/rwwwwwwwwweeeeeeeeeeeeeeee net/ htte://ooouummddssBe30000
Surat Teerapittayanon, Bradley McDanel, and Hsiang-Tsuun Kung. Branchynet: Fast inference via early exiting from deep neural networks. In 2016 23rd International Conference on Pattern Recognition (ICPR), pp. 2464-2469. IEEE, 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. httttttts//::eeemt
Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dynamic routing in convolutional networks. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 409-424, 2018.
Yue Wang, Jianghao Shen, Ting-Kuei Hu, Pengfei Xu, Tan Nguyen, Richard Baraniuk, Zhangyang Wang, and Yingyan Lin. Dual dynamic inference: Enabling more efficient, adaptive, and con- trollable deep inference. IEEE Journal of Selected Topics in Signal Processing, 14(4):623-63 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A com- prehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 2020.
12

---

Under review as a conference paper at ICLR 2022
Zuxuan Wu, Tushar Nagarajan, Abhishek Kumar, Steven Rennie, Larry Davis, Kristen Grauman, and Rogerio Feris. Blockdrop: Dynamic inference paths in residual networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 8817-8826, 2018.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning pp. 5453-5462. PMLR, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Aceu- rate, efficient and scalable graph embedding. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 462-471. IEEE, 2019.
Chiyuan Zhang, Samy Bengio, and Yoram Singer. Are all layers created equal? arX.v:1902.0199, 2019.
arXiv preprint
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in gnns. arXiv preprint arXiv:1909.12223, 2019.
13

---

Under review as a conference paper at ICLR 2022
A IMPLEMENTATION DETAILS
We provide the implementation details of our experiments here, including our D2-GCN (1) on Cora, Citeseer and Pubmed datasets (Sen al. 2008) on top of GCNII models (Chen et al. 2020 and (2) ogbg-molhiv, obgn-arXiv, and ogbn-proteins dataset (Hu et al. 2020 on top of DeeperGCN
models (Li et al. 2020a) in Section 4.2 4.5
D2-GCN models on Cora, Citeseer and Pubmed datasets. All the reported D²-GCN models on these datasets on top of GCNII models (Chen et al. (020)) follow the same training recipe (including data pre-processing) with the one proposed in (Chen et al., 2020). For Cora dataset, the number of layers and hidden dimensions are both 64, the dropout rate is 0.6, the weight decay of graph convolutional layers is 0.01, and the weight decay of the fully-connected layers at the beginning and the end is 5e-4, For Citeseer dataset, the number of layer is 32, the hidden dimensions is 256, the dropout rate is 0.7, and the weight decay setting is the same with the one for Cora dataset. For Pubmed dataset, the number of layers is 16, hidden dimension is 256, the dropout rate 0.7, the weight decay of all layers is 5e-4. Note that, the described in Eq. 6 sweeps from [0.1, 0.2, 0.5, 1.0, 2.0, 5.0, 10.0), and the best a for Cora, Citeseer, and Pubmed datasets are 10, 0.2, and 1.0, respectively.
D2-GCN models on oghg-molhiv, ogbn-arxiv, and oghn-proteins dataset. All the reported DC-GCN models on these datasets top of DeeperGCN models (Li al. 2020a) follow the same training recipe (including data pre-processing) as the one proposed in (Li et al. 2020a). For ogbg-molhiv dataset, the model (1) is built with the block type res+, the normalizatio type as BatchNorm, the number of layers as 7, the hidden dimension as 256, and the graph convolution aggregation type is softmaz; (2) is trained with the learning rate 0.0001 and the dropout rate as 0.2. For ogbn-arxiv dataset, the model (1) shares the same architecture configurations as the one for oghg-molhiv dataset except stacking for for 28 layers instead of 7 layers, decreasing the hidden di- mensions from 256 to 128, and using so at as the graph convolution aggregation type; (2) is trained with the learning rate as 0.001 and the dropout rate as 0.5. For ogbu- coootipoteins dataset, the model (1) is built with the block type rest, the normalizatio type as LayerNorm, the number of layers as 112, the hidden dimension as 64, and the graph convolution aggregation type is so ftmaz; (2) is trained with the learning rate 0.001 and the dropout rate as 0.1. Same with the setting in D2-GCN models on Cora, Citeseer and Pubmed datasets, the a described in Eq. sseepps from [0.1, 0.2, 0.5, 1.0, 2.0, 5.0, 10.0], and the best a for ogbg-molhiv, ogbn-arxiv, and are 1.0, 1.0, and 10.0, respectively.
datasets
14


Reviews:
[{"review_id": "YPGAL29oQ1y", "reviewer": "Reviewer_pLUm", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrength:\n\nThe writing is easy to understand and the idea is clearly presented. The experiment results show good empirical inference speed compared to the existing methods.\n\n\nWeakness&Advice:\n\n1. The description of “The inference process of one GCN layer can be viewed as two separated phases: Aggregation and Combination. …” for equation (1) is not precise. See page 52 in [1]. Instead of being viewed as two separated phases, “we no longer need to define an explicit update function, as the update is implicitly defined through the aggregation method”.\n\n2. “we hypothesize that explicit or implicit regularizations during GCN training can improve GCNs’ scalability towards going deeper,”  Randomly dropping being able to help with deeper GCN does not mean all regularization methods can. This hypothesis is over-claimed and groundless.\n\n3. What is the training speed of your model and the three-stage training pipeline compared to the existing methods?\n\n4. \"$L_{comp}$  is the computational cost determined by the decisions made by the gating functions” What does this sentence means? It’s better to write $\\mathcal{L}_{comp}$ in formula.\n\n5. What is the performance after each stage in your three-stage training pipeline. I would like to know which stage plays the most important role and how other stages improve the performance.\n\n6. Gating is not a new technique for GNNs, e.g. [2]. It’s better to draw the difference with these methods and emphasize the novelty and contribution of your method. Note that I will not consider it novel if you only put some existing tricks into your model.\n\nTypos:\nSection 3.2, 3rd paragraph, graphes —> graphs\n\nBit-wise skipping in figure 1, $x_2$ —> $x_1$\n\nIn equation (4), should use parenthesis after $\\odot$ to avoid confusion.\n\n[1] Hamilton WL. Graph representation learning. Synthesis Lectures on Artifical Intelligence and Machine Learning. 2020 Sep 15;14(3):1-59.\n\n[2] Li Y, Tarlow D, Brockschmidt M, Zemel R. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493. 2015 Nov 17.\n\n", "summary_of_the_paper": "The authors propose a Data-Dependent GCN framework D$^2$-GCN which integrates data-dependent node-wise, edge-wise and bit-wise skipping to save the cost for inference while does not sacrifice prediction accuracy.", "summary_of_the_review": "Some of the technical details need to be provided. The novelty need to be emphasized. I'll consider raise my score if my concerned can be properly addressed.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ELPn2TQIW1s", "reviewer": "Reviewer_AVzB", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n\n(1) This paper is well motivated. \n\n(2) The Introduction and Related works parts are well written.\n\n(3) Experiments on top of various SOTA GCNs and datasets validate the effectiveness and advantages of D$^2$-GCN.\n\n\nWeaknesses:\n\n(1) The paper has limited technique contributions. The problem of boosting the efficiency and scalability of GCNs has been fully studied by existing works. The ideas of *Node-wise skipping* and *Edge-wise skipping* are not novel enough. Please refer to the following references:\n\n- [KDD 2019] [Cluster-GCN] An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks\n- [ICCV 2019] [DeepGCNs] Can GCNs Go as Deep as CNNs\n- [ICLR 2016] [GGS-NNs] Gated Graph Sequence Neural Networks\n- [ICLR 2020] [DropEdge] Towards Deep Graph Convolutional Networks on Node Classification\n- [NIPS 2020] [DropNode] Graph Random Neural Networks for Semi-Supervised Learning on Graphs\n\n(2) The main contribution of this work is reducing the GCN inference cost. The data-dependent dynamic skipping strategies achieve this. I suggest the authors add theoretical complexity analysis comparison to better support this. \n\n(3) The skipping strategy are confusing: \n- the node-wise skipping parameter $G_l^n$ is 0 or 1. However, the authors claim $G_l^n \\in R^{N*1}$. The problems also exist for $G_l^b$ and $G_l^e$.\n- The gate function design part is important. However, the description is too brief. \n\n(4) In Eq.(6), $L_{comp}$ denotes the computational cost determined by the decisions made by the gating functions. The paper lacks a detailed calculation method.\n\n(5) This paper lacks hyperparameters experiments about trade-off parameter $\\alpha$, which can intuitively provide the trade-off between accuracy and efficiency.\n\n(6) The writing needs improvements. There are many typos and problems with the mathematical symbols, sentence structure, such as\n\n- The real number (M,N), vector ($G_l^n$) and matrix ($X$) are denoted as uppercase characters.\n- The sentence in the first paragraph of page 6 is too long and hard to read.\n- \"Specially, where $X_1$ ∼ $X_4$ are the 4 nodes in the graph.\"?\n- \"input images or graphes\"?\n", "summary_of_the_paper": "This paper proposes a Data-Dependent GCN framework (D$^2$-GCN) that integrates data-dependent dynamic skipping at multiple granularities. D$^2$-GCN is achieved by identifying the importance of node features via a low-cost indicator and thus is simple and generally applicable to various graph-based learning tasks. Experiments certify the effectiveness and efficiency of D$^2$-GCN. ", "summary_of_the_review": "Overall, this work is well motivated. However, the theoretical complexity analysis is missing and the methodology part remains confused. The technique contributions are limited.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6mF3Wr6ni3v", "reviewer": "Reviewer_u2pj", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I think D2-GCN is well-designed with simple components and the experimental results are impressive in that many recent graph data are at large-scale (especially, web data).\n\nThe authors focus on the efficiency of computation but I want to ask about the effectiveness of information processing.\n\n1. Authors argue that it can be helpful to alleviate the over-smoothing issue. It makes sense because three gating (or blocking) functions might prevent mixing node information. However, is there any experimental evidence (e.g. measurement of smoothness)?\n\n2. Can it be extended as (integrated with) a disentangled representation learning framework for GNNs? If so, could you briefly explain it? Because cutting connection and quantizing information seem like Disentangled GCN [1] in broad concept. I think it would be interesting to analyze which information is discarded or not.\n\n\nThe above questions are just for constructive discussion.\n\n\n[1] Disentangled Graph Convolutional Networks (ICML 2019)", "summary_of_the_paper": "In this work, the authors propose relatively low-cost GCNs in a data-dependent way.\n\nTheir framework has three main components: node-wise, edge-wise, and bit-wise skipping.\n\n1. Node-wise skipping is determined by a binary decision for each node based on its features.\n\n2. Edge-wise skipping is about the removal of connections between two nodes.\n\n3. Bit-wise skipping is about the quantization precision of aggregated node features.\n\n\nIt boosts efficiency while achieving comparable performance over benchmark datasets.", "summary_of_the_review": "I would recommend this paper to be accepted if other issues do not arise.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "2JPlqUFjyjO", "reviewer": "Reviewer_gZU6", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths:\n+ The paper is clearly written and easy to follow. \n+  Integrating node-wise skepping, edge-wise skipping, an bit-wise skipping  to reduce the nodes, prune the edges, and compress the bit-precision is interesting and somewhat novel.\n+ Experiments are extensive and promissing.\n\n\nWeaknesses: \n\n- In the discussion in Section 4.3 it is mentioned that \"our proposed D$^2$GCN can resolve the over-smoothing issue.\" The reviewer is quite interesting how the over-smoothing issue is resolved in the proposed D$^2$GCN. More discussions, empirical or theoretical analysis on this point is needed.\n- Furthermore, it is stated that  \"such data-dependent skipping techniques serve as a regularization effect\". It is appealing to mention of the regularization. However, the interpretation---\" since different components of a graph may work together or independently in an data-dependent manner to avoid the over-smoothing issue\" is disappointingly too vague. \nCould it possible to develop any theoretical analysis on the skipping techniques to verify whether it is equivalent to a special implicit regularization and, what kind of impilicit regularization?   Since that the idea of the paper is very simple, it would make the paper stronger if the theory behind could be developed. \n\n\nMinor issues:\nThere is a mistake in the subfigure of the right panel: $X_2 --> X_1$; \n", "summary_of_the_paper": "The paper  attempts to address the training efficiency and scalability of GCNs. To be specific, a so-called Data-Dependent dynamic GCN framework is proposed, in which node-wise skepping, edge-wise skipping, an bit-wise skipping are integrated via gate function to squeeze out (or reduce) the unimportant neighbor nodes in combinations, unimportant edge connections, and in the bit-precision, respectively. Extensive experiments are provided, showing new SOTA results on benchmark datasets. ", "summary_of_the_review": "While the paper is clearly written and the empirical evaluation is convincing, it is not clear why and how the over-smoothing issue could be resolved or what kind of equivalent regularization behind. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes Data-Dependent GCN (D2-GCN), which improves the efficiency of vanilla GCN by node-wise skipping, edgewise skipping, and bit-wise skipping. Gate functions are learned to prune the unimportant neighbor nodes in combinations, unimportant edge connections, and in the bit-precision. The proposed method boosts efficiency while achieving comparable performance over benchmark datasets. Most reviewers agree that the paper is well motivated, and the writing is clear. However, two of the reviewers found the novelty of the paper compared to previous work (for example, [1]) is limited. Three reviewers raised concerns about the lack of theoretical or empirical analysis on how D2-GCN can alleviate the over-smoothing problem, and how the proposed method can serve as an implicit regularization.

For the novelty concerns, the authors provided a detailed comparison with previous work during the rebuttal. For the lack of analysis on over-smoothing, the authors provided an additional empirical analysis using the distance of different intermediate layers’ output as the metric for measuring over-smoothing. But at least one reviewer is still not satisfied with those.

Given the current review scores (3, 5, 5, 6), the paper is below the acceptance threshold for the conference. The AC believes that the proposed method seems to be an effective and simple way towards more efficient graph neural networks and hence encourages the authors to submit the revised paper to another venue after addressing the reviewers’ concerns, especially on theoretical or empirical analysis on over-smoothing and implicit regularization.


[1]: Gated graph sequence neural networks
Decision: Reject