LINGUINE: LearnIng to pruNe on subGraph convolUtIon NEtworks
Authors: Yihan He
Wei Cao
Shun Zheng
Zhifeng Gao
Jiang Bian
Venue:  (2021)
Keywords: Graph Neural Networks
Meta-Learning
Pruning

Abstract: Graph Convolutional Network (GCN) has become one of the most successful methods for graph representation learning. Training and evaluating GCNs on large graphs is challenging since full-batch GCNs have high overhead in memory and computation. In recent years, research communities have been developing stochastic sampling methods to handle large graphs when it is unreal to put the whole graph into a single batch. The performance of the model depends largely on the quality and size of subgraphs in the batch-training. Existing sampling approaches mostly focus on approximating the full-graph structure but care less about redundancy and randomness in sampling subgraphs. To address these issues and explore a better mechanism of producing high-quality subgraphs to train GCNs, we proposed the \texttt{Linguine} framework where we designed a meta-model to prune the subgraph smartly. To efficiently obtain the meta-model, we designed a joint training scenario with the idea of hardness based learning. The empirical study shows that our method could augment the accuracy of the current state-of-art and reduce the error incurred by the redundancies in the subgraph structure. We also explored the reasoning behind smart pruning via its visualization.

Under review as a conference paper at ICLR 2021
LINGUINE: LEARNING TO PRUNE ON SUBGRAPH CONVOL UTION NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Convolutional Network (GCN) has become one of the most successful methods for graph representation learning. Training and evaluating GCNs on large graphs challenging since full-batch GCNs have high overhead in mem- ory and computation. In recent years, research communities have been devel- oping stochastic sampling methods to handle large graphs when is unreal to put the whole graph into a single batch. The performance of the model depends largely on the quality and size of subgraphs in the batch-training. Existing sam- pling approaches mostly focus approximating the full-graph structure but care less about redundancy and randomness in sampling subgraphs. To address these issues and explore better mechanism of producing high-quality subgraphs train GCNs, we proposed the Linguine ne framework where we designed a meta- model prune the subgraph smartly. To efficiently obtain the meta-model, we designed a joint training scenario with the idea of hardness based learning. The empirical study shows that our method could augment the accuracy of the cur- rent state-of-art and reduce the error incurred by the redundancies in the subgraph structure. We also explored the reasoning behind smart pruning via its visualiza- tion.
INTRODUCTION
Graph Representation Learning has attracted much attention from the research communities re- cent years, with emerging new work every year. Graph Convolution Neural Networks (GCNs) were proposed as the extension of Convolutional Neural Networks(CNNg, (LeCun et al. 1995) on geo- metric data. The first spectral-basee GCN was designed on Spectral Graph Theory (Bruna al.,
2013) and was extended by many following works (Henaff et al. 2015: Defferrard et al. (016)) Over recent years, the spatial-based counterpart (Kipf & Welling (01 gained more attention and had facilitated many machine learning tasks (Wu et al.) 22220] Cai et al. 2018) including semi- supervised node classification (Hamilton et al., (017b), link prediction (Kipf & WWeling 201 Berg et al. 2017) and knowledge graphs (Schlichtkrull et al. 2018). In this work, primarily focused on large-scale spatial- spatial-based GCNs (Hamilton et al.] 201 Chen et al. 2018b) /Gai et al. 2018 Huang al. 2018 Zeng et al., 2019 Zou al. 2019 Chiang al. 2019), where given node aggregates hidden states from its neighbors in the previous layer, followed by a non-linear activation to obtain the topological representation.
However, as the graph gets larger, GNN models suffer from the challenges imposed by limited physical memory and exponentially growing computation overhead. Recent work adopted sampling methods to handle the large volume of data and facilitate batch training. The majority of them
types, layer-wise sampling (Hamilton al. 2017a Gao et al.) 2018 Huang et al., 2018; Zou et al.] (211)). node-wise sampling (Chen et al. 2018b) and subgraph sampling (Chiang et al. 2019 Zeng et al. 2019). In layer-wise sampling, we take samples from the neighbors of a given node in each layer. The number of nodes is growing exponentially
could be classified
the GCNs gets deeper, which resulted 'neighbor explosion". : In node-wise sampling, the nodes in each layer are sampled independently to form the structure of GCNs, which did avoid 'neighbor explosion'. But the GCN's structure is unstable and resulted in inferior convergence. In subgraph sampling, the GCNs trained on subgraph sampled on the original graph. The message was passed within the subgraph during training. This approach resolved the problem of neighbor explosion and can be applied to training deep GCNs. However, the subgraph's 's structure and connectivity had great

---

Under review as a conference paper at ICLR 2021
impact in the training phase. It might result in suboptimal performance and slow convergence if the subgraph is overly sparse (Chen et al., 2018b). Different sampling methods can make a huge difference in the final accuracy and the convergence speed shown in (Zeng et al. 2019). In the context of large-scale GCN training, the limitations in GPU memory makes the maximum batch size restricted. Research communities are actively seeking efficient sampling methods to deal with the challenges in scalability, accuracy, and computation complexity on large-scale GCNs.
The initiative of subgraph GCN is stochastic approach to approximate their full-graph counterparts. However, experiments showed that GCN trained with partial information can achieve even less bias. (Zou al. 2 This was even more so when variance reduction is applied in GCN's training, which overcomes the negative effect induced by subgraph GCNs and improves its convergence speed as well as inference performance. (Hamilton et al., 2017a Chen et al.) 2018a Zeng et al. 2019) However, the inner mechanism behind this random sample has yet to be studied.
GCNs are also made to be deeper and more complicated with architecture design. The model over- comes the drawbacks of the gradient vanishing problem via applying Deep CNN's residual/dense connection and dilated convolution, achieving state of art performance on open graph bench- marks. (Li et al., 2019; 2020; Weihua Hu 2020) However, as their model is significantly larger (amounting to more than 100 layers in some occasions) than previous approaches, the model suf- fered from high computation overhead and memory cost. With the model taking up much space, the batch sizes are also strictly limited. We aim to provide an easier solution to train complex models while maintaining relatively large receptive field in the graph, and keeping the training quality.
We propose L Linguine framework. In each forward pass, we 'smartly prune' inferior nodes to ex- tract concentrated smaller subgraph from the large subgraph randomly sampled previously. There- fore, we reduce the batch size and the memory requirement in training the model. We are also able to train the complex GCNs with larger receptive field and achieve better performance with the same budget. We parameterize the decision function in smart pruning with light-weight which is fed with the meta-information we obtained from training Eight--wiggt proxy model. This keeps the extra cost of algorithm under control. Our framework is built upon existing subgraph sampling methods and utilize joint training to learn the meta-model. Our meta-mode improved the quality of the subgraphs in training via actively dropping redundant nodes from its receptive field and concentrate the information.
meta-model,
We summarize the contributions of this work as follows:
1. We designed a new training framework Linguine which aims to train perforrefor GCNs on large graphs via model-parameterizae smart pruning techniques.
2. Linguine provides a joint-training algorithm called bootstrapping, originally designed train the meta-model in smart pruning, but also has a favorable impact in augmenting existing models and converge to better solutions with scalability and lower bias. It is also an effective algorithm inspired by the idea in the real-world learning process.
3. Empirical study justified that Linguim ne framework worked well on different scaled pub- lie benchmarks and compares favorably to previous methods.
4. We did analysis the mechanism behind smart- marrt-pruning via graph visualization.
2 RELATED WORK
Our framework was inspired and built upon two popular branches in Machine Learning.
Graph Neural Networks Many GNNs have emerged over the recent years. Spatial-bused GCNs are the most popular approaches among them and have gained broad interest from research com- munities (Atwood& & Towsley 2016 Niepert et al. 2016) Gilmer al., 2017). They stack multiple graph convolutional layers to extract high-level representations. In each layer, every node in the graph aggregates the hidden states from its neighbors on the previous layer. The final output is the embedding of each node in the graph. Existing work on GCNs utilized sampling technique to per- form efficient minibatch training. Common approaches can be categorized as Layer-wise Sampling, Node-wise Sampling and Subgraph Sampling. In Layer-wise sampling and Node-wise Sampling, the layers are sampled recursively from top to bottom to form mini-batches. The major difference between Node-wise Sampling and Layer-wise Sampling lied in the sampling mechanism.
2

---

Under review as a conference paper at ICLR 2021
Sample
Aggregate
Sample
Aggregate
Sample
Aggregate
(a)
(b)
(c)
Figure 1: Illustration of Subgraph GCN: (a) Layer-wise Sampling (b) Node-wise Sampling (c)
Subgraph Sampling
Node-wise Sampling sampled from the whole graph dataset whereas Layer-wise Sampling only fo- cused on the neighbors from the upper layer.
In Subgraph Sampling we only sample once and propagate through the subgraph to formalize batch training. Among work in Layer-wise Sampling, GraphSAGE (Hamilton al.) 2017a) performed uniform Node-wise Sampling on the neighbors of nodes in the previous layer. (Ying et al. 2018) introduced the importance score each neighbor and performed weighted aggregation enhance the model. The potential drawback of Layer-wis wise Sampling is Neighbor Explosion where we created an overly-large receptive field in the bottom layer and resulted memory overflow.
In Node-wise Sampling, FastGCN (Chen et al. 2018b) performs sampling independently across all layers and perform importance sampling on the node level reduce the variance. This approach was further extended by LADIES (Zou et al. 2019) which performs importance sampling adaptively from top to bottom.
Recently, Subgraph Sampling emerged as low complexity solution for large-scale GCN training. ClusterGCN (Chiang et al. (219) performs clustering on the graph. This work partitions the graph into densely connected clusters. Random sampling is performed on the cluster level to form mini- batches in training. GraphSAINT (Zeng et al. 2019) directly sampled the mini-hatches at node-level. This approach also performed normalization the node level reduce the sampling variance. It achieves the new state of the art performance on multiple public datasets. The main difference between Subgraph Sampling and other approaches is that GCN is trained on the subgraph instead of a massage passing flow containing different nodes on different layers.
Sampling subgraph has been important method leveraging limited memory achieve better performance, However, the variance introduced by sampling negatively impacts the training, Recent approaches adopted Variance Reduction (Hamilton al., 2017at Chen et al., 2018a| Zeng et al., 2019) to stochastically approximate the activations of sampled nodes. which was shown to boost the final model performance and convergence speed (Zeng et al. (019). Besides, empirical study found that different sampling methods can also create a great gap the final performance of GCNs and varied convergence speed.
The advance of deepening GCNs has drawn extensive attention in the research community, lever- aging the computation power of pigh-performance GPU devices. (Li et al. 2019) adapted residual connections and dilated convolutions into GCNs. (Li et al., (020) proposed a general aggregation function, which further improves the capacity deep GCNs.
Meta-Learning Our work is inspired by recent meta-learning and model-teaching approaches, which is also a trendy topic in recent years.
Learning to Learn, MetanLearning (Schmidhuber 1987 Thrun & Pratt 2012) proposed as an exploration using automatic learning via transferring knowledge learned from meta tasks. was designed two-level structure, in which the meta-level model evolves slowly and the task
3

---

Under review as a conference paper at ICLR 2021
model progresses quickly. Recently, meta-learning has been utilized in different machine learning scenarios. There is work trying to design optimizer and neural network architectures. (Andrychow- icz et al. 2016 Li & Malik 2016 Zoph & Le 2016). Other approaches similar to Meta-Learning
'Teaching (Anderson et al. 1985] Goldman & Kearns 1992). which can be categorized as machine- teaching and hardness based methods. Machine teaching (Zhul 2013) is construct minimal training set for the student model to learn a target model. However, due to the strong assumption of the oracle's existence in machine teaching. Hardness-basee models are proposed on the assump- tion that data order from easy to hard can benefit model training. There are many different works in the hardness-bart based method. Curriculum Learning (CL) (Bengio et al.) 2009; Spitkovsky et al.) 2010 Graves et al. 2017) utilizes hardness measure based on heuristic understanding of data. Self-paced learning(SPL), (Kumar et al. 2010) heuristically define the scheduling of training data in easy-to-hard manner. Learning to Teach (Fan et al. 2018) Wu et al. 2018 designed new teacher-student model and perform transferable model teaching.
Our meta-model incorporates graph topological information and node-wise performance informa- tion into meta information. We used a learned model instead of heuristic and fixed rules in the model to explore the optimal policy.
3 METHODS
In this section, we introduce the background of our problem, followed by the formal definition of Linguine framework.
3.1 PRELIMINARIES
A GCN learns representation of an un-directed, arributed graph G(V, 8) where each node E V has attribute F. TR. Let A be the adjacency matrix and A be the normalized (i.e., Á
D 1 AD-1, where D the diagonal degree matrix). The activation node v is x:( R
and the weight matrix is W Note that x. =x(") The rules of forward propogation per layer is defined as:
(1)
where A is the scalar element of Á. And a is the activation function.
The propogation of Subgraph GCN can be summarized as:
(1+1) a
Σ PEP
A r.u W (
(2)
A is the stochastic adjacency martix we sampled previously. where U and V are subspaces of hidden-state space of layer i and 1 + respectively. The &, is the l-layer embeddings of sampled nodes. As have been addressed previously on the 3 different types of subgraph GCNs, the main diference can be formally defined with A node-wise sampling, A., is stochastically sampled from A with [T] rows and V columns, where the number of nodes is not necessarily identical. In layer- sampling, the A_, is similar that in node-wise sampling where the cross-section of those rows and columns is 1. Meanwhile, the set U is subset of V, making Au,v surjective mapping. In subgraph sampling, the implied that the same adjacency matrix Ág in every layer. In this case, the mapping is isotonic, which keeps the network structure stable and facilitates the deepening of GCNs.
also a mapping in U -> V
and V are identical, which
The goal of training a Subgraph GCN is to perform batch training with each batch containing a subset of V and approximate the effect of training a full graph GCN.
The learning tasks can be categorized as inductive and transductive. In the inductive setting, we assume neither attributes connections of the test node be seen in the training phase whereas in the transductive setting we have access to them. The inductive model is much more challenging to train shown in (Hamilton al. 2017a) and has generalize to unseen graphs
4

---

end for Under review as a conference paper at ICLR 2021
Meta-Model
Training Subgraph GCN
Mota: Model
Subgraph GCN
(a) Bootstrapping
(b) Smart Pruning
Figure 2: Li Linguinn inguine Framework
3.2 LINGUINE FRAMEWORK
Linguine follows the design philosophy of utilizing a Meta-Model to optimize the training of subgraph GCNs. We divide the whole framework into 2 consecutive parts: Bootstrapping and Smart Pruning. In Bootstrapping we designed a joint training scenario detailed in 3.2.1 and algorithm .W also analyzed the convergence of under the convex scenario. In Smart Pruning designed algorithmmaand detailed the mechanism in 3.2.2
Our goals set follows: (1) Optimizing the subgraphs to minimize information loss and achieve better generalization. (2) Leveraging limited memory to achieve scalable learning (3) Utilizing the model feedback to optimize the training process.
Algorithm Bootstrapping
Input Full Graph G(V,E, X), hight-weight GCN Glight Output Learned Meta-Model M
1: Initialize meta-infon informattoo I(V). meta-model weight WM. Glight
2: for minibatch from to N do
3: Randomly Sample subgraph Gsampte(Vaame (Vaampte, Esamples X ssmmlte sample(())
4: Fed M with [V (Vaampte) and get pruning weight W
5: Normalize V and get !0
6: X sample = - C W
7: Fed Glight with Gsample and calculate task loss L
8: if i is even then
9:
Calculating WWanih
OL and update Glight
else
11:
Calculating 3W
a1 and update M
12: end if
Update I(Vaample)
14:
3.2. BOOTSTRAPPING
In algorithm the meta-model designed 2-layer vanilla GCN. The light-weight GCN (i.e. Glight) is used as proxy, escalating the training of meta-model. The meta-information (i.e. I(V)) includes 3 types of information from the model feedback: (Fan al., 2018): (1) Model information (i.e. average loss in the past epochs in training set, the loss oberserved so far on validation set ) (2) Node information (i.e. nodes' predicted labels) (3) Joint information (i.e. predicted class probabilities of Subgraph GCN in previous epochs)
The meta-model jointly trained with a lightweight GCN where the update of the meta-model and the light- GCN are trained alternately. The goal of bootstrapping is to obtain potent meta- model selective of existing subgraphs with the most informative nodes while weakening the redun- dant nodes. The light-wette weight design expedites the training process since it is audget-friendl] The sampling algorithm is defredef We use random- node subgraph sampling in our experiments, which is the simplest and most cost-effective.
5

---

Under review as a conference paper at ICLR 2021
Algorithm 2 Smart Pruning
Input Full Graph (VV,,, é, X), Meta-model M, Meta-informatiion I(V). Desired Subgraph Scale K Output High Performance GCN G
1: Initialize GCN weight We
2: for each minibatch do
3: Randomly sample subgraph Gisampte (Veemple Ssample: X sample) from G
4: Feed M with (( sVaampl) and obtain pruning score W
5: Select top-K K nodes in V and prune the rest, forming Gprune
6: Normalize top K score and drop the rest, getting Wtopk
7: X prune = =X prrnne + Wropk
8: Feed G with Gprune and calculate task loss
9: Backpropogate with at and update G
aWa
10: Update I(V
end for
Formally, the update of model weight of minibatch can be explicitly written as (For simplicity, we take fixed step vanilla gradient descent scenario):
t w = w - (L.
v/ as (W)
(4)
VG and Var Ms the partial gradients on GCN and meta-model respectively. Since the parameters of GCN and meta-model are independent of each other, formally, (VM, Va) = O.
We then provide a theorem on the convergence on this joint training scenario convex scenario and leave the proof in the appendix.
Theorem (Convergence of Joint Training) Suppose the function J R R is convex and differentiable, and that its gradient is Lipschitz continuous with constant > O. Then if we run gradient descent for k iterations with a fixed step size 17 I under the joint training theme, it will yield a solution f f(xlt) which satisfies:
fa:1)) - [(x)) 1|2
x= 11
(5)
nf
where f(x") ) is the optimal value. This means that joint training theme of convex function is guar- anteed to converge and it converges with rate O(L/t).
3.2.2 SMART PRUNING
In Smart Pruning, the meta-model is fixed and acts as scorer the previously sampled subgraph. We keep the nodes with top scores in the subgraph while pruning the rest before forwarding it to the target GCN. The meta-model is then acting like teacher akin to that of (Wu et al. 2018 Kumar
jet al. 2010), who selects the proper 'material' (e.g. subgraphs) for the student model (e.g. complex GCNs) learn. The meta-model is still fed with the meta-information from the student model alike Bootstrapping. This is akin to teachers getting feedback (i.e. what has been well received and what has not) from their students and adaptively changing the teaching contents for the next lecture in the real world. Since the full graph is overly large to digest by the student model, the meta- meta-model is also acting concentrator and enlarges the receptive field while keeping relatively small mini-batch size. This is done through dropping the redundant nodes from the existing subgraphs by pruning, our assumptions of redundancy are characterized as: (1) Nodes that are hard to learn by existing model (i.e. having high training loss) (2) Nodes that affect its neighbors' categorization. (i.e. nodes with high degree) These two assumptions have been discussed the experiment visualization at Appendix D
4 EXPERIMENTS
The purpose of our experiments is to answer the following questions: (1) How would bootstrap- ping algorithm compare with original methods? (2) How would graph sampling methods affect the

---

Under review as a conference paper at ICLR 2021
Datasets
PPI
Flickr
Reddit
Yelp
OGB-Product
Vanilla GCN
0.515(0.006)
0.492(0.003)
0,933
0.378(0.001)
0.756(0.002)
GraphSAGE
0.637(0.006)
0.501(0.013)
0,953(0.001)
0.634(0.006)
0.785(0.001)
FastGCN
0.513(0.032)
0.504(0.001)
0.924(0.001)
0.265(0.053)
ClusterGCN
0.875(0.004)
0.481(0.005)
0,954(0.001)
0.609(0.005)
0.790(0.003)
GraphSAINT-RN
0.960(0.001)
0.507(0.001)
0.962(0.001)
0.641(0.000)
0.781
GraphSAINT-RW
0.981)0.004)
0.511(0.001)
0.966(0.001)
0.653(0.003)
0.791(0.002)
DeepGCN
0.800(0.002)
RW + Bootstrapping
0.974(0.001) 0.517(0.002) 0.988(0.003))
0.680(0.004)
0.803(0.002)
RN Bootstrapping
0.980(0.004)
0.512(0.003)
0,970(0.003)
0.672(0.003)
0.790(0.002)
Table 1: F1-micro benchmark on node classification task
outcome of bootstrapping? (3) How many nodes should we prune to achieve commendable perfor- mance? (4) How does the pruning work?
We address the above problem by comparing the different algorithmic compositions of bootstrapping with the current state of arts well as the vertical comparison within the pruning algorithm. The code we implemented in Pytorch available online
4.1 DATASETS
PPI: Protein-protein interaction networks from ZZimik Leskoved 2017). Our goal is classi- fying protein functions based on the interactions between human tissue proteins. Flickr: Flickr dataset from (Zeng et al. 2019) We did categorization on the images based on the properties of online images. Reddit: Reddit dataset comes from (Hamilton et al.) (017a), containing Reddit posts collecting from different communities. We did prediction on the communities of online posts us- ing user comments. Yelp: Yelp dataset comes from (Zeng et al., 2019), containing relationships between custom reviewers, on which we did categorization of types of businesses with customer reviewers and their friendship. Open Graph Benchmarks: (OGB for short) is a diverse set of chal- lenging benchmark datasets (Weihua Hu 2020). We used Dgbn--rroteins where the major task is to categorize the protein based on the associations between different proteins. Ogbn-produccs comes from the Amazon product co-purchasing network. This dataset is also used in (Chiang et al.) 2019) but it is modified on the split ratio to produce a much more challenging task. We did a classification task on the products' category. Dataset statistics are in Table 2
4.2 BASELINES
We used normally trained large-scale GCN as baselines for comparison: Vanilla GCN
Kipf &
Welling 2016aa 6a) is the simplest peatial-based GCN. GraphSage (Hamilton et al. 2017a is typical layer-wise sampling method. FastGCN (Chen et al. 2018b) typical node sampling method.
ClusterGCN The first subgraph-sampling GCN algorithm. GraphSAINT (Zeng al. 2019 is another typical subgraph sampling method and the state of art method. DeepGCNs (Li et 2019 2020) deepens the GCNs and is by far the most parameterized GCN, which scales up to 8 to 10 times the parameter of previous GCNs in some cases with 10 times the layer of regular one. It is also straining the memory budget of GPUs and requires very high computation power with long convergence time.
4.3 RESULTS
Bootstrapping We examine the effect of doing joint training in the bootstrapping phase. Our im- plementation of GCN is a layer SageNet. Hamilton et al. (2017a) Random node(RN for short)

---

Under review as a conference paper at ICLR 2021
and random walk(RW for short) as sampling algorithm respectively. Our experiments show that the Bootstrapping algorithm can achieve state-of-art performance on public datasets. All baselines are reported at their best parameter settings 2-layer GCN as has been studied extensively in (Zeg et al. 2019). We also compared the influence of different batch sizes in Bootstrapping in the ap- pendix C The result shows that our joint training strategy has bigger improvement over existing methods on larger datasets. However, as has been discussed in 3.2.1 the joint training theme has lower convergence speed in experiments, roughly using 1.5 times the number of epochs to converge than the one trained directly, this can be partially justified in the theoretical results we give in the theorem
Smart Pruning We did experiments on (GB-Protein on a 24 layer DeepGCN backbone. The result is Figure 3 The implementation using 2-layer vanilla GCN as the gegh-weight proxy model in the algorithm 2 We adjust different batch sizes as well as pruning ratio and extensively studied the effect of smart pruning. We found that smart pruning could improve the generalization of complex GCN model when the batch sizes are limited and achieve commendable performance. One interesting symptom is that we achieve the best model performance when the pruning ratio around 0.8. We can achieve even performance with the original 0.5. This implies that we do not need the whole subgraph as the training set to achieve the optimal generalization. The pruning process removed some of the redundancies and helped the model to 'focus' on the key elements in the graph. However, when we continued to prune more nodes from the subgraph, the performance dropped. As the pruning ratio goes lower, more nodes are out of reach, which sparsifies the graph and caused bad generalization. We did an extensive visualization of the pruning process to explore the mechanism behind it. It shows that the first batch of nodes we pruned out are those with high loss and high degrees. These nodes are difficult for the model to learn since the background knowledge is over- complicated as their adjacent nodes might belong to totally different classes. Learning these nodes is also complicating the learning process. This explanation follows the idea that in the real world, the learning process is a hardness-basee process for human beings. We provide a more detailed analysis in the appendix D
300
(b)
(c)
Figure 3: (a) is the test result of OGB-Protein on smart pruning with different batch sizes and pruning ratio, we used two settings of bootstrapping/smart pruning batch sizes configuration. Means and standard deviation is reported accordingly. Experiments are based on 20 runs of the same algorithm with different initialization. training at 0.7 pruning ratio on Yelp dataset. Color bar is of loss scale. The original subgraph size is 1000.(c) The original subgraph is in (b)
(b) One visualization of the real-time pruned subgraph during
5 CONCLUSION AND FUTURE WORK
We have presented Linguine as a subgraph GCN training framework. Our design on bootstrap- ping and smart pruning algorithm improved the quality of GCN models. Extensive empirical study and visualization of the pruning procedure had justified the rationale of pruming subgraphs. Future directions included incorporating such mechanisms into designing better sampling methods in train- ing and the study of training GCNs with partial information from the original graphs to achieve better generalization and efficiency.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
John R Anderson, C Franklin Boyle, and Brian J Reiser. Intelligent tutoring systems. Science, 228
(4698):456-462 1985.
Marcin Andrychowicz, Misha Denil, Sergio Gomez, Matthew W Hoffman, David Pfau, Tom Schaul, Brendan Shillingford, and Nando De Freitas. Learning to learn by gradient descent by gradient descent. In Advances in neural information processing systems, pp. 3981-3989, 2016.
James Atwood and Don Towsley. Diffusion--oonvllutional neural networks. In Advances in neural information processing systems, pp. 1993-2001, 2016.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In Proceedings of the 26th anmual international conference machine learning, pp- 41 41-48, 2009.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv preprint arXiv:/706.022300 2017.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203. 2013.
Hongyun Cai, Vincent W Zheng, and Kevin embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering, 3009):1616-163) 2018.
Chang. A comprehensive survey of graph
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942-9500, 2018 8a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 201
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. 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.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in neural information processing systems, pp. 3844-3852, 2016.
Yang Fan, Fei Tian, Tao Qin. Xiang- Yang Li, and Tie- Yan Liu. Learning to teach. In International Conference on Learning Representations, 2018.
Hongyang Gao, Zhengyang Wang. and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1416-1424, 2018.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint arXiv: 2017.
Sally A Goldman and Michael Kearns. On the complexity of teaching. 1992.
Alex Graves, Mare G Bellemare, Jacob Menick, Rémi Munos, and Koray Kavukcuoglu. Automated curriculum learning for neural networks. In International Conference on Machine Learning, pp- 1311-1320 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances neural information processing systems, pp. 1024-1034, 20.
William I. Hamilton, Rex Ying, and Jure Leskovec. Representation learning graphs: Methods and applications. arXiv preprint 170900558..8 2017b.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint 1006v: 163, 2015.

---

Under review as a conference paper at ICLR 2021
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558 4567, 2018.
Thomas N Kipf and Max Welling. Semi-super classification with graph convolutional net- works. arXiv preprint 160,00609,,2207, 2016a.
Thomas N Kipf and Max Welling. arXiv:1611.07300, 2016b.
Variational graph auto-encoders.
arXiv preprint
M Pawan Kumar, Benjamin Packer, and Daphne Koller. Self-paced learning for latent variable models. In Advances in neural information processing systems, pp. 1 1189-1197, 2010.
Yann LeCun, Yoshua Bengio, et al. Convolutional networks for images, speech, and time series. The handbook of brain theory and neural networks, 3361(10):1995, 1995.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739 2020.
Ke Li and Jitendra Malik. Learning to optimize. arXiv preprint wrXivv1606.01885 2016.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In International conference on machine learning, pp. 2014-2023, 2016.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Jurgen Schmidhuber. Evolutionary principles in self-referential learning. On learning how to learn: The mela-mela-... hook.) Diploma thesis, Institul f. Informatik, Tech. Univ. Munich, 1(2), 1987.
Valentin Spitkovsky, Hiyan Alshawi, and Dan Jurafsky. From baby steps to leapfrog: How "less is more" in unsupervised dependency parsing. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, pp. 751-759, 2010.
Sebastian Thrun and Lorien Pratt. Learning to learn. Springer Science & Business Media, 2012.
Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta Jure Leskovec Weihua Hu, Matthias Fey. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00687 006807 2020.
Lijun Wu, Fei Tian, Yingce Xia, Yang Fan, Tao Qin, Lai Jian-Huang, and Tie- Yan Liu. Learning to teach with dynamic loss functions. In Advances in Neural Information Processing Systems, pp. 6466 6477, 2018.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
Rex Ying. Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 974 983, 2018
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In International Conference Learning Representations, 2019.
Jerry Zhu. Machine teaching for bayesian learners in the exponential family. In Advances Neural Information Processing Systems, pp. 1905-1913, 2013.
10

---

Under review as a conference paper at ICLR 2021
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. Bioinformatics, 33(14):110--1188 2017.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv: 1.01578, 2016.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 11249-11259, 2019.
A PROOF OF CONVERGENCE
We give a detailed proof of convergence on the joint training theme. We had the assumption that V is L-Smooth and (VD VM) = O which implies that V f and Vbf is Lipschitz continuous with constant L and = I and
(0)
In the joint training we can derive the bound of A++1 = f(x f(x'
f(x f(x)) v.f(z') (o ( x²)
_/2 "1x4t1 -2-1-=110
L
x'112
2
- V.ll 112 1/
2 [V(((=))1
Vvs(('') 113
(1)
where i M when odd and D when even.
follows that
|
x²11
1 x² - [Vif(() - v.f(2"))
1x" x² 112 27( x. - -
S | x= 112 21 | f(x') V
L
< 1x x 112 17 [vf((=)) V (x 1
| x= 112 172 (V.((())))
where M when odd and = when t is even. This followed by
|| - x 1| < | - - n7 V f
(2)
according to ①I.
Using Convexity and Cauchy-Schwarz inequality we obtain:
f(x') [xxx < V.f(=')T (x x0) S (x." M|al|=* x²112
(3)
It follows by
|V M VDf(<>>\ 2 ( f(xt)- f(x²)) )(x²)) 2 ((a))_((z") )(x²))
1|x* - xx l012
1|000 x0112 l|2
Setting A, = f(x²) f(x)) and combing the above bounds
13 3 yield
A,
S
10000 r
Dividing both sides by A,4441 and rearranging terms give
1
A
A
A
1l2
A+11
")
>
+
A
|,-00
x 1
A
1
x
112
11

---

Under review as a conference paper at ICLR 2021
Using the fact that f is decreasing every iteration, we have
1
npt
D
|
x
1/2
and
1100
x=
[(x²) - [(x))
S
17
claimed.
B DATASET STATISTICS
Datasets
Nodes
Edges
Feature
Classes
Class Type
Train/Val/Test
PPT
14,755
225,270
50
121
Multi
0.66/0.
Flickr
89,250
889,756
500
7
Single
0.50/0.25/0 25/0.25
Reddit
232,965
11,606,919
602
41
Single
0.66/0. 10/0.24
Yelp
716,847
6,977,410
300
100
Multi
0.75/0.10/0.0
ogbn-protein
132,534
39,561,255
112
Multi
0.65/0. 16/0.19
ogbn-product
2,449,029
61,859,140
100
47
Single
0.081/0.016/0.903
Table 2: Statistics for datasets
C HYPERPARAMETER EVALUATION
Since we found that batch size of subgraphs greatly determines the actual impacts the performance of GCNs, we explored the results trained with different batchsizes. This showcased it is important that we made the right choice on the batch sizes in training large graph GCNs.
Sampler
Batch Size
PPI
Yelp
Flickr
Reddit
2000
0.901
0.573
0.470
0.933
4000
0.942
0.587
0.485
0.954
6000
0.958
0.595
0.504
0.970
Random Node
8000
0.972
0.603
0.508
0.969
10000
0.980
0.648
0.512
12000
0.976
0.672
0.511
2000
0.934
0.584
0.496
0.962
4000
0.983
0.623
0.505
0.969
6000
0.962
0.642
0.506
0.974
Random Walk
8000
0.982
0.663
0,513
0.972
10000
0,988
0.647
0.517
12000
0.987
0.682
0.514
Table 3: Detailed Result of Bootstrapping on various batch sizes
D VISUALIZATION OF SUBGRAPHS IN TRAINING
We take the snapshots of subgraphs before and after smart pruning and visualized them together with the degree histogram as well as loss histograms in 9 We used batch size 1000 for clarity of figures and showcased the smart-pruned subgraphs at different levels pruning ratio and training epochs. The figure shows that our pruning method is especially good at selecting low-loss nodes during training and simplifying the graph structure. Also, as the training proceeds, the pruned graph became sparse with most low-loss nodes exists. The performance of GCNs the best in the ratio of 0.9 and 0.7 can also be attested in the visualization since we preserved most of the details in the graph and cut off nodes concentrating at 'high loss hull'. However, when the pruning ration
12

---

Under review as a conference paper at ICLR 2021
continues to go lower, where preserve less structure within the graph, the performance didn't t seem to improve anymore but drops monotonically. This can be caused by less information in the graph, many nodes are ignored in the training process. It is also surprising that we maintain more than 90% accuracy with only 30% nodes in the graph.
We can conclude that, since the model has strong tendency overfit at the verge of different classes, removing some training data through meta-learning could be an effective approach espe- cially in geometric deep learning, where the graph structure itself determines the network structure. We have seen work adding up more and more structure (more complicated aggregation functions, more layers ,etc) to achieve better model capacity on learning large graphs, however, this work addresses the problem from different direction, rather than adding up, we aim to remove the re- dundancies. the other hand, we also take the message that GCN itself might also be an over- parameterized on large graphs.
(a)l (original)
(.)
(c) 0.7
0.5 0.5
14
(e) 0.3
Figure Pruning example on 1000 node subgraph of Yelp training with different ratio epoch 100, color on loss scale
13

---

Under review as a conference paper at ICLR 2021
(a)l (original)
0.)
46
(c) 0.7
(d) 0.5
(e) 0.3
Figure 5: Pruning example on 1000 node subgraph of Yelp training with different ratio at epoch 500, color loss scale
14

---

Under review as a conference paper at ICLR 2021
(a)l (original)
0.)
46
(c) 0.7
(d) 0.5
(e) 0.3
Figure 6: Pruning example on 1000 node subgraph of Yelp training with different ratio at epoch 500, color loss scale
15

---

Under review as a conference paper at ICLR 2021
(a)l (original)
(b) 0.9
(c) 0.7
(d) 0.5
605
(e) 0.3
Figure 7: Pruning example on 1000 node subgraph of Yelp training with different ratio at epoch 700, color loss scale
16

---

Under review as a conference paper at ICLR 2021
Histogram
Original
Kato
kato du
Depres
(a) Epoch 100
(b) Epoch 300
Histogran
Histogram-27 700
Rarto
Hatoo
Harko dub
COARE
Degre
Degne
(c) Epoch 500
(d) Epoch 700
Loss mm00g
Loss Histogram-1100
Orignd
Orignal
Hakoo
180
Rorko Eub
Harto
COUFT
Depres
(c) Epoch 900
(f) Epoch 1100
Loss Mistogramm111 1.500
Loss Hatogram-1550
120
Deggral
kadoo
Ctrrt
35
6.0
(g) Epoch 1300
(h) Epoch 1500
Figure Loss Histogram of Flickr dataset at different epochs and pruning ratio
17

---

Under review as a conference paper at ICLR 2021
Histogram-100
Histogram-33
Original
karo dut
240
350
230
230
150
120
(a) Epoch 100
(b) Epoch 300
Histogram-500
Histggaa-700
Reroo
Hatoo
280
Kaboo dub
200
230
250
300
Degree
Degnes
(c) Epoch 500
(d) Epoch 700
Mettgram-770
Hsttggam-500
COART 350
330
Oriind
Orignal
Hako
300
500
Deprec
(c) Epoch 900
(f) Epoch 1100
Matogram-1100
Histggaam-330
Dig
Oegiial Ruaur
330
kado
Ctrrt
100
(g) Epoch 1300
(h) Epoch 1500
Figure 9: Degree Histogram of Flickr dataset different epochs and pruning ratio
18


Reviews:
[{"review_id": "hMTKSnhN4tB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "--------------\nSummary\n--------------\n\nThis paper proposes an approach to compute GNNs on pruned subgraphs. The authors use a \"meta-model\" to learn a good node pruning strategy during training. Then the meta-model is used to generate pruned subgraphs during inference. The proposed pruning algorithm can be applied to various graph samplers. The authors evaluate such pruning on two simple samplers, random node and random walk samplers.  Some theoretical analysis is performed. However, the analysis is not quite convincing. Evaluation on several graph benchmarks show that the proposed LINGUINE framework achieves good accuracy using pruned subgraphs. \n\n------\nPros\n------\n\n+ The paper is well-organized. Ideas are easy to follow. \n+ Accuracy on standard benchmarks is promising.\n+ Scalability of GNNs is an important topic. This paper performs meaningful exploration by trying to learn the pruning stategy.\n\n-------\nCons\n-------\n\n- The theoretical analysis (Theorem 1) seems problematic and not that useful. First of all, Theorem 1 relies on strong assumptions on the objective function (convex; L-Lipschitz), and Theorem 1 basically just tells the convergence rate of the (almost) standard GD algorithm. Conclusion from Theorem 1 neither gives new insights into the proposed optimization procedure (not much more than standard GD), nor guides us to design better algorithms. Secondly, the proof of Theorem 1 seems problematic: \n    * The first issue is that Theorem 1 talks about full-batch training, while the main algorithm of LINGUINE relies on random graph sampling. Theorem 1 should consider such stochasticity rather than completely ignoring it. I think due to the irregular graph structure, convergence analysis might be much harder than the current one presented with Theorem 1. Then, it would be valuable if we could get some insights into how the sampling algorithm and pruning could affect convergence. \n    * The second issue is that, even with the full-batch setting, the detailed proof in the Appendix doesn't seem correct (note, the equation indices under this bullet point refers to the equalities / inequalities in the Appendix rather than those in the main text). 1). How would the assumption that $D$ and $M$ being independent guarantee $\\langle\\nabla_D, \\nabla_M\\rangle=0$? I think $\\langle\\nabla_D, \\nabla_M\\rangle$ can be any value since $D$ and $M$ contain free parameters. Also, if $M$ and $D$ does not have the same amount of parameters, the dot product is invalid since $\\nabla_D$ and $\\nabla_M$ don't even have the same dimension. 2). Inequality 4 (following Eq. 3 rather than Eq. 2, typo in the paper) should be \"$\\leq$\" rather than \"$\\geq$\". This is a significant issue since the last inequality of 4 and all derivations following Inequality 4 may not hold. 3). There are multiple typos in the proof that sounds confusing. E.g., in between Eq. 1 and Eq. 2, $\\nabla f(x^t) - \\nabla f(x^*)$ should be $\\nabla_i f(x^t) - \\nabla_i f(x^*)$, and the norm should be L-2 norm rather than L-$x$ norm. Below Inequality 4, $\\Delta_t - \\Delta_t$ should be $\\Delta_t - \\Delta_{t+1}$. \n- Lacks justification on the proposed meta-model design / training. \n    * Why do we need to alternatively optimize $M$ and $G_{light}$ (Algorithm 1)? Since we are only performing one-step gradient descent on $G_{light}$ or $M$ in each training iteration, and the full model ($M$ + $G_{light}$) is end-to-end differentiable, I don't see the benefit of alternating weight update between $G_{light}$ and $M$. It seems you can simply update $G_{light}$ and $M$ in a single back-prop pass. Also, the proof of Theorem 1 still holds by removing the part of alternating update (in fact, removing alternating update may improve convergence).\n    * The connection to meta-learning is weak. It has been promoted as a main contribution that $M$ is derived from meta-learning. However, I find such connection a bit weak. I personally think $M$ as just an auxillary NN similar to that used by AS-GCN (Huang, 2018). There isn't really a \"teacher-student\" relationship. Arranging data from easy to hard is also missing in the design -- LINGUINE simply perform random sampling. Treating the pruning as a process of scheduling data from easy-to-hard seems to be a misuse of the meta-learning concept. In summary, I tend not to connect $M$ with meta-learning. $M$ is more like a sampling NN. \n    * Meta-model $M$ ignores subgraph structure completely. It is not justified why $M$ can learn a good pruning strategy. It seems that the input to $M$ is just node-level information. How can you prune subgraphs effectively without even considering the topology / structure of the subgraph?\n    * Can we really use $\\mathcal{W}$ to achieve good pruning? It is stated that during inference, pruning score $\\mathcal{W}$ is processed by top-k selection. I would imagine that a good model should try its best to reduce the information loss due to top-k selection. Then naturally, $M$ should output $\\mathcal{W}$ with many close-to-zero entries. However, there is no design in the training algorithm to encourage such close-to-zero behavior of $\\mathcal{W}$. If $\\mathcal{W}$ can freely take any value, the role of $\\mathcal{W}$ sounds just like node attention (similar to edge attention in GAT). Then I wonder if we can simply train a GAT and prune those edges with low attention values. How would LINGUINE compare to such pruning based GAT?\n    * Lacks information during inference. Algorithms 1 and 2 seem to imply that $M$ takes the same input as $I(\\mathcal{V})$. According to the first paragraph of Section 3.2.1, the information in $I(\\mathcal{V})$ seems to be only available during training (e.g., loss of previous epochs). How can you retrieve such $I(\\mathcal{V})$ during inference? \n- Lacks justification on the claims of \"scalability and lower bias\". Regarding scalability: from the sample size shown in the experiments, it seems that LINGUINE requires its subgraph sizes to be as large as those of the baselines, if not larger (e.g., 12000 nodes). Even though after pruning, the subgraph sizes can be smaller, $M$ still needs to process all the 12000 nodes in each subgraph. More importantly, in a 2-layer GCN, such subgraph size may even be larger than the full 2-hop neighborhood size. Then how would it help to alleviate neighbor explosion? Regarding bias, I didn't seem to find a discussion on why LINGUINE reduces biases. \n- Unclear experiment setup: there are some missing details about the GNN architecture (e.g., what are the hidden dimensions), and about the hyperparameter tuning procedure (i.e., the only hyperparameter available is the batch size listed in Table 3). Therefore, it may be hard to tell if the comparison is fair. \n\nMinor issues (e.g., typos):\n* Abstract: \"unreal\" should be \"non-realistic\"\n* Meta-learning paragraph in Section 2: incomplete sentence \"However, due to the strong assumption of the oracle's existence in machine learning. \"\n* Equations 3, 4 (in the main text) seem confusing. Should $w$ and $W$ come with subscripts? What's the difference between $w$ and $W$?\n* Multiple typos in the proof of Theorem 1 (see above). \n\n-----------------------------------\nRecommendation: Reject\n-----------------------------------\nIn summary, I think there are multiple major issues with the analysis and design choices, as detailed in the above \"Cons\" section. \n\n--------------\nQuestions\n--------------\n\nBelow is a summary of the questions raised in the \"Cons\" section. \n\n1. Please clarify the proof of Theorem 1.\n2. Please justify the design choices. i.e., alternativing optimization on $G_{light}$ and $M$; inputs to meta-model $M$; values of $\\mathcal{W}$.\n3. Please specify how to feed $I(\\mathcal{V})$ during inference.\n4. Please clarify the claims on scalability and biases. \n5. Please clarify the connection with meta-learning. \n6. Detailed experiment setup. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "eU6w_9at4K4", "reviewer": "AnonReviewer2", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "————————————————Summary————————————————\nThe author presented Linguine as a subgraph GCN training framework to train GCNs on large graphs. It includes bootstrapping and smart pruning algorithm to improve the quality of GCN models. In each forward pass, smart pruning algorithm prunes nodes to extract a concentrated smaller subgraph from the large subgraph randomly sampled previously. \n\n————————————————Strengths————————————————\n+ It is good to visualize the Pruning example.\n+ It is good to include rich baseline methods.\n+ well organization\n\n————————————————Weaknesses————————————————\n- I am not convinced regarding the nodes with high training loss as redundant nodes. From my understanding, redundant nodes mean the nodes carry redundant information. Apparently, nodes that are hard to learn by the existing models bring richer information rather than bring redundant information.\n- GCN prone to overfit the error (error with low degree can easily get low training loss), the proposed methods will aggravate the negative impact brought by the error.\n- From my point of view, the nodes with the highest degree are the most import node which affects message passing among nodes in the graph the most. However, it seems that smart pruning tends to prune these important nodes instead.\n\nQuestions:\nSince vanilla GCN is non-convex, I don’t see why we need the proof of the theorem on the convergence on joint training scenario in the convex scenario.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ss4jsSQpUxN", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes a new framework, called LINGUINE, to produce high-quality sub-graphs that can assist in effective training of graph convolutional networks (GCNs) with a lower computational cost. The framework uses two consecutive components - (1) Bootstrapping, which learns a meta-model that can assign weights to nodes by being jointly trained with a proxy ‘light’ GCN model (2) Smart pruning, which uses the learned meta-model to perform pruning on the large graph as the GCN model trains on it using the student-teacher learning concept. The paper presents results that the bootstrapping method improves the accuracy of smaller GCN models on large graph classification tasks. The smart pruning method removes nodes that are hard to learn or have a high degree of neighboring nodes in the subgraph, thus reducing error. \n\nStrengths: \n+ The idea of performing smarter subgraph selection via meta-learning is very interesting. Sub-graph selection is an important problem in the domain for training GCN models on large graphs \n+ The paper presents a theorem to show that under a convex setting, the proposed join training during bootstrapping is guaranteed to converge\n+ The benchmarking results illustrate that the bootstrapping step with a 2 layer SageNet architecture performs similar to the much bigger DeepGCN model on the OGBN-Product (Amazon product co-purchasing graph) dataset\n+ On the OBGN-protein dataset, the results demonstrate that the smart pruning step can improve model performance by selecting sub-graphs without nodes  that are hard to learn or have a high degree of neighboring nodes\nThe paper also presents visualizations and results on batch size effect and pruning ratios on the model performance\n\nWeaknesses:  \n+ My understanding from the method section is that LINGUINE is a framework that combines the meta-model learning and smart pruning to produce high-quality subgraphs that can be used to train a GCN effectively. However, the benchmarking results have been performed for the bootstrapping step only, instead of the whole framework. Since the output of this step (according to Algorithm 1) is meta-model, how are the F1-scores being reported in Table 1? \n+ What is the architecture of the light-weight GCN? How is it used in reporting the bootstrapping results?\n+ The paper states that the “sampling algorithm is user-defined”. Is this suggesting only a node sampling algorithm? Also, while it is mentioned that a random node algorithm is chosen, the results also have a random-walk algorithm. How do the two compare in terms of cost-effectiveness? Since one gives better performance of the other. \n+ The reasoning for missing DeepGCN F1-scores for 4 datasets is not provided.\n+ The paper describes results on the OBGN-protein dataset, for smart pruning. This is a different dataset from the ones for which the F1-score has been reported. The justification for this choice is missing. Similarly, the visualization results have been presented for Yelp data, and pruning ration graphs in the appendix for Flickr. These results should be presented consistently for one/multiple datasets. \n+ For a paper trying to solve the computational cost issue of training on large graphs, there are no results comparing the numbers related to memory or time for LINGUINE with other baselines. The discussion on such a tradeoff would be very useful to the end-user. \n+There are multiple typos and grammatical errors in the paper that would require thorough reading and revisions. \n\nMinor comments: \n- Figure 1 is not intuitive in demonstrating different sampling strategies\n- In Figure 2, the role of the light-weight Graph is missing\n- Is there a reason to choose accuracy instead of F1-score for Figure 3(a)\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "B3zVzSzkM5M", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "### Summary\n\nThe main idea of this paper is to improve the training of GCNs by smartly selecting subgraphs to train on in order to reduce memory consumption when running on large graph datasets. The proposed model consists of two stages:\n1) A bootstrapping stage. In this stage, a lighter-weight GCN and a meta-model are alternately trained. They use a 2-layer vanilla GCN to speed up training. The meta-model is fed in statistics from the training process, and is used to assign pruning weights to the nodes in a graph. For each iteration, a training graph is first randomly subsampled, then the meta model is used to smartly prune it further.\n2) A smart pruning stage. Now the meta-model is fixed, and a heavier-weight GCN is now trained on graphs that are pruned using the meta-model weights.\n\nThe model is evaluated on standard large datasets (Flickr, Reddit, Yelp, PPI), as well as the newer OGB-product and OGB-proteins datasets. Using random walk sampling as the base sampling algorithm, they achieve up to 1% absolute improvement over the baselines.\n\nThey also claim that redundant nodes will be removed by this process, and that nodes that have high training loss or that affect how their neighbors are classified (i.e. high-degree nodes) are more likely to be redundant. They then show an analysis on the OGB-proteins dataset to support this claim.\n\n### Recommendation / Justification\nThe results aren't bad, but the ideas in this paper aren't terribly novel, as there are already so many other node / subgraph sampling algorithms out there to scale GNNs, and I don't feel like this one contributes anything new to this area. Also the paper is lacking in analysis of why the method works or why it is justified, and I find the OGB-proteins dataset analysis at the end to be unconvincing.\n\n### Suggestions\nFor the pruning analysis, the pruned nodes plots, like Figure 3(b) and those in the appendix, are a bit hard to interpret. It might be better to show some histograms with the statistics of the pruned nodes vs those that end up in the final training graphs, as these would be easier to read.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an approach for training GCNs by learning to select subgraphs to train on to improve efficiency when transferring the model to larger graphs. In the proposed method, a meta-model and a light-weight GCN are trained iteratively in turns. Results are presented on medium-to-large graph datasets such as Reddit, Flickr, Yelp, PPI, and OGB-Product.

The reviewers agree that the method and the results are interesting, and that the topic addressed in the paper is important, but that the paper generally needs more work in terms of presentation, motivation, experimental evaluation, and theoretical analysis to meet the bar for acceptance, which the authors also acknowledge during their rebuttal. 
Decision: Reject