PaperlayerView exact revision on arXiv

Source-linked AI summary

Edge Directionality Improves Learning on Heterophilic Graphs

Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, Michael Bronstein

arXiv:2305.10498v3cs.LGcs.SI

TL;DR

Many GNNs discard direction in real-world directed graphs, despite the possibility that it contains useful information. The paper introduces Dir-GNN, which separately aggregates incoming and outgoing edges, and reports state-of-the-art results on five directed heterophilic benchmarks while leaving homophilic performance almost unchanged.

  • Problem

    Many GNNs make directed input graphs undirected or propagate in only one direction, potentially discarding information relevant to downstream tasks.

    Source: §1 · p. 1

  • Method

    Dir-GNN extends MPNNs to directed graphs by separately aggregating incoming and outgoing edges.

    Source: §4 · p. 5

  • Results

    Dir-GNN achieves state-of-the-art results on five directed heterophilic benchmarks, while performance is almost unchanged on homophilic benchmarks.

    Source: §7 · p. 9

  • Takeaways & Limitations

    Treating graphs as directed improves effective homophily in heterophilic settings, with negligible or no impact in homophilic settings.

    Source: §1 · p. 2

    The conditions that increase effective homophily under directionality, Dir-GNN’s expressivity advantage on heterophilic graphs, and alternative in/out aggregation functions remain unexplored.

    Source: §7 · p. 9

Abstract

from arXiv · show

Graph Neural Networks (GNNs) have become the de-facto standard tool for modeling relational data. However, while many real-world graphs are directed, the majority of today's GNN models discard this information altogether by simply making the graph undirected. The reasons for this are historical: 1) many early variants of spectral GNNs explicitly required undirected graphs, and 2) the first benchmarks on homophilic graphs did not find significant gain from using direction. In this paper, we show that in heterophilic settings, treating the graph as directed increases the effective homophily of the graph, suggesting a potential gain from the correct use of directionality information. To this end, we introduce Directed Graph Neural Network (Dir-GNN), a novel general framework for deep learning on directed graphs. Dir-GNN can be used to extend any Message Passing Neural Network (MPNN) to account for edge directionality information by performing separate aggregations of the incoming and outgoing edges. We prove that Dir-GNN matches the expressivity of the Directed Weisfeiler-Lehman test, exceeding that of conventional MPNNs. In extensive experiments, we validate that while our framework leaves performance unchanged on homophilic datasets, it leads to large gains over base models such as GCN, GAT and GraphSage on heterophilic benchmarks, outperforming much more complex methods and achieving new state-of-the-art results.

1 Introduction

Many GNNs discard edge direction, despite directed real-world networks; the paper argues directionality can help in heterophilic settings. It introduces Dir-GNN, which separates incoming and outgoing aggregation, and reports gains on heterophilic benchmarks without harming homophilic performance.

1 Introduction

  • Most GNNs assume undirected input graphs, although many real-world networks are directed, and converting them or propagating in only one direction may discard useful information.The paper notes that this preprocessing became standard and that PyTorch-Geometric automatically makes some datasets undirected when loading them.Source: §1 · pp. 1–2
  • The historical preference for undirected graphs reflects early spectral GNN requirements and stronger results on homophilic node-classification benchmarks.The paper traces the first reason to the spectral methods’ use of symmetric Laplacians and orthogonal eigendecomposition.Source: §1 · p. 1
  • Dir-GNN improves results on heterophilic benchmarks, achieving state-of-the-art performance while leaving homophilic benchmark performance almost unchanged.The authors report that it outperforms methods designed for heterophily and previously proposed directed-graph methods.Source: §1 · p. 2
  • Dir-GNN extends any MPNN to directed graphs by separately aggregating incoming and outgoing edges.The authors also report that Dir-GNN leads to more homophilic aggregations than undirected counterparts.Source: §1 · p. 2
  • Accounting for edge direction substantially increases effective homophily in heterophilic settings, with negligible or no impact in homophilic settings.The paper presents this as a key observation motivating its study of directionality.Source: §1 · p. 2

2 Background

This background frames the paper around semi-supervised node classification on attributed graphs, homophily measures, and message passing. It introduces compatibility matrices to describe class relationships and explains how MPNNs aggregate neighbor information.

2 Background

  • The paper frames its task as semi-supervised node classification on an attributed graph with node features and labels.It distinguishes the directed adjacency matrix from an undirected one that records an edge if either orientation exists.Source: §2 · p. 2

2.1 Homophily and Heterophily in Undirected Graphs

  • The class compatibility matrix H captures the fraction of edges from nodes of class k to nodes of class l, representing homophily beyond a single scalar.Homophilic datasets concentrate matrix mass on the diagonal, while heterophilic datasets concentrate it away from the diagonal.Source: §2.1 · p. 3

2.2 Message Passing Neural Network

  • An MPNN iteratively updates node embeddings using aggregation and combination maps, with messages carrying neighbor information.Because MPNNs send messages along graph edges, they suit settings where adjacent nodes often share labels but can struggle when neighboring nodes must be separated.Source: §2.2 · p. 3

3 Heterophily in Directed Graphs

The section argues that directionality can raise effective homophily in heterophilic graphs, while having little impact in homophilic graphs. It defines effective homophily across possible higher-order directed neighborhoods and shows why mixed-direction paths matter.

3 Heterophily in Directed Graphs

  • The section extends homophily metrics to weighted, directed message-passing matrices and higher-order neighborhoods.Using S=A or S=A⊤ gives homophily based on outgoing or incoming edges, respectively.Source: §3 · pp. 3–4
  • Effective homophily is the maximum weighted node homophily across the graph’s possible hops; the empirical analysis focuses on 2-hop matrices.Directed graphs have multiple possible k-hop matrices, while an undirected graph has only A^k.Source: §3 · p. 4
  • For heterophilic graphs, AA⊤ and A⊤A are among the most homophilic diffusion matrices, but undirected 2-hop averaging dilutes A⊤A with less homophilic A².The example contrasts citation paths that reach older papers with papers that share citations.Source: §3 · pp. 4–5
  • Effective homophily gains are around 3% for homophilic datasets and almost 30% for heterophilic datasets.The comparison is for directed versus undirected graphs.Source: §3 · p. 4, Table 1 · p. 4
  • Synthetic directed graphs have higher effective homophily than their undirected counterparts, with a larger gap at lower homophily levels.The same figure reports that only Dir-Sage(α=0.5), using both directions, almost perfectly solves a directionality-dependent synthetic task.Source: §3 · p. 4, Figure 2 · p. 5

4 Directed Graph Neural Network

Dir-GNN extends message-passing networks to directed graphs by aggregating incoming and outgoing information separately. The section also establishes its directed expressivity advantage over conventional directed or undirected MPNNs.

4 Directed Graph Neural Network

  • Dir-GNN extends MPNNs by separately aggregating incoming and outgoing neighbors, with the two aggregators able to use independent parameters and normalizations.Its implementation can weight the two directions with a tunable or learnable α.Source: §4 · pp. 5–6
  • Using both directions includes mixed-direction multi-hop terms, avoids ignoring nodes with zero degree in the chosen direction, and preserves expressivity.Dir-GCN, Dir-Sage, and Dir-GAT retain their base models’ per-layer computational complexity but use twice as many parameters.Source: §4 · p. 6

4.1 Expressive power of Dir-GNN

  • Dir-GNN can match D-WL expressivity when its aggregation and combination maps meet the stated injectivity conditions.The theorem’s informal statement specifies injective AGG(k)← and COM(k) maps.Source: §4.1 · p. 7
  • Dir-GNN is strictly more expressive than MPNNs applied to either undirected or directed graphs.The paper reports that this theoretical result aligns with empirical comparisons in which Dir-GNN performs comparably or better, typically under heterophily.Source: §4.1 · p. 7

5 Related Work

Prior directed-GNN approaches include specialized spectral methods and models that use limited direction information. The section positions Dir-GNN as a general framework and relates it to relational GNNs and existing approaches to heterophily.

5 Related Work

  • Several directed spectral methods use the same weights for incoming and outgoing neighbors, are specialized architectures, and face scalability limits.GatedGCN is cited as an example of a model that aggregates only from out-neighbors.Source: §5 · p. 7
  • Dir-GCN can be viewed as an R-GCN on an augmented graph with separate original-edge and inverse-edge relation types.The paper also describes its work as an in-depth investigation of directionality’s relation to graph homophily.Source: §5 · p. 7
  • Heterophilic GNN approaches include learning generalized negative graph weights and enlarging neighborhoods to use higher-hop similarity.The latter approach draws on the observation that similar nodes may be more likely beyond one hop.Source: §5 · p. 7
  • Table 2 reports little or no directionality improvement on homophilic datasets, but large accuracy improvements on heterophilic datasets.The table compares base MPNNs on undirected graphs with their Dir-GNN extensions on directed graphs.Source: Table 2 · p. 8

6 Experiments

Across the experiments, Dir-GNN improves results on heterophilic graphs, from a synthetic task to real-world benchmarks, while its gains depend on preserving and using edge direction. It also reaches state-of-the-art results on all five tested heterophilic datasets.

6.1 Synthetic Task

  • Dir-Sage(α = 0.5), using both edge directions, almost perfectly solves the synthetic task; using one direction reaches around 75% accuracy, while undirected GraphSage is no better than random.The task labels nodes according to whether the mean in-neighbor feature exceeds the mean out-neighbor feature.Source: §6.1 · p. 8

6.2 Extending Popular GNNs with Dir-GNN

  • 10% to 20% absolute accuracy gains appear across GCN, GraphSage, and GAT on heterophilic datasets; on homophilic datasets, directionality leaves performance unchanged or slightly hurts.The comparison uses the best Dir-GNN results over α ∈ {0, 0.5, 1}.Source: §6.2 · p. 8

6.3 Comparison with State-of-the-Art Models

  • Dir-GNN achieves new state-of-the-art results on all five directed heterophilic datasets, outperforming complex methods designed for heterophily.The authors note that selective directional aggregation helps address a limitation of DiGCN and MagNet on Squirrel and Chameleon.Source: Table 3 · p. 9, §6.3 · p. 9

7 Conclusion

The paper concludes that Dir-GNN uses edge direction to improve effective homophily and heterophilic node classification, and is more expressive than conventional MPNNs. The appendix illustrates the directionality argument and develops the framework’s expressivity analysis.

7 Conclusion

  • Dir-GNN is strictly more expressive than MPNNs and achieves state-of-the-art results on the five tested directed heterophilic benchmarks, while performance is almost unchanged on homophilic benchmarks.The authors identify further work on conditions for higher effective homophily, expressivity on heterophilic graphs, and alternative in/out aggregation forms.Source: §7 · p. 9

A Compatibility Matrices

  • For Arxiv-Year, the directed diffusion matrices A and A⊤ have more distinguishable class rows than the undirected diffusion operator Au, despite remaining heterophilic.The appendix presents compatibility matrices for Citeseer-Full and Chameleon as well.Source: A Compatibility Matrices · p. 14

B Harmless Heterophily Through Directions

  • The toy graph illustrates harmless heterophily: direction preserves distinct class-neighborhood patterns, and mixed 2-hop operators A⊤A and AA⊤ have perfect homophily, unlike the undirected 2-hop.Making the toy graph undirected makes its classes harder to distinguish.Source: B Harmless Heterophily Through… · p. 14, Figure 5 · p. 15

C Extension of Popular GNNs

  • The directed GAT extension computes attention coefficients over in-neighbors and out-neighbors separately.The corresponding attention matrices are row-stochastic and supported on A and A⊤, respectively.Source: C Extension of Popular GNNs · p. 15

D.1 (Directed) Weisfeiler-Lehman Test

  • D-WL refines node colors using the node’s prior color and separate sets of in- and out-neighbor colors.The paper focuses on a directed Weisfeiler-Lehman variant that treats incoming and outgoing neighbors separately.Source: §D.1 · p. 16

D.2 Expressiveness and color refinements

  • Color refinement can be used to reason about graph discrimination when graphs are represented by multisets of vertex colors or an injection of those multisets.The paper uses this link to analyze discriminative power at the node level, relevant to node classification.Source: §D.2 · p. 17

D.3 MPNNs on Directed Graphs

  • The appendix distinguishes directed MPNNs, which propagate according to edge direction, from undirected MPNNs, which propagate equally along incident edges.With no bidirectional edges, the latter is equivalent to converting the graph to undirected form and applying an undirected MPNN.Source: §D.3 · p. 17

D.4 Comparison with D-WL

  • Under the theorem’s injectivity assumptions, Dir-GNN is as expressive as D-WL; the appendix illustrates this with directed graphs that Dir-GNN can distinguish but MPNN-D cannot.The stated assumptions include injective aggregation and combination functions and an injective readout.Source: §D.4 · p. 17, Figure 6 · p. 19

D.5 Comparison with MPNNs

Dir-GNN is strictly more expressive than MPNNs that use only directed or undirected propagation; simple relational symmetrization can also erase distinctions between directed graphs.

D.5 Comparison with MPNNs

  • Dir-GNN is strictly more expressive than both MPNN-D and MPNN-U.Source: §D.5 · pp. 19–20
  • On the illustrated graph pair, MPNN-D cannot distinguish the graphs, while Dir-GNN can distinguish them after two D-WL iterations.The proof notes a simple one-layer Dir-GNN can assign the graphs distinct representations.Source: §D.5 · p. 20
  • The Fig. 7 pair is distinguishable by Dir-GNN but not by any MPNN-U model.Source: Figure 7 · p. 21

E Exploring Alternative Representations for Directed Graphs

  • Encoding directed edges as two undirected relations can map non-isomorphic directed graphs to the same representation, whereas a cited source/destination-node construction can represent directed graphs equivalently [52].Source: E Exploring Alternative… · p. 23, Figure 8 · p. 23

F MPNN with Binary Edge Features

The binary-edge-feature alternative augments each directed edge with an inverse edge carrying a distinct feature; explicit edge messages raise its memory cost relative to Dir-GNN.

F MPNN with Binary Edge Features

G Relation with Existing Methods for Directed Graphs

This material compares directed-graph methods and documents synthetic-graph generation, experiment settings, and hyperparameter searches.

G Relation with Existing Methods for Directed Graphs

  • DGCN uses A⊤A and AA⊤ alongside Au, but is limited to homophilic datasets, two-hop matrices, a GCN-like architecture, and explicit matrix computation.The passage contrasts this with Dir-GNN's use of directed one-hop edges and reports benefits from five or six layers.Source: G Relation with Existing Methods for… · p. 24

H.1 Effective Homophily of Synthetic Graphs

  • Synthetic directed graphs are generated by modified preferential attachment, with heterophily controlled by class compatibility and no bidirectional edges by construction.The experiments use 1,000 nodes, five classes, and m = 2.Source: §H.1 · p. 24

H.2 Synthetic Experiment

  • The synthetic node-classification task labels each node according to whether its in-neighbor feature mean exceeds its out-neighbor feature mean.The graph has 5,000 nodes, edge probability 0.001, and scalar features sampled uniformly from [−1, 1].Source: §H.2 · p. 25

H.3 Experimental Setup

  • Experiments use Adam for up to 10,000 epochs with validation-accuracy early stopping, and report mean and standard deviation over 10 runs.Patience is 200 except for Chameleon and Squirrel, where it is 400; dataset splits vary by dataset.Source: §H.3 · p. 25

H.4 Directionality Ablation Hyperparameters

  • The directionality ablation uses shared hyperparameters across models and datasets, including learning_rate = 0.001, hidden_dimension = 64, and num_layers = 3.It also sets norm = True and jk = max.Source: §H.4 · p. 25

H.5 Comparison with State-of-the-Art Results

  • Dir-GNN comparisons with state-of-the-art results use grid searches over model type, learning rate, hidden dimension, layers, jumping knowledge, normalization, dropout, and α.Source: §H.5 · p. 25

H.6 Baseline Results

The baseline results show directionality substantially improves accuracy on heterophilic datasets, while offering no significant gain or a slight decline on homophilic datasets.

H.6 Baseline Results

  • Reported GNN baseline results draw on prior papers and reimplementations, with sources varying by model and dataset.Source: §H.6 · p. 25
  • For directed baselines, the study uses PyTorch Geometric Signed Directed implementations of DiGCN and MagNet and tunes their model-specific hyperparameters.Source: §H.6 · p. 25
  • On heterophilic datasets, adding directionality substantially improves accuracy, while on homophilic datasets it does not significantly improve or may slightly impair performance.The table compares base MPNNs on undirected graphs with Dir-GNN extensions on directed graphs, including α settings for in-edges, out-edges, or both.Source: Table 10 · p. 26

I.1 Synthetic Experiment

On the synthetic task, Dir-GNN variants using both edge directions significantly outperform the other configurations, while one-direction models reach 70%–75% accuracy and undirected models resemble a random classifier.

I.1 Synthetic Experiment

  • Using both directions (α = 0.5) significantly outperforms the other configurations for GraphSage, GCN, and GAT on the synthetic task.The two-direction configuration does not reach 100% accuracy.Source: §I.1 · p. 26
  • One-direction models obtain between 70% and 75% accuracy on the synthetic task.The passage reports this for models using only one direction, without distinguishing which direction.Source: §I.1 · p. 26
  • Undirected models on the synthetic task perform akin to a random classifier.Source: §I.1 · p. 26

I.2 Ablation Study on Using Directionality

The ablations show that direction choice can matter greatly when many nodes lack incoming edges, while using both directions is generally preferred. A single Dir-GCN layer improves on undirected GCN on Arxiv-Year, and Dir-GNN performance is similar across most α values except at the endpoints; Dir-Sage adds only marginal runtime.

I.2 Ablation Study on Using Directionality

  • On Chameleon and Squirrel, out-edge-only propagation performs better than using both directions, with an accuracy gap greater than 40% between α = 0 and α = 1.About 62% of Chameleon nodes and 57% of Squirrel nodes have no in-edges, so in-only propagation leaves those nodes with zero features; using both directions is generally preferred.Source: §I.2 · p. 27

I.3 Ablation Study on Using a Single Layer

  • A one-layer Dir-GCN significantly outperforms one-layer undirected GCN on Arxiv-Year, despite lacking access to the more homophilic directed 2-hop.Source: §I.3 · p. 27

I.5 Runtime Analysis

  • Dir-Sage validation accuracy is compared with Sage over time, and Dir-Sage has only a marginal runtime increase despite using two separate weight matrices.Per-epoch runtimes are 0.71 ± 0.59 seconds for Dir-Sage and 0.57 ± 0.48 seconds for Sage, on one NVIDIA V100 GPU with 16GB memory.Source: Figure 12 · p. 28, §I.5 · p. 28

I.4 Ablation Study on Different Values of α

  • Dir-GNN results on Arxiv-Year are largely similar across α values other than α = 0 and α = 1, which show a large drop.Source: §I.4 · p. 28

Related papers

Loading 2305.10498v3…