PaperlayerView exact revision on arXiv

Source-linked AI summary

Half-Hop: A graph upsampling approach for slowing down message passing

Mehdi Azabou, Venkataramana Ganesh, Shantanu Thakoor, Chi-Heng Lin, Lakshmi Sathidevi, Ran Liu, Michal Valko, Petar Veličković, Eva L. Dyer

arXiv:2308.09198v1cs.LGcs.SIstat.ML

TL;DR

Message passing can be limiting on heterophilic graphs, where connected nodes may belong to different classes. Half-Hop inserts slow nodes into the input graph to delay messages, and the paper reports improvements across supervised and self-supervised benchmarks, including heterophilic settings.

  • Problem

    Message passing can be limiting on complex heterophilic graphs, where nodes from different classes are connected, motivating flexible approaches that work across encoders and learning settings.

    Source: §1 · p. 1

  • Method

    Half-Hop upsamples the input graph by inserting slow nodes along edges to delay messages, without explicitly modifying the loss or encoder.

    Source: §1 · p. 1

  • Results

    Across supervised and self-supervised benchmarks, Half-Hop improves tested baselines; on heterophilic datasets, adding it to a simple GCN yields over 10% boost in performance.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    Half-Hop adds a useful option to the limited pool of graph augmentations and can be used across a wide range of datasets.

    Source: §6 · p. 9

    Further study is needed to understand Half-Hop's representation invariances and its performance on downstream tasks such as link prediction or graph classification.

    Source: §6 · p. 9

Abstract

from arXiv · show

Message passing neural networks have shown a lot of success on graph-structured data. However, there are many instances where message passing can lead to over-smoothing or fail when neighboring nodes belong to different classes. In this work, we introduce a simple yet general framework for improving learning in message passing neural networks. Our approach essentially upsamples edges in the original graph by adding "slow nodes" at each edge that can mediate communication between a source and a target node. Our method only modifies the input graph, making it plug-and-play and easy to use with existing models. To understand the benefits of slowing down message passing, we provide theoretical and empirical analyses. We report results on several supervised and self-supervised benchmarks, and show improvements across the board, notably in heterophilic conditions where adjacent nodes are more likely to have different labels. Finally, we show how our approach can be used to generate augmentations for self-supervised learning, where slow nodes are randomly introduced into different edges in the graph to generate multi-scale views with variable path lengths.

1. Introduction

Message passing can be limiting on heterophilic graphs, motivating flexible approaches that work across encoders and learning settings. Half-Hop adds slow nodes to the input graph, with reported gains in supervised and self-supervised learning and a focus on slowing oversmoothing.

1. Introduction

  • Message passing can be limiting on complex, heterophilic graphs and where degree distributions and connectivity vary, motivating flexible strategies across encoders and supervised and unsupervised settings.The introduction also frames robust learning across variable graph problems as a broader challenge.Source: §1 · p. 1
  • Half-Hop inserts slow nodes along graph edges to delay messages, modifying the input graph rather than the encoder or loss.This makes it plug-and-play with existing models.Source: §1 · p. 1
  • Half-Hop can serve as a standalone augmentation or be combined with other augmentations to improve state-of-the-art graph SSL models.The paper identifies designing graph views for contrastive learning as a challenge in graph SSL.Source: §1 · p. 2
  • Adding Half-Hop to a simple GCN yields over 10% boost in performance on heterophilic datasets.With GraphSAGE, Half-Hop achieves results comparable with state-of-the-art methods using more complex architectures.Source: §1 · p. 2
  • The paper studies Half-Hop theoretically and empirically, reporting that it slows the effects of oversmoothing.The analysis examines its impact on message-passing dynamics.Source: §1 · p. 2

2. Method

Half-Hop upsamples a graph by inserting slow nodes along edges and interpolating their features, then passes the modified graph to message-passing models. It can also produce sampled graph views for self-supervised learning.

2. Method

  • Graph upsampling introduces nodes along edges and interpolates their features, after which the modified graph can be passed to any message-passing neural network.The method draws an analogy to increasing image resolution by adding pixels.Source: §2 · p. 2

2.1. Background and Notation

  • Message passing updates each node by combining its previous embedding with aggregated neighbor embeddings; the section also describes GCN, GraphSAGE, and GAT variants.For GCN, the update uses shared learnable weights, an activation, and neighbor aggregation.Source: §2.1 · p. 2

2.2. Half-Hop: Graph upsampling by inserting slow nodes between adjacent nodes

  • Half-Hop splits a directed edge by inserting a slow node, making the original one-hop path two hops; both endpoint nodes send messages to it, which passes information onward in the original direction.The authors report this connectivity configuration as optimal relative to other motifs in their ablations.Source: §2.2 · p. 2
  • Slow-node features are initialized by linearly mixing source and target features, with α controlling their proximity to either endpoint.The paper tunes α on a validation set and reports robustness to it in many experiments.Source: §2.2 · p. 3

2.3. Combining Half-Hop with any MPNN

  • Original and slow nodes use the same message-passing rules, but only original-node embeddings are retained for downstream loss and encoder operations.At inference, the model can use either the original or Half-Hopped graph; augmenting then also uses Half-Hop's message-passing changes.Source: §2.3 · p. 3

2.4. Using Half-Hop to generate views for Self-supervised learning

  • For self-supervised learning, Half-Hop creates graph views with different neighborhood path lengths by sampling which nodes' incoming edges are half-hopped.The views use separate node-sampling probabilities, and only original nodes serve as positive or negative examples in the contrastive loss.Source: §2.4 · p. 3

3. Understanding Half-Hop

Half-Hop reshapes receptive fields and slows message-passing smoothing. Its effects differ by graph type, with lower risk on the examined heterophilic graphs and delayed oversmoothing on homophilic graphs.

3.1. Reshaping the node’s receptive field with Half-Hop

  • By routing 1-hop neighbors through slow nodes, Half-Hop reshapes the receptive field into a more gradual neighbor-weight decline and preserves self-weight over message-passing steps.The analysis uses a 2D planar graph and mean aggregation without learned weights.Source: §3.1 · pp. 3–4
  • Randomly half-hopping edge subsets generates different receptive fields for the same node, ranging from narrow to broad or hybrid, enabling multi-scale views for self-supervised learning.The illustrated probabilistic setting uses α = 0.5 and p = 0.75.Source: §3.1 · p. 4

3.2.1. DIFFUSION ON REAL-WORLD DATASETS

  • On homophilic graphs, Half-Hop widens the low-error basin and delays oversmoothing beyond the expected diameter-based shift; on heterophilic graphs, it lowers risk and stabilizes early Texas steps.For Chameleon, the passage also reports improved descent and overall test risk.Source: §3.2.1 · p. 5

3.2.2. ANALYZING THE EFFECT OF HALF-HOP ON GENERALIZATION

  • The theorem approximates risk through Half-Hop’s augmented covariance: its first term smooths at roughly half the original rate, while α boosts the spectrum and preserves small eigenvalues.The slower decay of small eigenvalues delays the point at which diffusion stops being beneficial.Source: §3.2.2 · pp. 5–6

4. Experimental Results

The experiments assess Half-Hop across supervised and self-supervised benchmarks, with especially strong gains on heterophilic graphs. Results also show improvements when Half-Hop is used to create self-supervised views or at inference time.

4.1. Experimental Setup

  • Experiments use GCN, GraphSAGE, and GAT; supervised tuning uses development sets, while SSL experiments use standard model-and-dataset hyperparameters.For heterophilic datasets, the setup follows the provided splits and the same hyperparameter-search protocol.Source: §4.1 · p. 6

4.2. Supervised node classification benchmarks

  • Supervised results show gains across datasets for GCN, while GraphSAGE varies; HH-GraphSAGE improves 1.81% on Amazon Computers.Experiments train GCN and GraphSAGE with and without Half-Hop on Wiki-CS, Amazon-Computers, Amazon-Photo, and Coauthor datasets.Source: §4.2 · pp. 6–7

4.3. Heterophilic benchmarks

  • On heterophilic benchmarks, Half-Hop improves simple encoders, including 21.8% on Chameleon with GCN and 28.38% on Texas with GAT.HH-GraphSAGE reaches performance comparable to more complex competitor approaches.Source: §4.3 · p. 7

4.4. Self-supervised learning benchmarks

  • Combining Half-Hop with BGRL and GRACE augmentations improves on the BGRL baseline, with GRACE gains of 2% on Amazon Photos and Coauthor-CS.As a standalone augmentation, Half-Hop performs comparably to FeatDrop, EdgeDrop, and GCA variants.Source: Table 3 · p. 7, §4.4 · p. 8
  • At inference time, HH-GRACE improves by more than 2% on Amazon-Photos and Coauthor-CS, with similar improvements for HH-BGRL over the 2-layer GCN baseline.Table 4 reports classification accuracy for SSL frameworks, encoders, and test-time graph choices.Source: Table 4 · p. 7, §4.4 · p. 8
  • With a 3-layer GCN, BGRL performance falls by an average of 0.8%, while deeper HH-BGRL improves, especially on WikiCS with homophily 0.66.Figure 4 shows the largest inference-time HH-BGRL boosts on more heterophilic nodes across tested datasets.Source: §4.4 · p. 8, Figure 4 · p. 8

5. Related Work

Related work groups graph augmentations into feature and edge perturbations, k-hop augmentation, inference-time graph manipulation, and self-supervised view generation. Half-Hop is contrasted with methods that expand receptive fields by reducing the receptive field instead.

5.1. Graph data augmentations for regularization

  • Feature augmentations include masking, dropout, adversarial perturbations, and mixup, while edge perturbations remove edges or use guidance to add them.Examples include DropEdge, GCA, GCC, and GAug.Source: §5.1 · p. 8
  • Diffusion-based k-hop augmentations connect more distant neighbors and expand receptive fields; Half-Hop instead reduces receptive fields, a zoom-in operation.The passage frames these as opposite receptive-field changes.Source: §5.1 · p. 8

5.2. Graph manipulation at inference time

  • Graph rewiring methods address sparse, heterophilic, or bottlenecked graphs through curvature-based, Cayley-graph, diffusion, or learned edge changes.Some supervised approaches use labels to remove task-irrelevant edges associated with oversmoothing in heterophilic neighborhoods.Source: §5.2 · p. 9

5.3. Self-supervised and contrastive learning methods

  • Graph SSL methods create positive views and bring their representations closer; GRACE uses contrastive loss, while BGRL avoids explicit negative examples.Common view augmentations include node and edge dropout, while GCA also uses topology and node attributes to choose edges to mask.Source: §5.3 · p. 9

6. Discussion

The discussion presents Half-Hop as a practical graph augmentation with results across supervised and self-supervised benchmarks. It also identifies open questions about generalization, invariances, and downstream tasks.

6. Discussion

  • Across 11 real-world datasets, Half-Hop improves simple encoders on heterophilic graphs and improves SSL methods as a standalone or combined augmentation.The discussion describes Half-Hop as integrating into existing workflows through a graph-only modification.Source: §6 · p. 9
  • Further study is needed to characterize Half-Hop's representation invariances and its performance on link prediction and graph classification.The discussion also identifies deeper analysis of augmentation effects on generalization as future work.Source: §6 · p. 9

A.1. Problem Setup

  • The appendix adopts Keriven (2022)'s risk framework; message passing changes the covariance-dependent risk term from Σ to A^2kΣ.Small eigenvalues decay faster than large ones, which can introduce harmful bias when β* aligns with eigenvectors having small eigenvalues.Source: §A.1 · pp. 13–14

A.2. Main Result

Half-Hop inserts slow nodes along edges, changing how messages propagate through the graph. The analysis finds slower spectral decay, and the tested HH connectivity scheme outperforms alternative motifs on three heterophilic datasets.

A.2. Main Result

  • Small eigenvalues decay at half the rate of ordinary MPNNs, while large eigenvalues largely preserve their magnitude under Half-Hop.The analysis describes the small-eigenvalue decay as λ(k) ∼ (1 + (1 − α)^2)λ^(k+1).Source: §A.2 · p. 14
  • Half-Hop replaces each original-node path with a route through a slow node, which copies its source node’s features.Source: §A.2 · pp. 14–15
  • After two Half-Hop message-passing rounds, original-node embeddings match those from one round without Half-Hop.Source: §A.2 · p. 15
  • The iterative covariance analysis approximates aggregation with multiplication by A under assumptions of Gaussian features and approximate feature independence for large n.Source: §A.2 · p. 15
  • Half-Hop’s modified covariance combines smoothing at roughly half the original rate with a second term that boosts self-loops, especially for small α.Source: §A.2 · p. 15

B.1. Testing the directionality of edges added in Half-Hop

  • HH performs significantly better than alternative slow-node connectivity schemes across Texas, Actor, and Cornell.The preferred scheme preserves the original edge direction and lets the slow node communicate with both source and target nodes.Source: §B.1 · p. 16, Table 1 · p. 16

B.2. Testing different initializations for the slow node

Linear interpolation initializes slow-node features from the source and target nodes. The alternatives tested—zero and random initialization—hurt model performance.

B.2. Testing different initializations for the slow node

  • Zero and random slow-node initializations hurt model performance, while linear interpolation mixes features from the real-node distribution.Source: §B.2 · p. 16, Table 2 · p. 16
  • Slow-node features are initialized by linearly interpolating the source and target node features.Source: §B.2 · p. 16

C. Details for Supervised Experiments

C.1. Homophilic Datasets

The homophilic supervised experiments use five real-world datasets and evaluate models on held-out test data after tuning on development data.

C.1. Homophilic Datasets

  • The homophilic experiments use Amazon Computers, Amazon Photos, Coauthor CS, Coauthor Physics, and WikiCS.Dataset statistics are listed in Table 3.Source: §C.1 · p. 17, Table 3 · p. 17
  • Amazon and Coauthor datasets use 60:20:20 train/validation/test splits, while WikiCS uses 20 provided masks.Source: §C.1 · p. 17
  • Hyperparameters are tuned on development data, and reported test results are averaged over 20 random splits.Source: §C.1 · p. 17

C.2. Heterophilic Datasets

The heterophilic supervised experiments use five low-homophily datasets, with model selection on training and validation data and test evaluation on provided splits.

C.2. Heterophilic Datasets

  • The heterophilic experiments use Texas, Wisconsin, Actor, Chameleon, and Cornell, each with homophily at or below 0.30.Dataset statistics are listed in Table 4.Source: §C.2 · p. 17, Table 4 · p. 17
  • The experiments use the ten provided train/validation/test splits, and hyperparameter tuning uses only training and validation data.Source: §C.2 · p. 17
  • The selected model’s test accuracy is reported after the test set is seen once.Source: §C.2 · p. 17

D. Details for Self-supervised Experiments

This block documents self-supervised evaluation and augmentation settings, then compares Half-Hop’s components with design choices in other GNNs for heterophilic node classification.

D. Details for Self-supervised Experiments

  • Evaluation uses full-graph pretraining, then a 10:10:80% train/validation/test node split and a frozen encoder with a linear classifier.The setup follows Thakoor et al. (2022); linear evaluation follows Veliˇckovi´c et al. (2019).Source: D. Details for Self-supervised… · p. 17
  • Self-supervised views reuse GRACE and BGRL edge- and feature-dropout settings, adding Half-Hop probabilities and slow-node initialization coefficients; Table 6 lists their values.The Half-Hop coefficients are used for linear interpolation to initialize slow nodes.Source: D. Details for Self-supervised… · p. 17, Table 6 · p. 18
  • Table 5 reports validation-selected best hyperparameters for experiments on heterophilic datasets.Source: Table 5 · p. 18

E. Comparisons with other GNNs

  • Half-Hop is lightweight: it adds no loss components and does not explicitly compute separate self-loop weights, unlike design choices detailed for MixHop, GGCN, and H2GCN.Table 7 compares architectural components and choices used to improve heterophilic node classification.Source: E. Comparisons with other GNNs · p. 18, Table 7

F. Visualization of the embedding space across layers

The visualizations suggest that Half-Hop improves class grouping and separation in latent space, with the clearest example in GraphSAGE on Citeseer.

F. Visualization of the embedding space across layers

  • With Half-Hop, same-class embeddings appear to cluster together and different classes to separate; this is clearest for GraphSAGE on Citeseer.The Citeseer figure caption likewise notes closer clustering of similar latents with Half-Hop.Source: F. Visualization of the embedding… · p. 19, Figure 3 · p. 20
  • Class separation appears strongest after layers two and three, consistent with the reported best raw performance for models two or three layers deep.Source: F. Visualization of the embedding… · p. 19
  • Interpret the dataset plots with care: class 1 is rare in Texas, Citeseer’s more numerous nodes make its latents denser, and Wisconsin’s class distribution differs from Texas’s.The Wisconsin caption notes that the same color scheme can look different because node-class distributions differ.Source: Figure 1 · p. 19, Figure 3 · p. 20, Figure 2 · p. 20
Loading 2308.09198v1…