Instance Indistinguishability and the Limits of Graph Learning: A Local-Global Perspective

Graph-level prediction infers global properties from local neighborhoods, but it may fail when classes differ globally while local observations remain indistinguishable. We ask when interactions among local observations reveal a global difference and whether graph learners can exploit it. Planted Model RB makes this question controllable by varying problem size and constraint density. Although satisfiability distinguishes planted from random instances above the classical threshold, every individual constraint has the same distribution in both models. To characterize this transition, we derive the low-degree likelihood-ratio projection, showing that the first informative component comes from constraint pairs sharing variables and giving its exact finite-sample strength. We prove further that, when this pairwise signal vanishes, all polynomial statistics up to logarithmic degree are asymptotically uninformative, yielding a local-global separation that widens with problem size. Experiments corroborate this size dependence and reveal a growing gap between the shared-variable signal available in the complete instance and the signal extracted by the evaluated GNNs. This gap narrows substantially when the graph representation preserves shared-variable relations, but not under generic structural augmentation or increased architectural expressivity. Our theoretical and empirical findings therefore indicate that learning a global distinction from local observations depends on both sufficient overlap among those observations and a representation that preserves the structure through which the distinguishing signal emerges.