Directed Graph Auto-Encoders

Georgios Kollias, Vasileios Kalantzis, Tsuyoshi Idé, Aurélie C. Lozano, Naoki Abe

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:

  1. Source Vector ($s_i$): Encodes the node's behavior when it initiates a link.
  2. 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.

The dual-role representation and its relation to the directed Weisfeiler-Leman algorithm via bipartite mapping.

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.

t-SNE visualizations of the latent space, demonstrating clear separation between document classes.

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

Abstract

We introduce a new class of auto-encoders for directed graphs, motivated by a direct extension of the Weisfeiler-Leman algorithm to pairs of node labels. The proposed model learns pairs of interpretable latent representations for the nodes of directed graphs, and uses parameterized graph convolutional network (GCN) layers for its encoder and an asymmetric inner product decoder. Parameters in the encoder control the weighting of representations exchanged between neighboring nodes. We demonstrate the ability of the proposed model to learn meaningful latent embeddings and achieve superior performance on the directed link prediction task on several popular network datasets.
BibTeX
@inproceedings{kollias2022directed,
  author = {Georgios Kollias and Vasileios Kalantzis and Tsuyoshi Idé and Aurélie C. Lozano and Naoki Abe},
  title = {{Directed Graph Auto-Encoders}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=KXvx8Mk5Al},
}
Figure