Graph Neural Networks for Edge Signals: Orientation Equivariance and Invariance

## Abstract

Abstract Many applications in traffic, civil engineering, or electrical engineering revolve around edge-level signals. Such signals can be categorized as inherently directed, for example, the water flow in a pipe network, and undirected, like the diameter of a pipe. Topological methods model edge signals with inherent direction by representing them relative to a so-called orientation assigned to each edge.
These approaches can neither model undirected edge signals nor distinguish if an edge itself is directed or undirected. We address these shortcomings by (i) revising the notion of orientation equivariance to enable edge direction-aware topological models, (ii) proposing orientation invariance as an additional requirement to describe signals without inherent direction, and (iii) developing EIGN , an architecture composed of novel direction-aware edge-level graph shift operators, that provably fulfills the aforementioned desiderata. It is the first general-purpose topological GNN for edge-level signals that can model directed and undirected signals while distinguishing between directed and undirected edges. A comprehensive evaluation shows that EIGN outperforms prior work in edge-level tasks, for example, improving in RMSE on flow simulation tasks by up to 43.5%.

## 1 Introduction

Most research on Graph Neural Networks (GNN) research has focused on node- or graph-level tasks (Wu et al., ; Kipf & Welling, ; Hamilton et al., ; Velickovic et al., ; Gasteiger et al., ; AlQuraishi, ) while edge-level problems remain underexplored. Edge-level signals describe the properties of *existing* edges and are either the features, hidden representations of a GNN, or the targets. They naturally arise in applications involving traffic and many areas of engineering (e.g. electric circuits (Dörfler et al., ) or hydraulics (Garzón et al., ; Herrera et al., )).

Signals on edges come in two different modalities: (a) They can have an inherent orientation, like the water flow in a pipe network or traffic flow on streets.
We call them *orientation-equivariant* signals as they are naturally expressed as scalar values relative to a chosen orientation as reference (see Section 2).
(b) We refer to signals without intrinsic direction, e.g. pipe diameter or speed limits, as *orientation-invariant*.
Similar concepts in continuous domains are scalar fields that a single value to each point in space, while vector fields describe magnitude and direction.

At the same time, edges themselves may be directed or undirected. Examples that induce directed edges include valves in water networks, one-way roads in street networks, or diodes in electrical circuits. Often, in these applications, directed edges prohibit (to a large extent) a signal that is oriented against the edge direction. Such constraints can have a big impact on the targets. For example, imagine a one-way street that forces cars to take a detour.

Figure: (a) Application: Traffic
Refer to caption: x1.png

There are two relevant streams of work that, however, fall short of either representing orientation-equivariant or orientation-invariant signals. (a) One strategy is to map between orientation-invariant edge-level signals using Line Graphs. (b) The other line of work relies on Algebraic Topology (Schaub et al., ; Ebli et al., ; Bunch et al., ) to cope with orientation-equivariant signals. Topological models define an arbitrary reference direction for each edge, a so-called *orientation*, and use positive values to indicate that an orientation-equivariant signal aligns with this reference orientation whereas negative values indicate misalignment (see how in Figures 1a and 1b, the signal $1.3$ is represented as $-1.3$). For undirected edges, there is no preferred reference orientation. Consequently, a common requirement for topological models is to be *orientation-equivariant* (Roddenberry et al., ): The sign of the (orientation-equivariant) signal must change together with the orientation of the corresponding edge (see Figure 1). Orientation equivariance is a property of a topological model that allows it to deal with orientation-equivariant signals.

Many applications have both orientation-equivariant and invariant features with an arbitrary combination of orientation-equivariant and invariant targets. Moreover, real scenarios are often only accurately modeled using both undirected and directed edges. However, Line Graph approaches misrepresent the properties of orientation-equivariant signals, while topological approaches treat every signal as orientation-equivariant and can not distinguish edge direction.
Consistent with our experimental findings, the inductive biases of prior methods render them ineffective in practice.

We address these shortcomings and are the first to model edge-level tasks with orientation-equivariant and -invariant signals on graphs with directed and undirected edges. Our key contributions are:

- a)
Desiderata.
We formalize suitable desiderata:
(i) *Joint orientation equivariance*for orientation-equivariant signals, and
(ii) *joint orientation invariance*for orientation-invariant signals.
- b)
EIGN: The first general-purpose edge-level topological GNN.(^1^11We provide our code at [https://github.com/dfuchsgruber/eign](https://github.com/dfuchsgruber/eign).) EIGN provably fulfills these desiderata, leveraging novel direction-aware convolution operators.
and a fusion operation between both modalities to model their interactions ( see Figure 3).
- c)
Benchmarking. We devise a suite of challenging and diverse benchmarks covering synthetic and real-world tasks, including a novel dataset for electric circuits that requires dealing with orientation-equivariant and orientation-invariant signals on graphs with directed and undirected edges. EIGN outperforms prior work by reducing the RMSE up to 43.5% in our experiments.

## 2 Background

Algebraic Topology is a principled framework for representing orientation-equivariant edge signals (Roddenberry & Segarra, ; Roddenberry et al., ; Ebli et al., ).
In the interest of notational clarity, we simplify many concepts by directly applying them to the edge domain and omit general topological definitions. For a comprehensive introduction, we refer to Schaub et al. ().

Notation. We consider edge-level problems on a graph ${\mathcal{G}}=({\mathcal{V}},{\mathcal{E}})$ with $n=\lvert{\mathcal{V}}\rvert$ nodes and $m=\lvert{\mathcal{E}}\rvert$ edges. We distinguish between:
(i) directed edges, represented by ordered tuples ${{\mathcal{E}}_{{\text{D}}}}\subseteq{\mathcal{V}}\times{\mathcal{V}}$, and undirected edges ${{\mathcal{E}}_{{\text{U}}}}\subseteq\{\{u,v\}:u,v\in{\mathcal{V}}\}$, represented by unordered sets.
(ii) edge-signals (inputs, hidden representations, outputs) that come with inherent direction as *orientation-equivariant* ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and *orientation-invariant* ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$ otherwise.

Orientation. While orientation-invariant edge signals can be represented by scalar values as they are, orientation-equivariant edge signals need to be defined relative to the orientation of the associated edge. To that end, topological methods define an arbitrarily chosen orientation ${\mathfrak{O}}:{\mathcal{E}}\rightarrow{\mathcal{V}}\times{\mathcal{V}}$ for every edge, also represented by ordered tuples. If an orientation-equivariant signal $x$ aligns with the orientation of its edge, we represent it with $x$ and $-x$ otherwise. Changing from orientation ${\mathfrak{O}}$ to another orientation $\smash{\hat{{\mathfrak{O}}}}$ induces sign flips for all orientation-equivariant signals of edges whose orientation was flipped. We can represent this orientation change for signals with a diagonal matrix $\smash{{\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}\in\mathbb{R}^{m\times m}}$ with entries $\smash{[{\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}]_{e,e}=1}$ if $\smash{{\mathfrak{O}}(e)=\hat{{\mathfrak{O}}}(e)}$ and $-1$ otherwise.

Edge direction and orientation are different concepts. While the former is part of the given problem topology and may influence model predictions, the latter can be thought of as a basis in which orientation-equivariant edge signals are represented. For undirected edges, which orientation is chosen must not impact the problem itself. However, unlike previous work, we fix the orientation of *directed edges* to match their direction (${\mathfrak{O}}(e_{\text{D}})=e_{\text{D}}$) and, consequently, represent their orientation-equivariant signals relative to their direction. We refer to such orientations as *direction-consistent*. They can encode information about the direction of *directed* edges.

Boundary and Laplace Operators. For a given orientation ${\mathfrak{O}}$, one can define a boundary operator that maps signals on $m$ edges defined with respect to orientation ${\mathfrak{O}}$ to the domain of $n$ nodes. Reusing the analogy of water flow, the boundary operator sums all flow coming into a node and subtracts all outgoing flow. It can be represented by a matrix ${\bm{B}}_{\text{equ}}\in\mathbb{R}^{n\times m}$:

$$ $[{\bm{B}}_{\text{equ}}]_{v,e}=\begin{cases}-1&\text{if }{\mathfrak{O}}(e)=(v, \cdot)\\ 1&\text{if }{\mathfrak{O}}(e)=(\cdot,v)\\ 0&\text{otherwise}\end{cases}$ (1) $$

The boundary operator can be used to define a Laplace operator on the edges of the graph, the so-called (Equivariant) Edge Laplacian (Schaub et al., ): $\smash{{\bm{L}}_{\text{equ}}={\bm{B}}_{\text{equ}}^{T}{\bm{B}}_{\text{equ}}}$. This operator can be understood as message passing between edges that are incident to a shared node (see Section 4.3).

## 3 Related Work

Figure: (a) Traffic Scenarios
Refer to caption: x2.png

Orientation-Equivariant Models. Methods grounded in Algebraic Topology represent orientation-equivariant signals on undirected graphs relative to an arbitrary orientation (Schaub et al., ). Some of these approaches also utilize higher-order structures composed of edges that, however, often need to be handcrafted (Bunch et al., ; Giusti et al., ).
HodgeGNN (Roddenberry & Segarra, ) and similar architectures (Park et al., ; Roddenberry et al., ) satisfy a more limited notion of orientation equivariance compared to our proposal. This results in major shortcomings of these models in practice:
(i) They treat all input and output signals as orientation-equivariant and, therefore, can not model orientation-invariant edge signals appropriately. In the example of Figure 1, their model would not predict the same orientation-invariant output under different orientations ${\mathfrak{O}}$ and $\smash{\hat{{\mathfrak{O}}}}$ but instead induce sign flips as if they were orientation-equivariant signals. Thus, these models do not provide consistent predictions given different (arbitrary) orientations of the same topology.
(ii) These approaches also enforce orientation equivariance with respect to the orientation of *all* edges, whereas our desiderata relax this requirement to hold for *undirected* edges only. A model that is orientation-equivariant for directed edges can not encode edge direction as its predictions are equivariant to changing the edge direction. However, as depicted in Figure 2, edge direction often alters the nature of the problem: In one scenario cars go against the direction of a one-way street (e.g. in accident forecasting) while in the other they do not.

Flow Interpolation. An orthogonal line of research studies flow interpolation problems (Ford & Fulkerson, ; Lippi et al., ). Even though both features and targets are technically orientation-equivariant, many methods do not approach this task from a topological perspective. Instead, they utilize specialized inductive biases such as flow conservation (Jia et al., ) or physics-informed constraints (Smith et al., ). da Silva et al. () frame interpolation as a bi-level optimization problem where edge-level models serve as learned regularizers. Such approaches are limited to flow interpolation problems while our model is a general framework that can be applied to a broader range of edge-level tasks. As we find in Section 5.3, EIGN can learn the physical properties of a problem without explicitly encoding physics-informed inductive biases.

Edge-Level GNNs. Beyond flow-based problems, GNNs have been applied to (orientation-invariant) edge-level tasks as well. One family of approaches employs node-level GNNs and a successive readout function (Zhao et al., ). Such approaches have been particularly popular for link prediction (Zhou, ), where target edges are not present in the input data. Another paradigm is to apply node-level GNNs to the dual Line Graph (Jiang et al., ; Jo et al., ) of the topology. Only a few approaches rely on edge-specific methods (Zhang et al., ). Models that are not grounded in a topological framework lack appropriate inductive biases to model orientation-equivariant signals with inherent direction. These approaches can be categorized as treating both input and target as orientation-invariant signals. In the context of Figure 1, they would not represent orientation-equivariant signals relative to the respective orientation.

GNNs for Directed Graphs. Directed graphs have received a lot of attention for node-level problems. Many approaches discriminate between adjacent in-neighbors and out-neighbors (Li et al., ; Rossi et al., ). Also, spectral convolutions, that are based on the Node Laplacian, have been generalized to directed settings (Ma et al., ; Monti et al., ). From the different possible direction-aware Laplacians (Tong et al., ), our work takes inspiration from the Magnetic Node Laplacian (Zhang et al., ) which can be defined using a complex-valued boundary operator. It was recently utilized to compute direction-aware positional node encodings (Geisler et al., ). The Laplace operators of our approach generalize this concept to edge-level problems.

## 4 Method

We introduce the first orientation- Equivariant and orientation-Invariant edge-level GNN (EIGN) model. First, we formalize three desiderata for edge-level architectures that accommodate both orientation-equivariant and -invariant signals (Section 4.1). Then, we detail EIGN’s architecture in Section 4.2 and finally describe its convolution operators in Section 4.3.

### 4.1 Desirable Properties for Edge-Level GNNs

At the core of our work stand novel desiderata which enforce a model to make consistent predictions for both orientation-equivariant and -invariant edge signals among different orientations.
We restrict our novel constraints to *undirected edges* by requiring equivariance/invariance among direction-consistent orientations only.
This allows representing the direction of directed edges through their orientation which, consequentially, must not be arbitrary. We additionally prove that EIGN is also equivariant with respect to edge permutations, which we defer to Section A.2.

###### Definition 4.1 (Joint Orientation Equivariance) .

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be arbitrary *direction-consistent* orientations of edges on ${\mathcal{G}}$. We say that a mapping $f$ is jointly orientation-equivariant if for any orientation-equivariant input ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and any orientation-invariant input ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$:

$$ ${\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f({\bm{X}}_{\text{equ}},{\bm{X}} _{\text{inv}},{\mathcal{G}},{\mathfrak{O}})=f({\Delta_{{\mathfrak{O}},\hat{{ \mathfrak{O}}}}}{\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat {{\mathfrak{O}}})$ $$

###### Definition 4.2 (Joint Orientation Invariance) .

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be arbitrary *direction-consistent* orientations of edges on ${\mathcal{G}}$. We say that a mapping $g$ is jointly orientation-invariant if for any orientation-equivariant input ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and any orientation-invariant input ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$:

$$ $g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})=g( {\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}},{\bm{X}}_{ \text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}})$ $$

Both definitions ensure that a model predicts the same output signal when the orientation is changed from ${\mathfrak{O}}$ to $\smash{\hat{{\mathfrak{O}}}}$: While Definition 4.1 ensures that the orientation-equivariant output is represented relative to the new orientation $\smash{\hat{{\mathfrak{O}}}}$, Definition 4.2 requires the same orientation-invariant predictions which are not relative to the new orientation. In both desiderata, the orientation-equivariant input $\smash{{\bm{X}}_{\text{equ}}}$ needs to be represented relative to the respective orientation as well. Restricting these properties to direction-consistent orientations means that both properties only need to hold regarding the arbitrary orientation of undirected edges. This allows models to break both desiderata for the orientation of *directed edges*, which enables using their orientation to encode direction.

###### Definition 4.1 (Joint Orientation Equivariance) .

###### Definition 4.2 (Joint Orientation Invariance) .

### 4.2 EIGN : an orientation-equivariant and orientation-invariant Model

Figure: Figure 3: EIGN architecture: In each layer, message passing using novel Laplacians is performed within and between orientation-equivariant and orientation-invariant signals. The two aggregated modalities $\smash{{\bm{Z}}^{(l)}_{\text{equ}}}$ and then ${{\bm{Z}}^{(l)}_{\text{inv}}}$ are then fused.
Refer to caption: x3.png

We propose EIGN (Figure 3), a model that satisfies these desiderata. It consists of $L$ layers each of which takes orientation-equivariant and -invariant input edge signals $\smash{{\bm{H}}^{(l-1)}_{\text{equ}}}$, $\smash{{\bm{H}}^{(l-1)}_{\text{inv}}}$ and transforms them into outputs of the corresponding modality $\smash{{\bm{H}}^{(l)}_{\text{equ}}}$ and $\smash{{\bm{H}}^{(l)}_{\text{inv}}}$. It performs message passing between edge signals through different graph shift operators $\smash{\melequi,\melinv\,\melinvtoequi,\melequitoinv}$ (see “Convolutions” in Figure 3 and Section 4.3 for details) both within and between edge signal modalities. We set $\smash{{\bm{H}}^{(0)}_{\text{equ}}={\bm{X}}_{\text{equ}}}$, $\smash{{\bm{H}}^{(0)}_{\text{inv}}={\bm{X}}_{\text{inv}}}$ and $\smash{{\bm{H}}^{(L)}_{\text{equ}}}$ and $\smash{{\bm{H}}^{(L)}_{\text{inv}}}$ are the equivariant and invariant output signals, respectively. In the following, we denote with $\smash{{\bm{W}}^{(l)}_{(\cdot)}}$ model parameters of appropriate dimensions, with $\sigma_{\text{equ}}$ an element-wise sign equivariant activation function, i.e. $\sigma_{\text{equ}}(-x)=-\sigma_{\text{equ}}(x)$, and with $\sigma_{\text{inv}}$ an arbitrary non-linearity. We detail the implementation of EIGN in Section C.3.

$$ $\displaystyle{\bm{Z}}^{(l)}_{\text{equ}}=\sigma_{\text{equ}}(\melequi{\bm{H}}_ {\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{equ}}^{(l)}+ \melinvtoequi{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text {equ}}^{(l)}+{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ (2) $\displaystyle{\bm{Z}}^{(l)}_{\text{inv}}=\sigma_{\text{inv}}(\melinv{\bm{H}}_{ \text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+ \melequitoinv{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text {inv}}^{(l)}+{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}}^{(l)})$ (3) $$

The message passing scheme implied by intra-modality Laplacians $\smash{\melequi}$ and $\smash{\melinv}$ updates the orientation-equivariant and -invariant signal representation of an edge by aggregating orientation-equivariant and -invariant signals of adjacent edges. Similarly, the inter-modality Laplacians $\smash{\melinvtoequi}$ and $\smash{\melequitoinv}$ aggregate messages from adjacent edges of one modality and transform it into the other. While this enables information exchange between directed and undirected edge signals, it restricts their interaction to local aggregates: The edge orientation-equivariant signal only depends on the average of adjacent orientation-invariant signals and vice versa. This makes modeling interactions between orientation-equivariant and –invariant edge signals of the same edge difficult. Therefore, EIGN uses a second fusion operation that does not use Laplacians (depicted as “Fusion” in Figure 3):

$$ $\displaystyle{\bm{H}}^{(l)}_{\text{equ}}=\sigma_{\text{equ}}({\bm{Z}}^{(l)}_{ \text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ}\rightarrow\text{equ}}\odot{ \bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv}\rightarrow \text{equ}}+{\bm{Z}}^{(l)}_{\text{equ}})$ (4) $\displaystyle{\bm{H}}^{(l)}_{\text{inv}}=\sigma_{\text{inv}}({\bm{Z}}^{(l)}_{ \text{inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv}\rightarrow\text{inv}}\odot \operatorname*{abs}({\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}}, \text{equ}\rightarrow\text{inv}})+{\bm{Z}}^{(l)}_{\text{inv}})$ (5) $$

**Table 1: Convolution and self- interaction operators for both input and output signal modalities.**
| Output<br>Input | Equ. | Inv. |
| --- | --- | --- |
| Equ. | $\melequi$<br>${\bm{W}}_{\text{equ}}$ | $\melequitoinv$<br>${\bm{W}}_{\textsc{{F}},\text{equ}\rightarrow\text{inv}}$ |
| Inv. | $\melinvtoequi$<br>${\bm{W}}_{\textsc{{F}},\text{inv}\rightarrow\text{equ}}$ | $\melinv$<br>${\bm{W}}_{\text{inv}}$ |

Here, $\odot$ and $\operatorname*{abs}$ denote element-wise multiplication and absolute value. In general, the fusion operation can be realized arbitrarily. We chose point-wise multiplication and absolute values as they are jointly orientation-equivariant / -invariant fusion operations respectively (see Appendix A).

EIGN models all possible types of interactions between edge signal modalities (Table 1): The Laplacian operators of Equations 2 and 3 describe interactions of orientation-equivariant and -invariant signals with local aggregates of both the same and different modality. The residual connections in Equations 2 and 3 and the fusion operation of Equations 4 and 5 model interactions between orientation-equivariant and -invariant signals of the same edge.
The design choices of the fusion operation in Equations 4 and 5 and the definition of the Laplace operators $\smash{\melequi}$, $\smash{\melinv}$, $\smash{\melinvtoequi}$ and $\smash{\melequitoinv}$, which we detail next, enforce EIGN to conform to all desiderata proposed in Section 4.1.

### 4.3 orientation-equivariant and orientation-invariant Laplacians

Equivariant and Invariant Edge Laplacians. The Equivariant Edge Laplacian (see Section 2) arises from an (equivariant) boundary operator as ${\bm{L}}_{\text{equ}}={\bm{B}}_{\text{equ}}^{T}{\bm{B}}_{\text{equ}}$. Its sparsity pattern corresponds to the adjacency matrix of the dual Line Graph (Jiang et al., ; Jo et al., ), i.e. edges are adjacent if they are incident to the same node. It is a jointly orientation-equivariant mapping (see Lemma 4.1) and therefore suitable to convole orientation-equivariant edge signals. Intuitively, ${\bm{L}}_{\text{equ}}$ performs message passing: A target edge $e\in{\mathcal{E}}$ aggregates the orientation-equivariant signals of adjacent edges. Additionally, it re-orients the signal of an adjacent edge $e^{\prime}\in{\mathcal{E}}$ by multiplying with $-1$ if the orientations of $e$ and $e^{\prime}$ misalign. The orientations of two edges misalign if they are consecutive, i.e. the endpoint of one is the starting point of the other (see Figure 4).

$$ $\left[{\bm{L}}_{\text{equ}}\right]_{e,e^{\prime}}=\begin{cases}2&\text{if }e=e ^{\prime}\\ -1&\text{if }{\mathfrak{O}}(e),{\mathfrak{O}}(e^{\prime})\text{ consecutive}\\ 1&\text{if }{\mathfrak{O}}(e),{\mathfrak{O}}(e^{\prime})\text{ not consecutive , but }e,e^{\prime}\text{ adjacent}\\ 0&\text{otherwise}\end{cases}$ (6) $$

Figure: Figure 4: The Equivariant Magnetic Edge Laplacian $\smash{\melequi}$ induces a complex phase shift of $\pi q$ for signals of directed edges that are aggregated by the black undirected edge. Signals of misaligned edges are re-oriented.
Refer to caption: x4.png

We propose a novel Laplacian for orientation-invariant edge signals by defining a suitable boundary operator that is independent of any chosen orientation ${\mathfrak{O}}$:

$$ $\left[{\bm{B}}_{\text{inv}}\right]_{v,e}=\begin{cases}1&\text{if }v\in e\\ 0&\text{otherwise}\end{cases}$ (7) $$

It induces the Invariant Edge Laplacian $\smash{{\bm{L}}_{\text{inv}}={\bm{B}}_{\text{inv}}^{T}{\bm{B}}_{\text{inv}}}$ which has the same sparsity pattern as ${\bm{L}}_{\text{equ}}$. In particular, the Invariant Edge Laplacian can be obtained by taking the element-wise absolute value ${\bm{L}}_{\text{inv}}=\operatorname*{abs}({\bm{L}}_{\text{equ}})$. Its message passing scheme is similar to ${\bm{L}}_{\text{equ}}$ as well: It, too, aggregates messages of adjacent edges but does not re-orient them if their orientations are consecutive. Thus, it is a jointly orientation-invariant mapping and suitable to convolve orientation-invariant edge signals.

Direction-aware Edge Laplacians. Neither ${\bm{L}}_{\text{equ}}$ nor ${\bm{L}}_{\text{inv}}$ can distinguish directed from undirected edges as they do not explicitly model them differently. However, following a recent line of work on Magnetic Node Laplacians (Forman, ; Shubin, ; Colin de Verdière, ; Furutani et al., ; Geisler et al., ), we generalize both operators to make them direction-aware. Intuitively, the Magnetic Node Laplacian represents edge direction through complex phase shifts of magnitude $\pi q$ for some fixed hyperparamter $q\in\mathbb{R}$. It can be computed using a complex-valued boundary operator (Fanuel & Bardenet, ):

$$ $\left[\mboundaryequi\right]_{v,e}=\begin{cases}-\exp(i\pi q)&\text{if }e=(v, \cdot)\text{ and }e\in{{\mathcal{E}}_{{\text{D}}}}\\ \exp(-i\pi q)&\text{if }e=(\cdot,v)\text{ and }e\in{{\mathcal{E}}_{{\text{D}}} }\\ -1&\text{if }{\mathfrak{O}}(e)=(v,\cdot)\text{ and }e\in{{\mathcal{E}}_{{\text {U}}}}\\ 1&\text{if }{\mathfrak{O}}(e)=(\cdot,v)\text{ and }e\in{{\mathcal{E}}_{{\text{ U}}}}\\ 0&\text{otherwise}\end{cases}$ (8) $$

This boundary operator $\smash{\mboundaryequi}$ extends $\smash{{\bm{B}}_{\text{equ}}}$ by inducing complex phase shifts of $\pi q$ along directed edges. Consequently, $q=0$ recovers the direction-agnostic boundary operator of Equation 1. Using the boundary operator $\smash{\mboundaryequi}$, we can define a direction-aware Equivariant Magnetic Edge Laplacian analogously to its direction-agnostic counterpart as $\smash{\melequi=(\mboundaryequi)^{H}\mboundaryequi}$.
Its sparsity pattern is the same as $\smash{{\bm{L}}_{\text{equ}}}$ and for undirected edges both operators coincide.
Thus, its aggregation scheme is similar as well: The key difference is that $\smash{\melequi}$ applies a complex phase shift to the signals of *directed edges* before aggregating them instead of just re-orienting them by flipping their sign.
The direction of the phase shift is determined by how the edges relate to their shared incident node. The phases of ingoing edges will be shifted in a different direction than the phases of outgoing edges. Figure 4 depicts this mechanism for adjacent edges that are
(i) undirected and aligned in orientation
(ii) undirected and misaligned in orientation
(iii) directed and aligned in orientation.
$\smash{\melequi}$ is a jointly orientation-equivariant operator as per Definition 4.1 for the (arbitrary) orientation of undirected edges (even if they are adjacent to directed edges). It, however, specifically breaks orientation equivariance for *directed* edges by inducing complex phase shifts: Changing the direction of a directed edge flips the sign of the complex phase shift that is applied before aggregation. We detail how all Laplacian operators of EIGN materialize in Table 5.

###### Lemma 4.1 .

The Magnetic Equivariant Edge Laplacian implies a jointly orientation-equivariant mapping $\smash{f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{
O}})=\smash{\melequi}({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{equ}}}$.

Analogously, we use complex phase shifts to encode direction into the boundary operator ${\bm{B}}_{\text{inv}}$ (Equation 7) that induces the Laplacian ${\bm{L}}_{\text{inv}}$ for orientation-invariant signals:

$$ $\left[\mboundaryinv\right]_{v,e}=\begin{cases}\exp(i\pi q)&\text{if }e=(v, \cdot)\text{ and }e\in{{\mathcal{E}}_{{\text{D}}}}\\ \exp(-i\pi q)&\text{if }e=(\cdot,v)\text{ and }e\in{{\mathcal{E}}_{{\text{D}}} }\\ 1&\text{if }v\in e\text{ and }e\in{{\mathcal{E}}_{{\text{U}}}}\\ 0&\text{otherwise}\end{cases}$ (9) $$

It induces a Magnetic Invariant Edge Laplacian $\smash{\melinv=(\mboundaryinv)^{H}\mboundaryinv}$ that performs message passing analogous to the Magnetic Equivariant Edge Laplacian. Like its direction-agnostic counterpart $\smash{{\bm{L}}_{\text{inv}}}$, it is defined independently of orientation and does not re-orient its inputs. Instead, it generalizes $\smash{{\bm{L}}_{\text{inv}}}$ by only encoding edge direction through the direction of a complex phase shift similar to $\smash{\melequi}$. It is a jointly orientation-invariant mapping as per Definition 4.2.

###### Lemma 4.2 .

The Magnetic Invariant Edge Laplacian
implies a jointly orientation-invariant mapping $g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})=
\smash{\melinv}({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$.

Fusing Invariant and Equivariant Signals. Both $\smash{\melequi}$ and $\smash{\melinv}$ are convolutions within edge signals of the same modality, i.e. orientation-equivariant or orientation-invariant signals. We enable information exchange between both by combining the boundary operators of Equations 8 and 9. First, we define a Laplacian to transform orientation-equivariant edge signals into orientation-invariant edge signals as $\smash{\melequitoinv=(\mboundaryinv)^{H}\mboundaryequi}$. This operator allows modeling orientation-invariant outputs even if no orientation-invariant inputs are available. Since it is constructed from direction-aware boundary operators it, too, induces complex phase shifts to encode directed edges.

Analogously, a fusion operator that transforms orientation-invariant edge signals into orientation-equivariant edge signals can be constructed as $\smash{\melinvtoequi=({\bm{B}}_{\text{equ}})^{H}{\bm{B}}_{\text{inv}}}$. It transforms orientation-invariant inputs into an orientation-equivariant edge signal. Again, directed edges are encoded with complex phase shifts.
The outputs of both operators satisfy joint orientation equivariance/invariance (Definitions 4.1 and 4.2) for undirected edges for which no complex phase shift is applied.

###### Lemma 4.3 .

The Invariant Fusion Magentic Edge Laplacian
implies a jointly orientation-invariant mapping $g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})=
\smash{\melequitoinv}({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{equ}}$.
The Equivariant Fusion Magnetic Edge Laplacian
implies a jointly orientation-invariant mapping $f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})=
\smash{\melinvtoequi}({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$.

Since EIGN is composed of Laplacians that are jointly orientation-equivariant/-invariant mappings respectively, it satisfies the desiderata for edge-level GNNs stated in Section 4.1. The proof follows Lemmata 4.1, 4.2 and 4.3 and is supplied in Appendix A.

###### Theorem 4.1 .

###### Lemma 4.1 .

###### Lemma 4.2 .

###### Lemma 4.3 .

###### Theorem 4.1 .

## 5 Experiments

We showcase the efficacy of EIGN on three synthetic problems and three real-world tasks on five datasets. We devise the synthetic tasks to require proper handling of directionality as well as orientation-equivariant and orientation-invariant information.
We categorize all datasets in terms of whether the graphs are (partially) directed and if features and/or targets are orientation-equivariant or orientation-invariant in Section 5.1 (see details in Appendix C).

Baselines. We compare EIGN to five baselines:
(i) An MLP.
(ii) LineGraphGNN, a node-level spectral GNN applied to the line graph of the problem (Bandyopadhyay et al., )).
(iii) HodgeGNN(Roddenberry et al., ; Park et al., ), based on the Edge Laplacian ${\bm{L}}_{\text{equ}}$ (see Section 2): It assumes inputs to be orientation-equivariant and edges to be undirected.
(iv) Hodge+Invas a variant of Hodge+Inv that models orientation-invariant features as orientation-equivariant.
(v) Hodge+Dir, a variant of HodgeGNN that breaks orientation equivariance, and, thus, treats all edges as directed.
As depicted in Section 5.1, every baseline (or a variation thereof) fails to model at least one problem aspect. Only EIGN is applicable in every possible scenario.

### 5.1 Synthetic Tasks

**Table 2: Average performance of different models on synthetic tasks (best and runner-up). EIGN is particularly effective on the hard Tri-Flow problem with interactions between orientation-equivariant and orientation-invariant inputs.**
| Model | RW Comp<br>AUC-ROC ($\uparrow$) | LD Cycles<br>AUC-ROC ($\uparrow$) | Tri-Flow<br>RMSE ($\downarrow$) |
| --- | --- | --- | --- |
| MLP | $0.720$ | $0.500$ | $0.546$ |
| LineGraph | $0.758$ | $0.684$ | $0.498$ |
| HodgeGNN | $0.500$ | $0.500$ | $0.459$ |
| Hodge+Inv | $0.811$ | $0.753$ | 0.291 |
| Hodge+Dir | 0.819 | 0.802 | $0.293$ |
| EIGN | 0.862 | 0.996 | 0.036 |

Random Walk Completion (RW Comp). The first synthetic problem we devise is completing random walks on a directed graph. We input the (orientation-invariant) transition probabilities and a subset of the edges that were traversed. The task is to classify if an edge is part of the random walk (details in Section C.1). Since walks are sequences of consecutive edges, this problem tests if a model can distinguish different edge directions.

Longest Directed Cycle Prediction (LD Cycles). We increase the problem difficulty by including both directed and undirected edges: We generate different graphs that contain cycles entirely composed of each respective edge type. The task is to predict which edges belong to the largest cycle composed of only directed edges (details in Section C.1). Since there are no additional inputs, this task tests a model’s ability to distinguish directed and undirected edges.

Triangle Flow Orientation (Tri-Flow). This is the most challenging synthetic task as it requires combining orientation-equivariant and orientation-invariant features in a partially directed graph.
We create multiple graphs containing disjoint triangles and provide an (orientation-equivariant) flow input. The task is to reorient the flow such that for triangles satisfying certain conditions there is no excess flux. These constraints are based on both direction and an orientation-invariant color attribute we assign to every edge.
This task requires learning the relationship between edge direction and both orientation-equivariant and -invariant features.

Results. Table 2 shows that on all three synthetic tasks, EIGN is the superior architecture. Its high efficacy on the RW Comp and LD Cycles problems confirm its merits in modeling edge direction: It distinguishes between edges of different directions as well as undirected edges. As it satisfies our desiderata, it can model the relationship between orientation-equivariant and orientation-invariant features and relate them to edge direction. This is reflected in its impressive performance on the Tri-Flow task while the direction-aware HodgeGNN as well as Hodge+Dir, which also combines both orientation-equivariant and -invariant inputs, struggle to achieve comparable results.

### 5.2 Real-World Problems

**Table 3: Average RMSE ($\downarrow$) of different models for the simulation task on real-world datasets (best and runner-up). EIGN achieves substantial improvements over all baselines.**
| Model | Traffic |  |  |  |  |
| --- | --- | --- | --- | --- | --- |
| Anaheim | Barcelona | Chicago | Winnipeg | Circuits |  |
| MLP | $0.096$ | $0.150$ | $0.111$ | $0.165$ | $1.036$ |
| LineGraph | $0.087$ | $0.147$ | $0.112$ | $0.160$ | $1.046$ |
| HodgeGNN | $0.270$ | $0.170$ | $0.109$ | $0.174$ | $1.035$ |
| Hodge+Inv | $0.096$ | 0.146 | 0.108 | $0.162$ | 0.862 |
| Hodge+Dir | 0.081 | 0.146 | $0.110$ | 0.159 | $0.878$ |
| EIGN | 0.069 | 0.130 | 0.061 | 0.090 | 0.583 |

Datasets. We also apply EIGN to real-world flow data from the domains of traffic networks and electrical circuits.
(i) We select four transportation networks (Stabler et al., ) (Anaheim, Barcelona, Chicago, Winnipeg) where the targets are the best-known flow solutions in terms of lowest Average Excess Cost (Boyce et al., ). While these datasets only contain orientation-invariant features, two tasks use information from the orientation-equivariant targets as additional inputs.
(ii) We generate different electrical circuits consisting of resistances, diodes, and one power outlet with a given voltage. We then simulate currents and voltages using LTSpice (Asadi, ). Each circuit has orientation-equivariant (voltage at the source) and orientation-invariant features (resistance, component type), while the target current is also orientation-equivariant (details in Section C.1
).

**Table 4: Ablation of different components of EIGN on synthetic tasks and simulation on real data (best and runner-up). We omit (i) direction-awarenes by setting $q=0$, (ii) the fusion operation of Equations 4 and 5, (iii) the fusion operators using Laplacians $\melequitoinv$ and $\melinvtoequi$.**
|  | Dataset | EIGN<br>w/o Direction | EIGN<br>No Fusion | EIGN<br>No Fusion-Conv. | EIGN |
| --- | --- | --- | --- | --- | --- |
| AUC<br>$\uparrow$ | RW Comp | $0.761$ | $0.848$ | 0.850 | 0.862 |
| LD Cycles | $0.688$ | 0.983 | $0.928$ | 0.996 |  |
| RMSE<br>$\downarrow$ | Tri-Flow | $0.366$ | 0.119 | $0.267$ | 0.036 |
| Anaheim | $0.243$ | 0.093 | $0.270$ | 0.069 |  |
| Barcelona | $0.156$ | 0.148 | $0.169$ | 0.130 |  |
| Chicago | 0.061 | 0.084 | $0.109$ | 0.061 |  |
| Winnipeg | 0.098 | $0.152$ | $0.174$ | 0.090 |  |
| Circuits | 0.773 | $0.813$ | $1.083$ | 0.583 |  |

Tasks. For each dataset, we study three problems of increasing difficulty for each of which the edge flow needs to be predicted:
(i) *Denoising*: We noise the target flow and provide it as an (additional) equivariant input.
(ii) *Interpolation*: We supply the target flow on a subset of edges as an (additional) equivariant input.
(iii) *Simulation*: The target flow is to be predicted without any additional inputs.

Results. We report the RMSE ($\downarrow$) of all models for the simulation task in Table 3 and defer results for the easier denoising and interpolation problems to Appendix D. EIGN substantially improves over all baselines in denoising and simulation. In interpolation, it performs competitively or outperforms the baselines.
In particular, on the challenging simulation task, the merit of EIGN that treats orientation-equivariant and orientation-invariant signals in a principled way is apparent.

### 5.3 Ablations

Fusion Operators. In Section 4.3, we introduce Laplacian operators to fuse orientation-equivariant and orientation-invariant features by transforming a signal from one modality into the other. This is particularly useful as it allows EIGN to output orientation-equivariant signals in the absence of orientation-equivariant inputs and vice versa.
Omitting these Laplacian fusion operations and only relying on Equations 4 and 5 for interaction between the two modalities is problematic:

The only choice for an equivariant input signal in the absence of such features is 0 0.
Intuitively, this is because the sign of an orientation-equivariant input indicates its direction relative to the chosen orientation. However, the ”absence“ of an input has no inherent direction.
Setting the equivariant input to 0 0 while at the same time omitting the $\smash{\melinvtoequi}$ term in Equation 2 results embeddings $\smash{{\bm{Z}}_{\text{equ}}^{(l)}={\bm{L}}^{(q)}_{\text{equ}\rightarrow\text{
equ}}\bm{0}{\bm{W}}^{(l)}_{\text{equ}\rightarrow\text{equ}}+\bm{0}{\bm{W}}^{(l
)}_{\text{equ}}=\bm{0}}$. Using the point-wise multiplicative fusion operation of Equation 4 leads to a zero-valued output $\smash{{\bm{H}}^{(l)}=\bm{0}}$ as well. Therefore, omitting the Laplacian fusion operation from Equation 2 prohibits the model from learning any non-zero orientation-equivariant output in the absence of orientation-equivariant inputs. This is reflected in Table 4: Not using Laplacian fusion operations results in considerably worse performance in simulation tasks where no orientation-equivariant features are available.

At the same time, omitting the fusion operation of Equations 4 and 5 and only relying on the Laplacian fusion operators $\smash{\melequitoinv}$, $\smash{\melinvtoequi}$ is limiting as well. As mentioned in Section 4.2, this architecture would restrict the information exchange between orientation-equivariant and orientation-invariant features to only exchanging aggregated information through the convolution operators $\smash{\melequitoinv}$ and $\smash{\melinvtoequi}$. Therefore, it is more difficult to learn direct interactions between the signal modalities of *the same* edge. Both on Tri-Flow and real data, where these interactions are relevant, omitting the operators of Equations 4 and 5 leads to worse performance, see Table 4.

Figure: Figure 5: Distribution of simulated traffic flow on Anaheim for EIGN and a direction-agnostic variant. Direction-awareness makes predictions that obey flow constraints of one-way streets more likely.

Direction-Awareness. We also study the impact of using complex-valued Laplace operators to make EIGN direction-aware as described in Section 4.3 by ablating a direction-agnostic version of EIGN in Table 4 ($q=0$). First, the RW Comp and LD Cycles tasks that test direction-awareness benefit greatly from encoding direction with complex phase shifts. Second, many real-world datasets contain directed edges that constrain flow to follow a specific direction. Accurately modeling the system requires distinguishing between directed and undirected edges which is reflected in the superior performance of the direction-aware EIGN. Finally, Figure 5 shows that the direction-aware EIGN yields more plausible predictions than the direction-agnostic variant for one-way roads. It learns the problem constraints without encoding them into the architecture explicitly.

## 6 Limitations

We explore a principled approach to various edge-level problems. Due to the sparse body of work on edge-level tasks, the number of suitable benchmarks is limited. To cope with that, we design three synthetic tasks and propose a novel task involving real-world electric circuits. We leave collecting further benchmarks for future work. Furthermore, while EIGN is grounded in Algebraic Topology, we limit our study to edge-level problems. We believe that including higher-order and lower-order structures is an interesting avenue for further improvements.
As we are initiating a new line of work, we study a basic yet powerful message-passing paradigm that uses Laplacians as convolution operators. Future work may explore more sophisticated schemes, e.g., including attention (Velickovic et al., ). Lastly, we solely consider convolution operations that act locally. Since $\melequi$ and $\melinv$ are *normal matrices*, they would also lend themselves well to model global propagation schemes as in Geisler et al. ().

## 7 Conclusion

We propose EIGN, a framework for edge-level problems that allows modeling orientation-equivariant and orientation-invariant features and can encode edge direction. It relies on novel graph shift operators that provably preserve novel notions of joint orientation-equivariance and -invariance for undirected edges while also being sensitive to flipping directed edges. On a benchmark of synthetic tasks and real-world flow modeling problems from two domains, we show the high efficacy of the inductive biases encoded by EIGN.

## Ethics Statement

We acknowledge that we thoroughly read and adhere to the code of ethics. Since our work can be categorized as foundational research, we do not see any immediate implications beyond the risk of advancing Machine Learning, in general. We, nonetheless, encourage readers and practitioners building on our work to keep in mind the potential risks in the context of reliability, interpretability, fairness, and privacy for which we do explicitly account.

## Reproducability Statement

We detail assumptions and proofs for all claims made in our work clearly in Appendix A. Furthermore, we describe in detail how the data and models are tuned in Appendix C. Additionally, we provide our code and the optimal hyperparameter configurations we found in the supplementary material.

## Acknowledgements

We want to give special thank to Jan Schuchardt, Franz Rieger, Niklas Kemper, and Tim Beyer for giving helpful suggestions on an early draft of the manuscript. The research presented has been performed in the frame of the RADELN project funded by TUM Georg Nemetschek Institute Artificial Intelligence for the Built World (GNI). Moreover, this research was supported by the Helmholtz Association under the joint research school “Munich School for Data Science - MUDS“.

## Appendix A Proofs

### A.1 Joint Orientation Equivariance and Joint Orientation Invariance

###### Proposition A.1 .

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be two direction-consistent orientations of edges on ${\mathcal{G}}$. Let ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d}$. Then:

$$ $\displaystyle\mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\Delta_{{\mathfrak{O }},\hat{{\mathfrak{O}}}}}=\mboundaryequi({\mathcal{G}},\hat{{\mathfrak{O}}})$ $$

###### Proof.

By assumption, for any $e_{\text{D}}\in{{\mathcal{E}}_{{\text{D}}}}$ we have that $\hat{{\mathfrak{O}}}(e_{\text{D}})={\mathfrak{O}}(e_{\text{D}})={\Delta_{{
\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\mathfrak{O}}(e_{\text{D}})$. Now consider the case $e_{\text{U}}\in{{\mathcal{E}}_{{\text{U}}}}$.
If ${\mathfrak{O}}(e_{\text{U}})=\hat{{\mathfrak{O}}}(e_{\text{U}})$, then $\mboundaryequi({\mathcal{G}},{\mathfrak{O}})_{v,e_{\text{U}}}=\mboundaryequi(
\hat{{\mathcal{G}},{\mathfrak{O}}})_{v,e_{\text{U}}}$ for all $v\in{\mathcal{V}}$. Similarly, if ${\mathfrak{O}}(e_{\text{U}})\neq\hat{{\mathfrak{O}}}(e_{\text{U}})$, then $[\mboundaryequi({\mathcal{G}},{\mathfrak{O}})]_{v,e}=-[\mboundaryequi({
\mathcal{G}},\hat{{\mathfrak{O}}})]_{v,e_{\text{U}}}$ for all $v\in{\mathcal{V}}$.
∎

See 4.1

###### Proof.

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be two direction-consistent orientations of edges on ${\mathcal{G}}$. Let ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$. Then:

$$ $\displaystyle f({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{ equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}})$ $\displaystyle=\melequi({\mathcal{G}},\hat{{\mathfrak{O}}}){\Delta_{{\mathfrak{ O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}},\hat{{\mathfrak{O}}}))^{H} \mboundaryequi({\mathcal{G}},\hat{{\mathfrak{O}}}){\Delta_{{\mathfrak{O}},\hat {{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\Delta_{{\mathfrak {O}},\hat{{\mathfrak{O}}}}})^{H}\mboundaryequi({\mathcal{G}},{\mathfrak{O}}){ \Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\Delta_{{\mathfrak{O}},\hat{{ \mathfrak{O}}}}}{\bm{X}}_{\text{equ}}$ $\displaystyle=({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}})^{H}( \mboundaryequi({\mathcal{G}},{\mathfrak{O}}))^{H}\mboundaryequi({\mathcal{G}}, {\mathfrak{O}}){\bm{X}}_{\text{equ}}$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}\melequi({\mathcal {G}},{\mathfrak{O}}){\bm{X}}_{\text{equ}}$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f({\bm{X}}_{\text{ equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})$ $$

Here, we used Proposition A.1 and the facts that ${\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\Delta_{{\mathfrak{O}},\hat{{
\mathfrak{O}}}}}={\bm{I}}_{m}$ by definition and ${\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}=({\Delta_{{\mathfrak{O}},\hat{{
\mathfrak{O}}}}})^{H}$ as it is a diagonal real matrix.

∎

###### Proposition A.2 .

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be two direction-consistent orientations of edges on ${\mathcal{G}}$. Let ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d}$. Then:

$$ $\displaystyle\mboundaryinv({\mathcal{G}},{\mathfrak{O}})=\mboundaryinv({ \mathcal{G}},\hat{{\mathfrak{O}}})$ $$

###### Proof.

By assumption, for any $e_{\text{D}}\in{{\mathcal{E}}_{{\text{D}}}}$ we have that $\hat{{\mathfrak{O}}(e_{\text{D}})}={\mathfrak{O}}(e_{\text{D}})={\Delta_{{
\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\mathfrak{O}}(e_{\text{D}})$ and consequentially, $[\mboundaryinv({\mathcal{G}},{\mathfrak{O}})]_{v,e_{\text{D}}}=[\mboundaryinv(
{\mathcal{G}},\hat{{\mathfrak{O}}})]_{v,e_{\text{D}}}$ for all $v\in{\mathcal{V}}$. For $e_{\text{U}}\in{{\mathcal{E}}_{{\text{U}}}}$, the claim follows directly from Equation 9.
∎

See 4.2

###### Proof.

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be two direction-consistent orientations of edges on ${\mathcal{G}}$. Let ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$. Then:

$$ $\displaystyle g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat {{\mathfrak{O}}})$ $\displaystyle=\melinv({\mathcal{G}},\hat{{\mathfrak{O}}}){\bm{X}}_{\text{inv}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},\hat{{\mathfrak{O}}}))^{H} \mboundaryinv({\mathcal{G}},\hat{{\mathfrak{O}}}){\bm{X}}_{\text{inv}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}))^{H}\mboundaryinv({ \mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$ $\displaystyle=\melinv({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$ $\displaystyle=g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{ \mathfrak{O}})$ $$

Here, we directly applied Proposition A.2.
∎

See 4.3

###### Proof.

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be two direction-consistent orientations of edges on ${\mathcal{G}}$ that are valid. Let ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$. Then:

$$ $\displaystyle g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat {{\mathfrak{O}}})$ $\displaystyle=\melequitoinv({\mathcal{G}},\hat{{\mathfrak{O}}}){\Delta_{{ \mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},\hat{{\mathfrak{O}}}))^{H} \mboundaryequi({\mathcal{G}},\hat{{\mathfrak{O}}}){\Delta_{{\mathfrak{O}},\hat {{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}))^{H}\mboundaryequi( {\mathcal{G}},{\mathfrak{O}}){\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{ \Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}))^{H}\mboundaryequi( {\mathcal{G}},{\mathfrak{O}}){\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{ \bm{X}}_{\text{equ}}$ $\displaystyle=\melequitoinv({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{equ}}$ $\displaystyle=g({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{ \mathfrak{O}})$ $$

Here, we used Propositions A.1 and A.2 and the fact that ${\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\Delta_{{\mathfrak{O}},\hat{{
\mathfrak{O}}}}}={\bm{I}}_{m}$.

Let ${\mathfrak{O}},\hat{{\mathfrak{O}}}$ be two direction-consistent orientations of edges on ${\mathcal{G}}$. Let ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$. Then:

$$ $\displaystyle f({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{ equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}})$ $\displaystyle=\melinvtoequi({\mathcal{G}},\hat{{\mathfrak{O}}}){\bm{X}}_{\text {inv}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}},\hat{{\mathfrak{O}}}))^{H} \mboundaryinv({\mathcal{G}},\hat{{\mathfrak{O}}}){\bm{X}}_{\text{inv}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\Delta_{{\mathfrak {O}},\hat{{\mathfrak{O}}}}})^{H}\mboundaryinv({\mathcal{G}},{\mathfrak{O}}){ \bm{X}}_{\text{inv}}$ $\displaystyle=({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}})^{H}( \mboundaryequi({\mathcal{G}},{\mathfrak{O}}))^{H}\mboundaryinv({\mathcal{G}},{ \mathfrak{O}}){\bm{X}}_{\text{inv}}$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}\melinvtoequi({ \mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f({\bm{X}}_{\text{ equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})$ $$

Here, we used Propositions A.1 and A.2 and the fact that $({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}})^{H}={\Delta_{{\mathfrak{O}},
\hat{{\mathfrak{O}}}}}$ as it is a diagonal real matrix.
∎

We now prove that the composition of orientation-equivariant / invariant functions preserves orientation equivariance / invariance, which allows us to prove 4.1 by using Lemmata 4.2, 4.3 and 4.1.

###### Proposition A.3 .

Let $f_{1}$ and $f_{2}$ be jointly orientation-equivariant mappings according to Definition 4.1. Then $f_{1}\circ_{\text{equ}}f_{2}=f_{1}(f_{2}({\bm{X}}_{\text{equ}},{\bm{X}}_{\text
{inv}},{\mathcal{G}},{\mathfrak{O}}),{\bm{X}}_{\text{inv}},{\mathcal{G}},{
\mathfrak{O}})$ is also jointly orientation-equivariant.

###### Proof.

$$ $\displaystyle(f_{1}\circ_{\text{equ}}f_{2})({\Delta_{{\mathfrak{O}},\hat{{ \mathfrak{O}}}}}{\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat {{\mathfrak{O}}})$ $\displaystyle=f_{1}(f_{2}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X }}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}}),{\bm {X}}_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}})$ $\displaystyle=f_{1}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f_{2}({\bm{X }}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}}),{\bm{X}}_{ \text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}})$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f_{1}(f_{2}({\bm{X }}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}}),{\bm{X}}_{ \text{inv}},{\mathcal{G}},{\mathfrak{O}})$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}(f_{1}\circ_{\text {equ}}f_{2})({\bm{X}}_{\text{equ}},{\mathcal{G}},{\mathfrak{O}})$ $$

∎

Next we discuss the relationship between sign-equivariant and jointly orientation-equivariant mappings.

###### Proposition A.4 .

Let $\sigma$ be a sign-equivariant mapping, i.e. $\sigma(-x,-y)=-\sigma(x,y)$ and $f_{1}$ and $f_{2}$ be jointly orientation-equivariant mappings. Then $f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})=
\sigma(f_{1}({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{
\mathfrak{O}}),f_{2}({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}}
,{\mathfrak{O}}))$ is a jointly orientation-equivariant mapping as well.

###### Proof.

$$ $\displaystyle f({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{ equ}},{\mathcal{G}},\hat{{\mathfrak{O}}})$ $\displaystyle=\sigma(f_{1}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{ X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}}),f_{ 2}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}},{\bm{X} }_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}}))$ $\displaystyle=\sigma({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f_{1}({\bm{ X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}}),{\Delta_{ {\mathfrak{O}},\hat{{\mathfrak{O}}}}}f_{2}({\bm{X}}_{\text{equ}},{\bm{X}}_{ \text{inv}},{\mathcal{G}},{\mathfrak{O}}))$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}\sigma(f_{1}({\bm{ X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}}),f_{2}({ \bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}}))$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}f({\bm{X}}_{\text{ equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{O}})$ $$

∎

Note that Proposition A.4 generalizes to sign equivariant functions with one argument by defining $\sigma^{\prime}(x)=\sigma(x,0)$.

We can now prove that ${\bm{H}}^{(l)}_{\text{equ}}$ as defined in Equation 2 is a jointly equivariant mapping.

###### Lemma A.5 .

${\bm{H}}^{(l)}_{\text{equ}}$ as defined in Equation 2 is a jointly orientation-equivariant mapping. ${\bm{H}}^{(l)}_{\text{inv}}$ as defined in Equation 3 is a jointly orientation-invariant mapping.

###### Proof.

The proof is done inductively. Therefore, assume ${\bm{H}}^{(l-1)}_{\text{equ}}$ to be a jointly orientation-equivariant mapping and ${\bm{H}}^{(l-1)}_{\text{inv}}$ to be a jointly orientation-invariant mapping. For notational simplicitly, we absorb the dependency on ${\bm{X}}_{\text{equ}}$, ${\bm{X}}_{\text{inv}}$, ${\mathcal{G}}$ and ${\mathfrak{O}}$ into the mapping itself: That is, for a mapping ${\bm{F}}$, we denote ${\bm{F}}({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{
O}})={\bm{F}}$ and ${\bm{F}}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{X}}_{\text{equ}},{
\bm{X}}_{\text{inv}},{\mathcal{G}},\hat{{\mathfrak{O}}})=\hat{{\bm{F}}}$.

We first show that ${\bm{Z}}^{(l)}_{\text{equ}}$ to be a jointly orientation-equivariant mapping.

$$ $\displaystyle\hat{{\bm{Z}}}^{(l)}_{\text{equ}}$ $\displaystyle=\sigma_{\text{equ}}(\hat{{\bm{L}}}^{(q)}_{\text{equ}}\hat{{\bm{H }}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{equ}}^{(l)}+\hat{ {\bm{L}}}^{(q)}_{\text{inv}\rightarrow\text{equ}}\hat{{\bm{H}}}_{\text{inv}}^{ (l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{equ}}^{(l)}+\hat{{\bm{H}}}_{\text{ equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle=\sigma_{\text{equ}}(\hat{{\bm{L}}}^{(q)}_{\text{equ}}{\Delta_{{ \mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{ \text{equ}\rightarrow\text{equ}}^{(l)}+\hat{{\bm{L}}}^{(q)}_{\text{inv} \rightarrow\text{equ}}{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv} \rightarrow\text{equ}}^{(l)}+{\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{ \bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle=\sigma_{\text{equ}}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}} }}{\bm{L}}^{(q)}_{\text{equ}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ} \rightarrow\text{equ}}^{(l)}+{\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{ \bm{L}}^{(q)}_{\text{inv}\rightarrow\text{equ}}{\bm{H}}_{\text{inv}}^{(l-1)}{ \bm{W}}_{\text{inv}\rightarrow\text{equ}}^{(l)}+{\Delta_{{\mathfrak{O}},\hat{{ \mathfrak{O}}}}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}\sigma_{\text{equ} }({\bm{L}}^{(q)}_{\text{equ}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ} \rightarrow\text{equ}}^{(l)}+{\bm{L}}^{(q)}_{\text{inv}\rightarrow\text{equ}}{ \bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{equ}}^{(l)}+{ \bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{Z}}^{(l)}_{ \text{equ}}$ $$

Here, we first used the induction assumption, then applied the joint orientation equivariance property of $\melequi$ and $\melinvtoequi$ proven in Lemmata 4.1 and 4.3 and lastly used the fact that we assume $\sigma_{\text{equ}}$ to be sign-invariant function to apply Proposition A.4.

Similarily, we can show that ${\bm{Z}}^{(l)}_{\text{equ}}$ to be a jointly orientation-equivariant mapping.

$$ $\displaystyle\hat{{\bm{Z}}}^{(l)}_{\text{inv}}$ $\displaystyle=\sigma_{\text{inv}}(\hat{{\bm{L}}}^{(q)}_{\text{inv}}\hat{{\bm{H }}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+\hat{ {\bm{L}}}^{(q)}_{\text{equ}\rightarrow\text{inv}}\hat{{\bm{H}}}_{\text{equ}}^{ (l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{inv}}^{(l)}+\hat{{\bm{H}}}_{\text{ inv}}^{(l-1)}{\bm{W}}_{\text{inv}}^{(l)})$ $\displaystyle=\sigma_{\text{inv}}(\hat{{\bm{L}}}^{(q)}_{\text{inv}}{\bm{H}}_{ \text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+\hat{{\bm{ L}}}^{(q)}_{\text{equ}\rightarrow\text{inv}}{\Delta_{{\mathfrak{O}},\hat{{ \mathfrak{O}}}}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow \text{inv}}^{(l)}+{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}}^{(l)})$ $\displaystyle=\sigma_{\text{inv}}({\bm{L}}^{(q)}_{\text{inv}}{\bm{H}}_{\text{ inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+{\bm{L}}^{(q)}_{ \text{equ}\rightarrow\text{inv}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{ equ}\rightarrow\text{inv}}^{(l)}+{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{ inv}}^{(l)})$ $\displaystyle={\bm{Z}}^{(l)}_{\text{inv}}$ $$

Here, we first used the induction assumption, then applied the joint orientation invariance property of $\melinv$ and $\melequitoinv$ proven in Lemmata 4.2 and 4.3.

Next, we can show that ${\bm{H}}^{(l)}_{\text{equ}}$ is an orientation-equivariant mapping.

$$ $\displaystyle\hat{{\bm{H}}}^{(l)}_{\text{equ}}$ $\displaystyle=\sigma_{\text{equ}}(\hat{{\bm{Z}}}^{(l)}_{\text{equ}}{\bm{W}}^{( l)}_{\textsc{{F}},\text{equ},\text{equ}}\odot\hat{{\bm{Z}}}^{(l)}_{\text{inv}} {\bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{inv}}+\hat{{\bm{Z}}}^{(l)}_{ \text{equ}})$ $\displaystyle=\sigma_{\text{equ}}(({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}} }}}{\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{ equ}})\odot{\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ}, \text{inv}}+{\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{Z}}^{(l)}_{ \text{equ}})$ $\displaystyle=\sigma_{\text{equ}}({\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}} }}({\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{ equ}}\odot{\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ}, \text{inv}})+{\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{Z}}^{(l)}_{ \text{equ}})$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}\sigma_{\text{equ} }(({\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{ equ}}\odot{\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ}, \text{inv}})+{\bm{Z}}^{(l)}_{\text{equ}})$ $\displaystyle={\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{H}}^{(l)}_{ \text{equ}}$ $$

We first use the previously proven joint orientation equivariance of ${\bm{Z}}^{(l)}_{\text{equ}}$, and then the fact both ${\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}$ and $\odot$ are element-wise multiplications and, therefore, are associative operations. Lastly, we again make use of Proposition A.4 for the sign-equivariant function $\sigma_{\text{equ}}$.

Lastly, we can show that ${\bm{H}}^{(l)}_{\text{inv}}$ is an orientation-invariant mapping.

$$ $\displaystyle\hat{{\bm{H}}}^{(l)}_{\text{inv}}$ $\displaystyle=\sigma_{\text{inv}}(\hat{{\bm{Z}}}^{(l)}_{\text{inv}}{\bm{W}}^{( l)}_{\textsc{{F}},\text{inv},\text{inv}}\odot\operatorname*{abs}(\hat{{\bm{Z}} }^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}})+\hat{ {\bm{Z}}}^{(l)}_{\text{inv}})$ $\displaystyle=\sigma_{\text{inv}}({\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^{(l)}_{ \textsc{{F}},\text{inv},\text{inv}}\odot\operatorname*{abs}({\Delta_{{ \mathfrak{O}},\hat{{\mathfrak{O}}}}}{\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_ {\textsc{{F}},\text{inv},\text{equ}})+{\bm{Z}}^{(l)}_{\text{inv}})$ $\displaystyle=\sigma_{\text{inv}}({\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^{(l)}_{ \textsc{{F}},\text{inv},\text{inv}}\odot\operatorname*{abs}({\bm{Z}}^{(l)}_{ \text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}})+{\bm{Z}}^{(l)} _{\text{inv}})$ $\displaystyle={\bm{H}}^{(l)}_{\text{inv}}$ $$

Here, we first use the previously proven joint orientation invariance of ${\bm{Z}}^{(l)}_{\text{inv}}$. Then, we notice that ${\Delta_{{\mathfrak{O}},\hat{{\mathfrak{O}}}}}$ corresponds to an element-wise multiplication with $\pm 1$ and is therefore canceled out by the element-wise absolute value function.
∎

###### Proposition A.1 .

###### Proof.

###### Proof.

###### Proposition A.2 .

###### Proof.

###### Proof.

###### Proof.

###### Proposition A.3 .

###### Proof.

###### Proposition A.4 .

###### Proof.

###### Lemma A.5 .

###### Proof.

### A.2 Permutation Equivariance

A common requirement for GNNs is equivariance with respect to the ordering of input to enable generalization (Maron et al., ; Wu et al., ). While node-level GNNs are equivariant with respect to node permutations, we require edge-level permutation equivariance.

###### Definition A.1 (Permutation Equivariance) .

Let ${\mathfrak{O}}$ be an orientation of edges on ${\mathcal{G}}$ and ${\bm{P}}\in\mathbb{R}^{m\times m}$ be a permutation matrix on the edges. Let ${\mathfrak{O}}_{\bm{P}}$ and ${\mathcal{G}}_{\bm{P}}$ be its application to ${\mathfrak{O}}$ and ${\mathcal{G}}$ respectively.
We say that a mapping $f$ satisfies permutation equivariance if for any orientation-equivariant signal ${\bm{X}}_{\text{equ}}\in\mathbb{C}^{m\times d_{\text{equ}}}$ and any orientation-invariant signal ${\bm{X}}_{\text{inv}}\in\mathbb{C}^{m\times d_{\text{inv}}}$:

$$ ${\bm{P}}f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak {O}})=f({\bm{P}}{\bm{X}}_{\text{equ}},{\bm{P}}{\bm{X}}_{\text{inv}},{\mathcal{ G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})$ $$

We now proceed to prove that EIGN is a permutation equivariant mapping according to Definition A.1. Again, we first concern boundary operators and show results for the generalized, directed case and recover Equations 4 and 5 with $q=0$.

###### Proposition A.6 .

$\melequi$ is a permutation equivariant mapping according to Definition A.1.

###### Proof.

Let ${\mathfrak{O}}$ be an orientation of edges on ${\mathcal{G}}$ and ${\bm{P}}$ be a permutation matrix. Let ${\mathfrak{O}}_{\bm{P}}$ and ${\mathcal{G}}_{\bm{P}}$ its application to ${\mathfrak{O}}$ and ${\mathcal{G}}$ respectively.

$$ $\displaystyle f({\bm{P}}{\bm{X}}_{\text{equ}},{\bm{P}}{\bm{X}}_{\text{inv}},{ \mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})$ $\displaystyle=\melequi({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){\bm{P}} {\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})) ^{H}\mboundaryequi({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){\bm{P}}{\bm {X}}_{\text{equ}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H})^{H} \mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H}{\bm{P}}{\bm{X}}_{ \text{equ}}$ $\displaystyle={\bm{P}}(\mboundaryequi({\mathcal{G}},{\mathfrak{O}}))^{H} \mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{equ}}$ $\displaystyle={\bm{P}}\melequi{\bm{X}}_{\text{equ}}$ $\displaystyle={\bm{P}}f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{ G}},{\mathfrak{O}})$ $$

∎

###### Proposition A.7 .

$\melinv$ is a permutation invvariant mapping according to Definition A.1.

###### Proof.

Let ${\mathfrak{O}}$ be an orientation of edges on ${\mathcal{G}}$ and ${\bm{P}}$ be a permutation matrix. Let ${\mathfrak{O}}_{\bm{P}}$ and ${\mathcal{G}}_{\bm{P}}$ its application to ${\mathfrak{O}}$ and ${\mathcal{G}}$ respectively.

$$ $\displaystyle g({\bm{P}}{\bm{X}}_{\text{inv}},{\bm{P}}{\bm{X}}_{\text{inv}},{ \mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})$ $\displaystyle=\melinv({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){\bm{P}}{ \bm{X}}_{\text{inv}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}))^ {H}\mboundaryinv({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){\bm{P}}{\bm{X }}_{\text{inv}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H})^{H} \mboundaryinv({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H}{\bm{P}}{\bm{X}}_{\text {inv}}$ $\displaystyle={\bm{P}}(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}))^{H} \mboundaryinv({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$ $\displaystyle={\bm{P}}\melinv{\bm{X}}_{\text{inv}}$ $\displaystyle={\bm{P}}g({\bm{X}}_{\text{inv}},{\bm{X}}_{\text{inv}},{\mathcal{ G}},{\mathfrak{O}})$ $$

∎

###### Proposition A.8 .

$\melequitoinv$ is a permutation equivariant mapping according to Definition A.1.

###### Proof.

Let ${\mathfrak{O}}$ be an orientation of edges on ${\mathcal{G}}$ and ${\bm{P}}$ be a permutation matrix. Let ${\mathfrak{O}}_{\bm{P}}$ and ${\mathcal{G}}_{\bm{P}}$ its application to ${\mathfrak{O}}$ and ${\mathcal{G}}$ respectively.

$$ $\displaystyle f({\bm{P}}{\bm{X}}_{\text{equ}},{\bm{P}}{\bm{X}}_{\text{inv}},{ \mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})$ $\displaystyle=\melequitoinv({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){ \bm{P}}{\bm{X}}_{\text{equ}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}))^ {H}\mboundaryequi({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){\bm{P}}{\bm{ X}}_{\text{equ}}$ $\displaystyle=(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H})^{H} \mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H}{\bm{P}}{\bm{X}}_{ \text{equ}}$ $\displaystyle={\bm{P}}(\mboundaryinv({\mathcal{G}},{\mathfrak{O}}))^{H} \mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{equ}}$ $\displaystyle={\bm{P}}\melequitoinv{\bm{X}}_{\text{equ}}$ $\displaystyle={\bm{P}}f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{ G}},{\mathfrak{O}})$ $$

∎

###### Proposition A.9 .

$\melinvtoequi$ is a permutation equivariant mapping according to Definition A.1.

###### Proof.

Let ${\mathfrak{O}}$ be an orientation of edges on ${\mathcal{G}}$ and ${\bm{P}}$ be a permutation matrix. Let ${\mathfrak{O}}_{\bm{P}}$ and ${\mathcal{G}}_{\bm{P}}$ its application to ${\mathfrak{O}}$ and ${\mathcal{G}}$ respectively.

$$ $\displaystyle f({\bm{P}}{\bm{X}}_{\text{equ}},{\bm{P}}{\bm{X}}_{\text{inv}},{ \mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})$ $\displaystyle=\melinvtoequi({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){ \bm{P}}{\bm{X}}_{\text{inv}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})) ^{H}\mboundaryinv({\mathcal{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}}){\bm{P}}{\bm{ X}}_{\text{inv}}$ $\displaystyle=(\mboundaryequi({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H})^{H} \mboundaryinv({\mathcal{G}},{\mathfrak{O}}){\bm{P}}^{H}{\bm{P}}{\bm{X}}_{\text {inv}}$ $\displaystyle={\bm{P}}(\mboundaryequi({\mathcal{G}},{\mathfrak{O}}))^{H} \mboundaryinv({\mathcal{G}},{\mathfrak{O}}){\bm{X}}_{\text{inv}}$ $\displaystyle={\bm{P}}\melinvtoequi{\bm{X}}_{\text{inv}}$ $\displaystyle={\bm{P}}f({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{ G}},{\mathfrak{O}})$ $$

∎

###### Lemma A.10 .

${\bm{H}}^{(l)}_{\text{equ}}$ and ${\bm{H}}^{(l)}_{\text{inv}}$ as defined in Equation 2 are permutation equivariant mappings.

###### Proof.

The proof is done inductively. Therefore, assume ${\bm{H}}^{(l-1)}_{\text{equ}}$ and ${\bm{H}}^{(l-1)}_{\text{inv}}$ to be a permutation equivariant mappings. For simplicitly, we, again, absorb the dependency on ${\bm{X}}_{\text{equ}}$, ${\bm{X}}_{\text{inv}}$, ${\mathcal{G}}$ and ${\mathfrak{O}}$ into the mapping itself: That is, for a mapping ${\bm{F}}$, we denote ${\bm{F}}({\bm{X}}_{\text{equ}},{\bm{X}}_{\text{inv}},{\mathcal{G}},{\mathfrak{
O}})={\bm{F}}$ and ${\bm{F}}({\bm{P}}{\bm{X}}_{\text{equ}},{\bm{P}}{\bm{X}}_{\text{inv}},{\mathcal
{G}}_{\bm{P}},{\mathfrak{O}}_{\bm{P}})=\tilde{{\bm{F}}}$.

We first show that ${\bm{Z}}^{(l)}_{\text{equ}}$ to be a permutation equivariant mapping.

$$ $\displaystyle\tilde{{\bm{Z}}}^{(l)}_{\text{equ}}$ $\displaystyle=\sigma_{\text{equ}}(\tilde{{\bm{L}}}^{(q)}_{\text{equ}}\tilde{{ \bm{H}}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{equ}}^{(l)}+ \tilde{{\bm{L}}}^{(q)}_{\text{inv}\rightarrow\text{equ}}\tilde{{\bm{H}}}_{ \text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{equ}}^{(l)}+\tilde{{ \bm{H}}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle=\sigma_{\text{equ}}(\tilde{{\bm{L}}}^{(q)}_{\text{equ}}{\bm{P}}{ \bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{equ}}^{(l)}+ \tilde{{\bm{L}}}^{(q)}_{\text{inv}\rightarrow\text{equ}}{\bm{P}}{\bm{H}}_{ \text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{equ}}^{(l)}+{\bm{P}}{ \bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle=\sigma_{\text{equ}}({\bm{P}}{\bm{L}}^{(q)}_{\text{equ}}{\bm{H}}_ {\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{equ}}^{(l)}+{\bm{P}}{ \bm{L}}^{(q)}_{\text{inv}\rightarrow\text{equ}}{\bm{H}}_{\text{inv}}^{(l-1)}{ \bm{W}}_{\text{inv}\rightarrow\text{equ}}^{(l)}+{\bm{P}}{\bm{H}}_{\text{equ}}^ {(l-1)}{\bm{W}}_{\text{equ}}^{(l)})$ $\displaystyle={\bm{P}}\sigma_{\text{equ}}({\bm{L}}^{(q)}_{\text{equ}}{\bm{H}}_ {\text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{equ}}^{(l)}+{\bm{L}}^ {(q)}_{\text{inv}\rightarrow\text{equ}}{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{ \text{inv}\rightarrow\text{equ}}^{(l)}+{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{ \text{equ}}^{(l)})$ $\displaystyle={\bm{P}}{\bm{Z}}^{(l)}_{\text{equ}}$ $$

Here, we first used the induction assumption, then applied the permutation equivariance property of $\melequi$ and $\melinvtoequi$ proven in Propositions A.6 and A.9 and lastly used the fact that we assume $\sigma_{\text{equ}}$ to be an element-wise function which, hence, commutes with permutations.

Similarily, we can show that ${\bm{Z}}^{(l)}_{\text{equ}}$ to be a permutation equivariant mapping.

$$ $\displaystyle\tilde{{\bm{Z}}}^{(l)}_{\text{inv}}$ $\displaystyle=\sigma_{\text{inv}}(\tilde{{\bm{L}}}^{(q)}_{\text{inv}}\tilde{{ \bm{H}}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+ \tilde{{\bm{L}}}^{(q)}_{\text{equ}\rightarrow\text{inv}}\tilde{{\bm{H}}}_{ \text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{inv}}^{(l)}+\tilde{{ \bm{H}}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}}^{(l)})$ $\displaystyle=\sigma_{\text{inv}}(\tilde{{\bm{L}}}^{(q)}_{\text{inv}}{\bm{P}}{ \bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+ \tilde{{\bm{L}}}^{(q)}_{\text{equ}\rightarrow\text{inv}}{\bm{P}}{\bm{H}}_{ \text{equ}}^{(l-1)}{\bm{W}}_{\text{equ}\rightarrow\text{inv}}^{(l)}+{\bm{P}}{ \bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}}^{(l)})$ $\displaystyle=\sigma_{\text{inv}}({\bm{P}}{\bm{L}}^{(q)}_{\text{inv}}{\bm{H}}_ {\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+{\bm{P}}{ \bm{L}}^{(q)}_{\text{equ}\rightarrow\text{inv}}{\bm{H}}_{\text{equ}}^{(l-1)}{ \bm{W}}_{\text{equ}\rightarrow\text{inv}}^{(l)}+{\bm{P}}{\bm{H}}_{\text{inv}}^ {(l-1)}{\bm{W}}_{\text{inv}}^{(l)})$ $\displaystyle={\bm{P}}\sigma_{\text{inv}}({\bm{L}}^{(q)}_{\text{inv}}{\bm{H}}_ {\text{inv}}^{(l-1)}{\bm{W}}_{\text{inv}\rightarrow\text{inv}}^{(l)}+{\bm{L}}^ {(q)}_{\text{equ}\rightarrow\text{inv}}{\bm{H}}_{\text{equ}}^{(l-1)}{\bm{W}}_{ \text{equ}\rightarrow\text{inv}}^{(l)}+{\bm{H}}_{\text{inv}}^{(l-1)}{\bm{W}}_{ \text{inv}}^{(l)})$ $\displaystyle={\bm{P}}{\bm{Z}}^{(l)}_{\text{inv}}$ $$

Here, we first used the induction assumption, then applied the permutation equivariance property of $\melequi$ and $\melinvtoequi$ proven in Propositions A.7 and A.8 and lastly used the fact that we assume $\sigma_{\text{equ}}$ to be an element-wise function which, hence, commutes with permutations.

Next, we can show that ${\bm{H}}^{(l)}_{\text{equ}}$ is an permutation equivariant mapping.

$$ $\displaystyle\tilde{{\bm{H}}}^{(l)}_{\text{equ}}$ $\displaystyle=\sigma_{\text{equ}}(\tilde{{\bm{Z}}}^{(l)}_{\text{equ}}{\bm{W}}^ {(l)}_{\textsc{{F}},\text{equ},\text{equ}}\odot\tilde{{\bm{Z}}}^{(l)}_{\text{ inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{inv}}+\tilde{{\bm{Z}}}^{(l) }_{\text{equ}})$ $\displaystyle=\sigma_{\text{equ}}(({\bm{P}}{\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}} ^{(l)}_{\textsc{{F}},\text{equ},\text{equ}})\odot({\bm{P}}{\bm{Z}}^{(l)}_{ \text{inv}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{inv}})+{\bm{P}}{\bm{Z }}^{(l)}_{\text{equ}})$ $\displaystyle=\sigma_{\text{equ}}({\bm{P}}({\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}} ^{(l)}_{\textsc{{F}},\text{equ},\text{equ}}\odot{\bm{Z}}^{(l)}_{\text{inv}}{ \bm{W}}^{(l)}_{\textsc{{F}},\text{equ},\text{inv}})+{\bm{P}}{\bm{Z}}^{(l)}_{ \text{equ}})$ $\displaystyle={\bm{P}}\sigma_{\text{equ}}({\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^ {(l)}_{\textsc{{F}},\text{equ},\text{equ}}\odot{\bm{Z}}^{(l)}_{\text{inv}}{\bm {W}}^{(l)}_{\textsc{{F}},\text{equ},\text{inv}}+{\bm{Z}}^{(l)}_{\text{equ}})$ $\displaystyle={\bm{P}}{\bm{H}}^{(l)}_{\text{equ}}$ $$

We first use the previously proven joint permutation equivariance of ${\bm{Z}}^{(l)}_{\text{equ}}$, and then the fact both $\sigma_{\text{equ}}$ and $\odot$ are element-wise operations and, therefore, commute with permutations.

Lastly, we can show that ${\bm{H}}^{(l)}_{\text{inv}}$ is an orientation-invariant mapping.

$$ $\displaystyle\tilde{{\bm{H}}}^{(l)}_{\text{inv}}$ $\displaystyle=\sigma_{\text{inv}}(\tilde{{\bm{Z}}}^{(l)}_{\text{inv}}{\bm{W}}^ {(l)}_{\textsc{{F}},\text{inv},\text{inv}}\odot\operatorname*{abs}(\tilde{{\bm {Z}}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}})+ \tilde{{\bm{Z}}}^{(l)}_{\text{inv}})$ $\displaystyle=\sigma_{\text{inv}}(({\bm{P}}{\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}} ^{(l)}_{\textsc{{F}},\text{inv},\text{inv}})\odot(\operatorname*{abs}({\bm{P}} {\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}} ))+{\bm{P}}{\bm{Z}}^{(l)}_{\text{inv}})$ $\displaystyle=\sigma_{\text{inv}}(({\bm{P}}{\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}} ^{(l)}_{\textsc{{F}},\text{inv},\text{inv}})\odot({\bm{P}}\operatorname*{abs}( {\bm{Z}}^{(l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}} ))+{\bm{P}}{\bm{Z}}^{(l)}_{\text{inv}})$ $\displaystyle=\sigma_{\text{inv}}({\bm{P}}({\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}} ^{(l)}_{\textsc{{F}},\text{inv},\text{inv}}\odot\operatorname*{abs}({\bm{Z}}^{ (l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}}))+{\bm{P} }{\bm{Z}}^{(l)}_{\text{inv}})$ $\displaystyle={\bm{P}}\sigma_{\text{inv}}({\bm{Z}}^{(l)}_{\text{inv}}{\bm{W}}^ {(l)}_{\textsc{{F}},\text{inv},\text{inv}}\odot\operatorname*{abs}({\bm{Z}}^{( l)}_{\text{equ}}{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv},\text{equ}})+{\bm{Z}}^ {(l)}_{\text{inv}})$ $\displaystyle={\bm{P}}{\bm{H}}^{(l)}_{\text{inv}}$ $$

Here, we first use the previously proven joint permutation equivariance of ${\bm{Z}}^{(l)}_{\text{inv}}$, and then the fact $\sigma_{\text{inv}}$, $\operatorname*{abs}$ and $\odot$ are element-wise operations and, therefore, commute with permutations.
∎

###### Definition A.1 (Permutation Equivariance) .

###### Proposition A.6 .

###### Proof.

###### Proposition A.7 .

###### Proof.

###### Proposition A.8 .

###### Proof.

###### Proposition A.9 .

###### Proof.

###### Lemma A.10 .

###### Proof.

### A.3 The Main Result

We can now plug Lemmas A.5 and A.10 together and prove 4.1.

See 4.1

###### Proof.

The proof of (i) and (ii) is directly given by Lemma A.5. The proof of (iii) is directly given by Lemma A.10.
∎

###### Proof.

## Appendix B The Laplace Operators of EIGN

Here, we explicitly list the definitions of all Laplace operators and briefly describe some intuition. This is supplementary to the description for the Equivariant Edge Laplacian ${\bm{L}}_{\text{equ}}$ in Section 4.3. Intuitively speaking, each Laplacian is a composition of two boundary operators. Therefore, the message passing from an adjacent edge $e^{\prime}\in{\mathcal{E}}$ to a target edge $e\in{\mathcal{E}}$ can be understood as a two-step procedure:
1. The signal of $e^{\prime}$ is expressed relative to the node both $e$ and $e^{\prime}$ are incident to. This corresponds to the right-hand term in the construction of the Laplacian. Expressing the signal on the node level makes it invariant to the orientation (if the suitable boundary operator was used, i.e. the orientation-equivariant boundary for an orientation-equivariant signal and vice versa).
2. The signal of $e^{\prime}$, currently expressed in reference to the shared node (ingoing versus outgoing), is then expressed relative to $e$. This corresponds to the left-hand term in the construction of the Laplacian from composing two boundaries. Depending on which boundary operator is used, this signal will be orientation-equivariant or orientation-invariant.

**Table 5: Realization of different Laplacian operators for directed edges $\longrightarrow$ and undirected (oriented) edges $\Longrightarrow$. Equivariant operators encode if two edge orientations/directions align, i.e. whether they are non-consecutive through the sign of the real part. The sign of the complex phase determines the direction relative to the reference node both edges are incident to, i.e. whether they are in- or outgoing. The relative orientation (alignment) of two edges is ignored by orientation-invariant operators. We omit the cases for which the direction/orientation of both $e$ and $e^{\prime}$ are flipped (this realizes a different sign in the complex phase).**
| Adjacency | $[{\bm{L}}_{\text{equ}}]_{e,e^{\prime}}$ | $[\melequi]_{e,e^{\prime}}$ | $[{\bm{L}}_{\text{inv}}]_{e,e^{\prime}}$ | $[\melinv]_{e,e^{\prime}}$ | $[\melequitoinv]_{e,e^{\prime}}$ | $[\melinvtoequi]_{e,e^{\prime}}$ |
| --- | --- | --- | --- | --- | --- | --- |
| $e=e^{\prime}$ | $2$ | $2$ | $2$ | $2$ | $2$ | $2$ |
| $\overset{e}{\longrightarrow}\overset{e^{\prime}}{\longrightarrow}$ | ${\color[rgb]{0.87109375,0.5625,0.01171875}\definecolor[named]{pgfstrokecolor}{<br>rgb}{0.87109375,0.5625,0.01171875}\pm}1$ | $\exp({\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}2\pi q)$ | $1$ | $\exp({\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}2\pi iq)$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\mp}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}2\pi iq)$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}2\pi iq)$ |
| $\overset{e}{\longrightarrow}\overset{e^{\prime}}{\longleftarrow}$ | $1$ | $1$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}1$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}1$ |  |  |
| $\overset{e}{\longrightarrow}\overset{e^{\prime}}{\Longrightarrow}$ | ${\color[rgb]{0.87109375,0.5625,0.01171875}\definecolor[named]{pgfstrokecolor}{<br>rgb}{0.87109375,0.5625,0.01171875}\pm}1$ | ${\color[rgb]{0.87109375,0.5625,0.01171875}\definecolor[named]{pgfstrokecolor}{<br>rgb}{0.87109375,0.5625,0.01171875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}\pi iq)$ | $1$ | $\exp({\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\pi iq)$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\mp}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}\pi iq)$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}\pi iq)$ |
| $\overset{e}{\Longrightarrow}\overset{e^{\prime}}{\longrightarrow}$ |  |  |  |  |  |  |
| $\overset{e}{\longrightarrow}\overset{e^{\prime}}{\Longleftarrow}$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}\pi iq)$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\pm}\pi iq)$ |  |  |  |  |
| $\overset{e}{\Longrightarrow}\overset{e^{\prime}}{\longleftarrow}$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\mp}\pi iq)$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}\exp({\color[rgb]{<br>0.00390625,0.44921875,0.69921875}\definecolor[named]{pgfstrokecolor}{rgb}{<br>0.00390625,0.44921875,0.69921875}\mp}\pi iq)$ |  |  |  |  |
| $\overset{e}{\Longrightarrow}\overset{e^{\prime}}{\Longrightarrow}$ | ${\color[rgb]{0.87109375,0.5625,0.01171875}\definecolor[named]{pgfstrokecolor}{<br>rgb}{0.87109375,0.5625,0.01171875}\pm}1$ | ${\color[rgb]{0.87109375,0.5625,0.01171875}\definecolor[named]{pgfstrokecolor}{<br>rgb}{0.87109375,0.5625,0.01171875}\pm}1$ | $1$ | $1$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\mp}1$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}1$ |
| $\overset{e}{\Longrightarrow}\overset{e^{\prime}}{\Longleftarrow}$ | ${\color[rgb]{0.00390625,0.44921875,0.69921875}\definecolor[named]{<br>pgfstrokecolor}{rgb}{0.00390625,0.44921875,0.69921875}\pm}1$ |  |  |  |  |  |

The values in Table 5 assume values based on if
(i) $e$and $e^{\prime}$ align (i.e. are not consecutive). If they align, the first value is assumed, if they misalign, the second.
(ii) The direction of $e$ relative to the node. For the direction depicted in Table 5, the first value is assumed. Flipping the orientation / direction of both edges gives the second value.

Based on this intuition, we interpret how the Laplacians of EIGN materialize in Table 5. We can see that only the Magnetic Laplacians are direction-aware and ${\bm{L}}_{\text{equ}}$ and ${\bm{L}}_{\text{inv}}$ do not depend on the direction. Furthermore, messages between two directed edges experience phase shifts twice: Once when being emitted from the directed source edge and once when being aggregated by the target edge. If the two directions are aligned, these phase shifts cancel out ($\overset{e}{\longrightarrow}\overset{e^{\prime}}{\longleftarrow}$). Otherwise, they add to a total phase shift of $2\pi q$. One can also see that which direction an edge has (relative to the shared incident node) is encoded in the sign (i.e. direction) of the complex phase shift for both $\melequi$ and $\melinv$. The key difference between the orientation-equivariant $\melequi$ and the orientation-invariant $\melinv$ is that the former also re-orients signals depending on if the edges align, similar to ${\bm{L}}_{\text{equ}}$. The Fusion Laplacians $\melequitoinv$ and $\melinvtoequi$ mix both modalities and therefore can not be categorized intuitively as easily.

## Appendix C Experimental Details

### C.1 Datasets

Here, we detail statistics for all datasets and the exact generation process for synthetic data. An overview of the statistics of each dataset is given in Table 6.

**Table 6: Average performance of models on synthetic tasks (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Dataset | #Graphs | #Nodes | #Edges | #Features |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| Dir. | Total | Equ. | Inv. |  |  |  |
| RW Comp | 1000 | 50 | 161–249 | 161–249 | 0 | 2 |
| LD Cycles | 1000 | 12–16 | 16–31 | 25–33 | 0 | 1 |
| Tri-Flow | 100 | 300 | 245–282 | 400 | 1 | 3 |
| Anaheim | 1 | 416 | 354 | 634 | 0 | 7 |
| Barcelona | 1 | 930 | 1074 | 1798 | 0 | 8 |
| Chicago | 1 | 933 | 0 | 1475 | 0 | 9 |
| Winnepeg | 1 | 1040 | 354 | 1595 | 0 | 7 |
| Circuits | 591 | 8–12 | 0–7 | 12–20 | 1 | 4 |

RW Comp. In this inductive setting, we generate $1,000$ Erdős–Rényi graphs Erdos et al. () with $n=50$ nodes and choose the edge probability such that the expected number of edges is $200$. All edges are directed. Each graph is assigned a transition probability sampled uniformly from $[0,1]$. For each graph, we sample a random walk starting from a randomly selected node (uniform probabilities) up to length $100$. We then randomly select $20\%$ of the sampled transitions and provide them as orientation-invariant features as one-hot encoding and the transition probabilities. The task is to predict if a node is part of the $80\%$ nodes in the random walk that are not provided as an input, i.e. a binary classification problem. We use a $70/10/20$ split to assign graphs to train, validation, and test sets respectively.

LD Cycles. In this inductive setting, we generate $1,000$ graphs and sample a cycle size $c$ uniformly from $[6,8]$. We then generate two cycles, each consisting of $c$ nodes: The first one contains only directed and consecutive edges. The second one is similar but contains one undirected edge. To each cycle, we then add additional $c$ random edges between its nodes, each of which is directed with a probability of $25\%$. We ensure that no second consecutive, purely directed cycle of length $c$ is manually formed in this process. Lastly, we connect both cycles with an edge that, too, is directed with a probability of $25\%$. Therefore, each graph can be seen as consisting of two components: One contains one consecutive, purely directed cycle of length $c$, while the other contains a non-purely directed, consecutive cycle of the same length. The task is to classify edges as being part of the longest purely-directed cycle or not. We provide the constant $1$ vector as a surrogate orientation-invariant input, and, therefore, this task is purely topological. Models need to understand the concept of edge direction to perform well in this setting. Again, we use a $70/10/20$ split for the graphs.

Tri-Flow. In this inductive setting, we construct $100$ graphs with $n=300$ nodes and $m=400$ edges. We want to induce a relationship between orientation-invariant and orientation-equivariant features. We assign each edge one of $c=3$ colors as an orientation-invariant feature. We then plant $t=100$ disjoint triangles in the graph. Each triangle is constructed according to one of three patterns:
(i) Triangles with at least one directed edge, all edges of the same color.
(ii) Triangles with edges of the same color, but at least two edges are directed and ensure that the triangle can not be consecutive.
(iii) Triangles with edges of different colors.
We generate $50\%$ of triangles with mechanism (i), and $25\%$ with mechanisms (ii) and (iii) respectively. We then add $100$ random edges to connect the triangles and ensure that no new triangles are formed. For the task of this problem, we introduce an orientation-equivariant flow at each edge and the task is to re-orient these flow labels such that flows within triangles are closed. To that end, in the solution to this task, flow along directed edges must follow the edge direction while undirected edges permit flow in both directions. We introduce a dependency to orientation-invariant features by requiring that flow can only pass through triangles of the same color. That is, the target for triangles of type (i) is to re-orient the flow correctly such that it is closed within the monochromatic triangle. Triangles of type (ii) contain two directed edges that prevent consecutiveness and therefore, the target is 0 0 as no flow is permitted through such triangles. The same holds for triangles of type (iii) that prohibit flow as their edges are not monochromatic. We then add $100$ edges, while ensuring no new triangles of type (i) are formed, that, consequentially, also have a target of 0 0. This task, therefore, involves understanding and relating the concepts of direction, orientation, color (which is orientation-invariant), and flow (which is orientation-equivariant). It probes all possible modalities an edge-level GNN can be exposed to. We again split each of the graphs into train, validation, and test sets using a $70/10/20$ split.

Traffic Datasets.
We collect the Anaheim, Barcelona, Chicago, and Winnipeg datasets from the TNTP transportation network repository (Stabler et al., ). This project studies the Traffic Assignment Problem (Patriksson, ) and provides flows that correspond to the best-known solutions in terms of lowest Average Excess Cost (Boyce et al., ). We select these graphs based on that they are decently sized, provide both orientation-invariant features, and contain directed edges. Nodes correspond to intersections while edges represent links, e.g. streets. We use the following as orientation-invariant inputs (if available):
(i) capacity,
(ii) length,
(iii) free flow time (i.e. travel time with no congestion),
(iv) B factor and power, which are calibration parameters for the Traffic Assignment Problem,
(v) if there is a toll on the link, and
(vi) the link type, e.g. highway.
The topology is preprocessed as follows: The input data is entirely directed, and, therefore, we aggregate edges $(u,v)$ and $(v,u)$ into one undirected edge if both are present. The flow labels are combined using subtraction (i.e. we subtract the from the edge direction that is used as a reference orientation to represent the flow). We then normalize the orientation-invariant features to follow a standard normal and normalize the target flows to $[0,1]$.

Electrical Circuits.
We generate random topologies with the following procedure: First, a cycle of length $c_{\text{init}}=3$ is generated. Then, we iteratively attach new nodes $v$ to the graph by selecting random source and sink nodes $s,t$ and adding the edges $(s,v)$ and $(v,t)$. We then randomly assign different component types to each edge:
(i) exactly one power outlet,
(ii) resistors with a resistance uniformly sampled from $[100\Omega,10,000\Omega]$,
(iii) diodes with saturation current $18.8nA$, parasitic resistance $0\Omega$, reverse breakdown voltage $0.5\mu V$, zero-bias junction capacitance $30F$, a linearly graded junction, emission coefficient of $2.0$ and transit time of $0s$.
Diodes only permit current to flow in one direction.
The ratio of resistors and diodes is $80/20$. We then use LTSpice (Asadi, ) to simulate the currents at each edge and voltages at each node until a steady state is reached. We use the component type and resistance at resistors as orientation-invariant features and normalize the latter to follow a standard normal distribution. The voltage along the power outlet is the only orientation-equivariant input signal, and we assign 0 0 to all the other edges. For each graph we individually normalize the currents: First, we divide by the voltage at the power outlet. We then also normalize the currents again by dividing by the standard deviation of all flows on all graphs, i.e. a constant.

### C.2 Tasks

Denoising.
The first task is denoising the flow signal of traffic data and circuits. To that end, for each graph, we compute the standard deviation $\sigma_{y}$ of all flows and then add noise sampled uniformly from $[-\sigma_{y},\sigma_{y}]$ to all edges. The task is to recover the original signal, which we measure with the Root Mean Squared Error (RMSE) ($\downarrow$). Since the additional orientation-invariant input, the noisy flow provides a strong signal for the direction of the target, it is, arguably, considered to be the easiest of the three tasks.

Interpolation.
The second task is predicting the traffic flow / current from only a few ground-truth values. To that end, for each graph, we provide $10\%$ of the true flow labels as an additional orientation-equivariant input and set the rest to 0 0. The task is to predict the orientation-equivariant flow at edges for which flow was not provided. Again, we use RMSE as the main evaluation metric. Similar to the denoising task, the auxiliary orientation-invariant input signal can provide information about the true direction of the orientation-equivariant target. Since this information is now only available at some edges, we consider the interpolation task to be harder.

Simulation.
The third task is predicting the orientation-equivariant target (traffic flow / electrical current) from just the topology and available orientation-equivariant and orientation-invariant features. This task can be seen as learning to simulate the traffic flow / electrical current. An effective model has to learn the underlying physical processes the data is derived from. Since we do not provide any input regarding the direction of the orientation-equivariant target, we consider this task to be the hardest problem among the three. Again, we can measure the performance of a model using RMSE but also report the Mean Absolute Error (MAE) ($\downarrow$) and $R^{2}$ value ($\uparrow$).

### C.3 Model Architecture

MLP.
We use a standard MLP with ReLU activations. We concatenate both orientation-equivariant and orientation-invariant inputs as a model input. This, effectively, mistreats orientation-equivariant input signals as orientation-invariant. The same is true for the orientation-equivariant model output/target.

LineGraph. Similar to the MLP, we concatenate orientation-equivariant and orientation-invariant inputs, thereby mistreating the equivariant modality, and successively apply convolutions with the Line Graph Laplacian ${\bm{L}}_{\textsc{{LineGraph}}}={\bm{D}}_{\textsc{{LineGraph}}}-{\bm{A}}_{
\textsc{{LineGraph}}}$:

$$ $[{\bm{A}}_{\textsc{{LineGraph}}}]_{e,e^{\prime}}=\begin{cases}1&\text{if }e \neq e^{\prime}\text{ and }e,e^{\prime}\text{ adjacent}\\ 0&\text{otherwise}\end{cases}$ (10) $$

Here, ${\bm{D}}_{\textsc{{LineGraph}}}$ is a diagonal matrix of edge degrees, i.e. $[{\bm{D}}_{\textsc{{LineGraph}}}]_{e,e}=\sum_{e^{\prime}}[{\bm{A}}_{\textsc{{
LineGraph}}}]_{e,e^{\prime}}$. A LineGraph convolution is then realized as:

$$ ${\bm{H}}^{(l)}=\sigma({\bm{L}}_{\textsc{{LineGraph}}}{\bm{H}}^{(l-1)}{\bm{W}}^ {(l)}+{\bm{b}}^{(l)})$ (11) $$

Here, $\sigma$ is the ReLU non-linearity, and ${\bm{W}}^{(l)}$ and ${\bm{b}}^{(l)}$ are the trainable model parameters.

HodgeGNN. We use the HodgeGNNarchitecture of Roddenberry & Segarra (), which is a (jointly) orientation-equivariant architecture. It, however, can not model orientation-invariant inputs, as it treats all input signals as equivariant. We therefore do not input this modality at all. Each layer uses the Equivariant Edge Laplacian ${\bm{L}}_{\text{equ}}$ as a convolution operator.

$$ ${\bm{H}}^{(l)}=\sigma_{\text{equ}}({\bm{L}}_{\text{equ}}{\bm{H}}^{(l-1)}{\bm{W }}^{(l)})$ (12) $$

Here, $\sigma_{\text{equ}}$ is a sign-equivariant activation function, which we initialize as $\tanh$. To not break (joint) orientation equivariance, we can not use a bias term.

Hodge+Inv. We use the same architecture as for HodgeGNN, but also concatenate the orientation-invariant inputs to the orientation-equivariant inputs. This incorrectly models orientation-invariant signals as orientation-equivariant.

Hodge+Dir. We use the same architecture as for HodgeGNN, but use the ReLU as an activation function instead of the sign-equivariant $\tanh$. This breaks (joint) orientation equivariance: The model is now sensitive to the chosen orientation and, therefore, can be seen as direction-aware. However, this holds for all edges, and hence Hodge+Dir can also not model undirected edges anymore.

EIGN. We realize EIGN according to Equations 2, 3, 4 and 5. We realize the sign-equivariant activation $\sigma_{\text{equ}}$ as $\tanh$ to ensure joint orientation equivariance (see Appendix A. In the main text, we omitted biases for brevity. However, to not violate joint orientation equivariance, biases can only be used when the output of the affine transformation is not orientation-equivariant, i.e. orientation-invariant. Consequently, the following linear transformations are supplied with biases: ${\bm{W}}^{(l)}_{\text{inv}\rightarrow\text{inv}},{\bm{W}}^{(l)}_{\text{equ}
\rightarrow\text{inv}},{\bm{W}}^{(l)}_{\text{inv}},{\bm{W}}^{(l)}_{\textsc{{F}
},\text{inv}\rightarrow\text{equ}},{\bm{W}}^{(l)}_{\textsc{{F}},\text{inv}
\rightarrow\text{inv}}$.

A second caveat is that EIGN’s convolution operators output complex-valued signals. While one could, in general, backpropagate through such signals as well, we instead flatten the output signal of each convolution operation by concatenating real and imaginary parts. Notice that this operation is sign-invariant:

$$ $\displaystyle\textsc{{FLATTEN}}(-{\bm{X}})$ $\displaystyle=(-\operatorname*{Re}({\bm{X}}))\mathbin{\|}(-\operatorname*{Im}( {\bm{X}}))$ (13) $\displaystyle=-(\operatorname*{Re}({\bm{X}})\mathbin{\|}\operatorname*{Im}({ \bm{X}}))$ (14) $\displaystyle=-\textsc{{FLATTEN}}({\bm{X}})$ (15) $$

By Proposition A.4, applying this flattening operation, therefore, preserves orientation-equivariance. Orientation invariance is trivially preserved as there are no restrictions on the mappings applied to this signal modality as long as they are orientation-independent. This way, all model weights act on real-valued signals. Due to the concatenation of real and imaginary values, we keep hidden dimensions consistent by letting the affine / linear transformations project into a space of half the desired dimension. We fix the complex phase shift to $q=m^{-1}$, as this is the longest cycle length possible in any graph.

Third, we apply a final linear/affine transformation to the representation of the last layer (for the respective signal modality) ${\bm{H}}^{(L)}_{(\cdot)}$. In the case of orientation-invariant outputs, we can use an affine transformation with biases as orientation-independent transformations do not affect joint orientation invariance. For orientation-equivariant outputs, we have to omit biases and use a linear transformation only. This linear transformation is a sign-equivariant function and, again, preserves joint orientation equivariance as per Proposition A.4.

Lastly, we also omit the normalization of the Laplacians in the main text. Each Laplacian ${\bm{L}}^{(\cdot)}_{(\cdot)}$ is normalized symmetrically:

$$ $\tilde{{\bm{L}}}^{(\cdot)}_{(\cdot)}=({\bm{D}}_{(\cdot)}^{(\cdot)})^{-0.5}{\bm {L}}^{(\cdot)}_{(\cdot)}({\bm{D}}_{(\cdot)}^{(\cdot)})^{-0.5}$ (16) $$

Here, $[({\bm{D}}_{(\cdot)}^{(\cdot)})^{-0.5}]_{e,e}=\sum_{e^{\prime}}[\operatorname*
{abs}({\bm{L}}^{(\cdot)}_{(\cdot)})]_{e,e^{\prime}}$ is a diagonal matrix of degrees of the Laplacian.

Since the normalization is independent of the orientation (due to the absolute value), it does not affect joint orientation equivariance or invariance.

### C.4 Training Setup

For all models, including the baselines, we perform an extensive hyperparameter search to select the most suitable configuration. To that end, we perform $20$ different data splits for each hyperparameter configuration and compare the average performance to select the best hyperparameter configuration for each model. We search a cartesian grid of the following hyperparameter options:

- •
Learning Rate: $\{0.03,0.01,0.003,0.001\}$
- •
Hidden Dimension: $\{8,16,32\}$
- •
Number of Layers: $\{2,3,4\}$

For the LD Cycles, we always fix the number of layers to the cycle size $c$ since our convolution operators are local and cycles can not be detected if the receptive field of an edge can not access the entire cycle.

In all reported results here, we compute average metrics over $50$ different dataset splits and also provide the $95\%$ confidence interval for the mean.

All models are trained with the ADAM optimizer with no weight decay, a mean-squared error objective for regression problems, and cross-entropy for classification tasks. We clip gradients to norm $1$ and apply dropout (Srivastava et al., ) with probability $0.1$ after every layer. We use the following configurations for each dataset:

- •
Electrical Circuits: Batch size of $10$ graphs, $200$ epochs.
- •
Traffic Datasets: Batch size of $1$, $500$ epochs.
- •
RW Comp, LD Cycles: Batch size of $10$ graphs, $50$ epochs.
- •
Tri-Flow: Batch size of $1$ graph, $50$ epochs.

For the denoising task, we use a train/validation/test split of $40/10/50$, for the interpolation and simulation tasks as well as all synthetic tasks we use $70/10/20$. We track the validation RMSE over all epochs and select the model with the best validation metric. We implement our models in PyTorch (Paszke et al., ) and PyTorch Geometric (Fey & Lenssen, ) and train on these types of GPUs:
(i) NVIDIA GTX 1080TI GPU
(ii) NVIDIA A100 GPU
(iii) NVIDIA H100 GPU
.

## Appendix D Additional Results

Here, we report average results over $50$ runs with the best-found hyperparameter configuration for every model. We also report the $95\%$ confidence interval for the mean.

Synthetic Tasks and Simulation. We supply the confidence intervals for tables Tables 2 and 3 in Tables 7 and 10. Additionally, we report Mean Absolute Error (MAE) ($\downarrow$) and $R^{2}$ score ($\uparrow$) for the simulation task in Tables 11 and 12. The findings are consistent with the RMSE metric.

Denoising and Interpolation. We show the RMSE for the denoising task in Table 8. EIGN achieves the best results on four out of five datasets. Because the noisy flow input makes this problem significantly easier, some baselines achieve satisfactory performance and the gap to EIGN is not as pronounced as in the challenging simulation task. We make similar observations for the interpolation problem in Table 9.

Ablation. We supply the confidence intervals for the mean RMSE of Table 4 in Table 13. Additionally, we visualize the distribution of simulated electrical currents (orientation-equivariant targets) in Figure 6. Similar to Figure 5, we find that the direction-aware EIGN provides physically more plausible predictions. The non-negativity constraint imposed by diodes is learned to a lesser extent than on the Anaheim dataset (Figure 5).

**Table 7: Average performance of models on synthetic tasks (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Model | RW Comp<br>AUC-ROC($\uparrow$) | LD Cycles<br>AUC-ROC($\uparrow$) | Tri-Flow<br>RMSE($\downarrow$) |
| --- | --- | --- | --- |
| MLP | $0.720$$\scriptscriptstyle{\pm 0.001}$ | $0.500$$\scriptscriptstyle{\pm 0.000}$ | $0.546$$\scriptscriptstyle{\pm 0.001}$ |
| LineGraph | $0.758$$\scriptscriptstyle{\pm 0.001}$ | $0.684$$\scriptscriptstyle{\pm 0.001}$ | $0.498$$\scriptscriptstyle{\pm 0.002}$ |
| HodgeGNN | $0.500$$\scriptscriptstyle{\pm 0.000}$ | $0.500$$\scriptscriptstyle{\pm 0.000}$ | $0.459$$\scriptscriptstyle{\pm 0.002}$ |
| Hodge+Inv | $0.811$$\scriptscriptstyle{\pm 0.001}$ | $0.753$$\scriptscriptstyle{\pm 0.002}$ | 0.291$\scriptscriptstyle{\pm 0.002}$ |
| Hodge+Dir | 0.819$\scriptscriptstyle{\pm 0.001}$ | 0.802$\scriptscriptstyle{\pm 0.003}$ | $0.293$$\scriptscriptstyle{\pm 0.002}$ |
| EIGN | 0.862$\scriptscriptstyle{\pm 0.001}$ | 0.996$\scriptscriptstyle{\pm 0.000}$ | 0.036$\scriptscriptstyle{\pm 0.002}$ |

**Table 8: Average RMSE ($\downarrow$) of different for the denoising task on real-world datasets (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Model | Anaheim | Barcelona | Chicago | Winnipeg | Circuits |
| --- | --- | --- | --- | --- | --- |
| MLP | $0.079$$\scriptscriptstyle{\pm 0.001}$ | $0.067$$\scriptscriptstyle{\pm 0.001}$ | $0.048$$\scriptscriptstyle{\pm 0.001}$ | $0.076$$\scriptscriptstyle{\pm 0.001}$ | $0.453$$\scriptscriptstyle{\pm 0.005}$ |
| LineGraph | $0.076$$\scriptscriptstyle{\pm 0.001}$ | $0.069$$\scriptscriptstyle{\pm 0.001}$ | $0.047$$\scriptscriptstyle{\pm 0.001}$ | $0.074$$\scriptscriptstyle{\pm 0.001}$ | $0.437$$\scriptscriptstyle{\pm 0.006}$ |
| HodgeGNN | $0.082$$\scriptscriptstyle{\pm 0.002}$ | $0.065$$\scriptscriptstyle{\pm 0.001}$ | $0.047$$\scriptscriptstyle{\pm 0.001}$ | $0.068$$\scriptscriptstyle{\pm 0.001}$ | $0.354$$\scriptscriptstyle{\pm 0.005}$ |
| Hodge+Inv | $0.072$$\scriptscriptstyle{\pm 0.002}$ | $0.062$$\scriptscriptstyle{\pm 0.001}$ | $0.051$$\scriptscriptstyle{\pm 0.001}$ | $0.067$$\scriptscriptstyle{\pm 0.001}$ | $0.353$$\scriptscriptstyle{\pm 0.006}$ |
| Hodge+Dir | 0.068$\scriptscriptstyle{\pm 0.001}$ | 0.059$\scriptscriptstyle{\pm 0.001}$ | 0.045$\scriptscriptstyle{\pm 0.001}$ | 0.062$\scriptscriptstyle{\pm 0.001}$ | 0.306$\scriptscriptstyle{\pm 0.006}$ |
| EIGN | 0.065$\scriptscriptstyle{\pm 0.001}$ | 0.060$\scriptscriptstyle{\pm 0.001}$ | 0.040$\scriptscriptstyle{\pm 0.001}$ | 0.058$\scriptscriptstyle{\pm 0.001}$ | 0.275$\scriptscriptstyle{\pm 0.008}$ |

**Table 9: Average RMSE ($\downarrow$) of different for the interpolation task on real-world datasets (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Model | Anaheim | Barcelona | Chicago | Winnipeg | Circuits |
| --- | --- | --- | --- | --- | --- |
| MLP | $0.095$$\scriptscriptstyle{\pm 0.002}$ | $0.148$$\scriptscriptstyle{\pm 0.002}$ | $0.110$$\scriptscriptstyle{\pm 0.002}$ | $0.167$$\scriptscriptstyle{\pm 0.002}$ | $1.001$$\scriptscriptstyle{\pm 0.024}$ |
| LineGraph | $0.091$$\scriptscriptstyle{\pm 0.003}$ | $0.147$$\scriptscriptstyle{\pm 0.002}$ | $0.110$$\scriptscriptstyle{\pm 0.002}$ | $0.163$$\scriptscriptstyle{\pm 0.002}$ | $1.014$$\scriptscriptstyle{\pm 0.029}$ |
| HodgeGNN | $0.249$$\scriptscriptstyle{\pm 0.003}$ | $0.166$$\scriptscriptstyle{\pm 0.001}$ | 0.108$\scriptscriptstyle{\pm 0.002}$ | $0.166$$\scriptscriptstyle{\pm 0.002}$ | $0.987$$\scriptscriptstyle{\pm 0.030}$ |
| Hodge+Inv | $0.097$$\scriptscriptstyle{\pm 0.002}$ | 0.142$\scriptscriptstyle{\pm 0.002}$ | 0.108$\scriptscriptstyle{\pm 0.002}$ | 0.156$\scriptscriptstyle{\pm 0.002}$ | $0.825$$\scriptscriptstyle{\pm 0.022}$ |
| Hodge+Dir | 0.086$\scriptscriptstyle{\pm 0.002}$ | 0.145$\scriptscriptstyle{\pm 0.002}$ | $0.113$$\scriptscriptstyle{\pm 0.002}$ | 0.156$\scriptscriptstyle{\pm 0.002}$ | 0.786$\scriptscriptstyle{\pm 0.021}$ |
| EIGN | 0.084$\scriptscriptstyle{\pm 0.003}$ | $0.148$$\scriptscriptstyle{\pm 0.005}$ | 0.079$\scriptscriptstyle{\pm 0.004}$ | 0.129$\scriptscriptstyle{\pm 0.006}$ | 0.485$\scriptscriptstyle{\pm 0.025}$ |

**Table 10: Average RMSE ($\downarrow$) of different for the simulation task on real-world datasets (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Model | Anaheim | Barcelona | Chicago | Winnipeg | Circuits |
| --- | --- | --- | --- | --- | --- |
| MLP | $0.096$$\scriptscriptstyle{\pm 0.002}$ | $0.150$$\scriptscriptstyle{\pm 0.001}$ | $0.111$$\scriptscriptstyle{\pm 0.002}$ | $0.165$$\scriptscriptstyle{\pm 0.002}$ | $1.036$$\scriptscriptstyle{\pm 0.013}$ |
| LineGraph | $0.087$$\scriptscriptstyle{\pm 0.003}$ | $0.147$$\scriptscriptstyle{\pm 0.003}$ | $0.112$$\scriptscriptstyle{\pm 0.002}$ | $0.160$$\scriptscriptstyle{\pm 0.002}$ | $1.046$$\scriptscriptstyle{\pm 0.016}$ |
| HodgeGNN | $0.270$$\scriptscriptstyle{\pm 0.002}$ | $0.170$$\scriptscriptstyle{\pm 0.001}$ | $0.109$$\scriptscriptstyle{\pm 0.002}$ | $0.174$$\scriptscriptstyle{\pm 0.001}$ | $1.035$$\scriptscriptstyle{\pm 0.014}$ |
| Hodge+Inv | $0.096$$\scriptscriptstyle{\pm 0.002}$ | 0.146$\scriptscriptstyle{\pm 0.002}$ | 0.108$\scriptscriptstyle{\pm 0.002}$ | $0.162$$\scriptscriptstyle{\pm 0.002}$ | 0.862$\scriptscriptstyle{\pm 0.014}$ |
| Hodge+Dir | 0.081$\scriptscriptstyle{\pm 0.002}$ | 0.146$\scriptscriptstyle{\pm 0.002}$ | $0.110$$\scriptscriptstyle{\pm 0.002}$ | 0.159$\scriptscriptstyle{\pm 0.002}$ | $0.878$$\scriptscriptstyle{\pm 0.014}$ |
| EIGN | 0.069$\scriptscriptstyle{\pm 0.005}$ | 0.130$\scriptscriptstyle{\pm 0.009}$ | 0.061$\scriptscriptstyle{\pm 0.004}$ | 0.090$\scriptscriptstyle{\pm 0.006}$ | 0.583$\scriptscriptstyle{\pm 0.021}$ |

**Table 11: Average MAE ($\downarrow$) of different for the simulation task on real-world datasets (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Model | Anaheim | Barcelona | Chicago | Winnipeg | Circuits |
| --- | --- | --- | --- | --- | --- |
| MLP | $0.064$$\scriptscriptstyle{\pm 0.001}$ | $0.099$$\scriptscriptstyle{\pm 0.001}$ | $0.065$$\scriptscriptstyle{\pm 0.001}$ | $0.104$$\scriptscriptstyle{\pm 0.001}$ | $0.537$$\scriptscriptstyle{\pm 0.005}$ |
| LineGraph | $0.058$$\scriptscriptstyle{\pm 0.001}$ | 0.093$\scriptscriptstyle{\pm 0.001}$ | $0.066$$\scriptscriptstyle{\pm 0.001}$ | 0.100$\scriptscriptstyle{\pm 0.001}$ | $0.539$$\scriptscriptstyle{\pm 0.006}$ |
| HodgeGNN | $0.177$$\scriptscriptstyle{\pm 0.001}$ | $0.102$$\scriptscriptstyle{\pm 0.000}$ | 0.064$\scriptscriptstyle{\pm 0.000}$ | $0.109$$\scriptscriptstyle{\pm 0.001}$ | $0.517$$\scriptscriptstyle{\pm 0.005}$ |
| Hodge+Inv | $0.067$$\scriptscriptstyle{\pm 0.001}$ | $0.097$$\scriptscriptstyle{\pm 0.001}$ | $0.065$$\scriptscriptstyle{\pm 0.001}$ | $0.105$$\scriptscriptstyle{\pm 0.001}$ | 0.453$\scriptscriptstyle{\pm 0.007}$ |
| Hodge+Dir | 0.055$\scriptscriptstyle{\pm 0.001}$ | $0.094$$\scriptscriptstyle{\pm 0.001}$ | $0.065$$\scriptscriptstyle{\pm 0.001}$ | $0.101$$\scriptscriptstyle{\pm 0.001}$ | $0.463$$\scriptscriptstyle{\pm 0.006}$ |
| EIGN | 0.045$\scriptscriptstyle{\pm 0.003}$ | 0.081$\scriptscriptstyle{\pm 0.005}$ | 0.037$\scriptscriptstyle{\pm 0.002}$ | 0.053$\scriptscriptstyle{\pm 0.004}$ | 0.262$\scriptscriptstyle{\pm 0.007}$ |

**Table 12: Average $R^{2}$ ($\uparrow$) of different for the simulation task on real-world datasets (best and runner-up) with $95\%$ confidence intervals of the mean.**
| Model | Anaheim | Barcelona | Chicago | Winnipeg | Circuits |
| --- | --- | --- | --- | --- | --- |
| MLP | $0.900$$\scriptscriptstyle{\pm 0.005}$ | $0.282$$\scriptscriptstyle{\pm 0.017}$ | $-0.015$$\scriptscriptstyle{\pm 0.031}$ | $0.247$$\scriptscriptstyle{\pm 0.019}$ | $0.111$$\scriptscriptstyle{\pm 0.010}$ |
| LineGraph | $0.920$$\scriptscriptstyle{\pm 0.005}$ | $0.347$$\scriptscriptstyle{\pm 0.040}$ | $-0.034$$\scriptscriptstyle{\pm 0.032}$ | $0.360$$\scriptscriptstyle{\pm 0.027}$ | n.a. |
| HodgeGNN | $0.000$$\scriptscriptstyle{\pm 0.000}$ | $0.000$$\scriptscriptstyle{\pm 0.000}$ | $0.000$$\scriptscriptstyle{\pm 0.000}$ | $0.000$$\scriptscriptstyle{\pm 0.000}$ | $0.001$$\scriptscriptstyle{\pm 0.020}$ |
| Hodge+Inv | $0.902$$\scriptscriptstyle{\pm 0.005}$ | $0.342$$\scriptscriptstyle{\pm 0.014}$ | $0.014$$\scriptscriptstyle{\pm 0.020}$ | $0.335$$\scriptscriptstyle{\pm 0.020}$ | 0.582$\scriptscriptstyle{\pm 0.014}$ |
| Hodge+Dir | 0.930$\scriptscriptstyle{\pm 0.004}$ | 0.349$\scriptscriptstyle{\pm 0.025}$ | 0.021$\scriptscriptstyle{\pm 0.019}$ | 0.364$\scriptscriptstyle{\pm 0.019}$ | $0.536$$\scriptscriptstyle{\pm 0.014}$ |
| EIGN | 0.949$\scriptscriptstyle{\pm 0.007}$ | 0.471$\scriptscriptstyle{\pm 0.094}$ | 0.825$\scriptscriptstyle{\pm 0.026}$ | 0.830$\scriptscriptstyle{\pm 0.050}$ | 0.815$\scriptscriptstyle{\pm 0.012}$ |

**Table 13: Ablation of different components of EIGN on synthetic tasks and simulation on real data (best and runner-up) with $95\%$ confidence intervals of the mean. We omit (i) direction-awareness by setting $q=0$, (ii) the fusion operation of Equations 4 and 5, (iii) the fusion operators using convolutions $\melequitoinv$ and $\melinvtoequi$**
|  | Dataset | EIGN<br>w/o Direction | EIGN<br>No Fusion | EIGN<br>No Fusion-Conv. | EIGN |
| --- | --- | --- | --- | --- | --- |
| AUC<br>$\uparrow$ | RW Comp | $0.761$$\scriptscriptstyle{\pm 0.001}$ | $0.848$$\scriptscriptstyle{\pm 0.001}$ | 0.850$\scriptscriptstyle{\pm 0.001}$ | 0.862$\scriptscriptstyle{\pm 0.001}$ |
| LD Cycles | $0.688$$\scriptscriptstyle{\pm 0.002}$ | 0.983$\scriptscriptstyle{\pm 0.001}$ | $0.928$$\scriptscriptstyle{\pm 0.003}$ | 0.996$\scriptscriptstyle{\pm 0.000}$ |  |
| RMSE<br>$\downarrow$ | Tri-Flow | $0.366$$\scriptscriptstyle{\pm 0.003}$ | 0.119$\scriptscriptstyle{\pm 0.004}$ | $0.267$$\scriptscriptstyle{\pm 0.030}$ | 0.036$\scriptscriptstyle{\pm 0.002}$ |
| Anaheim | $0.243$$\scriptscriptstyle{\pm 0.012}$ | 0.093$\scriptscriptstyle{\pm 0.002}$ | $0.270$$\scriptscriptstyle{\pm 0.001}$ | 0.069$\scriptscriptstyle{\pm 0.005}$ |  |
| Barcelona | $0.156$$\scriptscriptstyle{\pm 0.004}$ | 0.148$\scriptscriptstyle{\pm 0.003}$ | $0.169$$\scriptscriptstyle{\pm 0.001}$ | 0.130$\scriptscriptstyle{\pm 0.009}$ |  |
| Chicago | 0.061$\scriptscriptstyle{\pm 0.004}$ | 0.084$\scriptscriptstyle{\pm 0.002}$ | $0.109$$\scriptscriptstyle{\pm 0.002}$ | 0.061$\scriptscriptstyle{\pm 0.004}$ |  |
| Winnipeg | 0.098$\scriptscriptstyle{\pm 0.010}$ | $0.152$$\scriptscriptstyle{\pm 0.004}$ | $0.174$$\scriptscriptstyle{\pm 0.001}$ | 0.090$\scriptscriptstyle{\pm 0.006}$ |  |
| Circuits | 0.773$\scriptscriptstyle{\pm 0.023}$ | $0.813$$\scriptscriptstyle{\pm 0.022}$ | $1.083$$\scriptscriptstyle{\pm 0.020}$ | 0.583$\scriptscriptstyle{\pm 0.021}$ |  |

Figure: Figure 6: Distribution of simulated traffic on the electrical circuits dataset for EIGN and a direction-agnostic variant that sets q = 0. Direction-awareness leads to more more plausible predictions, i.e. current that follows the constraints of diode components that only permit one flow direction.

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 5
presentation: 4
questions: - How many trainable parameters do the models use respectively?
- How sensitive to hyperparameters is your proposed model?
soundness: 4
strengths: The paper is well-written, bringing across the main point nicely. The theoretical claims are sound and the proofs seem correct.
summary: This paper distinguishes between orientation invariant (i.e. those with fixed sign regardless of orientation) and equivariant (those that change sign depending on orientation) features. It highlights the importance of being able to model both types of features in a graph learning scenario and proposes a new model that is able to do so.
weaknesses: The main idea of the paper brings little novelty. Both invariant and equivariant edge features have been explored previously - just not together. The performance gain could well be attributed to a more complex model. 
The theoretical contributions are very simple. Essentially Theorem 4.1 follows by design.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 3
questions: Please see comment above regarding weaknesses. Can the authors comment on whether it is possible to do away with magnetic Laplacian and construct their method using the most general framework for aggregating information in directed graphs from Rossi et al.? If so, can the authors implement this approach and do an empirical comparison to their current approach 
using the magnetic Laplacian?

To address this reviewer's concern about the niche nature of the problem tackled in the paper, could the authors elaborate on the broader applications of their work? What sort of real world problems can be solved using the proposed approach? Are there more general implications of the proposed approach for solving related problems?
soundness: 2
strengths: This reviewer generally liked the paper. The reviewer was not aware of the problem of graphs whose edge can take on both orientation-aware equivariant and invariant values. However, the author's real world data sets seem convincing and not too contrived. It seems like there is a problem here to solve. The way the authors construct their framework, for example how the equivariant and invariant graph Laplacians are constructed using boundary operators and stitched together, is clever and principled. There is no argument that the proposed GNN respects the symmetries of the problem when it comes to equivariance and invariance of edge values with respect to edge orientations. The empirical evidence is also strong. It seems that respecting the symmetries does help with performance. Finally, the authors do a reasonable job with their ablation studies to highlight where the improvements form their method is coming from.
summary: This paper focuses on dealing with edge values on graphs that can only be defined up to an orientation assigned to that edge. Such values flip their sign if the orientation direction of that edge is changed. Conversely, there are edge values that are scalars and do not require an orientation to be defined. Functions that aggregate and update edge values can be either equivariant (the predicted value changes with orientation) or invariant (the predicted value remains the same) to changing the orientation of edges. The authors propose GNN model that at each layer takes in as input orientation-aware equivariant and invariant edge values and outputs updated orientation-aware equivariant and invariant edge values. The authors use a clever design to ensure that the model keeps the equivariant and invariant edge values consistent across the layers. They also introduce a principled way to aggregate across equivariant and invariant edge values. Finally, they extend they approach to graphs with directed edges by using a magnetic Laplacian. Directed edges always have a well defined orientation given by the edge direction. The magnetic Laplacian incorporates a complex phase shift to values of directed edges during the aggregation step. The authors use synthetic data and some real world data sets that their proposed method outperform existing methods on graphs with orientation-aware edge values.
weaknesses: A minor weakness is potentially the nuanced nature of this problem. To this reviewer the problem of applying GNNs to graphs with mixed undirected and directed edges and edge values on undirected edges that can be both equivariant and invariant to their orientation could be viewed as too much of a niche problem and perhaps not enough of a significant advance for the field of learning of graphs more broadly. Therefore, this paper may lack broad interest at ICLR.

The main weakness of the proposed method is the use of magnetic Laplacian and phase shifts in the complex plane to account for directed edges. Although magnetic Laplacian is a reasonable way to aggregate information across neighboring nodes in a directed graph, it is not the most general way to do so and has limited expressivity. The reason for this is simple. The phase used to weigh features across directed edges can result in information loss when the complex features are aggregated at each node. For example, a phase angle of q aggregated with a phase angle of -q results in real value that is indistinguishable from a value aggregated from undirected edges. Similarly if q = 1/2 then 4 hops along directed edges will result in a purely real value indistinguishable from messages aggregated from undirected edges. Similarly, after multiple hops where the edge values may become complex, it will not be possible to determine whether a complex value arriving at a node came from a real value propagated along a directed edge or a complex edge value sent along an undirected edge. Therefore, the use of a phase shift and complex numbers is not the most general way to aggregated information in directed graphs and results in loss of information and thereby lower expressivity of GNNs.

Arguably, the most general way to do aggregation of features of neighboring nodes in a directed graph is proposed by Rossi et al. There, the features from neighbors connected by outgoing edges is aggregated separately from that of neighbors connected by incoming edges. This can be easily extended to include undirected edges as a separate category. During the update step the aggregated features of outgoing and incoming neighbors are concatenated alongside the self feature of the node. The authors should consider such a scheme and construct their boundary operator this way (a vector now that separately aggregates features from outgoing and incoming directed edges and undirected edges). The Laplacian operator can be constructed using this boundary operator and the same constraints applied to ensure that equivariance and invariance requirements are kept. Given how principled the author's approach has been to respecting the symmetries with respect to edge orientation, it would be interesting to see if the most principled way to incorporate edge directions will further improve the performance of their model.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1. On line 200-203, the authors state that “We restrict our novel constraints to undirected edges by requiring equivariance/invariance among direction-consistent orientations only. This allows representing the direction of directed edges through their orientation which, consequentially, must not be arbitrary.” Could you please explain the meaning behind this statement in a simpler term? If I understand correctly, orientation is generated arbitrarily for undirected edges, and direction-consistency only matters for directed edges. Also why does the representation of undirected edges allow representing the direction of directed edges?
2. Figure 2 should be explained more instead of just stating that the representations are indistinguishable for models that are orientation-equivariant for directed edges.
3. What is the time complexity to form the incidence and laplacian matrices in the paper?
4. I don’t think $\mathbf{B}_{\text{inv}}$ should be claimed to be a novel Laplacian as it is already standard definition in many works.
5. How sensitive the model is with respect to the hyperparameter $q$? It seems to me that if an edge has $k$ incoming edge messages such that $kq=2\pi m$ where $m$ is a natural number, the information regarding direction will be wiped out (assuming edge features are the same across edges).
soundness: 3
strengths: The paper defines a clear problem to solve, and the solution is well-motivated. Specifically, decoupling direction from orientation and differentiating directed equivariant edge signals in different scenarios make the work unique compared to prior works. I believe the setup for controlling edges’ signals can be set as a new standard for the field. The theoretical analysis is also comprehensive and sheds light on the design choice. The experiments are also well-designed. They cover different tasks related to directed graphs with no parallel edges. The proposed novel set of benchmarks, which includes 3 synthetic datasets and 5 real-world datasets with 3 different tasks, is a significant contribution to the field.
summary: The author proposes a novel model that decouples direction and orientation. The framework explicitly models equivariant/invariant orientation constraints for undirected and directed edges in graphs via different types of Laplacians. The model is comprehensively evaluated across a wide range of tasks and datasets, and outperforms prior works by a large margin.
weaknesses: One weakness of the paper is on the presentation side. The paper, even displays a lot of figures, to demonstrate different concepts, is still vague in many arguments. Please refer to the Questions section for detailed concerns. Another problem is model comparison. I think the paper will be more comprehensive if the model is compared with the more recent relevant work such as [1].  The next problem is the scalability problem. It seems to me that the novel way of different Laplacian constructions is a fairly computationally expensive process due to the unconventional way of defining incidence matrices. The benchmark itself also only contains small graphs, so it is unclear if the model can scale. Also, the method itself seems to not work on directed multigraphs. Intuition for using Magnetic Laplacian isn’t clear to me; do we really need to introduce complex phase shift to represent directed edges, or can we just pick an arbitrary value and separate undirected and directed Laplacian? Also please refer to question 5 for my concern.

[1] Geisler, S. et al. Transformers Meet Directed Graphs. (2023).

---

confidence: 3
contribution: 4
initial_rating: 6
presentation: 4
questions: The condition that \sigma_{equ}(-x)=-\simga_{\equ}(x) (line 242) seems stange. Are there common activation functions that satisfy this?

Why is there multiplication by the Laplacians in (2) and (3)? Based on standard GCNs it seems that left multiplication by low-pass filters (I-L/2) would be more natural?

Can this framework be extended to settings where there are both edge signals and node-signals?

Similarly, can it be extended to signed and directed graphs? The reference Zhang et al (2021), which the authors take setting from was extended to this setting in subsequent work ``MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian” (He et al.)
soundness: 4
strengths: The tasks are well motivated by realworld scenarios – figure 2 is quite nice!

The proposed network is an elegant solution for achieving the desired properties

Experiments are well sought out and feature a thorough ablation
summary: This paper seeks to extend equivariant machine learning to signals (functions) defined on the vertices of a graph, including signals which are inherently directed (as well as undirected signals). It aims to produce representations which are either invariant or equivariant to changes in edge direction as appropriate, which is non-trivial since standard methods require a boundary operator which chooses an arbitrary edge direction. 

It achieves its goals by formulating the notion of direction consistent orientations and uses this notation to formulate joint orientation equivariance / invariance and then applying several distinct convolution operations (with various generalized magnetic Laplacians ) together with a fusion module and showcases its numerical effectiveness on real and synthetic data sets including data sets from traffic, which was one of the motivating applications.

Overall: I am rating this paper a six, but would have rated this paper a seven if that were an option.
weaknesses: The use of separate equivariant/invariant Laplacains L_equ, L_{inv-> equ}, etc is quite interesting. However, it is unclear how the proposed model compares to other networks defined in these Lapacians. Could one instead constructed a ChebNet style architecture as was done in (Zhang et al 2021) with the magnetic Laplacian

I am unsure if the baselines adequately capture the current SotA


Minor:

Many equations, e.g., (6) and (7) are missing punctuation marks. (This does not affect my score but should be fixed)

The notation B^H is used without definition. I understand that this is the Hermitian transpose, but it should still be defined. (This does not affect my score but should be fixed)

Capitilization in the references e.g., ``laplacian” vs ``Laplacian”, should be fixed (This does not affect my score but should be fixed)

Meta-review: This paper extends equivariant ML to directed signals on directed graphs. All reviewers agreed this paper is worthy of publication in this venue. Some reviewers emphasized the simplicity of the results and that the problem is well-motivated by real-world scenarios. Others mentioned that the solution was elegant, while others valued the thorough ablation in the numerical experiments.

Decision: Accept (Poster)