python-graphblas/graphblas-algorithms

Alternative for square counting (for square clustering)

eriknw opened this issue · 0 comments

Inspired from this paper, https://arxiv.org/pdf/2007.11111.pdf, we can compute square counting for all nodes via:

    Q(~degrees.diag().S) << plus_pair(A @ A)  # Use mask to ignore diagonal
    all_squares = (Q * (Q - 1)).reduce_rowwise() // 2

This is probably better than counting squares one node at a time.

Now, can we come up with a better way to compute the denominator?