Bug: Negative eigenvalues from normalized_hypergraph_laplacian

[kaiser-dan]

Summary

The normalized hypergraph Laplacian of a hypergraph with non-uniformly sized edges is capable of returning negative eigenvalues.

Example

Below is a (minimal?) working example

import xgi
import numpy as np
from scipy.linalg import eigh

E = [
    {1, 2, 3},
    {1, 4, 5},
    {1, 6, 7, 8},
    {4, 9, 10, 11, 12},
    {1, 13, 14, 15, 16},
    {4, 17, 18}
]
H = xgi.Hypergraph(E)

L = xgi.normalized_hypergraph_laplacian(H, sparse=False)
evals, evecs = eigh(L)

assert np.all(evals >= 0)

Suspected problem

The referenced paper [1] in the implementation states that the Laplacian should have a trivial eigenvalue, eigenvector pair with eigenvalue 0 and eigenvector $(\sqrt{k_i})_i$. Since the Laplacian is real symmetric and positive semi-definite, it should also have non-negative real eigenvalues so I believe that eigenvalues are impossible.

Looking through the source implementation, I suspect the problem is that the current implementation utilizes a simplification of the Laplacian that is only valid in 2-uniform hypergraphs as derived in [1].

Suggested fix

I have been able to circumvent this error by relying on the definition directly in [1], i.e.,
$$\mathcal{L} = I - D_v^{-\frac{1}{2}}HD_e^{-1}H^{T}D_v^{-\frac{1}{2}}$$ (for unweighted hypergraphs).

I am happy to create a pull request!

Also, this is my first time submitting an issue to a public repo - sorry if I have done anything wrong with it!

---

[1] “Learning with Hypergraphs: Clustering, Classification, and Embedding” by Dengyong Zhou, Jiayuan Huang, Bernhard Schölkopf Advances in Neural Information Processing Systems (2006)

[maximelucas]

Hi @kaiser-dan, thanks for raising this issue, you exposed things very clearly!

After a quick check of the ref, I agree with you, it looks like we should've used the general formula.

For future reference, the original ref even works for weighted hypergraphs by adding a weight matrix $W$, where $\Delta$ is the Laplacian (top of page 5):

Feel free to create a pull request with your current solution, thanks so much!

[kaiser-dan]

Okie done, I have created a pull request #648