Timezone: »

 
Oral
GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models
Jiaxuan You · Rex (Zhitao) Ying · Xiang Ren · Will Hamilton · Jure Leskovec

Wed Jul 11 08:40 AM -- 08:50 AM (PDT) @ A5
in Networks and Relational Learning 2 »

Modeling and generating graphs is fundamental for studying networks in biology, engineering, and social sciences. However, modeling complex distributions over graphs and then efficiently sampling from these distributions is challenging due to the non-unique, high-dimensional nature of graphs and the complex, non-local dependencies that exist between edges in a given graph.Here we propose GraphRNN, a deep autoregressive model that addresses the above challenges and approximates any distribution of graphs with minimal assumptions about their structure. GraphRNN learns to generate graphs by training on a representative set of graphs and decomposes the graph generation process into a sequence of node and edge formations, conditioned on the graph structure generated so far. In order to quantitatively evaluate the performance of GraphRNN, we introduce a benchmark suite of datasets, baselines and novel evaluation metrics based on Maximum Mean Discrepancy, which measure distances between sets of graphs.Our experiments show that GraphRNN significantly outperforms all baselines, learning to generate diverse graphs that match the structural characteristics of a target set, while also scaling to graphs 50 times larger than previous deep models.

[ PDF]  [ Video] 

Author Information

Jiaxuan You (Stanford University)
Rex (Zhitao) Ying (Stanford University)
Xiang Ren (University of Southern California)

Xiang Ren joined the Department of Computer Science at USC as Assistant Professor in 2018. Previously, he was a visiting researcher at Stanford University. Xiang received his PhD in Computer Science at University of Illinois at Urbana-Champaign (2017), where he was a Google PhD Fellow and a Richard T. Cheng Fellow working with Prof. Jiawei Han. Xiang's research develops data-driven and machine learning methods for turning unstructured text data into machine-actionable structures. Xiang's research has been recognized with several prestigious awards including a Yahoo!-DAIS Research Excellence Award, a Yelp Dataset Challenge award, a C. W. Gear Outstanding Graduate Student Award and a David J. Kuck Outstanding M.S. Thesis Award. Technologies he developed has been transferred to US Army Research Lab, National Institute of Health, Microsoft, Yelp and TripAdvisor.

Will Hamilton (Stanford University)
Jure Leskovec (Stanford University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors