Interpretable Deep Graph Generation with Node-Edge Co-Disentanglement

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

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. Moreover, within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images. Qualitative and quantitative experiments on both synthetic and real-world datasets demonstrate the effectiveness of the proposed model and its extensions.

Introduction: The Challenge of Graph Disentanglement

In generative modeling, "disentanglement" refers to the ability to separate independent features within a latent space. In image generation, this allows for the independent control of attributes like a subject's pose or hair color. However, extending this concept to attributed graphs—where both nodes (e.g., users) and edges (e.g., relationships) possess distinct features—presents unique difficulties.

Existing graph generative models often struggle with three primary hurdles. First, there is a lack of standard "graph deconvolution" operations capable of simultaneously generating node and edge attributes while maintaining their independence. Second, factors in a graph are inherently entangled: some influence only nodes, some only edges, and others affect joint patterns. Finally, there is often a trade-off between the interpretability of a model and the quality of its reconstructions.

The NED-VAE Framework

To address these issues, the authors introduced NED-VAE (Node-Edge Disentangled Variational Auto-encoder). This framework is designed to independently control node attributes, edge attributes, and their joint patterns.

Architecture and Co-deconvolution

NED-VAE utilizes a modular architecture consisting of three sub-encoders: one for node features, one for edge features, and a "co-encoder" for joint graph-level patterns. On the decoding side, the model employs a novel "co-deconvolution" strategy. By replicating node features and concatenating them with edge features during the decoding process, the model synchronizes the generation of the graph's structure with its associated data.

Figure 3: Illustration of node-related, edge-related, and node-edge-joint factors in an attributed graph.

Hierarchical Disentanglement

The core innovation lies in a specialized mathematical objective that performs hierarchical decomposition of the Variational Lower Bound (ELBO). This objective penalizes entanglement at two levels:

  1. Group-wise Disentanglement: Ensuring that variables governing nodes do not leak into those governing edges.
  2. Variable-wise Disentanglement: Ensuring that individual variables within a group (e.g., the node group) control distinct, independent properties.

Experimental Evaluation

The model was evaluated using both synthetic and real-world datasets, including Erdos-Renyi (ER) graphs, Watts-Strogatz (WS) "small-world" graphs, and a protein structure dataset consisting of 8-node peptides.

Quantitative and Qualitative Results

NED-VAE demonstrated superior performance in isolating latent factors. On the ER dataset, a variant of the model (NED-IPVAE-II) achieved a 99.9% score in the $\beta-M$ disentanglement metric, significantly outperforming the standard GraphVAE's 79.2%.

Qualitatively, the model allows for precise, interpretable control over graph generation. As shown in the figure below, a single latent variable can be adjusted to smoothly transition the density of a graph's edges while the node attributes remain perfectly constant.

Figure 2: Smooth transition of a single disentangled edge factor while keeping other factors constant.

Conclusion

NED-VAE represents a significant step forward in making deep graph generation interpretable. By explicitly modeling the hierarchical relationship between topology and attributes, the framework provides a generalized approach to graph disentanglement that outperforms existing benchmarks. Future work will focus on scaling the model to larger graphs and handling discrete structural changes within the disentangled framework.

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. Moreover, within each type, individual-factor-wise disentanglement is further enhanced, which is shown to be a generalization of the existing framework for images. 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},
}
Figure