Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio

Jonathan Rubin, Sahil Loomba, Nick S. Jones · 2025

Read Limits of message passing for node classification: How class-bottlenecks restrict signal-to-noise ratio by Jonathan Rubin, Sahil Loomba, Nick S. Jones (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-17822.txt.

Description

Jonathan Rubin, Sahil Loomba, and Nick Jones set out limits of message passing for node classification on graphs. Their 2025 paper deals with two known weaknesses: heterophily, where neighbors often differ in class, and structural bottlenecks.

Their statistical framework ties the two through the signal-to-noise ratio of the learned representations. That ratio splits performance into feature-dependent parts and feature-independent sensitivities. They prove the sensitivity to class signals is bounded by a multi-hop generalization of homophily. Where that quantity is low, bottlenecks and labels interact locally to choke the signal. Analysis of graph ensembles quantifies the effect further.

Catalog record

CREATORJonathan Rubin, Sahil Loomba, Nick S. Jones
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE207 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2508-17822

Browse the full library · About the Tower of Babel