Back

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

Yunchong SongChenghu ZhouXinbing WangZhouhan Lin

article2023ICLR109 citations

Proposes Ordered GNN, a message-passing architecture that aligns neighborhood tree hierarchies with dedicated neuron blocks to prevent over-smoothing in deep networks while matching state-of-the-art accuracy across both homophilic and heterophilic graphs.

Listen

Graph neural networks are vital machine learning tools for analyzing interconnected data across domains like social networks, biology, and communication systems. However, standard models suffer from two major flaws: "over-smoothing," where node representations become indistinguishable and degrade in performance as models grow deeper, and "heterophily," where connected nodes have dissimilar attributes or labels, causing harmful mixing of conflicting information.

The article introduces and evaluates "Ordered GNN," a novel architecture designed to resolve both challenges by restructuring how information is merged across network neighborhoods. The approach aligns a node's local network hierarchy with specific blocks of artificial neurons in its representation. Using a specialized gating mechanism, the model assigns distinct neuron segments to specific neighborhood distances, preventing the conflation of local and distant features without requiring complex structural modifications.

The authors evaluated the framework across 11 benchmark datasets spanning citation and web networks, including large-scale graphs with over 160,000 nodes. The evaluation assessed classification accuracy across homophilic networks (where connected nodes are similar), heterophilic networks (where connected nodes differ), and deep network architectures scaling up to 64 layers.

The results show that Ordered GNN consistently matches or surpasses current state-of-the-art models across both network types. In heterophilic environments, it achieved major gains, such as reaching 62.44% accuracy on the dense Squirrel benchmark compared to 36.48%–38.47% from leading baselines. Crucially, the model maintained high classification accuracy even at depths of 32 and 64 layers, completely avoiding the severe performance drops typical of deep baseline architectures. Visualizations confirmed that the model automatically adapts its internal gating, preserving local identities on heterophilic data and filtering distant noise in deep configurations, all while maintaining competitive per-epoch training speeds comparable to standard models.

These findings demonstrate that managing the combination stage of message passing is an efficient, unified solution to multiple core graph learning limitations. By eliminating the need for ad-hoc heuristics, special edge-dropping training tricks, or separate models for different network types, Ordered GNN reduces engineering complexity and deployment risk in enterprise applications.

Organizations deploying graph machine learning should consider incorporating ordered gating principles into their model pipelines, particularly for deep networks or non-homophilic data. For future initiatives, the framework can be extended to link-level and graph-level tasks or tailored for complex graph types like knowledge graphs. However, practitioners should exercise caution on highly skewed, scale-free networks with extreme hub structures, where varying local topologies may require additional few-shot techniques or further data balancing.

Chinese Academy of SciencesShanghai Jiao Tong Universitygraph neural networksintermediate nodedestination nodesOrdered GNNordered message passingheterophily
arXiv: 2302.01524LUMIA-Group/OrderedGNN
  • Paper: A Generalization of ViT/MLP-Mixer to Graphs, Xiaoxin He et al. (2023). This work extends beyond local message passing by adapting vision-style patch and channel mixing to graphs, presenting an alternative way to bypass neighborhood over-squashing and long-range bottlenecks.
  • Paper: Simple and Efficient Heterogeneous Graph Neural Network, Xiaocheng Yang et al. (2023). It explores architectural simplifications and efficiency improvements for complex heterogeneous networks, continuing the investigation of tailored graph message passing.
Cover for Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing

Abstract

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.

Topics

graph neural networksintermediate nodedestination nodessource nodeshierarchical modelsms messages

Keywords

Ordered GNNordered message passingheterophilyover-smoothingmessage passinggraph neural networkshigh-order neighborspositional encodinglabel propagationnode representations

Table of Contents

  • 1 Introduction
  • 2 Our Approach
  • 2.1 Graph Neural Networks
  • 2.2 Aligning Rooted-Tree with Node Embedding
  • 2.3 The Split Points
  • 2.4 The Differentiable OR\operatorname{OR} Operator
  • 2.5 Putting it All Together
  • 3 Experiments
  • 3.1 Homophily and Heterophily
  • 3.2 Over-smoothing
  • 3.3 Visualizing the Gating Vectors
  • 3.4 Scaling to Larger Datasets
  • 3.5 Ablation Study
  • 4 Conclusion
  • 5 Ethics Statement
  • 6 Reproducibility Statement
  • References
  • A Proof
  • A.1 Soft Binary Gate
  • A.2 Convergence Rate of Gates
  • B Discussion
  • B.1 Connections with Related Works
  • B.2 Limitations
  • B.3 Broader Impact
  • C Running Time
  • D Further Increasing the GNN Layers
  • E Experimental Details

Knowls

  1. Knowl 1 — Ordered GNN Layer Formulation

    model/method

    Ordered GNN modifies the combine stage of graph neural message passing by ordering the hidden neurons to match the rooted-tree hierarchy of a node's multi-hop neighborhood. Given an unweighted graph G = (V, &\mathcal{E}) with node feature matrix X∈RN×FX \in \mathbb{R}^{N \times F}, an initial node representation is computed via an MLP projection hv(0)=fθ(Xv)∈RDh_v^{(0)} = f_\theta(X_v) \in \mathbb{R}^D for each node v∈Vv \in V.

    For layer k∈{1,…,K}k \in \{1, \dots, K\}, node vv updates its representation hv(k)∈RDh_v^{(k)} \in \mathbb{R}^D via the following message passing and ordered gating equations:

    mv(k)=MEAN({hu(k−1):u∈N(v)})m_v^{(k)} = \text{MEAN}\left(\{h_u^{(k-1)} : u \in \mathcal{N}(v)\}\right)

    g^v(k)=cumax←(fξ(k)(hv(k−1),mv(k)))=cumsum←(softmax(W(k)[hv(k−1);mv(k)]+b(k)))\hat{g}_v^{(k)} = \text{cumax}_\leftarrow\left(f_\xi^{(k)}\left(h_v^{(k-1)}, m_v^{(k)}\right)\right) = \text{cumsum}_\leftarrow\left(\text{softmax}\left(W^{(k)} [h_v^{(k-1)}; m_v^{(k)}] + b^{(k)}\right)\right)

    g~v(k)=SOFTOR(g~v(k−1),g^v(k))=g~v(k−1)+(1−g~v(k−1))∘g^v(k)\tilde{g}_v^{(k)} = \text{SOFTOR}\left(\tilde{g}_v^{(k-1)}, \hat{g}_v^{(k)}\right) = \tilde{g}_v^{(k-1)} + \left(1 - \tilde{g}_v^{(k-1)}\right) \circ \hat{g}_v^{(k)}

    hv(k)=g~v(k)∘hv(k−1)+(1−g~v(k))∘mv(k)h_v^{(k)} = \tilde{g}_v^{(k)} \circ h_v^{(k-1)} + \left(1 - \tilde{g}_v^{(k)}\right) \circ m_v^{(k)}

    where N(v)\mathcal{N}(v) is the immediate neighborhood of node vv, [⋅;⋅][\cdot ; \cdot] denotes vector concatenation, W(k)∈RDm×2DW^{(k)} \in \mathbb{R}^{D_m \times 2D} and b(k)∈RDmb^{(k)} \in \mathbb{R}^{D_m} are learnable parameters of the gating function fξ(k)f_\xi^{(k)}, ∘\circ denotes element-wise multiplication, and cumsum←\text{cumsum}_\leftarrow denotes cumulative summation evaluated from right to left across neuron indices.

  2. Knowl 2 — Alignment of Rooted-Tree Subtree Hierarchy with Node Embedding Blocks

    model/method

    The kk-hop neighborhood around a node vv can be represented as a rooted tree Tv(k)T_v^{(k)} of depth kk, with node vv at the root and its kk-th order neighbors at the leaves. Because lower-depth trees are strictly nested subtrees of higher-depth trees:

    Tv(0)⊆Tv(1)⊆⋯⊆Tv(k)⊆⋯⊆Tv(K)T_v^{(0)} \subseteq T_v^{(1)} \subseteq \dots \subseteq T_v^{(k)} \subseteq \dots \subseteq T_v^{(K)}

    Ordered GNN maps this nested hierarchy into the sequence of DD ordered neurons of the node embedding vector hv∈RDh_v \in \mathbb{R}^D by learning a monotonically non-decreasing set of split points:

    Pv(0)≤Pv(1)≤⋯≤Pv(k)≤⋯≤Pv(K)=DP_v^{(0)} \le P_v^{(1)} \le \dots \le P_v^{(k)} \le \dots \le P_v^{(K)} = D

    Information within the (k−1)(k-1)-th order tree Tv(k−1)T_v^{(k-1)} is confined to the first Pv(k−1)P_v^{(k-1)} neurons in hvh_v, while neurons located in the interval [Pv(k−1),Pv(k))[P_v^{(k-1)}, P_v^{(k)}) represent the delta between k−1k-1 and kk rounds of message passing. This structure restricts incoming messages from kk-th hop neighbors to specific neuron blocks, avoiding feature mixing across distinct topological distances.

  3. Knowl 3 — Soft Gating Vector Estimation via Cumulative Softmax

    equation

    To represent a split point Pv(k)∈{0,…,D−1}P_v^{(k)} \in \{0, \dots, D-1\} differentiably, the point is modeled as a categorical random variable with probability distribution p(Pv(k)=i)=softmax(z)ip(P_v^{(k)} = i) = \text{softmax}(z)_i, where z=W(k)[hv(k−1);mv(k)]+b(k)∈RDz = W^{(k)} [h_v^{(k-1)}; m_v^{(k)}] + b^{(k)} \in \mathbb{R}^D.

    The probability that the ll-th entry gv(k)[l]g_v^{(k)}[l] in a binary gating vector gv(k)∈{0,1}Dg_v^{(k)} \in \{0, 1\}^D equals 1 is given by the probability that Pv(k)≥lP_v^{(k)} \ge l:

    p(gv(k)[l]=1)=p(Pv(k)≥l)=∑i=lDp(Pv(k)=i)p(g_v^{(k)}[l] = 1) = p(P_v^{(k)} \ge l) = \sum_{i=l}^D p(P_v^{(k)} = i)

    Because gv(k)[l]∈{0,1}g_v^{(k)}[l] \in \{0, 1\}, its expected value equals p(gv(k)[l]=1)p(g_v^{(k)}[l] = 1). The expected gating vector g^v(k)=E[gv(k)]\hat{g}_v^{(k)} = \mathbb{E}[g_v^{(k)}] is computed across all dimensions simultaneously using the right-to-left cumulative softmax operator cumax←\text{cumax}_\leftarrow:

    g^v(k)=cumax←(z)=cumsum←(softmax(z))\hat{g}_v^{(k)} = \text{cumax}_\leftarrow(z) = \text{cumsum}_\leftarrow(\text{softmax}(z))

  4. Knowl 4 — Differentiable Bitwise OR Operator (SOFTOR)

    model/method

    To enforce the ordering constraint Pv(k−1)≤Pv(k)P_v^{(k-1)} \le P_v^{(k)} across GNN layers, the gating vector g~v(k)\tilde{g}_v^{(k)} at layer kk must maintain a coordinate-wise upper bound over its predecessor g~v(k−1)\tilde{g}_v^{(k-1)}. Ordered GNN achieves this differentiably via the SOFTOR\text{SOFTOR} operator:

    g~v(k)=SOFTOR(g~v(k−1),g^v(k))=g~v(k−1)+(1−g~v(k−1))∘g^v(k)\tilde{g}_v^{(k)} = \text{SOFTOR}\left(\tilde{g}_v^{(k-1)}, \hat{g}_v^{(k)}\right) = \tilde{g}_v^{(k-1)} + \left(1 - \tilde{g}_v^{(k-1)}\right) \circ \hat{g}_v^{(k)}

    where g^v(k)∈[0,1]D\hat{g}_v^{(k)} \in [0, 1]^D is the newly predicted soft gating vector at layer kk, and ∘\circ denotes Hadamard (element-wise) multiplication. Because g~v(k−1)[l]∈[0,1]\tilde{g}_v^{(k-1)}[l] \in [0, 1] and g^v(k)[l]∈[0,1]\hat{g}_v^{(k)}[l] \in [0, 1], the updated gate satisfies g~v(k)[l]≥g~v(k−1)[l]\tilde{g}_v^{(k)}[l] \ge \tilde{g}_v^{(k-1)}[l] for all dimensions l∈{1,…,D}l \in \{1, \dots, D\}, guaranteeing monotonic gate expansion across layers while remaining fully differentiable.

  5. Knowl 5 — Chunking Mechanism for Gating Network Efficiency

    model/method

    To reduce parameter count and computational complexity in the gating network, Ordered GNN groups hidden neurons into chunks using an integer chunking factor C∈N+C \in \mathbb{N}^+. The dimensionality of the predicted gating vector is reduced from the hidden embedding size DD to Dm=D/CD_m = D / C.

    Each gate coordinate in the predicted DmD_m-dimensional gating vector controls a contiguous block of CC hidden units in the node embedding hv(k)∈RDh_v^{(k)} \in \mathbb{R}^D, reducing the number of predicted gate parameters by a factor of CC.

  6. Knowl 6 — Flexibility of Inter-Layer Split Point Deltas Under SOFTOR

    theoretical result

    For the soft gating vector g~v(k)=g~v(k−1)+(1−g~v(k−1))∘g^v(k)\tilde{g}_v^{(k)} = \tilde{g}_v^{(k-1)} + (1 - \tilde{g}_v^{(k-1)}) \circ \hat{g}_v^{(k)}, the inter-layer finite difference is Δg~v(k)=g~v(k+1)−g~v(k)=(1−g~v(k))∘g^v(k+1)>0\Delta \tilde{g}_v^{(k)} = \tilde{g}_v^{(k+1)} - \tilde{g}_v^{(k)} = (1 - \tilde{g}_v^{(k)}) \circ \hat{g}_v^{(k+1)} > 0, ensuring monotonic gate growth. For any two indices i<ji < j, the difference in finite differences between dimensions is:

    Δg~i(k)−Δg~j(k)=g^j(k+1)∘(g~j(k)−g~i(k))+ϵ^(k+1)∘(1−g~i(k))\Delta \tilde{g}_i^{(k)} - \Delta \tilde{g}_j^{(k)} = \hat{g}_j^{(k+1)} \circ (\tilde{g}_j^{(k)} - \tilde{g}_i^{(k)}) + \hat{\epsilon}^{(k+1)} \circ (1 - \tilde{g}_i^{(k)})

    where ϵ^(k+1)=∑n=ij−1gn∗(k+1)\hat{\epsilon}^{(k+1)} = \sum_{n=i}^{j-1} g_n^{*(k+1)}, and gn∗(k+1)g_n^{*(k+1)} denotes the raw pre-accumulation softmax output from the linear gating layer at coordinate nn.

    Because each raw output gn∗(k+1)g_n^{*(k+1)} is produced independently by a linear layer without historical recurrence, the ratio g^j(k+1)/ϵ^(k+1)∈(0,+∞)\hat{g}_j^{(k+1)} / \hat{\epsilon}^{(k+1)} \in (0, +\infty) is unconstrained. Consequently, the convergence rate between different gate positions is unrestricted, proving that Ordered GNN constrains the relative ordering of split points (Pv(k−1)≤Pv(k)P_v^{(k-1)} \le P_v^{(k)}) without restricting the number of neurons ΔPv(k)=Pv(k)−Pv(k−1)\Delta P_v^{(k)} = P_v^{(k)} - P_v^{(k-1)} allocated to any individual hop.

  7. Knowl 7 — Node Classification Performance on Homophily and Heterophily Benchmarks

    empirical result

    Ordered GNN evaluated across 9 benchmark datasets (6 heterophilous web networks and 3 homophilous citation networks) using 10 random splits demonstrates state-of-the-art accuracy compared to classical GNNs, heterophily-specific baselines, and initial/residual connection methods.

    Model Texas Wisconsin Actor Squirrel Chameleon Cornell CiteSeer PubMed Cora
    Ordered GNN 86.22±\pm4.12 88.04±\pm3.63 37.99±\pm1.00 62.44±\pm1.96 72.28±\pm2.29 87.03±\pm4.73 77.31±\pm1.73 90.15±\pm0.38 88.37±\pm0.75
    H2GCN 84.86±\pm7.23 87.65±\pm4.98 35.70±\pm1.00 36.48±\pm1.86 60.11±\pm2.15 82.70±\pm5.28 77.11±\pm1.57 89.49±\pm0.38 87.87±\pm1.20
    GPRGNN 78.38±\pm4.36 82.94±\pm4.21 34.63±\pm1.22 31.61±\pm1.24 46.58±\pm1.71 80.27±\pm8.11 77.13±\pm1.67 87.54±\pm0.38 87.95±\pm1.18
    GGCN 84.86±\pm4.55 86.86±\pm3.29 37.54±\pm1.56 55.17±\pm1.58 71.14±\pm1.84 85.68±\pm6.63 77.14±\pm1.45 89.15±\pm0.37 87.95±\pm1.05
    GCNII 77.57±\pm3.83 80.39±\pm3.40 37.44±\pm1.30 38.47±\pm1.58 63.86±\pm3.04 77.86±\pm3.79 77.33±\pm1.48 90.15±\pm0.43 88.37±\pm1.25
    Geom-GCN 66.76±\pm2.72 64.51±\pm3.66 31.59±\pm1.15 38.15±\pm0.92 60.00±\pm2.81 60.54±\pm3.67 78.02±\pm1.15 89.95±\pm0.47 85.35±\pm1.57
    MixHop 77.84±\pm7.73 75.88±\pm4.90 32.22±\pm2.34 43.80±\pm1.48 60.50±\pm2.53 73.51±\pm6.34 76.26±\pm1.33 85.31±\pm0.61 87.61±\pm0.85
    JK-Net 83.78±\pm2.21 82.55±\pm4.57 35.14±\pm1.37 45.03±\pm1.73 63.79±\pm2.27 75.68±\pm4.03 76.05±\pm1.37 88.41±\pm0.45 85.96±\pm0.83
    GCN 55.14±\pm5.16 51.76±\pm3.06 27.32±\pm1.10 53.43±\pm2.01 64.82±\pm2.24 60.54±\pm5.30 76.50±\pm1.36 88.42±\pm0.50 86.98±\pm1.27
    GAT 52.16±\pm6.63 49.41±\pm4.09 27.44±\pm0.89 40.72±\pm1.55 60.26±\pm2.50 61.89±\pm5.05 76.55±\pm1.23 86.33±\pm0.48 87.30±\pm1.10
    GraphSAGE 82.43±\pm6.14 81.18±\pm5.56 34.23±\pm0.99 41.61±\pm0.74 58.73±\pm1.68 75.95±\pm5.01 76.04±\pm1.30 88.45±\pm0.50 86.90±\pm1.04
    MLP 80.81±\pm4.75 85.29±\pm3.31 36.53±\pm0.70 28.77±\pm1.56 46.21±\pm2.99 81.89±\pm6.40 74.02±\pm1.90 87.16±\pm0.37 75.69±\pm2.00

    Ordered GNN matches SOTA on homophilous datasets (tying GCNII on PubMed at 90.15% and Cora at 88.37%) and achieves large improvements on dense heterophilous graphs such as Squirrel (62.44% vs next-best GGCN at 55.17% and GCNII at 38.47%).

  8. Knowl 8 — Robustness to Over-Smoothing at Deep Model Configurations

    empirical result

    When scaling model depth to 64 layers on citation network benchmarks (Cora, CiteSeer, PubMed), Ordered GNN maintains high classification accuracy without requiring graph modification techniques like DropEdge.

    Methods (64 layers) Cora CiteSeer PubMed
    Ordered GNN 89.10 80.50 91.60
    GCN 52.00 44.60 79.70
    ResGCN 79.80 21.20 87.90
    JKNet 86.30 76.70 90.60
    IncepGCN 85.30 79.00 OOM
    GraphSAGE 31.90 16.90 40.70
    GCN+DropEdge 53.20 45.60 79.00
    ResGCN+DropEdge 84.80 75.30 90.20
    JKNet+DropEdge 87.90 80.00 91.60
    IncepGCN+DropEdge 88.20 79.90 90.00
    GraphSAGE+DropEdge 31.90 25.10 63.20

    While standard message passing networks (GCN, GraphSAGE) degrade severely at 64 layers due to over-smoothing, Ordered GNN outperforms both base deep models and models regularized with DropEdge.

  9. Knowl 9 — Performance on Large-Scale Homophily and Heterophily Benchmarks

    empirical result

    Ordered GNN evaluated on large-scale datasets with 169,343 nodes and 1,166,243 edges:

    Dataset GCN SGC LP CS JK-Net APPNP GCNII / LINK UniMP / H2GCN Ordered GNN
    ogbn-arxiv 71.74±\pm0.29 69.39 68.50 72.62 72.19±\pm0.21 66.38 72.74±\pm0.16 73.11±\pm0.21 72.81±\pm0.21
    arXiv-year 46.02±\pm0.26 32.83±\pm0.13 46.07±\pm0.15 42.17±\pm0.27 46.28±\pm0.29 38.15±\pm0.26 53.97±\pm0.18 49.09±\pm0.10 54.49±\pm0.29

    On the homophilous benchmark ogbn-arxiv (edge homophily H(G)=0.66\mathcal{H}(G)=0.66), Ordered GNN achieves 72.81% accuracy, outperforming GCNII (72.74%) and standard GNNs, trailing only UniMP (which uses a large Transformer backbone and masked node labels). On the heterophilous benchmark arXiv-year (edge homophily H(G)=0.22\mathcal{H}(G)=0.22), Ordered GNN achieves 54.49% accuracy, establishing a new state-of-the-art over LINK (53.97%) and H2GCN (49.09%).

  10. Knowl 10 — Ablation Study of Ordered GNN Components

    empirical result

    An ablation study isolating the architectural components of Ordered GNN shows progressive improvements across homophily (CiteSeer, 8 layers), heterophily (Wisconsin, 8 layers), and over-smoothing (CiteSeer, 32 layers) settings:

    Model Variant Homophily (CiteSeer 8L) Heterophily (Wisconsin 8L) Over-smoothing (CiteSeer 32L)
    Bare GNN (mean aggregator) 73.79 ±\pm 1.57 53.92 ±\pm 5.79 74.70
    +simple gating (Gated GNN) 75.78 ±\pm 1.49 86.27 ±\pm 5.23 79.30
    ++ordered gating (cumax) 76.45 ±\pm 1.35 85.69 ±\pm 4.90 79.40
    +++SOFTOR (Ordered GNN) 77.31 ±\pm 1.73 88.04 ±\pm 3.63 80.80

    Independent gate prediction (+simple gating) improves over Bare GNN by allowing selective suppression of messages, but the inclusion of ordered gating combined with the SOFTOR operator (+++SOFTOR) delivers the highest accuracy across all three settings.

  11. Knowl 11 — Gating Vector Interpretability Across Graph Regimes

    empirical result

    Visualizing the learned gating vectors g~v(k)\tilde{g}_v^{(k)} across network layers reveals distinct behaviors conditioned on the graph's structural properties:

    • Homophily: Gates distribute uniformly at layer 1 with a smooth gradient, and progressively saturate toward 1 as depth increases. After layer 4, most gate entries are saturated, suppressing higher-order aggregation precisely where standard GNNs begin to suffer from over-smoothing.
    • Heterophily: A large block of gates saturates to 1 in layer 1, preserving node ego embeddings by suppressing incoming neighbor representations. On datasets like Texas, gate saturation remains constant between layers 1 and 2, but expands at layer 3, demonstrating adaptive filtering of 1st-hop bad heterophily while preserving 2nd-hop shared neighborhood patterns.
    • Deep layers: In very deep models (e.g., 32–64 layers on Cora), almost all gates saturate to 1, completely shutting off message passing from distant nodes to retain distinct node representations.

  12. Knowl 12 — Limitations of Ordered GNN on Scale-Free Graphs and Relation Modeling

    limitation

    The authors identify two key limitations of Ordered GNN:

    1. Sensitivity to Degree Imbalance: In scale-free graphs featuring both extreme hub nodes and low-degree nodes, the neighborhood tree rollout varies significantly across nodes. Model performance can depend on degree balance, potentially requiring few-shot learning adaptations for outlier topologies.
    2. Reliance on Simple Aggregation for Complex Relations: Ordered GNN modifies only the combine stage of the message passing mechanism (using mean pooling for aggregation). Applying the model to multi-relational graphs, such as knowledge graphs with heterogeneous edge dependencies, will require extending the aggregation stage accordingly.

Coverage note — None was omitted; all contributed models, theoretical results, core benchmark tables (homophily, heterophily, over-smoothing, and large-scale), component ablations, gating interpretability analyses, and explicit limitations have been captured.

References

  1. 1.Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pp. 21–29. PMLR, 2019.
  2. 2.Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2020.
  3. 3.Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
  4. 4.Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. arXiv preprint arXiv:2101.00797, 2021.
  5. 5.Giorgos Bouritsas, Fabrizio Frasca, Stefanos P Zafeiriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
  6. 6.Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203, 2013.
  7. 7.Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3438–3445, 2020a.
  8. 8.Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International Conference on Machine Learning, pp. 1725–1735. PMLR, 2020b.
  9. 9.Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988, 2020.
  10. 10.Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936–9949, 2021.
  11. 11.Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in neural information processing systems, 29, 2016.
  12. 12.Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint arXiv:2110.07875, 2021.
  13. 13.Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems, 33:22092–22103, 2020.
  14. 14.Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp. 1263–1272. PMLR, 2017.
  15. 15.Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
  16. 16.Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  17. 17.Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118–22133, 2020.
  18. 18.Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin R Benson. Combining label propagation and simple models out-performs graph neural networks. arXiv preprint arXiv:2010.13993, 2020.
  19. 19.Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980, 2014.
  20. 20.Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang, Max Welling, and Richard Zemel. Neural relational inference for interacting systems. In International Conference on Machine Learning, pp. 2688–2697. PMLR, 2018.
  21. 21.Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
  22. 22.Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997, 2018.
  23. 23.Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. Policy-gnn: Aggregation optimization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 461–471, 2020.
  24. 24.Chang Li and Dan Goldwasser. Encoding social information with graph convolutional networks forpolitical perspective detection in news media. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2594–2604, 2019.
  25. 25.Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgcns: Can gcns go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pp. 9267–9276, 2019.
  26. 26.Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergcn: All you need to train deeper gcns. arXiv preprint arXiv:2006.07739, 2020a.
  27. 27.Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465–4478, 2020b.
  28. 28.Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
  29. 29.Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05493, 2015.
  30. 30.Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. arXiv preprint arXiv:2104.01404, 2021.
  31. 31.Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 338–348, 2020.
  32. 32.Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Is heterophily a real nightmare for graph neural networks to do node classification? arXiv preprint arXiv:2109.05641, 2021.
  33. 33.Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? arXiv preprint arXiv:2106.06134, 2021.
  34. 34.Yimeng Min, Frederik Wenkel, and Guy Wolf. Scattering gcn: Overcoming oversmoothness in graph convolutional networks. Advances in Neural Information Processing Systems, 33:14498–14508, 2020.
  35. 35.Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
  36. 36.Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903, 2019.
  37. 37.Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-Scale Attributed Node Embedding. Journal of Complex Networks, 9(2), 2021.
  38. 38.Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61–80, 2008.
  39. 39.Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. AI magazine, 29(3):93–93, 2008.
  40. 40.Yikang Shen, Zhouhan Lin, Athul Paul Jacob, Alessandro Sordoni, Aaron Courville, and Yoshua Bengio. Straight to the tree: Constituency parsing with neural syntactic distance. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 1171–1180, 2018a.
  41. 41.Yikang Shen, Shawn Tan, Alessandro Sordoni, and Aaron Courville. Ordered neurons: Integrating tree structures into recurrent neural networks. arXiv preprint arXiv:1810.09536, 2018b.
  42. 42.Yunsheng Shi, Zhengjie Huang, Shikun Feng, Hui Zhong, Wenjin Wang, and Yu Sun. Masked label prediction: Unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509, 2020.
  43. 43.José Suárez-Varela, Paul Almasan, Miquel Ferriol-Galmés, Krzysztof Rusek, Fabien Geyer, Xiangle Cheng, Xiang Shi, Shihan Xiao, Franco Scarselli, Albert Cabellos-Aparicio, et al. Graph neural networks for communication networks: Context, use cases and opportunities. arXiv preprint arXiv:2112.14792, 2021.
  44. 44.Ke Sun, Zhanxing Zhu, and Zhouchen Lin. Adagcn: Adaboosting graph convolutional networks into deep models. arXiv preprint arXiv:1908.05081, 2019.
  45. 45.Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. arXiv preprint arXiv:2106.06586, 2021.
  46. 46.Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. arXiv preprint arXiv:2111.14522, 2021.
  47. 47.Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10903, 2017.
  48. 48.Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint arXiv:2203.00199, 2022a.
  49. 49.Zhen Wang, Zhewei Wei, Yaliang Li, Weirui Kuang, and Bolin Ding. Graph neural networks with node-wise architecture. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 1949–1958, 2022b.
  50. 50.Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861–6871. PMLR, 2019.
  51. 51.Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826, 2018a.
  52. 52.Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pp. 5453–5462. PMLR, 2018b.
  53. 53.Yujun Yan, Jiong Zhu, Marlena Duda, Eric Solarz, Chandra Sripada, and Danai Koutra. Groupinn: Grouping-based interpretable neural network for classification of limited, noisy brain data. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 772–782, 2019.
  54. 54.Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. arXiv preprint arXiv:2102.06462, 2021.
  55. 55.Liang Yang, Mengzhe Li, Liyang Liu, Chuan Wang, Xiaochun Cao, Yuanfang Guo, et al. Diverse message passing for attribute with heterophily. Advances in Neural Information Processing Systems, 34:4751–4763, 2021.
  56. 56.Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. In International conference on machine learning, pp. 7134–7143. PMLR, 2019.
  57. 57.Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34:19665–19679, 2021.
  58. 58.Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
  59. 59.Dengyong Zhou, Olivier Bousquet, Thomas Lal, Jason Weston, and Bernhard Schölkopf. Learning with local and global consistency. Advances in neural information processing systems, 16, 2003.
  60. 60.Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. arXiv preprint arXiv:2009.13566, pp. 11168–11176, 2020a.
  61. 61.Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793–7804, 2020b.

Citation

MLA
Song, Y., et al. “Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing”. arXiv, 2023, http://arxiv.org/abs/2302.01524v1.
APA
Song, Y., Zhou, C., Wang, X., & Lin, Z. (2023). Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing. arXiv. http://arxiv.org/abs/2302.01524v1
Chicago
Song, Y., C. Zhou, X. Wang, and Z. Lin. 2023. “Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing”. arXiv. http://arxiv.org/abs/2302.01524v1.
Harvard
Song, Y. et al. (2023) “Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2302.01524v1.
Vancouver
1. Song Y, Zhou C, Wang X, Lin Z (2023) Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing. arXiv

BibTeX

@article{song2023ordered,
  title = {Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing},
  author = {Song, Yunchong and Zhou, Chenghu and Wang, Xinbing and Lin, Zhouhan},
  year = {2023},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2302.01524v1},
  eprint = {2302.01524}
}
Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF
License: Authors