On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices

Geoffrey Sanders, Roger Pearce, Timothy La Fond, Jeremy Kepner

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.

Relationship between triangle statistics in factor graphs A and B and the resulting Kronecker product graph C.

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.

Visualizing how edge types from factor graphs combine to form the structure of the Kronecker product graph.

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

BibTeX
@inproceedings{sanders2018large,
  author = {Geoffrey Sanders and Roger Pearce and Timothy La Fond and Jeremy Kepner},
  title = {{On Large-Scale Graph Generation with Validation of Diverse Triangle Statistics at Edges and Vertices}},
  booktitle = {Workshops @ IPDPS},
  year = {2018},
  doi = {10.1109/ipdpsw.2018.00056},
}
Figure