Graph Learning with Distributional Edge Layouts

Graph Neural Networks (GNNs) learn from graph-structured data by passing messages between neighboring nodes along edges on certain topological layouts. While layouts can be essential to GNNs' performance, extant methods generally consider obtaining layouts from limited perspectives. In this paper, we introduce Distributional Edge Layouts (DELs), a first-of-its-kind method to sample a collection of topological layouts from a Boltzmann distribution under physical energies. By integrating DELs into GNNs, a wide landscape of feasible graph layouts can be captured from a holistic perspective, overcoming the intrinsic drawbacks in existing GNN designs.In practice, DELs can complement various GNN architectures with high versatility. Our theoretical analysis proves that GNNs equipped with DELs maintain at least the same expressive as their original counterparts, with empirical potential offering extra expressivity. Extensive experiments demonstrate that DELs consistently and substantially improve the performance of a wide range of GNN baselines across multiple datasets, achieving state-of-the-art results. This improvement suggests that DELs capture important distributional information previously overlooked by traditional GNN approaches. DEL is open-sourced at https://github.com/LOGO-CUHKSZ/DEL.