Spectral sparsification of graphs with negative edge weights

Question

I am reading the following well-known paper on spectral sparsification of weighted graphs: https://arxiv.org/pdf/0808.4134.pdf. Page 2 contains most of the definitions relevant to this question.

It is said that a weighted graph $\tilde{G}$ (with vertex set $V$) is a $\sigma$-spectral approximation of a weighted graph $G$ (also with vertex set $V$) if, for all $x \in \mathbb{R}^V$, \begin{equation*} \frac{1}{\sigma} x^T L_{\tilde{G}} x \leq x^T L_{G} X \leq \sigma x^T L_{\tilde{G}} x, \end{equation*} Where $L_{G}$ is the Laplacian of $G$ and $L_{\tilde{G}}$ is the Laplacian of $\tilde{G}$.

This definition seems to apply naturally to graphs which are permitted to have negative edge weights. However, the assumption that the weights are non-negative is made throughout the rest of the paper.

Are there known algorithms for constructing a spectral sparsifier of a graph with some negative edge weights?

Answer 1

I personally do not work in spectral graph theory. I write this from a linear algebra perspective.

This definition seems to apply naturally to graphs which are permitted to have negative edge weights

The problem is that Laplacians rely significantly on the fact that the edges are the same sign (either all positive or all negative; by convention, positive). Recall the definition of a Laplacian puts the negative edge weights on the off-diagonal and the sum of all outgoing edge weights on the diagonal. Since the weights are all the same sign, the magnitude of the sum of the weights is the same as the sum of their magnitudes: the diagonal entry is "larger" than the rest of the off-diagonal entries combined, in each row (and column). This "diagonal dominance" guarantees that the Laplacian is positive (semi-) definite by Gesgorin's circle theorem.

My background is not in spectral graph algorithms but intuitvely, efficient algorithms for computation with graph Laplacians rely heavily on symmetry and diagonal dominance, which is lost if edges are allowed to have different signs. I'm not familiar with any work on Laplacians for graphs with mixed sign weights; indeed, I'm not sure if such a Laplacian can even be called "Laplacian."