Graph Learning with Distributional Edge Layouts
This addresses a bottleneck in graph learning for researchers and practitioners by enhancing GNN expressivity, though it is incremental as it complements existing methods rather than introducing a new paradigm.
The paper tackles the problem of deterministic or heuristic edge layouts in Graph Neural Networks (GNNs) by proposing Distributional Edge Layouts (DELs), a pre-processing method that globally samples layouts via Langevin dynamics, resulting in state-of-the-art performance improvements across multiple datasets.
Graph Neural Networks (GNNs) learn from graph-structured data by passing local messages between neighboring nodes along edges on certain topological layouts. Typically, these topological layouts in modern GNNs are deterministically computed (e.g., attention-based GNNs) or locally sampled (e.g., GraphSage) under heuristic assumptions. In this paper, we for the first time pose that these layouts can be globally sampled via Langevin dynamics following Boltzmann distribution equipped with explicit physical energy, leading to higher feasibility in the physical world. We argue that such a collection of sampled/optimized layouts can capture the wide energy distribution and bring extra expressivity on top of WL-test, therefore easing downstream tasks. As such, we propose Distributional Edge Layouts (DELs) to serve as a complement to a variety of GNNs. DEL is a pre-processing strategy independent of subsequent GNN variants, thus being highly flexible. Experimental results demonstrate that DELs consistently and substantially improve a series of GNN baselines, achieving state-of-the-art performance on multiple datasets.