  This paper studies the expressive power of graph neural networks falling
within the message-passing framework (GNNmp). Two results are presented. First,
GNNmp are shown to be Turing universal under sufficient conditions on their
depth, width, node attributes, and layer expressiveness. Second, it is
discovered that GNNmp can lose a significant portion of their power when their
depth and width is restricted. The proposed impossibility statements stem from
a new technique that enables the repurposing of seminal results from
distributed computing and leads to lower bounds for an array of decision,
optimization, and estimation problems involving graphs. Strikingly, several of
these problems are deemed impossible unless the product of a GNNmp's depth and
width exceeds a polynomial of the graph size; this dependence remains
significant even for tasks that appear simple or when considering
approximation.
