Abstract
Traditional Graph Convolutional Networks (GCNs) often struggle with directed graphs by treating edges as symmetric, thereby losing critical directional information. We present DiGAE (Directed Graph Auto-Encoder), a framework that models nodes through dual "source" and "target" roles. Grounded in a directed extension of the Weisfeiler-Leman algorithm, DiGAE utilizes tunable degree-normalization to capture asymmetric edge dynamics. Experimental results on citation and web networks demonstrate that DiGAE achieves state-of-the-art link prediction accuracy while offering up to 15x speed improvements over existing baselines.
Introduction
The majority of Graph Neural Networks (GNNs) are designed for undirected graphs. However, real-world networks—ranging from citation indices to knowledge graphs—are inherently directed. Treating these as undirected graphs discards the "directionality" that often defines the relationship (e.g., cause vs. effect). Existing solutions for directed graphs frequently rely on complex spectral methods or expensive kernels that hinder scalability. The challenge lies in developing an architecture that respects edge asymmetry without sacrificing the efficiency of standard GCNs.
Methodology: The DiGAE Framework
DiGAE addresses the limitations of undirected models through three primary innovations:
1. Dual-Vector Encoding
Instead of a single latent representation, each node $i$ is assigned a pair of vectors: a source vector ($s_i$) and a target vector ($t_i$). This allows the model to distinguish between a node's role as an origin of information (hub) and its role as a destination (authority).
2. Directed WL-Refinement and Message Passing
The model is theoretically supported by a directed extension of the Weisfeiler-Leman (1-WL) algorithm. The message-passing scheme updates source representations by aggregating the target representations of neighbors, and vice versa. This process is controlled by two hyperparameters, $\alpha$ and $\beta$, which scale the influence of in-degrees and out-degrees respectively.
3. Asymmetric Decoding
To reconstruct the graph, the decoder employs an asymmetric inner product ($s_i \cdot t_j$) followed by a sigmoid function. This naturally predicts the probability of a directed edge from node $i$ to node $j$, preserving the inherent asymmetry of the input data.
Experimental Evaluation
The authors evaluated DiGAE on several benchmarks, including citation networks (CoraML, CiteSeer, Pubmed) and web datasets (Texas, Cornell, Wisconsin). The primary task was directed link prediction: predicting both the existence and the specific direction of missing edges.
Key Results
DiGAE consistently outperformed both standard GAEs and specialized directed baselines like "Gravity GAE." Notably, a single-layer variant (DiGAE-1L) often yielded the best results, suggesting that local directional roles are more informative for link prediction than deep, multi-hop aggregations which risk over-smoothing.
As shown in the table above, DiGAE-1L achieved an AUC of 92.76% on CiteSeer, a significant jump from the 74.35% of standard GAE. Furthermore, DiGAE is remarkably efficient; on CoraML, it trained in approximately 7.6 seconds, making it nearly 7x faster than Gravity GAE.
Discussion and Future Work
The success of DiGAE highlights the importance of hyperparameter tuning for degree normalization ($\alpha$ and $\beta$). These parameters allow the model to adapt to different graph topologies by prioritizing either "authority" or "hub" dynamics.
Future research directions include transitioning from global $\alpha/\beta$ constants to learnable parameters that adapt to local neighborhood densities, and a deeper investigation into the spectral properties of the directed operators used in the message-passing scheme. By providing a simple yet theoretically grounded approach to directed graphs, DiGAE offers a scalable path forward for modeling complex, asymmetric real-world data.
Summary updated