<p>I personally do not work in spectral graph theory. I write this from a linear algebra perspective.</p>
<blockquote>
<p>This definition seems to apply naturally to graphs which are permitted to have negative edge weights</p>
</blockquote>
<p>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 &quot;larger&quot; than the rest of the off-diagonal entries combined, in each row (and column). This &quot;diagonal dominance&quot; guarantees that the Laplacian is positive (semi-) definite by Gesgorin's circle theorem.</p>
<p>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 &quot;Laplacian.&quot;</p>

CC BY-SA 4.0
2022-11-30T21:45:52.843Z
2022-11-30T21:45:52.843Z
BrownieInMotion
<p>I am reading the following well-known paper on spectral sparsification of weighted graphs: <a href="https://arxiv.org/pdf/0808.4134.pdf" rel="nofollow noreferrer">https://arxiv.org/pdf/0808.4134.pdf</a>. Page 2 contains most of the definitions relevant to this question.</p>
<p>It is said that a weighted graph <span class="math-container">$\tilde{G}$</span> (with vertex set <span class="math-container">$V$</span>) is a <span class="math-container">$\sigma$</span>-spectral approximation of a weighted graph <span class="math-container">$G$</span> (also with vertex set <span class="math-container">$V$</span>) if, for all <span class="math-container">$x \in \mathbb{R}^V$</span>,
<span class="math-container">\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*}</span>
Where <span class="math-container">$L_{G}$</span> is the Laplacian of <span class="math-container">$G$</span> and <span class="math-container">$L_{\tilde{G}}$</span> is the Laplacian of <span class="math-container">$\tilde{G}$</span>.</p>
<p>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.</p>
<p>Are there known algorithms for constructing a spectral sparsifier of a graph with some negative edge weights?</p>

<ds.algorithms><graph-theory><graph-algorithms><spectral-graph-theory><random-graphs>
Spectral sparsification of graphs with negative edge weights
K V
# Spectral sparsification of graphs with negative edge weights

(Asked by: username_0 on 2022-11-30)

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?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, spectral-graph-theory, random-graphs

---

## 1 answers

### Answer by username_1 on 2022-11-30. Score: 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."


---

