Why the non-exploitation of edge labels in current graph convolutions "results in an overly homogeneous view of local graph neighborhoods"?
Consider a two-dimensional convolution layer with 3x3 kernels. The 2d inputs of this layer can be seen as a particular graph with each pixel being a graph node, that is connected to 8 of his neighbors:

The 3x3 kernels of the convolutional layer not only process the information about neighborhood relation between pixels, but also about their relative orientation. For example the [0,0] element of the kernel might represent the weight of the node to NW. And the [1,2] element of the kernel represent the weight the node across the S edge:

Now, if we make a convolution that &quot;doesn't exploit edge labels&quot; then we'll have to forget the labels on the picture above, making us loose directional information:

All we can say now is that the &quot;red&quot; node has those neighbors, but we don't really know how they are oriented relative to it. Since now the sub-graph does not provide any directional information, the learned convolution kernels will be direction-agnostic - in other words, they will be rotation-invariant.