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 "doesn't exploit edge labels" 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 "red" 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.