Calibrated Bounded Message Passing for Robust Graph Learning

Message-passing graph neural networks learn node representations by aggregating information from their neighbours. However, widely used layers construct messages that depend linearly on neighbouring states, allowing a single anomalous or injected node to arbitrarily shift the aggregate. We introduce Calibrated Bounded Message Passing (CBMP), which normalises node inputs on both the message and residual streams and applies a calibrated saturating map before neighbourhood aggregation. Per-channel scales are estimated on the clean training graph and frozen, anchoring saturation thresholds to typical clean messages. We prove that changes in a node’s aggregate scale with the total aggregation weight assigned to corrupted neighbours, and derive injection bounds under explicit degree conditions. Across five node-classification graphs with ten paired seeds (five on ogbn-arxiv), CBMP matches or exceeds GCN’s clean performance and consistently improves robustness over GCN to feature outliers and node injection. Under degree-targeted, feature-adaptive injection, it gains 4–66 percentage points over GCN and outperforms the GRB LayerNorm defence on both heterophilous graphs and ogbn-arxiv while matching it on the other two graphs. Ablations isolate the benefit of bounding each incoming message and normalising both streams. These results establish pre-aggregation message control as an effective design principle for robust graph learning.