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 = {Hyokun Yun and S V N Vishwanathan}, booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics}, pages = {1389--1397}, year = {2012}, editor = {Neil D. Lawrence and Mark Girolami}, 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 = {http://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 %J Proceedings of Machine Learning Research %P 1389--1397 %U http://proceedings.mlr.press %V 22 %W PMLR %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 PY - 2012/03/21 DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-yun12 PB - PMLR SP - 1389 DP - PMLR EP - 1397 L1 - http://proceedings.mlr.press/v22/yun12/yun12.pdf UR - http://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 PMLR 22:1389-1397

Related Material