Year: 2019

Abstract:
Despite the impressive success of graph convolutional networks (GCNs) on numerous applications, training on large-scale sparse networks remains challenging. Current algorithms require large memory space for storing GCN outputs as well as all the intermediate embeddings. Besides, most of these algorithms involves either random sampling or an approximation of the adjacency matrix, which might unfortunately lose important structure information. In this paper, we propose Chordal-GCN for semi-supervised node classification. The proposed model utilizes the exact graph structure (i.e., without sampling or approximation), while requires limited memory resources compared with the original GCN. Moreover, it leverages the sparsity pattern as well as the clustering structure of the graph. The proposed model first decomposes a large-scale sparse network into several small dense subgraphs (called cliques), and constructs a clique tree. By traversing the tree, GCN training is performed clique by clique, and connections between cliques are exploited via the tree hierachy. Furthermore, we implement Chordal-GCN on large-scale datasets and demonstrate superior performance.

heading: 1 INTRODUCTION
text: Graph convolutional network (GCN) (Kipf & Welling, 2017) is a generalization of convolutional neural networks (CNNs) (LeCun & Bengio, 1998) to the graph structure. For a given node, the graph convolution operation aggregates the embeddings (features) of its neighbors, followed by a non-linear transformation. By stacking multiple graph convolutional layers, one can learn node representations by utilizing features of its distant neighborhood. The original GCN model, as well as its numerous variations, has shown great success in a variety of applications, including semisupervised node classification (Kipf & Welling, 2017), inductive node embedding (Hamilton et al., 2017), link prediction (van den Berg et al., 2017), and knowledge graphs (Schlichtkrull et al., 2018).
Despite the success of GCNs, training GCNs on large-scale graphs remains challenging due to the memory issue: we need to store all the parameters and outputs of GCN. Thus, the memory space scales linearly in the size of graph while quadratically in the feature dimension (Chiang et al., 2019; Zou et al., 2019). This prevents applications of GCN on many real-world networks, where the graphs usually contain millions or even billions of nodes.
Methods aimed at large-scale training have been proposed and can be roughly divided into two categories: (1) sampling-based methods and (2) clustering-based methods. For sampling-based methods, only a few neighbors for every node will be sampled in every GCN layer, and thus the size of intermediate embeddings for every layer will be reduced for each mini-batch. Works in this track include Hamilton et al. (2017); Chen et al. (2018a;b); Zou et al. (2019). However, ignorance of some neighbors might lose important structure information, which is the main drawback of all the sampling methods. Another direction of research notices the sparsity of real-world networks and exploits the clustering structure of the graph. For example, Cluster-GCN (Chiang et al., 2019) separates the graph into several clusters, and in every iteration of training, only one or a few clusters are picked to calculate the stochastic gradient for the mini-batch. However, Cluster-GCN ignores all the inter-cluster links, which are not negligible in many real-world networks. For example, Figure 1 shows the sparsity pattern of three citation networks. We first rearrange the vertices via an approximate minimum degree (AMD) ordering algorithm (Amestoy et al., 1996), and then observe a nice arrow pattern in the adjacency matrices. This indicates the existence of some highly-cited papers
(in the right bottom corner), which have impacts on multiple communities. In Cluster-GCN, these highly-cited papers are randomly put into one community and the adjacency matrix is approximated by a block-diagonal matrix; i.e., Cluster-GCN removes the fletching part of the arrow patterns in Figure 1. This approximation ruins the beautiful arrow pattern, and thus ignores the multi-community influence of some seminal papers.
The above difficulties can be easily tackled by the Chordal-GCN, a novel clustering-based method for the semi-supervised node classification task. Recall that Cluster-GCN ignores all the intercluster links and trains each cluster separately; comparatively, in Chordal-GCN, we keep all the links, train every cluster separately, and at the same time capture the connections between clusters by an additional loss term. This partially separable training process can be achieved with the help of chordal sparsity theory (Vandenberghe & Andersen, 2015): we first decompose a large-scale sparse graph into several small dense subgraphs, and we construct a tree of which the nodes are the subgraphs. Note that two subgraphs are adjacent in the tree if they share some vertices. In the training process, we traverse the tree from leaf to root; and when training on a certain subgraph, we minimize the usual GCN loss, plus an additional term called consistency loss. With the consistency loss, messages in the children subgraphs can be passed to their parent, and thus the relationship between subgraphs is leveraged via the hierarchy of the tree. Therefore, Chordal-GCN exploits the sparsity pattern as well as the clustering structure of the graph without any approximation or random sampling, while requires similar memory space to Cluster-GCN.
Our contribution is summarized as follows:
• We propose Chordal-GCN for semi-supervised node classification on large-scale sparse networks. The proposed model fully exploits the exact graph structure, while requires limited memory usage on large-scale graphs (much smaller than the original GCN).
• Chordal-GCN is able to train a large-scale graph in a partially separable manner; i.e., in every iteration, the training is performed on a subgraph, and the connections between subgraphs are handled by a consistency loss.
• We analyze the memory and time complexity of Chordal-GCN and compare them with other state-of-the-art GCN models. Also, we evaluate the performance of Chordal-GCN on benchmark datasets and demonstrate superior performance in large-scale datasets.

heading: 2 BACKGROUND AND RELATED WORK

heading: 2.1 SEMI-SUPERVISED NODE CLASSIFICATION WITH GCNS
text: Suppose G = (V,E) is an undirected graph with |V | = n and the n × n symmetric matrix A is the adjacency matrix. Every node k is associated with a feature vector xk ∈ Rd, and all the feature vectors are stored in the rows of X ∈ Rn×d. An L-layer graph convolutional network (GCN) (Kipf & Welling, 2017) has the layer-wise propagation rule:
H(l+1) = σl(ĀH (l)W (l)),
where W (l) ∈ Rdl×dl+1 is a weight matrix. The matrix Ā = D̃−1/2ÃD̃−1/2 is the normalized adjacency matrix, where Ã = I + A and D̃ ∈ Rn×d is diagonal with D̃ii = ∑ j Ãij . The matrix H(l) ∈ Rn×dl are the activations in the l-th layer (H(0) = X and d0 = d). The function σl is the activation function for layer l. The output of an L-layer GCN is an n × p matrix H(L), of which the k-th row is the predicted label for node k. Later in the paper, we will train GCN using only a subgraph G(γ), so the notation y〈pred〉k (W ;Xγ,:, Āγγ) is used to indicate the predicted label of node k, using the coefficient matrices W = (W (0), . . . ,W (L−1)), the submatrix Āγγ , and the corresponding feature vectors Xγ,:.
Semi-supervised node classification is a popular application of GCN. When applying GCN for this task, we minimize the loss function
L〈gcn〉(W ;X, Ā) = ∑ k∈V l `1 ( y 〈true〉 k , y 〈pred〉 k (W ;X, Ā) ) , (1)
to learn the weight matrices W = (W (0), . . . ,W (L−1)). In the formula, y〈true〉k is the given true label for node k, and V l ⊆ V is the subset of vertices with given true labels. The function `1(·, ·) is a loss function, and usually it is the cross entropy loss.
Much work has been done to apply GCN on large-scale datasets. For the sampling-based methods, different rules for random selection have been proposed: uniform sampling as in Hamilton et al. (2017), or importance sampling in Chen et al. (2018a). On the other hand, clustering-based methods become more interesting in the recent literature. Besides Cluster-GCN (Chiang et al., 2019), Graph Partition Neural Network (GPNN) Liao et al. (2018) also partitions the entire graph into small clusters, and the GCN model alternatively propogates within-cluster and between-cluster. In addition, clustering structure can also be utilized implicitly as a low-rank approximation of the graph Laplacian. This idea is exploited in LanczosNet (Liao et al., 2019) as well as the Lovász convolutional network (Yadav et al., 2019).

heading: 2.2 PRELIMINARIES ON CHORDAL GRAPHS
text: Chordal sparsity has been a classical topic in graph theory and found useful applications in various fields, including database theory (Beeri et al., 1983), probabilistic networks (Pearl, 1988; Cowell et al., 1999; Darwiche, 2009), linear algebra (Rose, 1970), combinatorial optimization (Golumbic, 2004; Gavril, 1972), semidefinite optimization (Andersen et al., 2010; 2013). In this paper, we will use chordal sparsity theory to exploit the clustering structure. So now we show that a chordal graph can be separated into cliques, and that these cliques form a clique tree with desirable properties.
Ordered undirected graph. Given an undirected graph G = (V,E) with |V | = n, we can order the vertices from 1 to n, and then we refer to a vertex in V by its order i ∈ [n] = {1, 2, . . . , n}. In addition, an index set γ ⊂ [n] represents a subset of vertices in V .
Cliques. A complete graph is a graph in which every pair of distinct vertices is adjacent. A clique γ ⊆ V of a graph G is a subset of vertices that induces a maximal complete subgraph. The graph induced by γ is denoted G(γ) = (γ,E(γ)) and has edge set E(γ) = {{v, w} ∈ E | v, w ∈ γ}.
Chordal graph. A path between v0 and vk is a sequence of distinct vertices (v0, v1, v2, . . . , vk) with {vi, vi+1} ∈ E for i = 0, 1, . . . , k − 1. For example, the graph in Figure 2a has a path (a, e, c, d). A chord in a path of an undirected graph is an edge between non-consecutive vertices on the path. For example, in Figure 2a, the edge {d, e} is a chord in the path (a, e, c, d), but in Figure 2b, the path (b, a, c, d) is chordless. An undirected graph is chordal if every cycle of length greater than three has a chord. Figure 2b and 2c show two examples of chordal graphs, while the graph in Figure 2a is non-choral.
Postordered clique tree. Given a (connected) chordal graphG = (V,E), we can always construct a clique tree T c: the nodes of T c are the cliques γ ⊆ V and two cliques are adjacent in T c if they share some vertices in V . In addition, we can arbitrarily pick a clique as the root of the tree, and then every non-rooted clique can be partitioned into clique separators and clique residuals. The clique separator is the intersection of the clique with its parent clique in T c. The clique residual is also called the (maximal) supernode, and by definition, all the supernodes form a partition of V .
More interestingly, we can always find an ordering of vertices V so that the clique tree T c satisfies the following properties.
1. The higher neighborhood of every vertex is complete: j, k ∈ adj+(i) implies {j, k} ∈ E, where the higher neighborhood of vertex i is defined as adj+(i) = {j | {i, j} ∈ E, j > i}. This means that every clique and supernode in T c can be written as γi and νi, respectively, where i ∈ V has the lowest order in the clique (and supernode). We denote by i the representative of the supernode νi, by αi = γi\νi the corresponding clique separator, and by V c the set of all representatives. The index set αi is empty if i is the root of T c.
2. The elements of each supernode are numbered consecutively: νi = {i, i + 1, . . . , i + ni} with ni = |νi − 1|.
3. All the representatives i ∈ V c are topologically ordered: i < p(i) if i ∈ V c and p(i) is the representative of the parent of γi in T c.
An ordering satisfying the above three properties is called topological postordering, and a clique tree T c with certain topological postordering is referred to as a postordered clique tree. Figure 3
shows a supernode partition of the chordal graph in Figure 2c with a topological postordering. (This example is adapted from the survey paper Vandenberghe & Andersen (2015).) In this example,
γ5 = {5, 6, 7, 8, 10}, ν5 = {5, 6, 7}, α5 = {8, 10}.
Given a chordal sparsity graph G = (V,E), there exist efficient algorithms (in O(|E|)) to find a topological postordering, and to generate a postordered clique tree T c together with the parent function p(i) and all the index sets (i.e., γi, νi, and αi for all i ∈ V c) (Lewis et al., 1989; Pothen & Sun, 1990). The whole process is called chordal decomposition (Vandenberghe & Andersen, 2015).

heading: 3 CHORDAL-GCN
text: Now we are ready to utilize the chordal decomposition technique in training large-scale sparse networks. We note that most real-world networks are indeed sparse, but not chordal. So we first introduce some data preprocessing steps, followed by the detailed description of Chordal-GCN. We also analyze the time and memory complexity of our model, and compare it with other GCN models.

heading: 3.1 PREPROCESSING
text: Reordering and chordal extension. Chordal extension describes the idea of transforming a nonchordal graph G = (V,E) into a chordal graph G′ = (V,E′) by adding edges, i.e., E ⊆ E′. Unfortunately, to find the minimum fill-in is claimed to be an NP-complete problem (Rose et al., 1976; Yannakakis, 1981), and is not always desirable due to algorithm complexity. However, given an ordering of vertices, it is practical to find a minimal chordal extension (Ohtsuki, 1976; Rose, 1974). (It is called minimal if the removal of any added edge results in a non-chordal graph.) That is to say, every minimal chordal extension is associated with certain vertex ordering. Thus, the reordering of vertices is important, especially when we prefer a sparse extended graph. So in this work, we use an approximate minimum degree (AMD) ordering algorithm (Amestoy et al., 1996) to first reorder the vertices, and then find a minimal chordal extension.
Clique merging. Often, the resulting extension contains many small cliques and it would be more efficient to merge some neighboring cliques, as reported in Ashcraft & Grimes (1989). In this work, traversing the tree from leaf to root, we greedily merge clique γi with its parent γp(i) if |νi| ≤ τ and |νp(i)| ≤ τ where τ is a pre-defined threshold. We denote the resulting graph as G′′ = (V,E′′).
Chordal decomposition. Given the graph G′′, we can now construct the postordered clique tree T c (together with all the index sets (γi, νi, and αi), and the parent function p(i)). With a little abuse of notation, we also use T c to indicate the postordered clique tree of G. In other words, the preprocessing steps reorder and partition the vertex set V , which helps us identify the clique γi and the corresponding induced subgraph G(γi). Although chordal extension and clique merging add edges into the graph, it will not affect the training process of GCN because we will use the subgraph G(γi), not G′′(γi).
Lastly, we emphasize that, although G(γi) no longer represents a complete subgraph, we still refer to γi as clique to distinguish from clusters or communities: in the chordal decomposition, one node k ∈ V is allowed to exist in multiple cliques while in community detection or graph clustering, one node appears in only one cluster.

heading: 3.2 CHORDAL-GCN: META ALGORITHM
text: With the postordered clique tree T c in hand, we are able to train a large-scale sparse graph in a partially separable manner, i.e., clique by clique. Suppose we traverse the tree T c in the topological order, i.e., from leaf to root. At clique γi, the loss function consists of two parts. The first part is the usual GCN loss defined in (1), but using only the induced subgraph G(γi) instead of the entire G:
L〈gcn〉(·;Xγi,:, Āγiγi) = ∑
k∈V l∩γi
`1 ( y 〈true〉 k , y 〈pred〉 k (·;Xγi,:, Āγiγi) ) ,
where Xγi,: takes the rows of X indexed by γi and Āγiγi is the submatrix of Ā with rows and columns indexed by γi.
Algorithm 1 Chordal-GCN. 1: Input. A normalized adjacency matrix Ā, a postordered clique tree T c, feature matrix X , and
true labels y〈pred〉k for k ∈ V l. 2: Output. The coefficient matrices W = (W (0), . . . ,W (L−1)). 3: Randomly initialize W [0]. 4: for t = 0, 1, 2, . . . do 5: for i ∈ V c in topological order do 6: Compute the loss by (4), i.e.,
Li(W ) = ∑
k∈V l∩γi
`1 ( yk, y 〈pred〉 k (W ;Xγi,:, Āγiγi) ) + ∑
j∈ch(i) ∑ k∈αj `2 ( y 〈pred〉 k (W ;Xγi,:, Āγiγi), y 〈pred〉 k (W [t];Xγj ,:, Āγjγj ) ) .
(2)
7: Perform a gradient descent step W [t+1] = W [t] − η∇Li(W [t]). 8: end for 9: end for
The second part of the loss is the consistency loss. When we arrive at clique γi, we have traversed all its children in the tree T c. This means that some nodes in γi have already been visited; namely, those clique separators of γi’s children in T c. For clarity, we denote by ch(i) the set of children representatives of γi; i.e., j ∈ ch(i) if j is a representative (i.e., j ∈ V c) and γj is a child of γi in T c. Then all the nodes in αj for j ∈ ch(i) have already been visited when we arrive at γi. Thereby, for k ∈ αj and j ∈ ch(i), we hope that the predicted label y〈pred〉k (·;Xγi,:, Āγiγi) using the current clique γi is consistent with the previous prediction y 〈pred〉 k (W̃ ;Xγj , Āγjγj ) using clique γj and the most recent parameter W̃ . Hence, the consistency loss for training clique γi can be formulated as
L〈cons〉(·;Xγi,:, Āγiγi) = ∑
j∈ch(i) ∑ k∈αj `2 ( y 〈pred〉 k (·;Xγi,:, Āγiγi), y 〈pred〉 k (W̃ ;Xγj ,:, Āγjγj ) ) , (3)
where `2(·, ·) is a loss function, for example, the KL divergence. Note that W̃ is not treated as the variable of L〈cons〉; i.e., the term y〈pred〉k (W̃ ;Xγj ,:, Āγjγj ) is considered constant when we take the gradient of L〈cons〉. Therefore, when training the clique γi, we compute the total loss
Li(·) = L〈gcn〉(·;Xγi,:, Āγiγi) + L〈cons〉(·;Xγi,:, Āγiγi), (4)
and perform a gradient descent step W+ = W − η∇Li(W ) where η is the learning rate. The whole algorithm is summarized in Algorithm 1. Note that the gradient descent step in line 7 of Algorithm 1 can be replaced with any other accelerated version, for example, Adam (Kingma & Ba, 2015).

heading: 3.2.1 CONNECTION TO THE ORIGINAL GCN
text: We note that Algorithm 1 is essentially the mini-batch gradient descent method applied to the loss L〈cgcn〉(W ) = ∑ i∈V c Li(W ) (5)
with γi taken as the mini-batch. Clearly, it is equal to the original GCN loss (1) if we have only one clique (i.e., V c = {1} and thus γ1 = V ). Also, when Ā is block diagonal, Chordal-GCN is equivalent to Cluster-GCN because the consistent loss (3) vanishes.
However, in the general case, without any assumption on the graph structure or the GCN structure, it is impossible to show the equivalence between Chordal-GCN and GCN. From another view of point, the non-convex functions (1) and (5) don’t share any global minimizer. For example, consider the chordal graph with two overlapping dense principal submatrices. We can easily choose the set of true labels y〈true〉 such that (1) and (5) don’t have the same minimizer.
Table 1: Time and memory complexity of GCN training algorithms. L is the number of layers, n is the number of nodes, ‖A‖0 is the number of nonzeros in the adjacency matrix A, and d is the number of features. For simplicity we assume the number of features is fixed for all layers, i.e., dl = d for l = 1, 2, . . . , L. For SGD-based methods, b is the batch size and r is the number of sampled neighbors per node. Also, c1 is the maximum cluster size in Cluster-GCN while c2 is the maximum clique size in our method. For memory complexity, Ld2 is used to store the parameters {W (l)}L−1l=0 and the other term is for storing embeddings {H(l)}Ll=1. For simplicity we omit the memory for storing the graph or subgraphs since they are fixed and usually not the main bottleneck.
Complexity GCN(Kipf & Welling, 2017) GraphSAGE (Hamilton et al., 2017) FastGCN (Chen et al., 2018a) VR-GCN (Chen et al., 2018b) Cluster-GCN (Chiang et al., 2019) Chordal-GCN
Time O(L‖A‖0d+ Lnd2) O(rLnd2) O(Lrnd2) O(L‖A‖0d+ (L+ rL)nd2) O(L‖A‖0d+ Lnd2) O(L‖A‖0d+ Lnd2) Memory O(Lnd+ Ld2) O(brLd+ Ld2) O(Lbrd+ Ld2) O(Lnd+ Ld2) O(Lc1d+ Ld2) O(Lc2d+ Ld2)

heading: 3.2.2 TIME AND MEMORY EFFICIENCY
text: Following Chiang et al. (2019), we report the time and memory complexity in Table 1. Although our method has the same time complexity as Cluster-GCN in big-O notation, Chordal-GCN needs an extra forward propagation on the children cliques in order to compute the predicted labels y 〈pred〉 k (W
[t];Xγj ,:, Āγjγj ) in (2). The extra forward propagation step would be the only price paid for single node being in multiple subgraphs. As we will see in the numerical experiments, this additional cost is minimal and worthwhile, especially in citation networks with an arrow pattern.
In addition, the memory bottleneck for Chordal-GCN and Cluster-GCN depend on the maximum cluster size and maximum clique size, respectively. Since these two numbers depend totally on the hyperparameters, i.e., number of clusters in METIS algorithm and the merging threshold τ , it is difficult to compare analytically. But both are much smaller than the memory usage of the original GCN, which is desirable.

heading: 4 EXPERIMENTS

heading: 4.1 EXPERIMENT SETTINGS
text: We evaluate our proposed model for the semi-supervised node classification task on four public datasets: cora, citeseer, pubmed, and reddit. We compare Chordal-GCN with the following stateof-the-art GCN training algorithms for comparison: GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), FastGCN (both uniform and importance sampling) (Chen et al., 2018a), VR-GCN (Chen et al., 2018b), and Cluster-GCN (Chiang et al., 2019). For all the methods we use the same GCN structure (i.e., L = 2), the same label rate, and Adam optimizer (Kingma & Ba, 2015) with learning rate 0.001, dropout rate as 20%, weight decay as zero. For the baselines, we use the implementations provided by the authors, and follow the default parameter settings in these models. Other implementation details are included in appendix A.
For all the methods and datasets, we conduct training for 10 times and take the mean of the evaluation results. Also, we stop training when the validation accuracy does not increase a threshold (0.01) for 10 epoches, and choose the model with the highest validation accuracy as convergent point. We use the following metrics to evaluate the performance of all methods.
• Accuracy: The micro F1 score of the test data at the convergent point. • Memory usage: The maximum GPU memory occupied by tensors. • Epoch time and number of epoches: Time to run an epoch and total number of epoches
before convergence. Note that in Chordal-GCN, an epoch is a traverse of the clique tree, rather than one clique.

heading: 4.2 NUMERICAL RESULTS
text: We summarize all the results in Table 2. In the three citation networks (cora, citeseer, and pubmed), Chordal-GCN achieves the highest accuracy among all baseline models. This desirable result is due to the exploitation of the exact sparsity pattern and clustering structure.
In terms of memory space, Chordal-GCN is superior to the original GCN, just as expected. All the sampling-based methods require limited memory space because they reduce the number of intermediate node embeddings. More interestingly, Chordal-GCN uses less memory space than ClusterGCN (except in reddit). This is because the Cluster-GCN implementation uses a few clusters in one epoch, and thus the memory bottleneck depends on the sum of the selected clusters, rather than the maximum cluster. The abnormal memory cost of Chordal-GCN in reddit dataset is attributed to our clique merging heuristic. The maximal clique in reddit has size 220, 069, almost 95% of the vertices. Splitting the graph into more cliques will help reduce the memory requirement, while increases the epoch time: we train smaller but more cliques in one epoch.
Lastly, we emphasize that the comparison of epoch time can never be fair: one epoch in ChordalGCN means one traverse of the clique tree while in other methods one epoch is one mini-batch. This explains the long epoch time of Chordal-GCN.

heading: 5 CONCLUSION
text: We propose Chordal-GCN for semi-supervised node classification on large-scale sparse networks. The proposed model exploits the sparsity pattern and clustering structure of the graph, and utilizes the exact graph structure (i.e., without sampling or approximation). Moreover, the memory usage
of Chordal-GCN is limited because the training is performed in a partially separable manner; i.e., clique by clique. Experiment results demonstrate that Chordal-GCN achieves the best test accuracy with much smaller memory cost on benchmark datasets.

heading: B ADDITIONAL EXPERIMENTS
text: B.1 ABLATION STUDY
We evaluate the contribution of the consistency loss L〈cons〉 (3) here. We train Chordal-GCN with and without L〈cons〉 on the cora, citeseer, and pubmed datasets, and plot the validation accuracy versus the number of epoches. Figure 4 shows that the consistency loss L〈cons〉 correctly captures the connection between cliques, and that improve the performance of Chordal-GCN. This explains why our model performs consistently better than Cluster-GCN: Cluster-GCN ignores those intercluster links and thus loses the connections between clusters. In the pubmed dataset, Chordal-GCN without consistency loss is even overfitting: the validation accuracy decreases after several epoches.
B.2 TRAINING DEEP GCNS
In this section, we study the performance of deeper Chordal-GCN, and explore how time and memory cost scales with GCN depth. As shown in Figure 5, both memory and time cost scale linearly with the number of layers. This result is consistent with theoretical analysis, and shows that ChordalGCN is applicable to training deeper GCNs.

Review summaries:
In this paper, the authors propose a new method referred to Chordal-GCN to optimize memory usage in large graphs. The authors borrow the ideas from Chordal Sparsity theory to first build a client tree. Then mini-batch updates are carried out individually on each clique from the leaves following the GCN loss. The authors add an additional consistency loss between shared node with children cliques. Experiments are carried out in four networks with comparison to several baselines.