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.
Introduction
In network science, generating synthetic graphs that accurately reflect real-world properties—such as power-law degree distributions and local clustering—is crucial for testing algorithms at scale. The Multiplicative Attribute Graph Model (MAGM) is a powerful framework for this, assigning latent binary attributes to nodes to determine edge probabilities. However, MAGMs have historically suffered from a significant computational bottleneck: the "naive" sampling approach requires $O(n^2)$ time, making it impractical for networks with millions of nodes.
This paper introduces a breakthrough sub-quadratic sampling algorithm. By leveraging the mathematical relationship between MAGMs and the simpler, faster Kronecker Product Graph Model (KPGM), the authors propose a "quilting" technique that reduces complexity to $O(\log^3(n) |E|)$.
Methodology: Bridging MAGM and KPGM
The core innovation lies in viewing the MAGM probability matrix as a collection of structured blocks. While a KPGM matrix has a rigid recursive structure, an MAGM matrix is more complex because node attributes can be arbitrary.
The authors demonstrate that by partitioning nodes into sets ($D_c$) where attribute configurations are unique, any specific block of the MAGM probability matrix can be transformed into a KPGM-like matrix through permutation.
The Quilting Algorithm
The proposed algorithm follows four main steps:
- Partitioning: Nodes are grouped into sets based on their attribute configurations.
- Permutation: The probability matrix for each pair of node sets is recognized as a permuted KPGM matrix.
- Sampling: Highly efficient KPGM sampling techniques are used to generate edges within these permuted blocks.
- Quilting: The resulting sub-graphs are "un-permuted" and stitched together to form the final MAGM graph.
Empirical Evaluation and Results
The authors evaluated the algorithm's performance using synthetic scalability tests. The results demonstrate a dramatic improvement over the state-of-the-art:
- Massive Scale: The algorithm successfully generated a graph with 8 million nodes and 20 billion edges in under 6 hours.
- Speedup: For a network of 1 million nodes, the quilting algorithm finished in approximately 20 minutes, whereas the naive $O(n^2)$ approach would take days.
- Structural Fidelity: Verification tests confirmed that the quilting process preserves the intended structural properties of the MAGM, such as degree distributions and component sizes.
Insights and Future Directions
The efficiency of this approach is most pronounced when attributes are "balanced" (attribute probability $\mu \approx 0.5$), which keeps the number of required "quilts" manageable. Because the runtime scales with the number of edges ($|E|$), the algorithm is perfectly suited for the sparse graphs typical of real-world social and technological networks.
Future work may address cases with highly "unbalanced" attributes or extremely high-dimensional attribute vectors, where partitioning becomes less efficient. The authors suggest that Locality Sensitive Hashing (LSH) could potentially provide further speedups in these high-dimensional regimes.
Summary updated