  It is by now a well known fact in the graph learning community that the
presence of bottlenecks severely limits the ability of graph neural networks to
propagate information over long distances. What so far has not been appreciated
is that, counter-intuitively, also the presence of strongly connected
sub-graphs may severely restrict information flow in common architectures.
Motivated by this observation, we introduce the concept of multi-scale
consistency. At the node level this concept refers to the retention of a
connected propagation graph even if connectivity varies over a given graph. At
the graph-level, multi-scale consistency refers to the fact that distinct
graphs describing the same object at different resolutions should be assigned
similar feature vectors. As we show, both properties are not satisfied by
poular graph neural network architectures. To remedy these shortcomings, we
introduce ResolvNet, a flexible graph neural network based on the mathematical
concept of resolvents. We rigorously establish its multi-scale consistency
theoretically and verify it in extensive experiments on real world data: Here
networks based on this ResolvNet architecture prove expressive; out-performing
baselines significantly on many tasks; in- and outside the multi-scale setting.
