Interpretable Deep Graph Generation with Node-edge Co-disentanglement

Xiaojie Guo, Liang Zhao, Zhao Qin, Lingfei Wu, Amarda Shehu, Yanfang Ye

This paper, presented at KDD '20, introduces a novel framework for making deep graph generation more "human-readable" by separating the underlying factors that govern how graphs are built.

TL;DR

The authors propose NED-VAE (Node-Edge Disentangled Variational Auto-encoder), the first generative model designed to independently control node attributes, edge attributes, and their joint patterns in attributed graphs. By "disentangling" these latent factors, the model allows for interpretable and controllable graph generation, outperforming existing benchmarks in both reconstruction quality and factor isolation.

What Problem Does This Paper Address?

In the world of image generation (like StyleGAN), "disentanglement" is a well-known concept. It’s the ability to separate independent features—for example, changing a person's "smile" without altering their "hair color."

However, doing this for attributed graphs (graphs where both nodes and edges have their own data, like a social network with user profiles and relationship types) is significantly harder. The authors identify three main hurdles:

  1. Decoding Complexity: There isn't a standard "graph deconvolution" that can easily generate nodes and edges simultaneously while keeping their features distinct.
  2. Factor Entanglement: In a graph, some factors might only affect nodes (e.g., a computer's CPU usage), some only edges (e.g., physical distance between servers), and some affect both (e.g., network traffic volume). Existing models mush these together.
  3. The Quality Trade-off: Usually, forcing a model to be "interpretable" (disentangled) makes the actual generated data less accurate.

Methods

The authors introduce the NED-VAE architecture and a specialized mathematical objective to solve these issues.

The Architecture

Instead of one giant encoder/decoder pair, NED-VAE uses a modular approach:

  • Three Sub-encoders: One for node features, one for edge features, and a "co-encoder" for joint graph-level patterns.
  • Two Sub-decoders: A node decoder and an edge decoder that work together (co-deconvolution) to reconstruct the graph from the separated latent factors.

The Objective Function

The core innovation is a hierarchical decomposition of the Variational Lower Bound (ELBO). They break the training loss into specific terms that penalize "entanglement" at two levels:

  • Group-wise Disentanglement: Ensuring the "node group" of variables doesn't leak into the "edge group."
  • Variable-wise Disentanglement: Ensuring that within the "node group," individual variables control distinct properties (e.g., one for color, one for size).

They also provide several extensions (like NED-TCVAE and NED-AnchorVAE) that allow researchers to prioritize different types of disentanglement depending on the use case.

Datasets

The model was evaluated on three distinct types of data:

  1. Erdos-Renyi (ER) Graphs (Synthetic): Graphs generated with specific rules for edge probability and node attributes to see if the model could "rediscover" those rules.
  2. Watts Strogatz (WS) Graphs (Synthetic): "Small-world" graphs where factors control ring topology and rewiring probability.
  3. Protein Structure Dataset (Real-world): 8-node peptides where the factors are physical properties like simulation time and ionic concentration.

Key Insights and Ideas

  • Hierarchical Control: The biggest "aha" moment is that graph disentanglement must be hierarchical. You can't just treat all latent variables the same; you must explicitly model the relationship between topology (edges) and attributes (nodes).
  • Generalization of Image Models: The authors prove that their framework is a mathematical generalization of famous image models like $\beta$-VAE. If you strip away the edge components, NED-VAE essentially becomes a state-of-the-art image disentanglement model.
  • Co-deconvolution: By replicating node features and concatenating them with edge features during decoding, they created a way to "synchronize" the generation of the graph's structure with its data.

Key Results

The researchers used four quantitative metrics ($\beta-M$, $F-M$, DCI, and Modularity) to measure how well the factors were separated.

  • Superior Isolation: On the ER dataset, NED-IPVAE-II achieved a 99.9% score in the $\beta-M$ metric, compared to only 79.2% for the standard GraphVAE.
  • Interpretability: Qualitatively, the authors showed they could "dial" a single latent variable to smoothly change the density of a graph's edges while the node colors remained perfectly constant—something previous models failed to do.
  • Efficiency: Despite the complex architecture, the model maintains $O(N^2)$ time complexity, making it significantly faster than some previous $O(N^4)$ graph generation methods.

Limitations and Future Work

  • Graph Size: While the model is efficient, the experiments focused on relatively small graphs (e.g., 8 nodes for the protein dataset). Scaling this to massive graphs with thousands of nodes remains a challenge.
  • Discrete vs. Continuous: The current framework is optimized for continuous latent factors. Handling purely discrete structural changes in a disentangled way is a suggested path for future research.
  • Complex Topology: While the model handles attributed graphs well, extremely complex or hierarchical topologies (graphs within graphs) might require even more specialized encoders.

Summary updated

Abstract

Disentangled representation learning has recently attracted a significant amount of attention, particularly in the field of image representation learning. However, learning the disentangled representations behind a graph remains largely unexplored, especially for the attributed graph with both node and edge features. Disentanglement learning for graph generation has substantial new challenges including 1) the lack of graph deconvolution operations to jointly decode node and edge attributes; and 2) the difficulty in enforcing the disentanglement among latent factors that respectively influence: i) only nodes, ii) only edges, and iii) joint patterns between them. To address these challenges, we propose a new disentanglement enhancement framework for deep generative models for attributed graphs. In particular, a novel variational objective is proposed to disentangle the above three types of latent factors, with novel architecture for node and edge deconvolutions. Qualitative and quantitative experiments on both synthetic and real-world datasets demonstrate the effectiveness of the proposed model and its extensions.
BibTeX
@inproceedings{guo2020interpretable,
  author = {Xiaojie Guo and Liang Zhao and Zhao Qin and Lingfei Wu and Amarda Shehu and Yanfang Ye},
  title = {{Interpretable Deep Graph Generation with Node-edge Co-disentanglement}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2020},
  url = {https://openreview.net/forum?id=dyDCPvEPC25},
}

Loading related content...

Figure