# MLGIB: Multi-Label Graph Information Bottleneck for Expressive and Robust Message Passing

arXiv: https://arxiv.org/abs/2605.13126 · HTML: https://mlsanity.com/paper/2605.13126/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 41 references that are in the map.
- First posted on arXiv 13 May 2026.

## Builds on (most cited first, 24 of 24)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [Deep Variational Information Bottleneck](https://mlsanity.com/paper/1612.00410/) (2016)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Graph Information Bottleneck](https://mlsanity.com/paper/2010.12811/) (2020)
- [FoSR: First-order spectral rewiring for addressing oversquashing in GNNs](https://mlsanity.com/paper/2210.11790/) (2022)
- [Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvature](https://mlsanity.com/paper/2211.15779/) (2022)
- [Large-scale Multi-label Learning with Missing Labels](https://mlsanity.com/paper/1307.5101/) (2013)
- [Spectral Graph Pruning Against Over-Squashing and Over-Smoothing](https://mlsanity.com/paper/2404.04612/) (2024)
- [Towards Bridging Generalization and Expressivity of Graph Neural Networks](https://mlsanity.com/paper/2410.10051/) (2024)
- [Correlation-Aware Graph Convolutional Networks for Multi-Label Node Classification](https://mlsanity.com/paper/2411.17350/) (2024)
- [Multi-label Node Classification On Graph-Structured Data](https://mlsanity.com/paper/2304.10398/) (2023)
- [Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equations](https://mlsanity.com/paper/2408.16115/) (2024)
- [Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsification](https://mlsanity.com/paper/2506.16110/) (2025)
- [Semi-Supervised Graph Embedding for Multi-Label Graph Node Classification](https://mlsanity.com/paper/1907.05743/) (2019)
- [Collaborative Graph Walk for Semi-supervised Multi-Label Node Classification](https://mlsanity.com/paper/1910.09706/) (2019)
- [Expressive Power of Temporal Message Passing](https://mlsanity.com/paper/2408.09918/) (2024)
- [Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarks](https://mlsanity.com/paper/2410.04287/) (2024)
- [Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily](https://mlsanity.com/paper/2511.06608/) (2025)
- [Graph Contrastive Learning on Multi-label Classification for Recommendations](https://mlsanity.com/paper/2501.06985/) (2025)
- [Does Homophily Help in Robust Test-time Node Classification?](https://mlsanity.com/paper/2510.22289/) (2025)

## Abstract (arXiv)

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.