Improving Graph Neural Networks by Learning Continuous Edge Directions
Authors: Seong Ho Pahng
Sahand Hormoz
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Directed Graphs
Graph Laplacian
Continuous Edge Directions
Graph Ensemble Data
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce a novel graph Laplacian and graph neural network (GNN) framework that allows learning of continuous edge directions alongside the GNN parameters, leading to improved performance on both undirected and directed graphs.

Abstract: Graph Neural Networks (GNNs) traditionally employ a message-passing mechanism that resembles diffusion over undirected graphs, which often leads to homogenization of node features and reduced discriminative power in tasks such as node classification. Our key insight for addressing this limitation is to assign fuzzy edge directions---that can vary continuously from node $i$ pointing to node $j$ to vice versa---to the edges of a graph so that features can preferentially flow in one direction between nodes to enable long-range information transmission across the graph. We also introduce a novel complex-valued Laplacian for directed graphs with fuzzy edges where the real and imaginary parts represent information flow in opposite directions. Using this Laplacian, we propose a general framework, called Continuous Edge Direction (CoED) GNN, for learning on graphs with fuzzy edges and prove its expressivity limits using a generalization of the Weisfeiler-Leman (WL) graph isomorphism test for directed graphs with fuzzy edges. Our architecture aggregates neighbor features scaled by the learned edge directions and processes the aggregated messages from in-neighbors and out-neighbors separately alongside the self-features of the nodes. Since continuous edge directions are differentiable, they can be learned jointly with the GNN weights via gradient-based optimization. CoED GNN is particularly well-suited for graph ensemble data where the graph structure remains fixed but multiple realizations of node features are available, such as in gene regulatory networks, web connectivity graphs, and power grids. We demonstrate through extensive experiments on both synthetic and real graph ensemble datasets that learning continuous edge directions significantly improves performance both for undirected and directed graphs compared with existing methods.

Published as a conference paper at ICLR 2025
IMPROVING GRAPH NEURAL NETWORKS BY LEARN- ING CONTINUOUS EDGE DIRECTIONS
Scong Ho Pahng!. & Sahand Hormoz
'Department of Chemistry and Chemical Biology, Harvard University
DDepartment of Data Science, Dana-Farber Cancer Institute
*Department of Systems Biology, Harvard Medical School
"Broad Institute of MIT and Harvard spahngeg. ha raaardeeee edu, sahand_hormo haw.aamd.aaaaadeeeee.mm.
ABSTRACT
Graph Neural Networks (GNNs) traditionally employ message-passinn mech- anism that resembles diffusion over undirected graphs, which often leads to ho- mogenization of node features and reduced discriminative power in tasks such as node classification. Our key insight for addressing this limitation is to assign fuzzy edge directions-ttat can vary continuously from node pointing to node j to vice versa-to the edges of a graph that features can preferentially flow in one di- rection between nodes to enable long-range information transmission across the graph. We also introduce novel romplex-valued Laplacian for directed graphs with fuzzy edges where the real and imaginary parts represent information flow opposite directions. Using this Laplacian, we propose a general framework, called Continuous Edge Direction (CoRD) GNN, for learning on graphs with fuzzy edges and prove its expressivity limits using a generalization of the Weisfeiler-Leman (WL) graph isomorphism test for directed graphs with fuzzy edges. Our architec- ture aggregates neighbor features scaled by the learned edge directions and pro- cesses the aggregated messages from in-neighbors and out-neighbors separately alongside the self-features of the nodes. Since continuous edge directions are differentiable, they can be learned jointly with the GNN weights via gradient- based optimization. CoED GNN is particularly well-suited for graph ensemble data where the graph structure remains fixed but multiple realizations of node fea- tures are available, such as in gene regulatory networks, web connectivity graphs, and power grids. We demonstrate through extensive experiments both synthetic and real graph ensemble datasets that learning continuous edge directions signif- icantly improves performance both for undirected and directed graphs compared with existing methods. Our code is available on GitHub
INTRODUCTION
Graph Neural Networks (GNNs) have emerged a powerful tool for learning from data that is structured as graphs, with applications ranging from social network analysis to molecular chemistry (Kipf Welling, 2017 Zhou al., 2020 Gilmer et al., 2017). GNNs typically employ a message passing mechanism where nodes aggregate and then transform feature information from their neigh- bors at each layer, enabling them to learn node representations that capture both local and global graph structures. When the graph is undirected, the aggregation of node features mimics diffu- sion process. Each node's representation becomes the averaged features of its immediate neighbors, leading to a homogenization of information across the graph. As depth increases, this diffusion of information culminates in uniform state where node representations converge towards a constant value across all nodes, which severely limits the discriminative power of GNNs, especially in tasks
such as node classification (Rusch et al. 2023a Oono & Suzuki 2020
Cai & Wang 2020
Li et al.
2018a Keriven 2022 Chen al. 2020al Wu al. 2023 2024).
"Corresponding author.

---

Published as a conference paper at ICLR 2025
Our key insight for improving the performance of GNNs to alter the nature of information transmission between nodes from diffusion to flow. To do so, add direc- tions to the edges of a graph so that features can be prop- agated from node u; to its neighbor node vy without recip- rocal propagation of information from node v; to node U,. Unlike diffusion, where information uniformly spreads across available paths, flow is directional and preserves the propagation of information across longer distances within a graph, as illustrated in Figure [ In general, the optimal information propagation could require edges whose directions fall anywhere in the continuum of node 2/ pointing to node U to vice versa.
(a)
(b)
Figure 1: (a) When edges are undi- rected, information diffuses across the graph and long-range transmission of information between nodes 1 and 2 is not possible. (b) Once the optimal edge directions are learned, information can flow directly from node I to node 2.
To capture such continuous edge directions, we propose concept of 'fuzzy edges,' where the direction of an edge between any two nodes V/ and Fj is not discrete but continuous value. An edge's s orientation can range con- tinuously-from exclusively pointing from node ny to node Vj. through a fully bidirectional state, to exclusively pointing from node My to node Uj. Therefore, "fuzzy' direction essentially controls the relative amount of information flow from node 2 to node By and the reciprocal flow from node oy to node u. To effectively model this directional flexibility, we introduce a complex-valued graph Laplacian called fuzzy Laplacian. In this framework, the real part of the ij-th entry in the fuzzy Laplacian matrix quantifies the degree of information transmission from node By to node d; while the imaginary part measures the flow from node 2; to node U/..
Next, we introduce the Continuous Edge Direction (CoED) GNN architecture. At each layer, a node's neighbors' features are scaled by the directions of their connecting edges and aggregated. This aggregation is performed separately for incoming and outgoing edges, following Rossi et al.) (202)), resulting in distinct features for incoming and outgoing messages. This is implemented by applying the fuzzy Laplacian to the node features, where the real and imaginary parts correspond to the features aggregated from incoming neighbors and outgoing neighbors, respectively. These ag- gregated features are then affine transformed using learnable weights and combined with the node's own transformed features. A nonlinear activation function is applied to obtain the updated node features. This process is repeated for each layer. The continuous edge directions have the added benefit that they are differentiable. During training, both the edge directions and weight matrices are learned simultaneously using gradient- based optimization to improve the learning objective.
Importantly, our approach is fundamentally different from methods such as Graph Attentions Net- work (GAT) (Veličković et al.) (0118) or graph transformers (Dwivedi & Bresson| 2021 Rampássk et al. 2022) that learn attention coefficients to assign weights to each edge of the graph based on the features (and potentially the positional encoding) of the nodes connected by that edge. While the attention mechanism can capture asymmetric relationships by computing direction-specifcc atten- tion weights based on node features, they do not learn edge directions as independent parameters. Instead, the attention coefficients from node By to node by are functions of the features of i, and Vy, and will change if node features change. In contrast, our approach introduces continuous edge directions as learnable parameters that are optimized end-to-end, independent of the node features.
Learning edge directions can make CoED susceptible to overfitting, especially when the same graph is used for both training and testing, as in standard node classification tasks. In such cases, edge directions may be optimized for the training nodes at the expense of effective information flow to the test nodes that are withheld during training. In contrast, CoED is very effective graph ensemble data, where the graph structure remains fixed but multiple realizations of node features and targets (such as node labels) are available. This allows optimization of information flow across all edges simultancously without masking parts of the graph for training and testing. Instead, training and testing splits are based on different feature realizations rather than on subsets of the graph. Graph ensemble data are increasingly common across various domains. For example, in biology, gene- regulatory networks are constant directed graphs where nodes represent genes and edges represent gene-gene interactions, while node features like gene expression levels vary across different cells. Similarly, in web connectivity, the network of websites remains relatively static, but traffic patterns change over time, providing different node feature sets on the same underlying graph. In power
2

---

Published as a conference paper at ICLR 2025
grids, the network of electrical components is fixed, while the steady-state operating points of these components vary under different conditions, yielding multiple observations on the same graph. In all these cases, fixed graph is paired with numerous feature variations. By applying CoED GNN to these scenarios, we demonstrate that learning edge directions significantly improves performance for both directed and undirected graphs. The main contributions of this paper the following:
We introduce a principled complex-valued valued graph Laplacian for graphs where edge direc- tions can vary continuously and prove that it is more expressive than existing forms of Laplacians for directed graphs, such as the magnetic Laplacian.
We propose an architecture called Continuous Edge Direction (CoED) GNN, which is a general framework for learning on directed graphs with fuzzy edges. We prove that CoED GNN is as expressive as weak form of the Weisfeiler-Leman (WL) graph isomorphism test for directed graphs with fuzzy edges.
Using extensive experiments, show that learning edge directions significantly improves performance by applying CoED GNN to both synthetic and real graph ensemble data.
PRELIMINARIES
graph defined as a pair 9 = (V,E), where {vi, V2, . un) is a set of nodes, and C V x V is a set of edges connecting pairs of nodes. Each node e is associated with feature vector f, E RD, where D is the dimensionality of the feature space, and collectively these feature vectors form the node feature matrix F E RNSD Additionally, each node is assigned prediction target, such as a class label for classification tasks or continuous value for regression tasks.
The connectivity of graph is encoded in adjacency matrix A E f0, 1)NNN If there is an undirected edge between i; and Bj. then both A.j = and A₁ = 1. For a directed edge, one of specifying the direction of information flow. A directed edge,
Ai Ajı is while the other Aij 1 and Ay: = 0, indicates that Uy sends information to U;. Hence, we refer to Uy as the in- neighbor of i and conversely to U; as the out-neighbor of vy. both A.j and Ay, = O, there is no edge between By and uy. Accordingly, in directed graph, we define two distinct degree matrices: the in-degree matrix Din = diag( (A1) and the out-degree matrix Dout diag(A (A 1).
GNNs iteratively processes node features via pressage-passing mechanism that leverages the struc- tural information of the graph G. This process involves two main steps at each layer l:
1. Message Aggregation: For each node Us an aggregated message m (1) (.)())) is computed from the features of its neighbors:
AGGREGATE
(((C""".r ENN))))
Here, (i)) denotes the set of nodes By that are connected to node i by an edge.
Feature Update: The feature vector of node iy is then updated using the aggregated message:
(1) UPDATE (p(L-
AGGREGATE and UPDATE are functions with learnable parameters, and their specific implemen- tations define different GNN architectures (Gimmer al.) 2017).
3 FORMULATION OF GNN ON DIRECTED GRAPHS WITH FUZZY EDGES
3.1 CONTINUOUS EDGE DIRECTIONS AS PHASE ANGLES
To describe a continuously varying edge direction between node v; and node Uj. we assign an angle to Uj. During aggregation of features from neighbors, features propagated from vy to e are scaled by a factor of cos 0ay. Conversely, the features that vy receives from 22 scaled by sin 81j. For example, when f,y 0, we have directed edge where vy sends messages to 2; but does not receive any messages from v, When 0,5 = T/4, the edge is undirected and the same scaling is applied the messages sent and received by Uy to and from vy.
0i, E [0, 2 to the edge connecting
3

---

Published as a conference paper at ICLR 2025
ie., cos x/4 sin 1/v2. To ensure consistency, require that the message received by oi from F should be equivalent to the message sent by 8 to v;- It follows that f = 8/2 - Bej- We define the phase matrix è E [0, π / to describe the directions of all the edges in a graph. (0), is only defined if there is an edge connecting nodes vs and Uj.
3.2 FUZZY GRAPH LAPLACIAN
To keep our paasage-ppsssngg GNN as expressive as possible, we define Laplacian matrix that, during the aggregation step, propagates information along directed edges but keeps the aggregated features from in-neighbors and out-ncighbors for each node distinct by assigning them to the real and imaginary parts of a complex number, respectively. For a given O we construct the corresponding fuzzy graph Laplacian Ly as follows. The diagonal entries (Lş) )it are zero as we cannot define edge directions for self-loops, and off-diagonal entries are either zero or a phase value.
if Aij Ag:
(LF)ss
(1)
(ep(()))))
otherwise
Since Osj and 05: are related by 0j: = T/2 Ozj. it follows that LF = -LL where f is the conjugate transpose. [e[L=] thus encodes all 4 edges scaled by cos Oig and [m[Lp] all i - edges scaled by sin 0z. In Appendix D we show the fuzzy graph Laplacian admits orthogonal eigenvectors with eigenvalues of the form a + ia with E R. Therefore, the eigenvectors of our Laplacian provide positional encodings that are informed by the directions of the edges in addition to their connectivities. We provide the visualizations of the eigenvectors in Appendix C A key implication of our Laplacian for GNN architectures is stated the following theorem.
GNN whose aggregation step is performed using the fuzzy graph Laplacian is as expressive as the weak form of the Weisfeiler-Leman (WL) graph isomorphism test for directed graphs with fuzzy edges.
Theorem 1. A
We prove this theorem in Appendix The most commonly used Laplacian for directed graphs is the magnetic Laplacian (Shubin 1994, Furutani et al. 22200] Zhang et al. 2021 He et al. 2022aa).
which also complex-valued. For directed graphs with fuzzy edges, the magnetic Laplacian not as expressive as the Laplacian proposed above. We provide proof in Appendix [ Briefly, the real and imaginary parts of the aggregated features produced by the magnetic Laplacian are both linear combinations of in- and out- neighbor messages. In principle, GNNs should be able to disentangle these linear combinations to recover the in- and out- neighbor messages. However, the linear combinations depend on the local neighborhood of each node which is distinct from one node to another, whereas GNN parameters are shared across all nodes. Therefore, in general, a GNN using the magnetic Laplacian loses the ability to disentangle the in- and out- neighbor messages at each node and thus has lower expressivity. Our Laplacian does not suffer from this limitation since by construction the real and imaginary values uniquely correspond to the in- and out- neighbor aggregated messages, respectively.
3.3 MODEL ARCHITECTURE: CONTINUOUS EDGE DIRECTION (COED) GNN
To ensure maximum expressivity, message-passeee paseeepppsnnggggae mechanism on a directed graph should, for each node, separately aggregate the features of the in nn-neighbors and the neighbeg,,,s, and independently process the two types of aggregated features and the self-features to obtain an updated feature for each node. To this end, define in- and out- edge weight matrices as A. Re[Lm] and A., [m[Lr]. respectively. We compute the in- and out- degree matrices as D = diag (A 1) and D diag (A_, 1), respectively. Following Rossi et al. (2024), but extending it to graphs with continuous edge directions, we define in- and out- fuzzy propagation matrices as
P 1/2 A. 1 1/2 and P D A D
Using these matrices, we compute in- and out- messages at layer / as
P P ((-1) and mD P ((-1)
(3)
which defines the AGGREGATE function.
4

---

Published as a conference paper at ICLR 2025
Input graph
graph
W model
Input features
model
phase
values
C
: lowa
Fignals
sargets
fXXy:w 0)
edge dirrctionss
Learned edge directions
1-+2
1-1
2-1
3-4
I-2
[-]
2-1
NiXsow
vs.
staps V. VoC 200 (EEIEEN)
Figure 2: Schematic of training with graph ensemble data. The input graph is undirected (left box). The graph ensemble data contains multiple realizations of node features and corresponding target values, either the node, edge, or graph level. The phase angle formulation allows continuous edge directions to be optimized alongside the GNN parameters in an end-to-end manner (middle box). The learned edge directions (right box) enable long range information transmission across the graph.
Since self-loops are omitted from Ly, we include current node features along with the two direc- tional messages in UPDATE function and update node features as,
F (F w m
m w m B())
where is an activation function, and w -it/+/// and B are self/in/out weight matrices and bias matrix, respectively.
The features at the final layer are then transformed using linear layer to obtain the output for specific learning task. We use end-to-end gradient-based optimization to iteratively update both the phase matrix è and the GNN parameters (()) self/t/-, and ( each layer, illustrated in Figure 2 We allow for the option learn different set of edge directions each layer, O just just
as we have distinct GNN parameters at each layer. We provide a runtime analysis of CoED against other GNNs in Appendix
RELATED WORK
The issue of feature homogenization in GNNs, known the oversmoothing problem. has been
a significant concern. Early studies identified the low-pass filtering effect of GNNs (Defferrard
let al.
2016
Wu et al. 2019), linking it oversmoothing and loss of discriminative power (Li
et al. 2018a Oono & Suzuki 2020). Proposed solutions include regularization techniques like edge
dropout (Rong al. 2020). feature masking (Hasanzadeh al. 2020). layer normalization Zhao
& Akoglu 2020). incorporating signed edges DDerr et al.) 2018). adding residual connections CCen
al. 2020b), gradient gating (Rusch et al. 2023b), and constraining the Dirichlet energy (Zhou
et al. 2021). Dynamical systems approaches have also been explored, modifying message passing
via nonlinear heat equations (Eliasof et al.) 202I), coupled oscillators (Rusch al.) (022). and
interacting particle systems (Wang et al.) 2022 Di Giovanni et al. (023). Other methods involve learning additional geometric structures, such as cellular sheaves (Bodnar et al. 2022).
Extending GNNs to directed graphs has been addressed through various methods. GatedGNN (Li ct al. 2016) processed messages from out-neighbors directed graphs. Some works constructed
symmetric matrices from directed adjacency matrices and their transposes to build standard Lapla-
cians (Tong et al. 2020b; Kipf & Welling 2017). while others (Ma et al., 2019 Tong et al., 2020a) developed Laplacians based on random walks and PageRank (Duhan al. (209).. MagNet (Zhang jet al. (02T)) utilized the magnetic Laplacian to represent directed messages a technique that has also been used adapt transformers to directed graphs (Geisler al. 2023) and visualize them
5

---

Published as a conference paper at ICLR 2025
(Fanuel al. 2018 FLODE (Maskey al. 2023) employed asymmetrically normalized adja- cency matrices within a neural ODE framework. DiTGNN (Rossi et al. 2024) separately processed the messages from in-neighbors and out-neighbors using asymmetrically normalized adjacency ma- trices, improving node classification on heterophilic graphs. A similar strategy was used in Koke & Cremers (2024). replacing the adjacency matrices with filters representing Faher polynomials. Recent graph PDE-based models (Eliasof et al., 2024; Zhao et al., 2023) introduced an advection term to model directional feature propagation alongside diffusion, assigning edge weights based on computed velocities between nodes, akin to attention coefficients in GAT. Finally, our approach conceptually related to He et al.] (2022b) where imbalance of incoming and outgoing messages across subsets of nodes is used to learn node embeddings for clustering.
GNNs have been increasingly applied in domains relevant to our work. In single-cell biology, GNNs have been used to predict perturbation responses in gene expression data (Roohani et al., 2023 Molho et al., 2024). with datasets compiled in scPerturb (Peidli et al.) (024). web traffic anal- ysis, a form of spatiotemporal data on graphs, GNNs often model temporal signals using recurrent neural networks on graphs (Li et al. 2018b Chen et al. 2018 Sahili & Awad, A with datasets and benchmarks provided by Py'oorch Geometric Temporal library (Rozemberczki al. 202I). In power grids, GNNs have been applied to predict voltage values (Ringsquandl et al. [202] and solve optimal power flow problems (Donon et al., 2020: Böttcher et al. 2023 Piloto et al. 2024). with
datasets compiled by Lovett et al. (2024).
EXPERIMENTS
5.1 NODE CLASSIFICATION WITHOUT EDGE DIRECTION LEARNING
While node classification is not the primary focus of our paper, we benchmarked our method on eleven standard datasets datasets-including both undirected and directed graphs covering a wide range of sizes and homophily levels-to highlight the advantage of our Laplacian over alternative forms of Laplacians for directed graphs as well as the benefit of processing self, in-neighbor, and out- neighbor features separately. Importantly, we do not learn edge directions in this case, and hence the phase value is either 0 or x /2 for directed graphs and π / /4 for undirected graphs. For comparison, we include the classical models: GCN (Kipf & Welling 2017). SAGE (Hamilton et al. 2017). GAT (Veličković et al. 2018); heterophill-sspeciie model, GGCN (Yan et al.) 202 directionality- aware models: MagNet (Zhang et al. 2021), FLODE (Maskey et al. (023). DirGNN (Rossi et al.) 2024]; and model that learns geometric structure of graph, Sheaf (Bodnar et al. (022).. We also include a model based on a Laplacian for directed graphs constructed from the transition matrix of the graph by Chung (2005), and Cooperative GNNs (Finkelshtein et al., 2023), which classify a node as broadcasting. listening, both, or neither based on its own and its neighbors' features. Finally, we also include MLP to highlight the effect of solely processing the nodes' self-features without aggregating features across the graph. Further details of the datasets and hyperparameters are provided in Appendix 1
As shown in Table CoED demonstrates competitive performance across all eleven datasets, rank- ing within the top three in terms of test accuracy for most. While all models exhibit compara- ble results on Cora and fiteseer-which are undirected and homophilic- their performances differ significantly on the directed, heterophilic graphs. The classical models developed for undirected graphs particularly struggle these datasets, with the exception of SAGE. This is because pro- cessing only the node's own features yields good performance, as evidenced by the MLP's results. In contrast, for the Squirrel and Chameleon datasets, processing directed messages along only one direction is crucial for good performance. Only FLODE, DirGNN, and CoED exhibit strong results on these datasets when configured accordingly. Specifically, for CoED, we introduce the hyper- parameter as in Rossi et al. 2024) to weigh the directional messages post aggregation, replacing m ( !) + m ( in Equation 4 with am (!! + (1 - a)m wtQ. In addition, we make the transformation of self-features optional.
Importantly, our results highlight the advantage of the fuzzy Laplacian over the magnetic Laplacian and the Chung Laplacian. In particular, the magnetic Laplacian does not process the aggregated messages from neightos and in-neighbors separately. Instead, it combines them into both the real and imaginary components of the aggregated feature vector, thus losing the opportunity to pro-

---

Published as a conference paper at ICLR 2025
Raman Empire
SNAP-Patenls
Troms
Wioomdn 0.21
Arsit- Year
Squirel 0.22
Chameloon 0.23
Cheoeer 0.24
Photo
Cora
Hom lool Undizeted
0.05
0.07
0.11
0.20
0.2%
0.81
MUP
11 54-005
29--3 31
30 10 21
57 17.51:1106 76
75 23.0M-12100
GCN
73369450744
31.76
39.47:1.47
1.
89.6588822
86.98:1.27
SAGE
85.744088
48.332821
124325514
81.18-5330
52.94:0:14
36.09-109
32:77
1.00
94.59
86.90
35.62
GGCN
74.40:20.4
00M
4.35
00M
37.46=1.57
38.71-344
17.14
94.50
87.95=1100
FLOOR
74 749711437
00M
77.57..224
80.20 135
00M
36.63
42.85.3.9
78.07 1200
50.88.0.25
05.00 03.03.00
86.4411.11 L.7
Sheaf
37 77.9420.5
00M
15.95
15.9555.11
89.41=4774
48.7799.00
39:03=1.73
41 41.95:3.42
17. 18.14
90 90,5050.3
95.01 0.17
87,30g1 15
MagNet
00M
5333251
65.7232
42.7
14.5-111
15 15.26-21.9
50.30 50.30255.7
94,58
82.8341 550
Chung
67.35
$0.54.100 1065
81.79
$3.01 .0.5
434
16.8
62.57.601
86-03
DIrGNN
83.78
85
85.88-2.11
2x
41.
76633-151
92
13
36.27=
91.3743432
4831
49
39.55-1-15
41:92:4015
62.76.0022
CoRD
92. 02.1710044
74.67
$4.99 4.53
87.84
64. 59 0.30
45.50 1:67
47.27
77.14.1.97
$2.88/0.1
95.83 0.11
87,00
Table 1: Comparison of baseline models and CoED (without edge direction learning) for node classification task across different types of graphs. Top three models are colored by First, Second, Third. The reported numbers are the mean and standard deviation of test accuracies across different splits. The first two rows report the homophily ratios of the graphs and whether they are directed or undirected. OOM indicates out-of-memory error.
cess the two separately. Moreover, during the Laplacian convolution, the directed messages further mix with self-features encoded in the real component. This results in poor performance by MagNet on directed graphs. The real-world directed graphs are often not strongly connected and thus the corresponding transition matrices' top left singular vectors are not informative as in the undi- rected cases. Since the Chung Laplacian is constructed from this singular vector, it shows relatively poor performance on such datasets as Roman- -amnane-mpirreeeee or Wisconsin compared the other directed models and instead delivers better results on datasets with undirected graphs. Sheaf also suffers on the datasets with directed graphs despite expanding the feature dimensions via an object called a stalk, because the sheaf Laplacian is constrained to be symmetric, thereby losing the ability to process directed messages. Taken together, our benchmarking demonstrates that CoED's ability to effectively process self-features and separately aggregate in-neighbor and out-neighbor messages using our fuzzy Laplacian enables it to achieve competitive performance across diverse datasets.
5.2 NODE REGRESSION ON GRAPH ENSEMBLE DATASET
Our key contribution is the joint learning of continuous edge directions alongside GNN parameters. This approach is particularly effective on graph ensemble data, where the graph structure remains fixed but multiple realizations of node features and targets exist. By learning edge directions for all edges without a need to mask parts of the graph, our method optimizes information flow across the entire graph. Learning edge directions for the node classification task above, where subset of nodes are masked for testing, would optimize the edges connected to the training node at the expense of those connected to the test nodes, diminishing overall performance. However, in the graph ensemble setting, learning continuous edge directions substantially improves performance, as we empirically demonstrate below on both synthetic and real-world datasets.
5.2. SYNTHETIC DATASETS
Directed flow on triangular lattice. We begin by applying CoED GNN to a node regression problem constructed on graph with continuous edge directions, where the target node features obtained by directionally message-passing the input node features over long distances across the graph. To generate such a graph with continuous edge directions exhibiting long-range order, we created a two-dimensional triangular lattice, assigning each node a position in the 2d plane. We then defined potential energy function V on this plane, consisting of one peak and one valley (Figure ((a)). The gradient of V yields a vector field with long-range order, which we used to assign continuous edge directions to the edges of the triangular lattice (Figure ((b). Using this graph, we performed the message passing step of Equation 4 iteratively 10
using random
matrices W... W... and Welff self that were shared across all 10 iterations, starting from the initial node features to obtain the target node values. We repeated this procedure 500 times for different random initial node features and generated an ensemble of input node features and corresponding target node values. During training, we provided all models with the undirected version of the triangular lattice graph (i.e., all f-j = म /4 for CoED). The goal of the learning task is to predict the target node values from the input node features. Additionally, CoED GNN is expected to learn
7

---

Published as a conference paper at ICLR 2025
gera actvadton
CEN(e)), - D Hi (kanddous grsas)
(a) Posential and gradient vector field
(b) directions luttice
regulatory network (GRN)
using GRN dynamics
Figure 3: Synthetic datasets. (a-b) Triangular lattice graph with edge directions derived from the gradient of a 2d potential function V (shown in a), creating long-range flows actoss the graph. (c-d) Gene regulatory network (GRN) represented as a directed graph where nodes are genes and edges denote interactions. Steady-state gene expression levels obtained from GRN dynamics, with perturbations simulated by setting the expression levels of specific genes to zero.
the underlying ground truth continuous edge directions of the graph as part of its training. Further details data generation are provided in Appendix A.2.
Gene Regulatory Network (GRN) dynamics. Gene Regulatory Networks (GRNs) are directed graphs where nodes represent genes and edges represent interactions between pairs of genes (Fig- ure ) In these networks, when two genes interact, either activates suppresses the other. We used Hill functions with randomly chosen parameters to define the dynamics of these gene- gene interactions. We constructed directed GRN graph with 200 nodes and randomly assigned interactions between them. Starting from random initial expression levels, we solved the system of nonlinear ordinary differential equations representing the GRN dynamics obtain the steady-state expression levels of all genes. Next, we modeled gene perturbations by setting the expression levels of either one or two genes (the perturbed set of genes) to zero and recomputing the steady-state expression levels for all genes using the same GRN dynamics (Figure 3(d) We performed this procedure for all single-gene perturbations and subset of double- double-gene gene perturbations, resulting in 1,200 different realizations. Our learning task is to predict the steady-state expression levels of all genes following perturbation (target node values) given the initial steady-state expression levels with the perturbed genes set to zero (input node features), We provided baseline models with the original graph and CoED with the undirected version of the graph. Further details of the data generation are provided in Appendix A.2.2
Results. 2 the test performances of CoED alongside several baseline models: classical models, GCN and GAT; a transformer based model with positional encoding, GraphGPS (Rampášek) et al. 2022); directionality-wware model, MagNet and the model based on the Chung Laplacian; higher-order model, DRew (Gutteridge et al. ); and a combination of directionality and higher-order model, FLODE. Details of the training setup, hyperparameter search procedure, and selected hyperparameters are provided in Appendix A.2.2
To identify which aspects of GNNs particularly effective for learning graph ensemble datasets, we analyze the baseline models' results detail. On the undirected lattice graph, MagNet provides only slight improvement over GCN, which is expected since MagNet reduces to ChebNet (Def-) ferrard et al. 2016) on undirected graphs, and GCN is a first-order truncation of ChebNet. How- ever, in the directed GRN experiments. MagNet shows substantial improvement over GCN. We also observe that higher-order GNNs like DRew and FLODE perform competitively on the undi- rected lattice graph. Notably, FLODE's instantancous enhancement of connectivity via fractional powers of the graph Laplacian outperforms DRew's 's more gradual incorporation of higher-hop mes- sages. However, both methods struggle on the directed GRN graph. The model based on the Chung Laplacian demonstrates strong performance on the lattice graph but offers only a modest improve- ment over GCN on the directed GRN. On both synthetic graphs, attention-based models GAT and GraphGPS-dedt deliver strong performance, coming in just behind CoED. GraphGPS, in particular, seems to benefit from its final global attention step, similar to how FLODE benefits from densifying the graph. We also notice that increasing the dimension of Laplacian positional encoding does not further enhance GraphGPS's performance. Interestingly, models that learn edge weights via atten- tion mechanisms outperform MagNet the directed GRN graph. This is likely because MagNet's
8

---

Published as a conference paper at ICLR 2025
unitary evolution of complex-valued features does not resemble the actual feature propagation (i.e., the GRN dynamics), in addition to the shortcomings highlighted in the previous section. CoED out- performs the attention-bres based models in both datasets as it optimizes the edge directions directly part of the learning objective independent of the node features. The shortcomings of GAT compared to CoED graph ensemble data are discussed further in Appendix H
We then investigated whether CoED can recover the ground truth continuous edge directions of the triangular lattice graph, given that the feature propagation steps during data generation closely resemble the message-passing operation of CoED. As shown in Figure + CoED correctly learns the true directions. Lastly, since both synthetic datasets are generated by propagating input features over multiple hops, we investigated how performance scales with model depth by training CoED and the second-best model with up to layers. Figure [ demonstrates that CoED continues to improve as depth increases, while the performance of the other models plateau at shallower depth.
Lattice
GRN
GCN
77.56 +0.47
69.38 =0.62
75*
GAT
9.41 +.0.55
12.07 11.50
Learned 0
GraphGPS
3.47 10.14
25.16
1.55
MagNet
75.06 10.03
43.42
Chung
8.03 +-0.3
62.95=0078
30"
DRew
28.55 +0.02
69.92 =0.15
15'
FLODE
7.54.10.05
70.31 .0.03
CoED
1.36 -0.06
5.02 +0045
75"
Table 2: Comparison of different models on the synthetic datasets. Values are test losses reported with a common factor of 10-3 in both columns.
Figure Learned theta vs. true theta for CoED applied directed flow triangular lattice syn- thetic dataset.
1e-2
CoED
CoED
GraphGPS
GAT
Sc
MSE loss
2e-3
1e-2
1e-3
Se-3
5e-4
2
6
10
# Model layers
Model layors
(a) Test loss vs. depth on triangular lnttice dataset
(b) Test loss vs. depth on GRN dataset
Figure 5: Model performance as function of depth.
5.2.2
REAL DATASETS
Perturb-seq (Dixit et al. 2016) is well-established experimental tech- nique single-cell biology that inspired the synthetic GRN experiment described earlier. In Perturb- seq experiments, one more genes in a cell are knocked out resulting in zero expression- as in our synthetic GRN dataset. The resulting changes in the expression levels of all other genes are then measured to elucidate gene-gene interactions. For our study, we used the Replogle-gwps dataset (Replogle et al. 2022, Peidli et al. 2024), which includes 9,867 distinct single-gene perturbations, along with control measurements from cells without any perturbation to establish baseline gene pression levels. The learning task is again predicting the expression levels of all genes following perturbation given the initial steady-state with the expression levels of the perturbed genes set to zero. Since there is no ground truth gene regulatory network (GRN) available for this dataset, we constructed undirected h-nearest neighbors graph to connect genes with highly correlated ex- pression levels. All models are trained using this heuristic graph. Details of the data processing procedure are provided in Appendix A.3.I
Single-cell Perturb-seq.
Wikipedia web traffic. We also modeled the traffic flow between Wikipedia articles using the WikiMath dataset, which is classified "static graph with temporal signals" in the PyTorch Ge-

---

Published as a conference paper at ICLR 2025
ometric Temporal library (Rozemberczki et al. 2021). In this dataset, each node corresponds to Wikipedia article on a popular mathematics topic, and each directed edge represents link from one article to another. The node features are the daily visit counts of all articles over a period of 731 consecutive days. The learning task is node regression: predict the next day's visit counts across all articles given today's visit counts. We trained the baseline models using the ground truth directed graph, while CoED was trained starting from the undirected version of the graph. Additional details are provided in Appendix A.3.2
Power grid. We applied CoED to the optimal power flow (OPF) problem using the OPF- Data (Lovett et al., (024) from the PyTorch Geometric library. In this dataset, a power grid is represented directed graph with nodes corresponding to buses (connection points for generators and loads) and edges representing transformers and AC lines. Input features are the operating values of all components under specific load conditions, and the targets are the corresponding AC-OPF lution values at the generator nodes. To compare different models, we used a consistent architecture across components but substituted different model layers for message passing. For CoED, they were again converted to undirected edges. Additional details are provided in Appendix A.3.3
Results. Table 3 reports the test performances of all baseline models and CoED on the three datasets. The baselines include GAT, MagNet, DirGCN, and DirGAT. We focus these models because attention-baat based approaches showed com- petitive performance on the synthetic datasets, and MagNet, which accounts for edge directions, per- formed well on the directed GRN dataset. Details of the training setup, hyperparameter search proce- dure, and selected hyperparameters are provided in Appendix A.3
Perturb-seq
Web traffic
Power grid
GCN
4.1310.08
7.07
28.56.16.08
MagNet
4.11=0011
6.94=0.02
18.05:2277
GAT
3.85=0003
6.00=0.03
13.57:41.7
DirGCN DirGAT
5.46:0.26
6.72:0004
6.15:0084
3.98
6.55=0.04
3.28:00117
CoED
3,56=0003
5.76:0005
2.91=0.11
Comparison of different methods real graph ensemble datasets. Values test losses reported with common factors of 10a 10-1, 10-3 for Perturb-seq, seq. web traffic, and power grid columns, respectively.
Table 3:
We observe that CoED achieves the best perfor- mance across all three datasets. On the Perturb-seq dataset with an undirected graph, MagNet performs similarly to GCN while DirGCN struggles. We at- tribute DirGCN's poor performance to clashing learnable parameters: uses two distinct weight matrices, W. and W w., applied to identical in- and out-neighbor aggregated messages in the case of undirected graphs. For propagation path of L hops, this results in 2 feature transformations, comprised of different combinations of the two weight matrices, which together reduce the model's ability to efficiently learn the optimal weight matrices. In contrast, DirGAT's s attention mechanisms break the symmetry of the undirected edges, leading to improved performance. CoED naturally ad- dresses this issue by learning the edge directions, which are visualized in Appendix [.] On the web traffic and power grid datasets, which have directed graphs, we observe similar trend. MagNet outperforms GCN due to its ability to process directed messages. However, GAT delivers better performance than MagNet, likely because its attention mechanism effectively captures important features. Since directed graphs create distinct feature propagation paths, DirGCN achieves sub- stantial performance gains. DirGAT further improves upon DirGCN by leveraging additional edge weight learning through an attention mechanism. CoED surpasses all these models, demonstrating the effectiveness of learning continuous edge directions.
CONCLUSION
We have introduced the Continuous Edge Direction (CoED) GNN, which assigns fuzzy, continuous directions to the edges of a graph and employs a novel complex-valued I Laplacian to transform in- formation propagation on graphs from diffusion to directional flow. Our theoretical analysis shows expressieeee that CoED GNN is more expressive than existing Laplacian- methods and matches the expres- siveness of an extended Weisfeiler-Lemat (WL) test for directed graphs with fuzzy edges. Through extensive experiments on both synthetic and real-world graph ensemble catasets-inclusee regulatory networks, web traffic, and power grids- we demonstrated that learning continuous edge directions significantly improves performance over existing GNN models.
gene
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
The authors thank Shishir Adhikari for his contributions to the conceptual formulation of this work and for numerous insightful discussions on graph Laplacians on directed graphs. We acknowledge funding from the National Institutes of Health (NIH)-National Heart, Lung, and Blood Institute (NHLBI)-ume under grant R01HL158269, and Advanced Research Projects Ageney for Health (ARPA- H) award IAYSAX000005.
REFERENCES
Cristian Bodnar, Francesco Di Giovanni, Benjamín Chamberlain, Pietro Liò, and Michael Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. In Advances in Neural Information Processing Systems, volume 35, pp. 24850-244665 2022.
Luis Böttcher, Hinrikus Wolf, Bastian Jung. Philipp Lutat, Marc Trageser, Oliver Pohl, Xiaohu Tao, Andreas Ulbig, and Martin Grohe. Solving ac power flow with graph neural networks under realistic constraints. In 2023 IEEE Belgrade PowerTech, pp. 1-7. IEEE, 2023.
Chen Cai and Yusu Wang. note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006.13311 133188 2020.
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.
Jinyin Chen, Xuanheng Xu, Yangyang Wu, and Haibin Zheng. Gc-Istm: Graph convolution embed- ded Istm for dynamic link prediction. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (ICCAI) pp. 219-225, 2018.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. International conference on machine learning, pp. 1725-1735, PMLR, 2020b.
Fan Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, 9: 1-19, 2005.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, 29, 2016.
Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-exppeesiive graph trans- former in linear time. In The Twelfth International Conference on Learning Representations, 2024. TtLLttpp:://penneriie.weet www.:nnteeoooommiddmmmmmoma
Tyler Derr Yao Ma, and Jiliang Tang. Signed graph convolutional networks. In 2018 IEEE Interna- tional Conference on Data Mining (ICDM), pp. 929-934. IEEE, 2018.
Francesco Di Giovanni, James Rowbottom, Benjamin Chamberlain, Thomas Markovich, and Michael M. Bronstein. Understanding convolution on graphs via energies. Transactions on Ma- chine Learning Research, 2023.
Atray Dixit, Oren Parnas, Biyu Li, Jenny Chen, Charles P Fulco, Livnat Jerby-Amon, Nemanja D Marjanovic. Danielle Dionne, Tyler Burks, Raktima Raychowdhury, et al. Perturb-seq: dissecting molecular circuits with scalable single-cell raa profiling pooled genetic screens. cell, 167(7); 1853-1866 2016.
Balthazar Donon, Rémy Clément, Benjamin Donnot, Antoine Marot, Isabelle Guyon, and Mare Schoenauer. Neural networks for power flow: Graph neural solver. Electric Power Systems Research, 189:106547, 2020.
Neelam Duhan, AK Sharma, and Komal Kumar Bhatia. Page ranking algorithms: a survey. In 2009 IEEE International Advance Computing Conference, pp. 1530-1537. IEFF, 2009.
11

---

Published as a conference paper at ICLR 2025
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Vijay Prakash Dwivedi, Yozen Liu, Anh Tuan Luu, Xavier Bresson, Neil Shah, and Tong Zhao. Graph transformers for large graphs. arXiv preprint arXiv:2312.11109. 2023.
Moshe Eliasof, Eldad Haber, and Eran Treister. Pde-gen: Novel architectures for graph neural networks motivated by partial differential equations. Advances in neural information processing systems, 34:383633849, 2021.
Moshe Eliasof, Eldad Haber, and Eran Treister. Feature transportation improves graph neural net- works. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11874- 11882, 2024.
Michaël Fanuel, Carlos M Alaíz, Ángela Fernández, and Johan AK Suykens. Magnetic eigenmaps for the visualization of directed networks. Applied and Computational Harmonic Analysis, 44( I): 189-199, 2018.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Ben Finkelshtein, Xingyue Huang, Michael Bronstein, and Ismail Ilkan Ceylan. Cooperative graph neural networks. arXiv preprint arXiv:2310.01267. 2023.
Satoshi Furutani, Toshiki Shibahara, Mitsuaki Akiyama, Kunio Hato, and Masaki Aida. Graph signal processing for directed graphs based on the hermitian laplacian. In Machine Learning and Knowledge Discovery in Databases: European Conference, ECML PKDD 2019, Würzburg, Germany, September 16-20, 2019, Proceedings, Part I, pp. 447-463. Springer, 2020.
Simon Geisler, Yujia Li, Daniel J Mankowitz, Ali Taylan Cemgil, Stephan Günnemann, and Cosmin Paduraru. Transformers meet directed graphs. International Conference on Machine Learning, pp. 11122. PMLR, 2023.
Justin Gilmer, Samuel Schoenholz, Patrick Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In International conference on machine learning, pp- 1263-1272. PMLR, 2017.
Mingyu Guan, Anand Padmanabha Iyer, and Taesoo Kim. Dynagraph: dynamic graph neural net- works scale. In Proceedings of the 5th ACM SIGMOD Joint International Workshop on Graph Data Management Experiences & Systems (GRADES) and Network Data Analytics (NDA), pp- 1-10, 2022.
Benjamin Gutteridge, Xiaowen Dong, Michael M Bronstein, and Francesco Di Giovanni. Drew: Dy- namically rewired message passing with delay. In International Conference on Machine Learning. pp. 12252-12267. PMLR, 2023.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems (NeurIPS), volume 30, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling. International conference on machine learning, pp. 4094-4104 4104. PMLR, 2020.
Yixuan He, Michael Perlmutter, Gesine Reinert, and Mihai Cucuringu. Msgan: A spectral graph neural network based on a novel magnetic signed laplacian. In Learning on Graphs Conference, pp. 40-1. PMLR, 2022a.
Yixuan He, Gesine Reinert, and Mihai Cucuringu. Digrae: digraph clustering based on flow imbal- ance. In Learning on Graphs Conference, pp. 21-1. PMLR, 2022b.
Kurt Hornik, Maxwell Stinchcombe, and Halbert White. Multilayer feedforward networks are uni- versal approximators. Neural nefworks, 2(5):359-366, 1989.
12

---

Published as a conference paper at ICLR 2025
Nicolas Keriven. Not too little, not too much: theoretical analysis of graph (over) smoothing. Advances in Neural Information Processing Systems, 35:2268- 22012 2022.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
C Koke and D Cremers. Holonets: Spectral convolutions do extend to directed graphs. In Interna- tional Conference on Learning Representations (ICLR), 2024.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018a.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In International Conference on Learning Representations (ICLR), 2018b.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings. 2016.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
Sean Lovett, Miha Zgubic, Sofia Liguori, Sephora Madjiheurem, Hamish Tomlinson, Sophie Elster, Chris Apps, Sims Witherspoon, and Luis Piloto. Opfdata: Large-scale datasets for ac optimal power flow with topological perturbations. arXiv preprint arXiv:2406.07234,, 2024.
Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. Spectral-based graph convolutional network for directed graphs. arXiv preprint arXiv:1907.08998 2019.
Sohir Maskey, Raffaele Paolino, Aras Bacho, and Gitta Kutyniok. fractional graph laplacian approach to oversmoothing. In Advances in Neural Information Processing Systems, 2023.
Dylan Molho, Jiayuan Ding, Wenzhuo Tang, Zhaoheng Li, Hongzhi Wen, Yixin Wang, Julian Vene- gas, Wei Jin, Renming Liu, Runze Su, et al. Deep learning in single-cell analysis. ACM Transac- fions Intelligent Systems and Technology. 15(3):1-62 2024.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations (ICLR), 2020.
Hongwei Pei, Bingzhe Wei, Kevin Chang, Yiming Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In Proceedings of the International Conference on Learning Represen- tations (ICLR), 2020.
Stefan Peidli, Tessa D Green, Ciyue Shen, Torsten Gross, Joseph Min, Samuele Garda, Bo Yuan, Linus Schumacher, Jake P Taylor-King, Debora S Marks, et al. scperturb: harmonized single- cell perturbation data. Nature Methods, pp. 1-10, 2024.
Luis Piloto, Sofia Liguori, Sephora Madjiheurem, Miha Zgubic, Sean Lovett, Hamish Tomlinson, Sophie Elster, Chris Apps, and Sims Witherspoon. Canos: fast and scalable neural ac- solver robust n-1 perturbations. arXiv preprint 240.:::20031166600 2024.
Adolfo Piperno et al. Isomorphism test for digraphs with weighted edges. In Proceedings SEA2018. Schloss Dagssuhl-Lcibiiz-eentter für Informatik GmbH, Dagstuhl Publishing, 2018.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. critical look evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference Learning Representations, 2023.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:14501-14515 2022.
13

---

Published as a conference paper at ICLR 2025
Joseph M Replogle, Reuben A Saunders, Angela N Pogson, Jeffrey A Hussmann, Alexander Lenail, Alina Guna, Lauren Mascibroda, Eric J Wagner, Karen Adelman, Gila Lithwick- Yanai, et al. Mapping information-rich senotype-phenotyy landscapes with genome-scale perturb-seq. seq. Cell, 185(14):2559-2777 2022.
Martin Ringsquandl, Houssem Sellami, Marcel Hildebrandt, Dagmar Beyer, Sylwia Henselmeyer, Sehastian Weber, and Mitchell Joblin. Power to the relational inductive bias: Graph neural net- works in electrical power grids. In Proceedings the 30th ACM International Conference Information & Knowledge Management, pp. 1538-1544 2021.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations (ICLR), 2020.
Yusuf Roohani, Kexin Huang, and Jure Leskovec. Predicting transcriptional outcomes of novel multigene perturbations with gears. Nature Biotechnology, pp. 1-9, 2023.
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael M Bronstein. Edge directionality improves learning heterophilic graphs. In Learning on Graphs Conference, pp. 25-1. PMLR, 2024.
Benedek Rozemberezki, Paul Scherer, Yixuan He, George Panagopoulos, Maria Sinziana Aste- fanoaei, Oliver Kiss, Ferenc Beres, Nicolas Collignon, and Rik Sarkar. Pytorch geometric tem- poral: Spatiotemporal signal processing with neural machine learning models. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management (CIKM), pp- doi: 10. 00.114//459637.448200
4564-4577 2021,
T Konstantin Rusch, Ben Chamberlain, James Rowbottom, Siddhartha Mishra, and Michael Bron- stein. Graph-coupled oscillator networks. In International Conference Machine Learning, pp. 18888-1888 18909. PMLR, 2022.
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprini arXiv:2303. 10993, 2023a.
T. Konstantin Rusch, Benjamin P. Chamberlain, Michael W. Mahoney, Michael M. Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. In International Conference on Learning Representations (ICLR), 2023b.
Zahraa Al Sahili and Mariette Awad. Spatio-temporal graph neural networks: A survey. arXiv preprint arXiv:2301.10569 2023.
Mikhail A Shubin. Discrete magnetic laplacian. Communications in mathematical physics, 164(2): 259-275, 1994.
Henan Sun, Xunkai Li, Zhengyu Wu, Daohan Su, Rong-Hua Li, and Guoren Wang. Breaking the entanglement of homophily and heterophily in sumi-vupe node classification. In 2024 IEEE 40th International Conference on Data Engineering (ICDE), pp. 2379-2392. IEEE, 2024.
Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David S Rosenblum, and Andrew Lim. Di- graph inception convolutional networks. In Advances in Neural Information Processing Systems (NeurIPS), 2020a.
Zekun Tong, Yuxuan Liang Changsheng Sun, David S. Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv preprint arXiv:2004. 13970, 2020b.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Yuelin Wang, Kai Yi, Xinliang Liu, Yu Guang Wang, and Shi Jin. Acmp: Allen-cahn message pass- ing with attractive and repulsive forces for graph neural networks. The Eleventh International Conference Learning Representations, 2022.
14

---

Published as a conference paper at ICLR 2025
F Alexander Wolf, Philipp Angerer, and Fabian Theis. Scanpy: large-scale single-cell gene pression data analysis. Genome biology, 19:1-5, 2018.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Sim- plifying graph convolutional networks. In International conference machine learning, pp- 6861-6871. PMLR, 2019.
Xinyi Wu, Zhengdao Chen, William Wei Wang, and Ali Jadbabaie. A non-asympiotic analysis of oversmoothing in graph neural networks. In The Eleventh International Conference on Learning Representations, 2023.
Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention- based graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations. 2019.
Shen Yan, Zeyuan Allen Xu, An Gu, Yufeng Sun, Charu Aggarwal, and Neil Shah. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In Pro- ceedings of the 30th ACM International Conference on Information and Knowledge Management (CIKM), pp. 1812-188 1821, 2021.
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, and Matthew Hirn. Magnet: A neural network for directed graphs. Advances in neural information processing systems, 34: 27003-27015, 2021.
Kai Zhao, Qiyu Kang, Yang Song, Rui She, Sijie Wang. and Wee Peng Tay. Graph neural convection convection-diftusion with heterophily. In Proceedings of the Thirty-Secone International Joint Conference on Artificial Intelligence, pp. 6656,4664, 2023.
Lingxiao Zhao and Leman Akoglu. Pairnorm: Tackling oversmoothing in GNNs. In International Conference Learning Representations (ICLR), 2020.
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applica- tions. Al open, 1:57-81, 2020.
Kaixiong Zhou, Xiao Huang, Daochen Zha, Rui Chen, Li Li, Soo-Hyun Choi, and Xia Hu. Dirichlet energy constrained learning for deep graph neural networks. Advances in Neural Information Processing Systems, 34:21834-21846, 2021.
15

---

Published as a conference paper at ICLR 2025
A EXPERIMENTAL DETAILS
A.1 NODE CLASSIFICATION
In Table MLP, GCN, SAGE, GAT, GGCN, and Sheaf's results Texas, Wisconsin, Citeseer, and Cora are taken from Bodnar et al.] ): MLP, GCN, MagNet, and DirGNN's results on Roman-Empire SNAP-Patents, and Arxiv-Yeas from Rossi et al. (2024); SAGE and GAT's re- sults on Koman-Empire, and GCN, SAGE, and GAT's results on the filtered versions of Squirrel and Chameleon from Platonov et al. 2 GCN, SAGE, GAT, and GGCN's 's results on AM-Computers and AM-Photo, and GGCN's s result on Roman Romin-Empire from Deng et al. (2024), SAGE and GAT's results on SNAP-Patents from Dwivedi et al. (0023); MagNet's result on Texas and Wisconsin from the original paper (Zhang et al. 2021) ) and the filtered versions of Squirrel and Chameleon from (Sun) ct al.
2024);
: Flode's 's results on Roman-Empire, Citeseer, and Cora from the original paper (Maskey
ct al.
2023) ; Co-GNN's results on Roman-Empire and Cora from the original paper (Finkelshtein
ct al. y023); GAT's result on Arxiv- Year from Lim et al. (202T). We trained CoED and baseline models to fill the remaining entries in the table. We describe the training procedures below. Texas, Wisconsin, Citeseer, and Cora datasets were downloaded using Py Geometric library (Fey & Lenssen 2019) with split= "geom-gen' argument use the 10 fixed 48%/32%/200 train- ing/validation/test splits provided by (Pei et al.] 2020). We downloaded AM-Computers and AM- Photo datasets from the same library but used the 60%620%%/20%
file provided in the repository Deng ct al. (2024). Since the original Squirrel and Chameleon datasets (Pei et al. (020) have re- dundant nodes, we used the filtered versions with directed graphs provided in the repository of Platonov et al. (2233). For Roman- SNAP-Patents, and Arxiv- Year datasets, we used the
dataloading pipeline provided in the repository Rossi al. (2024). All referenced results used the same splits as in our experiments.
Training. We evaluated the validation accuracy at each epoch, incrementing a counter if the value did not improve and resetting it to O when a new best validation accuracy was achieved. Train- ing was early-stopped when the counter reached a patience of 200. Unless otherwise mentioned, used the default hyperparameter settings of the respective models. We used the ReLU ac- tivation function and the ADAM optimizer in all experiments. Across all models, we searched over the following hyperparmeters: hidden dimension E [16, 256). learning rate E [5e-4, 2c-2], weight decay E [0, le-2), dropout rate E [0, and the number of layers E [2, 5). We addi- tionally searched over model-specific hyperparameters: the weight between in-/out-neighbor ag- gregated messages a E 0.5. 1). jumping knowledge (jk) E [None, 'cat', 'max') }. and layer- wise feature normalization (norm) (Tlue,Falsse for DirGNN, Chung, and CoED; self-feature transform E [True,False], self-loop value E {0, 1} for Chung and CoED; convolution type ('GCN', 'SAGE', 'GAT') for DirGNN; the order of Chebyshev polynomial
E (1,2), the global directionality a E [0, 0.25). and self-loop value E 10 for MagNet; the initial temperature for Gumbel-softtmx To E (0, 0.1), the number of environment network layers E [1, 4), the hid- den dimension of environment network E 16, 128). the number of action network layers E (1,2), the hidden dimension of action network {4, 8). layer norm E (True,Faase]) skip connection {True, False), model type in E {'Sum GNN', 'Mean GNN', 'GCN"); and the number of lay- ers E [1. 3). the number of both encoder and decoder layers E 21, and self-loop value E {0. 1} for FLODE. For FLODE, the number of layers refers to the number of forward Euler steps, and solved the heat equation with a minus sign, which was the default setup for node classification tasks. If the lelf- value is 1, the self-feature combined with neighbors' features in the AGGREGATE function. For CoED and Chung model on Roman-EEmire SNAP-Patents, and Arxiv-Yeas datasets, we only searched over the type of jumping knowledge ('cat', 'max'); setting all other hyperpa- rameters as reported in Rossi et al. (2024). For Sheaf, we searched over stalk dimension E [3, 8), hidden dimension E [8, 64], the number of layers E [2, 8), sheaf weight decay from the same weight decay range, the number of decoder layer E {1, and using both low-pass and high-pass filters E (True, F alse). We report in Table 1 the mean accuracy and standard deviation over the 10 test splits using the best hyperparameters presented below. All experiments were performed on two NVIDIA RTX 6000 Ada Generation GPUs with 48GB of memory and one NVIDIA A100 Tensor Core GPU with 80GB, and it took roughly three weeks of training to produce the results. We re- port OOM when a model with the minimum hyperparameter configuration fails to process data on a 48GB GPU.
16

---

Published as a conference paper at ICLR 2025
layers
hidden
Ir
wd
dropout
self-loop
jk
self-feature
Roman-Empire
le-2
0.5
False
max
SNAPPPatents
5
le-2
0.5
True
cat
Texas
2
2e-2
5e-4
0.5
0
0.5
False
None
True
Wisconsin
2
128
2e-2
le-3
0.5
0
0.5
False
None
True
Arxiv-Yeat
6
256
5e-3
0
0.5
False
max
False
Squirrel
3
64
le-2
5e-3
0
0.5
False
cat
False
Chameleon
2
64
1e-2
2e-3
0
0.5
False
cat
False
Citeseer
2
256
2e-3
0.7
0
0,5
False
None
True
AM- MM--Computers
2
512
5c-3
0.7
0
False
None
False
AMMPhoto
3
128
lc-3
0.7
0.5
False None
True
Cora
2
128
5c-4
lc-4
0.5
0
False
None
False
Table A.1: Selected hyperparameters CoED.
# cnv/act layers
env/act hidden
TO
conv type
Ir
wd
dropout
layer norm
skip
SNAP-Patents
2/1
32 /
0
GCN
1c-2
0
0
True
False
Texas
3/1
64 /4
0.1
GCN
2e-2
le-3
0.5
False
True
Wisconsin
4/2
0.1
GCN
2e-2
5c-4
0.5
False
True
Year
3/1
128/8
0.1
GCN
1c-3
0
True
Truc
Squirrel
2/1
64 /4
0.1
Mean GCN
5e-3
0
0
False
False
Chameleon
2/1
64
0.1
Mcan GCN
5c-3
0
0
False
False
Citeseer
4/1
64
GCN
1c-2
0.7
True
True
AM-Computers
4/2
GCN
5c-3
True
False
AM-Photo
3/2
/8
GCN
5e-3
0
0.5
Truc
True
Table A.2: Selected Hyperparameters for Co-GNN.
# layers
# hidden
conv type
Ir
wd
dropout
Qt
norm
jk
Texas
2
256
DirSAGE
2c-2
5e-4
0.5
0.5
False
None
Wisconsin
256
DirAGGE
le-2
le.4
0.5
0.5
False None
Squirrel
4
64
DirGCN
1e-2
5e-3
0
0.5
False
cat
Chameleon
2
64
DirGCN
1e-2
2e-3
0
0.5
False
cat
Citescer
2
128
DirSAGE
5e-3
1c-3
0.5
0.5
False
Nonc
AM-Computers
256
DGr
1c-3
0
0.5
0.5
Truc None
AM-Photo
128
DirSAGE
1c-3
0
0.5
0.5
Truc None
Cora
2
64
DirGCN
5e-3
5e-4
0.5
0
False
None
Table A.3: Selected hyperparameters for DirGNN.
# layers
# hidden
dropout
norm
jk
self-feature
Roman-Empir
5
256
1c-2
0.2
0.5
False
Truc
SNAP-Patents
le-2
0.5
True
cat
True
Texas
3
64
le-2
le-3
0
0.5
True
None
True
Wisconsin
2
32
le-2
le-4
0.5
0.5
False
None
True
Arxiv-Ycar
6
256
5c-3
0
0
0.5
Falsc
False
Squirrel
32
5e-3
5e-3
0.5
False
cat
False
Chamelcon
2
128
2e-2
lc-3
0.5
False
cat
False
Citeseer
2
64
le-3
le-4
0.5
0
False
None
True
AM-Computers
3
256
le-3
0
0
0
True
None
True
AM-Photo
4
256
Se-3
lc-4
0
True
None
True
Cora
32
5e-4
False
None
True
Table A.4: Selected hyperparameters for Chung.
17

---

Published as a conference paper at ICLR 2025
layers
hidden
dropout
K
q
Citeseer
256
le-3
0.5
2
MM-Computers
256
le-3
lc-4
0.5
AM-Photo
256
2e-3
0.7
3
Cora
32
1c-2
0.5
2
Table A.5: Selected hyperparameters for MagNet.
# layers
hiddon
stalk
Ir
wd
shaaf wed
dropout
hightlow-pass flter
#encoder layers
Roman- Koman-Empire
16
Diugonal
3
2e:3
le-2
0
0.7
Tulse/ru
2
Arxiv-Year
8
16
Diagonal
4
16-2
0
0
Trae/Falke
Squirell
Orthggnal
Chamelcon
2
16
Diagonal
6
1e-2
0
0
Trae/False
AM Computers
4
32
General
1e-2
0
True/Fake
AM-Photo
16
Dingonal
16-2
True/False
Table A.6: Selected hyperparameters for Sheaf.
# layers
# hidden
# encoder/decodert layers
wd dropout
self-loop
Texas
128
le-2
Wisconsin
128
1/1
5c-3
0.5
0
Squirrel
16
1/1
2c-2
le-2
0.5
Chameleon
256
1/1
1e-2
5e-3
0.5
A.- AM-Computers
32
1/2
AM-Photo
64
2/1
5e-3
5e-3
0.5
Table A.7: Selected hyperparameters for FLODE.
layers
hidden
dropout
MLP (Squirrel)
64
le-4
0.5
MLP (Chamelcon)
128
lc-2
0.7
MLP (AM-C (o-Coouuttrr)
256
5e-3
le-4
0
MLP (AM-Photh)
256
5e-3
le-4
0
SAGE (Arxiv-Year)
128
1e-3
le-4
GGCN (Squirrel)
32
5e-3
le-4
GGCN (Chameleon)
64
1e-2
5e-3
0.7
Table A.8: Selected hyperparameters for MLP, SAGE, and GGCN.
A.2 GRAPH ENSEMBLE EXPERIMENT WITH SYNTHETIC DATASETS
A.2.1 DATA GENERATION AND TRAINING SETUP FOR THE DIRECTED FLOW TRIANGULAR LATTICE GRAPH
To obtain the triangular lattice graph described in the main text. we first designed a potential function on 2) plane with peak (source) and valley (sink). We used quadratic potentials, located at μ4 (-1,1) and μl2 = (1, -1) with stiffness matrices,
Data generation.
(
K2 K2
With magnitudes a₁ and 02 -1, the potential function V(x) is parameterized as,
V (xx) = aı (x 41) (x (x w1) + az((x p2) K2(x (22
We then generated a triangular lattice on the 2d plane and considered this lattice as a graph Guauces where the vertices of the lattice serve the nodes of the graph, and the edges of the lattice form the edges of the graph. In this way, each node U; E Viatiee has an associated spatial position x; on the 2d plane. We computed AV₁- V(x,) V(x,) for all (us, vy) E Etatice- All AV, values were shifted
18

---

Published as a conference paper at ICLR 2025
and scaled to the range [0, /T/2 to obtain the Byj, which is an approximate version of the gradient direction of the potential. In the resulting lattice graph, an edge points towards the node with the lower potential energy.
We then assigned to each node a 10-dimensional random feature vector sampled independently from the standard multivariate normal distribution, and normalized them to have unit-norm, and repeated the process 500 times to generate an ensemble of node features. To generate corresponding target values, we propagated features using Equation 4 with message-passing matrices P_, and P computed from θ of the lattice graph as described in Equation [annd the entries of the 10 x 10 weight matrices W W W-, and setr sampled independently from the standard normal distribution and shared across all 10 iterations. Instead of applying an activation function, we normalized the features mseir + m + m to have unit norm. We used the features after 10 iterations of message passing as the target values. We divided these 500 instances of feature-target pairs using 60%/20%/2005 random training/validatioonness split.
Training, We used a batch size of 16 for training with random shuffling each epoch and full batch for both validation and testing. We evaluated the validation MSE at each epoch, increment- ing counter if the value did not improve and resetting it to 0 when new best validation MSE was achieved. Training was early-stopped when the counter reached patience of 20. We used neither dropout nor weight decay, as we aim to learn an exact mapping from node features to tar- get values for regression, as opposed to a noise-robust node embedding for classification. We used the ReLU activation function in all models, except for ELU in GAT, and used ADAM optimizer for all experiments. Across all models, we searched over the following hyperparmeters: the num- ber of layers E [2, 4]. hidden dimension E [16, 64), learning rate E [le-3, 1e-2]. We additionally grid-searched over model-specific hyperparameters. the number of attention heads E [1,4, 4, 8) and skip connection (sc) E [True,False] } for GAT; attention type E ('multihead', 'performer', ]. at- tention heads E {1, 4, 8), ). encoding type ('eigenvector', 'electrostatic' J. the dimension of eigen- vector encoding E [2, 5, 10, 20) and self-loop value E {0, 1 for GraphGPS; the order of Cheby- shev polynomial K [1,2] and self-loop value {0, 1} for MagNet:
{0, 0.5, 0.1) for Chung; multi-hop aggregation mechanism E f'sum', 'weight') } for DRew; the number of both en- coder and decoder MLP layers E (1, and self-loop value {0, for FLODE; self-feature transform E {True, False), learning rate for θ E [le-3, 1e-2]. and layer-wise (Iw) θ learning {True, False} for CoED. For GraphGPS, we used GINE as a convolution layer and provided as an edge attribute. Computing structural encoding via random walk resulted in an all-zero vector since the degree of node is 3 across all nodes except at the boundary in our lattice graph. We thus opted to use the electrostatic function encoding provided in the original paper as an alternative to structural encoding. For MagNet, we optimized g along with the model parameters during training. We supplied the undirected version of the lattice graph by setting all 0e values to a/4 and used self-feature transform with self-loop value set to O. We did not use layer-wise feature normalization. Table 2 reports the mean accuracy and standard deviation training runs with different initializations using the best hyperparameters shown below. All exper- iments were performed on two NVIDIA RTX 6000 Ada Generation GPUs with 48GB of memory and it took about 3 days of training time to generate the results.
the test data from the top 5 out of 7
Model
laaeer
hukice
sclf-lcop
slts. heads
ain type
cnc. typc
sggen
lapers
lays self-fcutre
e
Jw
GCN
GAT
32
16:3
True
GaytGes
64
16.5
0
motrheed
elgervenn (dins))
MarNet
18-3
Uitew
3e-3
FLOGE
64
16-2
0
3
Coll
16-3
Thm
16-3 Palie
Table A.9: Hyperparameters selected for node regression on the synthetic lattice graph.
A.2.2 DATA GENERATION AND TRAINING SETUP FOR THE GRN DYNAMICS EXPERIMENT
Data generation. We prepared a directed adjacency matrix A for graph with 200 nodes by sam- pling each entry of the matrix independently from a Bernoulli distribution with success probability 0.03. We interpreted an edge At as indicating that the gene represented by the node v, is regulating the gene represented by the node v; We then randomly chose half of the edges as activating edges and the other half as suppressing edges. The scalar feature value of each node is the expression level
19

---

Published as a conference paper at ICLR 2025
of gene, measured concentration G, In order to simulate the gene regulatory network dynamics where genes are either up- or down- regulating connected genes, we sampled the magnitudes of activation Yij and suppression " from a uniform distribution with the support [0.5, 1.5]. We ad- ditionally sampled half-saturation constants Kij, which control how quickly e; changes in response to cj. from uniform distribution with support [0.25, 0.75). Lastly, sampled the initial concen- trations independently from a uniform distribution with support [0.1, 10] for each gene, and ran the GRN dynamics described by,
de: di
Σ JEN((s
(783 ( D (cj, Kig) + 18g sup puu puup(c (cp, K.j)) - -i
(5)
for 250 time steps with dt = 0.05 to reach a steady state for c. The summation in the above
equation is over all genes that either activate repress gene i. (" Ki))= 2/(K3 k + +22 and (c,"(c,KK,, = K2 (K3) + +c)), which are the Hill functions defining up- and down- regulations of gene i by gene j. respectively. From this steady state, we mimicked the gene knockout experiment in biology by setting the concentration values of a chosen set of genes to zero and running the GRN dynamics for additional 100 time steps, by which time genes reached new steady-state values. We performed a single-gene knockout for all 200 genes and double-genc knockout for 1000 randomly selected pairs of genes. We defined node features as the original steady state with the values of knockout genes set to zero and the corresponding target values as the new steady-state values reached from this state. This procedure generates for the synthetic GRN graph. We used all 200 single gene knockout results as training data, and randomly selected 200 and 800 double gene knockout results for validation and testing, respectively.
ensemble of 1200 feature-targer pairs for each node
Training. For each knockout result, we used all nodes for regression except those corresponding to the knocked out genes. We used a batch size of for training with random shuffling at each epoch, and full batch for both validation and testing. We evaluated the validation loss at every epoch, and implemented the same counting scheme as in the directed flow experiment to early-stop the training with a patience of 50. We searched over the number of layers E [2, 5). hidden dimension E (16,32), and learning rate E (e-3), and otherwise conducted the same hyperparameter search as described in the lattice experiment, using the same training setup. Table reports the mean accuracy and standard deviation on the test data from the top 5 out of 7 training runs with different initializations using the best hyperparameters shown below. All experiments were performed on two NVIDIA RTX 6000 Ada Generation GPUs with 48GB of memory and it took about 3 days of training time to generate the results.
Mtode
flasers
d Haaden
I
self keep
SC
Eatts leads
ait type
eac type
Aggs
Eecc. layess
dev. leps
self feature
GAT
1p-3
0
miliiead
digmmeetrr (Amaat))
Maghen
Sp4
IIDE
40-3
1
CRED
32
1c3
Tiee
Ic2
Tixe
Table A.10: Hyperparameters selected for node regression on the synthetic GRN graph.
A.3 GRAPH ENSEMBLE EXPERIMENT WITH REAL DATASETS
A.3.1 PREPROCESSING, DATA GENERATION, AND TRAINING SETUP FOR SINGLE-CELL PERTURBATION EXPERIMENTS
Preprocessing. We downloaded Replogle-gwps dataset from scPerturb database (Peidli et al. 2024) and followed the standard single-cell preprocessing routine using Scanpy software (Wolf et al. 2018), selecting for the top 2000 most variable genes. This involved running the following four functions: filter_cells function with mi min_counts=20000 argument, normalize.per.com function, filter.genes function with min_cells=55 argument, function with a.top.genes=2000, flavor= 'seurat_v3' and 1ayer= 'counts' arguments. Afterwards, we discarded genes that were not part of the top 2000 most variable genes. These 2000 genes define nodes. We did not log transform the expres- sion values and used the normalized expression values obtained from these preprocessing steps for all downstream tasks. Out of 9867 genes that were perturbed in the original dataset, 958 of them
highhyy.varibblee.enne.
20

---

Published as a conference paper at ICLR 2025
among the top 2000 most variable genes. Note that perturbed genes should have near expression values since the type of perturbation in the original experiment was gene knockout via a technique called CRISPRi. Therefore, we disregarded perturbed genes if the perturbations did not result in more than 50% of cells with zero expression values for each respective gene. This prepro- cessing step identifies 824 effective gene perturbations. Note that there multiple measurements per perturbation.
Data generation for node regression. In perturbation experiments, the expression values are mea- sured post-perturbation" (equivalent to e; + Ac; in Figure of the main text). Consequently, do not have access to their ppre-interaction expression levels (equivalent to C with a perturbed gene's value set 0). To pair each post-perturbation expression values to its putative pre-interaction state, we randomly sampled a control measurement and set the expression value of the perturbed gene to O. These pairs of pre-interaction and post-perturbation expressions define the ensemble of features and targets. Since the number of measurements vary per perturbation, we standardized the dataset diversity by downsampling the feature target pairs to 2 per perturbation. We split each dataset based on perturbations, grouping all cells subject to the same perturbation together. We per- formed 60/10/30 aainiin//alidationntes. splits and computed k-nearest neighbors gene-gene graph with k = 3 using the training split. We checked that this graph roughly corresponds to creating an edge between genes whose Pearson correlation coefficient is higher than 0.5. We also confirmed that this graph represents single connected component.
Training. As in the GRN example, we used all nodes (i.e., genes) for regression except for those corresponding to knocked-out gene. We used batch size of 16 for training with random shuffling at each epoch, and full batch for both validation and testing. We evaluated the validation loss at every epoch, and implemented the same counting scheme as in the synthetic dataset experiments to early-stop the training with patience of 30. Since the models' performances generally improved as their depths and hidden dimensions increased, we used 4 layers and a hidden dimension of 32 across all models to streamline the comparison. We searched over learning rate E (le-3, Se-3, le-2) for all models, the order of Chebyshev polynomial K E (1, 2} for MagNet; the number of attention heads {1, 4, 8} for both GAT and DirGAT; additionally, skip connection (sc) E {True, False} for GAT; self-feature transform E {True, False). learning rate for θ E (5e-4, 1c-3, 5e-3, 1e-2] and layer-wise θ learning FFrue,False mean accuracy and standard deviation on the test data from the top 5 out of training runs with dif- ferent initializations using the best hyperparameters shown below. All experiments were performed on two NVIDIA RTX 6000 Ada Generation GPUs with 48GB memory and approximately one day of training time was spent for generating the results.
for CoED. We learned in MagNet. Table
3 reports the
Model
Paltn, heads sell-feature
Iw
GCN
Se-3
MagNet
le:3
GAT
DiEGON
Se-3
DirGAT
le-3
CoED
1e.3
False
5e-4
False
Table A.1I: Hyperparameters selected for node regression on the Perturb-seq data.
A.3.2 TRAINING SETUP FOR WEB TRAFFIC EXPERIMENTS
We downloaded WikiMath dataset from Py Torch Geometric Temporal library (Rozemberezkii al., 2021) with the default time lag value of 8. We followed the same temporal split from the paper where 90% of the snapshots were used for training and 10% of the forecasting horizons were used for testing.
Training. The input features and target values are shaped as N x 8 and x 1, respectively. Since we consider pair of the two consecutive snapshots as input and the corresponding target, we disregarded the first 7 snapshots (i.e., feature dimensions) and used only the node values (i.e., visit counts of Wikipedia articles) of the last snapshot for prediction for testing. For training, utilized all snapshots, generating 8 predictions. MSE loss for the predictions from the first snapshots were each evaluated with the next 7 snapshots target values. This procedure is similar
21

---

Published as a conference paper at ICLR 2025
to the 'incremental training mode' used to train time-series based models (Rozemberczki et al., 2021 Eliasof et al. 2024; Guan et al., 2022). We used a full batch for both training and testing. We evaluated test loss each step, and implemented the same counting scheme used above to early-stop training with a patience value of 50. We used 2 layers with a hidden dimension of 16 across all models. We searched over learning rate E (1e-3,5e-) 1e-2, 2e-2) for all models and also over the same model-specific hyperparameters discussed in the Perturb-seq experiments except the number of attention heads, which was limited MagNet. Table reports the mean accuracy and standard deviation on the test data from the top of 7 training runs with different initializations using the best hyperparameters shown below. All experiments were performed on two NVIDIA RTX 6000 Ada Generation GPUs with 48GB memory and approximately 16 hours of training time was spent for generating the results.
due memory constraints. We learned q for
Model
Ir
K
altn. heads
selttfeature
e
Iw e
GCN
le-2
MagNet
Se-3
GAT
1e-2
True
2
DirGON
26-2
DirAT
CoED
36-3
True
Te-2
Halse
Table A.12: Hyperparameters selected for node regression the WikiMath data.
A.3.3 TRAINING SETUP FOR POWER GRID EXPERIMENTS
We downloaded power grid graph with 2000 nodes from PyTorch Geometric library, compiled via OPFData (Lovett et al., 2024). We selected the 'fulltop' topology option to obtain the information of the entire graph, opposed to 'N-1' perturbation option which masks parts of the graphs. We randomly sampled 300 graphs and split them into 200 training set, 50 validation set, and 50 test set. Power grids are heterogeneous graphs. Refer to Figure of Piloto et al. 2024) for detailed overview the different components. Importantly, generators, loads, and shunts ( ('subnodes') are all connected to buses ('nodes') via edges, and buses connected to one another via two types of edges, transformers and AC lines. Thus, the load profile across the graph informs the generator subnodes via the bus-to-bus edges. We describe the architectural design choices that we made to accomplish this task while facilitating effective model comparison.
Model.
The primary goal is to ensure information flow into those buses connected to generators. We thus substituted different model layers to process messages over the two types of bus-to-bus edges while keeping the rest of the architecture unchanged. The processing steps are:
1. Transform node/subnode features and edge features using an MLP.
2. For each bus node, integrate the features of its subnodes into its own features via Graph- Conv (i.e., Wi + W2 ΣjeN() Eji X; ).
3. Incorporate edge features into node features using GINE.
4. Iterate message- paasinng among bus nodes
5. Decode the features of bus nodes into generator operating point values.
We varied the message-passinn mechanism step 4 by applying the different Aggregate and Update functions of each of the models that we analyzed.
Training. Following the example training routine outlined in Lovett et al. (022)). we trained mod- els predict generator active and reactive power outputs and evaluated MSE loss against those values in the AC-OPF solutions. We did not incorporate AC-OPF constraints, as the focus of the experiments was to compare the message-passing capabilities of CoED with other models. We refer Böttcher al. (2023); Piloto et al. (2024) for predicting AC-OPF solutions that satisfy constraints. We used a batch size 16 during training with random shuffling applied at each epoch. We evalu- ated the validation loss every epoch and carly-stopped the training with the same counting scheme with a patience of 50. We iterated the step above times (i.c., 3 layers) and used 32 hidden di- mension. We searched over learning rate (5e-4, 1e-3, 2e-3, 5e-3), and otherwise the same set of
22

---

Published as a conference paper at ICLR 2025
hyperparameters considered in the Perturb-seq experiments. We learned for MagNet. Table B re- ports the mean accuracy and standard deviation on the test data from the top out of training runs with different initializations using the best hyperparameters shown below. All training were per- formed on two NVIDIA RTX 6000 Ada Generation GPUs with 48GB memory and approximately one day of training time spent for generating the results.
Model
Ir
K
* atin. heads
sell-feature
by
GCN
Se-3
MagNet
le-3
GAT
2c-3
Falso
DirGCN
le.3
DirGAT
le-3
CoED
5e.4
Pulse
Trme
Table A.13: Hyperparameters selected for node regression the AC-OPF data.
B TIME AND SPACE COMPLEXITY
Let V and denote the numbers of nodes and edges, and let H denote hidden dimension, which we assume stays constant for two consecutive layers. At minimum, the cesssage-assiing mechanism outlined in 2 results in the time complexity that scales as OEEH + H²), where the first term corresponds to aggregating features with dimension H and the second term stems from the matrix- matrix multiplication of node features and a weight matrix. The space complexity is O(E + H²) due to the edges and the weight matrix.
With the sparse form of the phase matrix θ, CoED incurs an additional O(E) term both in the time complexity from computing fuzzy propagation matrices P-/- and in the space complexity due to storing O Unless layer-wise @ learning is employed, this computation happens once and thus only adds minimal overhead. The layer-wise learning adds an OEE)) term to the total time and space
complexities over L layers. For comparison, however, we note that computing S-head attentions incurs O (EH) term (or even O(FHS) term if feature dimension is not divided by S) in the time complexity and an (FES) term in the space complexity per layer.
C POSITIONAL ENCODING USING THE FUZZY LAPLACIAN
Graph Laplacians can be used to assign a positional encoding to each node of a graph based on the connectivity patterns of the nodes of the graph. Using the fuzzy Laplacian, we extend positional encoding to include variations in directions of the edges surrounding node in addition the connectivity pattern of the graph. To demonstrate the utility of the eigenvectors of the fuzzy Laplacian for positional encoding, we visualize the eigenvectors of the Laplacian computed from the triangular lattice graph (which has a trivial connectivity pattern as shown above by the random walk structural encoding being trivially zero) supplemented with two different sets of edge directions. In the first case, we obtained edge directions from the gradient of source-sink potential function described in A.2.T] These edge directions are visualized in Figure (3b) of the main text. In the second case, we obtained the edge directions for the same triangular lattice graph, from the following solenoidal vector field,
F(x) (sin(Tx) cos(TT), cos( (in)))))i
which does not have sources or sinks but instead features a cyclic flow. To assign edge directions using the solenoidal vector field, computed fi the angle between the unit vector pointing from Us to Uy and the vector evaluated at the midpoint of an edge, i.c., F((x; x1 )/2). All 0g were scaled to range from 0 to nt/2. As shown in Figure Ca-e)) the real part of the eigenvector distinguishes the peak and valley from the region in between, whereas the phase the eigenvector distinguish the peak from the valley. Similarly in Figure (f-(F-)) the real part of the eigenvector highlights the regions adjacent to the cyclic flows. The magnitude of the eigenvector picks out the centers of the four solenoids in the middle. Taken together, the eigenvectors of the fuzzy Laplacian contain positional information based on the directions the edges as demonstrated here for the same graph but with different edge directions.
23

---

Published as a conference paper at ICLR 2025
Gradient vector field
Real part for nourcosink
Imaginar for somcewink (8) Phane samx-sink gogph
Magnitale souna-iirk grggh
(6 Solenoidal vector field
(g) Real port for solenoodal vector rield
(1) Inneginary part for solenoidal vecter field
Phase for solencidal vector field
() Magnitude for solenoidal vester field
Figure C.I: Visualization of the eigenvector, corresponding to the eigenvalue with largest magnitude, of the fuzzy Laplacian of the triangular lattice whose edge directions are taken from the source-sink potential function described in the main text (top row) and the solenoidal vector field described in this section (bottom row). The original vector fields are shown in the left-most figures. The real and imaginary components, well as the magnitude and phase, of the eigenvector encode positional information each node about the direction of the edges surrounding that node.
D MATHEMATICAL PROPERTIES OF THE FUZZY LAPLACIAN
We propose a new graph Laplacian matrix for directed graphs which generalizes to the case of directed graphs with fuzzy edges, where an edge connecting two nodes and can take on any intermediate value between the two extremes of pointing from A to B and pointing from B to A. We will show that our Laplacian exhibits two useful properties: 1. The cigenvectors of our Laplacian matrix are orthogonal and therefore can be used as the positional encodings of the nodes of the graph. 2. For any node of the graph, our Laplacian aggregates information from neighbors that send information to the node separately from the neighbors that receive information from the node and therefore as expressive as a weak form of the Weisfeiler-Lens (WL) graph isomorphism test for directed graphs with fuzzy edges that we define below.
D.1 DIRECTED GRAPHS WITH FUZZY EDGES
We define directed graph with fuzzy edges follows. Our definition builds the standard definition of a graph.
A graph G is an ordered pair G = (V, E) comprising a set V of vertices nodes together with set edges. Each edge is 2-clement subset of V.
V: A finite, non-empty set of vertices
V (UI, U2...., vn)
E: A set of edges, each linking two vertices in V
m = ((vi, Uy)
0i fyy E V}
To incorporate fuzzy directions to the edges, we define new attribute for each edge.
A function defining the direction of each edge
ju (vi, vy)) - [0,
such that for each edge (v,, Uz) E F,, p(us, vt)) implies (u(1,, u:) v1 x
24

---

Published as a conference paper at ICLR 2025
In this model, each edge is associated with scalar that represents its direction. The value is a real number in the interval [0, 1]. for an edge By), pl u2) = 2, then must hold that ((0,,2) 2/) = /1 x², capturing the edge in both directions.
For example, if p( uj) then the edge is are (directed edge) connecting node v; node vy- (( vÿ) = then the edge an arc connecting node " to node v,. p((s; 13) = 1/22 then the edge is a bidirectional edge connecting node to node "/ and node Vi to node ti
For scalar-directed edge graph G (V,E,,) p4). the adjacency matrix sion [V] x [V]. The entry Aij of the matrix is defined as follows:
square matrix of dimen-
[u(r, U3), if (vi, mT)) E E 0.
otherwise
In this setting, plu;; vy) captures the direction of the edge from vs to uj. It follows that if an edge is present between nodes où and Uj then Aj+ / A
Therefore, the adjacency matrix captures not only the presence of edges but also their direction according to the function J.
D.2 FUZZY LAPLACIAN MATRIX
For scalar-directed edge graph G (V,E,)) with adjacency matrix A, we define its Fuzzy Lapla- cian matrix DF as follows:
The diagonal entries of Lp are zero:
(LF)a= =
The off-diagonal elements are
0
if Ay = Ay== =0 otherwise
(Lf) =
(6)
where Ozg is selected such that:
cos(O.)) Aij
other words, the real part of ei. is equal to the corresponding adjacency matrix entry Aij. We require that 0 < 0,5 < π 7/2. It follows that Ozi = π Ozj-
The Fuzzy Laplacian Lf satisfies the property:
LF iL
To confirm this, note that e -t9, cos(-0:5) 0ij) + (sin(-0;) = cos(O:s) isin(O.,). Therefore, (I=),; sin().;) + cos(O.,)) = ie 180, and thus LF iLp-
The fuzzy Laplacian takes the following form,
LF
ie -0.
Here, Gloy and ie 11 are sample off-diagonal elements corresponding to the edge (v, in the graph.
D.3 PROPERTIES OF FUZZY LAPLACIAN MATRIX Lp
In this section, we will show that the Fuzzy Laplacian matrix Ly has eigenvalues of the form a + ia, where a R, and orthogonal eigenvectors.
25

---

Published as a conference paper at ICLR 2025
D.3.1 EIGENVALUES OF THE FORM ia
LF has eigenvalues of the form in with E 18
Proof:
Let be eigenvalue of LF, and let be the corresponding eigenvector. Then:
LoW Aw = w'L ='w" w'L X"w"w w
= -1 where we used 3 r to go the second line. The last identity holds only when À + ia where a is a real number.
- iw LFw X" www"w
-ix=
D.3.2 ORTHOGONAL EIGENVECTORS
To prove that LF has orthogonal eigenvectors, we need to show that if w and v are eigenvectors corresponding to distinct eigenvalues Àι and A2 respectively, then and orthogonal.
Proof:
Let L X1 and Lpv X2V.
v'LFw \IV"w w 7 w AIV"W = iAyv'w Aiv"w = d2v"w Aiv"w
where we used À = ix* derived above for the last step. Therefore, '2v"w = Aiv'w. Since A1 F X2, it must be that v'w 0, i.e., w and are orthogonal.
Because the eigenvectors of the Fuzzy Laplacian matrix Lp are orthogonal, they can be used as the positional encoding of the nodes the graph.
E EXPRESSIVITY OF NEURAL NETWORKS USING THE FUZZY LAPLACIAN
E
GRAPH ISOMORPHISM FOR DIRECTED GRAPHS WITH FUZZY EDGES
First, we extend the standard definition of graph isomorphism to the case of directed graphs with fuzzy edges following similar approach as in Piperno et al. (2018).
We only consider graph with a finite number of nodes. Therefore, the of all edge weights form countable set with finite cardinality.
Two directed fuzzy graphs G (Vg. Eg. pg) and (Vr, Exg, (x)) are said to isomorphic there exists bijection Vg + Vn such that, for every pair of vertices in Vg, the following conditions hold:
1. (u, v) is an edge in Eg if and only if (f(u), f())) is an edge in Ey for all vertices u and v in Vg. For every edge (u, v) in Eg that maps to edge (f(u), f()) in Ex, the corresponding weights satisfy:
pg(u, v) pn(f(u), f(u))
E.2 WEISFEILER-LEMAN TEST FOR ISOMORPHISM OF DIRECTED GRAPHS WITH FUZZY EDGES
Next, we extend the Weisfeiler-Lemaal (WI) graph isomorphism test to determine whether two directed graphs with fuzzy edges are isomorphic or not according the extended definition of graph isomorphism stated above.
WL test is a vertex refinement algorithm that assigns starting features to each node of the graph. The algorithm then aggregates all the features of each node's neighbors and hashes the aggregated labels alongside the node's ' own label into a unique new label. At each iteration of the algorithm, the list of labels is compared across the two graphs. If the labels are different, the graphs not isomorphic. If the labels are no longer updated at each iteration, the two graphs can potentially be isomorphic.
26

---

Published as a conference paper at ICLR 2025
The Hrisfeiler-Lehmann (WL) graph isomorphism test treats all edges emanating from node equiv- alently, as long as they connect to neighbors with the same label. Neighbors are distinguished solely by their labels, not by the attributes of the edges that connect them. When extending the WL test to directed graphs with fuzzy edges, we must account for the fact that fuzzy edges disrupt this uniform treatment of edges. We introduce the following two extensions of the WI. test to handle directed graphs with fuzzy edges.
Strong form: A node can distinguish its neighbors not only by their labels but also by the weights of the edges connecting them. This allows the node to differentiate between neighbors of the same label based on edge attributes.
Weak form: A node cannot differentiate between neighbors of the same label based on edge weights. Instead, the only weight-related information a node can use is the sum of the edge weights connecting all neighbors with given label.
These extensions adapt the WL test to account for the additional complexity introduced by fuzzy edges in directed graphs. Importantly, for all the proofs that follow, we will assume that the graph has a finite number of nodes.
The strong form of WL test for fuzzy directed graphs:
Given a directed graph with fuzzy edges G = (V,E, p), the strong form of the WL test calculates a node coloring (t0)) V + {1, 2,..., k}. a surjective function that maps each vertex to a color. At the first iteration, (()) = 0. At all subsequent iterations,
......,,,,
(10 (i) = (et)be)(C())(()),, ((ag. (( :
(8)
where (my. Cf(-11) is tuple comprised of the weight of the edge from node i to node and c(t-1), the color of node in the previous iteration. To simplify notation, we will write 2kj to denote the weight of the edge connecting nodes and j instead of ja(;;, U2) from now on. N(i) denotes the set of all neighbors of node i. Function Relabel is an injective function that assigns a unique new color to each node based on the node's color the previous iteration and the tuples formed from its neighbors colors and the value of the edges connecting the node to those neighbors.
From the definition above, it follows that graph neural network r G + RRd that aggregates and updates the node features as follows
h - h = S(h (K))) -
(()))))
will map two graphs G1 and G2 to different vectors in TRd if the above strong form of the graph coloring test deems that the two graphs are not isomorphic. In the above equation, A is the hidden representation (or feature) of node at the kth layer. ó and f are injective functions with f acting on multisets of tuples of the edge weights and hidden representation of the neighbors of node i.
The proof of above statement is a trivial extension of the proof of Theorem 3 in (Xu et al. 2019). Briefly, the multiset of the features of the neighbors of node can be converted from multiset of tuples of the form (Mig. hy (k-1)) j E N()) to a multiset of augmented features of the neighbors (h : E [N) where 7 (k-1) = (Mig,
h ((-1))) Because Mij form set of finite cardinality,
the augmented feature space n. (k-11) is still a countable set and the same proof as in [Xu et al. 2019) can be applied.
The weak form of WL test for fuzzy directed graphs:
We introduce a weaker form of the WI. test for directed graphs with fuzzy edges where a given node cannot distinguish between its neighboring nodes that have the same color based on the weights of the edges that they share. Rather, the node aggregates the weights of all outgoing and incoming edges of its neighbors of given color.
The weak form of the algorithm is as follows. At the first iteration, (1)) = 0. At all subsequent iterations,
27

---

Published as a conference paper at ICLR 2025
2
2
0.3
Ne = 0.7
3
Ho 0.6
= 0.2
Figure E.1: Examples of two neighborhoods of a node i are shown on the left and right. The strong form of the WL test for directed graphs with fuzzy edges The weak form of the WL test, however, cannot do so because the sum of the weights of the edges connecting node i green-colored neighbors is 0.9 in both cases.
distinguish these two neighborhoods.
t (1) Relabel (c(t-1)(1).
{(
Σ
8(c)--1)-
cc)4ss
JEN(1)
Σ JEN(
8(0)
c)pse, c) :C ((D)))
(10)
The term EjEN(e) 8(C,t-)) -c) is summing over the edge weights Pij of all neighbors of that have color c. The tuple now also contains similar that sums over the edge weights pointing from node node i, jij for all neighbors of the same color. As stated above, the edge weights
related, namely, Mkja v mdy. The color of the node the previous iteration alongside the set
of tuples containing the sum of incorning edge weights from neighbors of given color, the sum of outgoing edge weights the neighbors of given color, and the color of those neighbors are inputs to the injective function Relabel, which assigns unique color to node i for the next iteration.
Theorem. Let + RRd be graph neural network that updates node features as follows.
1)
(k) MLP(N) h
M R
Σ JEN(()
(LF)ey
Σ JEN())
(Le)igh (k-1))
(II)
where MLP()) is multi-layer perceptron. The last terms of the MLP input are the real and imaginary parts of the aggregated features of the neighbors of node i, EjeN(o (Le) sufficient number layers, the parameters of I can be learned such that it is as expressive as the weak form of the WL test, in that I maps two graphs GI and G2 that the weak form of WL test decides to be non-isomorphic to different embeddings in IRd.
(k-1), (t=)), With
Proof. First, claim that there exists GNN of the form:
(k) h
((1(a-1)) D).
f(h)
Σ
(R-
Σ (n JEN(A)
(12)
JEN(S)
that is expressive as the weak form of the WL test. We will prove this by induction.
Note that F(i) = EjeN(o Mig fi (1((111) and G(t) = Ejen() [h (1-1)) are only injective up the sum of the incoming and outgoing weights for given type of neighbor (see Figure for an example). This is because the weak form of the WL test only accounts for the of the weights of outgoing and incoming edges to neighboring nodes of given color. This different from previous work that dealt with undirected graphs (Xu et al. 2019) graphs with directed but unweighted edges (Rossi et al. 2024).
Let's denote with X the multiset of the colors of all neighbors of node i after a given number of iterations of the color refinement algorithm. Equivalently, we can consider the multiset of all the features of the neighboring nodes of i after given number of iteration of the GNN algorithm.
28

---

Published as a conference paper at ICLR 2025
Because graphs have finite number of nodes, X is bounded. For graphs without directed edges or weighted edges, it can be shown (see Lemma of (Xu et al. 2019) that there always exists an injective function f such that F(x) = Erex f(z) is injective for all multisets X, i.e. if F(X) F(Y) for two multisets X and Y then X = Y. This result can be easily extended to regular directed graphs without weighted edges by considering the neighbors with incoming edges separately from the neighbors with outgoing edges (Rossi al. 2024). For such graphs, function exists such that the tuple (_
-2ex__ f(z)) is only the same for two nodes they have identical neighborhoods. X-, and X. denotes the multiset of features of the neighboring nodes that are connected to using an outgoing edge and incoming edge respectively.
Let's proceed with proof by induction. At the first iteration, color corresponding to the same trivial feature (e.g. scalar 0). Functions Fii) and G(i) then simply sum the weights of the outgoing and incoming edges of node respectively and use their values to
O, all the nodes have the same
assign updated feature () This is identical to the procedure that the weak WI. algorithm using to assign colors the nodes at its first iteration. Therefore, nodes that would be assigned
given color under the WI. color refinement algorithm at its first iteration will also be assigned the same updated feature vector h()).
Assume that our claim hold for iteration & - This mean that all the nodes that the weak WL color refinement assigns to different colors are also assigned different features ht (*-1) by the GNN. Following the weak WL test, iteration k, we need to sum the incoming and outgoing edges across all the neighbors with the same hg ((=1)) An example of an f that allows this one-hot encoding of
all features. There always exists a number N E N such that the features h (k-1) across all nodes of the graph can be one-hot encoded in N dimensional vector. It follows.
Σ JEN())
(i 1)-
Σ (IN(()
5(h
h)pss
(13)
where H (k-1) is the set of all the features h (k-1) of nodes j that are neighbors of node i. A similar expression can be written for the sum the incoming weights Mja. Thus, iteration & the GNN will assign distinct features to all nodes that are also assigned a distinct color at iteration k of the weak WL color refinement algorithm.
To complete the proof, we note that because Hja /1 11-Hi ~1 we can reparameterize the edge weights as μıj = cos( and Me sin() with 0 < Ozg S 7/2. Eq. 12 can be rewritten as:
(())= (100t
Σ JEN()
(LF)ss(h (k-1))
Σ JEN(
(L))s
(14)
Finally, we use universal approximation theorem of multilayer perceptrons (Horikk et al. 1989 to model both the é computation at layer l and the computation for the next layer, Namely M M.P((k denotes (k++1) ((())_ Taken together, the GNN in Eq. 11 is expressive the weak form of the WL color refinement algorithm for directed graphs with fuzzy edges.
F MAGNETIC LAPLACIAN IS NOT AS EXPRESSIVE AS THE FUZZY LAPLACIAN.
F.1 MAGNETIC LAPLACIAN
commonly used Laplacian for directed graphs is the Magnetic Laplacian. To construct the Mag- netic Laplacian, start with the asymmetric adjacency matrix of the graph and symmetrize it. Note that we are using the conventional definition of adjacency matrix this section and not the fuzzy definition used above. The adjacency matrix A for directed graph is binary matrix, where
29

---

Published as a conference paper at ICLR 2025
Ay represents the presence of a directed edge from vertex v to vertex by and A,y 0 represents the absence such an edge.
The symmetrized adjacency matrix S is defined as:
5 = 2 (Aig + Asa)-
To capture the direction of the edges, phase matrix is defined as,
2 Aje)-
(15)
The Hermitian adjacency matrix is defined the element-wise product of the above two matrices,
H 9)) = S c exp(io())).
H()) has some useful properties in capturing the directionality of the edges of the graph. For ex- ample, for = 1/4, if there is an edge connecting j to ko but no edge connecting k to j then H = 1/2 and H -1/2. Although this encoding of edge direction is useful, the fact that both incoming and outgoing edges are purely imaginary (only different up sign) means that in gen- eral it is impossible to distinguish features aggregated from neighbors that are connected to node through outgoing edges from those connected through incoming edges. The fuzzy Laplacian Lp, however, trivially distinguishes features from outgoing neighbors from those of incoming neighbors by keeping one set real and the other imaginary. We will expand on the implication of this for the expressivity of graph neural networks constructed using these two approaches below.
F.2 LIMITATIONS OF THE MAGNETIC LAPLACIAN
Conventionally, a magnetic Laplacian is defined by subtracting ( from the degree matrix, LM = D (()),, If such a Laplacian matrix used to aggregate information of the nodes of the graph, the features of a node itself are combined with the features of its neighboring nodes. For directed graphs, there are two categories
neighboring nodes, those connected to a node with outgoing edges from (Aij 1 and Aạı 0) and those connected to node i with incoming edges (A,s and A, = 0). Of course, is possible for a neighboring node to be both an outgoing and incoming neighbor, in which case A₁:- A.j 1.
Features from these two categories neighbors, alongside the feature of the node itself, form three distinct categories that in general must be kept distinet for maximum expressivity (Rossi et al., 2024). Using a complex Laplacian for aggregating the features across the nodes allows a simple mechanism for distinguishing two categories (corresponding the real and imaginary parts of the resulting complex features) but not all three. To get around this limitation, we keep the self-feature of every node distinct from the aggregated features of its neighbors and concatenate with the aggregated feature prior to applying the multi-layer perceptron to update the features from one layer to the next. Therefore, maximize the expressivity of the magnetic Laplacian, we set the diagonal terms of the Laplacian matrix zero, and define the magnetic Laplacian simply LM H())
Lemma. For simple directed graphs without fuzzy edges, using the magnetic Laplacian Ly in the graph neural network of Eq. in the place of the fuzzy Laplacian Lp.
((m)ighht (e 1):
h MLP())
Σ (L )EN(()
(16)
(jEN())
does not decrease the expressivity of the graph neural network in that both networks are as expres- sive the weak form of the WL graph isomorphism test.
Lemma. To prove this statement, we will show that the MLP can learn a linear combination of its input that would it make it equivalent to the graph neural network defined in Eq. TT This is because when q = 1/8, the real and imaginary parts of the aggregated features of the neighboring nodes are linear combinations of the features of the outgoing and incoming neighbors.
The fuzzy Laplacian LF directly separates the features of outgoing and incoming neighbors in the real and imaginary components of the aggregated features respectively. Define F.)
30

---

Published as a conference paper at ICLR 2025
EjENOo) (LF)) ( from the outgoing and incoming neighbors respectively. With 9 1/8, we have,
and F- = 3 (i (L ((
(k-1) as the features aggregated
1 (1)
R
(IM)ighh
2/2
((L (k-1)
1 (F- F-
3
2V2
The MLP layer then in the graph neural network of Eq simply needs to learn linear combination of its second and third concatenated inputs to become equivalent to the graph neural network of Eq [1 Therefore, the two graph neural networks are equally expressive.
Next, we extend the definition of the magnetic Laplacian to directed graphs with fuzzy edges, defined above, which have weighted edges that indicate intermediate values of directionality between the two extremes of the edge pointing form node to node j and the edge pointing from node j to node We implemented these intermediate values in the fuzzy Laplacian by assigning weight Jáj each
edge. Although not necessary in general, we further assumed that μij- V - ply This constraint allowed us to think of each edge weight angle fzg- arccos((5g)) which then used define the fuzzy Laplacian matrix (Eq 77
To extend the magnetic Laplacian directed graphs with fuzzy edges, value for (Eq. 15) to each edge. To keep the notation comparable to that of the fuzzy Laplacian, we instead assign separate angle 0zz each edge and define the magnetic Laplacian as, (La));; e for j > if there is an edge between the nodes i and j. Siy * O. To ensure that magnetic Laplacian remains Hermitian, Lis = Las we require that (Lar) e e-is which defines the Oig values for j < i. It follows that Oft Oij.
assign different
Lu
50
10
It remains be shown how assign the 0i values from the Piy in self-consistent way.
Theorem. For directed graphs with fuzzy edges, the graph neural network constructed using the magnetic Laplacian L,, Eq. 16 is not expressive as the weak form of the WL graph isomorphism test, and therefore not as expressive as the graph neural network defined using the fuzzy Laplacian LF, Eq. 11
Proof. The Fuzzy Laplacian matrix conveniently captures the outgoing and incoming weights of the edges from one node to another, (Lr)aj cos(O;;) (0.)) isin (0xz). Namely, R(LF) cos(O;)) is the outgoing weight Myy of node i to node j and 3 (LF);; sin O2y) is in the incoming weight from node j to node i, uls. Importantly. the outgoing weight from node node j. paj. is the same as the incoming weight from node i to node j. Similarly, the incoming weight from node j to node i, Haj the same as the outgoing weight from node j to node i. These relationships are directly captured in the fuzzy Laplacian because (L = sin(O.)) ) c0s)))))
Let's consider how we can construct the magnetic Laplacian Las from Pay- The weight of the edge from to j is Pij. The weight from j to is Pij
From our definition above, (LM) cos (0gg) + sin (O,)) and (LM)j² = cos() iin())))) To relate Ozy to Paj we note that the ratio of outgoing and incoming weights for node is Piy Myg and for node j
Because these two quantities are reciprocals of each other, we can define
Mij t2n
Myj
We chose the tan function on the right hand side because tan( (20.)) = - t2n(29.g). Moreover, the log-ratio the left hand side of above equation can take any value from -oo co. The right
31

---

Published as a conference paper at ICLR 2025
0.75
0.75
sin (Sarcton
In
0.50
0.50
Function 1 Velue
Function! 2 Value
Function 2 Value
0.25
0.25
0.85
0.80
-0.25
-0.25
0.75
0os
(Jarcann
V2-
-0.50
-0.50
0.70
0.00
0.25
0.50
0.75
1.00
0.00
0.25
0.50
0.75
1.00
0.8
0.9
1.0
Hg
Function Value
Figure F.l: The functions used to map the edge weights May to the 0,5 values of the magnetic Lapla- cian. (6gg)))) is plotted on the left. sin()))) ) is plotted in the middle. sin(O:z) versus cos(f,z) is plotted on the right.
hand side can take on a similar range values we allow -T/4 0i S 4/4. The specific form of this function does not matter long it is odd function that spans the specified domain and range.
Assume that each node of the graph has trivial scalar feature equal to (the first iteration of the WL test). The magnetic Laplacian applied this graph aggregate the features of the neighbors of node gives,
RR Σ (LM)ss
Σ
Mij
cos
arctan
2
Mag
3 Σ (LMdis 3
Σ sin
arctan
In
2
Mag
The above functions for a single value of μij are plotted in Figure F.1 Importantly, these functions are not an injective function of all possible neighborhoods of node Consider the case of node that has 5 neighbors with Psj values that result in cos (B:y) = 0.8 and sin(f:;) 0.6, and another set neighbors with Pıy values that result in cos(Oig) 0.8 and sin(O.z) = -0.6. It follows 0. The same values would have been obtained and 3 (La(s)
that R (L
node had neighborhood comprised of 8 neighbors with Pij values such that cos(O;)) 1 and sin (0ig) = 0. Therefore, the magnetic Laplacian cannot distinguish distinct neighborhoods and is as expressive the weak form of the WL test.
In practice, the more important limitation of the magnetic Laplacian is that it aggregates neigh- borhood information that results in linear combinations of the outgoing and incoming features node, In contrast, the fuzzy Laplacian by construct always keeps these contributions separate in the real and imaginary parts of the aggregated feature vector. In many applications, we would like to access the self-feature of the node and the incoming and outgoing aggregated features of its neigh- bors separately. The fuzzy Laplacian is thus a better choice. could be argued that the MLP of graph neural network can learn to disentangle the linear combinations of the outgoing and incoming features aggregated by the magnetic Laplacian. In general, however, this is not possible by the types of the graph neural networks that considered here. This is because the parameters are MLP are the same for all the nodes the graph. The linear combinations, however, depend on the specific weights jaj connecting node its neighboring nodes j. Therefore, in general, the MLP will not be able to learn to disentangle the linear combinations the incoming and outgoing features aggregated by the magnetic Laplacian.
G RUNTIME ANALYSIS
We conducted the runtime analysis evaluate the computational efficiency of CoED in comparison to other representative baseline models. All models were configured with three layers and 64 hidden dimensions. We measured the forward and backward pass times three graphs of increasing size.
32

---

Published as a conference paper at ICLR 2025
Table G.1 reports the runtime of the models datasets used for the node classification task, where edge directions are not learned. In this case, CoED's 's computational overhead stems from computing the in- and uttpropagation matrices, P / once the initial layer. Consequently, its runtime is comparable to DirGCN, which employs a similar architecture.
Table G.2 presents the runtime for the batches of triangular lattice graph ensemble data. When in- cluding backpropagation for phase angles, CoED's backward pass time is approximately twice that of DirGCN. If unique edge directions are learned at each layer, CoED computes different propa- gation matrices at every layer. While this increases the forward pass time, the backward pass time remains unchanged since the backpropagation contributions from intermediate layers are subleading compared to the backpropagation to the initial layer.
Dataset
GCN
GAT
MagNet
DirGN
CoED
Forward
Backward
Forward
Backward
Forward
Backward
Forward
Backward
Forward
Backward
CORA
4,8
25.3
62.9
89.3
120.6
14.3
17.6
14.1
Roman-Empire
16.9
37.2
218.9
646.1
300.1
331.5
30.0
48.7
34.5
66.1
Arxiv-Yem
450.4
985.0
3379.2
10354.7
5058.2
7792.1
458.8
838.9
690.4
1231.4
Table G.I: Runtime of the forward and backward passes in ther node classification task. Times are reported in milliseconds. We set the number of layers to 3 and the hidden dimensions to 64 for all models. Note that do not compute gradients with respect to phase angles θ in this case. Cora, Roman- Emmire, and Arxiv- Year respectively have 2708, 22662, and 169343 nodes and 10556, 44363, and 166643 edges.
Back Sice
GAT
Migher
Grypris
DIGAT
Coffi
EHEDD (byerst))
Powaad
Becoward
Nerwand
Badowad
Peewel
Pveeuet
Backeor
Femort
Boctward
Nerwadd
Hadowadd
Heewal
Hadowadi
Hiewant
Bactwan
2.5
3.0
15.4
15.2
14.
32.5
34.1
31.3
4,4
6.1
26.1
36.3
3.5
13,0
6.5
12.4
314
1913
Kll
1056
785.
719
264
41.
Table G.2: Runtime of the forward and backward passes the node regression task with graph ensemble dataset. Times are reported in milliseconds. All models have 3 layers with 64 hidden dimensions. The backward pass of CoED now involves gradients with respect to the phase angles. At 4, 32, and 256 batch sizes, there are 1796, 14368, and 114944 nodes and 5048, 40384, and 323072 edges, respectively.
H CONTRASTING COED GNN WITH GRAPH ATTENTION NETWORK (GAT)
Graph Attention Network (GAT) (Velicković et al. 2018), similar to CoED GNN, effectively learns edge weights prior to aggregating the features across neighboring nodes. Importantly, the learned edge weights are not necessarily symmetric. In the classic formulations of GAT, the attention weight from node i to (asj) depends on the concatenation of their feature vectors (u; (u)|)u,)) and the shared learnable parameter a: Gij LeakyReLU(a" (u::/[uul]]]))) Similarly, the attention weight from to i (ajz) is computed as: Czz LeakyReLU [[,]l/u]) Since uullu, * ujllu, the raw attention scores eij and ey will generally differ. Even if a symmetric function used to com- pute the attention weight, the attention coefficients 0ij are computed using a softmax function: explery
Oij = ExeNis ] This normalization performed separately for the neighbors of and j. so even if Eiy were equal to eja, the normalization step would generally make Oiyy * a'ja. Therefore, might appear that GATs can learn arbitrary asymmetric edge weights, much like CoED's continuous edge directions.
The key difference between CoED GNN and iieettionbbased models is that CoED GNN does not rely on node features to learn continuous edge directions. Instead, the continuous edge directions are learned directly as part of optimizing for the given learning task. Consider the toy problem illustrated in Figure H.I In this example, nodes in a linear-chain graph are assigned random input features that are independently and identically distributed. The output feature for each node is generated by shifting the input features along the chain in the clockwise direction by one hop. A training dataset consists of multiple realizations of the graph, each with different input and output node features, for a node regression task. GAT fails to correctly propagate the features across the graph in this setup because the node features are entirely uninformative. Consequently, it cannot learn meaningful edge
33

---

Published as a conference paper at ICLR 2025
Input
Output
Optimal edge directions
U1
Us
Ug
U2
U1
U7
Us
Us
U2
Us
Us
Us
U4
Figure H.1: A toy problem of learning to shift node features by one node in the clockwise direction for a circularized linear chain of nodes. In this hypothetical regression problem, the input are the original node features and the output are the node features shifted by one. The node features u, independently and identically distributed and therefore completely uninformative for determining the direction in which node features should be sent. The training data is ensemble of the same cheir--hhain graph with different realizations of the node features. Any method that relies on node features to propagate the features (such GAT) will fail at this task. CoED GNN, however, can learn the optimal edge directions for this task (shown on the right).
weights from the node features to perform the regression task. In contrast, CoED GNN successfully learns the optimal edge directions required to accomplish this task. The failure of GAT on directed graphs with random features has also been empirically demonstrated in the stochastic block model experiments in Zhang et al. (2021).
In many tasks, is necessary learn distinct edge directions in different parts of graph, even when the node features are identical. The GAT framework cannot achieve this because it relies solely on node features to compute edge weights. In contrast, CoED directly learns continuous edge direc- tions by optimizing them specifically for the task. To illustrate this, we compare GAT and CoED on synthetic triangular lattice node regression task, as described in the main text, using node fea- tures derived from CIFAR images (Figure H.2). In this scenario, many nodes share nearly identical features, such as those representing blue sky pixels in an image. GAT fails learn the correct edge directions under these conditions, while CoED successfully identifies the optimal directions for the task (Figure H.3)
Tables and in the main text empirically demonstrate that CoED GNN outperforms GAT on both synthetic and real-world datasets. The superior performance of CoED GNN may stem from the consistency of edge directions: the outgoing message from node i to node j must match the incoming message from node j to node This consistency can be enforced in GAT by requiring constructed modified GAT model enforcing this
that azy = 1 O:ji- To test this hypothesis, requirement and applied it to the synthetic node regression task of directed flow on a triangular lattice graph, described in the main text. To clarify the comparison, instead of using random features, we assigned CIFAR image pixel values as features for each node. Edge weights between nodes and j were determined using the GAT formulation: aij LeakyReLU(a* [u, u,]), where a is a learnable parameter. Importantly, we enforced the constraint aj 1 asj- As shown in Figure H.3] this modified GAT model, even with self cof-sssnsttt edge weights, fails learn the node regression task, much like the conventional GAT formulation. In contrast, CoED GNN successfully learns optimal edge directions and accurately predicts the output values.
Finally, we provide empirical evidence that CoED GNN can mitigate oversmoothing and facilitate long-range information transmission across graphs. In undirected graphs, information diffuses rather than flows because when node passes message to node j. node simultancously passes mes- sage back to node i. This bidirectional exchange causes the diversity of node features to diminish rapidly they converge to the averaged features across all nodes. Learning optimal edge directions addresses this issue by enabling directed information flow, preventing uniform diffusion (see Figure I..
To demonstrate this empirically, we applied CoED GNN to the synthetic triangular lattice graph problem, where node features are derived from CIFAR image pixels described earlier. Figure
34

---

Published as a conference paper at ICLR 2025
Original Image
Lattice Node Festures
Original Image
Lttice Node Features
Original Image
Lattice Node Features
Original Image
Lattice Node Fearures
21
0
0-
Figure H.2: Examples of triangular lattice graphs with node features derived from CIFAR image pixel values. The CIFAR image is shown on the left, and the corresponding matiie node features is depicted on the right. In practice, the feature of each node is 3 dimensional vector of RGB values. As described in the main text, output node features are generated by propagating these input features through the directed triangular lattice for 10 hops. The node regression task involves predicting these output node features from the input node features.
GAT
2.8e.1
SC-CAT
Co-CNN
1e:1
Loss
2.7e-1
MSE
2e:2
GAT
Se-3
SC-GAT
Co-GNN
Model Layers
Model Layers
(a) Comparison of baseline models with leamable edge attributes
(b) CoED the baseline models
Figure H.3: Left: Mean Squared Error (MSE) loss as function of model depth for GAT, the self- consistent GAT formulation (SC-GAT), and Cooperative GNN (Co-GNN) applied to the node gression task on a triangular lattice graph with node features derived from CIFAR images. Right: Same as left, but including results from CoED GNN. CoED GNN is the only model that demon- strates consistent performance improvement with increasing depth.
35

---

Published as a conference paper at ICLR 2025
5e-2
learned
learned original
26-1-
Dirchlet energy
Dinchler energy
1e-2
1e-1
3e-3
1e-3
Convolution
Convolution
(a) Triangular lattice (undirected)
(b) Synthetic GRN (directed)
Figure H.4: Dirichlet energy of node features computed after applying the graph Laplacian over multiple iterations (number of convolutions shown on the x-axis) for both the original graph Lapla- cian and the Laplacian constructed using the learned edge directions from CoED, Results for the triangular lattice graph with CIFAR-derived node features synthetic GRN data are shown on the right. The slower decay of Dirichlet energy when using the Laplacian with learned edge directions indicates that CoED mitigates the oversmoothing problem.
shown the left, and results for
(radi (radians)
Gone Indox
(radinn))
Gene index
Gene index
(a) Edge direction before training
(b) Edge directions after training
Figure 1.1: Visualization of the Perturb-seq data graph before and after applying CoED learn edge directions. Initially, all edges are undirected. CoED assigns continuous edge directions, revealing complex and structured pattern. For clarity, subset of genes is visualized, with the i-j element of the matrix representing the phase angle assigned to each edge using our fuzzy Laplacian formulation.
H.3 compares the performance of CoED GNN and a baseline GAT model as a function of model depth. CoED GNN's performance improves with increasing depth, whereas GAT's performance saturates, showing that CoED GNN's learned edge directions alleviate the oversmoothing problem. This trend also observed in Figure 4 with the random features. To further illustrate this, computed the Dirichlet energy node features by applying the graph Laplacian multiple times simulate information flow over increasing numbers of hops. As shown in Figure H.4 when the original graph Laplacian is used, the Dirichlet energy decreases rapidly, indicating that node features are converging to the same value. In contrast, using the Laplacian of the directed graph with learned edge directions results in a slower decrease in Dirichlet energy. showing that oversmoothing mitigated by directed information flow.
I VISUALIZATION OF THE LEARNED EDGE DIRECTIONS
To illustrate the edge directions learned by CoED, we visualized the phase angles of edges in a real- world single-cell Perturb-seq dataset (see main text for details). As shown in Figure [.1 the initial edge directions are undirected, with all phases set to π /4.. After training, CoED uncovers a complex structure of continuous edge directions, capturing the gene-gene interactions that connect the nodes (genes) in the graph.
36


Reviews:
[{"review_id": "ZmZxE2QuZ0", "reviewer": "Reviewer_b7qy", "summary": "Traditional GNNs often suffer from feature oversmoothing due to their diffusion-like message-passing mechanism over undirected graphs. To address this, the authors propose the Continuous Edge Direction (CoED) GNN framework that assigns differentiable fuzzy edge directions to graph edges, allowing features to preferentially flow in one direction and introducing a complex-valued Laplacian for directed graphs with fuzzy edges.", "questions": "1. What is the runtime of the proposed methods, and how does it compare to the baselines? Providing a detailed runtime analysis would enhance the evaluation.\n2. For the node classification task, how does the performance change if the edge direction is made learnable? Prior work, such as [3], suggests that it will likely improve performance.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well-written and offers an intriguing evaluation on graph ensemble data, where the graph structure remains fixed but multiple realizations of node features and targets exist—an important task that demands attention. Additionally, the authors demonstrate that their method is more expressive than the Magnet Laplacian.", "weaknesses": "1. The paper omits important baselines and related work, such as [3], which share similar concepts and should be included for a comprehensive comparison.\n2. If the theorem is highlighted in the abstract and introduction, it should be mentioned explicitly in the main paper for consistency and emphasis.\n3. The evaluation on node classification tasks is unconvincing:\n   - Only one homophilous dataset is included in the study.\n   - The Chameleon and Squirrel datasets used are known to be problematic [1], and it is advisable to use filtered versions for more reliable results.\n   - The heterophilous datasets used for evaluation are all quite small, and the results do not approach the current state-of-the-art. To more robustly validate the claims, experiments on larger-scale heterophilous datasets [1][2] are necessary.\n\n\nReferences\n\n[1] Platonov, O., Kuznedelev, D., Diskin, M., Babenko, A., & Prokhorenkova, L. (2023). A critical look at the evaluation of GNNs under heterophily: Are we really making progress?. arXiv preprint arXiv:2302.11640.\n\n[2] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34, 2021.\n\n[3]Finkelshtein, Ben, et al. \"Cooperative graph neural networks.\" ICML 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ot6B3StUDH", "reviewer": "Reviewer_QZRJ", "summary": "The paper presents a novel graph neural network architecture named Continuous Edge Direction (CoED) GNN, which improves upon traditional GNNs by introducing the concept of fuzzy edge directions. These directions allow for more effective feature propagation by varying continuously, enabling more controlled information flow between nodes. CoED GNN utilizes a complex-valued Laplacian that represents these fuzzy directions, where the real and imaginary parts correspond to opposite directions of information flow. The architecture is especially effective in graph ensemble settings, where the structure is static but node features vary, such as in gene regulatory networks and power grids.", "questions": "See Weaknesses", "limitations": "", "rating": 3, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper is well-written, and the motivation of the model is reasonable.\n2. The idea of learning optimal edge directions, and using phase angles to scale the direction-aware information flow is intuitive and interesting.\n3. Theoretical Analysis appears to be rigorous and formally describes the expressive power of the proposed model", "weaknesses": "1. Directed graph Laplacians have been extensively explored in previous studies, including seminal works like those by F. Chung [1] and on Hermitian Laplacian [2]. The introduction of the fuzzy graph Laplacian is a significant contribution of this work. However, while comparisons have been made with the magnetic Laplacian, it would be beneficial to extend these comparisons to include contemporary directed graph Laplacians to fully contextualize its advancements and differences.\n\n2. From my perspective, employing phase angles to dictate continuous edge directions is designed to adaptively modulate the weights from in-neighbors and out-neighbors. However, could we alternatively employ a shared learnable function $f$, , such as, $\\mathrm{Sigmoid}(f(u_i, u_j))$ and $1- \\mathrm{Sigmoid}(f(u_i, u_j))$ , to scale the information flow? This approach might offer a simpler alternative to using complex values. Furthermore, related work such as superGAT [3] enhances GAT by identifying important neighbors, a concept that could potentially be extended to directed graphs. By incorporating the separate message-passing strategy of DirGNN—which independently considers in-edges and out-edges—we could apply superGAT to each direction separately. Subsequently, the two representations could be combined to produce the final node representation.\n\n3. While the concept of learning optimal edge directions is intriguing, I find the experimental results presented in the paper unconvincing. Firstly, as illustrated in Table 1, the CoED model achieves the best results in only one out of the five datasets examined. Secondly, the paper omits experiments on several pertinent datasets commonly used in related works, notably those employed by DirGNN, which is frequently referenced in this study. Specifically, there are no results included for datasets such as SNAP-PATENTS, ROMAN-EMPIRE, and ARXIV-YEAR, despite DirGNN reporting significant findings on these along with various other baselines. Incorporating these datasets could enhance the persuasiveness of the results. Thirdly, I view SAGE as a specific instantiation of DirGNN, implying that the performance of DirGNN should be at least as good, if not better, than that of SAGE. To enhance DirGNN's performance, particularly on the Texas and Wisconsin datasets, I experimented with incorporating an MLP layer following the final layer of DirGNN. This modification has significantly improved its performance. Additionally, the Texas and Wisconsin datasets are relatively small, and the Chameleon and Squirrel datasets reportedly contain significant amounts of duplicate data [4]. Therefore, I believe these datasets may not be the most suitable for evaluating the model's performance. The authors might consider using the AM-Photo, AM-Computer, or Citeseer datasets, as employed in [5], to provide a more robust assessment.\n\n   \n\n[1] Laplacians and the Cheeger inequality for directed graphs. \n\n[2] Graph signal processing for directed graphs based on the hermitian laplacian.\n\n[3] How to find your friendly neighborhood: Graph attention design with self-supervision. \n\n[4] A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\n\n[5] Digraph Inception Convolutional Networks.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "w9PCCViKTd", "reviewer": "Reviewer_SbM9", "summary": "This paper leverages \"fuzzy edges\" to improve the flow of information across a graph. CoED GNN learns directions (coefficients) for each edge. This is achieved through a complex-valued fuzzy Laplacian. Experiments on both synthetic and real-world datasets demonstrate CoED GNN's good performance in node classification and regression tasks, attributed to its ability to optimize long-range feature propagation.", "questions": "1. Could the authors provide theoretical analysis of the superiority of CoED GNN over GAT?\n2. In Equation (1), why $(L_F)_{ij}=\\text{exp}(i\\theta_{ij})$? Is the first $i$ the imaginary unit? If so, the authors should use different letter to denote the $i$th node.\n3. Could the authors provide explanation and experimental results to show that CoED GNN can alleviate the problem of homogenization of information across the graph?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The fuzzy Laplacian enables CoED GNN to handle directional message passing, preserving the discriminative features over longer distances.\n2. CoED GNN shows performance gains in diverse datasets, highlighting its adaptability to both synthetic and real-world applications.", "weaknesses": "1. The edge directions are essentially edge weights. GAT can also learn edge weights, and it even leverages node features while doing so, unlike CoED GNN. Since GAT utilizes more information, it should perform better. At the very least, the weights learned by GAT should not be worse than those learned by CoED GNN. It is puzzling that GAT performs worse than CoED GNN in the experimental results provided by the authors. The authors should provide theoretical provements to show that CoED GNN is superior.\n2. The authors should explain why CoED GNN can alleviate the problem of homogenization of information across the graph. Also, the authors should  provide experimental validations.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Lr1rCdXq9f", "reviewer": "Reviewer_xqhX", "summary": "This paper proposes a novel framework for undirected and directed graphs called Continuous Edge Direction (CoED) GNN, based on the insight to assign fuzzy edge directions in a novel complex-valued Laplacian matrix. The paper includes empirical comparison to various GNNs on both synthetic and real-world datasets, and theoretically shows the expressive power of CoED.", "questions": "- What is the runtime comparison explicitly, e.g. via a table, when comparing CoDE with MagNet etc.?\n- The paper uses the idea of separate aggregation of in- and out- information in addition to self. [1] does something similar and is based on flow imbalance in its objective. How are they compared empirically?\n- In line 315, where should $\\alpha$ appear in the formula?\n- Table 1 compares a CoED version without edge direction learning, how about with edge direction learning for node classification?\n\nReference:\n\n[1] He, Y., Reinert, G., & Cucuringu, M. (2022, December). DIGRAC: digraph clustering based on flow imbalance. In Learning on Graphs Conference (pp. 21-1). PMLR.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is generally well-written and well-motivated.\n- The topics of expressive power, directed GNNs, and oversmoothing in GNNs are significant.\n- The proposal of fuzzy edge directions is novel and effective.\n- The statements are theoretically and empirically grounded.", "weaknesses": "- No source code is provided.\n- It would be better to show the runtime comparison explicitly, e.g. via a table, when comparing CoDE with MagNet etc.\n- The paper uses the idea of separate aggregation of in- and out- information in addition to self. [1] does something similar and is based on flow imbalance in its objective. It would be better to add some discussion and comparison in experiments.\n- In line 315, it is not clear where $\\alpha$ should appear in the formula.\n- Table 1 compares a CoED version without edge direction learning, how about with edge direction learning for node classification?\n- (bonus) It would be better to show the ultimate directions (visualized) for some directed or undirected graphs to show more insights.\n\nReference:\n\n[1] He, Y., Reinert, G., & Cucuringu, M. (2022, December). DIGRAC: digraph clustering based on flow imbalance. In Learning on Graphs Conference (pp. 21-1). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)