MagNet: A Neural Network for Directed Graphs
Authors: Xitong Zhang
Yixuan He
Nathan Brugnone
Michael Perlmutter
Matthew Hirn
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
directed graph
magnetic Laplacian

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.

MagNet: A Neural Network for Directed Graphs
Xitong Zhang', Yixuan He?, Nathan Brugnone Michael Perlmutter", and Matthew Hirn 1.566
Michigaa State University, Department of Computational Mathematics, Science & Engineering.
East Lansing, Michigan, United States
University of Oxford, Department of Statistics, Oxford, England, United Kingdom MMichigan State University, Department of Community Sustainability,
East Lansing, Michigan, United States
Universityy of California, Los Angeles, Department of Mathematics, Los Angeles, California, United States 'Michigan State University. Department of Mathematics,
East Lansing, Michigan, United States
Michigan State University, Center for Quantum Computing, Science & Engineering, East Lansing, Michigan, United States
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 directed graphs, including citation, website, and traffic networks, the vast majority of this research focuses on undirected graphs. In this paper, we propose MagNet, GNN for directed graphs based on a complex Hermitian matrix known as the magnetic Laplacian. This matrix encodes undirected geometric structure the magniuude 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 majority of such tasks. The underlying principles of MagNet are such that it can be adapted to other GNN architectures.
Introduction
Endowing collection of objects with 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 list of university websites with associated hyperlinks. In this context, one website might link to a second without reciprocal link to the first. Such datasets are naturally modeled by directed graphs. In this paper, introduce MagNet,, 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 graphs via the cigendecomposi- ton of the (normalized) graph Laplacian. The cigenvectors of the graph Laplacian assume the role of Fourier modes, and convolution is defined entrywise multiplication in the Fourier basis. For comprehensive review of both spatial and spectral networks, we refer the reader to 46) and
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,
35th Conference on Neural Information Processing Systems (NcurIPS 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 (using the @ functionalityy. To infer something about account there is important information to be gathered both from other accounts that mentions, and accounts that mention v. Therefore, it common for spatial methods to preprocess the data by symmetrizing the adjacency matrix, effectively creating an undirected graph. For example, while [4] 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 symmetric, real-valued Laplacian with a full set of real eigenvalues that uniquely encodes any directed graph. We overeome this challenge by constructing network based the magnetic Laplacian L(9) defined in Section 2 Unlike the directed graph Laplacians used in works such as [29]33] 33 41 real-valued symmetric matrix. Instead, it is complex-valued Hermitian matrix that encodes the fundamentally asymmetric nature of a directed graph via the complex phase of its entries.
421, the magnetic Laplacian is not
Since [ is Hermitian, the spectral theorem implies it has an orthonormal basis of complex eigenvectors corresponding to real eigenvalues. Moreover, Theorem D stated in Section of the supplement, shows that [ is positive semidefinite, similar to the traditional Laplacian. Setting q = 0 is equivalent to symmetrizing the adjacency matrix and no importance given directional information. When q- .25, on the other hand, we have that L ((25) (u, v) ( (v, u) whenever there is an edge from u to e but not from to u. Different values of q highlight different graph motifs 20 32, and therefore the optimal choice of q varies. Learning the appropriate value of q from data allows MagNet adaptively incorporate directed information. We also note that L(w) has been applied to graph signal processing 19], community detection [17,, and clustering
[16
17
[10] 16 15).
In Section 3 we show how the networks constructed in 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 [ 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- linkprediction tasks tested on real-world data, in addition to providing excellent node- oldeccaassfiicttio performance on difficult synthetic data. We also provide supplementary document with full implementation details, theoretical results concerning the magnetic Laplacian, extended examples, and further numerical details.
2
The magnetic Laplacian
Spectral graph theory has been remarkably successful in relating geometric characteristics of undi- rected 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 M.). Similarly, the graph signal processing research community leverages the full set of eigenvectors extend the Fourier transform to these structures [34]. Furthermore, numerous papers 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 set of N vertices and E C V x V is set of directed edges. (u, v) E E, then we say there 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) & F, but our methods have natural extensions to graphs with self-loops and/or weighted edges. If both (u, v) E E and (v, u) E E, then one may consider this pair of directed edges as single undirected edge.
2

---

A directed graph can be described by an adjacency matrix (A(u, u)), where A(u, v) 1 if (u, v)) E and A (u, 2) = 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-semidefinin 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.
key point of this paper is to represent the directed graph through a complex Hermitian matrix L such that: (1) the magnitude of C(u, u) indicates the presence of an edge, but not its direction; and (2) the phase of v(,,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, single symmetric real-valued matrix will not uniquely represent 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 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-symmetrie 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 J0 16 15].
We first define the symmetrized adjacency matrix and corresponding degree matrix by,
1 (A(u, v) + A(v,u)) 1 N, D.(u, = Σ A. v),, 1sus N,
A,(u, u) =
2
VEV
with Du 8) = 0 for u # v. We capture directional information via a phase matrix [
(u, = ( v) (v,, 2 0, where exp(iO(4)) is defined component-wise wise by exp(iO (u,, = exp(ie (w) (w) Letting @ denote component-wise multiplication, define the complex Hermitian adjacency matrix ((9) by
H A, O cxp(10
Since (x) is skew-symmetric, H99)) Hermitian. When q = 0, we have ( and so H A., This effectively corresponds treating the graph as undirected. For q + 0, the phase of (1)) (u, v) encodes edge direction and the value ((9) (u, v) separates four possible cases: no edge, edge from u to e, edge from v to u. and undirected edge. If there is no edge, we will have H v) 0. In the case of 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 we have
where q 22, if there is an edge from to u but not from
H ( (u, v) = = - 25) (v, u).
Thus, in this setting, an edge from u to e is treated as the opposite of an edge from v to u. On the other hand, if (u. v), (v, u) E E (which can be interpreted as a single undirected edge), then ((9) (u, v) H (F. u) 1, and we see the phase, ( (u, v) O, encodes the lack of direction in the edge. For the rest of this paper, we will assume that g lies in between these two extreme values, i... 0 < q < .25 We define the normalized and unnormalized magnetic Laplacians by
(g) D. (4)) D. A. Gexp(i (o)).
L = I- -- (L-DD-1/AA,D A, 1/2) (exp(ie (+)). (1)
U
'Our definition of ()) 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 trainable weight matrix (see Section 3 for details on the network structure).
3

---

Note that when G' is undirected, L
( and L (4) reduce to the standard undirected Laplacians.
L and L are Hermitian. Theorem (Section 5 of the supplement) shows they are positive- semidefinite and thus are diagonalized by an orthonormal basis of complex eigenvectors u...... uN associated to real, nonnegative eigenvalues : Av. Similar to the traditional normalized Lapla- cian, Theorem 2 (Section of the supplement) shows the eigenvalues of L lie in 20, and we may factor L (g) matrix with (kk k) = Ae. and Ut is the conjugate transpose of U (a similar formula holds for L Furthermore, recall L BB" T, where B is the signed incidence matrix. Similarly, Theorem 3 (Section of the supplement) shows that L BBa) (B())),, where B(a) is a modified incidence matrix. The magnetic Laplacian encodes geometric information in its eigenvectors and eigenvalues. In the directed star graph (Section [ 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.
N = UAU*, where U is the N x N matrix whose k-th column is ug. A is the diagonal
3 MagNet
Most graph neural network architectures can be described as being either spectral or spatial. Spatial networks such as [43 21 14] typically extend convolution to graphs by performing a weighted average of features over neighborhoods N(u) = {o : (u, v) E 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 (uu) are not capable of assimilating the equally important information contained in {u (u, u) E 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 incorporate the magnetic Laplacian. Our approach is very general, and so for most of this section, we will perform our analysis for 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
3.1 Spectral convolution via the magnetic Laplacian
In this section, we let C denote a Hermitian, positive semidefinite matrix, such as the normalized or unnormalized magnetic Laplacian introduced Section on 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 x N matrix whose k-th column is ug. We define the directed graph Fourier transform for a signal x : V - C by
& Utx, x, so that ((k) (x, uz). We regard the eigenvectors uI...., un as the generalizations of discrete Fourier modes to directed graphs. Since U is unitary, we have the Fourier inversion formula
UX Σ k(k)uz
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) (k)))()) By ( this implies y UDiag(ý)& (UDiag())Ui) and so we say Y is convolution matrix if
Y UEU!
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 spectral network can be implemented in the spatial domain via polynomials of L by having be polynomial of A 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 normalized eigenvalue matrix, with entries in 11, by A = 2 Amac A - and assume
K Σ (xTx(A), R=0
E
for some real-valued 0,,-.., O2, where Th is the Chebyshev polynomial defined by To(æ)
1, 7 (a:) = x, and Tx (x) = 2x - + + 22)) for k. 2 2. With (UAUt) UA*U one has
K Yx = U
K
Eo.T((E)x
(4)
k=0
k=
where, analogous to A, we define C = 2 It is important to note that, due to the complex
Hermitian structure of C. the value Yx(u) aggregates information both from the values of x on No (u). the k-hop neighborhood of u, and the values of on {u dist(v, u) S kj. 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 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 (uu).
To obtain network similar [24 set K 1. assume that L D using Amax S 2 make the approximation Amax ~ 2, and set 01 = -0g With this, we obtain
Yx = fT + (D, 1/2 A, 1/2) o exp(iO( ()))x.
As in (24). we substitute I + (D, A.D. 1/2) @ exp(ie - 1/2 A.D. @ (x) This renormalization helps avoid instabilities arising from vanishing/exploding gradients and yields
Yx = -,-5111 ", 1/2 @ exp((i())),
(5)
where A, A, + and (i, - E, (i.))).
In theory, the matrix exp(ie(4)) 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 only necessary to compute the phase matrix for entries (u, v) where A, (u, v) + O. Thus, the efficiency of the proposed algorithm is comparable 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 factor of four because of the computational complexity of complex-vais -aalue valued multiplication).
3.2 The MagNet architecture
Let L be the number of convolution layers in our network, and let (0) be an N x Fo input feature (0)
(0)
matrix with columns x1 .... ... Since our filters are complex, we use a complex version of ReLU
defined by (=) = 2, if - -x/2 < arg(2) < T/2, and (22) = O otherwise (where arg(z) is the
complex argument of E C). Let F; be the number of channels in layer E, and for S f < L,
1 <<> i < Fi-1. and 1 < < Fe, we let (f) be convolution matrix defined in the sense of either
or Define the gh layer feature matrix (()) with columns (f)
(f)
XF as:
x =
Σ
(1-1) + bb/²)
(6)
with (0) = 660) and rbal(b)")) imag(b In matrix form we write ( z (x-1)
where (1) is a hidden layer of the form (6). In the numerical experiments reported in Section 5 we
utilize formulation with L = (g) In most cases we K 1, for which
( =a (x sell [(0)
(()
neigh + B(²)
5

---

real
Magettc grach
conolution conale frUU
Unwind
Dieceed gass
hast katurad)) 2:1
Vette höldice feature vector
Fally
connectic laer
Class probatalities
Figure 1: MagNet (I. 2) applied node classification.
where (-(0) selr and (((6)
neigh are learned weight matrices corresponding to the filter weights in and (v,,), = (b(e) .9......b for each v E V.
After the convolutional layers, we unwind the complex N FL matrix X into a real-valued N 2FL matrix, apply linear layer, consisting of migttliutipliiationn by a 2FL x ne weight matrix W(L+1) (where ne is the number of classes) and apply softmax. In experiments, we set I, 2 3. When L = 2, our network applied to node classification, as illustrated in Figure [ is given by
softmax Eettmax(unwintie (unwind (2) (z)() (x (X)
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.
Related work
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 real- valued, 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 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].
construct graph neural network. We also note there are numerous approaches
4.1 Neural networks for directed graphs
In [29 the authors construct directed Laplacian, via identities involving the random walk matrix and its stationary distribution II. When undirected, one can use the fact that II proportional to the degree vector to verify this directed Laplacian reduces to the standard normalized graph Laplacian. However, this method requires to strongly connected, unlike MagNet. The authors of [2) use a first-order proximity matrix AF (equivalent to A, here), well as two second-orde proximity matrices As, and A As... As, is defined by As, (u, v) * there exists such that (w, u), (w, v) E E, and As.., 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 fusion operator to share information across channels. Similarly, inspired by [3, [33], the authors consider several different symmetric Laplacian matrices corresponding to number of different graph motifs.
The method of 41 builds upon the ideas of both 20 and 42 and considers directed Laplacian similar to the one used in (29), but with PageRank matrix in place of the random-walk matrix. This allows for applications to graphs which are not strongly connected. Similar 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 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).

---

4.2 Related work on the magnetic Laplacian and Hermitian adjacency matrices
The magnetic Laplacian has been studied since at least [2 The name originates from its interpreta- tion quantum mechanical Hamiltonian of particle under magnetic flux. Early works focused on d-regular graphs, where the cigenvectors of the magnetic Laplacian are equivalent to those of the Hermitian adjacency matrix. The authors of (20), for example, show that using complex-valued Her- mitian 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
32
The magnetic Laplacian is also the subject of ongoing research in graph signal processing [1]] community detection 17,, and clustering [10] I6 [5]. For example, [16] uses the phase of the eigenvectors 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 may highlight various graph motifs. In our context, this indicates that q should be carefully tuned via cross- vosssvvliattion. Lastly, we note that numerous other directed graph Laplacians have been studied and applied to data science 7 g 35]. However, alluded to in Section these methods typically do not use complex Hermitian matrices.
Numerical experiments
5.1
Datasets
5.1.1 Directed Stochastic Block Model
We construct a directed stochastic block (DSBM) model as fol- lows. First we divide N vertices into ne equally-sized clusters Ci....: Cn.. We define fas.jhsi.jss,, to be a collection of prob- abilities, 0 < di.j S 1 with Qi,j Oj,i, and for an unordered pair u + create an undirected edge between u and v with probability Oij if u E Ci,
Majorit flw
Cj. To turn this undirected graph into a directed graph, we define (8,g)s
1
4
be collection of probabilities such that 0 < Brr S and BrJ + 83 = 1. For each undirected edge {u, v), we assign that edge a direction by the rule that the edge points from to with probability Brg if C, and v Cj, and points from e to u otherwise. If oss. is constant, then the only way to determine the clusters will be from the directional information.
2
In Figure 3 we plot the performance of MagNet and other methods
(a) Ordered meta-graph.
on variations of the DSBM. In each of these, we set n. 5 and the goal 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 a4j a = .1, .08, and .05 for i * j. which varies the density of inter-cluster edges, and set a,, = .1. Here we set 3 = .5 and Brg- = .05 for j. This corresponds to the ordered meta-graph in Figure 2a Figure abja uses the ordered meta- prath, but here we fix as = for all i.j, and set Br, 8", for j. and allow 3 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 a cyclic meta-graph structure as in Figure 2h (without the gray noise edges). Specifically,
edges Majortt flw
0
1
4
(b) Cyclic meta-graph.
or j i and ai.j = 0 otherwise. We define Big 8 -,,,, 1 1 8 when j (i 1) mod 5, and Br, = 0 otherwise. In Figure 3d we add noise to the cyclic structure of our meta-graph by setting æ;jj = =.1 for all i and Bi,j = 55 for all (i.j) connected by gray edge in Figure 2b (keeping Br., the same as in Figure 3d for the blue edges).
set 0gj = if
mod 5
Figure 2: Meta-graph: for the synthetic data sets.
5.1.2 Real datasets
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
7

---

labeled as student, project, course, staff, and faculty in the latter case. Telegram [5] is 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 [S, 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 of the supplement). Cora-ML and SiteSeer 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.
5.2 Training and implementation details
Node classification is performed in 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 valitinn/vaidaationneesttt split, which might be viewed 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.
60%/20%/20%
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 E or (v. u) E. The second type is existence prediction. The model is asked to predict if (u, v) E 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 in-degree and out-degree of nodes. In the supplement, we report two additional link prediction tasks based on a three-class classification setup: (u, v) E E. (v. u) E 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 con- volution defined 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 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 + (c + id) = (ac bd) + +((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 442 and two variants of 41). basic version (DiGraph) and 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 Bc| 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.
5.3 Results
We see that MagNet performs well across all tasks. As indicated in Table our cross-validation procedure selects y = 0 for node classification on the citation networks Cora-ML and CiteSeer. This means we achieved the best performance when regarding directional information suggesting symmetrization-bant
noise, methods are appropriate in the context of node classification on citation networks. This matches our intuition. For example, in ML, the task is to classify
8

---

Table 1: Node classification accuracy (%).
The best results are in bold and the second are underlined.
Type
Method
Cornell
Texas
Wisconsin Cora-ML
CiteSeer
Telegram
Score
ChebNet
79.8+5.00
79.2:17.5
81.611..3
8..0
66.7=1.6 70.2 16.8 6.94
Spectral
GCN
59.0:16.4
58.7:4.8
55.911.4
1.
66.0=1.5
73.4 +5,8
19.16
APPNP
58.7=4..0
57.0+4.88
51.8
12.6#1.4
66.9=1.8
67.3+3.0
18.75
SAGE
80.0#6.1
84.3
83.114.8
82.3#1.2
66.0=1.5 66.416.4
5.76
Spatial
GIN
57.9+-577
6..2++6.5
58.2+-5.1
78.1+22.0
63.3=2.5
86.444.3
16.53
GAT
57.6+
61.1++5.0
54.1+4.2
81.9+1.0
67.3-1.3
72.6+7.5
16.39
DGCN
6..314.3
71.747.44
65.5
1..
66.3=2.0
90.415..6
8.55
Directed
Digraph
66.816.2
64.9
59.613.8
1..
62.6=2.2
82.0
15.70
DiGraphIB
64.4+9.0
64.9+13.7
64.1+7.0
1.2
61.1=1.7
64.1
16.36
MagNet
8.0
83.
85.71332
79.8
67.5=1.8
87.6.12.9
1.10
This paper
Best
0.25
0.15
0.05
0.0
0.0
0.15
1.2
0.9
0.6
Nayle
PM
0.8
0.8
Digian
20.
20.6
Chailee
2.
20.6
0.4
0.3
0.2
0.2
0.2
8.57 0.56
(a) Ordered DSBM with (b) Ordered DSBM with (c) Cyclic DSBM with (d) Noisy Cyclic DSBM varying edge density.
varying net flow. ing net flow.
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 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 > O. These networks are similar to ours but with the classical graph Laplacian. This isolates the effects of the magnetic Laplacian and shows that is a valuable tool for encoding directional information. MagNet also compares favorably to non-spectral methods 4% improvement
on the WebKB networks (Cornell, Texas. Wisconsin). Indeed, MagNet obtains 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 method with score of zero indicates the method is the top performing method on each data set. As reported Table I MagNet achieved a best score of 1. percent.
On the DSBM datasets, as illustrated in Figure (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 33| these methods are well suited for networks with a cyclic meta- veta-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 3ch with R .I, whereas q 2 .2 is

---

Table Link prediction accuracy (%). The best results are in bold and the second are underlined.
Direction prediction
Existence prediction
Cornell
Wisconsin Cora-ML CiteSeer
Cornell
Wisconsin
Cora-ML CiteSeer
ChebNet GCN
71.0+5..5
67.5114.5
72.7=1.55
68.0 80.1
1.
80,0 77.4
56.211..7
71.0:1..0
7.
68.942.8 75.1
7..1
81.6+10.5 76.9
APPNP
69.5+.9.0
75.1+:3.5
83.7:10.7
77.9
7..9
75.7+:2.2
82.5::0.6
78.6+1..7
SAGE
75.2++1..0
72.0+:3.5
68.2++088
68.7+
79.8+2.4
77.3+2299
75.0++0.0
1..1
GIN
69.3++6.0
74.8++3.7
83.2+00.9
76.3+1.4
74.5+2.1
7..2+119
0..5+0.7
77.9+0.7
GAT
67.9+11.1
53.242.6
50.0
50.6:0.5
77.943.2
74.6=0.0
75.0=000
75.0+0.0
DGCN
80.7+6.3
74.5+7.2
79.6+1.5
78.5+2.3
80.0+:3.9
2.0
82.1+0.55
81,2+0.4
DiGraph
7..3+119
82.3+449
80.8+1.1
81.0+1.1
80.6+2.5
82.8
01.8+
0.6
DiGraphIB
79.8++4.8
82.0++499
83.4+1.1
82,5+
80.5++3.6
82.4+2.2
82.2+0055
81.0++..5
MagNet 82.9+3.5
83.3++3.0
86.5+
84.8+112
81.1+33.3
8.2
02.7+0077
79.940.6
Best 4
0.20
0.10
0.20
0.15
0.25
0.05
0.05
0.05
preferred for the other three DSBM tests; we leave a more in-depth investigation for future work. Further details are available in Section of the supplement.
For link prediction, achieve the best performance on seven out of eight tests shown in Table 2] We also note that Table 2 reports optimal non-zero values for each task. This indicates that incorporating directional information is important for link prediction, even citation networks such as Cora and CiteSeer. This matches our intuition, since there is a clear difference between 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.
6 Conclusion
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 the best way to extend it to weighted mixed graphs (with both directed and undirected edges). Our network does not incorporate 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 greater lesser impact on society than other graph neural network algorithms.
Acknowledgments
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-RO1GMI 135929 to M.H. and supporting X.Z, N.B.J: the University of Oxford [the Clarendon scholarship to Y.H.J: the National Science Foundation [grant DMS-1845856 to M.H.J; and the Department of Energy Igrant DE-SC0021152 to M.H.).
10

---

References
[1] James Atwood and Don Towsley. niffusion-convolttion neural networks. In D. Lee,
M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, pages 1993-2001. Curran Associates, Inc., 2016.
[2] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation. 15(6):1373-136. 2003.
[3] Austin R Benson, David F Gleich, and Jure Leskovec. Higher-order organization of complex networks. Science, 16366655)113-116 2016.
[4] Aleksandar Bojchevski and Stephan Günnemann. Deep Gaussian embedding of graphs: Un- supervised inductive learning via ranking. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2017.
[5] Alexandre Bovet and Peter Grindrod. gram. attps://wwrz rossarchhaeeecatteeee.e......... htt/:/uliiaaiiio//4466555.....e Activiittttiitttttt v21 2020.
The activity of the far right on tele-
of_ _are__aa___ae
[6] Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and deep locally connected networks on graphs. In International Conference on Learning Representations (ICLR), 2014.
[7] Fan Chung. Laplacians and the Cheeger inequality for directed graphs. Annals of Combinatorics, 9(1):1-19, 2005.
[8] Fan Chung and Mark Kempton. local clustering algorithm for connection graphs In International Workshop on Algorithms and Models for the Web-Graph, pages 26-43. Springer, 2013.
[9] Fan RK Chung and Fan Chung Graham. Spectral graph theory. Number 92, American Mathematical Soc., 1997.
[10] Alexander Cloninger. A note on markov normalized magnetic eigenmaps. Applied and Computational Harmonic Analysis, 43(2):370- - 2017.
[11] Ronald R Coifman and Stéphane Lafon. Diffusion maps. Applied and computational harmonic analysis. 21(1):5-30, 2006.
[12] Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti. Hermitian matrices for clustering directed graphs: insights and applications. In International Conference Artificial Intelligence and Statistics, pages 983-992. PMLR, 2020.
[13] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems 29, pages 3844-3852, 2016.
[14] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alan Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 28, pages 2224-2232. Curran Associates, Inc., 2015.
[15] Bruno Messias F. de Resende and Luciano da F. Costa. Characterization and comparison of large directed networks through the spectra of the magnetic laplacian. Chaos: An Interdisciplinary Journal of Nonlinear Science, 30(7):073141, 2020.
[16] Michael Fanuel, Carlos M. Alaíz, Ángela Fernández, and Johan A.K. Suykens. Magnetic cigenmaps for the visualization of directed networks. Applied and Computational Harmonic Analysis, 44: 14:1999199, 2018.
[17] Michaël Fanuel, Carlos Alaiz, and Johan AK Suykens. Magnetic eigenmaps for community detection in directed networks. Physical Review E, 92(2):022302, 2017.

---

[18] Matthias Fey, Jan E Lenssen, Frank Weichert, and Jure Leskovec. GNNAutoScale: Scalable and expressive graph neural networks via historical embeddings. In International Conference on Machine Learning (ICML), 2021.
[19] Satoshi Furutani, Toshiki Shibahara, Mitsuaki Akiyama, Kunio Hato, and Masaki Aida. Graph signal processing for directed graphs based on the hermitian laplacian. In Machine Learning and Knowledge Discovery Databases. pages 447-463, 2020.
[20] Krystal Guo and Bojan Mohar. Hermitian adjacency matrix of digraphs and mixed graphs. Journal of Graph Theory, 85()):217-248, 2017..
[21] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Proceedings of the 31st International Conference Neural Information Processing Systems, NIPS' 17, page 1025-1035, Red Hook, NY, USA, 2017. Curran Associates Inc.
[22] David K Hammond, Pierre Vandergheynst, and Rémi Gribonval. Wavelets graphs via spectral graph theory. Applied and Computational Harmonic Analysis, 30(2):29-150,, 2011.
[23] Yixuan He, Gesine Reinert, and Mihai Cucuringu. Digrac: Digraph clustering with flow imbalance. arXiv preprint 211.::2000.01994 2021.
[24] Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[25] Johannes Kliepera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR. 2019.
[26] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. In International Conference Learning Representations, 2019.
[27] Ron Levie, Wei Huang. Lorenzo Bucci, Michael M Bronstein, and Gitta Kutyniok. Trans- ferability of spectral graph convolutional neural networks. arXiv preprint arXiv: 2019.
[28] Elliott H Lieb and Michael Loss. Fluxes, laplacians, and kasteleyn's theorem. In Statistical Mechanics, pages 457-483. Springer, 1993.
[29] Yi Ma, Jianye Hao, Yaodong Yang, Han Li, Junqi Jin, and Guangyong Chen. Spectral-based graph convolutional network for directed graphs. 1xXiv:197.008900 2019.
[30] Antonio G Marques, Santiago Segarra, and Gonzalo Matcos. Signal processing on directed graphs: The role of edge directionality when processing and learning from network data. IEFE Signal Processing Magazine, 37(6):99-116, 2020.
[31] Péter Mernyci and Cătälina Cangea. Wiki-cs: A wikipedia- benchmark for graph neural networks. arXiv preprint arXiv:200..02901 2020.
[32] Bojan Mohar. A new kind of hermitian matrices for digraphs. Linear Algebra and its Applications, 584:343-352 2020.
[33] Federico Monti, Karl Otness, and Michael M. Bronstein. Motifnet: A motif-based graph convolutional network for directed graphs. In 2018 IEEE Data Science Workshop. pages 225-228, 2018.
[34] Antonio Ortega, Pascal Frossard, Jelena Kovačević, José MF Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106(5):808-82,, 2018.
[35] William R Palmer and Tian Zheng. Spectral clustering for directed networks. Computational Intelligence, 943, 2021.
Studies in
[36] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint 0522 2020.
12

---

[37] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. arXiv preprint 1rXiv:1909.1380 13021, 2019.
[38]
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. In Proceedings of IEEE computer society conference on computer vision and pattern recognition, pages 731-737.
IEEE, 1997.
[39] Aaron Sim, Maciej Wiatrak, Angus Brayne, Páidí Creed, and Saee Paliwal. Directed graph embeddings in pseudo-riemannian manifolds. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 9681-9690. PMLR, 2021.
[40] Daniel A Spielman and Shang-Hua Teng. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 8 81-90. 2004.
[41] Zekun Tong, Yuxuan Liang, Changsheng Sun, Xinke Li, David Rosenblum, and Andrew Lim. Digraph inception convolutional networks. In NeurIPS, 2020.
[42] Zekun Tong, Yuxuan Liang. Changsheng Sun, David S. Rosenblum, and Andrew Lim. Directed graph convolutional network. arXiv:2004. 13970,, 2020.
[43] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018.
[44] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip Yu. comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 32(1):4-24, 2020.
[45] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural 2018.
networks? arXiv preprint
[46] Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint arXiv: 2.04444, 2018.
13


Reviews:
[{"review_id": "iE5MkUS37D", "reviewer": "Reviewer_3ZNa", "summary": "This work focus on modeling directed graph in the spectral domain, which is not handled well by current spatial and spectral methods. The major contribution is using the Hermitian matrix to encode direction information.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nThis paper proposed a graph neural network for directed graphs. To encode direction, the Hermitian matrix is used as a Laplacian substitute in normal graph convolution.\n\n### 1 Motivation \n- Directed graph is not well handled by the current graph neural network, and the author clearly presents the pros and cons of spectral and spatial methods, showing a new approach is needed.\n- The example in the introduction shows a suitable potential to address the directionality. However, it is not clear if the Hermitian matrix can distinguish forward, backward, bi-direction, and no link.\n- In the spatial method, what is the benefit to consider a neighbor even it is not connected through a directed link? \n\n### 2 Presentation- Overall, the presentation is good, but there exist several weaknesses. \n- Sections 2 and 3 present a workflow that is very similar to the most popular graph convolution. Obviously, it is better to focus on the proposed component.\n- several related works are missing such as ICML 21 Directed Graph Embeddings in Pseudo-Riemannian Manifolds, and ICLR 20 DIMENet\n\n### 3 Technical analysis- The paper proposes Hermitian matrices as a substitute for graph Laplacian.\n- The major concern is that how the Hermitian matrix can distinguish directions. In the definition of phase matrix in line 103, how to tell (1) no link between u and v, from (2) bi-directional link between u and v ? Do they both equal to zero?\n- The phase matrix is as large as the adjacency matrix, there may be an efficiency issue when the graph is large.\n\n### 4 Experiment- The proposed method has been evaluated on both synthetic and real-world graph datasets.\n- The results of link prediction well support the proposed method, but the performance on the node classification task is not significantly better than the baselines.\n- Since there might be an efficiency issue, efficiency evaluation is expected.\n\n### After rebuttal\nThe author well cleared my concerns and the score was updated.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "- describe how the proposed method distinguishes forward, backward, bi-direction, and no link.\n- discuss and study the efficiency problem: how much will the additional phase matrix and its multiplication take?\n- present the implementation of multiplication between complex matrices", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "RHcg59lE5kH", "reviewer": "Reviewer_ie35", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I will begin by discussing the strengths of this paper, then move on to the weaknesses, followed by some brief comments.\n\n**Strengths**\n\n1. The presentation of this paper is quite nice. It is simple, well-structured, and readable. The magnetic Laplacian is defined and explained clearly, and the convolutional networks are well-explained in the context of the existing literature. The experiments are also described well. This paper was very easy to read and understand.\n\n2. The \"MagNet\" architecture is not overly dependent on a particular convolutional structure, as indicated by the authors explaining how to use the magnetic Laplacian in multiple contexts. This makes the proposed approach appealing, as it is basically a drop-in change that is appropriate for handling directed graphs.\n\n3. The empirical validation is quite convincing. The authors were quite thorough in describing their experiments, and designed the synthetic datasets carefully to demonstrate how MagNet can fully leverage the directed information while approaches based on symmetrized matrices can't. Moreover, the results on real data, including common benchmarks, are strong. Another strength of the proposed approach is in the selection of the parameter $q$ via cross-validation. Since $q$ reflects the utility of the directional information in the dataset, it is useful itself as an output of the model for interpretation of the dataset's properties, e.g., the importance of directionality in the Cora/CiteSeer networks for link prediction, but not for classification. They also compare to a good spread of other neural approaches.\n\n4. The magnetic Laplacian is a novel addition in this context, which I have not seen before in a paper on graph neural networks.\n\n**Weaknesses**\n\n1. Some reasonable approaches were not addressed in the experiments. In the introduction, it is noted that the magnetic Laplacian has been used recently for community detection and clustering. On at least some of the experiments, it seems like it would be appropriate to apply these simple approaches to compare to, especially given that the node data on the synthetic dataset is randomly sampled.\n\n2. The description of how $q$ was selected is vague. I can only guess how it was done: this should be described in more detail, perhaps in the supplement.\n\n3. There are no comments on complexity. Although it is mentioned that this approach is not scalable in its current form in the Limitations section, there is no discussion on this in the body of the paper. I would have liked to see a better explanation of this, perhaps via a simple description of the computational complexity. This comment also holds for the selection of the $q$ parameter as mentioned above.\n\n4. The neural architecture itself is not particularly novel, as it is directly adapted from previous papers. However, I do not view this as much of a weakness, since the point of this paper is the use of the magnetic Laplacian as a way to encode the directed structure, as well as the tuning of the parameter $q$.\n\n**Comments**\n\n1. Overall thoughts: this paper does not advance the field in terms of graph neural network architectures, their training, or theoretical underpinnings. However, it does introduce an operator, namely the magnetic Laplacian, that is likely unfamiliar to many in the community. By combining graph neural networks with proper parameter selection for the magnetic Laplacian, this approach proves effective in handling data on directed graphs. For this reason, I recommend this paper for acceptance.\n\n2. This is not an important question to address, but perhaps it could improve the presentation. A common way to describe the graph Laplacian for undirected graphs is as the product $L=BB^\\top$, where $B$ is the signed incidence matrix. Given that the magnetic Laplacian is Hermitian, it admits a similar factorization for some matrix other than $B$. Does it admit a factorization in terms of a modified incidence matrix?\n\n**Editorial** (no influence on decision)\n\n1. Line 42, \"informatio\" is misspelled\n\n2. Lines 104-105, \"component-wise\" and \"componentwise\" are not consistent\n\n3. Lines 58,189, and elsewhere, \"link-prediction\" and \"link prediction\" are not consistent\n\n4. The plot in Figure 2 isn't very attractive. Perhaps the legend should be separated from all the plots to emphasize that it is shared, as well as to make it more readable.\n\n5. Some of the citations do not look very good. Please take another pass on these, with a particular focus on capitalization. Some problematic citations I noticed were [7],[9],[10],[15],[18],[23],[25],[28],[29]. There are also inconsistencies on venue citation, for instance between [1],[20], and [36], or in capitalization between [10] and [11]. I would suggest using the `@string` macro in BibTeX to ensure consistent venue naming, e.g.,\n\n```\n@string{iclr={International Conference on Learning Representations}}\n\n@article{\ntitle={Absurdly Deep Convolutional Neural Networks},\nauthor={A. Authors},\njournal=iclr,\n}\n```\n\n**After Rebuttal**\n\nThanks to the authors for considering my comments as well as the comments of the other authors. I am not sure if the paper is in the top 50% of accepted papers, but I still believe that it should be accepted. Thus, I am keeping my score the same. The authors have done a good job with this work.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The societal impact is not notable compared to other graph neural network literature. Limitations on scalability are mentioned at the end, but should be discussed more in the body of the paper, as mentioned in the main review.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "0ULusubYJLe", "reviewer": "Reviewer_YVEh", "summary": "This paper proposes to use magnetic Laplacian within GNNs to better capture the direction information. They introduce a spectral GNN based on this and show the performance on some node and link prediction tasks.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is well-written and easy to follow. It also has a good justification of why their method works, and in practice they show that they are getting good results on some node and link prediction benchmarks. The idea is not new in graph signal processing community but it seems it is the first time that is being incorporated into GNNs as an inductive bias. There are three main concerns/questions that I have:\n\n1- Sparse representation of graphs is very important as many real-world graph problems deal with huge graphs. However it seems that the exponential of phase matrix is dense because even if there is no connection between two nodes the exp(phase) will be 1. Can you comment on this?\n\n2 - One simple baseline for directed graphs can be decoupling the incoming edges from outgoing edges for each node, learn two disentangled representations, and then aggregate them. Any thoughts how this simple baseline would perform compared to  your model? Also, approaches such as Graph diffusion convolution (GDC) [1], or Graphormer [2] should also be able to capture direction information using diffusion and structural self-attention, respectively. I wonder how such models would perform compared to yours.\n\n3- Also I have two concerns regarding the performance and scalability of the proposed models. Especifically, it seems that all your evaluations are performed on transductive taks and it is not clear how your method would work on inductive tasks. Moreover, the benchmarks that you have chosen are fairly small with maximum of  3,312 nodes for node prediction and 11,701 nodes for link prediction tasks. I recommend to evaluate on more realistic directed benchmarks such as ogbn-papers100M, ogbn-arxiv, ogbn-mag, ogbl-citation2, ogbl-wikikg2. (Thanks for explicitly mentioning this in limitations section: \"is not scalable to large graphs in \nits current form (although this may be addressed in future work).\"\n\n4- Finally, I couldn't find information about how you would treat edge features in your framework if available. \n\n\n[1] https://proceedings.neurips.cc/paper/2019/hash/23c894276a2c5a16470e6a31f4618d73-Abstract.html\n\n[2] https://arxiv.org/abs/2106.05234\n\nAfter receiving the author responses and also reading the reviews of the other reviewers, I decided to increase the score. However, I still think showing results for inductive tasks and tasks with edge features can make the paper stronger.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a new GNN for directed graphs using magnetic Laplacian. Specifically, the authors use a complex operator encoding edge direction via phase. This is an interesting approach, which was appreciated by the reviewers. The authors provided detailed responses that addressed the reviewers' comments in a satisfactory manner. The AC recommends acceptance.  

Decision: Accept (Poster)