Deep Generative Models for Subgraph Prediction

Erfaneh Mahmoudzadeh, Parmis Naddaf, Kiarash Zahirnia, Oliver Schulte

Introduction

Traditional graph machine learning tasks typically focus on "single-shot" predictions, such as determining if a link exists between two nodes (link prediction) or assigning a category to a single node (node classification). However, real-world scenarios often involve complex, interdependent queries. For instance, in a movie database, knowing a director and a lead actor might lead one to predict not just other cast members, but also the film's genre simultaneously.

Figure 1: An example of a subgraph query in a movie database where links and attributes are jointly predicted.

Predicting these elements independently ignores the inherent correlations between graph structure and node attributes. Furthermore, many existing models struggle with inductive scenarios—making predictions about nodes that were not present during training. This paper introduces the task of subgraph prediction, where a model jointly predicts an entire set of links and node attributes based on an "evidence subgraph."

Methodology: The VGAE+ Framework

The authors propose VGAE+, an augmented Variational Graph Auto-Encoder designed to capture the joint distribution of links and labels.

Architecture

The model utilizes a Graph Isomorphism Network (GIN) as an encoder to map nodes into a latent space. Unlike standard VGAEs, VGAE+ incorporates three specialized decoders to handle the multi-faceted nature of subgraphs:

  1. Link Decoder: Reconstructs the graph structure using a Stochastic Block Model.
  2. Feature Decoder: Predicts continuous node features.
  3. Label Decoder: Predicts categorical node labels.
Figure 6: The VGAE+ architecture featuring a GIN encoder and three distinct decoders for links, features, and labels.

Training and Inference

To balance these three objectives, the authors employ a modified Evidence Lower Bound (ELBO) with hyperparameters weighting the importance of links, features, and labels. These weights are optimized per dataset using Bayesian optimization to ensure the model doesn't over-prioritize one task at the expense of others.

For inference, the model performs zero-shot inductive learning. Given an evidence subgraph, it encodes the nodes and uses the decoders to estimate probabilities. The authors found that a Monte Carlo (MC) approach—sampling multiple times from the latent distribution—consistently outperformed a simple deterministic mean-based approach by better accounting for structural uncertainty.

Experimental Evaluation

The model was evaluated on six benchmark datasets across three domains: Citation Networks (Cora, ACM, CiteSeer), Movie Data (IMDb), and Co-purchase Networks (Amazon Photo, Amazon Computers).

Key Results

VGAE+ (specifically the MC variant) demonstrated significant improvements over state-of-the-art independent baselines like GraphSage, GAT, and SEAL. In subgraph prediction tasks, the model achieved Area Under the Curve (AUC) gains ranging from 0.06 to 0.2 points.

The performance on the IMDb dataset was particularly noteworthy, with a 0.16 AUC improvement. This highlights the model's ability to leverage strong correlations between movie genres and casting patterns. Additionally, the model showed robust performance in fully inductive settings, successfully generalizing to unseen nodes without retraining.

Discussion and Future Work

The core insight of this work is that joint prediction of structure and attributes is superior to independent modeling. By capturing the joint distribution, VGAE+ understands how specific labels imply certain connectivity patterns.

However, some limitations remain. The current framework is restricted to homogeneous graphs, whereas many real-world knowledge graphs are heterogeneous. Furthermore, the superior Monte Carlo inference method comes with a higher computational cost compared to deterministic methods. Future research may explore more expressive generative architectures, such as Graph Diffusion or auto-regressive models, to capture even more intricate structural dependencies.

Summary updated

Abstract

Graph Neural Networks (GNNs) are important across different domains, such as social network analysis and recommendation systems, due to their ability to model complex relational data. This paper introduces subgraph queries as a new task for deep graph learning. Unlike traditional graph prediction tasks that focus on individual components like link prediction or node classification, subgraph queries jointly predict the components of a target subgraph based on evidence that is represented by an observed subgraph. For instance, a subgraph query can predict a set of target links and/or node labels. To answer subgraph queries, we utilize a probabilistic deep Graph Generative Model. Specifically, we inductively train a Variational Graph Auto-Encoder (VGAE) model, augmented to represent a joint distribution over links, node features and labels. Bayesian optimization is used to tune a weighting for the relative importance of links, node features and labels in a specific domain. We describe a deterministic and a sampling-based inference method for estimating subgraph probabilities from the VGAE generative graph distribution, without retraining, in zero-shot fashion. For evaluation, we apply the inference methods on a range of subgraph queries on six benchmark datasets. We find that inference from a model achieves superior predictive performance, surpassing independent prediction baselines with improvements in AUC scores ranging from 0.06 to 0.2 points, depending on the dataset.
BibTeX
@inproceedings{mahmoudzadeh2024deep,
  author = {Erfaneh Mahmoudzadeh and Parmis Naddaf and Kiarash Zahirnia and Oliver Schulte},
  title = {{Deep Generative Models for Subgraph Prediction}},
  booktitle = {ECAI},
  year = {2024},
  url = {https://openreview.net/forum?id=GR2WMhQdHi},
}
Figure