Directed Graph Auto-Encoders

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

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).

The DiGAE architecture represents nodes as split source/target entities, facilitating directed message passing.

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.

Performance comparison of DiGAE against baselines on CoraML and CiteSeer datasets.

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

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