Abstract: Deep generative models, since their inception, have become increasingly more
capable of generating novel and perceptually realistic signals (e.g., images
and sound waves). With the emergence of deep models for graph structured data,
natural interests seek extensions of these generative models for graphs.
Successful extensions were seen recently in the case of learning from a
collection of graphs (e.g., protein data banks), but the learning from a single
graph has been largely under explored. The latter case, however, is important
in practice. For example, graphs in financial and healthcare systems contain so
much confidential information that their public accessibility is nearly
impossible, but open science in these fields can only advance when similar data
are available for benchmarking.
In this work, we propose an approach to generating a doppelganger graph that
resembles a given one in many graph properties but nonetheless can hardly be
used to reverse engineer the original one, in the sense of a near zero edge
overlap. The approach is an orchestration of graph representation learning,
generative adversarial networks, and graph realization algorithms. Through
comparison with several graph generative models (either parameterized by neural
networks or not), we demonstrate that our result barely reproduces the given
graph but closely matches its properties. We further show that downstream
tasks, such as node classification, on the generated graphs reach similar
performance to the use of the original ones.