mpbl#

Maximum potential bipartite lattice (MPBL) algorithm.

hypercoil.init.mpbl.maximum_potential_bipartite_lattice(potentials: Tensor | ~typing.Tuple[Tensor, Tensor], n_out: int | ~typing.Tuple[int, int], order: int, iters: int = 100, temperature: float = 0, random_init: bool = True, attenuation: float = 2.0, objective: Tensor | None = None, criterion: ~typing.Callable = <function corr_criterion>, *, key: ~jax._src.random.PRNGKey) → Tuple[Tensor | Tuple[Tensor, Tensor], Tensor, Tensor][source]#

Estimates the maximum potential bipartite lattice using a greedy Monte Carlo approach. A naive solution to the vertical compression problem.

Warning

This function is experimental and currently incompatible with JAX JIT compilation.

Parameters:
potentials: Tensor or (Tensor, Tensor)

Array of potentials to be maximised in the bipartition. This could, for instance, be the mutual information among vertices or the community allegiance matrix. Size: n_in x n_in If this is a tuple, then the algorithm will solve two different MPBL problems: one for each tensor. In this case, the first tensor should be of dimension H_in x H_in and the second should be of dimension W_in x W_in, where the dimension of the objective matrix is H_in x W_in.

n_out: int or (int, int)

Number of output vertices. Ideally, this should be selected such that there are many common multiples of n_out and the number of vertices in the input potentials.

order: int

Lattice order of the bipartition. 1: total number of edges is the least common multiple of n_in and

n_out

2: total number of edges is twice the least common multiple

iters: int

Number of iterations of the greedy approach to run. Only the result that maximises the final potential will be returned.

temperature: float

Softmax temperature for selecting the next vertex to fuse. 0 deterministically fuses the maximum (default). Infinity fuses randomly.

random_init: bool

Procedural initialisation. True begins from a random vertex (default). False begins from a vertex connected to the edge with the maximum overall potential.

attenuation: float

Attenuation factor for the potentials matrix. The potentials joining each vertex set that is compressed into a single new vertex are divided by the attenuation factor. This helps to prevent redundancy in compressed sets.

objective: Tensor

Tensor whose reconstruction from vertical compression determines the best bipartite lattice. If none is provided, the algorithm defaults to the input potentials matrix.

criterion: function

Objective function that accepts three parameters and returns a scalar value.

  • orig is the original objective matrix.

  • recon is the reconstructed objective matrix (compressed and uncompressed).

  • u is the vector of potentials included in the compression.

  • The returned scalar is minimal for an optimum compression.

Returns:
Tensor

Assignment of nodes into a bipartition that maximises the potential of the resultant graph, among those tried by the greedy approach. This is not guaranteed to be a global optimum.

float

Overall potential of the bipartition.

Tensor

Propagated potentials. These can be maximised, for instance, in downstream vertical compressions.