Parallelism in GNN: Possibilities and Limits of Current Approaches

Graph Neural Networks (GNNs) have emerged as powerful tools for learning on graph-structured data, demonstrating state-of-the-art performance in various applications such as social network analysis, biological network modeling, and recommendation systems. However, the computational complexity of GNNs poses significant challenges for scalability, particularly with large-scale graphs. Parallelism in GNNs addresses this issue by distributing computation across multiple processors, using techniques such as data parallelism and model parallelism. Data parallelism involves partitioning the graph data across different processors, while model parallelism splits the neural network’s layers or operations. These parallelization strategies, along with optimizations such as asynchronous updates and efficient communication protocols, enable GNNs to handle larger graphs and improve training efficiency. This work explores the key computational kernels and looks for those where parallelism could significantly enhance the scalability and performance of GNNs, highlighting the algebraic aspects of each one. This is the first step to better compare recent advances and their implications for future research.