MagNet: A Neural Network for Directed Graphs
Year: 2022

Abstract:
The prevalence of graph-based data has spurred the rapid development of graph neural networks (GNNs) and related machine learning algorithms. Yet, despite the many datasets naturally modeled as directed graphs, including citation, website, and traffic networks, the vast majority of this research focuses on undirected graphs. In this paper, we propose MagNet, a GNN for directed graphs based on a complex Hermitian matrix known as the magnetic Laplacian. This matrix encodes undirected geometric structure in the magnitude of its entries and directional information in their phase. A “charge” parameter attunes spectral information to variation among directed cycles. We apply our network to a variety of directed graph node classification and link prediction tasks showing that MagNet performs well on all tasks and that its performance exceeds all other methods on a majority of such tasks. The underlying principles of MagNet are such that it can be adapted to other GNN architectures.

heading: 1 Introduction
text: Endowing a collection of objects with a graph structure allows one to encode pairwise relationships among its elements. These relations often possess a natural notion of direction. For example, the WebKB dataset [36] contains a list of university websites with associated hyperlinks. In this context, one website might link to a second without a reciprocal link to the first. Such datasets are naturally modeled by directed graphs. In this paper, we introduce MagNet, a graph convolutional neural network for directed graphs based on the magnetic Laplacian.
Most graph neural networks fall into one of two families, spectral networks or spatial networks. Spatial methods define graph convolution as a localized averaging operation with iteratively learned weights. Spectral networks, on the other hand, define convolution on graphs via the eigendecompositon of the (normalized) graph Laplacian. The eigenvectors of the graph Laplacian assume the role of Fourier modes, and convolution is defined as entrywise multiplication in the Fourier basis. For a comprehensive review of both spatial and spectral networks, we refer the reader to [46] and [44].
Many spatial graph CNNs have natural extensions to directed graphs. However, these extensions typically only consider the outgoing neighbors of each vertex and neglect the incoming neighbors. Therefore, they run the risk of discarding potentially important information. Consider, for example, a
35th Conference on Neural Information Processing Systems (NeurIPS 2021), virtual.
directed social network such as Twitter, where the nodes are Twitter accounts and a directed edge (u, v) ∈ E means that account u mentions account v (using the @ functionality). To infer something about account v, there is important information to be gathered both from other accounts that v mentions, and accounts that mention v. Therefore, it is common for spatial methods to preprocess the data by symmetrizing the adjacency matrix, effectively creating an undirected graph. For example, while [43] explicitly notes that their network is well-defined on directed graphs, their experiments treat all citation networks as undirected for improved performance.
Extending spectral methods to directed graphs is not straightforward since the adjacency matrix is asymmetric and, thus, there is no obvious way to define a symmetric, real-valued Laplacian with a full set of real eigenvalues that uniquely encodes any directed graph. We overcome this challenge by constructing a network based on the magnetic Laplacian L(q) defined in Section 2. Unlike the directed graph Laplacians used in works such as [29, 33, 41, 42], the magnetic Laplacian is not a real-valued symmetric matrix. Instead, it is a complex-valued Hermitian matrix that encodes the fundamentally asymmetric nature of a directed graph via the complex phase of its entries.
Since L(q) is Hermitian, the spectral theorem implies it has an orthonormal basis of complex eigenvectors corresponding to real eigenvalues. Moreover, Theorem 1, stated in Section 5 of the supplement, shows that L(q) is positive semidefinite, similar to the traditional Laplacian. Setting q = 0 is equivalent to symmetrizing the adjacency matrix and no importance is given to directional information. When q = .25, on the other hand, we have that L(.25)(u, v) = −L(.25)(v, u) whenever there is an edge from u to v but not from v to u. Different values of q highlight different graph motifs [16, 17, 20, 32], and therefore the optimal choice of q varies. Learning the appropriate value of q from data allows MagNet to adaptively incorporate directed information. We also note that L(q) has been applied to graph signal processing [19], community detection [17], and clustering [10, 16, 15].
In Section 3, we show how the networks constructed in [6, 13, 24] can be adapted to directed graphs by incorporating complex Hermitian matrices, such as the magnetic Laplacian. When q = 0, we effectively recover the networks constructed in those previous works. Therefore, our work generalizes these networks in a way that is suitable for directed graphs. Our method is very general and is not tied to any particular choice of network architecture. Indeed, the main ideas of this work could be adapted to nearly any spectral graph neural network, and some spatial ones.
In Section 4, we summarize related work on directed graph neural networks as well as other papers studying the magnetic Laplacian and its applications in data science. In Section 5, we apply our network to node classification and link prediction tasks. We compare against several spectral and spatial methods as well as networks designed for directed graphs. We find that MagNet obtains the best or second-best performance on five out of six node-classification tasks and has the best performance on seven out of eight link-prediction tasks tested on real-world data, in addition to providing excellent node-classification performance on difficult synthetic data. We also provide a supplementary document with full implementation details, theoretical results concerning the magnetic Laplacian, extended examples, and further numerical details.

heading: 2 The magnetic Laplacian
text: Spectral graph theory has been remarkably successful in relating geometric characteristics of undirected graphs to properties of eigenvectors and eigenvalues of graph Laplacians and related matrices. For example, the tasks of optimal graph partitioning, sparsification, clustering, and embedding may be approximated by eigenvectors corresponding to small eigenvalues of various Laplacians (see, e.g., [9, 38, 2, 40, 11]). Similarly, the graph signal processing research community leverages the full set of eigenvectors to extend the Fourier transform to these structures [34]. Furthermore, numerous papers [6, 13, 24] have shown that this eigendecomposition can be used to define neural networks on graphs. In this section, we provide the background needed to extend these constructions to directed graphs via complex Hermitian matrices such as the magnetic Laplacian.
We let G = (V,E) be a directed graph where V is a set of N vertices and E ⊆ V × V is a set of directed edges. If (u, v) ∈ E, then we say there is an edge from u to v. For the sake of simplicity, we will focus on the case where the graph is unweighted and has no self-loops, i.e., (v, v) /∈ E, but our methods have natural extensions to graphs with self-loops and/or weighted edges. If both (u, v) ∈ E and (v, u) ∈ E, then one may consider this pair of directed edges as a single undirected edge.
A directed graph can be described by an adjacency matrix (A(u, v))u,v∈V where A(u, v) = 1 if (u, v) ∈ E and A(u, v) = 0 otherwise. Unless G is undirected, A is not symmetric, and, indeed, this is the key technical challenge in extending spectral graph neural networks to directed graphs. In the undirected case, where the adjacency matrix A is symmetric, the (unnormalized) graph Laplacian can be defined by L = D −A, where D is a diagonal degree matrix. It is well-known that L is a symmetric, positive-semidefinite matrix and therefore has an orthonormal basis of eigenvectors associated with non-negative eigenvalues. However, when A is asymmetric, direct attempts to define the Laplacian this way typically yield complex eigenvalues. This impedes the straightforward extension of classical methods of spectral graph theory and graph signal processing to directed graphs.
A key point of this paper is to represent the directed graph through a complex Hermitian matrix L such that: (1) the magnitude of L(u, v) indicates the presence of an edge, but not its direction; and (2) the phase of L(u, v) indicates the direction of the edge, or if the edge is undirected. Such matrices have been explored in the directed graph literature (see Section 4), but not in the context of graph neural networks. They have several advantages over their real-valued matrix counterparts. In particular, a single symmetric real-valued matrix will not uniquely represent a directed graph. Instead, one must use several matrices, as in [42], but this increases the complexity of the resulting network. Alternatively, one can work with an asymmetric, real-valued matrix, such as the adjacency matrix or the random walk matrix. However, the spatial graph filters that result from such matrices are typically limited by the fact that they can only aggregate information from the vertices that can be reached in one hop from a central vertex, but ignore the equally important subset of vertices that can reach the central vertex in one hop. Complex Hermitian matrices, however, lead to filters that aggregate information from both sets of vertices. Finally, one could use a real-valued skew-symmetric matrix but such matrices do not generalize well to graphs with both directed and undirected edges.
The optimal choice of complex Hermitian matrix is an open question. Here, we utilize a parameterized family of magnetic Laplacians, which have proven to be useful in other data-driven contexts [17, 10, 16, 15]. We first define the symmetrized adjacency matrix and corresponding degree matrix by,
As(u, v) := 1
2 (A(u, v) + A(v, u)), 1 ≤ u, v ≤ N, Ds(u, u) := ∑ v∈V As(u, v), 1 ≤ u ≤ N ,
with Ds(u, v) = 0 for u 6= v. We capture directional information via a phase matrix,1 Θ(q), Θ(q)(u, v) := 2πq(A(u, v)−A(v, u)) , q ≥ 0 ,
where exp(iΘ(q)) is defined component-wise by exp(iΘ(q))(u, v) := exp(iΘ(q)(u, v)). Letting denote component-wise multiplication, we define the complex Hermitian adjacency matrix H(q) by
H(q) := As exp(iΘ(q)) . Since Θ(q) is skew-symmetric, H(q) is Hermitian. When q = 0, we have Θ(0) = 0 and so H(0) = As. This effectively corresponds to treating the graph as undirected. For q 6= 0, the phase of H(q)(u, v) encodes edge direction and the value H(q)(u, v) separates four possible cases: no edge, edge from u to v, edge from v to u, and undirected edge. If there is no edge, we will have Hq(u, v) = 0. In the case of a directed edge, the Hermitian adjacency will be complex valued, and changing the direction of an edge will correspond to complex conjugation. For example, in the case where q = .25, if there is an edge from u to v but not from v to u we have
H(.25)(u, v) = i
2 = −H(.25)(v, u) .
Thus, in this setting, an edge from u to v is treated as the opposite of an edge from v to u. On the other hand, if (u, v), (v, u) ∈ E (which can be interpreted as a single undirected edge), then H(q)(u, v) = H(q)(v, u) = 1, and we see the phase, Θ(q)(u, v) = 0, encodes the lack of direction in the edge. For the rest of this paper, we will assume that q lies in between these two extreme values, i.e., 0 ≤ q ≤ .25. We define the normalized and unnormalized magnetic Laplacians by
L (q) U := Ds−H (q) = Ds−As exp(iΘ(q)), L(q)N := I− ( D−1/2s AsD −1/2 s ) exp(iΘ(q)) . (1)
1Our definition of Θ(q) coincides with that used in [19]. However, another definition (differing by a minus sign) also appears in the literature. These resulting magnetic Laplacians have the same eigenvalues and the corresponding eigenvectors are complex conjugates of one another. Therefore, this difference does not affect the performance of our network since our final layer separates the real and imaginary parts before multiplying by a trainable weight matrix (see Section 3 for details on the network structure).
Note that when G is undirected, L(q)U and L (q) N reduce to the standard undirected Laplacians.
L (q) U and L (q) N are Hermitian. Theorem 1 (Section 5 of the supplement) shows they are positivesemidefinite and thus are diagonalized by an orthonormal basis of complex eigenvectors u1, . . . ,uN associated to real, nonnegative eigenvalues λ1, . . . , λN . Similar to the traditional normalized Laplacian, Theorem 2 (Section 5 of the supplement) shows the eigenvalues of LqN lie in [0, 2], and we may factor L(q)N = UΛU
†, where U is the N ×N matrix whose k-th column is uk, Λ is the diagonal matrix with Λ(k, k) = λk, and U† is the conjugate transpose of U (a similar formula holds for L (q) U ). Furthermore, recall L = BB
>, where B is the signed incidence matrix. Similarly, Theorem 3 (Section 5 of the supplement) shows that L(q)U = B
(q)(B(q))†, where B(q) is a modified incidence matrix. The magnetic Laplacian encodes geometric information in its eigenvectors and eigenvalues. In the directed star graph (Section 6 of the supplement), for example, directional information is contained in the eigenvectors only, whereas the eigenvalues are invariant to the direction of the edges. On the other hand, for the directed cycle graph the magnetic Laplacian encodes the directed nature of the graph solely in its spectrum. In general, both the eigenvectors and eigenvalues may contain important information, which we leverage in MagNet.

heading: 3 MagNet
text: Most graph neural network architectures can be described as being either spectral or spatial. Spatial networks such as [43, 21, 1, 14] typically extend convolution to graphs by performing a weighted average of features over neighborhoods N (u) = {v : (u, v) ∈ E}. These neighborhoods are well-defined even when E is not symmetric, so spatial methods typically have natural extensions to directed graphs. However, such simplistic extensions may miss important information in the directed graph. For example, filters defined using N (u) are not capable of assimilating the equally important information contained in {v : (v, u) ∈ E}. Alternatively, these methods may also use the symmetrized adjacency matrix, but they cannot learn to balance directed and undirected approaches.
In this section, we show how to extend spectral methods to directed graphs using the magnetic Laplacian introduced in Section 2. To highlight the flexibility of our approach, we show how three spectral graph neural network architectures can be adapted to incorporate the magnetic Laplacian. Our approach is very general, and so for most of this section, we will perform our analysis for a general complex Hermitian, positive semidefinite matrix. However, we view the magnetic Laplacian as our primary object of interest (and use it in all of our experiments in Section 5) because of the large body of literature studying its spectral properties and applying it to data science (see Section 4).

heading: 3.1 Spectral convolution via the magnetic Laplacian
text: In this section, we let L denote a Hermitian, positive semidefinite matrix, such as the normalized or unnormalized magnetic Laplacian introduced in Section 2, on a directed graph G = (V,E), |V | = N . We let u1 . . . ,uN be an orthonormal basis of eigenvectors for L and let U be the N × N matrix whose k-th column is uk. We define the directed graph Fourier transform for a signal x : V → C by x̂ = U†x, so that x̂(k) = 〈x,uk〉 . We regard the eigenvectors u1, . . . ,uN as the generalizations of discrete Fourier modes to directed graphs. Since U is unitary, we have the Fourier inversion formula
x = Ux̂ = N∑ k=1 x̂(k)uk . (2)
In Euclidean space, convolution corresponds to pointwise multiplication in the Fourier basis. Thus, we define the convolution of x with a filter y in the Fourier domain by ŷ ∗ x(k) = ŷ(k)x̂(k). By (2), this implies y ∗ x = UDiag(ŷ)x̂ = (UDiag(ŷ)U†)x, and so we say Y is a convolution matrix if
Y = UΣU† , (3)
for a diagonal matrix Σ. This is the natural generalization of the class of convolutions used in [6].
Next, following [13] (see also [22]), we show that a spectral network can be implemented in the spatial domain via polynomials of L by having Σ be a polynomial of Λ in (3). This reduces the number of trainable parameters to prevent overfitting, avoids explicit diagonalization of the matrix L,
(which is expensive for large graphs), and improves stability to perturbations [27]. As in [13], we define a normalized eigenvalue matrix, with entries in [−1, 1], by Λ̃ = 2λmax Λ− I and assume
Σ = K∑ k=0 θkTk(Λ̃) ,
for some real-valued θ1, . . . , θk, where Tk is the Chebyshev polynomial defined by T0(x) = 1, T1(x) = x, and Tk(x) = 2xTk−1(x) + Tk−2(x) for k ≥ 2. With (UΛ̃U†)k = UΛ̃kU†, one has
Yx = U K∑ k=0 θkTk(Λ̃)U †x = K∑ k=0 θkTk(L̃)x , (4)
where, analogous to Λ̃, we define L̃ := 2λmax L− I. It is important to note that, due to the complex Hermitian structure of L̃, the value Yx(u) aggregates information both from the values of x on Nk(u), the k-hop neighborhood of u, and the values of x on {v : dist(v, u) ≤ k}, which consists of those of vertices that can reach u in k-hops. While in an undirected graph these two sets of vertices are the same, that is not the case for general directed graphs. Furthermore, due to the difference in phase between an edge (u, v) and an edge (v, u), the filter matrix Y is also capable of aggregating information from these two sets in different ways. This capability is in contrast to any single, symmetric, real-valued matrix, as well as any matrix that encodes just N (u).
To obtain a network similar to [24], we set K = 1, assume that L = L(q)N , using λmax ≤ 2 make the approximation λmax ≈ 2, and set θ1 = −θ0. With this, we obtain
Yx = θ0(I + (D −1/2 s AsD −1/2 s ) exp(iΘ(q)))x .
As in [24], we substitute I + (D−1/2s AsD −1/2 s ) exp(iΘ(q))→ D̃−1/2s ÃsD̃−1/2s exp(iΘ(q)). This renormalization helps avoid instabilities arising from vanishing/exploding gradients and yields
Yx = θ0D̃ −1/2 s ÃsD̃ −1/2 s exp(iΘ(q)) , (5) where Ãs = As + I and D̃s(i, i) = ∑ j Ãs(i, j).
In theory, the matrix exp(iΘ(q)) is dense. However, in practice, one only needs to compute a small fraction of its entries. In most real-world datasets, the symmetrized adjacency matrix will be sparse. Since the Hermitian adjacency matrix is constructed via pointwise multiplication between the symmetrized adjacency matrix and the phase matrix, it is only necessary to compute the phase matrix for entries (u, v) where As(u, v) 6= 0. Thus, the efficiency of the proposed algorithm is comparable to standard GCN algorithms, and can leverage any existing developments such as [18] that increase efficiency of standard GCNs (although the computational complexity our method does differ by a factor of four because of the computational complexity of complex-valued multiplication).

heading: 3.2 The MagNet architecture
text: Let L be the number of convolution layers in our network, and let X(0) be an N × F0 input feature matrix with columns x(0)1 , . . .x (0) F0
. Since our filters are complex, we use a complex version of ReLU defined by σ(z) = z, if −π/2 ≤ arg(z) < π/2, and σ(z) = 0 otherwise (where arg(z) is the complex argument of z ∈ C). Let F` be the number of channels in layer `, and for 1 ≤ ` ≤ L, 1 ≤ i ≤ F`−1, and 1 ≤ j ≤ F`, we let Y(`)ij be a convolution matrix defined in the sense of either (3), (4), or (5). Define the `th layer feature matrix X(`) with columns x(`)1 , . . .x (`) F` as:
x (`) j = σ F`−1∑ i=1 Y (`) ij x (`−1) i + b (`) j  , (6) with b(`)j (v) = b (`) j and real(b (`) j ) = imag(b (`) j ). In matrix form we write X (`) = Z(`) ( X(`−1) ) , where Z(`) is a hidden layer of the form (6). In the numerical experiments reported in Section 5, we utilize formulation (4) with L = L(q)N . In most cases we set K = 1, for which
X(`) = σ ( X(`−1)W
(`) self + L̃ (q) N X (`−1)W (`) neigh + B
(`) ) ,
where W(`)self and W (`) neigh are learned weight matrices corresponding to the filter weights in (4), and B(`)(v, ·) = (b(`)1 , . . . , b (`) F` ) for each v ∈ V .
After the convolutional layers, we unwind the complex N × FL matrix X(L) into a real-valued N × 2FL matrix, apply a linear layer, consisting of right-multiplication by a 2FL × nc weight matrix W(L+1) (where nc is the number of classes) and apply softmax. In our experiments, we set L = 2 or 3. When L = 2, our network applied to node classification, as illustrated in Figure 1, is given by
softmax(unwind(Z(2)(Z(1)(X(0))))W(3)) .
For link-prediction, we apply the same method through the unwind layer, and then concatenate the rows corresponding to pairs of nodes to obtain the edge features.

heading: 4 Related work
text: In Section 4.1, we describe other graph neural networks designed specifically for directed graphs. Notably, none of these methods encode directionality with complex numbers, instead opting for realvalued, symmetric matrices. In Section 4.2, we review other work studying the magnetic Laplacian which has been studied for several decades and lately has garnered interest in the network science and graph signal processing communities. However, to the best of our knowledge, this is the first work to use it to construct a graph neural network. We also note there are numerous approaches to graph signal processing on directed graphs. Many of these rely on a natural analog of Fourier modes. These Fourier modes are typically defined through either a factorization of a graph shift operator or by solving an optimization problem. For further review, we refer the reader to [30].

heading: 4.1 Neural networks for directed graphs
text: In [29], the authors construct a directed Laplacian, via identities involving the random walk matrix and its stationary distribution Π. When G is undirected, one can use the fact that Π is proportional to the degree vector to verify this directed Laplacian reduces to the standard normalized graph Laplacian. However, this method requires G to be strongly connected, unlike MagNet. The authors of [42] use a first-order proximity matrix AF (equivalent to As here), as well as two second-order proximity matrices ASin and ASout . ASin is defined by ASin(u, v) 6= 0 if there exists a w such that (w, u), (w, v) ∈ E, and ASout is defined analogously. These three matrices collectively describe and distinguish the neighborhood of each vertex and those vertices that can reach a vertex in a single hop. The authors construct three different Laplacians and use a fusion operator to share information across channels. Similarly, inspired by [3], in [33], the authors consider several different symmetric Laplacian matrices corresponding to a number of different graph motifs.
The method of [41] builds upon the ideas of both [29] and [42] and considers a directed Laplacian similar to the one used in [29], but with a PageRank matrix in place of the random-walk matrix. This allows for applications to graphs which are not strongly connected. Similar to [42], they use higher-order receptive fields (analogous to the second-order adjacency matrices discussed above) and an inception module to share information between receptive fields of different orders. We also note [25], which uses an approach based on PageRank in the spatial domain. There are also some related methods for directed graphs that are not based on the graph Laplacian, such as the directed graph embedding [39], and directed message passing for molecular graphs [26].

heading: 4.2 Related work on the magnetic Laplacian and Hermitian adjacency matrices
text: The magnetic Laplacian has been studied since at least [28]. The name originates from its interpretation as a quantum mechanical Hamiltonian of a particle under magnetic flux. Early works focused on d-regular graphs, where the eigenvectors of the magnetic Laplacian are equivalent to those of the Hermitian adjacency matrix. The authors of [20], for example, show that using a complex-valued Hermitian adjacency matrix rather than the symmetrized adjacency matrix reduces the number of small, non-isomorphic cospectral graphs. Topics of current research into Hermitian adjacency matrices include clustering tasks [12] and the role of the parameter q [32].
The magnetic Laplacian is also the subject of ongoing research in graph signal processing [19], community detection [17], and clustering [10, 16, 15]. For example, [16] uses the phase of the eigenvectors to construct eigenmap embeddings analogous to [2]. The role of q is highlighted in the works of [16, 17, 20, 32], which show how particular choices of q may highlight various graph motifs. In our context, this indicates that q should be carefully tuned via cross-validation. Lastly, we note that numerous other directed graph Laplacians have been studied and applied to data science [7, 8, 35]. However, as alluded to in Section 2, these methods typically do not use complex Hermitian matrices.

heading: 5 Numerical experiments

heading: 5.1 Datasets
text: 5.1.1 Directed Stochastic Block Model
We construct a directed stochastic block (DSBM) model as follows. First we divide N vertices into nc equally-sized clusters C1, . . . , Cnc . We define {αi,j}1≤i,j≤nc to be a collection of probabilities, 0 < αi,j ≤ 1 with αi,j = αj,i, and for an unordered pair u 6= v create an undirected edge between u and v with probability αi,j if u ∈ Ci, v ∈ Cj . To turn this undirected graph into a directed graph, we define {βi,j}1≤i,j≤nc to be a collection of probabilities such that 0 ≤ βi,j ≤ 1 and βi,j + βj,i = 1. For each undirected edge {u, v}, we assign that edge a direction by the rule that the edge points from u to v with probability βi,j if u ∈ Ci and v ∈ Cj , and points from v to u otherwise. If αi,j is constant, then the only way to determine the clusters will be from the directional information.
In Figure 3, we plot the performance of MagNet and other methods on variations of the DSBM. In each of these, we set nc = 5 and the goal is to classify the vertices by cluster. We set N = 2500, except in Figure 3d where N = 500. In Figure 3a, we plot the performance of our model on the DSBM with αi,j := α∗ = .1, .08, and .05 for i 6= j, which varies the density of inter-cluster edges, and set αi,i = .1. Here we set βi,i = .5 and βi,j = .05 for i > j. This corresponds to the ordered meta-graph in Figure 2a. Figure 3b also uses the ordered meta-graph, but here we fix αi,j = .1 for all i, j, and set βi,j = β∗, for i > j, and allow β∗ to vary from .05 to .4, which varies the net flow (related to flow imbalance in [23]) from one cluster to another. The results in Figure 3c utilize a cyclic meta-graph structure as in Figure 2b (without the gray noise edges). Specifically, we set αi,j = .1 if i = j or i = j ± 1 mod 5 and αi,j = 0 otherwise. We define βi,j = β∗, βj,i = 1− β∗ when j = (i− 1) mod 5, and βi,j = 0 otherwise. In Figure 3d we add
noise to the cyclic structure of our meta-graph by setting αi,j = .1 for all i, j and βi,j = .5 for all (i, j) connected by a gray edge in Figure 2b (keeping βi,j the same as in Figure 3c for the blue edges).

heading: 5.1.2 Real datasets
text: Texas, Wisconsin, and Cornell are WebKB datasets modeling links between websites at different universities [36]. We use these datasets for both link prediction and node classification with nodes
labeled as student, project, course, staff, and faculty in the latter case. Telegram [5] is a pairwise influence network between 245 Telegram channels with 8, 912 links. To the best of our knowledge, this dataset has not previously been studied in the graph neural network literature. Labels are generated from the method discussed in [5], with a total of four classes. The datasets Chameleon and Squirrel [37] represent links between Wikipedia pages related to chameleons and squirrels. We use these datasets for link prediction. Likewise, WikiCS [31] is a collection of Computer Science articles, which we also use for link prediction (see the tables in Section 7 of the supplement). Cora-ML and CiteSeer are popular citation networks with node labels corresponding to scientific subareas. We use the versions of these datasets provided in [4]. Further details are given in the supplementary material.

heading: 5.2 Training and implementation details
text: Node classification is performed in a semi-supervised setting (i.e., access to the test data, but not the test labels, during training). For the datasets Cornell, Texas, Wisconsin, and Telegram we use a 60%/20%/20% training/validation/test split, which might be viewed as more akin to supervised learning, because of the small graph size. For Cora-ML and CiteSeer, we use the same split as [41]. For all of these datasets we use 10 random data splits. For the DSBM datasets, we generated 5 graphs randomly for each type and for each set of parameters, each with 10 different random node splits. We use 20% of the nodes for validation and we vary the proportion of training samples based on the classification difficulty, using 2%, 10%, and 60% of nodes per class for the ordered, cyclic, and noisy cyclic DSBM graphs, respectively, during training, and the rest for testing. Hyperpameters were selected using one of the five generated graphs, and then applied to the other four generated graphs.
In the main text, there are two types of link prediction tasks conducted for performance evaluation. The first type is to predict the edge direction of pairs of vertices u, v for which either (u, v) ∈ E or (v, u) ∈ E. The second type is existence prediction. The model is asked to predict if (u, v) ∈ E by considering ordered pairs of vertices (u, v). For both types of link prediction, we removed 15% of edges for testing, 5% for validation, and use the rest of the edges for training. The connectivity was maintained during splitting. 10 splits were generated randomly for each graph and the input features are in-degree and out-degree of nodes. In the supplement, we report on two additional link prediction tasks based on a three-class classification setup: (u, v) ∈ E, (v, u) ∈ E, or (u, v), (v, u) /∈ E. Full details are provided in the supplementary material.
In all experiments, we used the normalized magnetic Laplacian and implement MagNet with convolution defined as in (4), meaning that our network may be viewed as the magnetic Laplacian generalization of ChebNet. The setting of the hyperparameter q and other network hyperparameters is obtained by cross-validation. Since currently complex tensors are still in beta in PyTorch, we did not use them, and instead we stored any complex tensor as two real tensors (one for the real part, one for the imaginary part), and carried out complex multiplication using the standard formula: (a + ib)(c + id) = (ac − bd) + i(bc + ad) (note, a, b, c, d can be real numbers or real matrices). We compare with multiple baselines in three categories: (i) spectral methods: ChebNet [13], GCN [24]; (ii) spatial methods: APPNP [25], SAGE [21], GIN [45], GAT [43]; and (iii) methods designed for directed graphs: DGCN [42], and two variants of [41], a basic version (DiGraph) and a version with higher order inception blocks (DiGraphIB). All baselines in the experiments have two graph convolutional layers, except for the node classification on the DSBM using the cyclic meta-graphs (Figures 3c, 3d, and 2b) for which we also tested three layers during the hyperparameter search. For ChebNet, we use the symmetrized adjacency matrix. For the spatial networks we apply both the symmetrized and asymmmetric adjacency matrix for node classification. The results reported are the better of the two results. The supplement provides full details, as well as results for two other types of baselines: (i) BiGCN, BiSAGE, BiGAT which are obtained by applying GCN, SAGE, GAT on both the original adjacency matrix and the transposed adjacency matrix; and (ii) a k-nearest neighbors classifier based on the eigenvector with the smallest eigenvalue of the magnetic Laplacian [17].

heading: 5.3 Results
text: We see that MagNet performs well across all tasks. As indicated in Table 1, our cross-validation procedure selects q = 0 for node classification on the citation networks Cora-ML and CiteSeer. This means we achieved the best performance when regarding directional information as noise, suggesting symmetrization-based methods are appropriate in the context of node classification on citation networks. This matches our intuition. For example, in Cora-ML, the task is to classify
(a) Ordered DSBM with varying edge density.
(b) Ordered DSBM with varying net flow.
(c) Cyclic DSBM with varying net flow.
(d) Noisy Cyclic DSBM with varying net flow.
Figure 3: Node classification accuracy. Error bars are one standard error. MagNet is bold red.
research papers by scientific subarea. If the topic of a given paper is “machine learning,” then it is likely to both cite and be cited by other machine learning papers. For all other datasets, we find the optimal value of q is nonzero, indicating that directional information is important. Our network exhibits the best performance on three out of six of these datasets and is a close second on Texas and Telegram. We also achieve an at least four percentage point improvement over both ChebNet and GCN on the four data sets for which q > 0. These networks are similar to ours but with the classical graph Laplacian. This isolates the effects of the magnetic Laplacian and shows that it is a valuable tool for encoding directional information. MagNet also compares favorably to non-spectral methods on the WebKB networks (Cornell, Texas, Wisconsin). Indeed, MagNet obtains a ∼ 4% improvement on Cornell and a ∼ 2.5% improvement on Wisconsin, while on Texas it has the second best accuracy, close behind SAGE. We also see the other directed methods have relatively poor performance on the WebKB networks, perhaps since these graphs are fairly small and have very few training samples. To make this analysis more quantitative, we computed the absolute difference of the classification accuracy of each method from the classification accuracy of the top performing method (in percentage points) on each data set, and averaged over the six data sets. In this context, lower scores are better, and a method with a score of zero indicates the method is the top performing method on each data set. As reported in Table 1, MagNet achieved a best score of 1.1 percent.
On the DSBM datasets, as illustrated in Figure 3 (see also the tables in Section 7 of the supplement), we see that MagNet generally performs quite well and is the best performing network in the vast majority of cases (for full details, see Section 7 of the supplement). The networks DGCN and DiGraphIB rely on second order proximity matrices. As demonstrated in Figure 3c, these methods are well suited for networks with a cyclic meta-graph structure since nodes in the same cluster are likely to have common neighbors. MagNet, on the other hand, does not use second-order proximity, but can still learn the clusters by stacking multiple layers together. This improves MagNet’s ability to adapt to directed graphs with different underlying topologies. This is illustrated in Figure 3d where the network has an approximately cyclic meta-graph structure. In this setting, MagNet continues to perform well, but the performance of DGCN and DiGraphIB deteriorate significantly. Interestingly, MagNet performs well on the DSBM cyclic meta-graph (Figure 3c) with q ≈ .1, whereas q ≥ .2 is
preferred for the other three DSBM tests; we leave a more in-depth investigation for future work. Further details are available in Section 8 of the supplement.
For link prediction, we achieve the best performance on seven out of eight tests as shown in Table 2. We also note that Table 2 reports optimal non-zero q values for each task. This indicates that incorporating directional information is important for link prediction, even on citation networks such as Cora and CiteSeer. This matches our intuition, since there is a clear difference between a paper with many citations and one with many references. More results on different datasets, and closely related tasks (including three-class classification), are provided in Section 7 in the supplement.

heading: 6 Conclusion
text: We have introduced MagNet, a neural network for directed graphs based on the magnetic Laplacian. This network can be viewed as the natural extension of spectral graph convolutional networks to the directed graph setting. We demonstrate the effectiveness of our network, and the importance of incorporating directional information via a complex Hermitian matrix, for link prediction and node classification on both real and synthetic datasets. Interesting avenues of future research would be using multiple q’s along different channels, exploring the role of different normalizations of the magnetic Laplacian, and incorporating the magnetic Laplacian into other network architectures.
Limitations and Ethical Considerations: Our method has natural extensions to weighted, directed graphs when all edges are directed. However, it not clear what is the best way to extend it to weighted mixed graphs (with both directed and undirected edges). Our network does not incorporate an attention mechanism and, similar to many other networks, is not scalable to large graphs in its current form (although this may be addressed in future work). All of our data is publicly available for research purposes and does not contain personally identifiable information or offensive content. The method presented here has no greater or lesser impact on society than other graph neural network algorithms.

heading: Acknowledgments
text: We would like to thank Jie Zhang who pointed out that our definition of the magnetic Laplacian differed by an entry-wise complex conjugation from the most commonly used definition in the literature. Y.H. thanks her supervisors Mihai Cucuringu and Gesine Reinert for their guidance.
This work was supported by the National Institutes of Health [grant NIGMS-R01GM135929 to M.H. and supporting X.Z, N.B.]; the University of Oxford [the Clarendon scholarship to Y.H.]; the National Science Foundation [grant DMS-1845856 to M.H.]; and the Department of Energy [grant DE-SC0021152 to M.H.].

Review summaries:
This paper considers the design of graph neural networks for directed graphs. In particular, it uses the magnetic Laplacian, a complex-valued Hermitian matrix that encodes edge directions via a phase parameter, as a matrix from which convolutional filters are formed. By defining this matrix, the authors demonstrate how it can be used in place of more traditional Laplacians in a few existing graph neural network architectures. This approach is then empirically verified on synthetic and real datasets, where the utility of the the magnetic Laplacian for encoding edge directionality is demonstrated.