Source-linked AI summary
MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, Aram Galstyan
TL;DR
Popular graph neural-network methods cannot learn general neighborhood-mixing relationships, limiting graph-convolution expressiveness. MixHop repeatedly mixes feature representations from neighbors at multiple distances through adjacency powers, while sparsity regularization learns dataset-specific architectures. The paper reports state-of-the-art performance on several node-classification benchmarks and shows that preferred neighborhood mixing varies across datasets.
Problem
Popular graph-convolution methods cannot learn general neighborhood-mixing functions, including Delta Operators, limiting their representational capacity.
Method
MixHop uses graph-convolution layers that mix multiple adjacency powers, with repeated application and L2 group lasso regularization for dataset-specific architectures.
Results
The paper reports state-of-the-art performance on several node-classification tasks while learning neighborhood-mixing architectures that vary by dataset.
Takeaways & Limitations
MixHop can learn general neighborhood mixing, including averaging and delta operators, without additional memory or computational complexity.
Takeaways & Limitations
Searching MixHop architectures is multiplicatively O(l × |P|) more expensive than searching vanilla-GCN architectures, motivating automatic lasso-based architecture learning.
Abstract
from arXiv · showhide
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.
1. Introduction
Graph convolution was motivated by CNNs but efficient approximations restrict neighborhood representations. MixHop addresses this limitation by learning combinations of neighborhood information at multiple distances, with theoretical and architectural tools for expressive, compact models.
- Motivation: Efficient graph-convolution approximations scale to large and inductive graphs but limit representational capacity.Earlier theoretically motivated operators had quadratic node complexity and required fully observed training graphs, whereas later approximations are linear in edges and inductive.
- Motivation: These limitations prevent graph convolutions from learning Gabor-like filters and other feature differences among graph neighbors.Such filters are fundamental in vision and are automatically recovered by CNNs trained on natural images.
- MixHop: MixHop enables full linear mixing of neighborhood information at every message-passing step.Its propagation combines features from neighbors at multiple distances rather than aggregating only immediate neighbors.
- Contributions: Popular graph-convolution models such as GCN cannot learn Delta Operators or their generalized neighborhood-mixing representations.The paper formalizes these operators to analyze graph-convolution expressiveness.
- Contributions: MixHop mixes powers of the adjacency matrix to learn a wider representation class without increasing prior GCN memory or computational complexity.The paper also proposes learning how modeling capacity is divided across widths and depths, producing compact architectures that support visual inspection.
2. Preliminaries and Related Work
Graph neural networks represent nodes through repeated message passing and aggregation, supporting semi-supervised node classification. The vanilla GCN uses normalized adjacency averaging, an efficient simplification that constrains its representation.
- Notation: A graph is represented by nodes, edges, node features, partial training labels, an adjacency matrix, and degree information.The notation includes feature matrix X, labels for a partial node set, binary adjacency A, identity matrix I_n, and degree matrix D.
- Message Passing: Graph message-passing models repeatedly exchange and aggregate latent vectors from immediate neighbors before an upstream prediction task.After l steps, node representations can support node or whole-graph classification, with parameters trained by backpropagation through structure.
- Vanilla GCN: The vanilla GCN layer transforms activations using a trainable weight matrix, an element-wise activation, and symmetrically normalized adjacency with self-connections.Its output at each layer is formed from the preceding activations through normalized neighborhood propagation.
- Vanilla GCN: The vanilla GCN effectively replaces each feature row with the average of its neighbors and itself.This behavior follows from left-multiplication by normalized adjacency after the renormalization trick adds self-connections.
- Semi-Supervised Learning: Semi-supervised GCN training evaluates loss on labeled output rows while backpropagation through normalized adjacency spreads gradients to unlabeled nodes.This connects partial supervision to representations learned across the graph.
3. Our Proposed Architecture
MixHop replaces vanilla neighborhood averaging with trainable mixing of information from multiple adjacency powers, enabling representations that vanilla GCNs cannot learn. The architecture preserves the vanilla GCN’s computational complexity while supporting two-hop Delta Operators and general layer-wise neighborhood mixing.
- 3.1. MixHop Graph Convolution Layer: Higher-order message passing lets each layer mix latent representations from immediate and more distant neighbors using trainable aggregation parameters.The model is designed to choose how information from neighbors at various distances is combined at every message-passing step.
- 3.1. MixHop Graph Convolution Layer: MixHop replaces the graph-convolution layer with separate trainable transformations for selected adjacency powers, concatenated column-wise.P is a set of integer powers; P = {1} recovers the original layer, while P = {0, 1, 2} includes self, one-hop, and two-hop information.
- 3.2. Computational Complexity: MixHop matches vanilla GCN computational complexity under realistic sparsity assumptions, with an l-layer model taking O(lm) time.An efficient implementation computes adjacency-power products through repeated sparse multiplication rather than explicitly forming each power.
- 3.3. Representational Capability: MixHop can represent two-hop Delta Operators, whereas vanilla GCNs cannot represent them even when stacked over multiple layers.A Delta Operator captures feature differences between information collected at different distances; MixHop’s powers can receive positive and negative coefficients through learned column combinations.
- 3.4. General Neighborhood Mixing: MixHop can represent general layer-wise neighborhood mixing by using adjacency powers from 0 through m.The generalized operation represents linear combinations of features across multiple hops, including subtraction.
4. Learning Graph Convolution Architectures
This section develops MixHop architectures that allocate capacity across adjacency powers and constrain output features, using sparsity to learn compact graph convolutional models.
- 4.1. Output Layer: MixHop’s output layer groups columns into sets and combines them using learned weights before applying softmax.The weights define a distribution over grouped feature sets.
- 4.1. Output Layer: The constrained output layer forces the model to prioritize selected feature groups by assigning them greater weight.This design is motivated by MixHop’s ability to mix features from different information sets.
- 4.2. Learning Adjacency Power Architectures: Different tasks and datasets may require different parameter sizes for adjacency powers, rather than equal capacity across powers.The default architecture gives all adjacency powers equally sized weight matrices.
- 4.2. Learning Adjacency Power Architectures: Architecture search becomes O(l × |P|) more expensive than vanilla GCN search because each layer width must be divided among adjacency powers.The additional search choices concern how each layer’s width is allocated across powers.
- 4.2. Learning Adjacency Power Architectures: The proposed staged procedure trains a wide network with L2 Group Lasso, thresholds column norms, shrinks matrices, and restarts with standard L2 regularization.Columns below the selected percentile are removed after measuring norms at peak validation accuracy.
5. Experimental Design
The experiments evaluate MixHop on synthetic graphs spanning homophily levels and on real-world node-classification splits, using repeated training runs and tracking delta-operator capacity.
- 5. Experimental Design: The study tests hypotheses with synthetic experiments varying graph homophily and real-world experiments evaluating MixHop’s performance.The experiments are semi-supervised node-classification evaluations.
- 5. Experimental Design: Synthetic data comprise 10 graphs with homophily coefficients from 0.0 to 0.9, each containing 5000 nodes.The coefficient indicates the likelihood that an edge connects nodes with the same label.
- 5. Experimental Design: Real-world evaluations use the classic split with 20 samples per label and random splits with 100 samples per label.The authors state that test splits will be released.
- 5.2. Training: All experiments use a 2-layer MixHop network trained with gradient descent, weight L2 regularization, and dropout.Training runs for at most 2000 steps and stops after 40 consecutive validation steps without improvement.
6. Experimental Results
Experiments show that MixHop is especially effective when graph homophily is low and achieves strong node-classification results on citation datasets. Learned sparse architectures differ across datasets, indicating that neighborhood information is prioritized in dataset-specific ways.
- Synthetic Experiments: At low homophily, MixHop performs significantly better than the most competitive baseline, while GAT performs worse than the features-only MLP control.The synthetic experiment varies graph homophily and compares average accuracy across models.
- Synthetic Experiments: MixHop uses 2.5X more model capacity for learning delta operators at low homophily than at higher homophily.The authors relate this pattern to the reduced need for feature differences when neighbors are more likely to share labels.
- Node Classification Results: 71.4%, 81.9%, and 80.8% test accuracy are achieved on Citeseer, Cora, and Pubmed, respectively, using common splits with 20 labeled nodes per class.These results are reported for the learned MixHop architecture; the Citeseer learned architecture equals the default architecture.
- Node Classification Results: 77.0%, 87.2%, and 83.9% test accuracy are achieved on Citeseer, Cora, and Pubmed, respectively, using random splits with 100 labeled nodes per class.The random splits provide more training information than the common splits.
- Model Visualization: All three real datasets learn different final architectures, with Cora assigning zero capacity to the zeroth adjacency power in the second layer.Citeseer prefers the default parameter settings, whereas the other datasets select different capacity allocations.
7. Related Work
Prior approaches use adjacency powers for propagation or embedding learning but combine them at network boundaries. MixHop instead intermixes powers layer-wise to learn neighborhood-mixing operations such as delta operators.
- Prior Graph Convolution Methods: Some prior methods use adjacency powers for embedding learning, while others use them for feature propagation but combine powers only before classification or at the input.These approaches differ from MixHop in where information from adjacency powers is combined.
- MixHop: MixHop intermixes information from adjacency powers layer-wise, enabling it to contrast immediate-neighbor features with features from farther-away neighbors.This layer-wise design targets neighborhood mixing, including delta operators.
- Graph Convolution Perspective: The paper frames message passing along graph edges as an alternative to explicit alignment onto the graph Fourier basis.This comparison is stated as a hypothesis about graph convolution approaches.
8. Conclusion
The paper argues that popular graph neural networks cannot learn general neighborhood mixing, and introduces MixHop to address this limitation. MixHop combines multiple adjacency powers without added memory or computational complexity, while sparse regularization learns dataset-specific architectures.
- Conclusion: Popular methods for semi-supervised graph learning cannot learn general neighborhood mixing functions.The analysis identifies neighborhood difference operators as an important example of the missing expressive capability.
- Conclusion: MixHop repeatedly applies layers using multiple adjacency powers to learn averaging and delta operators without additional memory or computational complexity.The method mixes neighborhood information from different distances in feature space.
- Conclusion: L2 group-lasso regularization learns a unique architecture for each dataset, and neighborhood difference operators are especially useful in graphs with low homophily.The conclusion links learned architecture specialization with the observed usefulness of neighborhood differences.