PaperlayerView exact revision on arXiv

Source-linked AI summary

Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing

Yunchong Song, Chenghu Zhou, Xinbing Wang, Zhouhan Lin

arXiv:2302.01524v1cs.LG

TL;DR

Message-passing GNNs face heterophily and over-smoothing. Ordered GNN aligns rooted-tree depth with ordered neurons through gating, and the authors report state-of-the-art performance across homophily and heterophily settings while preventing over-smoothing in deep models.

  • Problem

    Message-passing GNNs can mix features of dissimilar neighboring nodes and produce indistinguishable representations when many layers are stacked.

    Source: §1 · p. 1

  • Method

    Ordered GNN uses gating to align rooted-tree hierarchies with ordered neurons, assigning embedding regions to subtrees of different depths.

    Source: §1 · p. 2

  • Results

    The authors report state-of-the-art performance across homophily and heterophily settings and effective prevention of over-smoothing in very deep models.

    Source: §4 · p. 9

  • Takeaways & Limitations

    Visualized gates can reveal the data's connecting type, offering an explainable graph model.

    Source: §1 · p. 2

    The gating mechanism learns from labeled samples and may be misled by corrupted graph structures or features, potentially causing negative social impact.

    Source: §5 · p. 10

Abstract

from arXiv · show

Most graph neural networks follow the message passing mechanism. However, it faces the over-smoothing problem when multiple times of message passing is applied to a graph, causing indistinguishable node representations and prevents the model to effectively learn dependencies between farther-away nodes. On the other hand, features of neighboring nodes with different labels are likely to be falsely mixed, resulting in the heterophily problem. In this work, we propose to order the messages passing into the node representation, with specific blocks of neurons targeted for message passing within specific hops. This is achieved by aligning the hierarchy of the rooted-tree of a central node with the ordered neurons in its node representation. Experimental results on an extensive set of datasets show that our model can simultaneously achieve the state-of-the-art in both homophily and heterophily settings, without any targeted design. Moreover, its performance maintains pretty well while the model becomes really deep, effectively preventing the over-smoothing problem. Finally, visualizing the gating vectors shows that our model learns to behave differently between homophily and heterophily settings, providing an explainable graph neural model.

1 INTRODUCTION

Ordered GNN aligns rooted-tree depth with ordered neurons to organize message passing by hop. The authors propose this design to address heterophily and over-smoothing while supporting strong performance across homophily and heterophily settings.

1 INTRODUCTION

  • Message-passing GNNs face heterophily, where neighboring nodes may have dissimilar features or labels, and over-smoothing, where stacked layers make node representations indistinguishable.The latter limits use of high-order neighborhood information.Source: §1 · p. 1
  • Prior approaches modify aggregation or use skip connections, but the authors say these can overlook multi-hop integration, mix information across orders, or lack node-personalized decisions.Some graph-rewiring approaches are not learnable and apply only to certain graphs.Source: §1 · pp. 1–2
  • The paper focuses on the combine stage of message passing, which it says is often implemented as a self-loop and can mix node features.Concatenation can address mixing, but with fixed embedding dimensions local information is squeezed at an exponential rate.Source: §1 · p. 2
  • The model aligns rooted-tree hierarchy with ordered neurons so messages are encoded according to their distance from the node.An ordered gating mechanism assigns neurons to subtrees of different depths.Source: §1 · p. 2
  • The authors report that this design supports superior performance in both homophily and heterophily settings.They describe the rooted-tree hierarchy as a general topological inductive bias with few assumptions about neighbor distributions.Source: §1 · p. 2
  • Ordered gating is intended to prevent feature mixing across hops, preserve ego and local information, and make gate visualizations a source of insight into data connectivity.The authors associate these properties with addressing heterophily and easing over-smoothing.Source: §1 · p. 2

2 OUR APPROACH

Ordered GNN aligns node-embedding neurons with rooted-tree depth through learned gates, changing the combine stage to keep information from different hops distinct. The approach is intended to handle both heterophily and over-smoothing while allowing flexible integration across neighborhood orders.

2.1 GRAPH NEURAL NETWORKS

  • Ordered GNN modifies the combine stage while retaining a mean-neighbor aggregation, and can be extended to GCN, GAT, or GIN by changing aggregation.The first update equation performs aggregation; the remaining equations implement the combine stage.Source: §2.1 · p. 3, §2.5 · p. 5

2.2 ALIGNING ROOTED-TREE WITH NODE EMBEDDING

  • Because each GNN layer adds one message-passing round, the k-th representation depends on the k-hop rooted-tree, whose nested depths guide neuron allocation.Information through depth k−1 uses a subset of the neurons assigned through depth k; neurons between split points encode exactly the k-th order.Source: §2.2 · pp. 3–4

2.3 THE SPLIT POINTS

  • Learned split points divide the ordered embedding into blocks, using gates to control how ego representations and newly aggregated context are combined.Soft expected gates keep the split operation differentiable; cumax← forms the expectation from split-position probabilities.Source: §2.3 · p. 4

2.4 THE DIFFERENTIABLE OR OPERATOR

  • SOFTOR combines each new gate with its predecessor to preserve the relative split-point constraints needed for rooted-tree alignment.The unconstrained predicted points could otherwise break the alignment; the softened OR makes the operation differentiable.Source: §2.4 · p. 5

2.5 PUTTING IT ALL TOGETHER

  • Case analyses describe how ordered gates can preserve useful first-order heterophily, capture useful second-order patterns, and limit cross-class mixing in homophily.The authors also state that split-point gaps remain flexible, so neuron allocation across orders is not fixed.Source: §2.5 · pp. 5–6, Figure 2 · p. 5

3 EXPERIMENTS

Experiments evaluate Ordered GNN on 11 datasets for homophily, heterophily, and over-smoothing, with two larger benchmarks used to examine scalability (p35).

3.1 HOMOPHILY AND HETEROPHILY

  • Ordered GNN consistently achieves state-of-the-art performance on both homophilous and heterophilous datasets.On homophilous datasets it matches GCNII; GCNII performs worse on heterophilous datasets, including a gap of more than 20 percent on Squirrel.Source: §3.1 · p. 7, Table 2 · p. 7

3.2 OVER-SMOOTHING

  • Across datasets and depths, Ordered GNN achieves the best accuracy and does not drop significantly as some baselines do.The reported result uses no training trick such as DropEdge.Source: Figure 3 · p. 7, §3.2 · p. 8

3.3 VISUALIZING THE GATING VECTORS

  • Gating patterns differ by setting: homophilous gates saturate after layer 4, heterophilous gates suppress many first-layer messages, and deep Cora gates nearly all close.On Texas, more gates saturate at layer 3; on Cora, the authors interpret closed deep-layer gates as rejecting farther-neighbor messages and keeping representations distinguishable.Source: §3.3 · p. 8, Figure 4 · p. 8

3.4 SCALING TO LARGER DATASETS

  • On larger benchmarks, Ordered GNN beats all listed baselines except UniMP on ogbn-arxiv and outperforms state-of-the-art models on the heterophily dataset.The authors note UniMP uses a larger graph Transformer and extra node-label information.Source: §3.4 · p. 9, Table 3 · p. 9

3.5 ABLATION STUDY

  • In the ablation, simple and ordered gating perform closely and improve on Bare GNN, while adding SOFTOR yields state-of-the-art performance.The comparison uses CiteSeer for homophily and over-smoothing and Wisconsin for heterophily.Source: §3.5 · p. 9, Table 4 · p. 9

4 CONCLUSION

Ordered GNN organizes message passing by aligning rooted-tree hierarchy with ordered neurons. The conclusion reports state-of-the-art results across homophily and heterophily, and effective prevention of over-smoothing in very deep models.

4 CONCLUSION

  • Ordered GNN aligns a central node’s rooted-tree hierarchy with ordered neurons to organize message passing by neighbor distance.The conclusion describes the model as more explainable and stronger in performance.Source: §4 · p. 9
  • The model achieves state-of-the-art results across datasets spanning homophily and heterophily settings.Source: §4 · p. 9
  • Ordered GNN effectively prevents over-smoothing when made very deep.Source: §4 · p. 9

5 ETHICS STATEMENT

The model uses graph topology without explicit assumptions about node labels, but its gating mechanism learns from labeled samples and may be misled by corrupted graph structure or features, with possible negative social impact.

5 ETHICS STATEMENT

  • The model makes no explicit assumptions about graph-node labels, avoiding the occurrence of social bias.Its inductive bias comes from graph topology.Source: §5 · p. 10
  • The gating mechanism must learn from labeled samples and may be misled by corrupted graph structure or features.Source: §5 · p. 10
  • Misleading gates on corrupted data can result in negative social impact, motivating corresponding ethical guidelines and constraints on model use.Source: §5 · p. 10

6 REPRODUCIBILITY STATEMENT

The reproducibility statement describes three evaluation settings and points to configuration, hyperparameter, environment, preprocessing, and code details for reproducing the experiments.

6 REPRODUCIBILITY STATEMENT

  • The model is tested in heterophily and homophily, over-smoothing, and larger-benchmark settings.Source: §6 · p. 10
  • Dataset and model configuration details appear in Section 3, while Appendix E describes grid search and the hardware and software environment.Source: §6 · p. 10
  • Tables 7–9 list hyperparameters for the proposed model and baselines, and Appendix E covers dataset download, loading, and preprocessing.Source: §6 · p. 10
  • Released source code lists reproduction steps and hyperparameters in YAML files.Source: §6 · p. 10

A.1 SOFT BINARY GATE

The soft binary gate represents ordered neuron assignments through probabilities over split positions. Across layers, gates tend toward saturation, while their relative split positions remain flexible.

A.1 SOFT BINARY GATE

  • A gate vector is represented as a distribution over categorical split positions, with softmax probabilities for each position.The probability that a gate is active at a position is obtained by summing probabilities for split positions at or beyond it.Source: §A.1 · p. 14
  • The gate vector’s expectation can be computed from the probabilities of its possible binary vectors.The described binary vectors consist of leading ones followed by zeros.Source: §A.1 · p. 14

A.2 CONVERGENCE RATE OF GATES

  • Gate vectors tend to saturate as the GNN gets deeper, but the saturation rate can vary across gate positions.Source: §A.2 · p. 14
  • Relative split-point magnitudes are not restricted between layers, allowing flexible neuron blocks for ego and neighborhood information at different orders.Source: §A.2 · p. 14

B.1 CONNECTIONS WITH RELATED WORKS

The discussion connects ordered gating to approaches for heterophily and over-smoothing, while distinguishing its use of a known rooted-tree structure from prior ordered-neuron work.

Heterophily

Over-smoothing

  • Ordered gating assigns different hop information to neuron blocks and locks ego information at hop=0 in a specified block, like initial connections in APPNP (Klicpera et al., 2018) and GCNII (Chen et al., 2020b).The approach also models relationships between contexts through tree hierarchy.Source: §B.1 · p. 15

Ordered Neurons

  • Unlike Ordered Neurons (Shen et al., 2018b), which induces syntactic trees from gating results, this method starts with a known rooted-tree structure and learns gates from it.Source: §B.1 · p. 15

B.2 LIMITATIONS

The model has limitations on scale-free graphs with both large hubs and low-degree nodes, and may need changes to its aggregation stage for complex node dependencies.

B.2 LIMITATIONS

  • On scale-free graphs with both large hubs and low-degree nodes, performance may depend on balanced data distributions; extreme cases may require few-shot learning.Source: §B.2 · p. 15
  • Because the model changes only the combine stage, modeling complex dependencies between nodes, such as in knowledge graphs, may require modifying aggregation.Source: §B.2 · p. 15
  • Addressing complex dependencies through aggregation changes is left for future work.Source: §B.2 · p. 15

B.3 BROADER IMPACT

The paper reports Ordered GNN outperforming other methods on three datasets at 64 layers and consuming similar training time to GAT. It also discusses possible over-squashing relevance and implicit positional encoding as broader implications.

B.3 BROADER IMPACT

  • On Squirrel, the authors suspect strong performance relates to over-squashing; its edge-to-node ratio is 40, 2.6 times Chameleon's.They suggest ordered gating preserves local and ego information, unlike baselines focused on aggregation that ignore the combine stage.Source: §B.3 · p. 15
  • Rooted-tree hierarchy may act as implicit positional encoding, representing node distance and importance without an external source.The paper distinguishes this from injected pre-computed graph heuristics and separate learnable positional-feature channels, and proposes exploring it for graph- and link-level tasks.Source: §B.3 · pp. 15–16

C RUNNING TIME

  • Ordered GNN consumes similar per-epoch training time to GAT across the four reported settings.The comparison uses matched framework, training/evaluation code, and hardware; Table 5 reports the averaged per-epoch times.Source: C RUNNING TIME · p. 16, Table 5 · p. 16

D FURTHER INCREASING THE GNN LAYERS

E EXPERIMENTAL DETAILS

The experiments use grid search and validation-based early stopping, with separate hyperparameter spaces for homophily and heterophily, over-smoothing, and expressivity settings. The reported setup also specifies computing hardware, software, and dataset handling.

E EXPERIMENTAL DETAILS

  • Models were tuned by grid search over dropout, learning rate, weight decay, and MLP layers, with validation accuracy selecting the best model and 200-epoch early stopping.Runs lasted up to 2,000 epochs; random seeds were fixed for reproducibility.Source: E EXPERIMENTAL DETAILS · pp. 16–17
  • Homophily and heterophily searches varied dropout, weight decay, learning rate, and MLP depth; parameters were tied across layers in specified datasets.Chameleon and Squirrel used empty features and reversed edges; best model-dataset hyperparameters are listed in Table 7.Source: E EXPERIMENTAL DETAILS · p. 17, Table 7 · p. 17
  • Over-smoothing searches covered dropout (0, 0.1, 0.2, 0.3, 0.4, 0.5), weight decay (5e-1, 5e-2, 5e-4, 5e-6, 5e-8), learning rate (0.01, 0.005, 0.001), and MLP layers (1, 2).Parameters for f(k) were tied across layers; best parameters for each model-dataset combination are reported in Table 7.Source: E EXPERIMENTAL DETAILS · p. 17
  • Expressivity experiments fixed MLP depth at three and learning rate at 0.005, varied dropout and weight decay, and tied parameters across layers on ogbn-arxiv.Best model-dataset hyperparameters are listed in Table 9.Source: E EXPERIMENTAL DETAILS · p. 17, Table 9 · p. 18

Related papers

Loading 2302.01524v1…