Google Research

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

  • Sami Abu-El-Haija
  • Bryan Perozzi
  • Amol Kapoor
  • Hrayr Harutyunyan
  • Nazanin Alipourfard
  • Kristina Lerman
  • Greg Ver Steeg
  • Aram Galstyan
The Thirty-sixth International Conference on Machine Learning (ICML) (2019)

Abstract

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.

Learn more about how we do research

We maintain a portfolio of research projects, providing individuals and teams the freedom to emphasize specific types of work