Redundancy-Free Computation Graphs for Graph Neural Networks
Authors: Zhihao Jia
Sina Lin
Rex Ying
Jiaxuan You
Jure Leskovec
Alex Aiken.
Venue:  (2020)
Keywords: Graph Neural Networks
Runtime Performance

Abstract: Graph Neural Networks (GNNs) are based on repeated aggregations of information across nodes’ neighbors in a graph.  However, because common neighbors are shared between different nodes, this leads to repeated and inefficient computations.We propose Hierarchically Aggregated computation Graphs (HAGs), a new GNN graph representation that explicitly avoids redundancy by managing intermediate aggregation  results  hierarchically,  and  eliminating  repeated  computations  and unnecessary data transfers in GNN training and inference. We introduce an accurate cost function to quantitatively evaluate the runtime performance of different HAGsand use a novel search algorithm to find optimized HAGs.  Experiments show that the HAG representation significantly outperforms the standard GNN graph representation by increasing the end-to-end training throughput by up to 2.8x and reducing the aggregations and data transfers in GNN training by up to 6.3x and 5.6x. Meanwhile, HAGs improve runtime performance by preserving GNNcomputation, and maintain the original model accuracy for arbitrary GNNs.

Under review as a conference paper at ICLR 2020
REDUNDANCY-FREE COMPUTATION GRAPHS FOR GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) are based on repeated aggregations of information across nodes' neighbors in graph. However, because common neighbors are shared between different nodes, this leads to repeated and inefficient computations. We propose Hierarchically Aggregated computation Graphs (HAGs), graph representation that explicitly avoids redundancy by managing intermediate aggregation results hierarchically, and eliminating repeated computations and unnecessary data transfers in GNN training and inference. We introduce an accurate cost function quantitatively evaluate the runtime performance of different HAGs and use a novel search algorithm to find optimized HAGs. Experiments show that the HAG representation significantly outperforms the standard GNN graph representation by increasing the end-to-end training throughput by up to 2.8 and reducing the aggregations and data transfers GNN training by up to 6.3 and 5.6x. Meanwhile, HAGs improve runtime performance by preserving GNN computation, and maintain the original model accuracy for arbitrary GNNs.
GNN
INTRODUCTION
Graph neural networks (GNNs) have shown state-of-tte-art performance across a number of tasks with graph-structe data, such as social networks, molecule networks, and webpage graphs (Kipf and Welling 2016 Hamilton et al. 2017, Ying et al.) [218]] Xu et al.) 2019). GNNs use a recursive neighborhood aggregation scheme - in GNN layer, each node aggregates its neighbors' activations from the previous GNN layer and uses the aggregated value to update its own activations. The activations of the final GNN layer are used for downstream prediction tasks, such as node classification, graph classification, link prediction.
Due to the clustering nature real-world graphs, different nodes in a graph may share a number of common neighbors. For example, in webpage graphs, different websites under the same domain generally have a number of common links (i.e., neighbors). As another example, in recommender systems, users in the same group may have interests common items.
However, existing GNN representations do not capture these common neighbors in real-world graphs, leading redundant and unnecessary computation in both GNN training and inference. In partieular, most existing GNN models (Kipf and Welling 2016 Xu et al., 2019 Wu et al., 2019) use the full-batch training method that computes the activations for all nodes each layer. Existing GNN representations use computation graph (referred to as GNN-graph) to define computation in GNN layer. The GNN-graph includes a tree structure for each node in the input graph describing how to compute v's activations by aggregating the previous-layer activations of u's neighbors. Figure Tp shows the GNN-graph of the input graph in Figure [ for example, for node A, its
neighbor's activations h he (k-1) and h from the layer k - 1 are aggregated to compute
new activations (k) for the layer i (see the top portion of Figure (p). The new activations of the other nodes are computed similarly using the previous activations of their neighbors. Notice that this representation results redundant computation and data transfers. In this small example, both B) and {C, D) are aggregated twice. In wider and multi-layer GNNs, the redundancies in existing GNN representations account for a significant fraction of all computation. For example, our experiments show that in modern GNNs up to 84% of the aggregations are redundant and avoidable.
In this paper, we propose a new GNN representation called Hierarchically Aggregated computation Graphs (HAGs). Figure Th shows one possible HAG for the input graph in Figure Tp. HAGs

---

Under review as a conference paper at ICLR 2020
A5 -
AC
A
B
Ag
R--1
C
C
A
D
ACD
B
A
8
B
B
C
A
A AB
A
A
(i) Inpul graph
(b) GNN-graph
(c) HAG
Figure 1: Comparison between a GNN-graph and an equivalent HAG. (a) Input graph; (b) 1-layer GNN computation graph (GNN-graph); (c) HAG that avoids redundant computation. The GNN- graph computes new activations h by aggregating the previous-layer activations of v's neighbors. Because nodes in the input graph share common neighbors, the GNN-graph performs redundant computation (e.g., both {A, B] and D) are aggregated twice). (c) By identifying common computational patterns, the HAG avoids repeated computation.
functionally equivalent to standard GNN-graphs (produce the same output), but represent common neighbors across different nodes using aggregation hierarchies, which eliminates redundant putation and unnecessary data transfers both GNN training and inference. In addition, a HAG is agnostic to any particular GNN model, and can be used eliminate redundancy for arbitrary GNNs.
For a GNN-graph, there exist numerous equivalent HAGs with different aggregation hierarchies and runtime performance. We introduce an accurate cost function to quantitatively estimate the performance of different HAGs and develop novel HAG search algorithm to automatically find optimized HAGs.
Theoretically, we prove that the search algorithm finds HAGs with strong performance guarantees: (I) for GNN models whose neighborhood aggregations require a specific ordering on a node's 's neighbors, the algorithm finds globally optimal HAG under the cost function; and (2) for other GNN models, the algorithm finds HAGs whose runtime performance is at least a (1 1/e) approximation ( 63%) of globally optimal HAGs using the submodularity property (Mossel and Roch 2007). Empirically, the algorithm finds HAGs that lead to major improvements, reducing the runtime by up to 2.9x.
Our HAG abstraction maintains the predictive performance of GNNs but leads to much faster training and inference. We evaluate the performance of HAGs on five real-world datasets and along three dimensions: (a) end-to-end training and inference runtime; (b) number of aggregations; and (c) size of data transfers. Experiments show that HAGs increase the end-to-end training and inference performance by up 2.8x and 2.9x, respectively. In addition, compared reduce the number of aggregations and the size of data transfers by up to 6.3 x and 5.6x, respectively.
GGNNggraple HAGs
RELATED WORK
Graph neural networks have been used solve various real-world tasks with relational struc- tures (Kipf and Welling 2016: Hamilton et al., 2017; Ying et al.) 2018 Xu et al.) 2019). Fast- GCN (Chen et al.] 2018) and SGC (Wu et al. 2019) accelerate GNN training using importance sampling and removing nontinearilities. This paper solves orthogonal problem: how to optimize GNN efficiency while maintaining network accuracy. Our methods can be applied automatically to climinate redundancy for arbitrary GNN models.
Join-trees are a tree decomposition technique that maps a graph into corresponding tree structure to solve optimization problems on the graph, such query optimization (Flum et al. 2002). Although a join-tree tree provides possible way to find optimal HAGs for a GNN GNN-graph, its time complexity is exponential in the treewidth of graph (Arnborg et al. 1987), and real graphs tend to have very large treewidths. For example, Adcock et al. (2016) shows that the treewidth real-world social networks grows linearly with the network size, making it infeasible use join-trees to find optimal HAGs.
2

---

Under review as a conference paper at ICLR 2020
Table 1: Existing GNNs described in our abstraction. GraphSAGE-P and GraphSAGE-LSTM are the pooling and LSTM variants of GraphSAGE, respectively. a and max indicate element wise non-linear activation and max functions. For sequential AGGREGATE, V2 denotes the i-th in-neighbor of node e.
GNN
AGGREGATE (IN 1/ M(v1))
UPDATE ( .N0 ")
Set ACGREGATE
GCN (Kppf and Welling 2016
LucK(v) A 1
Wo]+T
GIN XX et al.
2019
ab
LueNio 1
N. =[ ((1 MA
4 +0t o
Sequenial AGGREGATE
GCN-LSTM Hamilton et al.
2017
ab LSTM(N (1-1)
A. =W((k) -(a))) ((a6) 11b 11b--119)
N-ary Tree-LSTM Taa et al.
2015
(1 Tree-LSTM-Agg(Re (1-1
D)
R Tree-LSTM- (.--SSTM-Updat((a)) h2--1)
Computation reduction in DNNs. Several techniques have been proposed to reduce computation in DNNs, including pruning weights (Han et al. 2015) and quantization (Han et al. 2016). These techniques reduce computation the cost of modifying networks, resulting decreased accuracy (as reported in these papers). By contrast, we propose new GNN representation that accelerates GNN training by eliminating redundancy in GNN-graph. while maintaining the original network accuracy.
HIERARCHICALLY AGGREGATED COMPUTATION GRAPHS (HAGS)
Existing GNN-graph representation. An input graph G E) has nodes V and edges E. For each node v E (v) denotes the set of neighbors of v. and Te denotes the input node features. A GNN iteratively learns representations for individual nodes over the entire graph through a number of GNN lay- ers, as shown in Algorithm [ The learned
Algorithm 1 An abstraction for GNNs. V is the set of nodes in an input graph, and ((v)) denotes the set of neighbors for node
1: h, Tu, Ve E V
2:
for k 1 to K do
3:
for v do
4:
ag + AGGREGATE 1Iu (()))) (.( UPDATE(A (k) hhe 1)
activations of node v at layer is (R) and we initialize ( with z.. At the k-th layer, (1) av denotes the aggregated activations u's neighbors, which is combined with he (k-1) to compute an updated activation h The learned node activations of the final layer (i.e., 1. are used for downstream learning tasks, and a GNN model generally minimizes a loss function L that takes the final node activations as inputs (line 6).
5:
6: Goal: minimize (((1))) (V)
Existing GNN models use a GNN computation graph (GNN-graph) describe the computation in each GNN layer, as shown in Figure Lp. For each node in the input graph, the GNN-graph includes an individual tree structure define how to compute the activations ( of node by aggregating the previous-layer activations of v's neighbors (i.c., { (k-)) u E (N)))) GNN-graphs are efficient expressing direct neighborhood relations between nodes, but are not capable of capturing common
neighbors across multiple nodes, leading to redundant computation in GNN training and inference.
3.1 HAG REPRESENTATION
We propose new graph representation called Hierarchically Aggregated computation Graphs (HAGs) for GNNs. HAGs climinate redundancy in the GNN-graph representation by hierarchically managing and reusing intermediate aggregation results. A HAG Č = (V,,) has nodes ÿ = VUU, and edges ε, where V is the set of nodes in the original graph, and VA is new set of aggregation nodes. Each aggregation node in VA represents the intermediate aggregations result for subset of nodes (i.e., aggregation on subset of 1. ((-1)). For the HAG example in Figure | the new nodes AB and CD denote the aggregation results of [A, B} and (C, D). respectively. A HAG can contain multi-level aggregation hierarchy. For example, Figure Th can also have third aggregation node ABCD that depends on AB and CD. Similar to edges in GNN-graphs, an edge (u, v) in a HAG denotes aggregation relation computing v's activations requires aggregating u's activations.
The standard GNN graph representation can be considered as a special case in the HAG representation with no intermediate aggregation nodes (i.e.. VA 0). Our HAG abstraction is general and applicable to many existing GNN models. Table shows how to use our abstraction to define existing GNNs, which can be further divided into two categories.
3

---

Under review as a conference paper at ICLR 2020
Set AGGREGATE. Most GNNs assume the neighbors of node have ordering, and the aggrega- tions are associative and commutative operations that are invariant to the order which the aggre- gations performed. Examples include GCN with summation aggregations and GraphSAGE-P with element-wise pooling aggregations (Table T Note that set aggregations in GNNs are designed do in HAGs.
to be order invariant and thus be performed in hierarchical fashion
Sequential AGGREGATE. Another class of GNNs require specific ordering of node's neighbors and the aggregations are not commutative. Examples include Nary Tree-LSTM (Tai et al. 2015)
and the LSTM variant of GraphSAGE (Hamilton et al. 2017). HAGs can be applied the case of sequential aggregations as well. Rather than identifying common subsets of neighbors, we identify the common prefixes of the sequence of aggregated nodes, which can then be reused among nodes.
We further define two properties for the aggregation nodes VA- First, for each v E VA Fg denotes its intermediate aggregation result, and (V)) denotes the in-neighbors of node v. To capture the aggregation hierarchy a HAG, we use a recursive function to define ā..
(k-1)
E V u uE VA
T. = AGGREGATE
"EN(o)
au
Second, C(:) denotes the set of input activations li! (k-1) used compute ā, in the recursive procedure.
ā AGGREGATE (( 1) ((v)))
Intuitively, C(v) defines the coverage of node in HAG. For the HAG example in Figure I (k)
Č(A) {B,C, because hB (k-1) he (k-1) and h (k-1)
are used as inputs to compute h
For set AGGREGATE, Č(-) is an unordered set:
C(v) U
u u V ((u)
(3)
We VA
(E)())
For sequential AGGREGATE, Ō(.) is an ordered list:
((u) (Č(uz), C(um))
(4)
where uI,... Um are the ordered in- in-neighbors of v.
3.2 GNNS WITH HAGS
We extend the GNN abstraction to make it also applicable HAGs, as shown in Algo- rithm 2 The extension does not require any modification to GNN model, and the only difference is how to compute neighborhood
Algorithm 2 GNN abstraction with HAGs. We exclude layer index superscripts in ã to denote that ā does need be memoized for back prop- agation, and its memory can be reused across all layers.
aggregations (i.e., ar (k) in each GNN layer. Before the original aggregations, we add one
1:
u. Ve V k to do for o E VA do
step that precomputes commonly used inter-
2:
mediate aggregation results to reduce redun-
3:
dant computation. In Algorithm [ we first
4:
compute âo using Equation I for v E V do
compute a for all aggregation nodes VA (line
5:
6:
a < AGGREGATE( (ā., lu N..)) (4) + UPDATE(( (K) (Kk (k-11))
3-4). This is performed recursively follow-
ing the aggregation hierarchy of the HAG. We then compute the neighborhood aggregations
7:
(k)
(line 5-6) using the precomputed intermediate aggregations a...
Memory overhead. Although Algorithm 2 includes new intermediate variables a,, the memory overhead for storing ā is negligible since a,, is not used for back propagation and can be saved in a constant memory across all GNN layers. the experiments, we show that HAGs can increase the training throughput by 2.8x, while maintaining the original model accuracy at the cost of 0. % memory overhead to save a,.. Meanwhile, storing a HAG representation requires less memory than the original GNN-graph, HAGs generally contain much fewer edges.
4

---

Under review as a conference paper at ICLR 2020
Equivalence between GNN-graphs and HAGs. We define GNN-graph and HAG to be equiv- alent they produce the exact same outputs and gradients for GNN model. Formally, a GNN graph G and HAG 9 are equivalent for GNN model if (1) the GNN model outputs the same activations (i.e., ) each GNN layer, and (2) the GNN model computes the same gradients for all trainable parameters in back propagation. Equivalent graphs guarantee the same predictive performance, and therefore can be used interchangeably for both GNN training and inference. Theorem I provides simple yet efficient condition to check graph equivalence. We prove the theorem in the Appendix.
Theorem 1. GNN-graph with nodes V and a HAG with nodes (V, VA) are equivalent if and only (()) C(u) for all v E V, where (v) is v's neighbors in the input graph and C(-) is defined in Equation Band 4
HAG SEARCH ALGORITHM
For GNN model and an input GNN- there exists large space of equivalent HAGs with the same model accuracy but various runtime performance. Our goal is to explore the search space to discover a HAG with optimized runtime performance. First. we define a realistic cost function to quantitatively evaluate the runtime performance of different HAGs. Second, we introduce an efficient search algorithm that finds an optimized HAG with the following guarantees:
For GNNs with sequential AGGREGATE, the HAG search algorithm find globally optimal HAGs under the cost function.
For GNNs with set AGGREGATE, finding an optimal HAG is NP-hard by a reduction from the NP-hard maximum coverage problem (see Appendix for the proof). The search algorithm finds at least a (1 -pproxaiionnnaatinn globally optimal HAGs based on the submodularity property.
4.1 COST FUNCTION
We introduce cost function that estimates the runtime performance of a HAG by measuring the computation cost to perform one epoch of GNN training on the HAG.
The computation cost of GNN model includes aggregating the neighbors of each node by calling AGGREGATE and updating the activations of each node via UPDATE, as shown in Algorithm For GNN model M, we assume the cost of performing AGGREGATE on two elements is a,M, and the
cost of computing an UPDATE is 9M. In Algorithm 2. computing ā with [W,] neighbors requires performing (o 1) binary aggregations, whose cost is am x (I - 1). Therefore, the total computation cost of training GNN model M HAG Č is
cost(M M, 9) = Σ
a. - 1) + Σ
BM = a (1ε) - IVAl) + -B8M - aa
DEVUVA
eEV
Since |V| is determined by the input graph, our goal is to minimize (181-17 -DA
4.2 SEARCH ALGORITIM
We present a HAG search algorithm that finds a globally optimal HAG for GNNs with sequential AG- GREGATE and a (1 -
(1 -pprroxaxxinnooonn of globally optimal HAGs for GNNs with set AGGREGATE. In addition to an input GNN-graph and a GNN model, the algorithm also takes a hyper-parameter capucity, defining an upper limit on the number of intermediate aggregation nodes (i.e., Val).
Algorithm 3 shows the pseudocode of the HAG search algorithm. We start with an input GNN- and iteratively insert aggregation nodes into the current HAG merge highly redundant aggregations and remove unnecessary computation and data transfers.
In each iteration, we find binary aggregation with the highest redundancy and insert new aggrega- tion node w in VA to represent the binary aggregation results (line 12-15). All nodes containing this binary aggregation can directly use the output of without recomputing the aggregation (line 16- 18-. The search algorithm iteratively reduces the computation cost of the HAG by eliminating the most redundant aggregation in each iteration. The redundancy scores are maintained in heap structure.
5

---

Under review as a conference paper at ICLR 2020
Algorithm 3 A HAG search algorithm to automatically find an equivalent HAG for GNN-graph with optimized runtime performance. E and VA are the set of edges and aggregation nodes in the HAG. REDUNDANCY(11, v2, 8) calculates the number of nodes aggregating both ii and U2. Recall that C(u) is an ordered list for sequential AGGREGATE (see Equation
1: Input: A GNN-graph and GNN model M.
Output: An equivalent HAG with optimized performance
3: function REDUNDANCY(0) 12: E)
if. has set AGGREGATE then
5: R = {u](v), u) E (v2, u) E E
6: else
7:
{u|m1 C(u) A2 [(4)
8:
return [R]
9:
10: VA 3
while [Val capacity do
12:
(V1, 02) = arg max,,, 22 REDUNDANCY(01, 02,
13:
if REEDDNDANCY((1) U2 E) > VA + Va + {w} 6 E. + (v1,w) (v2,
then
14:
b. where w a new node
15:
16:
for E V do
17:
if (V1, u) E E.A (U2, u) E then
18:
ELE
(v,,u) (u2, u) (w,u)
19:
return (VA,
For GNN model with sequential AGGREGATE, Theorem an equivalent HAG with globally optimal computation cost. We prove the theorem in Appendix.
2 shows that our search algorithm finds
Theorem For any GNN-graph G (V, 8) and any GNN model M with a sequential AGGREGATE,
Algorithm 3 returns an equivalent HAG with globully minimum cost as long capacity 2 [8).
For a GNN model with set AGGREGATE, Theorem 3 shows that our search algorithm finds a HAG that is at least
1 //e-aopproxiitioon of the globally optimal HAGs (see proof in Appendix).
Theorem 3. For any GNN- graph G and GNN model M with set AGGREGATE, Algoritlum gives (1 - 1f))-//ppoooimattiiii of globally optimal HAGs under the cost function. Formally, let G be the HAG returned by Algorithm and Go is a globally optimal HAG under the capacity constraint,
cost(M, cost((MM
cost(MM
Time and space complexity. Our HAG algorithm achieves low theoretical complexity and has negligible runtime overhead. particular, the overall time complexity of Algorithm Ocapacityy x [V] + |8| x log [V]), and the space complexity is O(capaccity x [V] + (ε]) (see Appendix for the proof). One key optimization a heap data structure for maintaining the redundancy scores of the highest O(VVl) node pairs. Finding the most redundant node pair over the entire graph thus only takes O(1) time, and updating the redundancy scores (i.c., line 15 and 18) each takes O(log [V]) time.
EXPERIMENTS
The HAG representation maintains the predictive performance of GNNs but has much better run- time performance. This section evaluates the runtime performance of HAGs on five real-world graph datasets. We evaluate HAGs along three dimensions: (a) end-to-end training and inference performance; (b) number of aggregations; and (c) size of data transfers.
5.1
IMPLEMENTATION
Existing deep learning frameworks such as TensorFlow and PyTocch are designed for spatial data structures (e.g., images and text), and have limited support for irregular data structures such graphs.

---

Under review as a conference paper at ICLR 2020
As result, GNN models in existing frameworks translate graph structures to sparse adjacent matrices and use matrix operations to perform GNN training.
We implemented the following operations in TensorFlow r1.14 to support GNN training with HAGs. First, graph to hag automatically transforms an imput GNN-graph to an equivalent HAG with optimized performance. Second, hag wagg.aggregate takes HAG and nodes' activations inputs, and computes the aggregated activations all nodes. Finally, aag.aggregate. -araaddeerrdddee computes the gradients of haw.aagaaa.. aaggregagg for back propagation. Our implementation minimizes changes to existing GNN programs: a GNN application can directly use all HAG optimizations by only modifying few lines of code.
5.2 EXPERIMENTAL SETUP
Datasets. Table 2 summarizes the public
Table 2: Datasets used in the experiments.
datasets used in our experiments. BZR is chemical compound dataset, where each node an atom and an edge is chemical bond be-
Name
# Nodes
# Edges
Node Classification
BZR
6,519
137,734
tween two atoms (Kriege and Mutzel 2012). PPI contains number of protein-proteie inter- action graphs, each of which corresponds different human tissue (Zitnik and Leskovec 2017). REDDIT is online discussion forum dataset, with each node being a Reddit post and each edge being commenting relations. For both PPI and REDDIT, we directly use prepossessed data from Hamilton et al. (2017). IMDB and COL- LAB are collaboration datasets for graph classification (Yanardag and Vishwanathan 2015). IMDB is a movie collaboration dataset, with each node representing an actor/actress, while COLLAB a scientific collaboration dataset, with each node representing a researcher.
PPI
56,944
1,612,348
REDDIT
232.965
114,615,892
Graph Classification
IMDB
19,502
197,806
COLLAB
372,474
12,288,900
All experiments were performed rumning TensorFlow r1.14 on NVIDIA Tesla V100 GPUs. Following previous work (Kipf and Welling 2016, /Hamilton et al., 2017), each GNN model has two GNN layers and one SoftMax layer. For graph classification datasets, each GNN model also includes a mean mean-pooling layer to gather graph-level activations. For all experiments, we set the maximum capacity of [VAl in HAG to be /V//4, which achieves high performance on real-world graphs.
5.3 END-TO-END PERFORMANCE
GNN-graph
HAG
first measure the per-epoch training time and
inference latency to 2-layer GCN model on different graph datasets. We follow previous work (Hamilton al. 2017 Kriege and Mutzel 2012; Yanardag and Vishwanathan, 2015) to split the datasets into trainingvalidaatoonnssiing sets, and use the testing sets to measure the av- erage inference latency.
Training Speedups
2.8x
2.5
2.1x
1.7x
1.2x
1.2x
1.
Inference
Speedups
2.9k
2.3
2.0x
2.0x
1.8k
Higure/2compane the per-epoch training time and inference latency between GNN-graphe and
1.2x
1.2x
HAGs. Compared to GNN- graphs, HAGs can improve the training and inference performance by up to 2.8x x and 2.9x, respectively, while maintaining the same network accuracy. We note this improvement is achieved completely automatically, and computing a HAG is inexpen- sive. Thus, because the improvement is essen- tially for free. we believe there is no reason not use HAGs in preference GNN-graphs.
COLLAB
Figure 2: End-to-end performance comparison be- tween GNN- ANN-graphs and HAGs. We measure the per-epoch training time and inference latency on a 2-layer GCN model with 16 hidden dimensions in each layer. The performance numbers are normal- ized by the GNN-graph numbers.
7

---

Under review as a conference paper at ICLR 2020
Relative Relstive Number Data Trensfers of Aggregation
GNN-graph
HAG
Relative Reletive Number
Aggregations
GNN-graph
HAG
1.4
97%
92%
58%
6995
.o.
5556
41%
n.2-
97%
71%
7156
5.%
4556
2995
6ZR
PPI
REDDIT IMDB COLLAS Mean
BZR PPI
REDDIT
IMD6 COLLA6
Mean
(a) Set Aggregations.
(b) Sequential Aggregations.
Figure 3: Comparing the number of aggregations and amount of data transfers between GPU threads to perform aggregations (lower is better). The y-axes are normalized by GNN-graphs, and the last column in each figure is the geometry mean over all datasets.
5.4 AGGREGATION PERFORMANCE
We further compare the aggregation performance of GNN-graphs and HAGs the following two metrics: (1) the number of binary aggregations performed in each GNN layer; and (2) the size of data transfers between GPU threads perform the aggregations. Note that aggregating neighbor's activations requires transferring the activations from GPU global memory to thread's 's local memory.
Figure shows the comparison results. For GNNs with set aggregations, HAGs reduce the number of aggregations by 1.5-6.3x and the size of data transfers by 1.3-5.6x. For GNNs with sequential aggregations, HAGs reduce aggregations and data transfers by up to 1.8x and 1.9x, respectively.
Although the search algorithm finds globally optimal HAG for sequential aggregations (Theorem) and a (1 approxxipiiiiiaooonn of globally optimal HAGs for set aggregations (Theorem 3), we observe the performance improvement is more significant for set aggregations. Optimality for HAGs with set aggregation involves more potential redundancy compared to sequential aggregations, due to permutation invariance of set aggregation. Thus higher performance be achieved with HAGs for set uggregations, though optimal solutions are more difficult to compute.
It is also worth noting that the HAG search algorithm find highly optimized HAGs even very sparse graphs. For example, on the COLLAB dataset with a graph density 0.01% our algorithm reduces the number of aggregations and data transfers by 3.3x and 2.2x, respectively.
5.5 HAG SEARCH ALGORITHM
We evaluate the performance of the HAG search algorithm. Recall that the search algorithm uses a pper-pareeeter capacity control the number of aggregation nodes in HAG. A larger capacity allows the algorithm to eliminate more redundant aggregations and achieves lower cost.
End-to End-to-end -ndend Training (6)
agu
Figure shows the end-to-end GCN training time on the COLLAB dataset using HAGs with different capacities. A larger value of capacity can consistently improve the train- ing performance, which indicates that the function is an appropriate metric to evaluate and compare the per- formance of different HAGs. By gradually increasing the capacity, the search algorithm eventually finds HAG with ~10KK aggregation nodes, which consume 6MB of mem- ory (0.1% 1% memory overhead) while improving the training performance by 2.8x. x. In addition, the HAG search time negligible compared to the end-to-end training time.
100
20K
40K
60K
80K
100K
Capacity
Figure 4: End-to-end GCN training time on the COLLAB dataset using HAGs with different capacities. We train GCN for a maximum of 350 epochs by follow- ing prior work (Kipf and Welling 2016).
Limitation. One limitation of the HAG graph representation is that it does not apply to attention- based GNN models, such as GAT (Veličković al. 2017), which uses the attention scores (Vaswani cet al. 2017) between nodes to guide activation updates and results in limited redundancy that can be optimized by HAG.
8

---

Under review as a conference paper at ICLR 2020
Conclusion. We introduce HAG, new graph representation to eliminate redundancy in GNNs. We propose a cost function to estimate the performance different HAGs and use a search algorithm to find optimized HAGs. We show that HAGs outperform existing GNN-grapha by improving the end-to-end training performance and reducing the aggregations and data transfers in GNN training.
REFERENCES
Thomas N Kipf and Max Welling. Semi- semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.00 029007 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems 30. PMLR, 2017.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances in Neural Information Processing Systems, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019.
Felix Wu, Tianyi Zhang, Amauri H. Souza Jr., Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifyinng graph convolutional networks. CoRR, abx/1902.07153, 2019, http:
org arg/abs/190 1902. 07153
Elchanan Mossel and Sebastien Roch. On the submodularity of influence in social networks. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 128-134. ACM, 2007.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. CoRR, abs/1801.10247, 2018. URL
10247
Jörg Flum, Markus Frick, and Martin Grohe. Query evaluation via tree-decompositions.. J. ACM, 2002.
Stefan Arnborg, Derek G. Corneil, and Andrzej Proskurowski. Complexity of finding embeddings in k-tree. SIAM Algebraic Discrete Methods, 1987.
Aaron B Adcock, Blair Sullivan, and Michael W Mahoney. Tree decompositions and social graphs. Internet Mathematics, 12(5), 2016.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural networks. In Proceedings of the 28th International Conference Neural Information Processing Systems, NIPS, 2015.
Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural network with pruning, trained quantization and huffman coding. CoRR, 2016.
Kai Sheng Tai, Richard Socher, and Christopher D) Manning. Improved semantic representations from tree-structured long short-term memory networks. arXiv preprint arXiv: 1503.00075, 2015.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint
arXiv: 1206::2006.644 6483, 2012.
Marinka Zitnik and Jure Leskovec. Predicting multicellular function through multi-layer tissue networks. CoRR, 0tbs/170.0044 2017.
Pinar Yanardag and S. V.N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '15, 2015.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 1710. 10903, 2017.

---

Under review as a conference paper at ICLR 2020
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pages 5998-6008 2017.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009.
A PROOF OF THEOREM
Proof. It is sufficient to prove that if (()) C(u) for all V, then the GNN-graph ç and the HAG Č generate the same outputs (i.e., ()) for every GNN layer.
We prove this by induction. Assume a GNN-graph 9 and HAG generate the same outputs for the (k-1))th layer, we prove the two graphs produce the same outputs for the k-th GNN layer.
In Algorithm 2, On is the aggregation results of node v, which is defined as
ā
AGGREGATE (h( E C(v))
AGGREGATEEM (M E (V
This proves that Algorithm I and Algorithm 2 compute the same de (k) In addition, both algorithms
use the same UPDATE function that takes (h()) and h (k]1)) as inputs and computes h(**,, which applies that the two algorithms compute the same 11
B PROOF OF THEOREM 2
Proof. Sequential aggregations require a specific ordering of a node's neighbors. Let N2 denote the ordered list of node e's neighbors and (( denote a list of the first i elements in Ng:
c (N,)))) ..... No))
where (t) is the i-th neighbor of node
c(') represents a necessary intermediate aggregation step for computing ap (since sequential aggregations are not commutative), and therefore any HAG must compute (() as intermediate aggregation. Counting the number of distinct ! (where v E V and 1 < S (W, provides lower bound on the number of aggregations any equivalent HAG must perform. Assuming Go is globally optimal HAG under the cost model, we have:
cost(M, 9.) 2 O. X lb + (8m aM)
where lb is the number of distinct c( that must be computed by any equivalent HAG.
Assuming ② is the output HAG of Algorithm we prove that cost(M, .) cost(M, (.)) by using contradiction. the case cost(M, 9) > cost[M, G.). & must perform more than aggregations.
Case 1. One possible case is that ğ computes at least one aggregation that is not prefix of any N,. indicating that & performs some useless aggregations, which contradicts with the fact that all intermediate aggregations added to & must be used at least once.
Case 2. The other possible case is that Ś computes the aggregation of some ch multiple times. However, in Algorithm 3, each iteration reduces the number of aggregations by least 1, and there are [8] aggregations initially. This implies there cannot redundant aggregations after |8] iterations, which contradicts with the precondition of Case 2.
C PROOF OF THEOREM 3
Proof. The idea of the proof is to build a monotone submodular function Cormen et al. (2009) based on the cost model.
10

---

Under review as a conference paper at ICLR 2020
For any GNN-graph G and equivalent G, we define
f()) cost(M - ccos((M,
(5)
am((E) - (Va))
(6)
where VA the of aggregation nodes in G. and and E are the set of edges in 9 and g. respectively, f()) measures the number of aggregations that can be saved by using & for GNN training.
We begin by defining the subset relations between different HAGs. For two HAGS 9 and G' we define 9 S G iff VA is a subset of VAA where VA and V'a are the aggregation nodes in & and g', respectively.
Prove that (()) monotone. We show that for all & c C. c Č' indicates that G' contains all aggregation nodes in 9. which applies that Ø can at least save the same number of aggregations as G.
(() - f(¹').
This is true since
Prove that f()) is submodular. We show that for all 3 C G and any aggregation node n, f(ğ ( ,(" + {n]) ( This inequality holds because l + {n}) (() measures the number of aggregations we can further save by adding aggregation to the existing HAG, which monotonically decreases as we add more aggregation nodes the HAG.
Let 7 denote the result HAG after the i-th iteration of Algorithm 3. G(I) includes exactly
aggregation nodes. Let Go denote the optimal HAG under the cost model with & aggregation nodes. We claim via induction that for 0 S $ k
f(O.) f(ī()) s (1 - 1/K)
The base case is trivially true. In the i-th step, Algorithm 3 selects aggregation node a; by maximizing the marginal gain f( +a;) f(g())) Observe that the remaining aggregation nodes includes Go \\ G(i-1), a set at most elements. The submodularity applies that
f(C.) f(((-1)
Σ
( + +a) - f(ğ())
and this implies that the aggregation node a; has marginal value
f(@ + a.) - ((()--1)
Σ
+a)
3. \ (01-1)
k (f(G)) - f()(i-1)))
Assuming that Inequality 7 holds for 111-1), we have
((0)))(((0)
(( 1(0v-1)) -
I f(ğ.) f()(--1) 1 ((G.) f()(1-1)) = (1 1.K) /((--11)
< (1 - 1/A))
which proves Inequality 7 Therefore, have
f(ā.) f((()) s (1 (1- f(G S se-
By taking in the definition of f(.). we have
cos(( 9) < cost(MM + e-
cos(MM go)
11

---

Under review as a conference paper at ICLR 2020
GNN-graph
HAG
GNN-graph
HAG
Inference Training Speedups
Speedups
2.
Training Speedups
1.9x
1.7x
1.2x
1.7x
1.4x
2.1x
1.8x
1.8x
3.3x
Inference Speedups
2.5x
2.3x
2.4x
1.7x
1.8x
2.0x
1.2x
1.3x
1.2x
BZR
PPI REDDIT IMDB COLLAB Mean
BZR
PPI REDDIT IMDB COLLAB Mean
(a) GIN.
(b) SGC.
Figure 5: End-to-end performance comparison between GNN-graphs and HAGs. We measure the per-epoch training time and inference latency on 2-layer GIN and a 2-layer SGC model. Both models have 16 hidden dimensions in each layer. The performance numbers are normalized by the GNN- GNN-graph numbers (higher better).
D COMPLEXITY OF THE HAG SEARCH ALGORITHM
Theorem 4. The overall time complexity of Algorithm 3 (capacity x |V] + |8| log [V), where capacity is the upper bound on the number of aggregatton nodes a HAG.
Proof. We use a heap to maintain the redundancy score of each potential node pair and only update the heap when we add and remove edges in E. Since the depth of the heap is at most Olog VI) querying the most redundant binary aggregation and modifying & each takes Olog [V]) time.
First, we calculate the number of queries and updates to the heap structure:
The algorithm iteratively pull the most redundant binary aggregation from the heap and add it to VA. Since the number of vertices in VA is smaller than capacity, the total number of queries is Occapaiity.
The algorithm inserts two new edges into E line 16 and removes one edge from & in line 19. Since line 16 be invoked at most Ocapucityy) times, the total number of invocations to line 19 is O[[E] + 2 x capacity). Therefore, the overall number of updates is 0((8| capacity).
Second, the enumeration over all vertices in V (line 17) involves time complexity Occapacity [V]). Therefore, the overall time complexity of Algorithm 3 is
(capacity [V] + (|E) + capacity) log (V])
= Ocapaciit x M + ||| x log (/l)
E PERFORMANCE EVALUATION
further evaluate the effectiveness of the HAG optimizations on two additional GNN models: GIN[Xu et al. (2099) and SGC Wu et al. (2019). The experimental setup is described in Section 5.2 We measure the per-epoch training time and inference latency for GIN and SGC. We follow previous work Xu et al. (2119) Wu et al. (2019) to split the datasets into traiiin/valicaaiion/estngg sets, and use the testing sets to measure the average inference latency.
Figure 1acuree5coomn compares the performance between GNN-graphs and HAGs. Compared to GNN-graphs, HAGs improve the training performance by up to 2.6x and 3.1x x on GIN and SGC, while maintaining the same network accuracy. This shows that the HAG optimization is general and applicable to various GNN models.
This because there be O(1212) node pairs.
12

---

Under review as a conference paper at ICLR 2020
0.95
Test Accuracy
0.9
0.8
HAG
GNN-graph
0.75
20
30
40
Time (minutes)
Figure 6: Time- tlne-to-ac comparison between HAG and GNN-graph for training a 2-layer GCN model on the Reddit dataset.
F TIME-TO- ACCURACY EVALUATION
We compare the time-to-accuracy performance between HAG and GNN-graph. We train a 2-layer GCN model (with 64 hidden dimensions in each layer) on the Reddit dataset until the test accuracy exceeds 95%. We follow previous work Kipf and Welling (2016) to set all hyper-parameter and split the dataset.
Figure 6 shows the results. Each dot indicates the training time and test accuracy of each epoch. Training the GCN model using the HAG representation achieves the same training and test accuracy at the end of each epoch. This is because the HAG optimization maintains the same results as the original GNN-graph representation and therefore preserves the model accuracy. It takes 55 training epochs to achieve test accuracy of 95% for both HAG and GNN- and HAG improves the end-to-end training time by 1.8x.
13


Reviews:
[{"review_id": "ryxmxkCRtB", "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": "This paper aims to propose a speeding-up strategy to reduce the training time for existing GNN models by reducing the redundant neighbor pairs. The idea is simple and clear. The paper is well-written. However, major concerns are:\n\n1. This strategy is only for equal contribution models (e.g., GCN, GraphSAGE), not for methods which consider distinct contribution weights for individual node neighbor (e.g. GAT). However, in my opinion, for one target node, different neighbors should be assigned with different contributions instead of equal contributions.\n\n2. What kind of graphs can the proposed model be applied to? This paper seems to only consider unweighted undirected graphs. How about directed and weighted graphs? Even for an unweighted undirected graph, the symmetric information may also be redundant for further elimination. Then can HAG reduce this symmetric redundancy?\n\n3. There is no effectiveness evaluation comparing the original GNN models with the versions with HAG. The authors claim that, with the HAG process, the efficiency could be improved without losing accuracy. But there are no experimental results verifying that the effectiveness of the HAG-versions which could obtain comparable performance with the original GNN models for some downstream applications (e.g., node classification).\n\n--------------------------------------------------Update------------------------------------------------\nThanks very much for the authors' feedback. The revised version has clarified some of my concerns. However, the equal-contribution (in Comment 1) is still a big one that the authors should pay attention. I increase my score to 3.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rkxBrYqaYH", "reviewer": "AnonReviewer2", "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": "In this paper, authors propose a way to speed up the computation of GNN. More specifically, the hierarchically aggregate computation graphs are proposed to aggregate the intermediate node and utilize this to speed up a GNN computation. Authors proof that the computation based on HAGs are equivalent to the vanilla computation of GNN (Theorem1). Moreover, for sequential aggregation, it can find a HAG that is at least (1-1/e)-approximation of the globally optimal HAGs (Theorem 3). These theoretical results are nice. Through experiments, the authors demonstrate that the proposed method can get faster computation than vanilla algorithms.\n\nThe paper is clearly written and easy to follow. However, there are some missing piece needed to be addressed.\nI put 6 (weak accept), since we cannot put 5. However, current my intention about the score is slightly above 5.\n\nDetailed comments:\n1. Experiments are only done for computational time comparison. In particular, for the sequential one, prediction accuracy can be changed due to the aggregation algorithm. Thus, it needs to report the prediction accuracy.\n\n2. In GraphSAGE, what is the sampling rate? It would be nice to have the trade-off between the sampling rate and the speedup. I guess if we sample small number of points in GraphSAGE, the performance can be degraded. In contrast, the proposed algorithm can get similar performance with larger sampling rate? Related to the question 1, the performance comparison is needed. \n\n3. Equations are used without not explaining the meaning. For instance AGGREGATE function (1), there is no definition how to aggregate. \n", "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 assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "rJxFqXA1ir", "reviewer": "AnonReviewer4", "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 proposes a new graph Hierarchy representation named HAG. The HAG aiming at eliminating the redundancy during the aggregation stage In Graph Convolution networks. This strategy can speed up the training and inference time while keeping the GNN output unchanged, which means it can get the same predict result as before. The idea is clear and easy to follow. For the theory part, I do not thoroughly check the theoretical proof but the theorem statement sounds reasonable for me. The experiment shows the HAG performs faster in both training and inference.\n\nGenerally speaking, I think this paper has good theory analysis, the speed-up effect is also good from the experimental result.  However, I still have some concerns and comments.\n\n1. The algorithm seems hard to apply on the attention-based Graph Neural network, which achieves good performance in several benchmarks these years. In other words, the redundancy of the node aggregate only exists in the Graph Convolution model with the fix node weight, which is replaced by a dynamic weight in many latest models with higher performance. That weakens the empirical use of this algorithm.\n\n2. The authors state that the HAG can optimize various kinds of GNN models, but the experiment only shows the results on a small GCN model. More GNN results in different models and settings would make the algorithm more convincing.\n\nIn conclusion, I think this is a good paper. Regards the comments above, I prefer a grade around the borderline. ", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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 assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new graph Hierarchy representation (HAG) which eliminates the redundancy during the aggregation stage and improves computation efficiency. It achieves good speedup and also provide theoretical analysis. There has been several concerns from the reviewers; authors' response addressed them partially. Despite this, due to the large number of strong papers, we cannot accept the paper at this time. We encourage the authors to further improve the work for a future version.  



Decision: Reject