Chordal-GCN: Exploiting sparsity in training large-scale graph convolutional networks
Authors: Xin Jiang*
Kewei Cheng*
Song Jiang*
Yizhou Sun
Venue:  (2020)
Keywords: graph convolutional network
semi-supervised learning

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 hierarchy. Furthermore, we implement Chordal-GCN on large-scale datasets and demonstrate superior performance.


Under review as a conference paper at ICLR 2020
CHORDAL-GCN: EXPLOITING SPARSITY IN TRAINING LARGE-SCALE GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Despite the impressive success of graph convolutional networks (GCNs) on nu- merous applications, training on sarge-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 ei- ther random sampling unfortunately lose important structure information. this paper, we propose Chordal-GCh for semi-supervised node classification. The proposed model uti- lizes 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 clique tree. By traversing the tree, GCN training 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.
approximation of the adjacency matrix, which might
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 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 variety of applications, including semi- supervised 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: 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 al., 2019). This prevents applications of GCN 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- 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 al. (2017): Chen et al. (2018a;b); Zou 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 shows the sparsity pattern of three citation networks. We first rearrange the vertices via an approx- imate 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

---

Under review as a conference paper at ICLR 2020
500
1000
1200
30000
1500
2500
Figure 1: 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 affect the overall arrow pattern. For simplicity, we treat them 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. Cluster-GCN these highly-cited papers are randomly put into one community and the adjacency matrix is approximated by a blocklokieaee -diagonal matrix; i.e., Cluster-GCN removes the fletching part of the arrow patterns in Fig- ure 1. This approximation ruins the beautiful arrow pattern, and thus ignores the multi-community influence of some seminal papers.
The above difficulties be easily tackled by the Chordal-GCN, novel clustering beateriing-bsedd method for the semi-supervised node classification task. Recall that Cluster-GCh ignores all the inter- cluster 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 large-scale sparse graph into several small dense subgraphs, and construct 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 root; and when training on a certain subgraph, we minimize the usual GCN loss, plus additional term called consistency loss. With the consistency loss, messages in the children subgraphs can 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 Cluster-GCN.
of which the nodes are
Our contribution is summarized as follows:
We propose Chordal-GCN for semi-supervised node classification 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 large-scale graph in partially separable manner; i.e., in every iteration, the training is performed on a subgraph, and the connections between sub- graphs are handled by 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-SUPERVIISH NODE CLASSIFICATION WITH GCNS
Suppose EV is an undirected graph with [V| = n and the n x n symmetric matrix A is the adjacency matrix. Every node l is associated with a feature vector 24 Rd and all the feature vectors are stored in the rows of X E Boxd, An L-layer graph convolutional network (GCN) (Kipf & Welling, 2017) has the layer-wise propagation rule:
H(+1) oi ((HH((()))
2

---

Under review as a conference paper at ICLR 2020
(c)
(a)
(b)
Figure 2: (a) An example of non-chordal graph. The edge {d, }) is a chord in the path (a, e, c, d). This graph non-chordal because the cycle (a, d, c, a) is chordless. (b) example of chordal graph. The path (b, a, c, d) is chordless. (c) A chordal graph with 17 vertices.
where W 14xd is a weight matrix. The matrix A D 1/2 1 1/-1//11/2 1/2 is the normalized adjacency matrix, where H( E Raxd are the activations in the I-th layer (H = X and do = d). The function is the activation function for layer 1. The output of an L-layer GCN is an n x matrix H()), of which the k-th row the predicted label for node k. Later in the paper, we will train GCN using only a subgraph G(r), so the notation yi (pred) (W; X Avr) is used to indicate the predicted label of node k, using the coefficient matrices W = (W w(L-1)), the submatrix Any, and the corresponding feature vectors X,,:
+ and D E Rxxd is diagonal with D E3 Aij. The matrix
Semi- supervipe node classification is popular application of GCN. When applying GCN for this task, we minimize the loss function
(( (W; =
Σ
& (yi
(true) (pred) (W;
KEVI
to learn the weight matrices W = (W(O) W(L-1)). In the formula, Uk
(true) is the given true label for node k, and V C V is the subset of vertices with given true labels. The function Ej (-.-) is a loss function, and usually 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 basceing--bsedd methods become more interesting the recent literature. Besides Cluster-GCN (Chiang al., 2019), Graph Partition Neural Network (GPNN) Liao et al. (2018) also partitions the entire graph into small clus- ters, and the GCN model alternatively propogates within-cluster and between-cluster In addition, clustering structure can also be utilized implicitly low-rank approximation of the graph Lapla- cian. This idea is exploited 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 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). this paper, we will chordal sparsity theory to exploit the clustering structure. So now 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, with [V| n, order the vertices from 1 to n, and then we refer to a vertex in V by its order E [m] {1, 2........ n). In addition, an index set 7 C [n] represents a subset of vertices in V.
3

---

Under review as a conference paper at ICLR 2020
13, 14, 15, 16, 17
3
16, 17
14, 15,
10
11,
10, 16
8,9 9
11
separator os; residual v
12
8, 10
9, 16
9, 10
13
5, 7
1,2
14
clique
6,
16
17
Figure 3: Left. The (symmetric) adjacency matrix of the graph G shown in Figure 2c. (For simplicity we only show the lower triangular part.) bullet in the (i,j)tt entry means nodes i and are adjacent. The dashed lines separate the supernodes (clique residuals) in the clique tree. Right. The corresponding postordered clique tree T Every node T is a clique in G, and the red index in every clique indicates the clique representative. The dashed box shows an example clique.
Cliques. A complete graph is graph in which every pair of distinct vertices is adjacent. A clique S V of a graph G is a subset of vertices that induces a maximal complete subgraph. The graph induced by y is denoted G(y) (7, E())) and has edge set E(y) {(v, w) E E v. E Y)
Chordal graph. A path between uo and es is sequence of distinct vertices (Ng, U1, .2,... with (uy, 1441) E for 0, ...... h 1. For example, the graph in Figure 2a has path (a, e, 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 ed } is a chord in the path (a, e, c, d), but in Figure 2b, the path (b, a, d) is chordless. An undirected graph is chordal if every cycle of length greater than three has chord. Figure 2b and show two examples of chordal graphs, while the graph in Figure 2a is non-choral.
Postordered elique tree. Given a (connected) chordal graph G (V, E). we can always construct clique tree Tc; the nodes of 7 are the cliques y C V and two cliques adjacent in T if they share some vertices in V. In addition, we can arbitrarily pick a clique as the root every non-rooted clique be partitioned into clique separators and clique residuals. The clique separator is the intersection of the clique with its parent clique in T The clique residual is also called the (maximal) supernode, and by definition, all the supernodes form partition of V.
tree, and then
More interestingly, we can always find an ordering vertices V so that the clique tree 7 satisfies the following properties.
1. The higher neighborhood of every vertex is complete: k E adj (1) implies (j,k) E E, where the higher neighborhood of vertex defined as adj (1) = (j {i.}} E E j> i). This means that every clique and supernode in T can be written as 7 and 74, respectively, where E V has the lowest order in the clique (and supernode). We denote by the representative of the supernode v4, by a; 7 7 ; the corresponding clique separator, and by v the set of all representatives. The index set a is empty if is the root of T
2. The elements of each supernode are numbered consecutively: Vi {i,i 1, with n; = j14 1/.
3. All the representatives E yc are topologically ordered: < p(1) if V and p(i) the representative of the parent of 7/ in 7
An ordering satisfying the above three properties is called topological postordering, and a clique tree 7 with certain topological postordering referred to postordered clique tree. Figure
4

---

Under review as a conference paper at ICLR 2020
shows supemoode 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, at = {8, 10).
s 6,,6, 8,8, 10),
V/5 {5. 6, 7).
Given a chordal sparsity graph G = E), there exist efficient algorithms (in O(EE)) to find a topologiaal postordering, and to generate a postordered clique tree T together with the parent function p(t) and all the index sets (i.e., Y/8 My, and a for all i Vº) (Lewis et al., 1989; Pothen & Sun, 1990). The whole process is called chordal decomposition (Vandenherghe & Andersen, 2015).
CHORDAL-GCN
Now are ready to utilize the chordal decomposition technique in training large-scale sparse net- works. 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 non- chordal graph G (V. F)) into a chordal graph G' (V. F²) by adding edges, i.e. E C F'. Unfortunately, to find the minimum fill-in 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, 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 to say, every minimal chordal extension is associated with certain vertex ordering. Thus, the reordering of vertices is important, especially when prefer 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 minimal chordal extension.
Clique merging. Often, the resulting extension contains many small cliques and it would be more efficient to merge some neighboring cliques, reported in Ashcraft & Grimes (1989). In this work, traversing the tree from leaf to root, we greedily merge clique with its parent 7p(()) if [yyl S T and |Pro)] < 7 where 7 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 (together with all the index sets (7i. Vi, and a.), and the parent function p())). With little abuse of notation, we also use T 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 "/s and the corresponding induced subgraph G(x). 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(v)), not G" (1:).
Lastly, we emphasize that, although G(7x) no longer represents complete subgraph, we still refer to 7 as clique to distinguish from clusters or communities: in the chordal decomposition, one node k E 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 in hand, we are able train a large-scale sparse graph in partially separable manner, i.e., clique by clique. Suppose we traverse the tree T in the topological order, i.e., from leaf to root. At clique Yi, the loss function consists of two parts. The first part the usual GCN loss defined in (1), but using only the induced subgraph G(y) instead of the entire G:
C (gen)) (v; Xy.. Aner))
Σ
& (1
(true) (pred)
(:; Xx Amar)))
KEViNW
where X.,.: takes the rows of X indexed by n and Any, is the submatrix of A with rows and columns indexed by 74-
5

---

Under review as a conference paper at ICLR 2020
Algorithm 1 Chordal-GCN.
1: Input. A normalized adjacency matrix A, a postordered clique tree To, feature matrix X, and (prod) for k E Vl.
true labels yk
2: Output. The coefficient matrices W (Wr") ,..., W(L-1)). (..,),,,,,)))
3: Randomly initialize W
4: for = 0, 1, 1......dd do
5: for i e V topological order do
6: Compute the loss by (4), i.e.
L,(W) = E
la (yk: U/ (pred) (W; x Awx)))
REVINS
(2)
Σ
l2 (u (pred) (W; XW,: Aneu) 1/x
(pred) (Wll); Xagin Ansns))
jEch(f) kEa,
7: Perform gradient descent step Wi++1] w -w (7VC)(()))
8: end for
9: end for
The second part of the loss the consistency loss. When we arrive at clique Ys we have traversed all its children in the tree T This means that some nodes in have already been visited; namely, those clique separators of 74's children in T For clarity, we denote by ch(i) the set of children representatives of YG Le., j E ch(i) if j is representative (i.e, E Vo) and Yj is child of in 7 Then all the nodes in Og for j E ch(i) have already been visited when we arrive at %. Thereby, for & E aj and ch(i), hope that the predicted label y/ (pred) (W; X Anyns) using clique 7 and the clique is consistent with the previous prediction yk y most recent parameter W. Hence, the consistency loss for training clique Y/ can be formulated
(pred), (:: using the current
(oons) Ny.r Ansr) = Σ Σ
l (pred)
(:: Anow) vi (pred) (W; XXyxs Anyzy)) (3)
(E) kEo;
where -2( is loss function, for example, the KL divergence. Note that W is not treated as the (W; X Ansro) considered constant when we take the
variable of (cous)) i.e., the term y
(pred)
gradient of (coon))
Therefore, when training the clique Yi we compute the total loss
(4) and perform a gradient descent step W+ = W (W) where is the learning rate. The whole algorithm is summarized in Algorithm Note that the gradient descent step line of Algorithm can be replaced with any other accelerated version, for example, Adam (Kingma & Ba, 2015).
(.(-) (ienn) (: X Test A ) + ((cons) (1; X Awy:)
3.2. CONNECTION TO THE ORIGINAL GCN
We note that Algorithm is essentially the mini-batch gradient descent method applied to the loss
(legen) (W) Σ C.WW) iEVe
(5)
with 7 taken the mini-batch. Clearly. it is equal to the original GCN loss (1) if we have only one clique (ie., /e- = {1} and thus 7 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, is impossible 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.

---

Under review as a conference paper at ICLR 2020
Table 1: Time and memory complexity of GCN training algorithms. is the number of nodes, || lo is the number of nonzeros in the adjacency matrix A, and is the number of features. For simplicity we assume the number of features is fixed for all layers, i.e, di = d for = 1,2,..., For SGD-based methods, b is the batch size and is the number of sampled neighbors per node. Also, 6j is the maximum cluster size in Cluster-GCN while 02 the maximum clique size in our method. For memory complexity, Laf is used to store the parameters === (WO) and the other term is for storing embeddings (f For simplicity we omit the memory for storing the graph or subgraphs since they are fixed and usually not the main bottleneck.
the number of layers, n
Complesity
GCN (Kipl Welling, 2017)
GraphSAGIE Olamilion
FaeKOON
2018s)
VR-GON
al., 20186)
(Chiang 2019)
Chuser-GGN
Chordal
Time Memory
AlL] Indf) OlInd + LeF)
O(rfndP) O(ird + Lo))
OlLrnd)) OkZAnd + Lif)
O(L] ud (2 (fuP)) Oftond + Ld9)
AlL] Ladf) Otleyd Ld))
All Lndf) Ol + Ldf)
3.2.2 TIME AND MEMORY EFFICIENCY
Following Chiang et al. (2019), we report the time and memory complexity in Table Although our method has the same time complexity as Cluster-GCN in big-O notation, Chordal-GCN needs an extra forward propagation
the children cliques in order to compute the predicted labels
yk (pred) (Will; X X,y. Ayyyy) in (2). The extra forward propagation step would be the only price paid for single node being in multiple subgraphs. As 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 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 desirable.
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 state- of-the-art GCN training algorithms for comparison: GCN (Kipf & WWeling, 2017), GraphSAGE (Hamilton et al., 2017), FasIGCN (both uniform and importance sampling) (Chen et al., 201 8a), 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., = 2), the same label rate, and Adam optimizer (Kingma & Ba, 2015) with learning rate 0.001, dropout rate 20%, weight decay zero. For the baselines, 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, stop training when the validation accuracy does not increase threshold (0.01) for 10 epoches, and choose the model with the highest validation accuracy as convergent point. We use the following metries to evaluate the performance of all methods.
Accuracy: The micro Fl 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-GCM, an epoch is 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-GCS achieves the highest accuracy among all baseline models. This desirable result is due to the exploitation of the exact sparsity pattern and clustering structure.
7

---

Under review as a conference paper at ICLR 2020
Table 2:
Comparsion of Chordal-GCN with original GCN, GraphSAGE. FastGCN with uni- form/importance sampling, VR-GCN, and Cluster- We report the micro Fl 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.
Datasct
Method
F1 (%)
Mcm. (MB)
Epoch time (ms)
# epoches
GraphSAGE
78.4
565.12
44.26
11
FastGCN (uniform)
78.2
28.42
27.10
88
FastGCN (importance)
83.5
28.42
30.41
84
Cora
VR-GCN
81.6
4.60
14,90
(2708)
Cluster-GCN
68.2
36.14
62.65
GCN
78.4
20.23
5.35
119
Chordal-GCN
81.2
5.69
90.90
GraphSAGE
61.8
932.14
37.97
60
FastGCN (uniform)
70.2
98.93
111.00
53
FastGCN (importance)
72.2
98.93
104.90
Citeseer (3327)
VR-GCN
71.2
7.01
32.00
35
Cluster-GCN
62.8
60.35
82.09
GCN
70.5
52.16
6.42
95
Chordal-GCN
74.1
8.47
38.91
57
GraphSAGE
76.8
475.84
43.57
47
FastGCN (uniform)
77.4
107.20
25.41
52
FastGCN (importance)
78.0
107.20
22.00
47
Pubmed
VR-GCN
78.4
14.49
25.21
33
(19717)
Cluster-GCN
71.2
25.35
59.84
10
GCN
78.0
66.03
7.52
109
Chordal-GCN
80.2
15.37
55.94
83
GraphSAGE
93.1
1192.00
185.22
62
FastGCN (uniform)
92.9
1656.14
15.83
64
FastGCN (importance)
93.0
1722.05
21.60
31
Reddit
VR-GCN
93.2
1054.21
5041.32
32
(232965)
Cluster-GCN
96.1
231.32
2407.61
43
GCN
93.9
2992.12
261.81
190
Chordal-GCN
94.2
2501.23
987.12
410
In terms 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 inter- mediate node embeddings. More interestingly, Chordal-GCN uses less memory space than Cluster- GCN (except in reddit). This is because the Cluster- implementation epoch, and thus the memory bottleneck depends on the sum of the selected clusters, rather than the maximum cluster. The abnormal memory 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.
few clusters in one
of Chordal-GCN in reddit dataset is attributed to our
Lastly, we emphasize that the comparison 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.
CONCLUSION
We propose Chordal-GCN for sumi-supervised node classification large-scale sparse networks. The proposed model exploits the sparsity pattern and clustering structure the graph, and utilizes the exact graph structure (i.e,, without sampling approximation). Moreover, the memory usage
8

---

Under review as a conference paper at ICLR 2020
of Chordal-GCN is limited because the training is performed in partially separable manner; i.e., clique by clique. Experiment results demonstrate that Chordal-GCI achieves the best test accuracy with much smaller memory cost benchmark datasets.
REFERENCES
P. Amestoy, T. Davis, and I. Duff. An approximate minimum degree ordering algorithm. SIAM Journal on Matrix Analysis and Applications, 17(4))886-99) 905, 1996.
M. S. Andersen and L. Vandenberghe. CHOMPACK: A Python Package for Chordal Matrix Com- putations, 2015, cvxopt www.tg......oooooooooooooo
M. S. Andersen, J. Dahl, and I.. Vandenberghe. Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones. Mathematical Programming Compu- tation, 2:16 2:167,201, 2010.
M. S. Andersen, J. Dahl, and L. Vandenberghe. Logarithmic barriers for sparse matrix cones. mization Methods and Software, 28(3):396-423, 2013.
Opti-
M. S. Andersen, J. Dahl, and L. Vandenberghe. CVXOPT: A Python Package for Convex Optimiza- tion, 2015, www. ewxopt.org.
C. Ashcraft and R. Grimes. The influence of relaxed supernode partitions on the multifrontal method. ACM Transactions on Mathematical Software, 15())2991-309 1989.
C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. Journal of the Association for Computing Machinery, 30(3):479-513, 1983.
J. Chen, T. Ma, and C. Xiao. FastGCN: Fast learning with graph convolutional networks via impor- tance sampling. In International Conference on Learning Representations, 2018a.
J. Chen, J. Zhu, and L. Song. Stochastic training of graph convolutional networks with variance duction. In J. Dy and A. Krause (eds.), Proceedings of the 35th International Conference on Ma- chine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 942-950, 2018b.
W.-L. Chiang. X. Liu, S. Si, Y. Li, S. Bengio, and C.-J. Hsieh. Cluster-GCN; efficient algo- rithm for training deep and large graph convolutional networks. In ACD SIGKDD International Conference Knowledge Discovery and Data Mining, 2019.
G. R. Cowell, A. P. Dawid, S. L. Lauritzen, and D. J. Spiegelhalter. Probabilistic Networks and Expert Systems. Springer, 1999.
A. Darwiche, Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
K. Dong, R. Benson, and D. Bindel. Network density of states. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. ACM, 2019.
F. Gavril. Algorithms for minimum coloring, maximum clique, minimum covering by cliques, and maximum independent set of chordal graph. SIAM Journal on Computing. 1(2):180-18)) 187, 1972.
M. C. Golumbic. Algorithmic Graph Theory and Perfect Graphs, volume 57 of Annals of Discrete Mathematics. North-Holland Publishing Company, Amsterdam, The Netherlands, The Nether- lands, 2004.
W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017.
D. P. Kingma and J. L. Ba. ADAM: a method for stochastic optimization. ICLR, pp. 1-15, 2015.
N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference Learning Representations, 2017.
Y. LeCun and Y. Bengio. Convolutional networks for images, speech, and time series. In Michael A. Arbib (ed.), The Handbook of Brain Theory and Neural Networks, pp. 255-22 258. MIT Press, Cambridge, MA, USA, 1998.

---

Under review as a conference paper at ICLR 2020
J. G. Lewis, B. W. Peyton, and A. Pothen. A fast algorithm for reordering sparse matrices for parallel factorization. SIAM Journal on Scientific and Statistical Computing. 10(6):114-1117) 1989.
R. Liao, M. Brockschmidt, D. Tarlow, A. Gaunt, R. Urtasun, and R. S. Zemel. Graph partition neural networks for semi-supervised classification, 2018. ht BRLLttts:://peneeeeee http//ppnneeeeeeeeeeee Forum?id-rae 4i 22b
R. Liao, Z. Zhao, R. Urtasun, and R. Zemel. LanczosNet: multi-scale deep graph convolutional networks. In International Conference on Learning Representations, 2019.
T. Ohtsuki. A fast algorithm for finding an optimal ordering for vertex elimination graph. SIAM Journal on Computing, 5(1):1331445 1976.
J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, 1988.
A. Pothen and C. Sun. Compact clique tree data structures in sparse matrix factorizations. SIAM Journal on Large-Scale Numerical Optimizations, pp. 180-204, 1990.
D. J. Rose. Triangulated graphs and the elimination process. Journal of Mathematical Analysis and Applications, 32(3):597-609, 1970.
D. J. Rose. On simple characterizations of k-trees. Discrete Mathematics, 7(3-4):317-222, 1974.
D. J. Rose, R. E. Tarjan, and G. S. Lueker. Algorithmic aspects of vertex elimination on graphs SIAM Journal on Computing, 5(2):266-28,, 1976.
M. Schlichtkrull, T. N. Kipf, P. Bloem, R. vanden Berg, I. Titov, and M. Welling. Modeling relational data with graph convolutional networks. In A. Gangemi, R. Navigli, M.-E. Vidal, Hitzler, R. Troncy, I.. Hollink, A. Tordai, and M. Alam (eds.), The Semantic Web, pp. 593-607. 593-607. Springer International Publishing, 2018.
R. den Berg, T. N. Kipf, and M. Welling. Graph convolutional matrix completion. arXiv e-prints, June 2017.
L. Vandenberghe and M. Andersen. Chordal graphs and semidefinite optimization. Foundations and Trends in Optimization, 1(4):241-433, 2015.
Yadav, M. Nimishakavi, N. Yadati, Vashishth, A. Rajkumar, and P. Talukdar. Lovász convolu- tional networks. In AISTATS, pp. 1978-1987, 2019,
M. Yannakakis. Computing the minimum fill-in is NP-complete. SIAM Journal on Algebraic Dis- crete Methods, 2(1):77-79, 1981.
D. Zou, Z. Hu, Y. Wang, S. Jiang, Y. Sun, and Q Gu. Layer-dependent iimportance sampling for training deep and large graph convolutional networks. In Advances Neural Information Processing Systems, 2019.
A IMPLEMENTATION DETAILS
Hardware and software. We use Tesla V100 GPU, Intel Xeon CPU E5-2698 (2.20GHz) with 500GB. We use PyTorch 1.2.0 in our implmentation and Tensorflow 1.13 to test the baselines.
Datasets. The cora, citeseer, and pubmed datasets are from httpps://gghthhbbbcoo http://tttt..cccttii/ttto/octt/t gen. The reddit data is from https: stanfooo wetpeedd////raeeeeeee data statisties in Table 3.
stwfford.
We report the
Table 3: Data statistics
Dataset
Nodes
Edges
Classes
Features
Label rate
Cora
2, 708
5, 429
1, 433
140 (5.1%)
Citeseer
3, 327
4, 732
3, 703
120 (3.6%)
Pubmed
19, 717
44, 338
3
500
60 (0.3%)
Reddit
232, 965
11, 606, 919
602
152, 410 (65.4%)
10

---

Under review as a conference paper at ICLR 2020
Table Parameters in Chordal-GCN
Threshold for merging (T)
Number of cliques
Maximum clique size
Minimum clique size
Dataset
cora
100
19
446
125
citeseer
200
512
227
pubmed
2, 000
8
6, 105
2, 132
reddit
10, 000
126
220, 069
1, 1,001
Preprocessing. In Chordal-GCN, we use the AMD ordering (Amestoy 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 Vanden- berghe, 2015). We also use the clique merging heuristic described in section 3.1. The threshold is different 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. wwwemoryBByttsIntne () for TensorFlow and torch. cuda www....eooy....oom
for PyTorch.
B ADDITIONAL EXPERIMENTS
B. ABLATION STUDY
We evaluate the contribution of the consistency loss (rons) (3) here. We train Chordal-GCN with and without (coos) on the cora, citeseer, and pubmed datasets, and plot the validation accuracy versus the number of epoches. Figure 4 shows that the consistency loss ((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-GCNN GCN: Cluster- GCN ignores those inter- cluster links and thus loses the connections between clusters. In the pubmed dataset, Chordal-GCN without consistency loss even overfitting: the validation accuracy decreases after several epoches. Ablatins audy
study
sludy
46
0.0
0.0
with Cloose
with ((eaa))
with gloual witloua
willoun
willout
nam of spoches
nuto epockes
nutD of spocktes
Figure 4: Validation accuracy of Chordal-GCN the datasets: cora, citeseer, and pubmed. The blue curve shows the validation accuracy with the consistent loss (ioons) while the red curve shows that without C (cnns)
B.2 TRAINING DEEP GCNS
In this section, we study the performance deeper Chordal-GCN, and explore how time and mem- ory 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 training deeper GCNs.
11

---

Under review as a conference paper at ICLR 2020
time complexity (ms)
120
memory cost (MB)
20
16
number of GCN layers
number of GCN layers
Figure 5: Memory (leff) and time (right) versus number of GCN layers. Both curves scale linearly, which is promising and consistent with theoretical analysis.
12


Reviews:
[{"review_id": "SJxy62zaFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 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.\n\nOverall, 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.\n\nPros:\n\n1, 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.\n\n2, The examples in Figure 2 and 3 are very helpful in understanding the concepts related to the clique tree decomposition.\n\n3, The summarization of time and memory complexity is very helpful in comparing different models. \n\n4, 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. \n\nCons & Questions:\n\n1, 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.\n\n2, 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).\n\n3, Why does Chordal-GCN take significant more epochs than GCN on Reddit and less epochs on all other datasets?\n\nSuggestion:\n\n1, 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.\n\n2, 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].\n\n[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.\n\n[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.\n\n======================================================================================================\n\nThank 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.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "BJeCB_sT_H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "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": "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.\n\nStrength:\n1. The authors study an interesting and important problem to reduce memory usage for GCN in large-scale graphs. The usage of chordal sparsity is interesting and innovative.\n2. The authors carry out ablation study on the consistency loss components in the algorithm.\n\nWeakness:\n1. One major concern is that the reduction in memory usage is not large enough to justify the huge increment in running-time. For example, on Cora dataset, the memory is reduced by 4x while the running time is 16x compared to vanilla GCN.\n2. It is not clear why Chordal-GCN can achieve better accuracy compared to vanilla GCN. Since Chordal-GCN serves as approximation for GCN as the authors claim that using entire graph will provide better accuracy. As a result, the vanilla GCN is expected to achieve better accuracy. It would be better if the authors could provide more intuition and explanations.\n3. The evaluation does not take the graph preprocessing into consideration. The authors should report the time and memory taken to carry out the preprocessing steps as well.\n4. For most real-world large-scale industry networks, it is hard to fit the graph into memory. Though the GCN training part could run in distributed way, it is not clear how to efficiently build the clique tree in similar method.\n5. Given the main purpose of the algorithm is to reduce memory usage for large-scale networks, it is expected to see experiments on larger graphs where the large memory footprint becomes a real issue.\n\nDetailed comments:\n1. The description in Section 2.2 is not very clear. It would be better if the authors could provide a more detailed introduction to clique tree and the algorithms used.\n2. For the Chordal-GCN in algorithm 1, for epoch 2 onwards, do we also add consistent-loss when training leaves as well?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "B1e8GSdatH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "The authors propose Chordal-GCN which is based on the chordal decomposition method post-ordered clique tree and propagates the features based on the order within each subgraph in order to reduce memory usage. The authors show that Chordal-GCN outperforms GCN [1] on all four datasets and argue that Chordal-GCN reduces memory usage.\nThe idea of using Chordal graphs to GCN is novel and interesting. However, my main concern lies in the experiment results.\n\n1) To my best knowledge, the proposed Chordal- match SOTA results on Cora, Citeceer, and Pubmed. However, since these datasets are small and easy to run, I would like to see the mean and standard deviation of the accuracy of all models you ran. Can you also provide the results of the commonly used \"random split setting\"[1]?\n\n2) What is the epoch time of the Chordal-GCN? Can you also report it in Table 2? Without including the pre-processing time, we don't know the overall training time of the method.\n\n3) Given that the main concern is the memory usage, the authors should compare to a strong baseline, SGC [2], which is a linear classifier trained on top of propagated features with memory/space complexity O(d) when using mini-batch training. This is much smaller than the proposed method O(Lc_2d + Ld^2).\nAlso, SGC is at least two magnitudes faster to train (2.7s vs 0.987*410=367.8s + unknown pre-processing time) and more accurate (94.9 vs 94.2) than the proposed Chordal-GCN on the largest Reddit dataset. The authors emphasize that the proposed method is scalable. Please compare it to SGC in Table 2. \nNevertheless, there is some chance that the authors can apply the same method to SGC and speed it up further as long as the preprocessing time is relatively small.\n\n4) Based on Table 2, Cluster-GCN uses less memory and is more accurate and faster to train than Chordal-GCN. Can you justify why people should use the proposed method instead?\n\n5) There are some missing citations. These papers [3,4,5,6] achieved previous SOTA results and should be included in the Tables. \n\nReferences:\n[1] Kipf and Welling: Semi-Supervised Classification with Graph Convolutional Networks (ICLR 2017)\n[2] Wu et al.: Simplifying Graph Convolutional Networks (ICML 2019)\n[3] Klicpera et al.: Predict then Propagate: Graph Neural Networks meet Personalized PageRank (ICLR 2019)\n[4] Gao and Ji: Graph U-Nets (ICML 2019)\n[5] Zhang et al.: GaAN: Gated Attention Networks for Learning on Large and Spatiotemporal Graphs (UAI 2018) \n[6] Fey: Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks (ICLR-W 2019)", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The submission is proposed a rejection based on majority review.
Decision: Reject