MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing

Recently, many methods have been proposed for semi-supervised learning that extend the convolutional operator from Euclidean domains to graph-structured data by approximating the eigenbasis of the graph Laplacian. However, despite their prevalence, there has not been extensive analysis of the expressive power of these models. In this work, we prove that popular methods (such as the Graph Convolutional Network) do not model and cannot learn a class of neighborhood difference relationships which we call \delta operators. To address this weakness, we propose a new model, MixHop, that can capture these difference relationships by learning mixed feature representations of neighbors at various distances. MixHop requires no additional memory or computational complexity, and outperforms challenging baselines on several graph datasets including citation networks, synthetic graphs, and molecule classification for quantum chemistry. Furthermore, we quantify how the model prioritizes neighborhood information across different network datasets by adding a sparsity regularizer.

• Data Mining and Modeling

• Machine Intelligence