MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing
For practitioners using GNNs on multi-label graphs, this work addresses the specific challenge of over-squashing exacerbated by irrelevant labels, offering a principled solution.
The paper identifies a distinct failure mode of over-squashing in multi-label graphs, where irrelevant label noise dilutes predictive signals. It proposes MLGIB, a framework that balances expressiveness and robustness via information bottleneck principles, achieving consistent improvements over existing methods on multiple benchmarks.
Graph Neural Networks (GNNs) suffer from over-squashing in deep message passing, where information from exponentially growing neighborhoods is compressed into fixed-dimensional representations. We show that this issue becomes a distinct failure mode in multi-label graphs: neighboring nodes often share only limited labels while differing across many irrelevant ones, causing predictive signals to be diluted by noisy label information. To address this challenge, we propose the Multi-Label Graph Information Bottleneck (MLGIB), which formulates multi-label message passing as constrained information transmission under irrelevant label noise. MLGIB balances expressiveness and robustness by preserving predictive label signals while suppressing irrelevant noise. Specifically, it constructs a Markovian dependence space and derives tractable variational bounds, where the lower bound maximizes mutual information with target labels and the upper bound constrains redundant source information. These bounds lead to an end-to-end label-aware message-passing architecture. Extensive experiments on multiple benchmarks demonstrate consistent improvements over existing methods, validating the effectiveness and generality of the proposed framework.