CMU-Led Team Wins "Test of Time" Award at ECML/PKDD 2015
"Realistic, Mathematically Tractable Graph Generation and Evolution, Using Kronecker Multiplication," Jure Leskovec, Deepayan Chakrabarti, Jon M. Kleinberg, Christos Faloutsos
ECML/PKDD is one of the top data mining conferences. Both Jure Leskovec and Deepayan Chakrabarti were ML PhD students in 2005, advised by Christos Faloutsos, while Jon Kleinberg was on sabbatical at CMU. Both Jure and Deepayan are now tenure-track faculty, at Stanford and UT Austin, respectively. The paper showed how to generate realistic graphs, using recursion and self-similarity. Not only the resulting graphs obey several "power laws" that real graphs obey, but they also have a very simple, recursive mechanism, the so-called Kronecker matrix multiplication, that has been studied extensively, and leads to simple and elegant proofs about the graph properties. Its simpler version, "RMAT" is the basis behind the graph500 benchmark http://www.graph500.org/ which is used to generate benchmarks for supercomputer competitions on graph analytics.