Scale Continuity in Graph Learning: Going beyond spectral methods

Standard message passing graph neural networks (MPNNs) assign vastly different latent embeddings to graphs that describe the same underlying object at different resolution scales. As a result, message passing graph neural networks generically fail to generalize across resolution scales. Previous work showed that this issue can be overcome if instead of MPNNs certain special types of spectral graph neural networks are used. In this tiny-paper, we show that spectral methods are not necessary for achieving scale continuity. We demonstrate that if message passing networks are suitably modified, they can be rendered scale-continuous as well. By identifying the structural requirements for continuity, we derive a class of message passing architectures that provably preserve embeddings across resolution scales. Empirically, we show that these models match the cross-scale generalization performance of spectral approaches while retaining the flexibility and scalability of local message passing methods.