Kronecker powers and graphs

Kronecker powers

Repeated Kronecker multiplications of the same matrix, i.e.

\[A^{\otimes n}=\otimes_{i=1}^n A = \underbrace{A \otimes A \otimes \ldots \otimes A}_{n\text{ times}}\,.\]

Kronecker powers are supported using kronecker(A, n) or, equivalently, ⊗(A, n). These functions yield an instance of KroneckerPower, as struct which holds the matrix and the power. It works just like instances of KroneckerProduct, but more efficient since only a single matrix has to be stored and manipulated. These products work as expected.

julia> using Kronecker
julia> A = rand(2, 2)2×2 Array{Float64,2}:
 0.831585  0.0403041
 0.550888  0.360614
julia> K2 = A ⊗ 24×4 KroneckerPower{Float64,Array{Float64,2}}:
 0.691534  0.0335163  0.0335163  0.00162442
 0.45811   0.299881   0.0222031  0.0145342
 0.45811   0.0222031  0.299881   0.0145342
 0.303478  0.198658   0.198658   0.130042
julia> inv(K2)4×4 KroneckerPower{Float64,Array{Float64,2}}:
  1.68656  -0.188499  -0.188499   0.0210677
 -2.57646   3.88925    0.287959  -0.434684
 -2.57646   0.287959   3.88925   -0.434684
  3.9359   -5.94138   -5.94138    8.96872
julia> K12 = K2 ⊗ 6  # works recursively4096×4096 KroneckerPower{Float64,KroneckerPower{Float64,Array{Float64,2}}}:
 0.109365     0.00530057   0.00530057   …  3.79099e-16  1.83736e-17
 0.0724497    0.0474259    0.00351139      2.51136e-16  1.64395e-16
 0.0724497    0.00351139   0.0474259       3.39191e-15  1.64395e-16
 0.0479947    0.0314175    0.0314175       2.24699e-15  1.47089e-15
 0.0724497    0.00351139   0.00351139      3.39191e-15  1.64395e-16
 0.0479947    0.0314175    0.00232614   …  2.24699e-15  1.47089e-15
 0.0479947    0.00232614   0.0314175       3.03485e-14  1.47089e-15
 0.0317943    0.0208127    0.0208127       2.01045e-14  1.31605e-14
 0.0724497    0.00351139   0.00351139      3.39191e-15  1.64395e-16
 0.0479947    0.0314175    0.00232614      2.24699e-15  1.47089e-15
 ⋮                                      ⋱               ⋮
 0.00117924   0.000771937  0.000771937     8.25725e-7   5.40523e-7
 0.00268714   0.000130236  0.000130236     1.39311e-7   6.75195e-9
 0.00178011   0.00116527   8.62758e-5      9.22875e-8   6.04118e-8
 0.00178011   8.62758e-5   0.00116527   …  1.24646e-6   6.04118e-8
 0.00117924   0.000771937  0.000771937     8.25725e-7   5.40523e-7
 0.00178011   8.62758e-5   8.62758e-5      1.24646e-6   6.04118e-8
 0.00117924   0.000771937  5.71539e-5      8.25725e-7   5.40523e-7
 0.00117924   5.71539e-5   0.000771937     1.11525e-5   5.40523e-7
 0.000781195  0.000511374  0.000511374  …  7.38802e-6   4.83623e-6
julia> K12^2  # example4096×4096 KroneckerPower{Float64,KroneckerPower{Float64,Array{Float64,2}}}:
 0.0174766   0.00117657   0.00117657   …  2.25019e-15  1.51488e-16
 0.0160816   0.00372788   0.00108266      2.07058e-15  4.79982e-16
 0.0160816   0.00108266   0.00372788      7.12959e-15  4.79982e-16
 0.014798    0.00343033   0.00343033      6.56052e-15  1.52079e-15
 0.0160816   0.00108266   0.00108266      7.12959e-15  4.79982e-16
 0.014798    0.00343033   0.00099624   …  6.56052e-15  1.52079e-15
 0.014798    0.00099624   0.00343033      2.25897e-14  1.52079e-15
 0.0136169   0.00315653   0.00315653      2.07866e-14  4.81855e-15
 0.0160816   0.00108266   0.00108266      7.12959e-15  4.79982e-16
 0.014798    0.00343033   0.00099624      6.56052e-15  1.52079e-15
 ⋮                                     ⋱               ⋮
 0.00699954  0.00162256   0.00162256      2.1113e-10   4.8942e-11
 0.0082665   0.000556521  0.000556521     7.24153e-11  4.87518e-12
 0.00760668  0.0017633    0.000512101     6.66353e-11  1.54467e-11
 0.00760668  0.000512101  0.0017633    …  2.29444e-10  1.54467e-11
 0.00699954  0.00162256   0.00162256      2.1113e-10   4.8942e-11
 0.00760668  0.000512101  0.000512101     2.29444e-10  1.54467e-11
 0.00699954  0.00162256   0.000471226     2.1113e-10   4.8942e-11
 0.00699954  0.000471226  0.00162256      7.26978e-10  4.8942e-11
 0.00644085  0.00149305   0.00149305   …  6.68953e-10  1.5507e-10

Kronecker.kronecker — Method

kronecker(A::AbstractMatrix, pow::Int)

Kronecker power, computes A ⊗ A ⊗ ... ⊗ A. Returns a lazy KroneckerPower type.

source

Kronecker.:⊗ — Method

⊗(A::AbstractMatrix, pow::Int)

Kronecker power, computes A ⊗ A ⊗ ... ⊗ A. Returns a lazy KroneckerPower type.

source

Kronecker graphs

An exciting application of Kronecker powers (or Krocker products in general) is generating large, realistic graphs from an initial 'seed' via a stochastic process. This is called a Kronecker graph and is described in detail in Leskovec et al. (2008).

If we use an initial matrix $P$ with values in $[0,1]$ as a seed, then $P_n=P^{\otimes n}$ can be seen as a probability distribution for an adjacency matrix of a graph. The elements $(P_n)_{i,j}$ give the probabilities that there is an edge from node $i$ to node $j$. Leskovec and co-authors give two algorithms for sampling adjacency matrices from this distribution, both provided by Kronecker.jl:

naivesample gives exact samples, but has a computational time proportional to the number of elements and hence prohibitive for large graphs;
fastsample a recursive heuristic, has a computational time proportional to the expected number of edges in the graph.

The latter can easily scale to generate graphs of millions of nodes. Both return the adjacency matrix as a sparse array.

julia> using Kronecker
julia> P = rand(2, 2)2×2 Array{Float64,2}:
 0.936656  0.969162
 0.954668  0.2919
julia> P10 = P ⊗ 101024×1024 KroneckerPower{Float64,Array{Float64,2}}:
 0.519759  0.537797  0.537797  0.55646    …  0.706557     0.731077
 0.529754  0.161978  0.548139  0.167599      0.720144     0.220192
 0.529754  0.548139  0.161978  0.167599      0.212806     0.220192
 0.539941  0.165093  0.165093  0.0504789     0.216899     0.0663191
 0.529754  0.548139  0.548139  0.567161      0.212806     0.220192
 0.539941  0.165093  0.558679  0.170822   …  0.216899     0.0663191
 0.539941  0.558679  0.165093  0.170822      0.0640947    0.0663191
 0.550324  0.168267  0.168267  0.0514496     0.0653273    0.0199745
 0.529754  0.548139  0.548139  0.567161      0.212806     0.220192
 0.539941  0.165093  0.558679  0.170822      0.216899     0.0663191
 ⋮                                        ⋱
 0.616952  0.18864   0.18864   0.0576786  …  4.87663e-5   1.49108e-5
 0.593892  0.614502  0.614502  0.635828      0.000158858  0.000164371
 0.605312  0.185081  0.626319  0.191504      0.000161913  4.95067e-5
 0.605312  0.626319  0.185081  0.191504      4.78463e-5   4.95067e-5
 0.616952  0.18864   0.18864   0.0576786     4.87663e-5   1.49108e-5
 0.605312  0.626319  0.626319  0.648054   …  4.78463e-5   4.95067e-5
 0.616952  0.18864   0.638363  0.195186      4.87663e-5   1.49108e-5
 0.616952  0.638363  0.18864   0.195186      1.44107e-5   1.49108e-5
 0.628816  0.192267  0.192267  0.0587877     1.46878e-5   4.49096e-6
julia> sum(P10)  # expected number of edges96915.62106162743
julia> A = fastsample(P10)1024×1024 SparseArrays.SparseMatrixCSC{Bool,Int64} with 83574 stored entries:
  [2  ,    1]  =  1
  [3  ,    1]  =  1
  [4  ,    1]  =  1
  [5  ,    1]  =  1
  [7  ,    1]  =  1
  [8  ,    1]  =  1
  [9  ,    1]  =  1
  [13 ,    1]  =  1
  [15 ,    1]  =  1
  ⋮
  [642, 1023]  =  1
  [794, 1023]  =  1
  [1  , 1024]  =  1
  [21 , 1024]  =  1
  [37 , 1024]  =  1
  [98 , 1024]  =  1
  [131, 1024]  =  1
  [163, 1024]  =  1
  [321, 1024]  =  1
  [649, 1024]  =  1

Kronecker.isprob — Function

isprob(A::AbstractArray)

Test if a matrix can be interpeted as a probability matrix, i.e., all elements are between 0 and 1.

source

isprob(K::AbstractKroneckerProduct)

Test if a Kronecker product can be interpeted as a probability matrix, i.e., all elements are between 0 and 1.

source

Kronecker.naivesample — Function

naivesample(P::AbstractKroneckerProduct)

Sample a Kronecker graph from a probabilistic Kronecker product P using the naive method. This method has a time complexity in the size of the Kronecker product (but is still light in memory use). Consider using fastsample.

source

Kronecker.fastsample — Function

fastsample(P::AbstractKroneckerProduct)

Uses the heuristic sampling from Leskovec et al. (2008) to sample a large Kronecker graph.

source