MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
This work addresses a fundamental weakness in semi-supervised learning with Graph Neural Networks, offering a novel solution for tasks involving graph-structured data.
The paper tackles the limitation of existing Graph Neural Networks in learning neighborhood mixing relationships by proposing MixHop, a model that mixes feature representations of neighbors at various distances, achieving superior performance on challenging baselines without additional computational cost.
Existing popular methods for semi-supervised learning with Graph Neural Networks (such as the Graph Convolutional Network) provably cannot learn a general class of neighborhood mixing relationships. To address this weakness, we propose a new model, MixHop, that can learn these relationships, including difference operators, by repeatedly mixing feature representations of neighbors at various distances. Mixhop requires no additional memory or computational complexity, and outperforms on challenging baselines. In addition, we propose sparsity regularization that allows us to visualize how the network prioritizes neighborhood information across different graph datasets. Our analysis of the learned architectures reveals that neighborhood mixing varies per datasets.