modularity: Relaxed modularity

modularity

hypercoil.loss.modularity(Q: Tensor, A: Tensor, D: Tensor | None = None, theta: Tensor | None = None, *, gamma: float = 1.0, exclude_diag: bool = True, key: PRNGKey | None = None)

Modularity functional.

The connectopies that minimise the modularity functional define a community structure for the graph.

Dimension:

Q : \((D, C)\)

D denotes the number of vertices in the affinity matrix and C denotes the number of proposed maps.

A : \((D, D)\)

As above.

D : \((D, D)\)

As above.

theta : \((C)\) or \((C, C)\)

As above.

Parameters:

Qtensor

Proposed connectopies or maps.

Atensor

Affinity matrix.

Dtensor or None (default None)

If this argument is provided, then the affinity matrix is first transformed as \(D A D^\intercal\). For instance, setting D to a diagonal matrix whose entries are the reciprocal of the square root of vertex degrees corresponds to learning eigenmaps of a normalised graph Laplacian.

thetatensor, float, or None (default None)

Parameterisation of the pairwise dissimilarity function.

omegatensor, float, or None (default None)

Optional parameterisation of the affinity function, if one is provided.

dissimilaritycallable

Function to compute dissimilarity between latent coordinates induced by the proposed connectopies. By default, the square of the L2 distance is used. The callable must accept Q and theta as arguments. (theta may be unused.)

affinitycallable or None (default None)

If an affinity function is provided, then the image of argument A under this function is the affinity matrix. Otherwise, argument A is the affinity matrix.

gammafloat (default 1.)

Modularity parameter. Takes the place of the omega argument in connectopy.

exclude_diagbool (default True)

If True, then the diagonal of the affinity matrix is set to zero.

Returns:

Tensor

Connectopic functional value.

ModularityLoss

class hypercoil.loss.ModularityLoss(nu: float = 1.0, name: str | None = None, *, theta: Tensor | None = None, gamma: float = 1.0, exclude_diag: bool = True, scalarisation: Callable | None = None, key: 'jax.random.PRNGKey' | None = None)

Differentiable relaxation of the Girvan-Newman modularity.

This relaxation supports non-deterministic assignments of vertices to communities and non-assortative linkages between communities. It reverts to standard behaviour when the inputs it is provided are standard (i.e., deterministic and associative).

Girvan-Newman Modularity Relaxation

The relaxed modularity loss is defined as the negative sum of all entries in the Hadamard (elementwise) product between the modularity matrix and the coaffiliation matrix.

\(\mathcal{L}_Q = -\nu_Q \mathbf{1}^\intercal \left( B \circ H \right) \mathbf{1}\)

• The modularity matrix \(B\) is the difference between the observed connectivity matrix \(A\) and the expected connectivity matrix under some null model that assumes no community structure, \(P\): \(B = A - \gamma P\).

  • The community resolution parameter \(\gamma\) essentially determines the scale of the community structure that optimises the relaxed modularity loss.

  • By default, we use the Girvan-Newman null model \(P_{GN} = \frac{A \mathbf{1} \mathbf{1}^\intercal A}{\mathbf{1}^\intercal A \mathbf{1}}\), which can be interpreted as the expected weight of connections between each pair of vertices if all existing edges are cut and then randomly rewired.

  • Note that \(A \mathbf{1}\) is the in-degree of the adjacency matrix and \(\mathbf{1}^\intercal A\) is its out-degree, and the two are transposes of one another for symmetric \(A\). Also note that the denominator \(\mathbf{1}^\intercal A \mathbf{1}\) is twice the number of edges for an undirected graph.)

• The coaffiliation matrix \(H\) is calculated as \(H = C_{in} L C_{out}^\intercal\), where \(C_{in} \in \mathbb{R}^{(v_{in} \times c)}\) and \(C_{out} \in \mathbb{R}^{(v_{out} \times c)}\) are proposed assignment weights of in-vertices and out-vertices to communities. \(L \in \mathbb{R}^{c \times c)}\) is the proposed coupling matrix among each pair of communities and defaults to identity to represent associative structure.

  • Note that, when \(C_{in} = C_{out}\) is deterministically in \(\{0, 1\}\) and \(L = I\), this term reduces to the familiar delta-function notation for the true Girvan-Newman modularity.

Penalising this favours a weight that induces a modular community structure on the input matrix – or, an input matrix whose structure is reasonably accounted for by the proposed community affiliation weights.

Warning

To conform with the network community interpretation of this loss function, parameters representing the community affiliation \(C\) and coupling \(L\) matrices can be pre-transformed. Mapping the community affiliation matrix \(C\) through a softmax function along the community axis lends the affiliation matrix the intuitive interpretation of distributions over communities, or a quantification of the uncertainty of each vertex’s community assignment. Similarly, the coupling matrix can be pre-transformed through a sigmoid to constrain inter-community couplings to \((0, 1)\).

Note

Because the community affiliation matrices \(C\) induce parcellations, we can regularise them using parcellation losses. For instance, penalising the entropy will promote a solution wherein each node’s community assignment probability distribution is concentrated in a single community. Similarly, using parcel equilibrium will favour a solution wherein communities are of similar sizes.

Parameters:

name: str

Designated name of the loss function. It is not required that this be specified, but it is recommended to ensure that the loss function can be identified in the context of a reporting utilities. If not explicitly specified, the name will be inferred from the class name and the name of the scoring function.

nu: float

Loss strength multiplier. This is a scalar multiplier that is applied to the loss value before it is returned. This can be used to modulate the relative contributions of different loss functions to the overall loss value. It can also be used to implement a schedule for the loss function, by dynamically adjusting the multiplier over the course of training.

thetatensor, float, or None (default None)

Parameterisation of the pairwise dissimilarity function.

omegatensor, float, or None (default None)

Optional parameterisation of the affinity function, if one is provided.

dissimilaritycallable

Function to compute dissimilarity between latent coordinates induced by the proposed connectopies. By default, the square of the L2 distance is used. The callable must accept Q and theta as arguments. (theta may be unused.)

affinitycallable or None (default None)

If an affinity function is provided, then the image of argument A under this function is the affinity matrix. Otherwise, argument A is the affinity matrix.

gammafloat (default 1.)

Modularity parameter. Takes the place of the omega argument in connectopy.

exclude_diagbool (default True)

If True, then the diagonal of the affinity matrix is set to zero.

scalarisation: Callable

The scalarisation function to be used to aggregate the values returned by the scoring function. This function should take a single argument, which is a tensor of arbitrary shape, and return a single scalar value. By default, the mean scalarisation is used.

Methods

__call__(Q, A[, D, theta, key])

Call self as a function.