The cause of instability of LE iterative embedding

[skojaku]

Identified that this line of the code is the cause of the stability. By examining the error message from the eign solver, the matrix to be decomposed have excessively large values and make the solver instable.

https://github.com/BianKov/iterEmb/blob/dd8691be25335f1cd6168d331f42938a63545456/iteremb/embedding.py#L349C6-L349C54

A quick fix would be to clip the value to a very small value, for instance

sparse.diags(1.0/np.maximum(1e-16,np.sqrt(deg)))

This will help the solver being stable and perhaps run faster.

[skojaku]

Probable cause of the inconsistency

The solver starts from random vectors and update them iteratively to get the eigenvectors until convergence. The initial vectors are randomly initialized and are different between me and Bianka. Usually, the solver produces the same eigevectors if iteration converges. But given that the solver sometimes does not converge, and we did some trick to get through the non-convergence problem, the output of the eigensolvers might differ.

Why the solver becomes instable

Having examining the error message, it says that the matrix to be decomposed has extremely large/small values. And this occurrs when a node has effectively nearly zero degree during the iteration process, i.e., the node has edges but the weight (similarity) of the edges are very close to zero, so that the node is effectively unconnected to the rest of the network. If such a node exists, the normalized laplacian breaks since it involves the inverse of the node’s degree.

Fix

I confirmed that the problem is fixed by clipping the degree when if the degree is extremely small. Now that the iterative embedding works without any convergence problem, although this fix did not produce an extreme separation like 10^8.

[BianKov]

Following the original algorithm, we don't use anymore the normalized version of the graph Laplacian for which this examination was carried out.