# What is the normalized graph matrix if the row-sum of proximity matrix is zero?

Let $$S \in \mathbb{R}_{\ge 0}^{n \times n}$$ be the proximity (or similarity) matrix of a graph, e.g. $$S = \left[ \begin{matrix} 0 & 0.9 & 0.3 \\ 0.9 & 0 & 0.4 \\ 0.3 & 0.4 & 0 \end{matrix}\right]$$ Here, the elements on the diag should be $$0$$s.

Now, we define $$D$$ be a diagonal matrix with the row-sum of $$S$$ on the diagonal entries. In my running example, $$D = \left[ \begin{matrix} 1.2 & 0 & 0 \\ 0 & 1.3 & 0 \\ 0 & 0 & 0.7 \end{matrix}\right]$$

Then, we normalize $$S$$ with $$D$$, i.e. \begin{align} \bar{S} &= D^{-\frac{1}{2}} S D^{-\frac{1}{2}} \\ &= \left[ \begin{matrix} \frac{1}{\sqrt{1.2}} & 0 & 0 \\ 0 & \frac{1}{\sqrt{1.3}} & 0 \\ 0 & 0 & \frac{1}{\sqrt{0.7}} \end{matrix}\right] \left[ \begin{matrix} 0 & 0.9 & 0.3 \\ 0.9 & 0 & 0.4 \\ 0.3 & 0.4 & 0 \end{matrix}\right] \left[ \begin{matrix} \frac{1}{\sqrt{1.2}} & 0 & 0 \\ 0 & \frac{1}{\sqrt{1.3}} & 0 \\ 0 & 0 & \frac{1}{\sqrt{0.7}} \end{matrix}\right] \\ \end{align} (omit subsequent steps...)

My question is: How can I handle when the row-sum of $$S$$ is zero?

Specifically, if $$S = \left[ \begin{matrix} 0 & 0 & 0.3 \\ 0 & 0 & 0 \\ 0.3 & 0 & 0 \end{matrix}\right]$$ i.e. no edge is connected to vertex 2. Thus, $$D$$ will be $$D = \left[ \begin{matrix} 0.3 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0.3 \end{matrix}\right]$$ As a result, I don't know how to compute $$D^{-\frac{1}{2}}$$. 😔 So, what is the correct calculation method for $$D^{-\frac{1}{2}}$$ and $$\bar{S}$$ hereafter at this time?

• Not my field, but are you referring to the Graph Distance Matrix? Would a zero column indicate that a given vertex was distance zero from every other vertex? Is that permitted in such a matrix? – Theo Bendit Apr 23 at 11:51
• @TheoBendit Maybe Graph Distance Matrix is what I refer. I look up wikipedia and find a sentence in the 2nd para., it says "For the isolated vertices (those with degree 0), a common choice is to set the corresponding element ${\textstyle L_{i,i}^{\text{rw}}}$ to 0." Is it right for my question? – Lizhi Liu Apr 23 at 12:16
• It doesn't look right for your question. The Laplacian matrix has negative entries, whereas your matrices don't seem to. Could you define what a proximity matrix is? Am I correct in thinking that it's an $n \times n$ matrix $A$ defined by $n$ points $x_1, \ldots, x_n$ where $A_{ij} = d(x_i, x_j)$? – Theo Bendit Apr 23 at 12:26
• @TheoBendit Yes, your understanding is right! – Lizhi Liu Apr 23 at 12:30
• OK, so then the $i$th column totalling zero can only happen if every entry is $0$, since every distance is non-negative. This means that $d(x_i, x_j) = 0$ for all $j$, which presumably means that $x_i = x_j$ for all $j$. That is, every point is equal to every other point, and the whole matrix is the zero matrix. This seems like a pretty degenerate case, and I suspect that such a case is either purposefully excluded, or already normalised without having to conjugate by $D^{\frac{1}{2}}$. – Theo Bendit Apr 23 at 12:34

## 1 Answer

(This is just an expansion on the points in the comments above, so that the question has a proper answer.)

Given $$n$$ points $$x_1, \ldots, x_n$$ in a metric space $$(X, d)$$ (e.g. $$X = \Bbb{R}^m$$ with the Euclidean distance function), the proximity matrix $$A$$ is defined by $$A_{ij} = d(x_i, x_j)$$. Naturally, the symmetry of metrics imply that $$A$$ must be symmetric, and the positive-definiteness of the metric implies that the entries of $$A$$ are non-negative, with $$0$$s down the diagonal.

However, not every symmetric matrix with non-negative entries and $$0$$s down the diagonal will be a proximity matrix. Indeed, the example provided: $$S = \begin{pmatrix} 0 & 0 & 0.3 \\ 0 & 0 & 0 \\ 0.3 & 0 & 0 \end{pmatrix}$$ cannot be a proximity matrix, as we have $$d(x_1, x_3) = 0.3 > 0 + 0 = d(x_1, x_2) + d(x_2, x_3),$$ violating triangle inequality.

Indeed, if the $$j$$th column of the matrix sums to $$0$$, then we have $$d(x_i, x_j) = 0$$ for all $$i$$, as each entry is non-negative. By the definiteness of the metric, this implies $$x_i = x_j$$ for all $$i$$. That is, all the points are the same! In such cases, every entry in the proximity matrix must be $$0$$.

Can this ever happen? Sure, if all the points are the same. If not, then all the column sums are strictly positive, and computation of $$D^{-\frac{1}{2}}$$ is straight forward.

Is this allowed to happen? Maybe; it depends on the circumstances. Certainly such a case is pretty degenerate, and I could foresee many applications of proximity matrices rejecting such a case, or treating it specially.

Ultimately, it's up to the individual to decide what their proximity matrix is modelling, and what every point being identical says about the situation they're modelling.

In this case, you indicated that this was modelling protein interactions, with $$0$$ columns appearing when data was missing. It's difficult to tell without a much wider perspective, but it would appear that filling in missing data with zeros breaks the proximity matrix, for the reasons argued above (it makes the matrix not a valid proximity matrix). If you don't have data on a given protein, then try performing your analysis with one fewer protein.

• Thank you for ur very long supplement! Grateful! – Lizhi Liu Apr 24 at 5:17