Energy-Based Graph Partitioning for Scalable Node Prediction in Large Graphs

Abstract

Graph Neural Networks are some of the most powerful tools for learning from graph structured data and have been used in recommendation systems, drug discovery, and fraud detection. Due to their great advantage in finding and utilizing relational information, GNNs support Graph-based Semi-Supervised Learning. But the training of GNNs is computationally very expensive, and therefore, effective graph partitioning is required to enable scalable learning. Because it needs to minimize the overhead on communications, this is not optimal in respect to the known edge-level and vertex-level partitioning strategies, and also to scalable learning of GNN. In this thesis, a novel energy-based graph partitioning method, based on Gutman's graph energy theories, is introduced to handle the problems of big data management. This method achieves decomposition of large-scale graph structures into other much more discernible partitions while retaining the salient structural features intact. So, this energy feature thereby facilitates the partitioning process with balanced cuts with high internal connectivity, thus reducing costs in terms of distributed scenarios. Extensive experiments show improvements in scalability, processing time, and resource consumption as compared to traditional methods. Furthermore, it enhances the feature propagation and predictive performance of graph neural networks, paving the way for more efficient and robust graph-based learning in the future.