Abstract: Despite their popularity for graph structured data, existing {\em Graph Neural Networks}~(GNNs) have inherent limitations for fundamental graph problems such as shortest paths, $k$-connectivity, minimum spanning tree and minimum cuts. In these instances, it is known that one needs GNNs of high depth, scaling at a polynomial rate with the number of nodes $n$, to provably encode the solution space, in turn affecting their statistical efficiency.



In this work we propose a new hybrid architecture to overcome this limitation. Our proposed architecture that we call as {\GNNplus} networks involve a combination of multiple parallel low depth GNNs along with simple pooling layers involving low depth fully connected networks. We provably demonstrate that for many graph problems, the solution space can be encoded by {\GNNplus} networks using depth that scales only {\em poly-logarithmically} in the number of nodes. This also has statistical advantages that we demonstrate via generalization bounds for {\GNNplus} networks.