  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.
