Decouped Variational Graph Autoencoder for Link Prediction

Yoon-Sik ChoWWW 2024 · OpenReview

Abstract

Link prediction is a fundamental task in graph-structured data analysis, with applications ranging from social network recommendation to biological interaction discovery. While Graph Neural Network (GNN)-based approaches like the Variational Graph Autoencoder (VGAE) have significantly outperformed traditional methods, they often rely on an inner product decoder that suffers from intrinsic limitations. Specifically, the node norm and the angular similarity simultaneously attempt to explain link probability, leading to gradient interference and suboptimal representation learning. In this paper, we propose the Decoupled Variational Graph Autoencoder (D-VGAE), which explicitly separates these factors into two distinct components: homophily and node popularity. By utilizing a two-stage generative process and a hard expectation-maximization (EM) learning scheme, D-VGAE achieves state-of-the-art performance on link prediction across multiple real-world datasets while maintaining robustness in downstream tasks like node classification.

Introduction

The standard VGAE framework learns latent node representations and predicts links based on the similarity between these embeddings. Most implementations use the inner product ($z_i^\top z_j$) as the decoding mechanism. Mathematically, this product is the result of the magnitudes (norms) of the vectors and the cosine of the angle between them.

However, this coupling creates a competition. We find that the norm and the angle often try to explain the same link probability simultaneously, which hinders the gradient flow during training. Furthermore, in the message-passing phase of GNNs, nodes with large norm values (often high-degree "hubs") can dominate the features of their neighbors, drowning out local structural information. D-VGAE addresses these issues by decoupling the embedding space into homophily-driven and popularity-driven components.

The Problem: The Inner Product Bottleneck

The authors identify two major issues stemming from the standard inner product decoder:

  1. Gradient Interference: During training, if the model can minimize loss by simply increasing the norm of a high-degree node, it may ignore the directional (angular) information. This prevents the model from learning nuanced representations of node similarity.
  2. Message Passing Domination: In traditional GNNs, the features of nodes with very large norms can overwhelm the message-passing process. This leads to a bias where the representations of low-degree nodes are distorted by their high-degree neighbors.

Proposed Method: D-VGAE

D-VGAE introduces a generative framework that explicitly separates the two fundamental principles of graph formation: homophily (nodes connecting because they are similar) and node popularity (nodes connecting because one is a high-traffic hub).

Decoupled Embedding Spaces

Instead of a single vector, D-VGAE assigns each node two distinct embeddings:

  • Homophily Embedding ($z^h$): Learned using a Graph Normalized Convolutional Network (GNCN) to produce normalized embeddings that focus strictly on angular similarity.
  • Popularity Embedding ($z^p$): Learned as an intrinsic property of the node itself. Crucially, this component is learned without message passing, as popularity is considered an individual trait rather than a neighborhood-derived feature.

Two-Stage Generative Process and Hard EM

To predict a link, the model follows a two-stage logic: it first evaluates if a link exists due to homophily (cosine similarity). If not, it evaluates if a link exists due to node popularity.

Since the ground truth does not specify why a link was formed, the authors employ a Hard Expectation-Maximization (EM) strategy. This "winner-take-gradient" approach involves the model stochastically "guessing" which mechanism caused the link and updating only the parameters for that specific component. To manage this stochasticity, the model uses temperature annealing to transition from exploration to confident exploitation during training.

Experimental Evaluation

The model was evaluated on several benchmark datasets, including citation networks (Cora, CiteSeer, PubMed), co-authorship graphs (CS, Physics), and co-purchase graphs (Amazon Computers, Photo).

D-VGAE consistently outperformed existing state-of-the-art models. For instance, on the Cora dataset, D-VGAE achieved an AUC of 96.34%, surpassing the previous best VGAE variants. The performance gains were even more significant on larger, denser datasets like CS and Physics, demonstrating the model's scalability and robustness.

Qualitative Insights: Popularity vs. Degree

A qualitative analysis of an IMDb actor network revealed a fascinating distinction between simple node degree and the learned popularity ($z^p$). While the highest-degree nodes in the raw data were local actors with many niche connections, the model identified Pierce Brosnan as having the highest node popularity. This suggests that D-VGAE's popularity component captures "global appeal"—nodes that bridge different genres and clusters—rather than just raw connectivity.

Conclusion

By decoupling the competing factors of norm and angle, D-VGAE resolves the intrinsic limitations of the inner product decoder in graph autoencoders. This separation not only improves link prediction accuracy but also ensures "message passing hygiene," preventing hub nodes from dominating the representation space. Future work may extend this decoupling principle to directed and heterogeneous graphs, or explore its potential in reducing degree-related bias in GNN fairness.

Summary updated

Abstract

Link prediction is an important learning task for graph-structured data, and has become increasingly popular due to its wide application areas. Graph Neural Network (GNN)-based approaches including Variational Graph Autoencoder (VGAE) have achieved promising performance on link prediction outperforming conventional models which use hand-crafted features. VGAE learns latent node representations and predicts links based on the similarities between nodes. While the inner product based decoder effectively utilizes the node representations for link prediction, it exhibits sub-optimal performance due to the intrinsic limitation of the inner product. We found that the the cosine similarity and norm simultaneously try to explain the link probability, which hinders the gradient flow during training. We also point out the message passing scheme is unexpectedly dominated by the nodes with large norm values. In this paper, we propose a stochastic VGAE-based method that can effectively decouple the norm and angle in the embeddings. Specifically, we relate the cosine similarity and norm to two fundamental principles in graph: homophily and node popularity respectively. Following the principles in graph, we define a generative process in the VGAE framework. Our learning scheme is based on a hard expectation maximization learning method; we infer which of the two has been exerted for link formation, and subsequently optimize based on this guess. We comprehensively evaluate our proposed method on link prediction task. Through extensive experiments on real-world datasets, we demonstrate our model outperforms the existing state-of-the-art methods on link prediction and achieves comparable performances on other downstream tasks such as node classification and clustering. Our code is at https://anonymous.4open.science/r/dvgae-A0B4.
BibTeX
@inproceedings{cho2024decouped,
  author = {Yoon-Sik Cho},
  title = {{Decouped Variational Graph Autoencoder for Link Prediction}},
  booktitle = {WWW},
  year = {2024},
  url = {https://openreview.net/forum?id=qoKHBoLzwX},
}
Figure