igraph::laplacian_matrix(normalized = TRUE) changes in igraph 2.0.0

[krlmlr]

Upstream: igraph/rigraph#1102 (comment).

Tracker: igraph/rigraph#989.

Can you work with normalized = FALSE or adapt to the new normalization behavior? It might be hard to restore the original behavior.

[szhorvat]

To clarify, this isn't a new normalization behaviour but a bug fix for the case when the graph contains self-loops. The old behaviour was incorrect so it won't be restored. Are you sure you want to use the Laplacian of a graph with loops?

For complete clarity, this is how igraph (and most authors) define the Laplacian $L$ of an undirected graph with adjacency matrix $A$:

$$L = D - A,$$

where $D$ is a diagonal matrix containing the degrees. More precisely, $D_{ii} = \sum_{j} A_{ij}$, keeping in mind that $A$ is symmetric. The normalized version is

$$L = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}.$$

These definitions were not followed properly by 1.6 when the diagonal of $A$ was not all-zero. In 2.0 they are.

Something to pay attention to here is that this definition assumes that each self-loop adds 2 (or twice its weight) to the diagonal of the adjacency matrix. This is implied by the definition of $D$ as $D_{ii} = \sum_{j} A_{ij}$.

[shchurch]

Thank you for bringing this to our attention and for the helpful clarifications. To give some context on what we were doing here:

We initially released our package in both python and R, and our aim was to achieve the exact same numerical result from spectral embedding in R as with scikit.manifold.spectral_embedding in python.

Here is the test result from python

Python 3.11.4 (main, Jul  5 2023, 09:00:44) [Clang 14.0.6 ] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> import numpy as np
>>> from sklearn.manifold._spectral_embedding import csgraph_laplacian
>>> 
>>> mat = np.array([[116,210,200],[210,386,380],[200,380,401]])
>>> norm_laplacian = bool
>>> adjacency = mat
>>> laplacian, dd = csgraph_laplacian(
...         adjacency, normed=norm_laplacian, return_diag=True
...     )
>>> laplacian
array([[ 1.        , -0.42697393, -0.41013239],
       [-0.42697393,  1.        , -0.64959638],
       [-0.41013239, -0.64959638,  1.        ]])

Given the new behavior of igraph, it sounds like we need to remove self loops to achieve this. My understanding is we can do this setting diag=F. I confirmed the same numeric result in R with the following

> #previously: 
> #Ai <- igraph::as.undirected(igraph::graph.adjacency(A,weighted=T))
> 
> #now:
> Ai <- igraph::graph_from_adjacency_matrix(A,mode="undirected",weighted=T,diag=F)

        L <- igraph::laplacian_matrix(Ai,normalized=T)> 
> L <- igraph::laplacian_matrix(Ai,normalized=T)
> 
> L
3 x 3 sparse Matrix of class "dgCMatrix"
                                     
[1,]  1.0000000 -0.4269739 -0.4101324
[2,] -0.4269739  1.0000000 -0.6495964
[3,] -0.4101324 -0.6495964  1.0000000

If this seems appropriate to you, I will make that change.
Thanks again
Sam

[szhorvat]

You don't need to cycle the graph through an adjacency matrix to remove self-loops. You can simply use simplify(graph, remove.multiple = FALSE, remove.loops = TRUE). I hope this helps.

[shchurch]

Ok thanks. I will simplify in the next patch.

Closing this issue now, I hope this resolves the reverse dependency issue above.

Feel free to open a new issue if something else is needed.