Non-dissipative Propagation by Randomized Anti-symmetric Deep Graph Networks

Deep Graph Networks (DGNs) currently dominate the research landscape of learning from graphs, due to the efficiency of their adaptive message-passing scheme between nodes. However, DGNs are typically afflicted by a distortion in the information flowing from distant nodes (i.e., over-squashing) that limit their ability to learn long-range dependencies. This reduces their effectiveness, since predictive problems may require to capture interactions at different, and possibly large, radii in order to be effectively solved. We focus on Anti-symmetric Deep Graph Networks (A-DGNs), a recently proposed neural architecture for learning from graphs. A-DGNs are designed based on stable and non-dissipative ordinary differential equations, with a key architectural design based on an anti-symmetric structure of the internal weights. In this paper, we investigate the merits of the resulting architectural bias by incorporating randomized internal connections in node embedding computations and by restricting the training algorithms to operate exclusively at the output layer. To empirically validate our approach, we conduct experiments on various graph benchmarks, demonstrating the effectiveness of the proposed approach in learning from graph data.