What Are Good Positional Encodings for Directed Graphs?
Authors: Yinan Huang
Haoyu Peter Wang
Pan Li
Venue: ICLR 2025 Poster (2025)
Keywords: Directed graphs
positional encodings
graph neural networks
Primary area: learning on graphs and other geometries & topologies

Abstract: Positional encodings (PEs) are essential for building powerful and expressive graph neural networks and graph transformers, as they effectively capture the relative spatial relationships between nodes. Although extensive research has been devoted to PEs in undirected graphs, PEs for directed graphs remain relatively unexplored. This work seeks to address this gap. We first introduce the notion of *Walk Profile*, a generalization of walk-counting sequences for directed graphs. A walk profile encompasses numerous structural features crucial for directed graph-relevant applications, such as program analysis and circuit performance prediction. We identify the limitations of existing PE methods in representing walk profiles and propose a novel *Multi-q Magnetic Laplacian PE*, which extends the Magnetic Laplacian eigenvector-based PE by incorporating multiple potential factors. The new PE can provably express walk profiles. Furthermore, we generalize prior basis-invariant neural networks to enable the stable use of the new PE in the complex domain. Our numerical experiments validate the expressiveness of the proposed PEs and demonstrate their effectiveness in solving sorting network satisfiability and performing well on general circuit benchmarks. Our code is available at https://github.com/Graph-COM/Multi-q-Maglap.

Published as a conference paper at ICLR 2025
WHAT ARE GOOD POSITIONAL ENCODINGS FOR DIRECTED GRAPHS?
Yinan Huang
Haoyu Wang
Georgia Institute of Technology yhuang 903 g0 edu
Georgia Institute of Technology haoyu. wang@gatech. edu
Pan Li
Georgia Institute of Technology panli@gatech. edu
ABSTRACT
Positional encodings (PEs) are essential for building powerful and expressive graph neural networks and graph transformers, they effectively capture the relative spatial relationships between nodes. Although extensive research has been devoted to PEs in undirected graphs PEs for directed graphs remain relatively unexplored. This work seeks to address this gap. We first introduce the notion Walk Profile, a generalization of walk-counting sequences for directed graphs. A walk profile encompasses numerous structural features crucial for directed graph- relevant applications, such as program analysis and circuit performance prediction. We identify the limitations of existing PE methods in representing walk profiles and propose a novel Multi-q q Magnetic Laplacian PE, which extends the Magnetic Laplacian eigenvector- based PE by incorporating multiple potential factors. The new PE can provably express walk profiles. Furthermore, we generalize prior basis- invariant neural networks to enable the stable use of the new PE in the complex domain. Our numerical experiments validate the expressiveness of the proposed PEs and demonstrate their effectiveness in solving sorting network satisfiability and performing well on general circuit benchmarks. Our code is available at httpp:://githe cot wwtp://acoo.aaaacooooooooo Mutoo//MMlltee -t-prrapppooooootuiii-----a--ala
INTRODUCTION
Positional encoding (PE) (Vaswani al. 2017 Su et al. 2024), which refers to the vectorized representation of token positions within series of tokens, has been widely integrated into modern deep learning models across various data modalities, such language modeling (Vaswani et al.
2017). vision tasks (Dosovitskiy et al. 2020), and graph learning (Dwivedi et al. 2023 Rampášek al. 2022). The key advantage of PE is its ability preserve crucial positional information of tokens, thereby complementing many downstream position-agnone
models like transformers (Yun et al.,
2019) and graph neural networks (GNNs) (Li Leskovec 2022 Lim al. (022). For regularly ordered data, such as sequences or images, defining PE is relatively straightforward: for instance, one can use sinusoidal functions of varying frequencies (known as Fourier features) PE (Vaswani et al. 2017). In contrast, designing PE for structured graph data is more challenging due to the lack of canonical node ordering in graphs.
Designing effective positional encodings for graphs (Dwivedi et al. 2023 Kreuzer et al. 202 Beaini
al. 2021 [im et al. 2022 Dwivedi al. 2021 Rampášek et al.) 2022 Li et al.) 2020 Wang et
2022) is significant because graph PEs can be used for building powerful graph transformers as well
as improving the expressive power of GNNs (Li et al. 2020 Wang et al. 2022 Lim al. 2022)
In particular, for undirected graphs, Laplacian positional encoding (Lap-PD) (Dwivedi al. 2023
Kreuzer et al. 2021), ) derived from the eigenvalues and eigenvectors of graph Laplacians, is adopted
by many state-of the-art graph machine learning models (Rampášek et al. [022]] Chen al. 2022
Lim et al. 2022 Huang et al. 2023). Lap-PE is powerful as it well preserves the information of the
graph structure and express various distance features defined undirected graphs: examples such

---

Published as a conference paper at ICLR 2025
as diffusion distance (Coifman & Lafon 2004 Bronstein et al. [017 Wang et al. 2024), resistance
distance (Xiao & Gutman 2003) and biharmonic distance (Lipmann et al. 2010 Kreuzer et al. 2021) crucial structural features widely used in many graph learning and analysis tasks.
Despite the success of Lap-PEs for undirected graphs, many real- applications involve directed
graphs, such circuit design, program analysis, neural architecture search, citation networks, and
financial networks Wang et al. [020] Phothilimthana et al. [024;] ZZhan et al.) [201% [a
[lllamanis
2022] Zhou al. 2019] Ren et 2021 Liu 20199 Boginnki al., [2005 Wen al.) 2020).
In these graphs, the structural motifs such as bidirectional walks and loops, which consist of edges
with different directions often carry critical semantic meanings. For example, in data-flow analysis.
programs can be represented as data-flow graphs (Brauckmann et al.) [2020] Cumminn et al. (020).
Understanding reachability, liveness, and common subexpressions requires analyzing whether walks between nodes have edges pointing in the same or reverse directions (Cummins et al. 2020; 2021).
Logical reasoning often depends on identifying directed relationships, such as common successors
(X Y + Z) or predecessors (X + Y < Z) (Qiu et al. 2023 Tian et al. 2022). Feed-forward loops that involve the two directed walks X - Z and X
Z, are fundamental substructures
in many biological systems (Mangan & Alon 2003). Figure shows some examples.
However, how to define PEs for directed graphs to capture the above bidirectional relations is still an open question. Most previous works focus dealing with the asymmetry of Laplacian matrix, and propose, e.g., symmetrized Laplacian PE (Dwivedi et al., 2023). singular value decomposition PE (SVD-PE) (Hussain et al.] 2022). Magnetic Laplacian PE (Mag-PE) (Geisler et al.. (023). Nevertheless, these PEs can be shown to be not expressive enough to capture the desired bidirectional relations. In this work, we address this problem by studying more expressive PEs for directed graphs.
Our main contributions include:
We formally propose a notion named (bidirectional) walk profile, which generalizes undirected walk counting to bidirectional walk counting and can be used to represent many important bidirectional relations in directed graphs such as directed shortest (longest) path distance, common successoos/prredccsssorr, feed-forward loops and many more. Walk profile ((m, k) represents the number of length-m bidirectional walks with exact & forward and m k backward edges.
We show that symmetrized Laplacian PE, SVD-PE, and Mag-PE fail to express walk profile To address this problem, we propose Multi-q Magnetic Laplacian PE (Multi-q Mag-PR) that jointly takes eigenvalues and eigenvectors of multiple Magnetic Laplacian with different potential constants q. Interestingly, this simple adaption turns out to be extremely effective: it can provably reconstruct walk profiles of the directed graph. The key insight is that serves as the frequency of phase shift that encodes the counts of the walks with certain numbers of forward and backward edges, and using certain number of different q allows full reconstruction of the counts of these bidirectional walks by Fourier transform. Notably, we show that the number of potential q have to be half of the desired walk length for perfect recovery.
Besides, naive use of complex eigenvectors of Magnetic Laplacian could lead to severe stability issues (Wang et al., 2022). ). we introduce the first basis-invariant and stable neural architecture to handle complex eigenvectors. Specifically, we generalize the previous stable PE frame- work (Huang et all 2023) from real to complex domain. The invariant property ensures that two equivalent complex eigenvectors (e.g., differ by complex basis transformation) have the same representations. Moreover, the stability allows bridging Lap-PE (potential = 0) and Mag-PE (potential q , 0) smoothly. Our experiments show the key role of stable PE architecture to get good generalization performance.
Empirical results on synthetic datasets (distance prediction, sorting network satisfiability pre- diction) demonstrate the stronger power of multi-q Mag-PEs to encode bidirectional relations. Real-world tasks (analog circuits prediction, high-level synthetic) show the constant performance gain of using multi-q Mag-PEs compared to existing PE methods.
2 RELATED WORKS
Neural networks for directed graphs. Neural networks for directed graphs can be mainly catego- rized into three types: spatial GNNs, spectral GNNs and transformers. Spatial GNNs those who directly use graph topology as the inductive bias in model design, including bidirectional message
passing neural networks (Jaume et al. 2019 Wen et al., 2020 Kollias al. 2022) for general
2

---

Published as a conference paper at ICLR 2025
directed graphs and asynchronous message passing exclusively for directed acyclic graphs (Zhag let [ 2019b] Dong et al. 2022b] Thost & Chen 2020). Spectral GNNs aim to generalize the concepts
of Fourier basis, Fourier transform and the corresponding spectral convolution from undirected graphs
to directed graphs. Potential spectral convolution operators include Magnetic laplaciann (Furutani
[022 Fiorini et al. [023] Zhang et al.) (02Tb), Jordan decomposition (Singh ct al. 2016). Perron eigenvectors (Ma et al. 2019), motif Laplacian (Monti et al., (018). Proxim- 2020) and direct generalization by holomorphic functional calculus (Koke) & Cremers, 2023). Finally, transformer- based models adopt the attention mechanism and their
eet al.
2020 He et al.
ity matrix TTng et al.
core ideas are to devise direction-aware positional encodings that better indicate graph structural
information (Geisler et al. 2023 Hussain et al. 2022). which are reviewed next.
Positional encodings for undirected/ddrrected graphs. Many works focus on designing positional
encodings (PE) for undirected graphs, e.g., Laplacian- based PE (Dwivedi et al. 2023] Kreuzer et al.
2021 Beaini et al. 2021] Lim et al. 2022 Wang et al. [022 Huang et al. (023), random walk PE (Li
et al. 2020 Dwivedì et al. 2021). See Rampášek et al. (2022) for survey and Black et al. (2024)
for a study that relates different types of PEs. On the other hand, recently there have been efforts to generalize PE to directed graphs. Symmetrized Laplacian symmetrizes the directed graph into an undirected one and applies regular undirected Laplacian PE (Dwivedi et al.) 2023). Singular vectors of the asymmetric adjacency matrix have also been used PE (Hussain et al. 2022 Wang a..).
and so have the eigenvectors of the Magnetic Laplacian and bidirectional random walks (Geisler al. 2023). For directed acyclic graphs. a depth-based PE has been used (Luo et al. 2024).
PRELIMINARIES
Basic notation. We denote the real domain by R and the complex domain by C. Bold-face letters such as A are used to denote matrices. At denotes the conjugate transpose of A. We use i = V-1 to represent the imaginary unit and I for the identity matrix.
Directed graphs. Let G = (V,E) be a directed graph, where V is the node set and & CCV x V the edge set. We call u predecessor of v if (u,v) & and call u successor of if (v.u) u) E E. Let A E {0, 1| be the adjacency matrix of directed graph with n nodes where Au, 1 if (u, v) E and 0 otherwise. Denote D as the diagonal node degree matrix where Da,a is the in-degree din, plus the out-degree doat. of node u.
Graph Magnetic Laplacian. With a parameter 9 E called potential, the complex adjacency matrix Ag E Caxn is defined by [Aglu.e - exp(i2ngg(A.. and 0 otherwise. A, encodes edge directions via the phases of complex numbers exp(=i2nq) Magnetic Laplacian Lg is correspondingly defined by Lg I-D 1/2 A 1/2, For a weighted graph A E R=Xn, we can instead define [Aglu.- = (A.. + A exp exp ( (Au, Ac,a)) and Ly thereby. As generalization of Laplacian to directed graphs, Lg is widely studied in applied mathematics, physics and network science for directed graph analysis (Shubin 1994 Fanuel et al.
Av,u)} } if (u, v) E E or (v. u) E E,
2017, 2018), and has been recently introduced as a promising way to build graph filters and deep learning models for directed graphs (Furutani et al., 2020 Geisler al., 2023 Fiorini al. 2023 He et al. (022). Symmetrizee Laplacian, i.e., Laplacian of the undirectized graph, is essentially special case of Magnetic Laplacian with potential q = 0 (no phase difference). Magnetic Laplacian Lg is hermitian since D L This implies that there exists eigendecomposition L, = V VAVi, where V E C is a unitary matrix, and A diag(A) A) constitutes of real eigenvalues À E R" The Magnetic Laplacian PE of node u is defined by the corresponding row of V, denoted by a,, = Vv..l
WHAT ARE GOOD POSITIONAL ENCODINGS FOR DIRECTED GRAPHS?
In this section, we are going to study the capability of directional PEs to encode bidirectional relations. We first define a generic notion Walk Profile, which counts the number of walks that consist of forward or backward edges and characterizes the expressive power of PEs to represent walk profiles. As aforementioned, these bidirectional walks are important they can form many crucial motifs to enable the studies and analysis of directed graphs, such as feed-forwart loops in biological systems and common successoors/preeecessoo for logie reasoning.
3

---

Published as a conference paper at ICLR 2025
(aa) Aue
Me 2 2) Alzo
C2 1) (AR har Abe
Groee
Aaragitaun
3
(ar(3.2) ho (a ther
+(A Aha
Soasdan
7ubo
P C 03- %
(a) Upper: Feed-forwane loop. Lower: logical reasoning
(b) Examples Walk Profile from node a to u.
Figure 1: Examples of real-world directed motifs/patterns (left) and walk profile (right).
4.1 WALK PROFILE: GENERAL NOTION THAT CAPTURES BIDIRECTIONAL RELATIONS
On undirected graphs, one way to describe the spatial relation between node u and v is through walk counting sequences different lengths Wa. (A,,0, A A ...,, A.). In particular, suppose E (0,1)xxM, then it is known that A u,v counts the number of ?-length walks from u to and the shortest path distance can be found by spdu. min( A > 0}. For directed graphs, we can adopt the same description with A replaced by the asymmetric adjacency matrix. However, this single-directional walk could miss important distance information on directed graphs. For example, consider a directed graph with E = {11, 3). (2,3)), where node and 2 share one common predecessor. However, as cannot reach node from node 1, the walk counting sequence from node 2 to node is always zero. In this case this single-directionll walk fail to capture the relation.
A key observation is that descriptions of directed motifs/patterns such as common succes- sors/predecessors require knowing both the powers of A (walks via forward edges) and that of A (walks via backward edges), and their combinations AA and A A. This observation moti- vates us define walks in bidirectional manner as follows.
Definition 4.1 (Bidirectional Walk), Let G (V,E) be directed graph. A bidirectional walk w = (wo; U1, U2, U2,...) ...) a sequence of nodes where every consecutive two nodes form either a forward edge (Vi, vi+1) E & or a backward edge (1:+1, U/) E &. The length of bidirectional walk is the total number of forward edges and backward edges it contains.
Bidirectional walks contain significantly more information than unidirectional walks. Note that two bidirectional walks of the same length can differ in the number of forward and backward edges. To capture this finer granularity, we introduce the concept of Walk Profile. generalization of walk counting on directed graphs that retains more detailed structural information.
Definition 4.2 (Walk Profile). Let G be directed graph and A be the adjacency matrix. Given two nodes u, v, Walk profile & (f. contains exact forward edges and o - backward edges.
(f k) is the number of length- bidirectional walks from u to v that
For example, (1, Au, represents the connectivity from u to e; 4 2u,
(AAT) Ja,o-
(AT T A) which counts the number 2-length walk with one forward edge and one backward edge, which corresponds the number of common successors or predecessors. One also compute the shortest/longest path distance using the walk profile. See Figure for illustrations. Note that the definition of walk profile can be generalized to weighted graphs by replacing adjacency matrix with weight matrix A E B
Remark 4.1. Let G be a directed graph with Adjacency matrix E (0. 1 and consider two nodes u. U. The shortest path distance can be computed via spd = min E Z: Dn Furthermore, if G is acyclic, then longest path distance is Ipda, = max(( E Z Pu, (l, > 0}.
(E, () 0}.
4.2 THE LIMITATIONS OF EXISTING PES TO EXPRESS WALK PROFILE
Intuitively, good PE can characterize certain notations of distances between nodes and based on PEs Z,, 2,, Now let us study the power of the existing PEs for directed graphs via the notion of walk profile. Formally, we say PE method is expressive if it can determine P based 2, and 2,.
4

---

Published as a conference paper at ICLR 2025
Mag-PE. L, -I- A- 1/2 D-1111 be Magnetic Laplacian with potential q. Since Magnetic graph Ag faithfully represents the directed structure of the graph, one may conjecture that eigenvalues À and eigenvectors Zu: 2n should be able to compute the walk profile. However, it turns out that it is impossible to recover (u,o(m, k) from them, as shown in the following Theorem 4.1
Theorem 4.1. Fix q IR. There exist graphs 9, G' with adjacency matrices A, A' E RRax, and nodes u, V E Vg and u', v' E Vgs, such that Mag-PE E (A, Rus zv) = (X, Zuu, : but 4 (m, of d' we (m, k) for some m.k. k.
Remark 4.2. From the formal proof of Theorem 4.1 (see Appendix A we can also show that Mag-PE node u, v unable to compute shortest path distance spdu. More insights into why single may fail are to be discussed after the proof sketch of Theorem 4.2 Besides, as symmetrized Laplacian can be seen as a special case of Magnetic Laplacian (q = 0). the same negative results also apply for symmetrized Laplacian PE.
SVD-PE. Singular vectors of the asymmetric adjacency matrix may also be used as directed PE (Hus) sain et al. 2022). That is, A ddiag(or) W and define SVD-PE 2n := (U..:, W..)) Here, we provide an intuition on why SVD-PE is hard to construct the walk profile. Recall that in eigen-decomposition, power series of A can be computed via power series of eigenvalues, i.e., (A) = E, 9, = (f be expressed by
which explains that the distance in the form of f(A) can @ Vo.)) In contrast, this property does not hold for SVD. For instance, A = Udiag(o) (() (r) U (d) # Udiag(o") W T. As a result, computation of [A²] [A (the walk profile more broadly) requires not only SVD-PEs Zus Ze but also w for some w E 4/(u,u),
4.3 MAGNETIC LAPLACIAN WITH MULTIPLE POTENTIALS Q
The limited expressivity of existing PE methods motivates us to design more powerful direction- aware PE. The limitation of Mag-PE comes from the fact that the accumulated phase shifts over all bidirectional walks by Magnetic Laplacian cannot uniquely determine the number of walks. For example, suppose q = 1/8, both the following cases - (1) node v is not reachable from u v.s. - (2) U2 <- yield the same [Lş 0 for any integer f. However, the numbers
#1 - and of length-é walks between u and v are different. The potential acts like a frequency that records the accumulated phase shift for a walk, and one single frequency q cannot faithfully decode the distance.
Based on the frequency intepretation, we propose Multi-q Magnetic Laplacian PE (Multi-q Mag-PE),, which leverages multiple Magnetic Laplacians with different q's simultaneously. A q vector denoted by q = (g....., (Q) is going to construct Q many Magnetic Laplacian Lig Laga and Multi-q Mag-PE PE is defined by concatenation of multiple Mag-PE:
- (VV VV.lu.))
where V,, is the eigenvectors of L Intuitively, different frequencies (potential g) give a spectrum of phase shifts that allows to decode spatial distances in a lossless manner.
Indeed, despite the simplicity of the above extension, the following Theorem d.mo that this simple extension can be rather effective: with a proper number q's, one is able to exactly compute the walk profile of the desired length. Section 5.1 also provides extensive empirical justifications.
Theorem 4.2. Let L be a positive integer and let Q = [ + L, where [.1 means ceiling. If we let q (q), 92, (2) with Q distinct q's and qı,..., Qr E [0, 1)). then for all E S L and k. S E, from
walk profile Eb (,, k) can be exactly computed from (X 24 2g), where X², 2 are concatenation of eigervaluesseiigemeettoss of different q from q.
Proof Sketch. Fix two nodes u, v. As from (X7, 2 2.), question becomes how we can determine the walk profile T (..) from [Allu.v By the definition, one can find the following key formula that relates walk profile with AC: For any q.
construct AAllu, for any q. So the
[A (A e -1mmg Σ & Pn (L, k)) i4mgk
K=
Fix the integer L and consider a length-Q list of a denoted by q = (qi,,.,, 42). Then, by Eq.
2 given [A] ju, A ggg u, for all I., solving Tb (n k) is equivalent solving linear
5

---

Published as a conference paper at ICLR 2025
Stable PE network processing eigenvectors V w. eigenvalues Au:
Stop
Step
Ve.
[diag((e(An.)]] (An)llo
[v (adaaaaa(aa))).. (
Agu
X
2m
(real&imag)
X
Stable PE feature augmentation for backbone models (end-to-oee aand-to-end training) IV d.diag( Wa. aleasa...om
Znodo
Zedge
Base Model GNNs,
Poodt Of Podge
graph Transforme...
RXP
X R
Figure 2: Multi-q Magnetic Laplacian under stable PE framework. Eigenvectors and eigenvalues of each Magnetic Laplacian with different q will be processed independently and identically and concatenated in the end.
system F$ = Y, where F CQX(L+1), + R(L+1)xL Y E CQXL and Fj F..m exp m. + j.m pm,,(m,)) (equals zero if m), y,m = [4 uu.v e22rgaym In order to make the linear system F well-posed for uniquely solving the walk profile & from Y. it generally requires F to have Q L distinct rows, i.c., ('4mq; ddmgq for any * such that Fourier matrix F becomes full-rank. Fortunately, as the unknowns + lies in real space, the number of rows Q can be reduced to [I//2] thanks the symmetry of Fourier coefficients Y of real $ As a result, we can choose Q L/2] many distinct qs with qi E [0, {), by which we can construct full-rank system to solve 4.
The proof provides several insights: (a) determining the walk profile from the powers of A, of single ş is ill-posed; (b) in contrast, using [/2]] + many q's simultaneously makes the problem uniquely determine the walk profile length L. The number q can be chosen based on the walk length of interest for a specific task; (c) the capability of expressing the walk profile is robust the values of multiple q' In practice, we may choose evenly-spaced
well-posed and allows
[L/21+1] where F indicates discrete Fourier transform, or randomly sampled
q = (2(L+)) .... 2(L+1)
%. E [0. where F is non-
non-singulae singular with high probability.
Limitations. Despite the provable effectiveness of Multi-q Mag-PE, it suffers from some limitations. One is its extra computational overhead: PEs induced by multiple q's require multiple runs of eigenvalue decomposition and introduce the higher PE input dimension. This introduces trade-off between the expressivity of PEs and computational complexity, which can be tuned in practice by selecting different numbers of q's. We provide runtime comparison with various numbers of q's. see Sec. 5.4 Typically, the actual runtime of Q = is about twice of the runtime when Q 1. We also discuss the pros and cons of using Multi-q Mag-PE PE v.s. directly using walk profiles as injected features Appendix G
4.4 THE FIRST BASIS-INVARIANT/STAAN NEURAL ARCHITECTURE FOR COMPLEX EIGENVECTORS
Recent studies have shown that Lap-PE has the issues of basis ambiguity and instability (Wang et al, 2022; Lim et al.) 2022 Huang et al. 2023 Black et al. 2024). That is, because cigen- decomposition is not unique (i.e.,
(VQ)A(VQ) for some orthogonal matrix Q), Lap-PE can become completely different for the same Laplacian and tend to be unstable to Laplacian perturbation. In fact, this problem technically becomes even harder for Mag-PEs because Mag-PEs live in the complex domain and the basis ambiguity extends to unitary basis transform:
Lg = VAVi = (VQ) for some unitary matrix Q E C"*", For Multi-q Mag-PE, even without duplicated eigenvalues, cigenvectors associated with each exhibit their own symmetry (if an eigenvector, " for any E (0, 2TT) is also an eigenvector). exacerbating the ambiguity and stability issues even further.

---

Published as a conference paper at ICLR 2025
To address this problem, aim to generalize the previous stable PE frameworks, PEG (Wang et al. 2022) and SPE (Huang et al. 2023), J, to handle complex eigenvectors. Our framework will process PEs into stable representations and use them augmented node/edge features in the backbone model. We first consider Mag-PE of a single q and then extend it. Specifically, let ofpuee dalgee _ R be cennuutttion-quivariiinnn function w.r.t. d-dim axis (i.e., equivariant to permutation of eigenvalues), we can construct node-level stable PE node E Rnxd and/or edge-level stable PE Zedge E Raxaxd,
[Re { V diag 01 (A)) Re V diiag(o mank (A))
nnade
Poode
(3)
Im diag
o node (A)) V ... Im V diag( om V)),
Zedge
Pedge
Re { V diag( (01
V Re diag @m sdge ()))
(4)
[ cdge (A)) ..... Im V diag ( (A))
where V. À are the eigenvectors and eigenvalues of Magnetic Laplacian with a certain q. (.).) lmf-) means taking the real and imaginary parts, respectively, and Pnode "xxxx22 - R=x and Padge R=xnx2m Fnxxxp are permutation equivariant funetion w.r.t. n-dim axis (i.e., equivariant to permutation of node indices). Afterwards, Znode will be concatenated with node features, and Redge will be concatenated with edge features.
Note that this is the first work to propose the usage of complex PEs in a stable way. In practice, the backbone model is GNN, only a portion of (sparse) entries [ (u, & need to be computed. For the multi-q case, we apply the same Φe and p to the eigenvectors and eigenvalues from different q's and concatenate the outputs. A similar proof technique can show that the above stable PE framework can achieve generalization benefits as stated in Proposition 3.1 in Huang et al. (2023). Moreover, can be shown that Gnode: Zedge are continuous in the choice of q due to the stable structure. Such continuity naturally unifies Lap-PE and Mag-PE, because symmetrized Laplacian L, a special case of Magnetic Laplacian Lg when q - O.
EXPERIMENTS
In this section, we evaluate the effectiveness of multi-q Mag-PEs by studying the following questions:
Q1: How good are the previous PEs and our proposed PEs at expressing directed dis- lances/relations, e.g., directed shortest/longest path distances and the walk profile?
Q2: How do these PE methods perform on practical tasks and real-world datasets?
Q3: What is the impact on using PEs with or without basis-invariant/stable architectures?
our experiments, we mainly consider three ways of processing PEs: (1) Naive: directly concatenates raw PEs with node features; (2) SignNet (Lim al. 2022): makes PEs sign invariant. We adopt the same pipeline as in (Geisler et al., 2203),, Figure G.I; (3) SPE (Eqs. 3 4): we follow (Huang et al.) 2023), and use clement-wine MLPs Φ1, ... om. GIN (Xu et al. 2018) Pmode and MLPs as Pedge- Key hyperparameters are included in the main text while full details of the experiment setup and model configurations can be found in Appendix B
5.1 DISTANCE PREDICTION ON DIRECTED GRAPHS
Datasets. To answer question Q1. we follow Geisler et al. (202)) and generate Erdös-Rényi ran- dom graphs. Specifically, we sample regular directed graphs with average node degree drawn from 11, 2}. or directed acyclic graphs with average node degree from (1, 1.5, 2, 2). In both cases, there are 400,000 samples for training and validation (graph size from 16 to 63, train- ing:validation=9555) and 5,000 samples for test (graph size from 64 to 71). Finally, We take the largest connected component of each generated graph and form our final dataset. The task is to predict the pair-wir wise distances for node pairs measured by: (1) shortest path distance; (2) longest path distance; (3) walk profile. Only node pairs that are reachable or have non-zero walk profile elements included for training and test. For the walk profile, choose predict the normalized walk profile of length 4, which is a 5-dim vector. Normalized walk profiles corresponds to the probability of bidirectional random walks, with adjacency matrix A in walk profiles replaced by random walk
D D=14 A. as the latter is consistent with the normalized Laplacian practice. See Appendix for discussions.
D D-112 AD
total we use in
total
7

---

Published as a conference paper at ICLR 2025
Table 1: Test RMSE results over 3 random seeds for node-pair distance prediction.
Directed Acyelic Graph
Regular Directed Graph
PE method
PE processing
spd
Ipd
wp(4.-)
epd
4pd
up(4.
Naive
0.727 20.00s
0.370
2,068 20088.0.044
1.808
a.480
Tap
SignNet
0.537+3.015
0.771 20.013
0.437
2.064
1.900=0..02
0.518=0.027
SPE
0.305
0. 0.636
0.326ga.01
2. 2.066
1. 1.920
0. 0.452
Naive
0.619 Lov002
0.833 1o.00e
0.721 1oo0m
2.196 uo.002
1.982 1.000
0.519_o..00
SVD
SignNet
0.673
a.872
0.443
2:229 so
1. 1.99Ki
0.541 1.54120.001
SPE
0.727 Louoen
0.912 Lo.001
0.721
0.721gaom Laoon
2.261 to noe
1.22 000
0.735 Lo,00
Naive
0.306
0. 0.50320.00m
I 1820
1,700g
0.31 20.033
MagLap--g (q=0.1)
SignNet
0.55442.001
0.609 20.002
0.208
2.048=0.004 2.004
1.88
= 1.881
0.413=0.000
SPE
0.12 0.144200022
0. 0.433
0.043
I L,220
1.547 #0.040
0.133
MagLap-1q (best g)
SPE
0.122
0.432 10.004
1 1.533 10.007
1. 1.493 Laous
0.132 10.000
Naive
0.353
0.03020.000
0. =0.0LD
2.70820.022
1.601 20.002
0.237 20.007
MagLap-Multig
SignNet
0.579 10.001
0. 2800 g.000
1 900 o.non.
1. 1.781
0.377
SPE
0.016-0.000
1855+00000
1.002-0.000
0.546+0.00s
1.100-0..07
0.074+0.001
PE method
PE processing
Test Fl
2.0
Naive
51.30+2.90
0.9
Lap
SignNet
49.50+4..1
SPE
50.3513.10
0.8
Naive
68.6819.65
0.7
Maglap- lq (best 9)
SignNet
76. 76.2816682
SPB
86, 86.855
3.6
Naive
75.12+12.78
Maglap-5q
SignNet
29.77799..88
0.5
Mag (3c)
Lup
SPE
91.27
6.4
Magrap (10)
14
15
Soquance Longth
Table 2: Test Fl scores over 5 random seeds for sorting network satisfiability.
Figure 3: Test Fl scores w.r.t. different sort- ing network lengths.
Models. To show the power of pure PEs, we take PEs z 2y of node u, predict the distance du between V. We consider three ways of processing PEs: (1) naïve concatenation: MLP((Zuv z. 2,]);; (2) SignNet-based: MLP(SignNerr)
MLLP(Zeedec)) (u,e) where Zedge is defined in Eq. 4 For Multi-q Magnetic Laplacian PE, we choose q= = (0. ...
(ognNet(=.)): (3) edge-SPE-based,
L-11 where 2L
L= 5 for predicting walk profile, L 10 for predicting shortest/longest path distances on directed 15 for predicting shortest/longest path distances on regular directed graphs For single-q Mag-PE: PE, we tunc q from 0 to 0.5, and report both the result of 0.1 and the tuned best q. It turns out the performance of single-q Mag-PE PE in this task is not sensitive to the value of as long as not being too large.
acyelic graphs and
Results. Table I indicates several conclusions. (1) Multi-q Mag-PE constantly outperforms other PE methods regardless of how process the PE. Particularly, it is significantly better than other methods when equipped with SPE; (2) impact of symmetry: when restricted to the use of naïve concatenation, the overall performance of all PE methods is not desired. This is because naive concatenation cannot handle the basis ambiguity of cigenvectors. It is also worth noticing that SignNet's performance may be even worse than naïve concatenation. This is because the PE processed by SignNet suffers from node ambiguity, which loses pair-wise distance information (Zhang et al., 202 Lim et al. (002)). Besides, SignNet is not stable. In contrast, when we properly handle the complex eigenvectors by SPE, the true benefit of Mag-PE starts to present. On average, the test RMSE of Multi-q Magnetic Laplacian gets reduced by 66% compared to the one uses naive concatenation.
Ablation study. The comparison to single-q Mag-PE naturally serves as an ablation study of Multi-q Mag-PE. One may wonder if Multi-q Mag-PE; performs better because it can search and find the best q from q. We can show that the joint use of different g's is indeed necessary, and it is constantly better than using the single best q. The hyper-paramen search of the best for single-q Magnetic Laplacian for different tasks can be found in Appendix C
Robustness of multiple 9 values. As implied by Theorem the expressivity to compute walk profile is robust to the choice of multiple g values. To verify this, Multi-q Mag-PE PE with randomly sampled q (draw each 9 from uniform distribution) is implemented. See details in Appendix EE] Our results show that random o sometimes achieves even better prediction than evenly-spaced q
8

---

Published as a conference paper at ICLR 2025
Table 3: Test results (RMSE for G/iM/BW/PM, MSE for DSP/LUT) for Open Circuit Benchmark and High-level Synthesis, For each base model and task, Bold denotes the best result for each base model and task, and Bold" for the best result that exceeds the second best result by one standard deviation.
Rise Modill
PR: metiodd
PF: prozessing
Gain
RW
PM
DSP
LLT
Nune
N/A
0.462amm
2.827
20e
1.55en
Lap
SPE
SignNet
0:2301000
4116..mm
1.22
1.22
2,062
4.187
144
Lo.0ce
Undirected GIN
Muglap 1q (g=0.011
SPE
SignNet
0 44
12
4.306 o0
1.12
2.606 -
2.039
2,027 esuoss
2.02
Maglip 1q ()
SPE
4.281
2011
2 ao
Muglip-Multigg
SPE
SignNet
0.01T
o.175
10
1 a...00000
2.552
2:005
4.311
2:125 10.076
Non:
N/A
0 2
2:32
1.30 20,
Tap
SPE
SignNet
2.3822001
4.37 29.71
4,153an
1.100.0.00
1,12
2,267 -8.19
2:200
1.800 200
Didirected
Maglap-1q (g=0:011)
SignNet
SPE
0.394gun
2.388
4.35Lauus2
4.1524000
1.123 uoe
2.344-8.15
2.314
29.22
1880 e0.1en..
Maglip-1q lq (best +)
SPE
0.38520002
4.1 431
1.09
2.256
1,768 g0
Muglap-Multiig
SPE
SignNet
0.371
0.3812000s
4. 2.05120.39
4 1.4
1. 1.119a0.00
1.16
2.207
2.212
1. 1.735
7.791 20.053
Nome
N/A
0.388
107 wss
8.154-6
2886 an
Lap
SPE
SignNet
0.375
4 10
4,08530 tee
L0 016
1065
5,107
5.103
2 2.2
2.223
SAT (undineesee-GIN))
Maglap-1q 1g (g-0::01
SPE
SignNet
0:382
4. 1.1
4.061 auunt
107
5.087
3 8.206-5.10
2 2.21
20.14
Maglap-1q Tq (best g)
SPE
0-301 sonis
LOMY ao.
4.11%
902 .0.354
Magle--Mulri-g
SPE
SignNet
0.050
4.044g
4.044a0m0
1.86600.cm nen
3.070+0.300
2.121 44.44
2:207 20.11n
2 2.553
Nome
N/
0.512
100550000
2.721
2.117
Lap
SPE
0.388
3.919an.15
1.046
L069an.ccm
2.519
2.178=9.2c7
s0.00
SAT (Nid
Muglap-1q la (g=00.11)
SignNet
0.384gomis
4.02340002
L0055a nea
2010
2.054
SPE
O 0.364
3.90610
1074
2.687 4..00
2. 2.192 2.192
Maglip-1q Iy (best
SPE
0.390:0.03
3.960
2.657
2.107
Maglap- Multiqq
SPE
0.42020015
0.359%..co
3.930...00
4112224.125
1.04
2.616.6.154
2,441 27.41
2.145 079
2.082
5.2 SORTING NETWORK SATISFIABILITY
Sorting network (Knuth) 1997) is a comparison-based algorithm designed to perform sorting on a fixed number of variables. Each sorting network consists of sequence of operations Ui, Vy sorted(v,, Uy) and we say a sorting network is satisfiable if it can correctly sort an arbitrary input of a given length. It can be parsed into directed graph for which the direction (i.e., the order of operations) impacts the satisfiability. We test the ability of positional encodings by how well they can predict the satisfiability.
Datasets. We randomly generate sorting networks by following the setup from Geisler et al. (2023). Sorting networks are parsed into directed acyclic graphs whose nodes are comparison operators and directed edges connect two operators that share variables to sort. The dataset contains 800k training samples with a length (the number of variables to sort) from 7 to 11, 60k validation samples with a length 12, and 60k test samples with a length from 13 to 16. We perform graph classification to predict satisfiability.
Models. We adopt a vanilla transformer /Vaswani et al. 2017 as our base model. PEs are either naively concatenated into node features, using SignNet before concatenation, concatenated both into node features and attention weights using SPES Eqs and For single-q Magnetic Laplacian PE, we tune q from 20-de to 5 20-de. where where de max (mi,mm, n), 1), m is the number of directed edges and n is the number of nodes. We find q = 20-dg gives the best results, which is the same y in Geisler et al. (2023). For multi-q Mag we choose q - (20-do 1... 5
5
Results. Table 2 displays the average Test F1 score of classifying satisfiability. Again, Multi-q Mag-PE equipped with SPE achieves the best performance. Mag-PE with SignNet (both single-q and multi-q) performs poorly compared to their SPE counterparts. Figure illustrates the test Fl on samples with respect to individual sorting network lengths. Note that although single-q Mag-PP PE and multi-q Mag-PE PEg perform equally well on length=13 samples, the single-q one generalizes worse on longer-length sorting networks. contrast, Multi-q Mag-PE has nearly the same generalization performance as the number of variables sort increases.

---

Published as a conference paper at ICLR 2025
5.3 CIRCUIT PROPERTY PREDICTION
Open Circuit Benchmark (Dong et al. 2022a) contains 10,000 operational amplifiers circuits directed graphs and the task is predict the DC gain (Gain), band width (BW) and phase margin (PM) of each circuit. These targets reflect the property of current flows from input nodes to output nodes and thus require a powerful direction-awarc model. The dataset consists of 2-stage amplifiers and 3-stage amplifiers and we use 2-stage amplifiers in our experiment. We randomly split them into 0.9:0.05:0.05 as training, validation and test set.
Open Circuit Benchmark.
High-level Synthesis. The HLS dataset (Wu et al., 2022) collects 18, 750 intermediate representation (IR) graphs of C/C++ code after front-end compilation (Alfred et al., (007). provides post- implementation performance metrics on FPGA devices as labels, which are obtained after hours of synthesis using the Vitis HLS tool (vit) and implementation with Vivado (viv). The task to predict resource usage, namely look-up table (LUT) and digital signal processor (DSP) usage. We randomly select 16570 for training, and 1000 each for validation and testing.
Models. We adopt GIN (Xu et al. 2018) as the backbone and implement two variants: (1) undirected- GIN: the normal GIN works on the undirected version of the original directed graphs; (2) bidirectional-
GIN: bidirectional message passing with different weights for two directions, inspired by (Jaume et al.,
2019 Thost Chen 2020 Wen et al., 2020). The state-of-the-an art graph transformer SAT (Chen et al.
is also adopted, whose GNN extractor is undirected-GIN bidirected-GIN as mentioned for self-attention computation. PEs are processed and then concatenated with node features using Sit or with node and edge features using SPE (Eqs. 3 4 We generally choose q (1, 2, .... 10) 100 or q= (1,2, 5)/ 5)/100 for Multi-q Mag-Ph PE (see Appendix B for specific for each tasks). For single-q
2022
Magnetic Laplacian, we report g 0.01 well as the best results of single q by searching over the range of multiple q. See Appendix C for full results of varying single
Results. Table 3 shows the test RMSE (5 random seeds) on Open Circuit Benchmark (Gain, BW, PM) and the test MSE (10 random seeds) high-level synthesis (DSP, LUT). Notably, Multi-q Mag-PE PE with Stable PE framework achieves most of the best results for targets compared to other PEs.
5.4 RUNTIME EVALUATION
Increasing the number of q boosts expressivity but brings extra computational costs. We evaluate the runtime of preprocessing (eigendecomposition) training and inference for various number of g, as shown in Figure 4 We can see that the training time of even 10 g generally about 1.5 3 times the training time of one single The preprocessing time is not concern as they are negligible compared total training time for hundreds of epochs in our experiments. See detailed setup at Appendix D
Traiingg
3500
distanc decsent dacaset
2500
distance detauen (x10
chitarcc decsent (x110)
datanet
soriing catasst
dacase:
2000
HLS dataset
NLS ditanee
1750
0.00
2000
1500
1500
1250
6:00
1000
1000
200
5
Number of
Numreer
Numberafa
Figure 4: Runtime of preprocessing (left), training (middle) and inference (right) on three datasets. The shown runtime distance dataset is 10 times the actual ones for better illustration.
CONCLUSION
This work studies the positional encodings (PEs) for directed graphs. We propose the notion of walk profile to assess the model's ability to encode directed relation. Limitations of existing PEs to express walk profiles are identified. We propose a simple yet effective variant of Magnetic Laplacian PE called Multi-q Mag-PE that can provably compute walk profile. the basis- insis-invariant and stable PE framework is extened to address the basis ambiguity and stability problem of complex eigenvectors. Experiments demonstrate the consistent performance gain of Multi-q Mag-PE.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This research supported by the NSF awards PHY-2117997, IIS-2239565, CFF-2402816, IIS- 2428777 and JPMorgan Faculty award.
REFERENCES
Vitis
hls tool.
https://wwH.
vitis-hle html
Vivado.
hctps:/ www. xi http///www.ppcccccc/////oooooaaa
Aho Alfred, Lam Monica, and Ullman Jeffrey, Compilers Principles, Techniques & Tools. pearson Education, 2007.
Miltiadis Allamanis. Graph neural networks in program analysis. Graph neural networks: foundations, frontiers, and applications, pp. 483-497, 2022.
Dominique Beaini, Saro Passaro, Vincent Létourneau, Will Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. In International Conference on Machine Learning, pp. 758.758. PMLR, 2021.
Mitchell Black, Zhengchao Wan, Gal Mishne, Amir Nayyeri, and Yusu Wang. Comparing graph transformers via positional encodings. arXiv preprint arXiv:2402. 14202, 2024.
Vladimir Boginski, Sergiy Butenko, and Panos M Pardalos. Statistical analysis of financial networks. Computational staristics & data analysis, 48(2):431 14:4,,1444,1- 2005.
Alexander Brauckmann, Andrés Goens, Sebastian Ertel, and Jeronimo Castrillon. Compiler- based graph representations for deep learning models of code. In Proceedings of the 29th International Conference on Compiler Construction, pp. 201-211, 2020.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-42, 2017.
Dexiong Chen, Leslie O' O'Bray, and Karsten Borgwardt. Structure-aware transformer for graph representation learning. In International Conference on Machine Learning, pp. 3469-3489. PMLR, 2022.
RR Coifman and S Lafon. Diffusion maps: Applied and computational harmonic analysis. Appl Compul Harmon Anal, 21(1):5-14, 2004.
Chris Cummins, Hugh Leather, Zacharias Fisches, Tal Ben-Nun, Torsten Hoefler, and Michael O'Boyle. Deep data flow analysis. arXiv preprint 201.v:201,.01470, 2020.
Chris Cummins, Zacharias V Fisches, Tal Ben-Nun, Torsten Hoefler, Michael FP O' Boyle, and Hugh Leather. Programl: A graph- based program representation for data flow analysis and compiler optimizations. In International Conference Machine Learning, pp. 2244-2253. PMLR, 2021.
Zehao Dong, Weidong Cao, Muhan Zhang, Dacheng Tao, Yixin Chen, and Xuan Zhang. Cktgnn: Circuit graph neural network for electronic design automation. In The Eleventh International Conference on Learning Representations, 2022a.
Zehao Dong, Muhan Zhang, Fuhai Li, and Yixin Chen. Pace: A parallelizable computation encoder for directed acyclic graphs. In International Conference on Machine Learning, pp. 5360-5377 PMLR, 2022b.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition at scale. International Conference Learning Representations, 2020.
11

---

Published as a conference paper at ICLR 2025
Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. In International Conference Learning Representations, 2021.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24 (43):1-48, 2023.
Michaël Fanuel, Carlos M Alaiz, and Johan AK Suykens. Magnetic eigenmaps for community detection in directed networks. Physical Review E, 95(2):022302, 2017.
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(1): 189-199, 2018.
Stefano Fiorini, Stefano Coniglio, Michele Ciavotta, and Enza Messina. Sigmanet: One laplacian to rule them all. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pp-
7368,7576, 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ürzhurg, Germany, September 16-20, 2019, Proceedings, Purt 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. In International Conference on Machine Learning, pp. 11144-11172. PMLR, 2023.
Yixuan He, Michael Perlmutter, Gesine Reinert, and Mihai Cucuringu. Msgnn:
A spectral graph neural network based on novel magnetic signed laplacian. In Learning on Graphs Conference, pp. 40-1. PMLR, 2022.
Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, and Pan Li. On the stability of expressive positional encodings for graph neural networks. arXiv preprint 2110v:2310.02579. 2023.
Md Shamim Hussain, Mohammed Zaki, and Dharmashankar Subramanian. Global self-attention as a replacement for graph convolution. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp. 655-665, 2022.
Guillaume Jaume, An-Phi Nguyen, Maria Rodriguez Martinez, Dean-Philiippe Thiran, and Maria Gabrani. edgnn: A simple and powerful gnn for directed labeled graphs. In International Conference on Learning Representations, 2019.
Donald Ervin Knuth. The art of computer programming, volume 3. Pearson Education, 1997.
Christian Koke and Daniel Cremers. Holonets: Spectral convolutions do extend to directed graphs.
In The Twelfth International Conference on Learning Representations, 2023.
Georgios Kollias, Vasileios Kalantzis, Tsuyoshi Idé, Aurélie Lozano, and Naoki Abe. Directed graph auto-encoders. In Proceedings of the AAAI conference on artificial intelligence, volume 36, pp. 7211-7219, 2022.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneuu, and Prudencio Tossou. Rethinking graph transformers with spectral attention. Advances in Neural Information Processing Systems, 34, 2021.
Pan Li and Jure Leskovee. The expressive power of graph neural networks. Graph Neural Networks: Foundations, Frontiers, and Applications, pp. 63-98, 2022.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. Advances in Neural Information Processing Systems, 33:4465 4478, 2020.
12

---

Published as a conference paper at ICLR 2025
Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXhh:2202.133111 2022.
Derek Lim, Joshua Robinson, Stefanie Jegelka, and Haggai Maron. Expressive sign equivariant networks for spectral geometric learning. Advances in Neural Information Processing Systems, 36, 2023.
Yaron Lipman, Raif M Rustamov, and Thomas A Funkhouser. Biharmonic distance. ACM Transac- tions on Graphics (TOG), 19(3):1-11, 2010.
Hanwen Liu, Huaizhen Kou, Chao Yan, and Lianyong Qi. Link prediction in paper citation network to construct paper correlation graph. EURASIP Journal on Wireless Communications and Networking, 2019(1):1-12, 2019.
Yuankai Luo. Veronika Thost, and Lei Shi. Transformers over directed acyclic graphs. Advances in Neural Information Processing Systems, 36, 2024.
Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. Spectral-based graph convolutional network for directed graphs. arXiv preprint wxxv:/907.089900 2019.
Shmoolik Mangan and Uri Alon. Structure and function of the feed-forward loop network motif. Proceedings of the National Academy of Sciences, 100(21):1 10980-1--95, 2003.
Federico Monti, Karl Otness, and Michael M Bronstein. Motifnet: a motif-based graph convolutional network for directed graphs. In 2018 IEEE data science workshop (DSW), pp. 225-228. IEEE, 2018.
Mangpo Phothilimthana, Sami Abu-El-Haija, Kaidi Cao, Bahare Fatemi, Michael Burrows, Charith Mendis, and Bryan Perozzi. Tpugraphs: A performance prediction dataset on large tensor compu- tational graphs. Advances in Neural Information Processing Systems, 36, 2024.
Haiquan Qiu, Yongqi Zhang, Yong Li, and Quanming Yao. Logical expressiveness of graph neural network for knowledge graph reasoning. arXiv preprint arXiv:2303, 12306, 2023.
Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Do- minique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 15:14551-14515, 2022.
Pengzhen Ren, Yun Xiao, Xiaojun Chang, Po-Ya Yao Huang, Zhihui Li, Xiaojiang Chen, and Xin Wang. A comprehensive survey of neural architecture search: Challenges and solutions. ACM Computing Surveys (CSUR), 54(4):1-34, 2021.
MA Shubin. Discrete magnetic laplacian. Communications in mathematical phythematicalphysccc,,, physics, 164(2):259-217 1994.
Rahul Singh, Abhishek Chakraborty, and BS Manoj. Graph fourier transform based on directed laplacian. In 2016 International Conference on Signal Processing and Communications (SPCOM), pp. 1-5. IEEE, 2016.
Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Neurocomputing, 568: 127063, 2024.
Veronika Thost and Jie Chen. Directed acyelic graph neural networks. In International Conference on Learning Representations, 2020.
Ling Tian, Xue Zhou, Yan-Ping Wu, Wang- Wao Zhou, Jin-Hao Zhang, and Tian-Shu Zhang, Knowl- edge graph and knowledge reasoning: A systematic review. Journal of Electronic Science and Technology, 20(2): 2022.
Zekun Tong, Yuxuan Liang, Changsheng Sun, David Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv preprint arXiv:2004. 13970, 2020.
13

---

Published as a conference paper at ICLR 2025
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
Hanrui Wang, Kuan Wang, Jiacheng Yang, Linxiao Shen, Nan Sun, Hae-Seung Lee, and Song Han. Gen-rl circuit designer: Transferable transistor sizing with graph neural networks and reinforcement learning. In 2020 57th ACM/IEEE Design Automation Conference (DAC), pp. 1-6. IEEE, 2020.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks. arXiv preprint arKiv:2203.0011: 2022.
Qitong Wang, Georgios Kollias, Vasileios Kalantzis, Naoki Abe, and Mohammed Zaki. Directed graph transformers. Transactions on Machine Learning Research.
Xiyuan Wang, Pan Li, and Muhan Zhang, Graph as point set. arXiv preprint (rXiv:4405.02793 2024.
Wei Wen, Hanxiao Liu, Yiran Chen, Hai Li, Gabriel Bender, and Pieter-Jan Kindermans. Neural predictor for neural architecture search. European conference on computer vision, pp. 660-676. Springer, 2020.
Nan Wu, Hang Yang. Yuan Xie, Pan Li, and Cong Hao. High-level synthesis performance prediction using gnns: Benchmarking, modeling, and advancing. In Proceedings of the 59th ACM/IEEE Design Automation Conference, pp. 49-54, 2022.
Wenjun Xiao and Ivan Gutman. Resistance distance and laplacian spectrum. Theoretical chemistry accounts, 110:284- 28944-2889220 2003.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2018.
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank Reddi, and Sanjiv Kumar. Are trans- formers universal approximators of sequence-to-sqqeene functions? In International Conference on Learning Representations, 2019.
Guo Zhang, Hao He, and Dina Katabi. Circuit-gnn: Graph neural networks for distributed circuit design. In International conference on machine learning, pp. 7364-7373. PMLR, 2019a
Muhan Zhang, Shali Jiang, Zhicheng Cui, Roman Garnett, and Yixin Chen. D-vae: variational autoencoder for directed acyclic graphs. Advances in neural information processing systems, 32, 2019b.
Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. Advances in Neural Information Processing Systems, 34:9061-9077 2021a.
Xitong Zhang, Yixuan He. Nathan Brugnone, Michael Perlmutter, and Matthew Him. Magnet: neural network for directed graphs. Advunces in neural information processing systems, 34: 27003-27015, 2021
Yaqin Zhou, Shangqing Liu, Jingkai Siow, Xiaoning Du, and Yang Liu. Devign: Effective vulner- ability identification by learning comprehensive program semantics via graph neural networks. Advances in neural information processing systems, 32, 2019.
14

---

Published as a conference paper at ICLR 2025
A DEFERRED PROOFS
A.1 PROOF OF THEOREM
Theorem 4.1. Fix q IR. There exist graphs 9, with adjacency matrices A, A' E Ruxn and nodes u, U E Vg and u', o' E Vg,, such that Mag-PE E (A, Rus 2o) = (X,2, 2ny/ but Lu Lu km, # 4 at wt (m, k) for some m, k.
Proof. Fix a E I and two nodes u, Pick and fix anther node ug that is not u, v. Let us define graph A RR such that diag(A) = 0, and for all w, r E V, Au., Aug.r otherwise, for all nodes w, r. Note that complex adjacency matrix A,- = (A + A @xpp ( A ZAg where 1, /,/ denote amplitude Ag 2ng
and A =
A uniquely determines A by the relation A and phase of complex numbers.
Now let us construct A' by constructing A' first. Suppose Hermitian A, has eigenvalue decomposi- tion [Ag]w,r Σx Zw, Let us define another group of eigenvalues X' andd eigenvectors (PE) via:
if w + u0
(5)
80
Fuo.:
140
that is, X, z' shares the exact same spectrum X, z, except that z'o.: exp(ii) Zuo.:- It easy to verify that 2' is indeed eigenvectors by their orthonormality, [A) >x x From this construction, we shall see that (A, Zus zu) (X, z 2()).
construct Hermitian A', as
On the other hand, let us examine the walk profile. For any two nodes w, r, we have
[Agla if W. r # uo if w + uo r u0
[Ag)..r Nu
(6)
[Aglaoirs
if w uo: r + dl
This determines A', which reads
[A] wgry if W, #
1
1 [A] [A wer 2 |[AA/uurl
1
if w + un 7 = tio
2 2nq
2
1
if up, # uo
2
where
1
1 f1
exp (ii)
0
0
2 [[Ag]1r. u, exp(-i0]|+
A Aw,0
(8)
2
2mq
4mq
4
and
1 (
| exp(-i0)
0
2 [Ag] ho.. exp(-i0)1 +
Ama.r + 4
1
+
(9)
2
2mq
4
Now we can see that for the fixed u, v. we have
Ln, (2,2) Φ/ (2, A
2 u,e Σ
Au,wAn
Aly A'
Al uo.v = 0. -0.1-10. 2
Au Aun,y
A u,u0
(10)
9
1 1 4
4Tq
Now let 0 4mg. Then 22, 2) Φ' V' (2,
112 + 0. So the walk profile
& (2, 2), & (2, 2) are different while the PE (A, Zus 2u) = (X, 2/y0 x()) are the samd It is
'Note that here PF denotes the eigenvalues/vectors of A, rather than Lg as the walk profile of A is more naturally correlated to the spectrum of Ag-
15

---

Published as a conference paper at ICLR 2025
worthy noticing that using the same construction except that let Auo.us O, we show that spd(uy u1) = but spd (ug, U1) = 2. Therefore, Mag-PE cannot express shortest path distance as well.
A.2 PROOF OF THEOREM 4.2
Theorem 4.2. Let L be positive integer and let Q -[2] 1/: + 1. where [-] means ceiling. If we let (q). 92, 92,..., with Q distinct o's and 91.... QL+1 E [0, 4). then for all S and k walk profile & (e, k) can be exactly computed from (X8, =/ =g), where X², 2 are concatenation of eigenvalues/eigeenvctooo of different 9 from q.
Proof. The proof starts with identifying a key relation between [A, and & " Note that [A,lu, equals the sum of weight of all length-l bidirectional walks:
[Ag],,
Σ
[Ag]aam [Ag]ur,0 A
Σ
[Ag]u.on (Aglui (.ggee
(11)
bi-walk (a, Mi tie of longth
15n)
is bidirectional because A, Hermitian and allows transition along the forward edges with weight Aa, exp (2mg) or backward edges with weight A exp(-i2nq). Note that we can categorize the bidirectional walks by their number of forward and reverse edges. Then for bidirectional walk of length é and exact & forward edges, the forward edges will cause an additional phase term exp(i2rk) while the remaining f & backward edges will cause
= exp(12e (k=()) {))- So there is common phase term exp ( (22m (2k - f)) for all bidirectional walks of length é and l forward edges. Assume there no multi-edges, i.c., directed edges (u, v), (v, u) cannot appear simultancously. now we can re-organize the formula into
[A
Σ
[Ag]a,es [Aylwanen (.gg
bi-walk( u. Mh wor.teg 11)) of length and & forward edges
(12)
Σ
exp(i2ng(2k 1u [Aglen ..ee [Aelu,,
O= bi-walk(u,,us -00.....-----11
length and forward edges
where A.,... A either A At, depending on a forward or backward edge. Now by taking phase term exp (22 E)} out the inner sum, we get exactly walk profile:
[Agl,, Σ
exp 12p 0)}
Σ
[Ai]a, [A2] w2 ... [Aee
bi-walk(u, M.M.a...... (...We-1.1) of length é and forward edges
Σ exp - (e,
(13)
km0
expl -i2mg)))
3xp(i
k=0
Let be any positive integer. Let write the relation above for T (L,) (E L) in a matrix form:
$
(1.
T Pu (2, 0)
Pa. [L, 0)
11
$ 2 (2, 1)
La, L,
Fg
0
Pa (2,
La (L, (a,v(L,2)
= [(e22TAAguuv
[Agluv e CHAT[A
22Ix (1),,,))
0
Pu L,
Pu
(14)
16

---

Published as a conference paper at ICLR 2025
where Fg (1, (xppp//dr)..pp(88s))...... ) RR ( For notation convenience, let us denote RHS as Yg so we write the linear system as Fg Y. Note that as are real values, we can know the values of Y --- by the complex conjugate of Y thanks to the symmetry of Fourier matrix Fg:
1- F
F 2
Fy
Yg
(15)
Now we are ready to prove the theorem. Let Q [L/2] and let q (2.............................. (Q) with each dn < 1/4 and qj are distinct. From eigenvalues/vectors at these frequencies we are able to get Yg. Furthermore, we get to know Y 1 = Y as we just argued. That is, we know Yg' where q² 1/2 g) Since q 1/4, claim that 1/2 q 1/4 and thus q' contains Q' == 2- ([L/2] 1) 2 L + 2 different qs. We can put equation F,y + Yg for each in q' into one matrix equation follows:
L (1,
(1,0)
(2 4 un.0 (2, 0)
Lu,o(L.))
u.e
(1.1)
$ uu (2.1)
Pu,v(L,1)
2 Agnla
2L [AL
u.
Fe.
0
$ (2,2
Pu,v(L,2)
0
Pu,
22 A Angrun
22 (A
Du, (T, L.)
(16)
where F-= = (Fo Fopi..:; F1 E ((L=11) Since Fg' contains Q' 2 different frequen- cies and thus is full-rank, can uniquely determine walk profile Da,y from the RHS matrix. Notably, 4j Iτंي makes Fj discrete Fourier transform, unitary matrix which is invertible by taking its conjugate transpose.
B EXPERIMENTAL SETUP
In this section, we give further implementation details. We use Quadro RTX 6000 Linux system to train the models. The training time for single run is typically between 1 hour to 5 hours.
Note that for SignNet, use e and p represent SignNet(Ur,,..., va) = where Uy is the i-th cigenvectors.
For SPE, task where we find using 2node only has comparable performance to both 2ndde and Zodge-
both node SPE Znode and edge SPE Zedge by default, except for High-level synthetic
For each experiment, the search space for bascline single q is exactly the range multiple For example, if for multiple q we choose q = (1/10, 2/ /0, .... 5/ 10), then for baseline single we search over a = 1/10, 2/1,,,,,...
B. DISTANCE PREDICTION ON DIRECTED GRAPHS
Targets
walk profile (regular graphs)
spd (regular graphs) 8-layer MLPs
1pd (regular graphs)
Base model
Hidden dim
64
Batch size
512
Learning rate
le-3
Dropout
0
Epoch
150
Optimizer PE dim
Adam (81
0.9, 82 0.999)
32
Multiplc
(1/10, 2/10, 5/10) (1/30, 2/30, 15/30)
(1/30, 2/30, 15/30)
PE processing
SignNet (6 =3-layer MLPs, p33-layer MLPs), SPE (d=3-layer MLPs, p=2-layer GIN)
Table 4: Hyperparameter for walk profile/shortest path distance/longest path distance prediction on regular directed graphs
17

---

random variables, Published as a conference paper at ICLR 2025
Targets
walk profile (DAG)
spd (DAG)
Ipd (DAG)
Base model
8-layer MLPs
Hidden dim
64
Batch size
512
Learning rate
le-3
Dropout
0
Epoch
150
Optimizer
Adam (91
0.9, 3g 0.999)
PE dim
32
Multiple PE processing
(1/10, 2/10, 5/10) (1/20, 2/20, ..... 10/20)
(1/20, 2/20, ..... 10/20)
SignNet (e) =3-layer ML.ss, p=3-layer MLPss, SPE (d=3-layer MLPss, p=2-layer GIN)
Table 5: Hyperparameter for walk profilc/shortest path distance/longest path distance prediction directed acyclic graphs.
B.1.1
MODEL HYPERPARAMETER
See Table 4 and 5
B.2 SORTING NETWORKS
Targets
Sorting Network
Base model
3-layer Transformer-mean pooleng++3-layer MLPs
Hidden dim
256
Batch size
48
Learning rate
le-4
Dropout
0.2
Epoch
15 (SignNet) or 5 (SPE)
Optimizer
Adam (3, 0.7, 0.9, weight decay x 5)
PE dim
25
Multiple
(1/20, 2/10, ... 5/20) / de SignNet (ò =3-layer MLPs, p=3-layer MLPs), SPE (d=3-layer MIPss p=2-layer GIN)
PE processing
Table 6: Hyperparameter for sorting network prediction.
B.2.1
MODEL. HYPERPARAMETER
See T
B.2.2 DATASET GENERATION
Our sorting networks generation follows exactly /eesserr et al. (2023). To generate sorting network, the length of sequence (number of variables to sort) is first randomly chosen. Given the sequence length, each step will generate pair-wise sorting operator between
until it becomes a valid sorting network (can correctly sort arbitrary input sequence) or reaches the maximal number of sorting operators. The resulting sorting network is then translated into directed graph, where each node represents sorting operator, whose feature is the ids of two variables to sort. In the sorting network, if two sorting operators share common variable sort, the corresponding nodes will be connected by a directed edge (from the first operator to the second one).
For each generated sorting network, the test dataset further contains the reversion version of the graph, by reversing every directed edge in the directed graph. The resulting reverse sorting network very likely not valid sorting network.
B.3
OPEN CIRCUIT BENCHMARK
B.4 BI-LEVEL GNN
Note that graphs in the dataset are two-level: some directed edges describe the connection of nodes (regular edges), while some extra edges represent subgraph patterns in the graph (subgraph edges). In
18

---

Published as a conference paper at ICLR 2025
Targets
Gain
BW
PM
Base model
4-layer bidi, GIN
3-layer bidi. GIN
4-layer hidi. GIN Sum
Graph Pooling
Sum
Sum
Hidden dim
Batch size
Learning rate
0.0067
0.0065
0.0021
Dropout
0.1
0.2
Epoch
300
300
300
Optimizer
Adam (3,
0.9, 82 = 0.999)
PE dim
10
Multiple
(1/100, 2/100, 10/100) (1/100, 2/100, 5/100)
(1/100, 2/100,
5/100)
PE processing
SignNet (d=1-layer bidi. GIN, p=3-layer MLPs), SPE (d=3-lay layer MLPs. p=2-layer bidi. GIN)
Table 7: Hyperparameter for bidirected GIN on Open Circuit Benchmark.
Targets
Gain
BW
PM
Base model
4-layer undi. GIN
3-layer undi GIN
4-layer undi GIN Sum 288
Graph Pooling
Sum
Sum
Hidden dim
96
192
Batch size
128 0.0067
64 0.0021
Learning
0.0065
Dropout
0.1
0.2
Fpoch
300
300
300
Optimizer
Adam (.0, 0.9, 02 0.999)
dim
Multiple q processing
(1/100, 2/100, ..., 10/100) (1/100, 2/100. .... 5/100)
(1/100, 2/100, .... 5/100)
SignNet (d=1-layer undi. GIN, p=3-layer MI.Ps), SPE (d==3llayer MLPs, p=2-layer undi GIN)
Table 8: Hyperparameter for undirected GIN on Open Circuit Benchmark.
Targets
Gain
BW
Base model
3-layer SAT (2-hop bidi. GIN)
3-layer SAT
(2-hop bidi. GIN)
3-layer SAT (1-hop bidi. GIN)
Graph Pooling
Sum
Sum
Sum
Hidden dim
54
78
Batch size
256
256
64 0.001
Learning rate
0.004
0.001
Dropout
0,2
0.3
0.2
Epoch
200
200
Optimizer
Adam (B, 0.9, 0.999)
PE Multiple q PE processing
(1/100. 2/100, ... 5/100)
(1/100, 2/100. ... 10/100) (1/100, 2/100, ... 5/100)
SignNet (d=1-layer bidi. GIN, p=3-layer MI. ML)ss, SPE (d=3-layer MILPs, /=2-layer hidi. GIN)
Table 9: Hyperparameter for SAT (each layer uses bidirected GIN as kernel) on Open Circuit Benchmark.
Targets
Gain
BW
PM
Base model
3-layer SAT (1-hop undi. GIN)
3-layer SAT (1-hop bidi. GIN)
3-layer SAT (1-hop bidi. GIN)
Graph Pooling
Sum
Sum
Sum
Hidden dim
54
54
54
Batch Size
64
256
64
Learning rate
0.009
0.002
0.001 17
Dropout
0.2
0.3
0.1
Epoch
200
200
200
Optimizer
Adam (B:
0.9, 82 0.999)
PE dim
10
Multiple q PE processing
(1/100, 2/100, ..., 10/100)
(1/100, 2/100,
10/100)
(1/100, 2/100, ..., 10/100)
SignNet (d=1-layer undi. GIN, p=3 layer MLPs), SPE (d=3-laaer MLPs, 2=2-layer undi. GIN)
Table 10: Hyperparameter for SAT (each layer uses undirected GIN as kernel) Open Circuit Benchmark.
our experiment, we uniform apply a GNN to the nodes with subgraph edges only, and then apply other GNN to the nodes with regular edges.
19

---

Published as a conference paper at ICLR 2025
Targets
DSP
LUT
Base model
4-layer bidi. GIN
4-layer hidi. GIN Mean
Graph Pooling
Mean
Hidden dim
84
192
Batch size
Learning rate
0.003
0.0023
Dropout
0.2
0.1
Epoch
400
400
Optimizer
Adam (3, = 0.9, 829,882 0.999)
PE dim
10
Multiple
(1/100, 2/100, 5/100)
(1/100, 2/100, 5/100)
PE processing
SignNet (d=2-layer bidi. GIN, p=3-layer MLPs), SPE (d=3-layer MLPs. p=2-layer bidi. GIN)
Table 11: Hyperparameter for bidirected GIN on High-level Synthetic dataset.
Targets
DSP
LUT
Base model
2-layer undi. GIN
4-layer bidi. GIN
Graph Pooling
Mean
Mean
Hidden dim
56
84
Batch size
32
32
Learning rate
0.006
0.0015
Dropout
0,1
0.3
Epuch
400
400
Optimizer
Adam (8) 0.9, .g 0.999)
PE dim
10
Multiple
(1/100, 2/100, 5/100)
(1/100, 2/100, 5/100)
PE processing
SignNet (d==2-layrr undi. GIN. p=3-layer MI.Ps), SPE (d==-llayer Ml.ss, p=2-layer undi. GIN)
Table 12: Hyperparameter for undirected GIN on High-level Synthetic dataset.
Targets
DSP
LUT
Base model
4-layer SAT (2-hop bidi. GIN)
3 layer SAT (2-hop bidh. GIN)
Graph Pooling
Mean
Mean
Hidden dim
78
62
Batch size
64
64
Learning
0.004
0.004
Dropout
0.1
0.1
Epoch
400
400
Optimizer
Adam (01 0.9, 02 0.999)
dim Multiple q processing
(1/100, 2/100, .... 5/100)
(1/100, 2/100)
SignNet (<==2-layer bidi. GIN, p=3-layer MIPs),, SPE (d=3-layer MI.Ps, /=2-layer hidi. GIN).
Table 13: Hyperparameter for SAT (each layer uses bidirected GIN kernel) on High-level Synthetic dataset.
B.4.1
MODEL HYPERPARAMETER
See Table 8
9
10
B.5
HIGH--EVELL SYNTHETIC
B.5.1
MODEL HYPERPARAMETER
See Table
C VARYING SINGLE q BASELINE
This section shows the effect the varying single the performance of Mag-PE. Horizontal axis is the value single g. vertical axis is the test performance. The dashed line represents the result of Multi-q Magnetic Laplacian with fixed multi-q q as described in Section 5.1
20

---

Published as a conference paper at ICLR 2025
Targets
DSP
LUT
Base model
3-layer SAT (2-hop bidi, GIN)
3-layer SAT (2-hop bidi. GIN)
Graph Pooling
Mean
Mean
Hidden dim
62
Batch size
64
64
Learning rate
0.004
0.004
Dropout
0.1
0.1
Epoch
400
400
Optimizer
Adam (3, = 0.9, 82 = 0.999)
PE dim
10
Multiple PE processing
(1/100, 2/100, 5/100)
(1/100, 2/100, 5/100)
SignNet (d=2-layer bidi. GIN, p=3-layer MLPs), SPE (d=3-laye) MLPs, p=2-layer bidi. GIN)
Table 14: Hyperparameter for SAT (each layer uses undirected GIN as kernel) on High-level Synthetic dataset.
we can see that the multiple q performance consistently beats best performance of single q. which demonstrates the benefits of using multiple q simultaneously.
As shown in Figures 5 6 g
spd
Ipd
walk profile @(4,
0.25
0.3
0.5
0.15
0.4
0.1
Test RMSE
0.05
0.2
0.2
0.4
0.2
0.4
0.2
0.4
2.0
1.8
1.5
1.6
0.3
0.2
12
0.5
Single
Figure 5: Test RMSE for distance prediction with varying g of single-q Magnetic Laplacian. First row is for directed acyclic graphs, and second row is for regular directed graphs.
Sorting network satisfiability
1.0
0.8
6.5
3,50 8,675 6,300 6.125 eise 0.175 0.200 0.25 0.50
Single q (actual patential ald.))
Figure 6: Test F1 of sorting network satisfibability with varying single g.
21

---

Published as a conference paper at ICLR 2025
4.00
0.43
4.50
0.42
4.45
0.41
4.35
4.30
0.40
Test RMSE
0.39
4.20
4.15
0.6
1.0
0.4
Gain (BIGINE)
BW (BIGINE)
PM (BIGINE)
0.42
4.40
0.40
1.11
0.38
1.10
1.09
0.36
1.08
0.2
0.4
0.6
1.0
0.1
0.2
0.3
0.4
0.5
0.2
0.4
0.6
0.8
1.5
Single
Figure 7: Test RMSE for prediction of Gain, BW, PM using backbone GINE or BIGINE, with varying q of single-q Magnetic Laplacian.
DSP (GINE)
LUT (GINE)
2.a
2.7
2.6
MSE
2.5-
0.1
0.2
233
0.4
0.1
0.2
0.3
0.4
0.5
DSP (BIGINE)
WUT (BIGINE)
2.45
2.42
2.35
1.85
233
1.70
93
0.2
8.3
0.4
0.5
0.1
0.2
0.3
0.4
0.5
Single
Figure 8: Test MSE for prediction of DSP and LUT, using backbone GINE or BIGINE, with varying q of single-q Magnetic Laplacian.
22

---

Published as a conference paper at ICLR 2025
Table 15: Test RMSE results over random seeds for node-pair distance prediction.
Acyelic Graph Jpd
Regalar Directed Graph
PB method
Pk processing
spd
apul
ipol
Naive
0.488440.00
0.727
0.370200004
20000000004
188820000
0.480220.00
Lap
SignNet
20.01
a..71
2.00
1.500
0.518
SPE
0.355
0. 0.655 10
0.326
2,066
1.920 10000
01:52
0.019 20.002
2.853
2002000000
2.150-
20000
0..19....0
SVD
SignNet
0.673 ana
0.872 008
0.443
2.229 20000
1.996 20
0.541
SPE:
0.727+0.000
0.912
0.72
2.261
2.12220000
0.755...00
0.360 dea
0.5883go 003
0,20110010
1.70020.00
0:311
Magl.ap-la ap-la (g-0.1)
SignNet
0.554 10.00000000
0. 0.68920 o0s
1..68
2.048_0004
1.881 Loott
0.413 i0.00
SPE
0. 0.121+0.00
0. 453+0,
0.043+0.000
1.020=0036
1.547
0. 0.133=0.00
Ma (bess
0.452
1555_.0m
1.433,000
0.132.0.00
L0.00
Naive
0. 0.30020.000
0.
0.188g0000
170020000
2001
0.251 0.251
Maglaop-Mult-q
SignNet
0.478
0.5799s..00
0.2802
1.900=
2.789
0.377 200007
SPE
0.016 10.200
0.185 1o.000
0.002
Lo.000
0.546 Lo.0s
1.100 10000
0.07 0.0741n..00
Navv
0. 0.350
0 1.50Aa0..00
O 0.204
1,781 1.781=0021
1.60
0:2888 0:288
MagLap-Mullis (random
SignNet
0.409 10.00
0.579 1...0o
Looos
1.895_
1.789 10.00
0.252 20.
SPE
0.015 0.015go.00
0.146000010
0.002-0.000
0.564g00
1.095g0.009
0.07 4.0.000000
PE method
PE processing
Test
1.0
Naive
51.39=2.36
Lap
SignNet
49.50
0.9
SPE
36.35_3.70
Naive
68.68
0.8
Scote
Maglap-1q (best @)
SignNet
76.28
SPR
86.86
0.7
Naive
75.12
Maglap-5q
SignNet
72.97
0.6
SPE
91.27
Maglap (5q)
Naive
51.47
0.5
Maglap (5q-random)
Maglap-5q (random g)
SignNet
30.37=2.12
Lap
SPE
89.36_2.74
0.4
Maglap (1q)
13
16
Table 16: Test F1 scores over 5 random seeds for sorting network satisfiability.
Sequence Length
Figure 9: Test Fl scores w.r.t. different sort- ing network lengths.
D RUNTIME EVALUATION
First, we note that introducing multiple q brings extra computational cost, as stated the Conelusion and Limitations section. But we would like to emphasize that the goal of this work is to illustrate the drawbacks and benefits of single q v.s. multiple q in theory. In particular, we prove that to represent walk profiles-a bidirectional walk descriptor, multiple q required. Thus there is natural trade-off between complexity and expressivity. Results on prediction of various distance metrics demonstrates the superior power of multiple q. further validating our theory.
We evaluate the actual runtime of preprocessing, training and inference stage. For distance prediction, choose connected acyclic graphs; for high-level synthetic dataset, choose undirected GIN as backbone for evaluation. We use SPE to handle PEs and all other hyperparameters are the same mentioned in Appendix B We exclude Open Circuit Benchmark since the the graph size is too small to be interesting (10 to 20 nodes). Figure show the runtime evaluation of multiple q for our tasks, using single Quadro RTX 6000. Preprocessing time refers the pre-computation of cigendecompositions. and training/inference time refers to the runtime on the training set per epoch (average over 10 epochs). Note that the preprocessing time typically a concern, is far less than the total training time, e.g., on high-level synthesis total preprocessing time / total training time (400 epochs) is about 0.5%.
The dataset statistics are also included below for reference.
E IMPACT OF MULTIPLE q VALUES SELECTION POLICY
As implied by Theorem 4.2 any choice of multiple q values should yields the same level of expres- sivity compute walk profile. To verify this, we further implement randomly sampled qī (each q is
23

---

Published as a conference paper at ICLR 2025
Dataset
Average Num. of Nodes
Average Num. of Edges
Distance Prediction
27.4
35.8
Sorting Networks
72.8
272.9
High-level Synthesis
94.7
122.1
Table 17: Dataset statistics.
Table 18: Test results (RMSE for Gain/BW/PM, MSE for DSP/LUT) for circuit properties prediction.
Bold denotes the best result for each base model, and Bold for the best result among all base models.
Base Model
PE mechou
PE processing
Gain
BW
PM
DSP
LUT
SignNet
0.430aan.00
4.712am:134
1.17
2.60han1144
2,022
4.321 mnvee
1.127
2,662 187
1.925
Maglap-1q (g-0.01)
SignNet
SPE
0.120 a000
4 1006
1.070aan111
1.121
a.12
amo0s
2.013
2.600ann19
2,027 aamm
2,024an.m
Undirected-GIX
Maplap-1g (best q)
SPE
a.398
4 4.281
1.11349.022
2.14
2.010anumz
Maglap M
SignNet
SPH
0.389 +0.07
4.175+0.115
1.120
2.582+0.11 133
2.022220.r ore
Maglap-Multi-q (random)
SPE
SignNer
0.397
4. 4.00020004
4 262 200
1.23
1.142
2.772
2,08
2.
Lap
SignNet
SPE
0.391 10007
0.0
4.153 an 100
4.37 m
1.135 n005
1.12
2220 10
2.267
10135
1.786 (.073
1.810 go
1a (q-D.01)
SPE
SignNet
4.152
4.351
1.120
1.131
2.304
1.344.0111
1882 n0.0
1.830.m
Bidircctd-GIN
Maglap-Ia lq (best q)
0.383 0.00
Lo.con
nume
Maglap-Multi-g
SignNet
gnoos
4.318gn
1.119 anos
2.222
1.791 aam:
SPF
0.371 cos
4.051 100
1.116
2,207
20
1.785 co
Maulap-Multi-q (random)
SPE
SignNet
0 0.388
a.078
4.372an Jos
4. 1.10220.123
2.
2.408
2.276am
1.821 none
1.87
Lap
SignNet
SPE
1.308
1.083 se
4.180ammm
1008aune
3.1
3 3.107
2.223
2-155
Maglap-1g 1g (q=0.01)
SPE
SignNer
0 2030
4. 4.148a
4.081
3 3.206
5.8 e0sss
221 42.
2.362
SAT (Undiircctoo-GGIN))
Maglap- lq ())ss
SPE
Lanos
Maglap-Multi-g
NignNer
0.308
2004000000
2000
1.000
2.12
1n.11a
SPE
0,350 kaons
4.0
1.055
Lacon
3.076
2.533
Muglap-Multi-q (random)
NignNer
SPE
0.301 anous
0.356aumm
3.958
20o7
1.052amm4
20004
2.10
2
2.320
Lap
Signiet
SPG
0,308 10
3,900
4.024 10
1.010 a0mm
1.009
2,509
2.713.011
1..09..110
2,005
in
Maglap-1q (q-0.01)
SPE
SignNet
0. 0.3
3 3,996
4.020ano22
1007
1.055an
2068
2.816an12
2. 2,192
2.0554.
SAT (bidirected-GIN)
Maplap-1g 1g (best q)
SPE
0,360
3,900 10o0e
1.02
2,657 in.2s
2,107
Maglap-Multi-g
SugnNNc
4.022 an
1080
2.7i
2
SPF
0.359+0.cos
3.930
cn onn
1.04540.022
2.616an1s:
2.082
Maglap-Multi-g (random)
SignNet
SPE
0.360
3.950
1.064anozzz
100880004
2.690
2.677
2.01620.0m
2.259ena44
uniformly sampled from [0, 1/2) to predict distances and walk profile. Table [5 16 18 and Figure show the results of randomly sampled multiple q compared to previous methods, where evenly-space 2 21 for some L (see specific values in Appendix B) is the origin one we adopted in the main text, and random q = (qi, 92..... qr.) contains L many q values randomly sampled from (0, 1/2]. Note that collision q R yj could lead to a ill-conditioned recovery of walk profile, so we force that 14- 40 2 0.2/ T. during g sampling process. For each run of model training (i.e., each random seed), we sample a different random q. [5]le|I5]show the results. We can see that randomly sampled q has comparable and even better performance than evenly-spaced T. which validates our theory.
q-= =22 2L
F DISTANCE PREDICTION WITH GRAPH TRANSFORMERS
we compared the effectiveness of powerful graph transformers SAT (Chen al. 2022 equipped with different PEs to predict various distance notions. The base graph encoder in SAT is a bidirectional GIN model. The results show that pairing previous PEs with a strong model cannot fully solve the problem of capturing graph distances, while Multi-q Mag PE still brings advantages.
In Table 19
G DISCUSSION: WALK PROFILE DIRECTLY AS FEATURES
One may wonder why not directly compute walk profile as features as alternative to multiple q PE. Walk profile itself is straightforward to compute and can serve as descriptors of graph bidirectional
24

---

Published as a conference paper at ICLR 2025
Table 19: Test RMSE results over random seeds for node-pair distance prediction, with SAT architecture.
Directed Acyelic Graph
Model architecture
PE method
processing
spd
Ipd
wp(4,
SAT (directed GIN)
Lup
SPE
0.355
0.655
0.326+0.001
SAT (directed GIN)
SVD
SPE
0.727
0.912+a.00
0.721 +0.000
SAT (directed GIN)
MagLap-lq lq (q=0.1)
SPE
0.124
0. e.
0.043+0.000
SAT (directed GIN)
MagLap-Multa
SPE
0.016g0.000
0.185
0.002=0.00m
walk patterns, similar random walks features on undirected graphs. However, the dimension of walk profile grows quadratically with walk length. For instance, when predicting the largest path distance on synthetic directed graphs, the longest path distance can be most around 15, and thus we use 15 qs (we find that decreasing the number of q, e.g., to 10, will fail to fit distance greater than 10). this case, the total dimension the walk profile is about (16*15)/22 15)2-2222 (with only top K eigenvectors, K=32 in our example) usually yields good approximation, as shown by the experimental results. Besides, we believe there are further potential advantages of multiple-q positional encodings. For instance, if there are indeed observed in our experiments), it is possible to downsample a small number of to recover the walk profile of large length. Finally, walk profiles inherently features tied to node pairs, it generally requires GNN model to handle node-pair features and yields quadratic complexity. In contrast, positional encodings are node features that are more scalable, especially one may choose top K eigenvectors instead of full eigenvectors.
contrast, multi-q PE
sparsity structures of walk profile (which is
H NORMALIZED WALK PROFILE
We define normalized walk profile (R, k) by replacing every A with random walks Disi A, where [Duaal] h., is the total node degree of node As result, (E, k) represents the probability of landing at node e in bidirectional random walk with forward edges, starting from node u. Note that normalized walk profiles still are able encode important structural/distance information, such as directed shortest/longest path distance.
The reason why considering normalized walk profile is to be consistent with the definition of normalized Laplacian = I D--1// 1/2
wial Ag 11/2 The normalization nature of makes it more suitable to recover normalized walk profile instead of the unnormalized ones.
25


Reviews:
[{"review_id": "FtES17q33v", "reviewer": "Reviewer_EKAQ", "summary": "The authors propose (i) the notion of walk profile in a directed graph for counting bidirectional walks with given numbers of forward and backward edges between two nodes and (ii) a novel positional encoding (PE) which can provably reconstruct the walk profiles of the directed graph. This PE is a direct extension of Magnetic Laplacian PE (Mag-PE) to multiple phase shift parameters q (potentials): the position of a graph node is represented by concatenating Mag-PEs for the different parameters. \n\nIn particular, they prove that in order to reconstruct walk profiles of some length L between any two nodes, just over half of this length is the number of potentials needed in their Multi-q Mag-PE. They also identify that expressing walk profiles is robust to the choice of the q values. Additionally, they generalize their PE, using ideas from previous stable PE frameworks, towards node-stable and edge-stable representations. \n\nIn the experimental section, Multi-q Mag-PE is benchmarked against Laplacian, SVD and Mag-PE in predicting node pair distances and and classifying synthetic graphs; their PE is also coupled with backbone models to predict properties of real word circuits and its robustness explored. In most cases, Multi-q Mag-PE demonstrates a consistent performance gain over comparison baselines with up to x3 execution overhead (due basically to processing/training for more q's).", "questions": "- What is the intuition behind needing the PE of another, third node (w) in addition to the SVD-PEs of u, v nodes when discussing the shortcomings of SVD-PE? Actually SVD seems to be a good choice for compactly expressing powers of special structures like (A * A^T) or its transpose; powers of A are not the only matrices to use in the presence of both forward and backward links/edges. \n\n- Could you provide a more detailed justification of how Equation (2) is produced? (currently: \"By the definition\" (line 260)).\n\n- A practical issue with Mag-PE is what q to choose. In Multi-q Mag-PE the choice of q's does not seem to be a critical factor in performance outputs (e.g. discrete Fourier transform based vs randomly sampled). Is there a justification for this empirically observed robustness? Or again, some care choosing q's should be exercised, but now on the range from which to select q's? For example for the case of random graphs q's are in (0, 1/2) range but for sorting network (satisfiability tasks) q's lie in a much \"slimmer\" range (defined as a function of the number nodes and edges)?\n\n- What is the role of m in Equations (3), (4) (also consider balancing paretheses in these: minor, unbalanced \"{\" instead of \"(\" appear in them)?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- This paper has an exemplary organization with clean definitions and explanation of fundamental developments and a balanced experimental section.\n\n- Both the notion of the walk profile and the generalization of Mag-PE to multiple q's are well motivated and simple to reason about.\n\n- It is important that the paper provides a provable connection of Multi-q Mag-PE (which is a latent representation) to something which is more \"tangible\": path type counters (i.e. walk profile) (Theorem 4.2).", "weaknesses": "- Runtime overhead, although quantified within the x3 envelope in Section 5.4, is a disadvantage in the approach. The combination of SPE and standard Mag-PE could strike a good balance (but then the \"which q value\" question will be raised). Also depending on the number of q's, runtime overhead would vary. On this front, having a rule of thumb to adopt for the cardinality of q's (i.e. Q) for a given task/dataset combination, would be very useful to have.", "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": "c0ndY06YiA", "reviewer": "Reviewer_BH1v", "summary": "This paper proposes a new positional encoding for node representation in directed graphs with provably better expressive power and stability. The paper starts by discussing Magnetic Laplacians with potential $q$, and introduces the concept of *walk profiles*, the number of walks of lengths $l$ given $l - k$ backwards passes of an edge, a more informative descriptor of directed graphs than the standard adjacency powers could provide. It then shows how a Magnetic Laplacian fails to predict walk profiles. Given this, the paper then proposes a simple extension, Multi-q Magnetic Laplacian Positional Encodings, and shows that this extension, with $Q$ distinct q values selected from the range $[0, \\frac{1}{4})$ can predict walk profiles of length $L$ of nearly double $Q$ (Precisely, $Q = \\lceil \\frac{L}{2}\\rceil + 1$). The paper then studies the stability of complex positional encodings returned with multiple Qs and proposes an invariant encoding mechanism (SPE) to circumvent the increasing ambiguity of complex eigenvectors and eigenvalues. \n\nEmpirically, the paper conducts extensive experimentation, both on real-world and synthetic baselines. In synthetic settings, the paper proposes a setting in which models must predict (normalized) walk profiles and other structural properties (shortest path, longest path) over directed graphs. In these experiments, Multi-q Magnetic Laplacian PE with SPE clearly demonstrates superior performance, even with respect to the same model with other encoding choices than SPE (such as SignNet). Moreover, the paper reports ablation results on the selection of $q$ values, showing that multiple $q$ values are indeed necessary for performance, and that even only using the best $q$ cannot reproduce the best results. A robustness study is also reported, highlighting that performance is robust to choices of $q$, and even improves slightly with random (distinct) $q$ values. In terms of real-world experiments, the paper conducts an extensive experimental study on a suite of directed graph benchmarks, demonstrating strong performance improvements with Multi-q Magnetic Laplacian PE across several baseline models. Finally, the paper discusses runtime for pre-processing, training and inference using their approach, and shows that while $q$ does lead to increased runtimes, these increases are palatable.", "questions": "No questions.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The theoretical arguments made by the paper are sound and well-thought: The definition and accompanying figures for walk profiles are very helpful, and are very well connected to real-world settings. Moreover, the proof sketch for showing how Multi-q Magnetic Laplacian can recover walk profiles in Theorem 4.2 appears sound. Overall, the flow of argumentation in this paper is smooth, balanced, and easy to follow, with all pre-requisite results presented in good time.\n- The experimental analysis is compelling and extensive. I especially appreciate the synthetic results and the targeted study of structural graph property predictions, which in my opinion really emphasizes the contribution of the paper's approach. These findings are also further supported by ablation and robustness analysis, and comprehensive details in the appendix. Real-world experiments are also strong and convincing. All in all, the empirical analysis ties very nicely with the theoretical results, and corroborates its results nicely.", "weaknesses": "- One aspect of this work that could be improved is to include baselines and datasets used in previous work, such as OGBG-code, NA and BN (as used, e.g., in Thost et al). The current results are quite strong, but I imagine that the message would be even more compelling if your findings also apply to more specialized models, and produce results on the corresponding datasets to glean more interesting insights, e.g., can these PEs even improve specialized directed GNN models? \n\nIn general, I find that this is a serious work with good presentation, extensive experimentation, and a strong take-away message. I therefore support this paper for publication.", "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": "4mSxwQIuyH", "reviewer": "Reviewer_vWvy", "summary": "This paper attempts to determine good positional encodings for directed graphs. To quantify this, the authors first introduce the graph-topological concept of “walk profilesˮ, which count how many paths there are between all two nodes with a varying relaxation $k$ of how many edges can be oriented in the “wrong wayˮ. Then, they show that a normal Laplacian PE cannot capture all of these walk profiles, while their extended Magnetic Laplacian, $L$-MagPE, can capture all such walks up to length $\\frac{L}{2} +1$.", "questions": "1. Have you tried reducing the cost when calculating higher terms? Or is it a fundamental limitation of the method?\n\n2. Why are walk profiles are of interest? Of course, they might be explicitly such for some tasks, but can graph transformers (such as SAT) not learn them some other way using other positional embeddings?\n\n3. Have you tried other simple models on the datasets, potentially with no positional encodings just to see how they perform as baselines?\n\n4. For the experiment in Section 5.1, have you tried larger graphs?\n\n5. Do you know whether walk profiles are related in any way to $1$-WL or beyond for measuring expressivity?\n\n6. How could the proposed approach be located within existing PEs in terms of expressiveness? The proposed approach may be better (as argued) in terms of capturing walk profiles, but other PEs (or their variations on directed graphs) may have other strengths.", "limitations": "", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "- The paper is presented adequately, and is easy to read.\n- The interest in being able to express the walk profiles is nicely motivated in the introduction.\n- Walk profiles are introduced as a way of counting walks which is more comprehensive than simple shortest path distances, which can be trivial in directed graphs.\n- The authors show empirically that their method is superior when simple models are used on simple tasks. They also show that theoretically their PE is more expressive with respect to walk profiles.", "weaknesses": "- As the authors have discussed it in Section 4.3, the main limitation is the extra compute-time with larger $L$, induced namely by the calculation of large and numerous eigendecompositions. As shown in Section 5.4, the cost seems to grow linearly.\n- While it is described informally why walk profiles can be of interest, there is no theoretical justification of their use. Moreover, there are no connections to existing measures of modelsʼ expressivity (e.g., $k$-WL[1]).\n- It is not clear whether the authors have attempted any other methods to provide information about walk profiles. It is also not discussed whether other PEs [2, 3] also lack this ability to capture walk profiles.\n- In the experiments, while there is a fair share of ablations, standard GNN models can be added.\n- In the experimental section, it seems that the biggest gain was in the Experiment 5.1, where very simple models are used. As soon as the task gets more complex, a stronger model is invoked (SAT), and there the gains are much less evident if present at all.\n\nOverall, the paper also does not adequately answer the question it sets in its title. While the paper propose a positional encoding specific for directed graphs (and discusses its properties), it does not answer the question of what makes good positional encodings for directed graphs (and where the expressiveness is located compared to many potential alternatives).\n\n[1] Morris, C., Ritzert, M., Fey, M., Hamilton, WL., Lenssen, JE., Rattan, G., Grohe, M. “Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networksˮ (2019). https://arxiv.org/abs/1810.02244\n\n[2] Dwivedi, VP., Luu, AT., Laurent, T., Bengio, Y., Bresson, X. “Graph Neural Networks with Learnable Structural and Positional Representationsˮ (2022). https://arxiv.org/abs/2110.07875\n\n[3] Li, P., Wang, Y., Wang, H., Leskovec, J, “Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learningˮ (2020). https://arxiv.org/abs/2009.00142", "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": "bUQqnnXn2T", "reviewer": "Reviewer_eJc6", "summary": "This paper addresses the need for improved positional encodings (PEs) specifically designed for directed graphs. The authors introduce Multi-q Magnetic Laplacian PE, an enhancement of the Magnetic Laplacian PE that incorporates multiple potential values (q) to better capture directed graph structure. This Multi-q Mag-PE method is proposed to address limitations in existing PEs for directed graphs by generalizing walk-counting sequences into a walk profile. The paper provides theoretical support for Multi-q Mag-PE's effectiveness and evaluates it on multiple tasks, where it is shown to outperform traditional single-q PEs and other established methods.", "questions": "1.\tGiven that the computational complexity of directly using the walk profile is potentially manageable, could you elaborate further on why it wasn’t directly computed as features? Additionally, would an ablation of such a direct computation provide insight into how Multi-q PE compares in practical tasks?\n\n2.\tWould it be possible to apply this model to larger graphs by selectively reducing the number of q values?\n\n3.\tHave you considered validating the proposed method on a wider range of GNN or transformer backbone models? This could help generalize the results and illustrate broader applicability across different architectures.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1.\tMulti-q Mag-PE is a unique extension within the domain of GNN, specifically targeting the gap in encoding methods for directed graphs.\n\n2.\tThe paper establishes theoretical backing for Multi-q Mag-PE's ability to capture bidirectional walks and to accurately express walk profiles. This is an advancement over prior methods that fall short in representing such details in directed graphs.\n\n3.\tThrough extensive experiments across synthetic and real-world datasets, the paper demonstrates that Multi-q Mag-PE can outperform existing PEs, validating its effectiveness for both complex and directed graph tasks.", "weaknesses": "1.\tAlthough theoretically the Multi-q Mag-PE should allow near-perfect reconstruction of the walk profile, practical RMSE results are not close to zero. This discrepancy, acknowledged by the authors, indicates limitations in applying the theoretical model to real-world scenarios.\n\n2.\tThe Multi-q approach significantly increases computational demands due to multiple eigenvalue decompositions, which could challenge its scalability to larger graphs, especially those with millions of nodes or edges. Although the authors attempt to address this with runtime experiments and discuss potential optimizations, questions about the approach's feasibility for large-scale real-world applications remain.\n\n3.\tThe motivation for introducing the walk profile is not so clear. To be specific, heuristic definitions or possible theoretical explanations are needed to illustrate its effectiveness.\n\n4.\tThe improvements shown in real-world tasks were less pronounced than those on synthetic datasets, potentially due to the controlled nature of synthetic datasets, which may not represent the broader spectrum of real-world graph structures.", "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": "7yxtdMHSMX", "reviewer": "Reviewer_XPm4", "summary": "The paper introduces a novel positional encoding (PE) to enhance both message-passing GNNs and graph transformers, specifically, over directed graphs. Essentially, it extends the Magnetic Laplacian eigenvector-based PE by incorporating multiple potential factors. The evaluation is rather detailed containing both general performance comparisons and more elaborate analysis.\n\n(Please note: I did not check all theoretical details)", "questions": "- Sec. 5.4: what is the size of the data here?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The research is well motivated in the first sections of the paper\n- The theory is well-explained\n- It is nice that the approach is considered with both MPNNs and transformers\n- Also, the authors mention that this is the first work to propose the usage of complex PEs in a stable way. But I don't have the expertise to judge the relevance of this.", "weaknesses": "- The paper is rather densely written\n- Table 3 (which contains the more important, real-world data) is hard to parse and the differences seem oftentimes marginal (e.g., considering standard deviation)\n- Another suitable baseline on the DAG data would be DAG transformer [1]\n- There is a recent paper [2], which considers other realistic datasets, and maybe should be considered as competitor and be compared to \n\n[1] Luo et al. Transformers over Directed Acyclic Graphs, NeurIPS'23 https://openreview.net/pdf?id=g49s1N5nmO\n\n[2] Wang et al. Directed Graph Transformers, TMLR'24 https://openreview.net/pdf?id=otTFPjziiK", "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)