Redundancy-Free Computation Graphs for Graph Neural Networks
  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, 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 HAGs and use a novel HAG 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, while maintaining
the original model accuracy.
