Source-linked AI summary
MagNet: A Neural Network for Directed Graphs
Xitong Zhang, Yixuan He, Nathan Brugnone, Michael Perlmutter, Matthew Hirn
TL;DR
Graph neural networks often focus on undirected graphs even though many datasets are naturally directed, creating a gap for spectral methods. MagNet addresses this gap with a magnetic-Laplacian-based spectral GNN whose complex phases encode direction, and it performs strongly across directed node-classification and link-prediction benchmarks. The framework also generalizes to other spectral GNN architectures.
Problem
Many graph datasets are naturally directed, but most graph neural network research focuses on undirected graphs and often symmetrizes directed data.
Method
MagNet uses a complex Hermitian magnetic Laplacian whose magnitude represents edge presence and phase represents direction, with q adapting spectral information to directed motifs.
Results
MagNet achieves the best or second-best performance on five of six node-classification tasks and the best performance on seven of eight link-prediction tasks.
Takeaways & Limitations
MagNet provides a directed-graph extension of spectral graph convolution and can be adapted to nearly any spectral network architecture.
Takeaways & Limitations
The method is not currently scalable to large graphs and its best extension to weighted mixed graphs remains unclear.
Abstract
from arXiv · showhide
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 spectral 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 spectral GNN architectures.
1 Introduction
MagNet addresses the difficulty of applying spectral graph neural networks to directed graphs without discarding edge direction. It uses the magnetic Laplacian and generalizes spectral architectures, achieving strong results across node-classification and link-prediction tasks.
- Motivation: Directed datasets such as university-website networks naturally encode asymmetric relationships, motivating graph neural networks designed for directed graphs.A website may link to another without receiving a reciprocal link.
- Challenge: Most existing directed extensions of spatial graph CNNs symmetrize adjacency matrices, effectively converting directed data into undirected graphs.Some experiments report improved performance after treating citation networks as undirected.
- Challenge: Spectral extension is difficult because asymmetric adjacency matrices do not yield an obvious symmetric real-valued Laplacian with a full set of real eigenvalues.MagNet instead uses a complex-valued Hermitian magnetic Laplacian whose phases encode directed asymmetry.
- Contribution: MagNet adapts spectral graph neural networks to directed graphs by incorporating complex Hermitian matrices, recovering prior networks when q = 0.The framework is not tied to one architecture and can be adapted to nearly any spectral network.
- Results: MagNet achieves the best or second-best performance on five of six node-classification tasks and the best performance on seven of eight link-prediction tasks.It also performs well on difficult synthetic node-classification data.
2 The magnetic Laplacian
The magnetic Laplacian provides a spectral representation for directed graphs that preserves Hermitian structure while encoding direction through complex phases. Its charge parameter controls how spectral information responds to directed graph motifs.
- Problem: For undirected graphs, the classical Laplacian is symmetric positive semidefinite, whereas asymmetric directed adjacency can produce complex eigenvalues that hinder spectral methods.This is the central technical obstacle in extending graph spectral theory and signal processing to directed graphs.
- Representation: MagNet represents directed graphs with a complex Hermitian matrix whose magnitude indicates edge presence and whose phase indicates edge direction.This representation avoids relying on a single symmetric real-valued matrix that cannot uniquely encode direction.
- Construction: The magnetic adjacency matrix combines a symmetrized adjacency magnitude with a parameterized phase matrix through componentwise multiplication.The phase matrix is generated by the charge parameter q.
- Spectral properties: The magnetic Laplacian is Hermitian and positive semidefinite, so it has orthonormal complex eigenvectors associated with real nonnegative eigenvalues.Its eigenvalues lie in [0, 2], and it admits a spectral factorization using a unitary eigenvector matrix.
- Spectral interpretation: Its spectral information can encode direction in eigenvectors, eigenvalues, or both, depending on graph structure such as directed stars and directed cycles.This means directional information is not confined to one spectral component across all graphs.
3 MagNet
MagNet extends spectral graph convolution to directed graphs by using the magnetic Laplacian and complex-valued spectral filters. Polynomial filters implement the convolution spatially while aggregating information along both incoming and outgoing directed paths.
- Architecture: MagNet adapts three spectral graph neural network architectures to directed graphs using the magnetic Laplacian or another complex Hermitian positive semidefinite matrix.The approach is designed to be general rather than tied to one architecture.
- Spectral convolution: The directed graph Fourier transform represents node signals in the basis of complex Laplacian eigenvectors, and convolution multiplies signal and filter coefficients in that basis.The resulting convolution matrix is formed from the eigenvector matrix and a diagonal spectral filter.
- Spectral convolution: Polynomial filters of the magnetic Laplacian implement spectral networks in the spatial domain without explicit eigendecomposition.This reduces trainable parameters, avoids expensive diagonalization, and improves stability to perturbations.
- Directed aggregation: Because the filter matrix is complex Hermitian, a k-hop convolution aggregates features from vertices reachable from a node and vertices that can reach it.Phase differences also allow the filter to use directional distinctions between edges.
- Network outputs: The network applies complex convolutional layers and a complex ReLU, then unwinds complex features into real and imaginary parts before classification.For link prediction, node-pair rows are concatenated after the unwind layer to form edge features.
4 Related work
Related work covers directed-graph neural networks and magnetic-Laplacian research, positioning MagNet as the first graph neural network built using the magnetic Laplacian.
- Prior directed-graph neural networks use real-valued symmetric matrices rather than complex numbers to encode directionality.
- MagNet is presented as the first graph neural network constructed using the magnetic Laplacian.
- Existing directed Laplacian methods use random-walk or PageRank constructions and may require strong connectivity or higher-order proximity representations.
- Magnetic-Laplacian work includes complex Hermitian adjacency matrices and eigenvector phases for embeddings and structural analysis.
- The magnetic Laplacian has been studied in graph signal processing, community detection, and clustering, with q choices highlighting different graph motifs.
5 Numerical experiments
The experiments evaluate MagNet on synthetic directed stochastic block models and real datasets for node classification and link prediction. MagNet performs strongly across tasks, with especially broad gains in link prediction and settings where directionality matters.
- The study evaluates MagNet on node classification and link prediction using benchmark datasets and a directed stochastic block model.
- Directed Stochastic Block Model: The directed stochastic block model varies inter-cluster density, directional flow, cyclic structure, and noise while preserving five vertex clusters.
- Results: For citation-network node classification, cross-validation selects q = 0, whereas all other datasets use nonzero q values, indicating task-dependent value in directional information.
- Results: MagNet improves over ChebNet and GCN by at least four percentage points on the four datasets with q > 0.
- Results: On noisy approximately cyclic DSBM graphs, MagNet remains effective while DGCN and DiGraphIB deteriorate significantly.
- Results: Link-prediction experiments select nonzero q values for every reported task, including citation networks, supporting the use of directional information.
6 Conclusion
The conclusion presents MagNet as a magnetic-Laplacian-based neural network for directed graphs and reports effectiveness across link prediction and node classification on real and synthetic data. It also identifies limitations and directions for extending the approach.
- MagNet is a neural network for directed graphs based on the magnetic Laplacian.
- The experiments support incorporating directional information through a complex Hermitian matrix for link prediction and node classification.
- Future work includes using multiple q values across channels, studying magnetic-Laplacian normalizations, and integrating it into other architectures.
- The method has natural extensions to weighted directed graphs when all edges are directed, but its extension to weighted mixed graphs is unclear.
C Further implementation details
The implementation compares MagNet with several graph neural networks using specified training limits, regularization, hyperparameter searches, and task-specific features.
- MagNet and ChebNet use K = 1, while other methods receive method-specific settings for heads, propagation steps, or PageRank coefficients.
- Models train for up to 3000 epochs with early stopping after 500 epochs without validation improvement, and include dropout before the final linear layer.
- Adam optimization and ℓ2 regularization with hyperparameter 5e−4 are used, with testing models selected through validation-accuracy grid search.
- Link prediction uses in-degree and out-degree node features, whereas node classification uses synthetic one-dimensional normal features or original features.
D Datasets
The study evaluates node classification and link prediction on real and synthetic directed-graph datasets using defined splits, features, and edge-pair prediction tasks.
- Node classification: Node classification uses six real datasets, including citation, university, and Telegram networks, together with synthetic DSBM graphs.
- Node classification: Node-classification evaluation uses random folds or established dataset folds, with citation datasets following the split from.
- Link prediction: Link prediction uses eight real datasets and replaces original node features with in-degree and out-degree to expose adjacency-derived structural information.
- Link prediction: The link-prediction construction includes existence, direction, and three-class direction tasks over ordered vertex pairs, with 15% testing and 5% validation edges.
E Eigenvalues of the magnetic Laplacian
The appendix establishes spectral properties of the magnetic Laplacian: both normalized and unnormalized forms are positive semidefinite, and normalized eigenvalues lie in [0, 2].
- The normalized magnetic Laplacian has real, nonnegative eigenvalues because it is positive semidefinite and Hermitian.
- For every q ≥ 0, the unnormalized and normalized magnetic Laplacians are positive semidefinite.
- The proof uses a quadratic-form argument together with diagonal degree matrices and the symmetry of the associated adjacency matrix.
- The eigenvalues of the normalized magnetic Laplacian are contained in the interval [0, 2].
F The eigenvectors and eigenvalues of directed stars and cycles
The magnetic Laplacian distributes directional information between eigenvectors and eigenvalues depending on graph structure. Directed stars encode direction in eigenvectors, whereas directed cycles encode it through q-dependent eigenvalues.
- Directed cycles: Directed cycles have classical Fourier-mode eigenvectors independent of q, but their eigenvalues depend on q.Thus, cycle direction is represented through the eigenvalues rather than changes in the eigenvectors.
- Spectral encoding: The star and cycle examples show that the magnetic Laplacian can place directional information in different spectral components.For stars, direction appears in eigenvectors; for cycles, it appears in eigenvalues.
- Directed stars: Directed stars encode source-versus-sink direction in eigenvector imaginary parts, while their eigenvalues provide no directional information.The leading eigenvectors identify the central vertex, and the sign of their imaginary parts distinguishes whether it is a source or sink.
G Expanded details of numerical results
The expanded experiments report node-classification and link-prediction results across synthetic and real directed-graph tasks, with MagNet generally performing strongly. Results also reveal task-dependent trade-offs between directed and undirected information.
- Experimental coverage: The appendix reports node-classification results for four DSBM graph types and additional link-prediction results, summarized as mean ± standard deviation.Tables 5–9 cover DSBM node classification, while Tables 10–15 cover expanded link-prediction settings.
- Baseline implementations: Symmetrizing adjacency improved node-classification performance for most baseline networks on most real datasets.The symmetric implementations were not tested on synthetic DSBM datasets because those datasets emphasize directional information.
- Link prediction: MagNet obtains top performance in 22/32 noiseless-label link-prediction experiments across four tables.These experiments exclude undirected edges and multi-edges, so all labels are well-defined and noiseless.
- Link prediction: MagNet achieves the highest testing accuracy in 20/24 experiments aside from Table 14.Digraph is best in 3/8 experiments in Table 14, while MagNet is best in 2/8 and is top or statistically tied in 5/8 datasets.
- Link prediction: For Table 14's three-class link prediction, MagNet is either the top performer or on par with the top method in 5/8 datasets.The task combines edge-existence and edge-direction prediction, making it more difficult for MagNet than the other tasks.
H Optimal q values for synthetic data
Optimal q values vary with how important direction is for synthetic-graph node classification. Smaller q suffices when connectivity reveals clusters, while larger q better encodes essential directional information.
- Synthetic graphs: For cyclic DSBM graphs, optimal q is smaller than for ordered and noisy cyclic DSBM graphs.Clusters in cyclic DSBM graphs are relatively clear from connectivity even without direction information.
- Synthetic graphs: When direction is less critical, q < 0.15 is enough; when direction is crucial, q > 0.15 is needed for better performance.Larger q encodes more directional information in the phase matrix.
- Synthetic graphs: If clusters are evident in the symmetrized adjacency matrix, q = 0 reduces MagNet to ChebNet.The paper reports this reduction for Cora-ML and CiteSeer in Table 9.