Graph to Graph: a Topology Aware Approach for Graph Structures Learning and Generation

Mingming Sun, Ping LiAISTATS 2019 · OpenReview

Abstract

Mapping one graph structure to another is a fundamental yet challenging task in machine learning. While sequence-to-sequence and graph-to-sequence models have matured, general graph-to-graph mapping remains difficult due to the need for deep "topology awareness." This paper introduces a novel framework that converts general graphs into Directed Acyclic Graphs (DAGs) and utilizes a "Topology-Flow" encoder. By employing orthogonal projections to explicitly memorize connections, the proposed model achieves near-perfect accuracy in graph reconstruction tasks where standard Graph Neural Networks (GNNs) fail.

Introduction: The Challenge of Topology Awareness

In machine learning, mapping sequences to sequences (e.g., machine translation) is a well-studied domain. However, mapping a general graph to another graph presents unique challenges. To succeed, a model must effectively capture the global arrangement of nodes and edges from a source graph and reconstruct it in a target structure.

Existing graph encoders, such as Graph Convolutional Networks (GCNs), are primarily optimized for node-level or link-level tasks. While they excel at local neighborhood aggregation, they often struggle to capture the long-term topological dependencies required to reconstruct an entire graph from scratch. This paper addresses this gap by focusing on how to effectively learn and generate graph topologies.

Methodology

The authors propose a three-step pipeline to facilitate graph-to-graph mapping:

1. DAG Formulation

To process graphs using recurrent architectures, arbitrary graphs are first converted into Directed Acyclic Graphs (DAGs). This is achieved through a Breadth-First Search (BFS) traversal, which imposes a partial ordering on nodes without losing structural information.

The process of converting a general graph (a) into a DAG (b) and adding an end node (c) for sequence processing.

2. Topology-Flow Encoder

The core innovation is the Topology-Flow encoder. Unlike standard encoders that focus solely on existing connections, this encoder introduces a "topology constraint." It mathematically forces the state of a node to be orthogonal to the states of nodes that are not its parents. By operating in the orthogonal complement space of non-connected nodes, the model is forced to explicitly memorize the specific topology.

3. Conditioned Decoders

Two generation strategies are proposed:

  • Edge-Bernoulli: Generates edges based on the individual state of the current node.
  • Edge-Connect: A more robust approach that determines edge existence by evaluating the relationship between pairs of nodes (the new node and potential neighbors).

Experiments and Results

The model was evaluated on two primary tasks: a graph copy "stress test" and a complex skeleton mapping task.

Graph Copy Task

Using a dataset of all possible 10-node topologies (over 11 million samples), the authors tested the model's ability to perfectly replicate a source graph. Standard baselines like GCN and Gated Graph Neural Networks (GGNN) performed poorly, achieving less than 1% graph-level accuracy. In contrast, the Topology-Flow encoder combined with the Edge-Connect decoder achieved a staggering 98.3% graph-level accuracy.

MNIST Skeleton Mapping

The model was also tasked with mapping the skeleton of one MNIST digit to another (e.g., transforming a '1' into a '2'). This required the model to discover and generate new, valid topologies.

Examples of skeleton graphs derived from MNIST digits, representing complex topological structures.

The Topology-Flow encoder outperformed other methods here as well, reaching approximately 82.3% accuracy in generating the correct target digit class skeleton.

Conclusion and Future Work

The "Graph-to-Graph" framework demonstrates that explicit topological constraints through orthogonal projections can significantly enhance a model's structural memory. While highly effective on small-to-medium graphs, future work will focus on scaling these computations to larger graphs and developing more robust, permutation-invariant DAG formulations. Potential real-world applications include Open Information Extraction and knowledge graph generation.

Summary updated

Abstract

This paper is concerned with the problem of learning the mapping from one graph to another graph. Primarily, we focus on the issue of how to effectively learn the topology of the source graph and t...
BibTeX
@inproceedings{sun2019graph,
  author = {Mingming Sun and Ping Li},
  title = {{Graph to Graph: a Topology Aware Approach for Graph Structures Learning and Generation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=f1g1mtXSh6},
}
Figure