Ego GNNs: Exploiting Ego Structures in Graph Neural Networks
Graph neural networks (GNNs) have achieved remarkable success as a framework for deep learning on graph structured data. However, GNNs are fundamentally limited by their tree structured inductive bias: the WL subtree kernel formulation bounds the representational capacity of GNNs, and polynomial time GNNs are provably incapable of recognizing triangles in a graph. In this work, we propose to augment the GNN message passing operations with information de fined on ego graphs (i.e. the induced subgraph surrounding each node) We term these approaches Ego GNNs and show that Ego GNNs are provably more powerful than standard message passing GNNs. In particular, we show that Ego GNNs are capable of recognizing closed triangles, which is essential given the prominence of transitivity in real world graphs. We also motivate our approach from the perspective of graph signal processing as a form of multiplex graph convolution. Experimental results on node classification using synthetic and real data highlight the achievable performance gains using this approach.
ICASSP 2021 2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)