| Paper ID | SS-16.4 |
| Paper Title |
EGO-GNNS: EXPLOITING EGO STRUCTURES IN GRAPH NEURAL NETWORKS |
| Authors |
Dylan Sandfelder, Priyesh Vijayan, William Hamilton, McGill University, Canada |
| Session | SS-16: Theoretical Foundations of Graph Neural Networks |
| Location | Gather.Town |
| Session Time: | Friday, 11 June, 14:00 - 14:45 |
| Presentation Time: | Friday, 11 June, 14:00 - 14:45 |
| Presentation |
Poster
|
| Topic |
Special Sessions: Theoretical Foundations of Graph Neural Networks |
| IEEE Xplore Open Preview |
Click here to view in IEEE Xplore |
| Virtual Presentation |
Click here to watch in the Virtual Conference |
| Abstract |
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 defined 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. |
