mlsanityData to 14 Oct 2026

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

arXiv 2605.13126 ↗First posted 13 May 2026cs.LG cs.AIcited by 0

Not on the map. Why?

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.

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

24 of 41 references.

References · 24

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2013Distributed Representations of Words and Phrases and their Compositionalitycited by 3,474
  4. 2016Deep Variational Information Bottleneckcited by 930
  5. 2015Deep Learning and the Information Bottleneck Principlecited by 802
  6. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  7. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  8. 2020Graph Information Bottleneckcited by 168
  9. 2022FoSR: First-order spectral rewiring for addressing oversquashing in GNNscited by 105
  10. 2022Revisiting Over-smoothing and Over-squashing Using Ollivier-Ricci Curvaturecited by 98
  11. 2013Large-scale Multi-label Learning with Missing Labelscited by 58
  12. 2024Spectral Graph Pruning Against Over-Squashing and Over-Smoothingcited by 24
12 more
  1. 2024Towards Bridging Generalization and Expressivity of Graph Neural Networkscited by 12
  2. 2024Correlation-Aware Graph Convolutional Networks for Multi-Label Node Classificationcited by 11
  3. 2023Multi-label Node Classification On Graph-Structured Datacited by 10
  4. 2024Uncertainty Modeling in Graph Neural Networks via Stochastic Differential Equationscited by 8
  5. 2025Mitigating Over-Squashing in Graph Neural Networks by Spectrum-Preserving Sparsificationcited by 8
  6. 2019Semi-Supervised Graph Embedding for Multi-Label Graph Node Classificationcited by 7
  7. 2019Collaborative Graph Walk for Semi-supervised Multi-Label Node Classificationcited by 7
  8. 2024Expressive Power of Temporal Message Passingcited by 7
  9. 2024Unveiling the Impact of Local Homophily on GNN Fairness: In-Depth Analysis and New Benchmarkscited by 6
  10. 2025Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophilycited by 5
  11. 2025Graph Contrastive Learning on Multi-label Classification for Recommendationscited by 2
  12. 2025Does Homophily Help in Robust Test-time Node Classification?cited by 1

Built on by

Not cited yet.