NetGAN without GAN: From Random Walks to Low-Rank Approximations

A graph generative model takes a graph as input and is supposed to generate new graphs that "look like" the input graph. While most classical models focus on few, hand-selected graph statistics and are too simplistic to reproduce real-world graphs, NetGAN recently emerged as an attractive alternative: by training a GAN to learn the random walk distribution of the input graph, the algorithm is able to reproduce a large number of important network patterns simultaneously, without explicitly specifying any of them. In this paper, we investigate the implicit bias of NetGAN. We find that the root of its generalization properties does not lie in the GAN architecture, but in an inconspicuous low-rank approximation of the logits random walk transition matrix. Step by step we can strip NetGAN of all unnecessary parts, including the GAN, and obtain a highly simplified reformulation that achieves comparable generalization results, but is orders of magnitudes faster and easier to adapt. Being much simpler on the conceptual side, we reveal the implicit inductive bias of the algorithm -an important step towards increasing the interpretability, transparency and acceptance of machine learning systems. NetGAN without GAN Input graph NetGAN: CELL: Sample random walks from graph Train GAN with LSTM Sample random walks from generator Count transitions in score matrix Solve optimization problem with rank constraint Solve eigenvector problem for score matrix Convert score matrix into edgeindependent model Sample output graph