Title: CHORDAL-GCN: EXPLOITING SPARSITY IN TRAINING LARGE-SCALE GRAPH CONVOLUTIONAL NETWORKS

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.

1. INTRODUCTION:

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 The LCCs contain the majority of the graph, so deleting other nodes does not affect the overall arrow pattern. For simplicity, we treat them as undirected graphs here. Similar patterns are also observed in many other real-world networks (Dong et al., 2019) .

(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.

2. BACKGROUND AND RELATED WORK:



2.1. SEMI-SUPERVISED NODE CLASSIFICATION WITH GCNS:

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 x k ∈ R d , and all the feature vectors are stored in the rows of X ∈ R n×d . An L-layer graph convolutional network (GCN) (Kipf & Welling, 2017) has the layer-wise propagation rule: where W (l) ∈ R d l ×d l+1 is a weight matrix. The matrix Ā = D-1/2 Ã D-1/2 is the normalized adjacency matrix, where Ã = I + A and D ∈ R n×d is diagonal with Dii = j Ãij . The matrix H (l) ∈ R n×d l are the activations in the l-th layer (H (0) = X and d 0 = 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 γ,: , Āγγ ) is used to indicate the predicted label of node k, using the coefficient matrices W = (W (0) , . . . , W (L-1) ), the submatrix Āγγ , 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

H (l+1) = σ l ( ĀH (l) W (l) ),

EQUATION

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 Lovász convolutional network (Yadav et al., 2019) .

2.2. PRELIMINARIES ON CHORDAL GRAPHS:

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 v 0 and v k is a sequence of distinct vertices (v 0 , v 1 , v 2 , . . . , v k ) with {v i , v i+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 graph G = (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 + n i } with n i = |ν 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) .

3. CHORDAL-GCN:

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.

3.1. PREPROCESSING:

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.

3.2. CHORDAL-GCN: META ALGORITHM:

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,: , Āγiγi ) = k∈V l ∩γi 1 y true k , y pred k (•; X γi,: , Āγiγi ) ,

where X γi,: takes the rows of X indexed by γ i and Āγiγi is the submatrix of Ā with rows and columns indexed by γ i .

Algorithm 1 Chordal-GCN.

1: Input. A normalized adjacency matrix Ā, 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.,

L i (W ) = k∈V l ∩γi 1 y k , y pred k (W ; X γi,: , Āγiγi ) + j∈ch(i) k∈αj 2 y pred k (W ; X γi,: , Āγiγi ), y pred k

(W [t] ; X γj ,: , Āγjγj ) .

(2) 7:

Perform a gradient descent step W [t+1] = W [t] -η∇L i (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,: , Āγiγi ) using the current clique γ i is consistent with the previous prediction y pred k ( W ; X γj , Āγ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,: , Āγiγi ) = j∈ch(i) k∈αj 2 y pred k (•; X γi,: , Āγiγi ), y pred k ( W ; X γj ,: , Āγ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 ,: , Āγjγj ) is considered constant when we take the gradient of L cons . Therefore, when training the clique γ i , we compute the total loss

EQUATION

and perform a gradient descent step W + = W -η∇L i (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) .

3.2.1. CONNECTION TO THE ORIGINAL GCN:

We note that Algorithm 1 is essentially the mini-batch gradient descent method applied to the loss

EQUATION

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 Ā 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., d l = 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, c 1 is the maximum cluster size in Cluster-GCN while c 2 is the maximum clique size in our method. For memory complexity, Ld 2 is used to store the parameters {W (l) } L-1 l=0 and the other term is for storing embeddings {H (l) } L l=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 + Lnd 2 ) O(r L nd 2 ) O(Lrnd 2 ) O(L A 0d + (L + r L )nd 2 ) O(L A 0d + Lnd 2 ) O(L A 0d + Lnd 2 ) Memory O(Lnd + Ld 2 ) O(br L d + Ld 2 ) O(Lbrd + Ld 2 ) O(Lnd + Ld 2 ) O(Lc1d + Ld 2 ) O(Lc2d + Ld 2 )

3.2.2. TIME AND MEMORY EFFICIENCY:

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 ,: , Āγ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.

4. EXPERIMENTS:



4.1. EXPERIMENT SETTINGS:

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.

4.2. NUMERICAL RESULTS:

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. Preprocessing. In Chordal-GCN, we use the AMD ordering (Amestoy et al., 1996) implemented in the python package CVXOPT (Andersen et al., 2015) . The minimal chordal extension and the chordal decomposition are performed using the python package chompack (Andersen & Vandenberghe, 2015) . We also use the clique merging heuristic described in section 3.1. The threshold τ is different in different datasets, and mainly depends on the size of the graph. We report the parameters in Table 4 .

GCN structure. We implement our model with PyTorch. We use a two-layer GCN with fixed parameter size 128.

To calculate the meory usage, we use tf.contrib.memory BytesInUse() for TensorFlow and torch.cuda.memory allocated() for PyTorch.

B ADDITIONAL EXPERIMENTS 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 Chordal-GCN is applicable to training deeper GCNs. 

:



Figures and Tables:

Figure1: Adjacency matrices for the largest connected component (LCC) of cora (left), citeseer (middle), and pubmed (right). The LCCs contain the majority of the graph, so deleting other nodes does not affect the overall arrow pattern. For simplicity, we treat them as undirected graphs here. Similar patterns are also observed in many other real-world networks(Dong et al., 2019).

Figure 2: (a) An example of non-chordal graph. The edge {d, e} is a chord in the path (a, e, c, d). This graph is non-chordal because the cycle (a, b, d, c, a) is chordless. (b) An example of chordal graph. The path (b, a, c, d) is chordless. (c) A chordal graph with 17 vertices.

Figure 3: Left. The (symmetric) adjacency matrix of the graph G shown in Figure 2c. (For simplicity we only show the lower triangular part.) A bullet in the (i, j)th entry means nodes i and j are adjacent. The dashed lines separate the supernodes (clique residuals) in the clique tree. Right. The corresponding postordered clique tree T c . Every node in T c is a clique in G, and the red index i in every clique indicates the clique representative. The dashed box shows an example clique.

Figure 4: Validation accuracy of Chordal-GCN on the datasets: cora, citeseer, and pubmed. The blue curve shows the validation accuracy with the consistent loss L cons while the red curve shows that without L cons .

Figure 5: Memory (left) and time (right) versus number of GCN layers. Both curves scale linearly, which is promising and consistent with theoretical analysis.

Comparsion of Chordal-GCN with original GCN, GraphSAGE, FastGCN with uniform/importance sampling, VR-GCN, and Cluster-GCN. We report the micro F1 score (%), memory usage (MB), time per epoch (ms), and number of epoches. Only GCN and Chordal-GCN utilize the exact graph, while other baseline methods lose some graph structure information.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 Cluster-GCN (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 Chordal-GCN 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. 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.

Table content: <table><tr><td>Dataset</td><td>Method</td><td>F1 (%)</td><td>Mem. (MB)</td><td>Epoch time (ms)</td><td># epoches</td></tr><tr><td/><td>GraphSAGE</td><td>78.4</td><td>565.12</td><td>44.26</td><td>11</td></tr><tr><td/><td>FastGCN (uniform)</td><td>78.2</td><td>28.42</td><td>27.10</td><td>88</td></tr><tr><td>Cora (2708)</td><td>FastGCN (importance) VR-GCN Cluster-GCN</td><td>83.5 81.6 68.2</td><td>28.42 4.60 36.14</td><td>30.41 14.90 62.65</td><td>84 64 8</td></tr><tr><td/><td>GCN</td><td>78.4</td><td>20.23</td><td>5.35</td><td>119</td></tr><tr><td/><td>Chordal-GCN</td><td>81.2</td><td>5.69</td><td>90.90</td><td>49</td></tr><tr><td/><td>GraphSAGE</td><td>61.8</td><td>932.14</td><td>37.97</td><td>60</td></tr><tr><td/><td>FastGCN (uniform)</td><td>70.2</td><td>98.93</td><td>111.00</td><td>53</td></tr><tr><td>Citeseer (3327)</td><td>FastGCN (importance) VR-GCN Cluster-GCN</td><td>72.2 71.2 62.8</td><td>98.93 7.01 60.35</td><td>104.90 32.00 82.09</td><td>61 35 5</td></tr><tr><td/><td>GCN</td><td>70.5</td><td>52.16</td><td>6.42</td><td>95</td></tr><tr><td/><td>Chordal-GCN</td><td>74.1</td><td>8.47</td><td>38.91</td><td>57</td></tr><tr><td/><td>GraphSAGE</td><td>76.8</td><td>475.84</td><td>43.57</td><td>47</td></tr><tr><td/><td>FastGCN (uniform)</td><td>77.4</td><td>107.20</td><td>25.41</td><td>52</td></tr><tr><td>Pubmed (19717)</td><td>FastGCN (importance) VR-GCN Cluster-GCN</td><td>78.0 78.4 71.2</td><td>107.20 14.49 25.35</td><td>22.00 25.21 59.84</td><td>47 33 10</td></tr><tr><td/><td>GCN</td><td>78.0</td><td>66.03</td><td>7.52</td><td>109</td></tr><tr><td/><td>Chordal-GCN</td><td>80.2</td><td>15.37</td><td>55.94</td><td>83</td></tr><tr><td/><td>GraphSAGE</td><td>93.1</td><td>1192.00</td><td>185.22</td><td>62</td></tr><tr><td/><td>FastGCN (uniform)</td><td>92.9</td><td>1656.14</td><td>15.83</td><td>64</td></tr><tr><td>Reddit (232965)</td><td>FastGCN (importance) VR-GCN Cluster-GCN</td><td>93.0 93.2 96.1</td><td>1722.05 1054.21 231.32</td><td>21.60 5041.32 2407.61</td><td>31 32 43</td></tr><tr><td/><td>GCN</td><td>93.9</td><td>2992.12</td><td>261.81</td><td>190</td></tr><tr><td/><td>Chordal-GCN</td><td>94.2</td><td>2501.23</td><td>987.12</td><td>410</td></tr></table>

Peer review (iclr2020):
This paper leverages the clique tree decomposition of the graph and design a new variant of GCN which does graph convolution on each clique and penalize the inconsistent prediction made on separators of each node and its children. Experiments on citation networks and the reddit network show that the proposed method is efficient. Overall, this paper could be a significant contribution on improving GCN, with the caveat for some clarifications on the model and experiments. Given these clarifications in an author response, I would be willing to increase the score. Pros: 1, I like the idea of exploiting graph decomposition. In my opinion, it may not only improve the scalability but also help the model learn representations which better capture the structure or speed up the learning process. It would be great if authors could show some evidence along this line. 2, The examples in Figure 2 and 3 are very helpful in understanding the concepts related to the clique tree decomposition. 3, The summarization of time and memory complexity is very helpful in comparing different models. 4, I read the detailed questions and responses in the open review. It helps me understand more details about the experiments. Besides the typo of Table 2, I tend to believe that the experimental setup is reasonable and results are convincing although I did not run the code by myself. Cons & Questions: 1, The main motivation of exploiting the graph decomposition is to save memory such that GCN could be applied to large scale graphs without sacrificing the structural information. However, the scale of the largest experiments is still less impressive. To strengthen the paper, it would be great to try larger graph datasets which have been used in the literature. 2, I am confused by the writing on the final prediction made by the model. In particular, do you only keep the prediction of residual or do you average the predictions on the separators? It may be interesting to explore different ways of making predictions based on this decomposition based inference. In general, it would be great to separate the writing of loss (learning) and prediction (inference). 3, Why does Chordal-GCN take significant more epochs than GCN on Reddit and less epochs on all other datasets? Suggestion: 1, I think the clique tree is very similar if not the same with the junction tree given the node ordering (see section 2.5.2 of [1]). It would be great to discuss the relationship between your chordal graph representation and the tree decomposition used by the probabilistic inference algorithms of graphical models. From the perspective of complexity, the junction tree method and yours both highly depend on the tree-width. Also, linking to probabilistic inference could help better motivate the method since tree-based inference algorithm is shown to converge faster in the literature. 2, It would be great to discuss and or compare with [2] as it uses graph partition algorithms to get clusters and apply GNN with a propagation schedule which alternates between within-cluster and between-cluster. It is closely related to the chordal-GCN as it uses the decomposition of graph clustering directly rather than the clique tree. Decomposition like multiple overlapping spanning trees are also studied in [2]. [1] Wainwright, M.J. and Jordan, M.I., 2008. Graphical models, exponential families, and variational inference. Foundations and Trends® in Machine Learning, 1(1–2), pp.1-305. [2] Liao, R., Brockschmidt, M., Tarlow, D., Gaunt, A.L., Urtasun, R. and Zemel, R., 2018. Graph partition neural networks for semi-supervised classification. arXiv preprint arXiv:1803.06272. ====================================================================================================== Thank authors for the thorough reply! After I read authors* rebuttal and other reviewers* comments, I would like to keep my original rating. Again, I like this idea and believe better exploiting structure in the propagation could improve the inference in many ways. I hope authors could keep improving it, e.g., better motivating the proposed method (memory saving is just one angle which sometimes may need more engineering work to fully verify) and change the experiments accordingly.