Kronecker Graph Generation with Ground Truth for 4-Cycles and Dense Structure in Bipartite Graphs

We demonstrate nonstochastic Kronecker graph generators produce massive-scale bipartite graphs with ground truth global and local properties and discuss their use for validation of graph analytics. Given two small connected scale-free graphs with adjacency matrices A and B, their Kronecker product graph [1] has adjacency matrix C = A ⊗ B. We first demonstrate that having one factor A non-bipartite (alternatively, adding all self loops to a bipartite A) with other factor B bipartite ensures G
_C
is bipartite and connected. Formulas for ground truth of many graph properties (including degree, diameter, and eccentricity) carry over directly from the general case presented in previous work [2], [3]. However, the analysis of higher-order structure and dense structure is different in bipartite graphs, as no odd-length cycles exist (including triangles) and the densest possible structures are bicliques. We derive formulas to give ground truth for 4-cycles (a.k.a. squares or butterflies) at every vertex and edge in G
_C
. Additionally, we demonstrate that bipartite communities (dense vertex subsets) in the factors A, B yield dense bipartite communities in the Kronecker product C. We additionally discuss interesting properties of Kronecker product graphs revealed by the formulas an their impact on using them as benchmarks with ground truth for various complex analytics. For example, for connected A and B of nontrivial size, G
_C
has 4-cycles at vertices/edges associated with vertices/edges in A and B that have none, making it difficult to generate graphs with ground truth bipartite generalizations of truss decomposition (e.g. the k-wing decomposition of [4]).