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

For more information about Stanford’s Artificial Intelligence professional and graduate programs, visit: https://stanford.io/3Eu3ZMV

Lecture 15.3: Scaling Up and Evaluating Graph Generation

Jure Leskovec
Computer Science, PhD

A key question when designing deep generative models for graphs is algorithm scalability. 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, a BFS ordering greatly reduces the steps for edge generation, since it limits the number of considered previous nodes to 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 between 2 graph statistic distributions; then, we will use Maximum Mean Discrepancy (MMD) to compute the similarity between 2 sets of graph statistics. More information can be found in the paper: “GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models” https://arxiv.org/abs/1802.08773

To follow along with the course schedule and syllabus, visit:
http://web.stanford.edu/class/cs224w/

Видео CS224W: Machine Learning with Graphs | 2021 | Lecture 15.3 - Scaling Up & Evaluating Graph Gen канала Stanford Online