Improving Expressivity of Graph Neural Networks
This addresses a fundamental limitation in graph representation learning for applications like social network analysis or molecular modeling, though it appears incremental as it builds on existing GNN architectures.
The paper tackles the limited expressivity of Graph Neural Networks (GNNs) by proposing a new model that can differentiate between graphs indistinguishable by the Weisfeiler-Lehman test, achieving greater expressive power through techniques like expanding attention windows and partially random initial embeddings.
We propose a Graph Neural Network with greater expressive power than commonly used GNNs - not constrained to only differentiate between graphs that Weisfeiler-Lehman test recognizes to be non-isomorphic. We use a graph attention network with expanding attention window that aggregates information from nodes exponentially far away. We also use partially random initial embeddings, allowing differentiation between nodes that would otherwise look the same. This could cause problem with a traditional dropout mechanism, therefore we use a "head dropout", randomly ignoring some attention heads rather than some dimensions of the embedding.