Introduction
Graph analytic researchers face a significant "ground truth" dilemma when benchmarking new distributed algorithms. While massive graphs mimicking real-world characteristics (like "small-world" properties and power-law degree distributions) are necessary, calculating exact local statistics—such as triangle counts for specific vertices or edges—is computationally prohibitive, typically scaling at $O(|E|^{1.5})$. Existing stochastic generators like R-MAT provide only expected values, making 100% accuracy verification impossible on a trillion-edge scale.
This paper introduces a deterministic method for generating massive synthetic graphs using non-stochastic Kronecker products. These graphs come with "built-in" exact ground truth for complex triangle statistics, enabling validation with sublinear computational cost.
Methodology: The Kronecker Formula
The core approach utilizes non-stochastic Kronecker product graphs. Given two small adjacency matrices $A$ and $B$, a large graph $C$ is defined as $C = A \otimes B$. The authors derive algebraic formulas that link the properties of these small factor graphs to the resulting large-scale graph.
Key contributions include formulas for:
- Undirected Graphs: Triangle participation at vertices in $C$ is calculated as $t_C = 2t_A \otimes t_B$ (for loop-free graphs).
- Self-Loops: Formulas accounting for self-loops, which significantly "boost" triangle counts.
- Directed & Labeled Graphs: Extensions to 15 "flavors" of directed triangles and vertex-labeled categories.
- Truss Decomposition: Conditions under which the $k$-truss of $C$ can be derived directly from $A$ and $B$.
Key Insights and Structural Predictability
The Kronecker structure allows for a "square-root" reduction in computational cost. Instead of processing the massive graph $C$, researchers only need to process the much smaller factors $A$ and $B$. This makes trillion-edge graphs highly compressible and easy to reproduce across different research teams.
As shown in the figure above, the specific structure of edges in the product graph (e.g., cycle-cycle, hub-hub) is a direct result of the edge types in the factor graphs. This deterministic mapping ensures that local neighborhoods (egonets) can be sampled and compared against theoretical values derived from the Kronecker formulas.
Results and Scalability
The authors validated their formulas using the web-NotreDame graph. By generating product graphs ($A \otimes A$ and $A \otimes B$), they reached scales of over 100 billion vertices and 2.7 trillion edges.
Using the Kronecker formulas, triangle counts for a graph with 141 trillion triangles were computed in just 10.5 seconds on a standard commodity laptop. For a general graph of this magnitude, such a calculation would be impossible on modest hardware.
Limitations and Future Work
While powerful, non-stochastic Kronecker graphs have structural constraints. Their degree distributions are multinomial rather than perfect power laws. Additionally, the current truss decomposition formulas require specific assumptions about the factor graphs (e.g., edges in factor $B$ participating in no more than one triangle) that may need relaxation in future work. Future directions include extending this framework to other graph analytics, such as pattern matching for motifs beyond triangles.
Summary updated