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

By Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, Aram Galstyan. International Conference on Machine Learning, 2019

1,157 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Health Information Management

View Paper: https://www.semanticscholar.org/paper/4efb9a950f252138a30eeb942ed02663a3ea29d1

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Health Information Management

Citations in the corpus

Revisiting Heterophily For Graph Neural Networks (2022, methodology): “We now discuss relevant work on addressing heterophily in GNNs. [1] acknowledges the difficulty of learning on graphs with weak homophily and propose MixHop to extract features from multi-hop neighborhoods to get more information.”
Multi-scale Attributed Node Embedding (2019, methodology): “• MixHop (Abu-El-Haija et al., 2019): We took advantage of the 0 th , 1 st and 2 nd powers of the normalized adjacency matrix with 32 dimensional convolutional ﬁlters for creating the ﬁrst hidden representations.”
Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs (2020, methodology): “com/williamleif/graphsage-simple (PyTorch implementation) • MixHop [1]: https://github.”
Propagation Model Search for Graph Neural Networks (2020, methodology): “For example, GCN (Kipf and Welling 2017) chooses the normalized adjacency matrix (with added self-loops) to propagate features between one-hop neighbors, while MixHop (Abu-El-Haija et al. 2019) employs powers of the propagation matrix of GCN in order to combine information at multiple distances.”
Pre-training Enhanced Spatial-temporal Graph Neural Network for Multivariate Time Series Forecasting (2022, methodology): “MTGNN replaces the GNN and Gated TCN in Graph WaveNet with mix-hop propagation layer [1] and dilated inception layer, and proposes to learn latent adjacency matrix to seek further improvement.”
NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification (2023, methodology): “Besides, we compare with some advanced GNN models, including JKNet [44] and MixHop [1].”
High-Order Graph Convolutional Recurrent Neural Network: A Deep Learning Framework for Network-Scale Traffic Learning and Forecasting (2018, background): “Previous work [24][25][28] has defined the graph convolution based the adjacency matrix.”
Is Homophily a Necessity for Graph Neural Networks? (2021, background): “Hence, several recent works claim (Zhu et al., 2020b;a; Chien et al., 2021), assume (Halcrow et al., 2020; Wu et al., 2018; Zhao et al., 2020) or remark upon (Abu-El-Haija et al., 2019; Maurya et al., 2021; Hou et al., 2020) GNN models homophily-reliance or unsuitability in capturing heterophily.”
AM-GCN: Adaptive Multi-channel Graph Convolutional Networks (2020, methodology): “MixHop [1] aggregates feature information from both first-order and higher-order neighbors in each layer of network, simultaneously.”
Graph Random Neural Networks for Semi-Supervised Learning on Graphs (2020, methodology): “Following the community convention [20, 35, 31], the results of baselines are taken from the original works [20, 35, 12, 1, 13, 9, 25, 36, 32, 21].”
Machine Learning on Graphs: A Model and Comprehensive Taxonomy (2020, neutral): “Reprinted with permission from [3, 111].”
GraphSAINT: Graph Sampling Based Inductive Learning Method (2019, methodology): “, 2018; Abu-El-Haija et al., 2019) or even more complicated networks for the task of graph classification (Ying et al., 2018b), we replace the full adjacency matrix A with the (normalized) one for the subgraph As to perform layer propagation. Comparison GraphSAINT enjoys: 1. high scalability and eff”
Graph Neural Networks with Heterophily (2020, methodology): “More recent works have looked into designs which strengthen the effectiveness of GNN to capture graph information: GAT (Veličković et al. 2018) and AGNN (Thekumparampil et al. 2018) introduced an edge-level attention mechanism; MixHop (Abu-El-Haija et al. 2019) and Geom-GCN (Pei et al. 2020) desig”
Reliable Data Distillation on Graph Convolutional Network (2020, background): “A natural approach to make better use of the unlabeled data is to use a deeper network [2, 51].”
Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning (2020, methodology): “[48] S.”
Traffic Graph Convolutional Recurrent Neural Network: A Deep Learning Framework for Network-Scale Traffic Learning and Forecasting (2018, background): “Previous work [23], [24], [27] has defined the graph con-”
Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks (2020, background): “[9] show that their proposed model with two mix-hop layers has the capability to represent the delta difference between two consecutive hops.”