When Do GNNs Work: Understanding and Improving Neighborhood Aggregation

When Do GNNs Work: Understanding and Improving Neighborhood Aggregation

Yiqing Xie, Sha Li, Carl Yang, Raymond Chi-Wing Wong, Jiawei Han

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
Main track. Pages 1303-1309. https://doi.org/10.24963/ijcai.2020/181

Graph Neural Networks (GNNs) have been shown to be powerful in a wide range of graph-related tasks. While there exists various GNN models, a critical common ingredient is neighborhood aggregation, where the embedding of each node is updated by referring to the embedding of its neighbors. This paper aims to provide a better understanding of this mechanisms by asking the following question: Is neighborhood aggregation always necessary and beneficial? In short, the answer is no. We carve out two conditions under which neighborhood aggregation is not helpful: (1) when a node's neighbors are highly dissimilar and (2) when a node's embedding is already similar with that of its neighbors. We propose novel metrics that quantitatively measure these two circumstances and integrate them into an Adaptive-layer module. Our experiments show that allowing for node-specific aggregation degrees have significant advantage over current GNNs.
Keywords:
Data Mining: Mining Graphs, Semi Structured Data, Complex Data
Machine Learning: Semi-Supervised Learning