Abstract
Directed Graph Auto-Encoders (DiGAE) address the limitations of standard Graph Convolutional Networks (GCNs) when applied to directed graphs. By learning dual latent representations for nodes as both sources and targets, DiGAE captures asymmetric transitivity and semantic directionality. Grounded in a directed version of the Weisfeiler-Leman algorithm, the framework achieves state-of-the-art performance in link prediction while offering significant computational efficiency, running up to 15 times faster than competing models.
Introduction
Most Graph Convolutional Networks (GCNs) are designed for undirected graphs. When applied to directed graphs—such as citation networks, web links, or causal pathways—they often "cheat" by symmetrizing the adjacency matrix. This effectively treats a one-way street like a two-way road, losing critical semantic meaning. In a citation graph, for instance, paper A citing paper B indicates a flow of ideas and time that is lost if the connection is treated as bidirectional.
Existing methods that handle directionality often produce single-vector representations that struggle to capture the "dual role" of a node (e.g., a paper acting as an influential source versus a comprehensive survey target). Furthermore, many current directed GCNs are computationally heavy or rely on complex preprocessing like calculating Perron vectors.
Methodology: The Dual-Role Framework
The authors introduce DiGAE, which breaks from the single-vector tradition by assigning every node two distinct embeddings:
- Source Vector ($s_i$): Encodes the node's behavior when it initiates a link.
- Target Vector ($t_i$): Encodes the node's behavior when it receives a link.
Directed WL Refinement
The theoretical foundation of DiGAE extends the Weisfeiler-Leman (WL) algorithm—a classic method for testing graph isomorphism—to directed graphs. The paper proves that their "pair-of-labels" refinement scheme is mathematically equivalent to running standard WL on a bipartite version of the directed graph.
Architecture
The encoder uses parameterized GCN layers that update source and target embeddings in an alternating fashion. A key innovation is the use of tunable hyperparameters ($\alpha$ and $\beta$) to weight the importance of in-degrees and out-degrees during message passing. The decoder uses an asymmetric inner product ($\sigma(Z_S Z_T^T)$) to reconstruct the graph, naturally allowing the model to predict directed edges (e.g., $u \to v$ exists while $v \to u$ does not).
Experimental Setup
The model was evaluated on two classic citation network benchmarks:
- CoraML: 2,995 nodes and 8,416 edges representing machine learning publications.
- CiteSeer: 3,312 nodes and 4,715 edges representing scientific papers.
The primary task was directed link prediction: hiding 15% of the edges and requiring the model to predict not just which nodes are connected, but in which direction.
Key Results and Insights
DiGAE-1L (the single-layer version) achieved an AUC of 94.09% on CoraML and 92.76% on CiteSeer, consistently outperforming standard GAE and the previous state-of-the-art, Gravity GAE.
Efficiency and Clustering
Beyond accuracy, DiGAE-1L demonstrated a 5x to 15x speedup over baseline models. For CiteSeer, DiGAE-1L trained in approximately 4 seconds, compared to over 100 seconds for Gravity GAE. Furthermore, t-SNE visualizations revealed that DiGAE’s latent space creates significantly crisper separations between document classes compared to raw features.
Latent Hubs and Authorities
The magnitudes of the learned source and target vectors correlate strongly with classical graph metrics like Hub and Authority scores. A node with a large source vector magnitude is likely a "hub," while a large target vector magnitude indicates an "authority."
Conclusion
DiGAE demonstrates that local neighborhood information, when handled with the correct directional inductive bias, is incredibly potent for graph learning. While the current model uses global parameters for degree scaling, future work may explore local scaling decisions to better handle complex, heterogeneous graph regions. Additionally, extending this performance to node classification remains an open area for further exploration.
Summary updated