Rewiring Networks for Graph Neural Network Training Using Discrete Geometry

Information over-squashing occurs under inefficient information propagation between distant nodes on networks, which can significantly impact graph neural network (GNN) training. Rewiring is a preprocessing procedure applied to the input network to mitigate this problem. In this paper, we investigate discrete analogues of various notions of curvature to model information flow on networks and rewire them. We show that classical notions of curvature achieve state-of-the-art performance in GNN training accuracy on a wide variety of real-world datasets. Moreover, these classical notions exhibit a clear advantage in computational runtime by several orders of magnitude.