CS224W: Machine Learning with Graphs | 2021 | Lecture 15.3 - Scaling Up & Evaluating Graph Gen

Lecture 15.3: Scaling Up and Evaluating Graph Generation Jure Leskovec Computer Science, PhD A key question for deep generative models for graphs is to scale the algorithm up. In principle, a newly added node could potentially connect with any prior node. GraphRNN solves this issue via enforcing a Bread-first-search (BFS) node ordering for any given graph. Through the BFS ordering, we can reduce the possible node orderings from O(n!) to the number of distinct BFS orderings; additionally, BFS ordering greatly reduce the steps for edge generation, since it limits the previous nodes to look at to be the nodes in the BFS frontier. Another core topic is how to properly evaluate a generative model for graphs. As an intuitive metric, one can visually examine the similarity of graphs. GraphRNN proposes a more rigorous approach, where we wish to compare the set of graph statistics between the synthetic graphs and the ground-truth graphs. Here, we will first use Earth Mover Distance (EMD) to compute similarity betwee