Substructured Graph Convolution for Non-overlapping Graph Decomposition
Authors: Youngkyu Lee
Chang-Ock Lee
Venue: Submitted to ICLR 2023 (2023)
Keywords: Graph convolution
non-overlapping graph decomposition
parallel computation
substructuring method

Abstract: Graph convolutional networks have been widely used to solve the graph problems such as node classification, link prediction, and recommender systems. It is well known that large graphs require large amount of memory and time to train graph convolutional networks. To deal with large graphs, many methods are being done, such as graph sampling or decomposition. In particular, graph decomposition has the advantage of parallel computation, but information loss occurs in the interface part. In this paper, we propose a novel substructured graph convolution that reinforces the interface part lost by graph decomposition. Numerical results indicate that the proposed method is robust in the number of subgraphs compared to other methods.

Under review as a conference paper at ICLR 2023
SUBSTRUCTURED GRAPH CONVOLUTION FOR NON- OVERLAPPING GRAPH DECOMPOSITION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph convolutional networks have been widely used to solve the graph problems such node classification, link prediction, and recommender systems. It is well known that large graphs require large amount of memory and time to train graph convolutional networks. To deal with large graphs, many methods are being done, such as graph sampling or decomposition. In particular, graph decomposition has the advantage of parallel computation, but information loss occurs in the interface part. In this paper, we propose a novel substructured graph convolution that rein- forces the interface part lost by graph decomposition. Numerical results indicate that the proposed method is robust in the number of subgraphs compared to other methods.
INTRODUCTION
Graph convolutional networks (GCNs) (Kipf & Welling 2017) are widely used in node classifi- cation (Xiao et al. 2022). link prediction (Zhagg & Chen 2018), and recommender systems (Wul let al. 2022). For given graph, GCN constructs a renormalized graph Laplacian using the graph's adjacency matrix and uses it for layer propagation. Therefore, as the dimension of the adjacency matrix of the graph increases, more memory and time are required to train the network.
There are two main types of research to solve the memory problem. The first is graph sampling methods (Hamilton et al. (2017) Chen al. 2018 Ye et al. 2019 Zeng al. 2020). These methods basically create subgraph at every iteration using an appropriate sampling algorithm like Deep- Walk (Perozzi et al. 2014). The network trained using this subgraph. GraphSAGE (Hamilton) et al., 2017) used the edge information corresponding to fixed-size neighborhood of uniformly sampled nodes. FastGCN (Chen al.] 2018) proposed the importance sampling and showed faster learning speed compared to GraphSAGE, VR-GCN (Ye et al. 2019) used the variance reduction technique to reduce the number of sampling nodes. GraphSAINT (Zeng et al., 2020) improved per- formance by using graph sampling instead of node sampling edge sampling. Because the graph sampling method uses subgraphs to reduce memory usage, is important to determine the number of samples. The higher the number of samples, the higher the performance is expected, but the slower the training speed and the memory is consumed.
On the one hand, there is another approach to decompose the graph (Chiang et al. 2019). The biggest advantage of the decomposition methods is that, unlike the sampling methods, it can be performed in advance before network training. A lot of research has been done how decompose the graph (Karypis & Kumar 1998) Avery [201]]
2 Gonzalez et al. (2012). Among them, METIS (Karypis) & Kumar 1998), which can quickly decompose a graph using multi-level structure, widely used.
In view of linear algebra, METIS derives a block diagonal matrix by performing non-overin non-overlapping decomposition on the adjacency matrix of a given graph. ClusterGCN (Chiang et al.) 2019) trains the network with a mini-batch gradient descent algorithm by performing block sampling on the block diagonal matrix generated by METIS. That is, this method trains the network by alternating block submatrices through random sampling. On the other hand, there is another way to train the network at once with the gradient descent algorithm by computing the block diagonal matrix for each block in parallel. A big difference from the alternating method is that it does not require inner iteration because it trains the network using all subgraphs at once and then merges them. However, non-ovellapping decomposition drops blocks in off-diagonal part and does not supplement

---

Under review as a conference paper at ICLR 2023
information about this part. Therefore, the number of blocks increases, the amount of information lost increases, which also affects training of the network.
In the field of numerical analysis, there are substructuring methods (Bramble et al. 1986; Farhat & Roux 199T) that additionally use information on the interface part in the domain that has undergone non-overlapping decomposition. Assuming that the interface part is sparse when appropriate non- overlapping decomposition is performed, the added computation and communication costs are very small. Therefore, although the interface part requires sequential computation, does not become bottleneck in the overall parallel structure.
Motivated by the substructuring method, we modify the graph convolution with the block diagonal adjacency matrix generated by non-overlapping decomposition. That is, substructure using the interface adjacency matrix added to the graph convolution. We call graph convolution with this added substructure a substructured graph convolution. A simple linear algebra calculation shows that the sum of the outputs of the aggregate using the block diagonal adjacency matrix and the in- terface adjacency matrix is different from the output of the aggregate using the original adjacency matrix. Therefore, to compensate for this difference, weighted sum performed by calculating coefficients by referring to the attention module that shows good performance in natural language processing (Vaswani et al. 2017) and image classification (Hu et al. 2018). From the numerical re- sults, it can be confirmed that the proposed graph convolution adequately complements the interface part.
The rest of this paper is organized follows. In Section 2] graph decomposition framework and two methods for training a given network with decomposed graphs. We present the substructured graph convolution in Section Improved node classification accuracy or Fl-score of the proposed graph convolution applied to GCN, GCNII, GAT, and SGC using various datasets presented in Section 4
introduce abstract non-overlapping
We conclude this paper with remarks in Section 5
NON-OVERLAPPING GRAPH DECOMPOSITION
In this section, we briefly introduce an algebraic framework of non-overlapping graph decomposi- tion. We then describe two methods for training the graph convolutional networks using the decom- posed graphs.
2.1 ALGEBRAIC FRAMEWORK
Let RRxn be an adjacency matrix of given graph consisting of n nodes. Without loss of generality, let the graph be uniformly decomposed so that each subgraph has n/N nodes for positive integer N. Let R. R" + R"/N be the restriction operator onto k-th subgraph.
We construct non-overlapping decomposition of given adjacency matrix A under the node decom- position setting, A subgraph adjacency matrix A& E g=/Nxn/N is defined by
A R2 ART 1, N.
(2.1)
The non-overlapping decomposition À of A with subgraph adjacency matrices 2.1 is given by
Ā
Σ R A.R
(2.2)
Then À becomes the adjacency matrix of the graph consisting of subgraphs having A..... An as adjacency matrices. We define this graph as non-overlapping graph decomposition for given graph.
For the block matrix representation
Auı
A
A IN
A
Ay
An
= [Aylissss
(2.3)
ANI
AN2
ANN
2

---

Under review as a conference paper at ICLR 2023
Non-overlapping decomposition
Alternating method
Additive method
GCN
Loss
GCN
Loss
Minibatch 2
GCN
Loss
GCN
Figure Schematic description of alternating method and the additive method after non- overlapping graph decomposition. Note that we assume the case of N for simplicity.
the corresponding block matrix representation of the non-overlapping decomposition À is written
A1 11
A22
= diag (lAillz))
(2.4)
ANN
where A, E Re/N Xn/N is defined by A.j = R:ART That is, À the block-diagonal part of A. Comparing 2..3 and 2.4h. it can be seen that the number of off-diagonal parts lost in A increases N increases. That is, it is clear that N increases, the degree to which A approximates A decreases significantly; see Toselli & Widlund (2005).
2.2 TRAINING WITH NON-OVERL GRAPH DECOMPOSITION
Now, we introduce two methods for training a network with a graph generated by the non- overlapping graph decomposition. One is alternating method known ClusterGCN (Chiang et al. 2019) and the other is an additive method similar to Data Parallelism (Gonzalez et al. 2012).
First, explain the basic training method of graph convolutional networks. Let G (V, A) be a graph consisting of node vector V (u),.... vn) with an adjacency matrix A E Ruxx Each node v; has F-dimensional feature vector æ; E RR and belongs one of the C classes. which is labeled with C-dimensional one-hot vector y: The entire node feature X E R=* has (æ1...., ) as row vectors. Similarly, the entire node label Y 1=x has {y1. 3n as row vectors.
For convenience, it is assumed that the network fe consists of one graph convolution layer with trainable parameter θ and the softmax function. Let W E FxC and b BC be the weight and bias of the layer and = [W,b) b). Then the forward propagation of se written as
fe A) = softmax(SXW + b):
D) is renormalized graph Laplacian (Kipf & Welling 2017]. Here D is a degree matrix of given A and I is an identity matrix. Let L be a loss function that trains the network fe. Then, for each epoch, the network is trained by gradient descent method
where S = +I+
-i+= 0' Ve Y),
3

---

Under review as a conference paper at ICLR 2023
Now, introduce the alternating method first. Using 2.1 and (.2 matrix X3 and label matrix Y& are defined as
each subgraph Gs, feature
GE [v,, As). V R&V, X = R,X, Y4 = RgY.
Then, for each epoch, the network is trained by mini-bateh gradient descent method described in Algorithm
Algorithm 1: The alternating method with learning rate 7
for k = .... N do
O++1 @ V C(fe Ak); Yx)
end
Next, we introduce the additive method. The additive method computes the total output of layer gathering the outputs derived from each subgraph in parallel. After that, the network is trained using the gradient descent method. For each epoch, Algorithm shows the update process of additive method.
Algorithm 2: The additive method with learning rate
for
k 1,.., N in parallel do
Y = fer (X,,
end
k= R Y @itl A v LY
Figure iillustrates a schematic description of the additive method and the alternating method in the case of
SUBSTRUCTURED GRAPH CONVOLUTION
As mentioned in Section the non-overlapping graph decomposition has disadvantage in that the loss off-diagonal information of the adjacency matrix increases as N increases. Therefore, can be expected that the performance of graph convolutional networks using graph decomposition depends heavily on the number of subgraphs N. The same phenomenon can be observed in both the alternating method and the additive method, and the experiment for this will be discussed in Section 4
3.1 ALGEBRAIC FRAMEWORK
In numerical analysis, there is a substructuring method that increases performance by using the in- terface part without disturbing the parallel structure; see, e.g., Toselli & Widlund (2055: Dolean al. 2015). Let the non-overlapping decomposition A defined in Section be the interior adja- cency matrix. We consider an interface adjacency matrix À graph convolution called substructured graph convolution, which improves performance by adding interface parts like substructuring method, while maintaining parallel structure. We now define the renormalized graph Laplacian S and for and A, respectively. as
Á. Then, we propose novel
5 = (I D) (I + Ā) + D)- 3
$ = - D) (
D
where D and Đ are the degree matrices of À and A. respectively. Note that S 5 other words, simply adding the outputs of graph convolution using S and Š is different from the output of graph convolution using S, the renormalized Laplacian matrix for A. Therefore, we consider weighted sum of S and Š rather than simple addition get better approximation to S.
4

---

Under review as a conference paper at ICLR 2023
Substructured Graph Convolution
Non-overtapping decomposition
S
Interior
Output
Interior
Interface
S
Interface
Figure Graphical description of the proposed substructured graph convolution after non- overlapping graph decomposition. Note that we assume the case of N 2 for simplicity.
The number of edge-cut according to the number of subgraphs N with random, ordered, and METIS decomposition applied to Cora. The random decomposition method uses the randperm function in PyTorch, and the ordered decomposition method divides the node indices in order of Cora, Note that the total number of edges in the Cora is 5429.
Table 1:
N
Random
Ordered
METIS
2
2613
2603
186
4
3907
3682
351
8
4580
4340
537
16
4898
4649
714
32
5082
4817
1018
64
5187
4941
1313
With appropriate coefficient vectors and o, we consider the forward propagation of substructured graph convolution fe
fe(X, A) o((iiag(@) diag S) + +b)
where ( (W,b) bb is parameter layer and a a nonlinear activation function.
For parallel computation of the substructured graph convolution, information compression is re- quired to minimize communication between the interior part S and the interface part S in designing a and & Motivated by the attention module, which is the core of the SE block used CNN (Hu al.) 2018). and the transformer structure mainly used in NLP (Vaswani et al. 2017), consider the coefficients & and & such as
@x, a) = softmax (
( SX)
F B [SS), 1)
where (.); denotes the i-th column. Note that F the feature dimension of X. This operation compresses the information of the intermediate features generated by S and S. and then obtains the softmax value with minimal communication and computation cost. The process of computing the coefficients & and â is structure that needs sequential computation, but it does not need additional parameters and uses the minimum cost to solve the bottleneck the overall parallel structure. A brief graphical description of the substructured graph convolution for the case of N 2 is shown in Figure
3.2 IMPLEMENTATION ISSUES
In this section, discuss several issues efficient implementation of the proposed substructured graph convolution. The first is the selection an algorithm that performs the non-overlapping de- composition given graph. It is natural that the density of the interface adjacency matrix increases
5

---

Under review as a conference paper at ICLR 2023
Table 2: Details of used datasets. Cora, CiteSeer, and PubMed datasets have single class label, but the PPI dataset can have multiple class labels.
Dataset
Nodes
Edges
Features
Classes
Train Validation Test
Cora
2708
5429
1433
7
140 / 500 1000
CiteSeer
3327
4732
3703
6
120 / 500 / 1000
PubMed
19717
44338
500
3
60 / 500 / 1000
PPI
56944
818716
50
121
44906 6514 / 5524
according to the shape of the graph if it is simply randomly cut or divided order. This makes, the interior adjacency matrix becomes sparser, which degrades the performance of the existing graph convolution. Note that the interface adjacency matrix sparse, the amount sequential com- putation decreases, so that the proposed graph convolution can be computed more efficiently. For this reason, we need a non-overlapping graph decomposition algorithm that minimizes edge-cuts. METIS (Karypis & Kumar 1998) is one of the good algorithms,, that uses multi-level structure to quickly perform the decomposition and minimize edge-cuts. Table [oolss the number of edge-cuts according each decomposition method applied to Cora (McCallum et al. 2000). METIS shows far fewer edge-cuts than simple random and ordered decomposition methods. Therefore, we use METIS for non-overlapping graph decomposition in the sequel.
Next, discuss why the renormalized graph Laplacian S and S are used. Since A = À + Å, the renormalized graph Laplacian S can be decomposed as
S = D) 3 (I Ā) ()(+D) D) (I+ A(T + DY
(3.1)
Therefore, when the decomposition (3.1 is performed, the computation of (I+D) required for the computation of the interface part. This reduces the computational efficiency of the interface part that requires sequential computation and may cause a bottleneck the interior part where parallel computation is possible. On the other hand, using S, sequential computation for the interface part can be efficiently performed.
Lastly, we note that the proposed substructured graph convolution was made by referring to the renormalized graph Laplacian of GCN, but it is also applicable to GCNII (Chen et al.] 2020), GAT (Veličković et al. 2018), and SGC (Wu et al. 2019). The key idea is to construct the interface adjacency matrix, process the aggregate, and then determine each coefficient via the attention mod- ule. Then, substructured graph convolution is performed using the renormalized graph Laplacian corresponding to the aggregate part of a given network instead of the whole renormalized graph Laplacian.
4 APPLICATIONS
In this section, we present numerical results of the proposed graph convolution embedded into sev- eral existing GCNs: GCN, GCNII, GAT, and SGC. We evaluate the performance of transductive learning and inductive learning, which are mainly used as benchmarks in graph node classification problems.
For the transductive learning task, standard citation network benchmark datasets Cora (McCallum al., 2000), CiteSeer (Giles et al., 1998), and PubMed (Yang et al. 2016) were used. In these datasets, node and an edge mean document and a citation, respectively. For the transductive environment, only 20 training nodes were used per class, and 500 and 1, 0000 nodes were used for validation and test, respectively. For the inductive learning task, used protein-protein interac- tion (PPI) dataset (Hamilton et al. (017) consisting of graphs of different human tissues. The dataset has 20 training graphs and 2 validation and test graphs each. Also, the graph of the PPI dataset can have multiple class labels. Details of the number of nodes, edges, features, and classes in the dataset given in Table

---

Under review as a conference paper at ICLR 2023
Table 3: The accuracy of GCN, GCNII, GAT, and SGC
Cora, CiteSeer, and PubMed datasets.
Network
Cora
CiteSeer
PubMed
GCN
82.40
71.60
78.90
GCNII
83.40
73.40
78.40
GAT
81.90
71.30
78.80
SGC
79.80
72.00
76.90
All networks implemented in Python with Py (Paszke al. 2019) and PyG (Fey & Lenssen (019)), and all computations were performed on cluster equipped with Intel Xeon Gold 6240R (2.4GHz, 48C) CPUs, NVIDIA 3090 GPUs, and operating system CentOS 7.8.
4.1 TRANSDUCTIVE LEARNING
Transductive learning is type of semi-supervised learning, i.e., given the nodes and edges of the graph, the network is trained using labeled nodes, and then the unlabeled nodes are labeled. In particular, the transductive learning uses the same graph for training and testing. Thus, the transduc- tive task shows how much the adjacency matrix given graph affects the labeling performance of the network.
4.1.1 NETWORK AND HYPERPARAMETES SETUP
GCN is a two-layer model which has 16 channels for the Cora and CiteSeer datasets and 64 chan- nels for the PubMed dataset. GCNII is a model using 64 layers with 64 channels for the Cora and CiteSeer datasets and 16 layers with 256 channels for the PubMed dataset. Note that the hyperpa- rameters a and À for GCNII are 0.1 and 0.3, respectively. GAT a model using two layers with 8 headers each with 8 channels. The last layer of GAT averages the outputs of the headers and all other layers concatenate the outputs. Finally, SGC performs feature propagation twice. Note that GAT uses ELU (Clevert et al., 2015) and other networks use ReLU as the activation function.
All neural networks were trained for 200 epochs using Adam optimizer (Kingma & Ba 2014). The learning rate, weight decay, and dropout (Srivastava al. 2014) were determined to give the best performance through grid search at [0.00T, 0.005, 0.01], 00 0.0001, 0.0005), and [o, 0.4, 0.6, 0.8). respectively.
4.1.2 EXPERIMENT RESULTS
First, to verify the performance of each convolution, provide Table which shows the accuracy of given networks trained using the standard graph convolution for standard citation network bench- mark datasets. Next, compare the performance of the proposed substructured graph convolution with the additive method and the alternating method. Table shows numerical results all of the previously mentioned methods applied PubMed datasets. First of all, as N increases, the overall accuracy decreases regardless of the net- work and dataset. In particular, in the cases of N 32 and 64, it can be seen that the accuracy of the additive and alternating methods is much lowered because the edge-cuts of the given graph are very large. On the other hand, the substructured graph convolution shows that the decrease in accuracy is small as N increases compared to the additive and alternating methods. Moreover, in certain cases, substructured graph convolution shows better performance than standard graph convolution. This shows that adding the information of the interface part is properly reflected in the network and helps to improve accuracy.
GCN, GCNII, GAT, and SGC with Cora, CiteSeer, and
4.2 INDUCTIVE LEARNING
The inductive learning task is supervised learning. The biggest difference from the transductive learning is that the graphs for testing are different from the training graphs. If the adjacency matrix of the training graph is block diagonal, the trained network learns the block diagonal shape, is

---

Under review as a conference paper at ICLR 2023
Table 4: The accuracy of GCN, GCNI,, GAT, and SGC equipped with additive (AD), alterntt- ing (AL), and substructuring (SS) for the Cora, CiteSeer, and PubMed datasets, where N denotes the number of subgraphs.
Network
Type
N
Com
CaeSear
PalMed
Network
Type
N
Cors
Ciickeor
PuhMol
Networkk
Type
N
Ciers
CieeSerr
Puiibed
80.60
71.00
79:00
AD
79.90
71.40
78.90
AD
79.20
71.60
77.20
GCN
80.00
79.10
GCN
78.10
GCN
71.90
80.30
78.30
78.90
72.20
78.30
79.90
72.00
75.00
82.30
70.30
73.00
AD
51.00
72.50
17.00
AD
32.60
73.20
76.30
GCNI
82.30
77.10
GUNI
80.90
78.20
OCNI
83.20
69.00
75.00
83.60
79.30
82.60
55
82.20
73.90
AD
81.30
70.90
75.40
AD
4
79.50
69.90
78.50
AD
$0.80
69.00
76.20
GAT
80.70
78.10
GAT
4
80.20
GAT
82.00
68.30
81.50
78.30
81.60
78.70
55
70.60
AD
76.50
71:70
76.90
AD
78, .0
70:40
77.20
AD
79.30
71.30
76,50
SGC
14.30
75.20
SGC
73.60
SGC
23.70
79.30
72,00
77.20
79.70
71,90
SS
72.20
78.70
Network
Type
Com
ChteSeer
PuhMell
Network
Type
N
Cora
CheeSvr
PuhMiod
Network
Type
Cor
ChecSorr
PubMMrd
AD
16
90.10
71.10
77.40
AD
32
79.10
70.00
78,
AD
64
78.40
67.50
78.10
GCN
AL
16
$1.440
72.10
77.30
GCN
AL
32
78, 10.10
71.50
78.60
GCN
AL
64
76.10
70,50
76.30
SS
16
90.20
72:30
79.00
SS
32
90.29
72,80
78.60
8S
64
81.20
72,00
78.60
AD
16
30.40
72.70
75.20
AD
32
$1.00
73.00
74,80
AD
64
79.30
71.00
76.00
GONI
AL
16
91.60
70:00
77:20
GUNII
Al.
32
K1.50
55.40
76.70
OCNI
AL
64
78.30
45.30
77.60
88
16
94.60
72.70
80.90
88
32
83.50
73,00
90.20
SS
64
83.80
75.30
$1.10
AD
16
80.40
70.70
77:50
AD
82
77.20
69.90
77.80
AD
64
77.10
60:20
77.20
GAT
AL.
16
75:500
71..00
76.80
GAT
A1.
32
79:70
68:80
73.90
GAT
AL.
64
76.30)
69:30
77.30
55
16
81.10
71.90
80.00
55
32
82.20
70.00
79.10
S5
64
83.00
70.60
79.80
AD
16
77.80
71.50
75.90
AD
32
77.50
77.00
11.50
96,20
AD
64
77.40
70.50
75.00
S0C
AL
16
74.00
17.90
SGC
A1.
72. 00
80
SGC
AL
64
61.40
65
21.90
55
16
79.50
72,99
78.70
55
32
79.70
72.50
78.40
55
64
30.40
72.10
78,80
difficult to expect labeling performance for a general graph. Thus, the inductive learning task shows the effect of reflecting the interface information on the generalizability of the network.
4.2.1 NETWORK AND HYPERPARAMETE SETUP
GCN is a three-layer model which has 1, 1.024-channel layers with skip-connections (He al. 2016). GCNII is model using 9 layers with 2,048 channels. Note that the hyperparameters and X for GCNII are set to 0.5 and 1.0, respectively. GAT is a model using three layers with 4 headers each with 256 channels. Also, the skip-connection is used in GAT. Finally, SGC performs feature propagation three times. GCN and GAT used ELU as the activation function, and the rest used ReLU. The optimizer and hyper parameters for training were set in the same way in Section 4. In addition, the network was trained using a total of 20 PPI training graphs, one at a time, and the sequence of training graphs is shuffled every epoch.
4.2.2 EXPERIMENT RESULTS
Similar to the transductive learning task, we compare the proposed substructured graph convolu- tion with the additive and alternating methods. Note that F1-scores for the PPI datasets of GCN, GCNII, GAT, and SGC trained using the standard graph convolution are 99.06, 89.79, 99.33, and 76.10, respectively. The numerical results Tablee5]cnniin confirm that the proposed substructured graph convolution performs better than other methods even on inductive learning tasks. In particular, the other two methods show that the Fl-score drops sharply as N increases, whereas the substructured graph convolution shows little change in the Fl-score. In other words, it can be seen that the form of the adjacency matrix of the graph used for training is important for the generalizability of the network. The adjacency matrix used in the additive method and the alternating method is in the form of a block diagonal excluding the interface part, and it can be seen that the interface adjacency matrix plays a large role in the generalizability of the network. In addition, it can be confirmed that the proposed substructured graph convolution improves the performance of the network by using the interface adjacency matrix appropriately in the inductive learning task as in the transductive learning task.
5 CONCLUSION
In this paper, we proposed a novel substructured graph convolution that is suitable for parallel com- putation and robust with respect to large numbers of subgraphs. Since the additional structure
8

---

Under review as a conference paper at ICLR 2023
Table 5: Fl-scores of GCN, GCNII, GAT, and SGC equipped with additive (AD), alternating (AI.), and substructuring (SS) for the PPI dataset, where N is the number of subgraphs.
Network
Type
N
PPI
Network
Type
N
PPI
Network
Type
N
PPI
AD
2
97.97
AD
4
94.34
AD
8
91.70
GCN
AL
2
98.17
GCN
AL
4
95.10
GCN
AL
8
92.49
SS
95.68
SS
4
96.52
8
96.87
AD
2
87.78
AD
85.00
AD
8
91.70
GCNII
AL
2
88.20
GCNII
AL
4 84.89
GCNII
AL
8
92.49
SS
2
87.29
SS
4
88.55
SS
88.76 8
AD
2
98.20
AD
4
93.48
AD
8
90.39
GAT
AL
2
98.42
GAT
AL
94.31
GAT
AL
8
91.13
SS
2
98.29
SS
4
98.66
SS
98.52 8
AD
2
75.29
AD
4
75.00
74.83
SGC
AL
2
75.79
SGC
AL
4
75.07
SGC
AL
8
74.90
SS
2
75.05
SS
4
75.25
SS
8 75.26
Network
Type
N
PPT
Network
Type
N
PPT
Network
Type
N
PPT
AD
16
88.39
AD
32
85.96
AD
64
84.24
GCN
AI.
16
89.68
GCN
AI.
32
78.82
GCN
AL
64
73.88
SS
16
96.61
SS
32
96.18
SS
64
95.58
AD
16
82.18
AD
32
81.56
AD
64
80.84
GCNII
AL
16
79.78
GCNII
AL
32
78.13
GCNII
AL
64
76.43
SS
16
88.30
SS
32
88.16
SS
64
85.33
AD
16
86.72
AD
32
83.55
AD
64
81.62
GAT
AL
16
75.88
GAT
AL
32
72.73
GAT
AL
64
73.24
SS
16
98.38
SS
32
98.41
SS
64
98.49
AD
16
74.72
AD
32
74.65
AD
64
74.60
SGC
AL
16
74.83
SGC
AL
32
74.71
SGC
AL
64
74.68
SS
16
75.27
SS
32
75.20
SS
64
75.10
quires little computation and has no parameters, the proposed graph convolution does not cause large bottleneck in parallel computation. We have experimentally shown that this novel graph convolution can train networks more effectively than additive and alternating methods. It also out- performed the standard graph convolution in certain cases. We expect that the proposed graph convolution can be efficiently utilized to train large graph datasets through multiple GPUs.
REFERENCES
Ching Avery. Giraph: Large-scale graph processing infrastructure on hadoop. Proceedings of the Hadoop Summit. Santa Clara, 11:5 2011.
James H Bramble, Joseph Pasciak, and Alfred H Schatz. The construction of preconditioners for elliptic problems by substructuring. I. Mathematics of Computation, 47:103-134 1986.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representatiinss, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In Proceedings of the 37th International Conference Machine Learning, volume 119, pp. 1725-1735. PMLR, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-GCC An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery and data mining, pp- 257-266. 2019.

---

Under review as a conference paper at ICLR 2023
Djork-Amé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (ELUs), 2015.
07289
Victorita Dolean, Pierre Jolivet, and Frédéric Nataf. An introduction to domain decomposition meth- ods: algorithms, theory, and parallel implementation. SIAM, Philadelphia, 2015.
Charbel Farhat and Francois-Xavier Roux. A method of finite element tearing and interconnecting and its parallel solution algorithm. International Journal for Numerical methods in Engineering, 32:1205 12:1205-1227, 1991.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with Py PyTorch Geometric. In ICLR Workshop Representation Learning on Graphs and Manifolds, 2019.
Lee Giles, Kurt D Bollacker, and Steve Lawrence. Citeseer: An automatic citation indexing system. In Proceedings of the third ACM conference Digital libraries, pp. 89-98, 1998.
Joseph E Gonzalez, Yucheng Low, Haijie Gu, Danny Bickson, and Carlos Guestrin. PowerGraph: Distributed graph-parallel computation on natural graphs. In 10th USENIX Symposium on Oper- ating Systems Design and Implementation, pp. 17-30, 2012.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, 30, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 770-778, 2016.
Jie Hu, Li Shen, and Gang Sun. Squeere-and-Fxcitatin Networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 7132-7141, 2018.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal on Scientific Computing, 20:359-392, 1998.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, 2014. URL
https::/ /aarxvivvv.v..////v/ org/ abs//aas///a/ 1412. 6980
Thomas N Kipf and Max Welling. Sumi-super classification with graph convolutional net-
works. In International Conference on Learning Representations, 2017.
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3: 3:127-163, 2000.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. PyTorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32, 2019.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. DeepWalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710, 2014.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15:1929-195 1958,, 2014.
Andrea Toselli and Olof Widlund. Domain Decomposition Melhoad--Agorrihms and Theory. Springer, Berlin, 2005.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances Neural Informa- fion Processing Systems, 30, 2017.
10

---

Under review as a conference paper at ICLR 2023
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning. volume 97, pp. 6861-6871. PMLR, 2019.
Shiwen Wu, Fei Sun, Wentao Zhang. Xu Xie, and Bin Cui. Graph neural networks in recommender systems: survey, ACM Comput, Surv., 2022. Just Accepted.
Shunxin Xiao, Shiping Wang, Yuanfei Dai, and Wenzhong Guo. Graph neural networks in node classification: survey and evaluation. Machine Vision and Applications, 33:1-19, 2022.
Zhilin Yang. William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on Machine Learning, volume 48, pp. 40-48, PMLR, 2016.
Rui Ye, Xin Li, Yujie Fang, Hongyu Zang, and Mingzhong Wang. A vectorized relational graph convolutional network for multi-relational network alignment. International Joint Conference on Artificial Intelligence, pp. 2,,,4111,,019
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learn- ing Representations, 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances Neural Information Processing Systems, 31, 2018.


Reviews:
[{"review_id": "tU_9DX21hXC", "reviewer": "Reviewer_Tixk", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper introduces how to train GNNs using non-overlapping decomposed graphs,  in order to scale GNNs to larger graphs and to obtain better performance.", "summary_of_the_review": "In summary, the concerns about novelty, technical depths, and experiment evaluation outweigh the merits.", "strength_and_weaknesses": "Strengths:\n\n1. The implementation details are described clearly, providing better reproducibility.\n2. The presentation is clear.\n\n\nI have the following concerns about the paper:\n\n1. The novelty of the proposed method, i.e., use METIS to partition the graph then training GNNs over them, is a bit limited. e.g., [1] ClusterGCN shares similar core ideas.\n2. The technical depth is a bit limited. It would be better if the authors can provide better decomposition/partition method more suitable for GNN training, or provide better insights about the information loss or the usage of the `interfaces`.\n3. Although in the abstract the authors stated the motivation is to deal with large graphs, the experiments are limited to small-size graphs.\n\n\n\n[1] Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks, Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, Cho-Jui Hsieh, SIGKDD 2019", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "aBIpUHC2JK", "reviewer": "Reviewer_TgT5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "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": "The paper is concerned with the scalability of training GNNs on large graph datasets where there may not be sufficient memory to store the graph structure. The basic idea is to decompose the graph into smaller components. The paper builds upon the earlier works such as (Chiang et al., 2019), which uses METIS to decompose a large graph into non-overlapping components and employs the alternating method to train the graph components and combine the results. In this paper, the authors basically also utilize the \"residual\" graph component (after the decomposition), the so-called \"interface adjacency matrix\", and construct a new (normalized) graph for simultaneous training. Experiment results show that the proposed method performs better than existing methods. ", "summary_of_the_review": "The paper builds upon the earlier works such as (Chiang et al., 2019), which uses METIS to decompose a large graph into non-overlapping components and employs the alternating method to train the graph components and combine the results. In this paper, the authors basically also utilize the \"residual\" graph component (after the decomposition), the so-called \"interface adjacency matrix\", and construct a new (normalized) graph for simultaneous training. While experiment results show that the proposed method performs better than existing methods, the proposed method is rather ad hoc without any mathematical justification. Perhaps more importantly, it requires a lot of more memory than existing methods based purely on  non-overlapping graph decomposition", "strength_and_weaknesses": "Strength:\n\n  + Addressing scaling of GNN training on large graphs.\n\n\nWeaknesses:\n   - With the use of the so-called \"interface adjacency matrix\", albeit in general sparser than the original matrix, still requires O(n) memory to store it. If n is larger than the available  memory, the proposed method will not work, whereas the decomposition methods such as (Chiang et al., 2019) requires only O([n/N]^2) memory to store individual graph components.\n   - The proposed method is rather ad hoc. There is no attempt in mathematically justification the proposed method.\n   ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4floIP-5_m", "reviewer": "Reviewer_zYgm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a way to improve performance of GCN when decomposing graph. To reduce GCN complexity on large graphs, a graph can be decomposed into non-overlapping subgraphs. GCN is then can be trained only on these subgraphs, ignoring the \"interface links\" that connect between subgraphs. To reduce information loss due to ignoring the interface links, the paper proposes to train GCN on both subgraph and interface part (SS method). The output is then a weighted average of the node features obtained by subgraph and interface part.\n", "summary_of_the_review": "The proposed SS method for training GCN on non-overlapping decomposed graph has unclear benefit.", "strength_and_weaknesses": "Strength:\n  - The paper is well-written with good notations, figures, and pseudo codes.\n\nWeaknesses:\n  - The paper only compares result of the new method (SS) against other learning scheme on decomposed graph (AD and AL). Both AD and AL ignores the links between subgraphs, so it's obvious for SS to have prediction performance advantage. The paper does not study the increase in computation and memory cost though. Saving computation and memory cost is the main reason why graph decomposition is needed in the first place. I believe SS method reduces that benefit significantly.\n  - It is unclear why the weighting formula is proposed that way. The author says to \"minimal communication and computation cost\" between subgraph and interface features, which I don't know what that actually means.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject