Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs

Hyokun Yun, S. V. N. Vishwanathan

Introduction

Simulating realistic social and information networks requires models that capture complex structural properties like power-law degree distributions and local clustering. While the Stochastic Kronecker Product Graph Model (KPGM) offers high efficiency, it often lacks the expressiveness needed for nuanced structural details. The Multiplicative Attribute Graph Model (MAGM) addresses this by assigning latent attributes to nodes, but its traditional sampling methods are computationally prohibitive, scaling quadratically ($O(n^2)$) with the number of nodes.

The Quilting Algorithm

To overcome the scalability bottleneck of MAGM, researchers developed the Quilting Algorithm. This approach bridges the gap between the efficiency of KPGM and the expressiveness of MAGM by observing that MAGM probability matrices can be decomposed into structures similar to KPGM.

Partitioning and Permutation

The core of the algorithm involves partitioning the node set into blocks where no two nodes share the same attribute configuration. This allows the complex MAGM probability matrix $Q$ to be viewed as a collection of sub-matrices.

The decomposition of the MAGM probability matrix Q into smaller sub-matrices.

Once partitioned, each "piece" of the MAGM matrix can be transformed via permutation into a sub-matrix that mimics a KPGM structure. This transformation is crucial because it enables the use of highly efficient recursive quadrisection sampling algorithms originally designed for KPGM.

Permuting a sub-matrix to match the structure required for efficient KPGM-style sampling.

By "quilting" these sampled sub-graphs back together, the algorithm achieves an expected time complexity of $O((\log_2(n))^3 |E|)$, where $|E|$ is the number of edges. This represents a massive improvement over the previous $O(n^2)$ bottleneck.

Results and Scalability

The Quilting Algorithm demonstrates unprecedented scalability. In empirical tests, the researchers generated a synthetic graph with 8.3 million nodes and 20 billion edges in under six hours—a task previously impossible for the MAGM model.

Key findings include:

  • Linear Scaling: The running time per edge remains nearly constant as the number of nodes increases, confirming that the algorithm scales linearly with the number of edges.
  • Statistical Fidelity: The generated graphs maintain the expected statistical properties of MAGM, such as power-law distributions and the growth of the largest strong component, ensuring that speed does not come at the expense of accuracy.

Conclusion

The Quilting Algorithm provides the first sub-quadratic sampling method for Multiplicative Attribute Graphs. By leveraging the mathematical relationship between MAGM and KPGM, it enables the generation of realistic, large-scale networks that were previously beyond reach. Future work may explore high-dimensional similarity search techniques like Locality Sensitive Hashing (LSH) to further optimize performance for graphs with a very high number of attributes.

Summary updated

Abstract

We describe the first sub-quadratic sampling algorithm for the 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 \emph{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.
BibTeX
@inproceedings{yun2012quilting,
  author = {Hyokun Yun and S. V. N. Vishwanathan},
  title = {{Quilting Stochastic Kronecker Product Graphs to Generate Multiplicative Attribute Graphs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2012},
  url = {https://openreview.net/forum?id=gxo0PsR4SN},
}
Figure