Message-passing graph neural networks (MPNNs) emerged as powerful tools for
processing graph-structured input. However, they operate on a fixed input graph
structure, ignoring potential noise and missing information. Furthermore, their
local aggregation mechanism can lead to problems such as over-squashing and
limited expressive power in capturing relevant graph structures. Existing
solutions to these challenges have primarily relied on heuristic methods, often
disregarding the underlying data distribution. Hence, devising principled
approaches for learning to infer graph structures relevant to the given
prediction task remains an open challenge. In this work, leveraging recent
progress in exact and differentiable $k$-subset sampling, we devise
probabilistically rewired MPNNs (PR-MPNNs), which learn to add relevant edges
while omitting less beneficial ones. For the first time, our theoretical
analysis explores how PR-MPNNs enhance expressive power, and we identify
precise conditions under which they outperform purely randomized approaches.
Empirically, we demonstrate that our approach effectively mitigates issues like
over-squashing and under-reaching. In addition, on established real-world
datasets, our method exhibits competitive or superior predictive performance
compared to traditional MPNN models and recent graph transformer architectures.

利用最近在精确和可微分的 k 子集采样中的进展，我们设计了一种概率重连的消息传递图神经网络（PR-MPNNs），该网络学习在省略不太有益的边的同时添加相关边。首次，我们的理论分析探索了 PR-MPNNs 如何增强表达能力，并且我们确定了它们优于纯随机方法的精确条件。经验证实，我们的方法有效地缓解了如过度压缩和预测能力不足等问题。此外，根据现有的真实世界数据集，我们的方法在预测性能上与传统的 MPNN 模型和最近的图变压器架构相比表现出有竞争力或更好的性能。