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

In plain words

A graph neural network learns about each node by blending in information from the nodes it is linked to. The standard layer blends in only the direct neighbours, so every node ends up holding an average of its surroundings. An average cannot express a contrast, such as how a node's direct neighbours differ from the neighbours of those neighbours.

MixHop keeps the same kind of layer but computes several versions of the neighbourhood side by side: the node itself, its direct neighbours, and the nodes two steps away. Each version gets its own learned weights, and the layer places the results next to each other. The next layer can then take weighted differences between the versions, which lets the model express contrasts across distances.

The authors also add a sparsity penalty that shows which distances a trained model relies on. The learned mix differs from one dataset to another. On the standard citation benchmarks, the reported accuracy is higher than that of a standard graph convolution network, with the numbers as the authors measured them.

TL;DR

• MixHop replaces the single propagation step of a GCN layer with a concatenation over adjacency powers j in a set P, each with its own weight matrix §3.1, eq. 4. With P = {1} it is exactly the GCN layer §3.1.
• The authors prove that a vanilla GCN cannot represent a two-hop delta operator, while MixHop with P = {0, 1, 2} can §3.3.
• Reported gains on Planetoid and random splits are author-reported [tab. 1, tab. 3].
• The official TensorFlow code runs the two-layer model with fixed hyperparameters, but it does not run the staged group-lasso search that the paper uses to choose per-power widths §4.2, code: mixhop_trainer.py#L71-L73.
• Use this card when you need node classification with few labels and want to test higher-order neighbourhood features.

Problem

The GCN layer multiplies the features by the normalized adjacency matrix, so each layer replaces a node's features with an average over its neighbourhood §2.3, eq. 1. The authors define a delta operator, a subtraction between features at two distances, and argue that such operators are needed for features like contrasts between a node's friends and its friends of friends §3, def. 1, eq. 3. They prove that a vanilla GCN stack, which is defined in §2.3, eq. 2, cannot represent the two-hop delta operator §3.3. The proof uses the special case of identity activation and X = I_n §3.3 proof. Early spectral convolutions were quadratic in the number of nodes and needed the full graph during training; the GCN approximations are linear in the number of edges and apply inductively §1.

Method

Notation

• A is the binary adjacency matrix, I_n the identity, D the degree matrix of A §2.1.
• The normalized adjacency with self-loops is  = D^(-1/2) (A + I_n) D^(-1/2) §2.3.

MixHop graph convolution layer

The layer takes H^(i) and outputs the column-wise concatenation over j in P, where each block is σ(Â^j H^(i) W_j^(i)) §3.1, eq. 4. P is a set of integer adjacency powers, Â^0 is the identity, and P = {1} recovers the GCN layer §3.1. Each power has its own weight matrix, which may have a different width. By default the widths are equal §3.1.

Powers are computed by repeated sparse multiplication, from right to left, so Â^j is never formed. The cost is O(j_max · m · s) per layer, where m is the number of non-zero adjacency entries and s the feature width §3.2. The authors state this matches the cost of a vanilla GCN for an l-layer model when j_max ≪ m and s ≪ m §3.2.

Algorithm 1 omits the activation alg. 1. The pseudocode below follows equation 4 and includes it eq. 4.

# MixHop graph convolution layer  [eq. 4] [alg. 1] [§3.2]
# H_prev: (n, s_in); adj: sparse (n, n), normalized Â
# weights[j]: (s_in, s_j) for each j in powers

def mixhop_layer(H_prev, adj, powers, weights, act):
    # Start from the input; each pass multiplies by  once  [§3.2]
    propagated = H_prev
    blocks = []
    for j in range(0, max(powers) + 1):
        # j = 0 keeps the input, since Â^0 = I_n  [§3.1]
        if j > 0:
            propagated = adj @ propagated
        # Keep only the powers listed in P  [eq. 4]
        if j in powers:
            # Each power has its own weights; act is σ  [eq. 4]
            blocks.append(act(propagated @ weights[j]))
    # Column-wise concatenation of all power blocks  [eq. 4]
    return concatenate(blocks, axis=1)  # (n, sum of s_j)

Two-layer classifier used in experiments

The experiments use a two-layer network built from MixHop layers §5.2. The output MixHop layer produces columns in groups of size c, the number of classes. The output is a softmax-weighted sum over those groups, followed by a softmax over classes §4.1. The experiments use 60 hidden columns, divided evenly across powers by default §5.2.

# Two-layer MixHop classifier  [§5.2] [§4.1]
# features: (n, F) sparse; adj: normalized Â; c: number of classes

def mixhop_forward(features, adj, is_training):
    # Input dropout, then L2-normalize each row  [code: mixhop_trainer.py#L259]
    x = l2_normalize_rows(dropout(features, input_drop, is_training))
    # Hidden MixHop layer, 60 columns split across powers  [§5.2]
    h = mixhop_layer(x, adj, powers, hidden_widths)
    # Batch norm, then the activation  [§4] [code: mixhop_trainer.py#L272-L274]
    h = act(batch_norm(h))
    # Dropout before the output layer  [§5.2] [code: mixhop_trainer.py#L266]
    h = dropout(h, hidden_drop, is_training)
    # Output MixHop layer, no activation  [§4.1] [code: mixhop_trainer.py#L276]
    z = mixhop_layer(h, adj, powers, output_widths)  # (n, sum of widths)
    # Softmax weights per group  [§4.1] [code: mixhop_model.py#L25]
    q = softmax(q_params)
    logits = sum(q[k] * z[:, k * c:(k + 1) * c] for k in range(len(q)))
    return logits  # (n, c), followed by softmax and cross-entropy  [§4.1]

Learning per-power widths

The paper picks the width of each power in each layer with a group-lasso penalty, in five stages §4.2:

1. Build a wide network, for example 200 columns per power per layer, and choose only the depth §4.2.
2. Train with an L2 group-lasso penalty on every column of each weight matrix, which drives whole columns towards zero §4.2.
3. At the peak validation accuracy, measure the L2 norm of each column and choose a threshold so that the shrunken model has the same size as the P = {1} baseline §4.2.
4. Remove the columns whose norm lies below the chosen percentile §4.2.
5. Replace the group-lasso penalty with ordinary L2 and retrain §4.2.

The paper reports learned architectures for the citation datasets in §6.3 and fig. 5.

Datasets

• Synthetic: 10 graphs with homophily from 0.0 to 0.9 in steps of 0.1, each with 5000 nodes. Node features come from overlapping Gaussians, and the nodes are split into equal train, validation and test parts §5.1. The generator is in app. A.
• Real: Citeseer, Cora and Pubmed, with the Planetoid split (20 labelled nodes per class) and random splits (100 labelled nodes per class) §5.1, §5.2 tab. 2.

Table 2 gives the dataset statistics, copied here from the paper tab. 2.

Hyperparameters

Values in "Paper" come from the text, and values in "Code" are the defaults in mixhop_trainer.py or the shell scripts. "not stated" means the paper and the code give no value.

Results

Author-reported. The setup is a two-layer MixHop network with 60 latent columns, compared against the baselines listed in each table. Hardware is not stated.

Planetoid splits

Table 1 tab. 1. Values are mean ± standard deviation over 50 runs §6.2. Rows above the double line are copied from Kipf and Welling; the MixHop rows were run by the authors §6.2.

Random splits

Table 3 tab. 3. Values are mean ± standard deviation; the number of runs behind each row is not stated in the table. The paper does not say whether the baseline rows were run by the authors or copied.

Synthetic graphs

Accuracy against homophily for each baseline, with a feature-only MLP as a control §6.1 fig. 4. At low homophily MixHop is significantly better than the strongest baseline, and GAT is significantly worse than the MLP control §6.1. The paper reports that at low homophily the learned model devotes about 2.5 times more capacity to delta operators than at high homophily §6.1 fig. 3.

Learned architectures

For Cora the zeroth power has no capacity in the second layer §6.3 fig. 5. The text says Citeseer prefers the default equal split §6.3, and also that all three datasets ended with different architectures §6.3.

Paper vs code

Official code: https://github.com/samihaija/mixhop, commit af9866ae49336c6f8f65f3077d239e856b62a88a. The repository has no LICENSE file, so its code license is unknown. No code is quoted; everything below is paraphrased and cited by path and line.

• Adjacency. Matches §2.3: self-loops are added, and each edge gets 1 / sqrt(|N(i)| · |N(j)|) with degrees counted including the self-loop mixhop_dataset.py.
• Layer and activation order. Equation 4 applies σ inside each block eq. 4. Algorithm 1 has no activation alg. 1. The code concatenates the linear blocks, applies batch normalization, then the activation mixhop_model.py mixhop_trainer.py.
• Output layer. The code computes the weighted sum with softmax weights q and adds a loss term of 1e-3 · mean(q²), which the paper does not state mixhop_model.py. The weights start at zero, so the start is uniform.
• Group lasso. The paper uses group lasso only in architecture learning §4.2. The code adds a column group-lasso term to every kernel, with the coefficient set to l2reg, and also adds L2 at the same value mixhop_trainer.py mixhop_trainer.py. The lasso_reg and architecture_search_steps flags are defined but never read mixhop_trainer.py. The README says the group-lasso code is still missing README.md. These statements conflict.
• Learning rate, steps, patience, L2, dropout. The scripts differ from §5.2 (see the Hyperparameters table) train_cora.sh train_citeseer.sh train_pubmed_2layer_psum.sh.
• Runs and selection. The paper runs 100 times and keeps the top 50 §5.2. The trainer runs once per call and records the test accuracy at the best validation step mixhop_trainer.py.
• Random splits and the synthetic loader. The loader reads Planetoid files only. The homophily branch is disabled mixhop_dataset.py. The random-split test indices are not in the repository mixhop_trainer.py.
• Synthetic feature covariance. The repository generator uses 350 · diag(70, 20), which is 3500 × diag(7, 2) as stated in app. A make_x.py.
• Other architecture. architectures/pubmed.json defines three MixHop layers and a dense output. The README says this script is "Model not in paper" README.md pubmed.json.
• Scripts labelled as the paper model. The README labels the Cora, Citeseer and Pubmed 2-layer scripts "Model in paper" README.md, and says the Cora and Citeseer scripts give slightly better results than the paper README.md. The scripts do not say which architecture the learned rows of Table 1 and Table 3 came from.

Pitfalls

• Learning-rate mismatch. The paper's rate is 0.05, decaying by 0.0005 every 40 steps §5.2. The code decays by 1% of the initial rate each time mixhop_trainer.py mixhop_trainer.py. The scripts use initial rates of 1, 0.25 and 0.5 and decay every 40 or 20 steps train_cora.sh train_citeseer.sh train_pubmed_2layer_psum.sh. Choose one set and state it.
• Dropout values are drop rates. The input dropout is applied with drop probability equal to the flag mixhop_model.py. The hidden dropout is passed as the rate argument of the framework's dropout layer mixhop_trainer.py. The scripts therefore drop 90% of hidden entries train_cora.sh. The paper gives no values §5.2.
• Model selection uses the test set. The best step is chosen by comparing tuples of (validation accuracy, test accuracy, step). A tie in validation accuracy is broken by the higher test accuracy mixhop_trainer.py mixhop_trainer.py. Select on validation accuracy alone to avoid this.
• Feature values are discarded. Every non-zero input entry is set to 1, and the values in the file are not used mixhop_dataset.py. The paper does not mention this. The row L2 normalization before the first layer is also not in the paper mixhop_trainer.py.
• Activation order matters with batch normalization. Equation 4 has no batch norm, while the code puts batch norm before the activation, with relu as the default mixhop_trainer.py mixhop_trainer.py. The paper does not name the activation §3.1. The example model uses tanh mixhop_model.py.
• Non-divisible output width drops columns. The grouping uses integer division by c. Leftover columns are ignored, and the code prints a warning mixhop_model.py.
• Expressiveness is not accuracy. The proof of the GCN negative result works in the linear case with X = I_n §3.3. The representability results do not show accuracy gains.
• Cost. The "no additional memory" claim [abstract] assumes each layer keeps a fixed total width. Each power adds its own weight matrix, and the largest power sets the number of sparse products per layer §3.2.
• Numbers that disagree. The random-split Pubmed value for the learned architecture is 83.9 in the text §6.2 but 83.8 in Table 3 tab. 3. The text also cites the dataset-statistics table where the Planetoid results are meant §6.2.
• Synthetic sizes. The text uses 5000-node graphs §5.1. The appendix figure shows a 500-node graph with 2798 edges app. A. The appendix formula for connection probability refers to |c_v - c_v|, which is probably meant to be |c_v - c_u| app. A.
• Baseline runs. For the Planetoid results, the rows above the double line are copied from Kipf and Welling, while the MixHop rows are rerun §6.2. Table 3 does not say where its baselines come from.

Lineage

• Builds on: the GCN layer and model of Kipf and Welling, which the paper uses as the vanilla GCN baseline §2.3, eq. 1, eq. 2. The introduction names two efficient approximations, one Chebyshev-based and the GCN §1.
• Compared against: MLP, Chebyshev, vanilla GCN and GAT on random splits tab. 3; LP, DeepWalk, ICA, ManiReg, SemiEmb and Planetoid on the Planetoid splits tab. 1; the P = {1} MixHop baseline tab. 1.
• Related code in the repository: the N-GCN trainer and scripts, for a separate paper cited in the README README.md.
• Superseded by: not stated in the paper.