Rethinking Message Passing Neural Networks with Diffusion Distance-guided Stress Majorization
This addresses performance limitations in graph neural networks for researchers and practitioners, though it appears incremental as it builds on existing MPNN frameworks.
The paper tackles the problems of over-smoothing and over-correlation in message passing neural networks (MPNNs) by proposing DDSM, a new MPNN model that incorporates stress majorization, orthogonal regularization, and diffusion distances. The result shows that DDSM consistently and considerably outperforms 15 strong baselines on both homophilic and heterophilic graphs.
Message passing neural networks (MPNNs) have emerged as go-to models for learning on graph-structured data in the past decade. Despite their effectiveness, most of such models still incur severe issues such as over-smoothing and -correlation, due to their underlying objective of minimizing the Dirichlet energy and the derived neighborhood aggregation operations. In this paper, we propose the DDSM, a new MPNN model built on an optimization framework that includes the stress majorization and orthogonal regularization for overcoming the above issues. Further, we introduce the diffusion distances for nodes into the framework to guide the new message passing operations and develop efficient algorithms for distance approximations, both backed by rigorous theoretical analyses. Our comprehensive experiments showcase that DDSM consistently and considerably outperforms 15 strong baselines on both homophilic and heterophilic graphs.