Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs

Hyokun Yun, S V N Vishwanathan
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1389-1397, 2012.

Abstract

We describe the first sub-quadratic sampling algorithm for Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample small number of KPGM graphs and quilt them together. Under a restricted set of technical conditions, our algorithm runs in $O((\log_2(n))^3 |E|)$ time, where n is the number of nodes and |E| is the number of edges in the sampled graph. We demonstrate the scalability of our algorithm via extensive empirical evaluation; we can sample a MAGM graph with 8 million nodes and 20 billion edges in under 6 hours.

Cite this Paper

BibTeX
@InProceedings{pmlr-v22-yun12, title = {Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs}, author = {Yun, Hyokun and Vishwanathan, S V N}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1389--1397}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/yun12/yun12.pdf}, url = {https://proceedings.mlr.press/v22/yun12.html}, abstract = {We describe the first sub-quadratic sampling algorithm for Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample small number of KPGM graphs and quilt them together. Under a restricted set of technical conditions, our algorithm runs in $O((\log_2(n))^3 |E|)$ time, where n is the number of nodes and |E| is the number of edges in the sampled graph. We demonstrate the scalability of our algorithm via extensive empirical evaluation; we can sample a MAGM graph with 8 million nodes and 20 billion edges in under 6 hours.} }
Endnote
%0 Conference Paper %T Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs %A Hyokun Yun %A S V N Vishwanathan %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-yun12 %I PMLR %P 1389--1397 %U https://proceedings.mlr.press/v22/yun12.html %V 22 %X We describe the first sub-quadratic sampling algorithm for Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample small number of KPGM graphs and quilt them together. Under a restricted set of technical conditions, our algorithm runs in $O((\log_2(n))^3 |E|)$ time, where n is the number of nodes and |E| is the number of edges in the sampled graph. We demonstrate the scalability of our algorithm via extensive empirical evaluation; we can sample a MAGM graph with 8 million nodes and 20 billion edges in under 6 hours.
RIS
TY - CPAPER TI - Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs AU - Hyokun Yun AU - S V N Vishwanathan BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-yun12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 1389 EP - 1397 L1 - http://proceedings.mlr.press/v22/yun12/yun12.pdf UR - https://proceedings.mlr.press/v22/yun12.html AB - We describe the first sub-quadratic sampling algorithm for Multiplicative Attribute Graph Model (MAGM) of Kim and Leskovec (2010). We exploit the close connection between MAGM and the Kronecker Product Graph Model (KPGM) of Leskovec et al. (2010), and show that to sample a graph from a MAGM it suffices to sample small number of KPGM graphs and quilt them together. Under a restricted set of technical conditions, our algorithm runs in $O((\log_2(n))^3 |E|)$ time, where n is the number of nodes and |E| is the number of edges in the sampled graph. We demonstrate the scalability of our algorithm via extensive empirical evaluation; we can sample a MAGM graph with 8 million nodes and 20 billion edges in under 6 hours. ER -
APA
Yun, H. & Vishwanathan, S.V.N.. (2012). Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:1389-1397 Available from https://proceedings.mlr.press/v22/yun12.html.

Related Material