What Are Good Positional Encodings for Directed Graphs?

## Abstract

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 .

## 1 Introduction

Positional encoding (PE) (Vaswani et al., ; Su et al., ), which refers to the vectorized representation of token positions within a series of tokens, has been widely integrated into modern deep learning models across various data modalities, such as language modeling (Vaswani et al., ), vision tasks (Dosovitskiy et al., ), and graph learning (Dwivedi et al., ; Rampášek et al., ). The key advantage of PE is its ability to preserve crucial positional information of tokens, thereby complementing many downstream position-agnostic models like transformers (Yun et al., ) and graph neural networks (GNNs) (Li & Leskovec, ; Lim et al., ). 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) as PE (Vaswani et al., ). 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., ; Kreuzer et al., ; Beaini et al., ; Lim et al., ; Dwivedi et al., ; Rampášek et al., ; Li et al., ; Wang et al., ) 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., ; Wang et al., ; Lim et al., ). In particular, for undirected graphs, Laplacian positional encoding (Lap-PE) (Dwivedi et al., ; Kreuzer et al., ), 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., ; Chen et al., ; Lim et al., ; Huang et al., ). Lap-PE is powerful as it well preserves the information of the graph structure and can express various distance features defined on undirected graphs: examples such as diffusion distance (Coifman & Lafon, ; Bronstein et al., ; Wang et al., ), resistance distance (Xiao & Gutman, ) and biharmonic distance (Lipman et al., ; Kreuzer et al., ) are crucial structural features widely used in many graph learning and analysis tasks.

Despite the success of Lap-PEs for undirected graphs, many real-world applications involve directed graphs, such as circuit design, program analysis, neural architecture search, citation networks, and financial networks (Wang et al., ; Phothilimthana et al., ; Zhang et al., ; Allamanis, ; Zhou et al., ; Ren et al., ; Liu et al., ; Boginski et al., ; Wen et al., ). 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., ; Cummins et al., ). Understanding reachability, liveness, and common subexpressions requires analyzing whether walks between nodes have edges pointing in the same or reverse directions (Cummins et al., ; ). Logical reasoning often depends on identifying directed relationships, such as common successors ($X\leftarrow Y\to Z$) or predecessors ($X\rightarrow Y\leftarrow Z$)  (Qiu et al., ; Tian et al., ). Feed-forward loops that involve the two directed walks $X\rightarrow Z$ and $X\to Y\to Z$, are fundamental substructures in many biological systems (Mangan & Alon, ). Figure 1 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 on dealing with the asymmetry of Laplacian matrix, and propose, e.g., symmetrized Laplacian PE (Dwivedi et al., ), singular value decomposition PE (SVD-PE) (Hussain et al., ), Magnetic Laplacian PE (Mag-PE) (Geisler et al., ). 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 successors/predecessors, feed-forward loops and many more. Walk profile $\Phi(m,k)$ represents the number of length-$m$ bidirectional walks with exact $k$ 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-PE) 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 $q$ serves as the frequency of phase shift that encodes the counts of the walks with certain numbers of forward and backward edges, and using a certain number of different $q$’s 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., ). we introduce the first basis-invariant and stable neural architecture to handle complex eigenvectors. Specifically, we generalize the previous stable PE framework (Huang et al., ) from real to complex domain. The invariant property ensures that two equivalent complex eigenvectors (e.g., differ by a complex basis transformation) have the same representations. Moreover, the stability allows bridging Lap-PE (potential $q=0$) and Mag-PE (potential $q\neq 0$) smoothly. Our experiments show the key role of stable PE architecture to get a good generalization performance.
- •
Empirical results on synthetic datasets (distance prediction, sorting network satisfiability prediction) 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 categorized into three types: spatial GNNs, spectral GNNs, and transformers. Spatial GNNs are those who directly use graph topology as the inductive bias in model design, including bidirectional message passing neural networks (Jaume et al., ; Wen et al., ; Kollias et al., ) for general directed graphs and asynchronous message passing exclusively for directed acyclic graphs (Zhang et al., ; Dong et al., ; Thost & Chen, ). 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 Laplacian (Furutani et al., ; He et al., ; Fiorini et al., ; Zhang et al., ), Jordan decomposition (Singh et al., ), Perron eigenvectors (Ma et al., ),
motif Laplacian (Monti et al., ), Proximity matrix (Tong et al., ) and direct generalization by holomorphic functional calculus (Koke & Cremers, ). Finally, transformer-based models adopt the attention mechanism and their core ideas are to devise direction-aware positional encodings that better indicate graph structural information (Geisler et al., ; Hussain et al., ), which are reviewed next.

Positional encodings for undirected/directed graphs. Many works focus on designing positional encodings (PE) for undirected graphs, e.g., Laplacian-based PE (Dwivedi et al., ; Kreuzer et al., ; Beaini et al., ; Lim et al., ; Wang et al., ; Huang et al., ), random walk PE (Li et al., ; Dwivedi et al., ). See Rampášek et al. () for a survey and Black et al. () 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., ). Singular vectors of the asymmetric adjacency matrix have also been used as PE (Hussain et al., ), and so have the eigenvectors of the Magnetic Laplacian and bidirectional random walks (Geisler et al., ). For directed acyclic graphs, a depth-based positional encoding has been used (Luo et al., ).

## 3 Preliminaries

Basic notation. We denote the real domain by $\mathbb{R}$ and the complex domain by $\mathbb{C}$. Bold-face letters such as $\bm{A}$ are used to denote matrices. $\bm{A}^{\dagger}$ denotes the conjugate transpose of $\bm{A}$. We use $i=\sqrt{-1}$ to represent the imaginary unit and $\bm{I}$ for the identity matrix.

Directed graphs. Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a directed graph, where $\mathcal{V}$ is the node set and $\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the edge set. We call $u$ predecessor of $v$ if $(u,v)\in\mathcal{E}$ and call $u$ successor of $v$ if $(v,u)\in\mathcal{E}$. Let $\bm{A}\in\{0,1\}^{n\times n}$ be the adjacency matrix of a directed graph with $n$ nodes where $\bm{A}_{u,v}=1$ if $(u,v)\in\mathcal{E}$ and 0 0 otherwise. Denote $\bm{D}$ as the diagonal node degree matrix where $\bm{D}_{u,u}$ is the in-degree $d_{\text{in},u}$ plus the out-degree $d_{\text{out},u}$ of node $u$.

Graph Magnetic Laplacian. With a parameter $q\in\mathbb{R}$ called potential, the complex adjacency matrix $\bm{A}_{q}\in\mathbb{C}^{n\times n}$ is defined by $[\bm{A}_{q}]_{u,v}=\exp\{i2\pi q(\bm{A}_{u,v}-\bm{A}_{v,u})\}$ if $(u,v)\in\mathcal{E}$ or $(v,u)\in\mathcal{E}$, and 0 0 otherwise. $\bm{A}_{q}$ encodes edge directions via the phases of complex numbers $\exp\{\pm i2\pi q\}$. *Magnetic Laplacian*
$\bm{L}_{q}$ is correspondingly defined by $\bm{L}_{q}=\bm{I}-\bm{D}^{-1/2}\bm{A}_{q}\bm{D}^{-1/2}$.
For a weighted graph $\bm{A}\in\mathbb{R}^{n\times n}$, we can instead define $[\bm{A}_{q}]_{u,v}=(\bm{A}_{u,v}+\bm{A}_{v,u})\odot\exp\{i2\pi q(\bm{A}_{u,v}-
\bm{A}_{v,u})\}$ and $\bm{L}_{q}$ thereby. As a generalization of Laplacian to directed graphs, $\bm{L}_{q}$ is widely studied in applied mathematics, physics and network science for directed graph analysis (Shubin, ; Fanuel et al., ; ), and has been recently introduced as a promising way to build graph filters and deep learning models for directed graphs (Furutani et al., ; Geisler et al., ; Fiorini et al., ; He et al., ). *Symmetrized Laplacian*, i.e., Laplacian of the undirectized graph, is essentially a special case of Magnetic Laplacian with potential $q=0$ (no phase difference). Magnetic Laplacian $\bm{L}_{q}$ is hermitian since $\bm{L}_{q}^{\dagger}=\bm{L}_{q}$. This implies that there exists eigendecomposition $\bm{L}_{q}=\bm{V}\bm{\Lambda}\bm{V}^{\dagger}$, where $\bm{V}\in\mathbb{C}^{n\times n}$ is a unitary matrix, and $\bm{\Lambda}=\text{diag}(\bm{\lambda})$ constitutes of real eigenvalues $\bm{\lambda}\in\mathbb{R}^{n}$. The Magnetic Laplacian PE of node $u$ is defined by the corresponding row of $\bm{V}$, denoted by $z_{u}=[\bm{V}_{u,:}]^{\top}$.

## 4 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 as they can form many crucial motifs to enable the studies and analysis of directed graphs, such as feed-forward loops in biological systems and common successors/predecessors for logic reasoning.

### 4.1 Walk Profile: a 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 at different lengths $\mathcal{W}_{u,v}=(\bm{A}_{u,v},\bm{A}^{2}_{u,v},\bm{A}^{3}_{u,v},...,\bm{A}^{
L}_{u,v})$. In particular, suppose $\bm{A}\in\{0,1\}^{n\times n}$, then it is known that $\bm{A}^{\ell}_{u,v}$ counts the number of $\ell$-length walks from $u$ to $v$ and the shortest path distance can be found by $spd_{u,v}=\min\{\ell:\bm{A}^{\ell}_{u,v}>0\}$. For directed graphs, we can adopt the same description with $\bm{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=\{(1,3),(2,3)\}$, where node $1$ and $2$ share one common predecessor. However, as we cannot reach node $2$ from node $1$, the walk counting sequence from node $2$ to node $1$ is always zero. In this case this single-directional walk fail to capture the relation.

A key observation is that descriptions of directed motifs/patterns such as common successors/predecessors require knowing both the powers of $\bm{A}$ (walks via forward edges) and that of $\bm{A}^{\top}$ (walks via backward edges), and their combinations $\bm{A}\bm{A}^{\top}$ and $\bm{A}^{\top}\bm{A}$.
This observation motivates us to define walks in a bidirectional manner as follows.

###### Definition 4.1 (Bidirectional Walk) .

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be a directed graph. A bidirectional walk $w=(v_{0},v_{1},v_{2},...)$ is a sequence of nodes where every consecutive two nodes form either a forward edge $(v_{i},v_{i+1})\in\mathcal{E}$ or a backward edge $(v_{i+1},v_{i})\in\mathcal{E}$. The length of a 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*, a generalization of walk counting on directed graphs that retains more detailed structural information.

Figure: (a) Upper: Feed-forward loop. Lower: logical reasoning
Refer to caption: x1.png

###### Definition 4.2 (Walk Profile) .

Let $\mathcal{G}$ be a directed graph and $\bm{A}$ be the adjacency matrix. Given two nodes $u,v$, Walk profile $\Phi_{u,v}(\ell,k)$ is the number of length-$\ell$ bidirectional walks from $u$ to $v$ that contains exact $k$ forward edges and $\ell-k$ backward edges.

For example, $\Phi_{u,v}(1,1)=\bm{A}_{u,v}$ represents the connectivity from $u$ to $v$; $\Phi_{u,v}(2,1)=(\bm{A}\bm{A}^{\top})_{u,v}+(\bm{A}^{\top}\bm{A})_{u,v}$, which counts the number $2$-length walk with one forward edge and one backward edge, which corresponds to the number of common successors or predecessors. One can also compute the shortest/longest path distance using the walk profile. See Figure 1(b) for illustrations. Note that the definition of walk profile can be generalized to weighted graphs by replacing adjacency matrix with weight matrix $\bm{A}\in\mathbb{R}^{n\times n}$.

###### Remark 4.1 .

Let $\mathcal{G}$ be a directed graph with Adjacency matrix $\bm{A}\in\{0,1\}^{n\times n}$, and consider two nodes $u,v$. The shortest path distance can be computed via
$spd_{u,v}=\min\{\ell\in\mathbb{Z}:\Phi_{u,v}(\ell,\ell)>0\}.$
Furthermore, if $\mathcal{G}$ is acyclic, then longest path distance is
$lpd_{u,v}=\max\{\ell\in\mathbb{Z}:\Phi_{u,v}(\ell,\ell)>0\}.$

###### Definition 4.1 (Bidirectional Walk) .

###### Definition 4.2 (Walk Profile) .

###### Remark 4.1 .

### 4.2 The Limitations of Existing PEs to Express Walk Profile

Intuitively, a good PE can characterize certain notations of distances between nodes $u$ and $v$ based on PEs $z_{u},z_{v}$. Now let us study the power of the existing PEs for directed graphs via the notion of walk profile. Formally, we say a PE method is expressive if it can determine $\Phi_{u,v}$ based on $z_{u}$ and $z_{v}$.

Mag-PE. Let $\bm{L}_{q}=\bm{I}-\bm{D}^{-1/2}\bm{A}_{q}\bm{D}^{-1/2}$ be Magnetic Laplacian with potential $q$. Since Magnetic graph $\bm{A}_{q}$ faithfully represents the directed structure of the graph, one may conjecture that eigenvalues $\lambda$ and eigenvectors $z_{u},z_{v}$ should be able to compute the walk profile. However, it turns out that it is impossible to recover $\Phi_{u,v}(m,k)$ from them, as shown in the following Theorem 4.2.

[]
Fix a $q\in\mathbb{R}$. There exist graphs $\mathcal{G},\mathcal{G}^{\prime}$ with adjacency matrices $\bm{A},\bm{A}^{\prime}\in\mathbb{R}^{n\times n}$, and nodes $u,v\in V_{\mathcal{G}}$ and $u^{\prime},v^{\prime}\in V_{\mathcal{G}^{\prime}}$, such that Mag-PE $(\lambda,z_{u},z_{v})=(\lambda^{\prime},z_{u^{\prime}}^{\prime},z_{v^{\prime}}
^{\prime})$, but $\Phi_{u,v}(m,k)\neq\Phi_{u^{\prime},v^{\prime}}^{\prime}(m,k)$ for some $m,k$.

###### Remark 4.2 .

From the formal proof of Theorem 4.2 (see Appendix A) we can also show that Mag-PE of node $u,v$ is unable to compute shortest path distance $spd_{u,v}$. More insights into why single $q$ may fail are to be discussed after the proof sketch of Theorem 4.3. 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 (Hussain et al., ). That is, $\bm{A}=\bm{U}\text{diag}(\bm{\sigma})\bm{W}^{\top}$ and define SVD-PE $z_{u}:=(\bm{U}_{u,:},\bm{W}_{u,:})^{\top}$. Here, we provide an intuition on why SVD-PE is hard to construct the walk profile. Recall that in eigen-decomposition, a power series of $\bm{A}$ can be computed via power series of eigenvalues, i.e., $f(\bm{A})=\sum_{p}a_{p}\bm{A}^{p}=\bm{V}\text{diag}[f(\bm{\lambda})]\bm{V}^{\top}$, which explains that the distance in the form of $f(\bm{A})_{u,v}$ can be expressed by $\langle\bm{V}_{u,:},f(\bm{\lambda})\odot\bm{V}_{v,:}\rangle$. In contrast, this property does not hold for SVD. For instance, $\bm{A}^{2}=\bm{U}\text{diag}(\sigma)\bm{W}^{\top}\bm{U}\text{diag}(\sigma)\bm{
W}^{\top}\neq\bm{U}\text{diag}(\sigma^{2})\bm{W}^{\top}$. As a result, computation of $[\bm{A}^{2}]_{u,v}$ (the walk profile more broadly) requires not only SVD-PEs $z_{u},z_{v}$ but also $z_{w}$ for some $w\in\mathcal{V}/\{u,v\}$.

###### Remark 4.2 .

### 4.3 Magnetic Laplacian with Multiple Potentials q 𝑞 q italic_q

The limited expressivity of existing PE methods motivates us to design a 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 of the following cases - (1) node $v$ is not reachable from $u$ - v.s. - (2) $u\rightarrow u_{1}\rightarrow v$ and $u\leftarrow u_{2}\leftarrow v$ - yield the same $[\bm{L}_{q}^{\ell}]_{u,v}=0$ for any integer $\ell$. However, the numbers of length-$\ell$ walks between $u$ and $v$ are different. The potential $q$ 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 $\vec{q}=(q_{1},...,q_{Q})$ is going to construct $Q$ many Magnetic Laplacian $\bm{L}_{q_{1}},...,\bm{L}_{q_{Q}}$, and Multi-q Mag-PE is defined by concatenation of multiple Mag-PE:

$$ $z^{\vec{q}}_{u}=([\bm{V}_{q_{1}}]_{u,:},...,[\bm{V}_{q_{Q}}]_{u,:})^{\top},$ (1) $$

where $\bm{V}_{q_{i}}$ is the eigenvectors of $\bm{L}_{q_{i}}$.
Intuitively, different frequencies (potential $q$) 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 4.3 demonstrates that this simple extension can be rather effective: with a proper number of $q$’s, one is able to exactly compute the walk profile of the desired length. Section 5.1 also provides extensive empirical justifications.

[]
Let $L$ be a positive integer and let $Q=\lceil\frac{L}{2}\rceil+1$, where $\lceil\cdot\rceil$ means ceiling. If we let $\vec{q}=(q_{1},q_{2},...,q_{Q})$ with $Q$ distinct $q$’s and $q_{1},...,q_{L+1}\in[0,\frac{1}{4})$, then for all $\ell\leq L$ and $k\leq\ell$, walk profile $\Phi_{u,v}(\ell,k)$ can be exactly computed from $(\bm{\lambda}^{\vec{q}},z^{\vec{q}}_{u},z^{\vec{q}}_{v})$, where $\bm{\lambda}^{\vec{q}},z^{\vec{q}}$ are concatenation of eigenvalues/eigenvectors of different $q$ from $\vec{q}$.

###### Proof Sketch.

Fix two nodes $u,v$. As from $(\bm{\lambda}^{\vec{q}},z^{\vec{q}}_{u},z^{\vec{q}}_{v})$, we can construct $[\bm{A}_{q}^{\ell}]_{u,v}$ for any $q$. So the question becomes how we can determine the walk profile $\Phi_{u,v}(\cdot,\cdot)$ from $[\bm{A}_{q}^{\ell}]_{u,v}$.
By the definition, one can find the following key formula that relates walk profile with $\bm{A}_{q}^{\ell}$: For any $q$,

$$ $[\bm{A}^{\ell}_{q}]_{u,v}=e^{-i2\pi q\ell}\sum_{k=0}^{\ell}\Phi_{u,v}(\ell,k)e ^{i4\pi qk}.$ (2) $$

Fix the integer $L$ and consider a length-$Q$ list of $q$ denoted by $\vec{q}=(q_{1},...,q_{Q})$. Then, by Eq. 2, given $[\bm{A}^{\ell}_{q_{1}}]_{u,v},...,[\bm{A}^{\ell}_{q_{Q}}]_{u,v}$ for all $l\leq L$, solving $\Phi_{u,v}(\ell,k)$ is equivalent to solving a linear system $\bm{F}\bm{\Phi}=\bm{Y}$, where $\bm{F}\in\mathbb{C}^{Q\times(L+1)}$, $\bm{\Phi}\in\mathbb{R}^{(L+1)\times L}$, $\bm{Y}\in\mathbb{C}^{Q\times L}$ and $\bm{F}_{j,m}=\exp\{i4\pi q_{j}m\}$, $\bm{\Phi}_{j,m}=\Phi_{u,v}(m,j)$ (equals zero if $j>m$), $\bm{Y}_{j,m}=[\bm{A}^{m}_{q_{j}}]_{u,v}\cdot e^{i2\pi q_{j}m}$. In order to make the linear system $\bm{F}$ well-posed for uniquely solving the walk profile $\bm{\Phi}$ from $\bm{Y}$, it generally requires $\bm{F}$ to have $Q=L+1$ distinct rows, i.e., $e^{i4\pi q_{i}}\neq e^{i4\pi q_{j}}$ for any $i\neq j$, such that Fourier matrix $\bm{F}$ becomes full-rank. Fortunately, as the unknowns $\bm{\Phi}$ lies in real space, the number of rows $Q$ can be reduced to $\lceil L/2\rceil+1$ thanks to the symmetry of Fourier coefficients $\bm{Y}$ of real $\bm{\Phi}$. As a result, we can choose $Q=\lceil L/2\rceil+1$ many distinct qs with $q_{i}\in[0,\frac{1}{4})$, by which we can construct a full-rank system to solve $\bm{\Phi}$.
∎

The proof provides several insights: (a) determining the walk profile from the powers of $\bm{A}_{q}$ of a single $q$ is ill-posed; (b) in contrast, using $\lceil L/2\rceil+1$ many $q$’s simultaneously makes the problem well-posed and allows it to uniquely determine the walk profile of length $\leq L$. The number of $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 to the values of multiple $q$’s. In practice, we may choose evenly-spaced $\vec{q}=(\frac{0}{2(L+1)},...,\frac{\lceil L/2\rceil+1}{2(L+1)})$ where $\bm{F}$ indicates discrete Fourier transform, or randomly sampled $q_{i}\in[0,\frac{1}{4})$ where $\bm{F}$ is non-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 a 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 a runtime comparison with various numbers of $q$’s, see Sec. 5.4. Typically, the actual runtime of $Q=5$ is about twice of the runtime when $Q=1$. We also discuss the pros and cons of using Multi-q Mag-PE v.s. directly using walk profiles as injected features in Appendix F.

###### Proof Sketch.

### 4.4 The First Basis-invariant/stable Neural Architecture for Complex Eigenvectors

Figure: 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.
Refer to caption: x3.png

Recent studies have shown that Lap-PE has the issues of basis ambiguity and instability (Wang et al., ; Lim et al., ; Huang et al., ; Black et al., ). That is, because eigen-decomposition is not unique (i.e., $\bm{L}=\bm{V}\bm{\Lambda}\bm{V}^{\top}=(\bm{V}\bm{Q})\bm{\Lambda}(\bm{V}\bm{Q}
)^{\top}$ for some orthogonal matrix $\bm{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: $\bm{L}_{q}=\bm{V}\bm{\Lambda}\bm{V}^{\dagger}=(\bm{V}\bm{Q})\bm{\Lambda}(\bm{V
}\bm{Q})^{\dagger}$ for some unitary matrix $\bm{Q}\in\mathbb{C}^{n\times n}$. For Multi-q Mag-PE, even without duplicated eigenvalues, eigenvectors associated with each $q$ exhibit their own symmetry (if $v$ is an eigenvector, $ve^{i\theta}$ for any $\theta\in(0,2\pi)$ is also an eigenvector), exacerbating the ambiguity and stability issues even further.

To address this problem, we aim to generalize the previous stable PE frameworks, PEG (Wang et al., ) and SPE (Huang et al., ), to handle complex eigenvectors. Our framework will process PEs into stable representations and use them as augmented node/edge features in the backbone model. We first consider Mag-PE of a single $q$ and then extend it. Specifically, let $\phi^{\text{node}}_{\ell},\phi^{\text{edge}}_{\ell}:\mathbb{R}^{d}\to\mathbb{R
}^{d}$ be permutation-equivariant function w.r.t. $d$-dim axis (i.e., equivariant to permutation of eigenvalues), we can construct node-level stable PE $z_{\text{node}}\in\mathbb{R}^{n\times d}$ and/or edge-level stable PE $z_{\text{edge}}\in\mathbb{R}^{n\times n\times d}$:

$$ $\begin{split}z_{\text{node}}=\rho_{\text{node}}(&\text{Re}\{\bm{V}\text{diag}( \phi^{\text{node}}_{1}(\lambda))\bm{V}^{\dagger}\},...,\text{Re}\{\bm{V}\text{ diag}(\{\phi^{\text{node}}_{m}(\lambda))\bm{V}^{\dagger}\},\\ &\text{Im}\{\bm{V}\text{diag}(\phi^{\text{node}}_{1}(\lambda))\bm{V}^{\dagger} \},...,\text{Im}\{\bm{V}\text{diag}(\{\phi^{\text{node}}_{m}(\lambda))\bm{V}^{ \dagger}\}),\end{split}$ (3) $$

$$ $\begin{split}z_{\text{edge}}=\rho_{\text{edge}}(&\text{Re}\{\bm{V}\text{diag}( \phi^{\text{edge}}_{1}(\lambda))\bm{V}^{\dagger}\},...,\text{Re}\{\bm{V}\text{ diag}(\{\phi^{\text{edge}}_{m}(\lambda))\bm{V}^{\dagger}\},\\ &\text{Im}\{\bm{V}\text{diag}(\phi^{\text{edge}}_{1}(\lambda))\bm{V}^{\dagger} \},...,\text{Im}\{\bm{V}\text{diag}(\{\phi^{\text{edge}}_{m}(\lambda))\bm{V}^{ \dagger}\}),\end{split}$ (4) $$

where $\bm{V},\bm{\lambda}$ are the eigenvectors and eigenvalues of Magnetic Laplacian with a certain $q$, $\text{Re}\{\cdot\},\text{Im}\{\cdot\}$ means taking the real and imaginary parts, respectively, and $\rho_{\text{node}}:\mathbb{R}^{n\times n\times 2m}\to\mathbb{R}^{n\times p}$ and $\rho_{\text{edge}}:\mathbb{R}^{n\times n\times 2m}\to\mathbb{R}^{n\times n
\times p}$ are permutation equivariant function w.r.t. $n$-dim axis (i.e., equivariant to permutation of node indices). Afterwards, $z_{\text{node}}$ will be concatenated with node features, and $z_{\text{edge}}$ 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, if the backbone model is a GNN, only a portion of (sparse) entries $[z_{\text{edge}}]_{u,v}$, $(u,v)\in\mathcal{E}$ need to be computed. For the multi-$q$ case, we apply the same $\phi_{\ell}$ and $\rho$ 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. (). Moreover,
it can be shown that $z_{\text{node}},z_{\text{edge}}$ are continuous in the choice of $q$ due to the stable structure. Such continuity naturally unifies Lap-PE and Mag-PE, because symmetrized Laplacian $\bm{L}_{s}$ is a special case of Magnetic Laplacian $\bm{L}_{q}$ when $q\rightarrow 0$.

## 5 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 distances/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?

In our experiments, we mainly consider three ways of processing PEs: (1) Naïve: directly concatenates raw PEs with node features; (2) SignNet (Lim et al., ): makes PEs sign invariant. We adopt the same pipeline as in (Geisler et al., ), Figure G.1; (3) SPE (Eqs. 3,4): we follow (Huang et al., ), and use element-wise MLPs as $\phi_{1},...,\phi_{m}$, GIN (Xu et al., ) as $\rho_{\text{node}}$ and MLPs as $\rho_{\text{edge}}$. 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. () and generate Erdős–Rényi random graphs. Specifically, we sample regular directed graphs with average node degree drawn from $\{1,1.5,2\}$, or directed acyclic graphs with average node degree from $\{1,1.5,2,2.5,3\}$. In both cases, there are 400,000 samples for training and validation (graph size from 16 to 63, training:validation=95:5), 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-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 are included for training and test. For the walk profile, we choose to 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 $\bm{A}$ in walk profiles replaced by random walk $\bm{D}_{\text{total}}^{-1}\bm{A}$, as the latter is consistent with the normalized Laplacian $\bm{I}-\bm{D}_{\text{total}}^{-1/2}\bm{A}\bm{D}_{\text{total}}^{-1/2}$ we use in practice. See Appendix G for discussions.

Models. To show the power of pure PEs, we take PEs $z_{u},z_{v}$ of node $u,v$ to predict the distance $d_{u,v}$ between $u,v$. We consider three ways of processing PEs: (1) naïve concatenation: $\text{MLP}([z_{u},z_{v}])$; (2) SignNet-based: $\text{MLP}(\text{SignNet}(z_{u}),\text{SignNet}(z_{v}))$; (3) edge-SPE-based: $\text{MLP}([z_{\text{edge}}]_{u,v})$ where $z_{\text{edge}}$ is defined in Eq. 4. For Multi-q Magnetic Laplacian PE, we choose $\vec{q}=(0,\frac{1}{2L},...,\frac{L-1}{2L})$ where $L=5$ for predicting walk profile, $L=10$ for predicting shortest/longest path distances on directed acyclic graphs and $L=15$ for predicting shortest/longest path distances on regular directed graphs. For single-q Mag-PE, we tune $q$ from 0 0 to $0.5$, and we report both the result of $q=0.1$ and the tuned best $q$. It turns out the performance of single-q Mag-PE in this task is not sensitive to the value of $q$ as long as not being too large.

Results. Table 1 indicates several conclusions. (1) Multi-q Mag-PE constantly outperforms other PE methods regardless of how we 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 eigenvectors. 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., ; Lim et al., ). 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 naïve 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 $\vec{q}$. We can show that the joint use of different $q$’s is indeed necessary, and it is constantly better than using the single best $q$. The hyper-parameter search of the best $q$ for single-q Magnetic Laplacian for different tasks can be found in Appendix C.

Table: Table 1: Test RMSE results over 3 random seeds for node-pair distance prediction.

Robustness of multiple $q$ values. As implied by Theorem 4.3, the expressivity to compute walk profile is robust to the choice of multiple $q$ values. To verify this, Multi-q Mag-PE with a randomly sampled $\vec{q}$ (draw each $q$ from uniform distribution) is implemented. See details in Appendix E. Our results show that random $\vec{q}$ sometimes achieves even better prediction than evenly-spaced $\vec{q}$.

Figure: Table 2: Test F1 scores over 5 random seeds for sorting network satisfiability.
Refer to caption: x4.png

### 5.2 Sorting Network Satisfiability

Sorting network (Knuth, ) is a comparison-based algorithm designed to perform sorting on a fixed number of variables. Each sorting network consists of a sequence of operations $v_{i},v_{j}=\emph{sorted}(v_{i},v_{j})$ 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 a 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. (). 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., ) as our base model. PEs are either naively concatenated into node features, or using SignNet before concatenation, or concatenated both into node features and attention weights using SPEs Eqs.3 and 4. For single-q Magnetic Laplacian PE, we tune $q$ from $\frac{1}{20\cdot d_{G}}$ to $\frac{5}{20\cdot d_{G}}$, where where $d_{G}=\max(\min(m,n),1)$, $m$ is the number of directed edges and $n$ is the number of nodes. We find $q=\frac{5}{20\cdot d_{G}}$ gives the best results, which is the same $q$ as in Geisler et al. (). For multi-q Mag-PE, we choose $\vec{q}=(\frac{1}{20\cdot d_{G}},...,\frac{5}{20\cdot d_{G}})$.

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 3 additionally illustrates the test F1 on samples with respect to individual sorting network lengths. Note that although single-q Mag-PE and multi-q Mag-PE perform equally well on length=13 samples, the single-q one generalizes worse on longer-length sorting networks. In contrast, Multi-q Mag-PE has nearly the same generalization performance as the number of variables to sort increases.

**Table 3: Test results (RMSE for Gain/BW/PM, MSE for DSP/LUT) for Open Circuit Benchmark and High-level Synthesis. Bold denotes the best result for each base model, and Bold^† for the best result among all base models.**
| Base Model | PE method | PE processing | Gain | BW | PM | DSP | LUT |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Undirected-GIN | Lap | SignNet | $0.430_{\pm 0.009}$ | $4.712_{\pm 0.134}$ | $1.127_{\pm 0.007}$ | $2.665_{\pm 0.184}$ | $2.025_{\pm 0.057}$ |
| SPE | $0.416_{\pm 0.021}$ | $4.321_{\pm 0.084}$ | $1.127_{\pm 0.020}$ | $2.662_{\pm 0.187}$ | $\bm{1.925_{\pm 0.059}}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.426_{\pm 0.009}$ | $4.670_{\pm 0.113}$ | $1.116_{\pm 0.009}$ | $2.673_{\pm 0.090}$ | $2.027_{\pm 0.091}$ |  |
| SPE | $0.405_{\pm 0.016}$ | $4.305_{\pm 0.092}$ | $1.121_{\pm 0.018}$ | $2.666_{\pm 0.190}$ | $2.024_{\pm 0.068}$ |  |  |
| Maglap-1q (best q) | SPE | $0.398_{\pm 0.025}$ | $4.281_{\pm 0.085}$ | $\bm{1.113_{\pm 0.022}}$ | $2.614_{\pm 0.098}$ | $2.010_{\pm 0.082}$ |  |
| Maglap-Multi-q | SignNet | $0.421_{\pm 0.015}$ | $4.743_{\pm 0.215}$ | $1.126_{\pm 0.011}$ | $2.665_{\pm 0.111}$ | $2.025_{\pm 0.076}$ |  |
| SPE | $\bm{0.389_{\pm 0.017}}$ | $\bm{4.175_{\pm 0.115}}$ | $1.137_{\pm 0.004}$ | $\bm{2.582_{\pm 0.133}}$ | $1.976_{\pm 0.089}$ |  |  |
| Bidirected-GIN | Lap | SignNet | $0.382_{\pm 0.008}$ | $4.371_{\pm 0.171}$ | $1.127_{\pm 0.021}$ | $2.256_{\pm 0.109}$ | $1.806_{\pm 0.096}$ |
| SPE | $0.391_{\pm 0.007}$ | $4.153_{\pm 0.160}$ | $1.135_{\pm 0.035}$ | $2.267_{\pm 0.126}$ | $1.786_{\pm 0.072}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.388_{\pm 0.012}$ | $4.351_{\pm 0.132}$ | $1.131_{\pm 0.012}$ | $2.304_{\pm 0.143}$ | $1.882_{\pm 0.085}$ |  |
| SPE | $0.384_{\pm 0.008}$ | $4.152_{\pm 0.056}$ | $1.123_{\pm 0.026}$ | $2.344_{\pm 0.134}$ | $1.830_{\pm 0.116}$ |  |  |
| Maglap-1q (best q) | SPE | $0.383_{\pm 0.002}$ | $4.113_{\pm 0.052}$ | $\bm{1.099_{\pm 0.020}}$ | $2.256_{\pm 0.144}$ | $1.768_{\pm 0.090}$ |  |
| Maglap-Multi-q | SignNet | $0.381_{\pm 0.008}$ | $4.443_{\pm 0.116}$ | $1.119_{\pm 0.016}$ | $2.212_{\pm 0.116}$ | $1.791_{\pm 0.091}$ |  |
| SPE | $\bm{0.371_{\pm 0.008}}$ | $\bm{4.051_{\pm 0.139}}$ | $1.116_{\pm 0.012}$ | $\bm{2.207^{\dagger}_{\pm 0.185}}$ | $\bm{1.735^{\dagger}_{\pm 0.096}}$ |  |  |
| SAT (undirected-GIN) | Lap | SignNet | $0.368_{\pm 0.022}$ | $4.085_{\pm 0.189}$ | $1.038_{\pm 0.016}$ | $3.103_{\pm 0.101}$ | $2.223_{\pm 0.175}$ |
| SPE | $0.375_{\pm 0.016}$ | $4.180_{\pm 0.093}$ | $1.065_{\pm 0.034}$ | $3.167_{\pm 0.193}$ | $2.425_{\pm 0.168}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.382_{\pm 0.009}$ | $4.143_{\pm 0.181}$ | $1.073_{\pm 0.021}$ | $3.087_{\pm 0.183}$ | $2.214_{\pm 0.150}$ |  |
| SPE | $0.366_{\pm 0.003}$ | $4.081_{\pm 0.071}$ | $1.089_{\pm 0.023}$ | $3.206_{\pm 0.197}$ | $2.362_{\pm 0.154}$ |  |  |
| Maglap-1q (best q) | SPE | $0.361_{\pm 0.016}$ | $\bm{4.014_{\pm 0.068}}$ | $1.057_{\pm 0.036}$ | $3.101_{\pm 0.176}$ | $2.362_{\pm 0.154}$ |  |
| Maglap-Multi-q | SignNet | $0.368_{\pm 0.020}$ | $4.044_{\pm 0.090}$ | $1.066_{\pm 0.028}$ | $3.121_{\pm 0.143}$ | $\bm{2.207_{\pm 0.113}}$ |  |
| SPE | $\bm{0.350^{\dagger}_{\pm 0.004}}$ | $4.044_{\pm 0.153}$ | $\bm{1.035^{\dagger}_{\pm 0.025}}$ | $\bm{3.076_{\pm 0.240}}$ | $2.333_{\pm 0.147}$ |  |  |
| SAT (bidirected-GIN) | Lap | SignNet | $0.384_{\pm 0.025}$ | $3.949_{\pm 0.125}$ | $1.069_{\pm 0.029}$ | $\bm{2.569_{\pm 0.116}}$ | $2.048_{\pm 0.088}$ |
| SPE | $0.368_{\pm 0.022}$ | $4.024_{\pm 0.106}$ | $1.046_{\pm 0.021}$ | $2.713_{\pm 0.135}$ | $2.173_{\pm 0.107}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.384_{\pm 0.015}$ | $4.023_{\pm 0.032}$ | $1.055_{\pm 0.028}$ | $2.616_{\pm 0.120}$ | $2.054_{\pm 0.127}$ |  |
| SPE | $0.364_{\pm 0.012}$ | $3.996_{\pm 0.178}$ | $1.074_{\pm 0.030}$ | $2.687_{\pm 0.209}$ | $2.192_{\pm 0.135}$ |  |  |
| Maglap-1q (best q) | SPE | $\bm{0.360_{\pm 0.009}}$ | $3.960_{\pm 0.060}$ | $1.062_{\pm 0.024}$ | $2.657_{\pm 0.128}$ | $2.107_{\pm 0.135}$ |  |
| Maglap-Multi-q | SignNet | $0.420_{\pm 0.035}$ | $4.022_{\pm 0.128}$ | $1.089_{\pm 0.046}$ | $2.741_{\pm 0.110}$ | $\bm{2.045_{\pm 0.079}}$ |  |
| SPE | $\bm{0.359_{\pm 0.008}}$ | $\bm{3.930^{\dagger}_{\pm 0.069}}$ | $\bm{1.045_{\pm 0.012}}$ | $2.616_{\pm 0.151}$ | $2.082_{\pm 0.099}$ |  |  |
|  |  |  |  |  |  |  |  |

### 5.3 Circuit Property Prediction

We evaluate different PE methods on real-world Circuit Property Prediction tasks.

Open Circuit Benchmark. Open Circuit Benchmark (Dong et al., ) contains 10,000 operational amplifiers circuits as directed graphs and the task is to 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-aware 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.

High-level Synthesis. The HLS dataset (Wu et al., ) collects $18,750$ intermediate representation (IR) graphs of C/C++ code after front-end compilation (Alfred et al., ). It provides post-implementation performance metrics on FPGA devices as labels, which are obtained after hours of synthesis using the Vitis HLS tool () and implementation with Vivado (). The task is 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., ) 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., ; Thost & Chen, ; Wen et al., ). The state-of-the-art graph transformer SAT (Chen et al., ) is also adopted, whose GNN extractor is undirected-GIN or bidirected-GIN as mentioned for self-attention computation. PEs are processed and then concatenated with node features using SignNet or with node and edge features using SPE (Eqs. 3, 4). We generally choose $\vec{q}=(1,2,...,10)/100$ or $\vec{q}=(1,2,...,5)/100$ for Multi-q Mag-PE (see Appendix B for specific $q$ for each tasks). For single-q Magnetic Laplacian, we report $q=0.01$ as 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 $q$.

Results. Table 3 shows the test RMSE (5 random seeds) on Open Circuit Benchmark (Gain, BW, PM) and the test MSE (10 random seeds) on high-level synthesis (DSP, LUT). Notably, Multi-q Mag-PE with Stable PE framework achieves most of the best results for 5 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 $q$, as shown in Figure 4. We can see that the training time of even 10 $q$ is generally about 1.5 to 3 times the training time of one single $q$. The preprocessing time is not a concern as they are negligible compared to total training time for hundreds of epochs in our experiments. See detailed setup at Appendix D.

Figure: Figure 4: Runtime of preprocessing (left), training (middle) and inference (right) on three datasets. The shown runtime of distance dataset is 10 times the actual ones for better illustration.
Refer to caption: x5.png

## 6 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-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.

#### Acknowledgments

This research is supported by the NSF awards PHY-2117997, IIS-2239565, CFF-2402816, IIS-2428777 and JPMorgan Faculty award.

## Appendix A Deferred Proofs

### A.1 Proof of Theorem 4.2

See 4.2

###### Proof.

Fix a $q\in\mathbb{R}$ and two nodes $u,v$. Pick and fix anther node $u_{0}$ that is not $u,v$. Let us define a graph $\bm{A}\in\mathbb{R}^{n\times n}$ such that $\text{diag}(\bm{A})=0$, and for all $w,r\in\mathcal{V}$, $\bm{A}_{u_{0},w}=\bm{A}_{u_{0},r}=1$ and $\bm{A}_{w,r}=0$ otherwise. for all nodes $w,r$. Note that complex adjacency matrix $\bm{A}_{q}=(\bm{A}+\bm{A}^{\top})\odot\exp\{i2\pi q(\bm{A}-\bm{A}^{\top})\}$ uniquely determines $\bm{A}$ by the relation
$\bm{A}=\frac{1}{2}|\bm{A}_{q}|+\frac{1}{2}\frac{\angle\bm{A}_{q}}{2\pi q},$
where $|\cdot|,\angle$ denote amplitude and phase of complex numbers.

Now let us construct $\bm{A}^{\prime}$ by constructing $\bm{A}_{q}^{\prime}$ first. Suppose Hermitian $\bm{A}_{q}$ has eigenvalue decomposition $[\bm{A}_{q}]_{w,r}=\sum_{k}\lambda_{k}z_{w,k}z_{r,k}^{*}$. Let us define another group of eigenvalues $\lambda^{\prime}$ and eigenvectors (PE) $z^{\prime}$ via:

$$ $\lambda^{\prime}=\lambda,\quad z^{\prime}_{w,:}=\left\{\begin{aligned} z_{w,:} ,\quad\text{if }w\neq u_{0}\\ e^{i\theta}z_{u_{0},:}\quad w=u_{0}\end{aligned}\right.,$ (5) $$

that is, $\lambda^{\prime},z^{\prime}$ shares the exact same spectrum as $\lambda,z$, except that $z^{\prime}_{u_{0},:}=\exp(i\theta)\cdot z_{u_{0},:}$. It is easy to verify that $z^{\prime}$ is indeed eigenvectors by their orthonormality, so we can construct Hermitian $\bm{A}_{q}^{\prime}$ as $[\bm{A}_{q}^{\prime}]_{w,r}=\sum_{k}\lambda^{\prime}_{k}z^{\prime}_{w,k}z^{
\prime*}_{r,k}$. From this construction, we shall see that $(\lambda,z_{u},z_{v})=(\lambda^{\prime},z_{u}^{\prime},z_{v}^{\prime})$.

On the other hand, let us examine the walk profile. For any two nodes $w,r$, we have

$$ $[\bm{A}^{\prime}_{q}]_{w,r}=\sum_{k}\lambda^{\prime}_{k}z^{\prime}_{w,k}z^{ \prime*}_{r,k}=\left\{\begin{aligned} {}_{w,r},\quad\text{if }w,r\neq u_{0}\\ e^{-i\theta}[\bm{A}_{q}]_{w,u_{0}},\quad\text{if }w\neq u_{0},r=u_{0}\\ e^{i\theta}[\bm{A}_{q}]_{u_{0},r},\quad\text{if }w=u_{0},r\neq u_{0}\end{ aligned}\right.$ (6) $$

This determines $\bm{A}^{\prime}$, which reads

$$ $[\bm{A}^{\prime}]_{w,r}=\frac{1}{2}|[\bm{A}^{\prime}_{q}]_{w,r}|+\frac{1}{2} \frac{\angle[\bm{A}^{\prime}_{q}]_{w,r}}{2\pi q}=\left\{\begin{aligned} {}_{w, r},\quad\text{if }w,r\neq u_{0}\\ \frac{1}{2}\cdot\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture \makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}},\quad\text{if }w\neq u_{0},r=u_{0}\\ \frac{1}{2}\cdot\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture \makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}},\quad\text{if }w=u_{0},r\neq u_{0}\end{ aligned}\right.,$ (7) $$

where

$$ $\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{ \hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}=\frac{1}{2}|[\bm{A}_{q}]_{w,u_{0}}\exp\{-i \theta\}|+\frac{1}{2}\frac{\angle[\bm{A}^{\prime}_{q}]_{w,u_{0}}\exp\{-i\theta \}}{2\pi q}=\bm{A}_{w,u_{0}}-\frac{\theta}{4\pi q}=-\frac{\theta}{4\pi q},$ (8) $$

and

$$ $\leavevmode\hbox to11.37pt{\vbox to11.37pt{\pgfpicture\makeatletter\hbox{ \hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke { }\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0} \pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ } \pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}=\frac{1}{2}|[\bm{A}_{q}]_{u_{0},r}\exp\{-i \theta\}|+\frac{1}{2}\frac{\angle[\bm{A}^{\prime}_{q}]_{u_{0},r}\exp\{-i\theta \}}{2\pi q}=\bm{A}_{u_{0},r}+\frac{\theta}{4\pi q}=1+\frac{\theta}{4\pi q}.$ (9) $$

Now we can see that for the fixed $u,v$, we have

$$ $\begin{split}\Phi_{u,v}(2,2)-\Phi^{\prime}_{u,v}(2,2)&=\bm{A}^{2}_{u,v}-\bm{A} ^{2}_{u,v}=\sum_{w}\bm{A}_{u,w}\bm{A}_{w,v}-\bm{A}^{\prime}_{u,w}\bm{A}^{ \prime}_{w,v}\\ &=\bm{A}_{u,u_{0}}\bm{A}_{u_{0},v}-\bm{A}^{\prime}_{u,u_{0}}\bm{A}^{\prime}_{u _{0},v}=0\cdot 1-\frac{1}{4}\leavevmode\hbox to11.37pt{\vbox to11.37pt{ \pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt{ \pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\cdot\leavevmode\hbox to11.37pt{\vbox to11.37 pt{\pgfpicture\makeatletter\hbox{\hskip 5.68657pt\lower-5.68657pt\hbox to0.0pt {\pgfsys@beginscope\pgfsys@invoke{ }\definecolor{pgfstrokecolor}{rgb}{0,0,0} \pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ }\pgfsys@color@rgb@fill{0}{0} {0}\pgfsys@invoke{ }\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox to 0.0pt{\pgfsys@beginscope\pgfsys@invoke{ }{ {{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{ }{{}{{{}}}{{}}{}{}{}{}{}{}{ }{}{}{{}\pgfsys@moveto{5.48657pt}{0.0pt}\pgfsys@curveto{5.48657pt}{3.03018pt}{ 3.03018pt}{5.48657pt}{0.0pt}{5.48657pt}\pgfsys@curveto{-3.03018pt}{5.48657pt}{ -5.48657pt}{3.03018pt}{-5.48657pt}{0.0pt}\pgfsys@curveto{-5.48657pt}{-3.03018 pt}{-3.03018pt}{-5.48657pt}{0.0pt}{-5.48657pt}\pgfsys@curveto{3.03018pt}{-5.48 657pt}{5.48657pt}{-3.03018pt}{5.48657pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto {0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{ } }{{{{}}\pgfsys@beginscope\pgfsys@invoke{ }\pgfsys@transformcm{1.0}{0.0}{0.0}{1 .0}{-2.5pt}{-3.22221pt}\pgfsys@invoke{ }\hbox{{\definecolor{pgfstrokecolor}{ rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{ } \pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}} }}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}} } \pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope{{{}}}{}{}\hss} \pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope\hss}} \lxSVG@closescope\endpgfpicture}}\\ &=-\frac{1}{4}\left(1+\frac{\theta}{4\pi q}\right)\frac{\theta}{4\pi q}.\end{split}$ (10) $$

Now let $\theta=4\pi q$. Then $\Phi_{u,v}(2,2)-\Phi^{\prime}_{u,v}(2,2)=-1/2\neq 0$. So the walk profile $\Phi_{u,v}(2,2),\Phi^{\prime}_{u,v}(2,2)$ are different while the PE $(\lambda,z_{u},z_{v})=(\lambda^{\prime},z_{u}^{\prime},z_{v}^{\prime})$ are the same(^1^11Note that here PE denotes the eigenvalues/vectors of $\bm{A}_{q}$ rather than $\bm{L}_{q}$, as the walk profile of $\bm{A}$ is more naturally correlated to the spectrum of $\bm{A}_{q}$.). It is worthy noticing that using the same construction except that let $\bm{A}_{u_{0},u_{1}}=0$, we can show that $spd(u_{0},u_{1})=0$ but $spd^{\prime}(u_{0},u_{1})=2$. Therefore, Mag-PE cannot express shortest path distance as well.

∎

###### Proof.

### A.2 Proof of Theorem 4.3

See 4.3

###### Proof.

The proof starts with identifying a key relation between $[\bm{A}_{q}]_{u,v}^{\ell}$ and $\Phi^{\ell}_{u,v}$. Note that $[\bm{A}_{q}]_{u,v}^{\ell}$ equals to the sum of weight of all length-$\ell$ bidirectional walks:

$$ $\begin{split}[\bm{A}_{q}]_{u,v}^{\ell}&=\sum_{w_{1},w_{2},...,w_{\ell-1}}[\bm{ A}_{q}]_{u,w_{1}}[\bm{A}_{q}]_{w_{1},w_{2}}...[\bm{A}_{q}]_{w_{\ell},v}\\ &=\sum_{\begin{subarray}{c}\text{bi-walk }(u,w_{1},...,w_{\ell-1},v)\\ \text{ of length }\ell\end{subarray}}[\bm{A}_{q}]_{u,w_{1}}[\bm{A}_{q}]_{w_{1} ,w_{2}}...[\bm{A}_{q}]_{w_{\ell},v}.\end{split}$ (11) $$

It is bidirectional because $\bm{A}_{q}$ is Hermitian and allows transition along the forward edges with weight $\bm{A}_{u,v}\exp\{i2\pi q\}$ or backward edges with weight $\bm{A}_{u,v}^{*}\exp\{-i2\pi q\}$. Note that we can categorize the bidirectional walks by their number of forward and reverse edges. Then for bidirectional walk of length $\ell$ and exact $k$ forward edges, the forward edges will cause an additional phase term $\exp\{i2\pi k\}$ while the remaining $\ell-k$ backward edges will cause $\exp\{-i2\pi(\ell-k)\}=\exp\{i2\pi(k-\ell)\}$. So there is a common phase term $\exp\{i2\pi(2k-\ell)\}$ for all bidirectional walks of length $\ell$ and $k$ forward edges. Assume there is no multi-edges, i.e., directed edges $(u,v),(v,u)$ cannot appear simultaneously, now we can re-organize the formula into

$$ $\begin{split}[\bm{A}_{q}]_{u,v}^{\ell}&=\sum_{k=0}^{\ell}\sum_{\begin{subarray }{c}\text{bi-walk}(u,w_{1},...,w_{\ell-1},v)\\ \text{of length }\ell\text{ and }k\text{ forward edges}\end{subarray}}[\bm{A}_ {q}]_{u,w_{1}}[\bm{A}_{q}]_{w_{1},w_{2}}...[\bm{A}_{q}]_{w_{\ell},v}\\ &=\sum_{k=0}^{\ell}\sum_{\begin{subarray}{c}\text{bi-walk}(u,w_{1},...,w_{\ell -1},v)\\ \text{of length }\ell\text{ and }k\text{ forward edges}\end{subarray}}\exp\{i2 \pi q(2k-\ell)\}[\bm{A}_{1}]_{u,w_{1}}[\bm{A}_{2}]_{w_{1},w_{2}}...[\bm{A}_{ \ell}]_{w_{\ell},v},\end{split}$ (12) $$

where $\bm{A}_{1},...,\bm{A}_{\ell}$ is either $\bm{A}$ or $\bm{A}^{\dagger}$, depending on it is a forward or backward edge. Now by taking phase term $\exp\{i2\pi q(2k-\ell)\}$ out the inner sum, we get exactly walk profile:

$$ $\begin{split}[\bm{A}_{q}]_{u,v}^{\ell}&=\sum_{k=0}^{\ell}\exp\{i2\pi q(2k-\ell )\}\sum_{\begin{subarray}{c}\text{bi-walk}(u,w_{1},...,w_{\ell-1},v)\\ \text{of length }\ell\text{ and }k\text{ forward edges}\end{subarray}}[\bm{A}_ {1}]_{u,w_{1}}[\bm{A}_{2}]_{w_{1},w_{2}}...[\bm{A}_{\ell}]_{w_{\ell},v}\\ &=\sum_{k=0}^{\ell}\exp\{i2\pi q(2k-\ell)\}\Phi_{u,v}(\ell,k)\\ &=\exp\{-i2\pi q\ell\}\sum_{k=0}^{\ell}\exp\{i4\pi qk\}\Phi_{u,v}(\ell,k).\end {split}$ (13) $$

Let $L$ be any positive integer. Let us write the relation above for $\Phi_{u,v}(\ell,\cdot)$ ($\ell\leq L$) in a matrix form:

$$ $\bm{F}_{q}\begin{pmatrix}\Phi_{u,v}(1,0)&\Phi_{u,v}(2,0)&...&\Phi_{u,v}(L,0)\\ \Phi_{u,v}(1,1)&\Phi_{u,v}(2,1)&...&\Phi_{u,v}(L,1)\\ 0&\Phi_{u,v}(2,2)&...&\Phi_{u,v}(L,2)\\ 0&0&...&\Phi_{u,v}(L,3)\\ ...&...&...&\Phi_{u,v}(L,L)\end{pmatrix}=\begin{pmatrix}e^{i2\pi}[\bm{A}_{q}]_ {u,v}&e^{i4\pi}[\bm{A}^{2}_{q}]_{u,v}&...&e^{i2L\pi}[\bm{A}^{L}_{q}]_{u,v}\end {pmatrix},$ (14) $$

where $\bm{F}_{q}=(1,\exp\{i4\pi q\},\exp\{i8\pi q\},...,\exp\{i8L\pi q\})\in\mathbb{
R}^{1\times(L+1)}$. For notation convenience, let us denote RHS as $\bm{Y}_{q}$ so we write the linear system as $\bm{F}_{q}\bm{\Phi}=\bm{Y}_{q}$. Note that as $\Phi$ are real values, we can know the values of $\bm{Y}_{\frac{1}{2}-q}$ by the complex conjugate of $\bm{Y}_{q}$ thanks to the symmetry of Fourier matrix $\bm{F}_{q}$:

$$ $\bm{Y}_{\frac{1}{2}-q}=\bm{F}_{\frac{1}{2}-q}\bm{\Phi}=\bm{F}_{q}^{*}\bm{\Phi} =\bm{Y}^{*}_{q}.$ (15) $$

Now we are ready to prove the theorem. Let $Q=\lceil L/2\rceil+1$ and let $\vec{q}=(q_{1},q_{2},...,q_{Q})$ with each $q_{j}\leq 1/4$ and $q_{j}$ are distinct. From eigenvalues/vectors at these frequencies we are able to get $\bm{Y}_{\vec{q}}$. Furthermore, we get to know $\bm{Y}_{\frac{1}{2}-\vec{q}}=\bm{Y}_{\vec{q}}^{*}$ as we just argued. That is, we know $\bm{Y}_{\vec{q}^{\,\prime}}$ where $\vec{q}^{\,\prime}=(\vec{q},1/2-\vec{q})$ . Since $\vec{q}<1/4$, we claim that $1/2-\vec{q}>1/4$ and thus $\vec{q}^{\,\prime}$ contains $Q^{\prime}:=2\cdot(\lceil L/2\rceil+1)\geq L+2$ different qs. We can put equation $\bm{F}_{q}\bm{\Phi}=\bm{Y}_{q}$ for each $q$ in $\vec{q}^{\,\prime}$ into one matrix equation as follows:

$$ $\bm{F}_{\vec{q}^{\,\prime}}\begin{pmatrix}\Phi_{u,v}(1,0)&\Phi_{u,v}(2,0)&...& \Phi_{u,v}(L,0)\\ \Phi_{u,v}(1,1)&\Phi_{u,v}(2,1)&...&\Phi_{u,v}(L,1)\\ 0&\Phi_{u,v}(2,2)&...&\Phi_{u,v}(L,2)\\ 0&0&...&\Phi_{u,v}(L,3)\\ ...&...&...&\Phi_{u,v}(L,L)\end{pmatrix}=\begin{pmatrix}e^{i2\pi}[\bm{A}_{q_{1 }}]_{u,v}&...&e^{i2L\pi}[\bm{A}^{L}_{q_{1}}]_{u,v}\\ ...&...&...\\ e^{i2\pi}[\bm{A}_{q_{Q^{\prime}}}]_{u,v}&...&e^{i2L\pi}[\bm{A}^{L}_{q_{Q^{ \prime}}}]_{u,v}\end{pmatrix},$ (16) $$

where $\bm{F}_{\vec{q}}=(\bm{F}_{q_{1}};\bm{F}_{q_{2}};...;\bm{F}_{q_{L+1}})\in
\mathbb{R}^{Q^{\prime}\times(L+1)}$. Since $\bm{F}_{\vec{q}^{\,\prime}}$ contains $\bm{Q}^{\prime}\geq L+2$ different frequencies and thus is full-rank, we can uniquely determine walk profile $\Phi_{u,v}$ from the RHS matrix. Notably, $q_{j}=\frac{j}{2(L+1)}$ makes $\bm{F}_{\vec{q}}$ discrete Fourier transform, a unitary matrix which is invertible by taking its conjugate transpose.

∎

###### Proof.

## Appendix B Experimental Setup

In this section, we give further implementation details. We use Quadro RTX 6000 on Linux system to train the models. The training time for single run is typically between 1 hour to 5 hours.

Note that for SignNet, we use $\phi$ and $\rho$ to represent $\text{SignNet}(v_{1},...,v_{d})=\rho([\phi(v_{j})+\phi(-v_{j})]_{j=1,...,d})$, where $v_{j}$ is the $i$-th eigenvectors.

For SPE, we use both node SPE $z_{\text{node}}$ and edge SPE $z_{\text{edge}}$ by default, except for High-level synthetic task where we find using $z_{\text{node}}$ only has comparable performance to both $z_{\text{node}}$ and $z_{\text{edge}}$.

For each experiment, the search space for baseline single $q$ is exactly the range of multiple $\vec{q}$. For example, if for multiple $\vec{q}$ we choose $\vec{q}=(1/10,2/10,...,5/10)$, then for baseline single $q$ we search over $q=1/10,2/10,...,5/10$.

### B.1 Distance Prediction on Directed Graphs

**Table 4: Hyperparameter for walk profile/shortest path distance/longest path distance prediction on regular directed graphs.**
| Targets | walk profile (regular graphs) | spd (regular graphs) | lpd (regular graphs) |
| --- | --- | --- | --- |
| Base model | 8-layer MLPs |  |  |
| Hidden dim | 64 |  |  |
| Batch size | 512 |  |  |
| Learning rate | 1e-3 |  |  |
| Dropout | 0 |  |  |
| Epoch | 150 |  |  |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |  |
| PE dim | 32 |  |  |
| Multiple q | (1/10, 2/10, …, 5/10) | (1/30, 2/30, …., 15/30) | (1/30, 2/30, …., 15/30) |
| PE processing | SignNet ($\phi=$3-layer MLPs, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer GIN) |  |  |

**Table 5: Hyperparameter for walk profile/shortest path distance/longest path distance prediction on directed acyclic graphs.**
| Targets | walk profile (DAG) | spd (DAG) | lpd (DAG) |
| --- | --- | --- | --- |
| Base model | 8-layer MLPs |  |  |
| Hidden dim | 64 |  |  |
| Batch size | 512 |  |  |
| Learning rate | 1e-3 |  |  |
| Dropout | 0 |  |  |
| Epoch | 150 |  |  |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |  |
| PE dim | 32 |  |  |
| Multiple q | (1/10, 2/10, …, 5/10) | (1/20, 2/20, …., 10/20) | (1/20, 2/20, …., 10/20) |
| PE processing | SignNet ($\phi=$3-layer MLPs, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer GIN) |  |  |

#### B.1.1 Model Hyperparameter

See Table 4 and 5.

### B.2 Sorting Networks

**Table 6: Hyperparameter for sorting network prediction.**
| Targets | Sorting Network |
| --- | --- |
| Base model | 3-layer Transformer+mean pooling+3-layer MLPs |
| Hidden dim | 256 |
| Batch size | 48 |
| Learning rate | 1e-4 |
| Dropout | 0.2 |
| Epoch | 15 (SignNet) or 5 (SPE) |
| Optimizer | Adam ($\beta_{1}=0.7,\beta_{2}=0.9$, weight decay $6\times 10^{-5}$) |
| PE dim | 25 |
| Multiple q | (1/20, 2/10, …, 5/20) / $d_{G}$ |
| PE processing | SignNet ($\phi=$3-layer MLPs, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer GIN) |

#### B.2.1 Model Hyperparameter

See Table 6.

#### B.2.2 Dataset Generation

Our sorting networks generation follows exactly as Geisler et al. (). To generate a sorting network, the length of sequence (number of variables to sort) is first randomly chosen. Given the sequence length, each step it will generate a pair-wise sorting operator between two random variables, 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 a directed graph, where each node represents a sorting operator, whose feature is the ids of two variables to sort. In the sorting network, if two sorting operators share a common variable to 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 is very likely not a 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 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.

**Table 7: Hyperparameter for bidirected GIN on Open Circuit Benchmark.**
| Targets | Gain | BW | PM |
| --- | --- | --- | --- |
| Base model | 4-layer bidi. GIN | 3-layer bidi. GIN | 4-layer bidi. GIN |
| Graph Pooling | Sum | Sum | Sum |
| Hidden dim | 96 | 192 | 288 |
| Batch size | 128 | 64 | 64 |
| Learning rate | 0.0067 | 0.0065 | 0.0021 |
| Dropout | 0.1 | 0 | 0.2 |
| Epoch | 300 | 300 | 300 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |  |
| PE dim | 10 |  |  |
| Multiple q | (1/100, 2/100, …, 10/100) | (1/100, 2/100, …, 5/100) | (1/100, 2/100, …, 5/100) |
| PE processing | SignNet ($\phi$=1-layer bidi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer bidi. GIN) |  |  |

**Table 8: Hyperparameter for undirected GIN on Open Circuit Benchmark.**
| Targets | Gain | BW | PM |
| --- | --- | --- | --- |
| Base model | 4-layer undi. GIN | 3-layer undi. GIN | 4-layer undi. GIN |
| Graph Pooling | Sum | Sum | Sum |
| Hidden dim | 96 | 192 | 288 |
| Batch size | 128 | 64 | 64 |
| Learning rate | 0.0067 | 0.0065 | 0.0021 |
| Dropout | 0.1 | 0 | 0.2 |
| Epoch | 300 | 300 | 300 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |  |
| PE dim | 10 |  |  |
| Multiple q | (1/100, 2/100, …, 10/100) | (1/100, 2/100, …, 5/100) | (1/100, 2/100, …, 5/100) |
| PE processing | SignNet ($\phi$=1-layer undi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer undi. 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 (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 | 54 |
| Batch size | 256 | 256 | 64 |
| Learning rate | 0.004 | 0.00119 | 0.00117 |
| Dropout | 0.2 | 0.3 | 0.2 |
| Epoch | 200 | 200 | 200 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |  |
| PE dim | 10 |  |  |
| Multiple q | (1/100, 2/100, …, 5/100) | (1/100, 2/100, …, 10/100) | (1/100, 2/100, …, 5/100) |
| PE processing | SignNet ($\phi$=1-layer bidi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer bidi. GIN) |  |  |

**Table 10: Hyperparameter for SAT (each layer uses undirected 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.00117 |
| Dropout | 0.2 | 0.3 | 0.1 |
| Epoch | 200 | 200 | 200 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |  |
| PE dim | 10 |  |  |
| Multiple q | (1/100, 2/100, …, 10/100) | (1/100, 2/100, …, 10/100) | (1/100, 2/100, …, 10/100) |
| PE processing | SignNet ($\phi$=1-layer undi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer undi. GIN) |  |  |

#### B.4.1 Model Hyperparameter

See Table 7, 8, 9, 10.

### B.5 High-level Synthetic

**Table 11: Hyperparameter for bidirected GIN on High-level Synthetic dataset.**
| Targets | DSP | LUT |
| --- | --- | --- |
| Base model | 4-layer bidi. GIN | 4-layer bidi. GIN |
| Graph Pooling | Mean | Mean |
| Hidden dim | 84 | 192 |
| Batch size | 64 | 56 |
| Learning rate | 0.003 | 0.0023 |
| Dropout | 0.2 | 0.1 |
| Epoch | 400 | 400 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |
| PE dim | 10 |  |
| Multiple q | (1/100, 2/100, …, 5/100) | (1/100, 2/100, …, 5/100) |
| PE processing | SignNet ($\phi$=2-layer bidi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer bidi. GIN) |  |

**Table 12: Hyperparameter for undirected 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 |
| Epoch | 400 | 400 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |
| PE dim | 10 |  |
| Multiple q | (1/100, 2/100, …, 5/100) | (1/100, 2/100, …, 5/100) |
| PE processing | SignNet ($\phi$=2-layer undi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer undi. GIN) |  |

**Table 13: Hyperparameter for SAT (each layer uses bidirected GIN as kernel) on High-level Synthetic dataset.**
| Targets | DSP | LUT |
| --- | --- | --- |
| Base model | 4-layer SAT (2-hop bidi. GIN) | 3-layer SAT (2-hop bidi. GIN) |
| Graph Pooling | Mean | Mean |
| Hidden dim | 78 | 62 |
| Batch size | 64 | 64 |
| Learning rate | 0.004 | 0.004 |
| Dropout | 0.1 | 0.1 |
| Epoch | 400 | 400 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |
| PE dim | 10 |  |
| Multiple q | (1/100, 2/100, …, 5/100) | (1/100, 2/100) |
| PE processing | SignNet ($\phi$=2-layer bidi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer bidi. GIN) |  |

**Table 14: Hyperparameter for SAT (each layer uses undirected GIN as kernel) on High-level Synthetic dataset.**
| 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 | 98 | 62 |
| Batch size | 64 | 64 |
| Learning rate | 0.004 | 0.004 |
| Dropout | 0.1 | 0.1 |
| Epoch | 400 | 400 |
| Optimizer | Adam ($\beta_{1}=0.9,\beta_{2}=0.999$) |  |
| PE dim | 10 |  |
| Multiple q | (1/100, 2/100, …, 5/100) | (1/100, 2/100, …, 5/100) |
| PE processing | SignNet ($\phi$=2-layer bidi. GIN, $\rho$=3-layer MLPs), SPE ($\phi$=3-layer MLPs, $\rho$=2-layer bidi. GIN) |  |

#### B.5.1 Model Hyperparameter

See Table 11, 12, 13, 14.

## Appendix C Varying Single q 𝑞 q italic_q Baseline

This section shows the effect the varying single $q$ on the performance of Mag-PE. Horizontal axis is the value of single $q$, vertical axis is the test performance. The dashed line represents the result of Multi-q Magnetic Laplacian with fixed multi-q $\vec{q}$ as described in Section 5.1.

As shown in Figures 5, 6, 7, 8, we can see that the multiple q performance consistently beats best performance of single q, which demonstrates the benefits of using multiple q simultaneously.

Figure: Figure 5: Test RMSE for distance prediction with varying $q$ of single-q Magnetic Laplacian. First row is for directed acyclic graphs, and second row is for regular directed graphs.
Refer to caption: x8.png

Figure: Figure 6: Test F1 of sorting network satisfibability with varying single $q$.
Refer to caption: x9.png

Figure: Figure 7: Test RMSE for prediction of Gain, BW, PM using backbone GINE or BIGINE, with varying $q$ of single-q Magnetic Laplacian.
Refer to caption: x10.png

Figure: Figure 8: Test MSE for prediction of DSP and LUT, using backbone GINE or BIGINE, with varying $q$ of single-q Magnetic Laplacian.
Refer to caption: x11.png

Table: Table 15: Test RMSE results over 3 random seeds for node-pair distance prediction.

Figure: Table 16: Test F1 scores over 5 random seeds for sorting network satisfiability.
Refer to caption: x12.png

## Appendix D Runtime Evaluation

First, we note that introducing multiple q brings extra computational cost, as stated in the Conclusion 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 are required. Thus there is a 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, we choose connected acyclic graphs; for high-level synthetic dataset, we choose undirected GIN as backbone for evaluation. We use SPE to handle PEs
and all other hyperparameters are the same as 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 4 show the runtime evaluation of multiple q for our tasks, using single Quadro RTX 6000.
Preprocessing time refers to the pre-computation of eigendecompositions, and training/inference time refers to the runtime on the training set per epoch (average over 10 epochs). Note that the preprocessing time is typically not a concern, as it 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.

**Table 17: Dataset statistics.**
| 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 |

## Appendix E Impact of Multiple q 𝑞 q italic_q Values Selection Policy

As implied by Theorem 4.3, any choice of multiple $q$ values should yields the same level of expressivity to compute walk profile. To verify this, we further implement a randomly sampled $\vec{q}$ (each $q$ is uniformly sampled from $[0,1/2]$) to
predict distances and walk profile. Table 15,16,18 and Figure 9 show the results of randomly sampled multiple $q$ compared to previous methods, where evenly-spaced $\vec{q}=(\frac{1}{2L},\frac{2}{2L},...,\frac{L}{2L})$ for some $L$ (see specific values in Appendix B) is the origin one we adopted in the main text, and random $\vec{q}=(q_{1},q_{2},...,q_{L})$ contains $L$ many $q$ values randomly sampled from $(0,1/2]$. Note that collision $q_{i}\approx q_{j}$ could lead to a ill-conditioned recovery of walk profile, so we force that $|q_{i}-q_{j}|\geq 0.2/L$ during $q$ sampling process. For each run of model training (i.e., each random seed), we sample a different random $\vec{q}$. Table 15 shows the results. We can see that randomly sampled $\vec{q}$ has comparable and even better performance than evenly-spaced $\vec{q}$, which validates our theory.

**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 method | PE processing | Gain | BW | PM | DSP | LUT |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Undirected-GIN | Lap | SignNet | $0.430_{\pm 0.009}$ | $4.712_{\pm 0.134}$ | $1.127_{\pm 0.007}$ | $2.665_{\pm 0.184}$ | $2.025_{\pm 0.057}$ |
| SPE | $0.416_{\pm 0.021}$ | $4.321_{\pm 0.084}$ | $1.127_{\pm 0.020}$ | $2.662_{\pm 0.187}$ | $\bm{1.925_{\pm 0.059}}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.426_{\pm 0.009}$ | $4.670_{\pm 0.113}$ | $1.116_{\pm 0.009}$ | $2.673_{\pm 0.090}$ | $2.027_{\pm 0.091}$ |  |
| SPE | $0.405_{\pm 0.016}$ | $4.305_{\pm 0.092}$ | $1.121_{\pm 0.018}$ | $2.666_{\pm 0.190}$ | $2.024_{\pm 0.068}$ |  |  |
| Maglap-1q (best q) | SPE | $0.398_{\pm 0.025}$ | $4.281_{\pm 0.085}$ | $\bm{1.113_{\pm 0.022}}$ | $2.614_{\pm 0.098}$ | $2.010_{\pm 0.082}$ |  |
| Maglap-Multi-q | SignNet | $0.421_{\pm 0.015}$ | $4.743_{\pm 0.215}$ | $1.126_{\pm 0.011}$ | $2.665_{\pm 0.111}$ | $2.025_{\pm 0.076}$ |  |
| SPE | $\bm{0.389_{\pm 0.017}}$ | $\bm{4.175_{\pm 0.115}}$ | $1.137_{\pm 0.004}$ | $\bm{2.582_{\pm 0.133}}$ | $1.976_{\pm 0.089}$ |  |  |
| Maglap-Multi-q (random) | SignNet | $0.409_{\pm 0.021}$ | $4.655_{\pm 0.054}$ | $1.124_{\pm 0.016}$ | $2.784_{\pm 0.157}$ | $2.087_{\pm 0.098}$ |  |
| SPE | $0.397_{\pm 0.020}$ | $4.267_{\pm 0.089}$ | $1.142_{\pm 0.011}$ | $2.772_{\pm 0.123}$ | $2.103_{\pm 0.117}$ |  |  |
| Bidirected-GIN | Lap | SignNet | $0.382_{\pm 0.008}$ | $4.371_{\pm 0.171}$ | $1.127_{\pm 0.021}$ | $2.256_{\pm 0.109}$ | $1.806_{\pm 0.096}$ |
| SPE | $0.391_{\pm 0.007}$ | $4.153_{\pm 0.160}$ | $1.135_{\pm 0.035}$ | $2.267_{\pm 0.126}$ | $1.786_{\pm 0.072}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.388_{\pm 0.012}$ | $4.351_{\pm 0.132}$ | $1.131_{\pm 0.012}$ | $2.304_{\pm 0.143}$ | $1.882_{\pm 0.085}$ |  |
| SPE | $0.384_{\pm 0.008}$ | $4.152_{\pm 0.056}$ | $1.123_{\pm 0.026}$ | $2.344_{\pm 0.134}$ | $1.830_{\pm 0.116}$ |  |  |
| Maglap-1q (best q) | SPE | $0.383_{\pm 0.002}$ | $4.113_{\pm 0.052}$ | $\bm{1.099_{\pm 0.020}}$ | $2.256_{\pm 0.144}$ | $1.768_{\pm 0.090}$ |  |
| Maglap-Multi-q | SignNet | $0.381_{\pm 0.008}$ | $4.443_{\pm 0.116}$ | $1.119_{\pm 0.016}$ | $2.212_{\pm 0.116}$ | $1.791_{\pm 0.091}$ |  |
| SPE | $\bm{0.371_{\pm 0.008}}$ | $\bm{4.051_{\pm 0.139}}$ | $1.116_{\pm 0.012}$ | $\bm{2.207^{\dagger}_{\pm 0.185}}$ | $\bm{1.735^{\dagger}_{\pm 0.096}}$ |  |  |
| Maglap-Multi-q (random) | SignNet | $0.378_{\pm 0.008}$ | $4.372_{\pm 0.108}$ | $1.142_{\pm 0.016}$ | $2.276_{\pm 0.170}$ | $1.823_{\pm 0.089}$ |  |
| SPE | $0.388_{\pm 0.020}$ | $4.102_{\pm 0.125}$ | $1.130_{\pm 0.018}$ | $2.499_{\pm 0.203}$ | $1.875_{\pm 0.082}$ |  |  |
| SAT (undirected-GIN) | Lap | SignNet | $0.368_{\pm 0.022}$ | $4.085_{\pm 0.189}$ | $1.038_{\pm 0.016}$ | $3.103_{\pm 0.101}$ | $2.223_{\pm 0.175}$ |
| SPE | $0.375_{\pm 0.016}$ | $4.180_{\pm 0.093}$ | $1.065_{\pm 0.034}$ | $3.167_{\pm 0.193}$ | $2.425_{\pm 0.168}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.382_{\pm 0.009}$ | $4.143_{\pm 0.181}$ | $1.073_{\pm 0.021}$ | $3.087_{\pm 0.183}$ | $2.214_{\pm 0.150}$ |  |
| SPE | $0.366_{\pm 0.003}$ | $4.081_{\pm 0.071}$ | $1.089_{\pm 0.023}$ | $3.206_{\pm 0.197}$ | $2.362_{\pm 0.154}$ |  |  |
| Maglap-1q (best q) | SPE | $0.361_{\pm 0.016}$ | $4.014_{\pm 0.068}$ | $1.057_{\pm 0.036}$ | $3.101_{\pm 0.176}$ | $2.362_{\pm 0.154}$ |  |
| Maglap-Multi-q | SignNet | $0.368_{\pm 0.020}$ | $4.044_{\pm 0.090}$ | $1.066_{\pm 0.028}$ | $3.121_{\pm 0.143}$ | $\bm{2.207_{\pm 0.113}}$ |  |
| SPE | $\bm{0.350^{\dagger}_{\pm 0.004}}$ | $4.044_{\pm 0.153}$ | $\bm{1.035^{\dagger}_{\pm 0.025}}$ | $\bm{3.076_{\pm 0.240}}$ | $2.333_{\pm 0.147}$ |  |  |
| Maglap-Multi-q (random) | SignNet | $0.361_{\pm 0.015}$ | $4.122_{\pm 0.067}$ | $1.094_{\pm 0.064}$ | $3.106_{\pm 0.123}$ | $2.236_{\pm 0.128}$ |  |
| SPE | $0.356_{\pm 0.010}$ | $\bm{3.953_{\pm 0.104}}$ | $1.052_{\pm 0.014}$ | $3.086_{\pm 0.174}$ | $2.320_{\pm 0.135}$ |  |  |
| SAT (bidirected-GIN) | Lap | SignNet | $0.384_{\pm 0.025}$ | $3.949_{\pm 0.125}$ | $1.069_{\pm 0.029}$ | $\bm{2.569_{\pm 0.116}}$ | $2.048_{\pm 0.088}$ |
| SPE | $0.368_{\pm 0.022}$ | $4.024_{\pm 0.106}$ | $1.046_{\pm 0.021}$ | $2.713_{\pm 0.135}$ | $2.173_{\pm 0.107}$ |  |  |
| Maglap-1q (q=0.01) | SignNet | $0.384_{\pm 0.015}$ | $4.023_{\pm 0.032}$ | $1.055_{\pm 0.028}$ | $2.616_{\pm 0.120}$ | $2.054_{\pm 0.127}$ |  |
| SPE | $0.364_{\pm 0.012}$ | $3.996_{\pm 0.178}$ | $1.074_{\pm 0.030}$ | $2.687_{\pm 0.209}$ | $2.192_{\pm 0.135}$ |  |  |
| Maglap-1q (best q) | SPE | $\bm{0.360_{\pm 0.009}}$ | $3.960_{\pm 0.060}$ | $1.062_{\pm 0.024}$ | $2.657_{\pm 0.128}$ | $2.107_{\pm 0.135}$ |  |
| Maglap-Multi-q | SignNet | $0.420_{\pm 0.035}$ | $4.022_{\pm 0.128}$ | $1.089_{\pm 0.046}$ | $2.741_{\pm 0.110}$ | $2.045_{\pm 0.079}$ |  |
| SPE | $\bm{0.359_{\pm 0.008}}$ | $\bm{3.930^{\dagger}_{\pm 0.069}}$ | $\bm{1.045_{\pm 0.012}}$ | $2.616_{\pm 0.151}$ | $2.082_{\pm 0.099}$ |  |  |
| Maglap-Multi-q (random) | SignNet | $0.417_{\pm 0.040}$ | $4.053_{\pm 0.094}$ | $1.078_{\pm 0.043}$ | $2.677_{\pm 0.146}$ | $\bm{2.016_{\pm 0.078}}$ |  |
| SPE | $0.363_{\pm 0.007}$ | $3.956_{\pm 0.087}$ | $1.064_{\pm 0.022}$ | $2.690_{\pm 0.165}$ | $2.259_{\pm 0.147}$ |  |  |
|  |  |  |  |  |  |  |  |

## Appendix F 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 walk patterns, similar to 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 at 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). In this case, the total dimension of the walk profile is about (16*15)/2=120. In contrast, multi-q PE (with only top K eigenvectors, K=32 in our example) usually yields a 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 some sparsity structures of walk profile (which is indeed observed in our experiments), it is possible to downsample a small number of q to recover the walk profile of large length. Finally, walk profiles are inherently features tied to node pairs, so it generally requires a 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.

## Appendix G Normalized Walk Profile

We define normalized walk profile $\hat{\Phi}_{u,v}(\ell,k)$ by replacing every $\bm{A}$ with random walks $\bm{D}_{\text{total}}^{-1}\bm{A}$, where $[\bm{D}_{\text{total}}]_{u,u}$ is the total node degree of node $u$. As a result, $\hat{\Phi}_{u,v}(\ell,k)$ represents the probability of landing at node $v$ in a bidirectional random walk with $k$ forward edges, starting from node $u$. Note that normalized walk profiles still are able to 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 $\hat{\bm{L}}=\bm{I}-\bm{D}_{\text{total}}^{-1/2}\bm{A}_{q}\bm{D}^{-1/2}_{\text
{total}}$. The normalization nature of $\bm{\hat{L}}$ makes it more suitable to recover normalized walk profile instead of the unnormalized ones.

## Peer Reviews

confidence: 4
contribution: 3
initial_rating: 8
presentation: 4
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. 

- Could you provide a more detailed justification of how Equation (2) is produced? (currently: "By the definition" (line 260)).

- 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)?

- What is the role of m in Equations (3), (4) (also consider balancing paretheses in these: minor, unbalanced "{" instead of "(" appear in them)?
soundness: 3
strengths: - This paper has an exemplary organization with clean definitions and explanation of fundamental developments and a balanced experimental section.

- 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.

- 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).
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. 

In 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. 

In 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).
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.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: No questions.
soundness: 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.
- 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.
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. 

Empirically, 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.
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? 

In 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.

---

confidence: 3
contribution: 2
initial_rating: 5
presentation: 2
questions: 1. Have you tried reducing the cost when calculating higher terms? Or is it a fundamental limitation of the method?

2. 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?

3. Have you tried other simple models on the datasets, potentially with no positional encodings just to see how they perform as baselines?

4. For the experiment in Section 5.1, have you tried larger graphs?

5. Do you know whether walk profiles are related in any way to $1$-WL or beyond for measuring expressivity?

6. 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.
soundness: 2
strengths: - The paper is presented adequately, and is easy to read.
- The interest in being able to express the walk profiles is nicely motivated in the introduction.
- 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.
- 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.
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$.
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.
- 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]).
- 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.
- In the experiments, while there is a fair share of ablations, standard GNN models can be added.
- 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.

Overall, 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).

[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

[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

[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

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: 1.	Given 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?

2.	Would it be possible to apply this model to larger graphs by selectively reducing the number of q values?

3.	Have 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.
soundness: 3
strengths: 1.	Multi-q Mag-PE is a unique extension within the domain of GNN, specifically targeting the gap in encoding methods for directed graphs.

2.	The 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.

3.	Through 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.
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.
weaknesses: 1.	Although 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.

2.	The 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.

3.	The 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.

4.	The 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.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: - Sec. 5.4: what is the size of the data here?
soundness: 3
strengths: - The research is well motivated in the first sections of the paper
- The theory is well-explained
- It is nice that the approach is considered with both MPNNs and transformers
- 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.
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.

(Please note: I did not check all theoretical details)
weaknesses: - The paper is rather densely written
- 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)
- Another suitable baseline on the DAG data would be DAG transformer [1]
- There is a recent paper [2], which considers other realistic datasets, and maybe should be considered as competitor and be compared to 

[1] Luo et al. Transformers over Directed Acyclic Graphs, NeurIPS'23 https://openreview.net/pdf?id=g49s1N5nmO

[2] Wang et al. Directed Graph Transformers, TMLR'24 https://openreview.net/pdf?id=otTFPjziiK

Meta-review: This paper focuses on position encodings (basically node embeddings) for directed graphs. They introduce a notion of a 'walk profile', which captures natural structures in directed graphs, show that existing embedding approaches cannot accurately represent the walk profile, and introduce a new embedding method based on the magnetic Laplacian with multiple phase shifts that can capture the walk profile. They demonstrate that their method is effective in a variety of applications.

The reviewers found the paper to be well-written and well-motivated. Some weaknesses brought up were the computational complexity of the method and the lack of a theoretical justification behind the walk profile, outside its intuitive capturing of some important structures in directed graphs. Although overall, the positives outweigh the negatives, leading to the recommendation of acceptance.

Decision: Accept (Poster)