# Pearson Correlations on Networks:
Corrigendum

Michele Coscia  CS Department, IT University of Copenhagen, Rued Langgaards
Vej 7, Copenhagen, DK  Karel Devriendt  Max Planck Institute for Mathematics
in the Sciences, Inselstraße 22, Leipzig, DE

###### Abstract

Recently, the first author proposed a measure to calculate Pearson
correlations for node values expressed in a network, by taking into account
distances or metrics defined on the network. In this technical note, we show
that using an arbitrary choice of distances might result in imaginary or
unbounded correlation values, which is undesired. We prove that this problem
is solved by restricting to a special class of distances: negative type
metrics. We also discuss two natural classes of negative type metrics on
graphs, for which the network correlations are properly defined.

##  1 Introduction

In [3] the first author extended the familiar Pearson linear correlation
coefficient to the case in which the correlated vectors live on a graph. In
practice, this means that each entry in the vector corresponds to a node in
the network. Then, to estimate the correlation, one compares the value for a
node in a vector with the values of all other nodes in the network from the
other vector, proportionally to their network distance. This is opposed to the
regular Pearson correlation, where only the values of the corresponding
entries are compared with each other, without checking their neighbors.

To compute the extended Pearson correlation, one needs to specify a weight
matrix $W$, which reflects the structure of the network. The original paper
fails to discuss properly the criteria one should follow when picking $W$.
This is important, because it is not just a matter of performance or
intuitiveness: some values of $W$ are invalid.

In this technical note we show that there is a strong constraint on $W$.
Specifically, $W$ must be positive definite for vectors with zero sum,
otherwise it would generate imaginary or infinite network Pearson correlation
values. These problems can arise for the $W$ suggested as default in [3],
which is a weight matrix defined based on the shortest path distances in the
graph.

We also show that this constraint is not insurmountable: all we need to obtain
a proper $W$ is to use a negative type metric instead of the shortest-path
distance. There are a few intuitive options to create positive definite $W$s.
We propose two examples, one based on effective resistances [10, 4], the other
on Euclidean node embeddings [13, 2].

The code and data to verify the claims of this note are publicly available at
http://www.michelecoscia.com/?page_id=2268.

##  2 Network Correlation

The classical Pearson linear correlation coefficient is defined as:

$\rho_{x,y}=\dfrac{\sum
I\times(\hat{x}\otimes\hat{y})}{\sigma_{x}\sigma_{y}},$ (1)

where:

  * •

$I$ is the identity matrix;

  * •

$\hat{x}=x-\bar{x}$ is the centered version of $x$, i.e. $x$ minus its mean
$\bar{x}$;

  * •

$\times$ is the elementwise matrix product;

  * •

$\otimes$ is the outer product;

  * •

$\sigma_{x}=\sqrt{\sum I\times(x\otimes x)}$ is the standard deviation of $x$.

We use this notation because it makes it easier to extend it to the network
case. In practice, multiplying $I$ with $\hat{x}\otimes\hat{y}$ results in
considering only its main diagonal, whose sum is the covariance of $x$ and
$y$.

Now suppose that we have a graph $G=(V,E)$ and that both $x$ and $y$ are
vectors of length $|V|$ – i.e. they record one value per node of $G$. We can
extend Equation 1 to take into account the topology of $G$. Specifically, a
valid measure of network co-variance will weight each entry $ij$ of
$\hat{x}\otimes\hat{y}$ proportionally to some function of the network
distance between nodes $i$ and $j$ in $G$, rather than only considering the
diagonal $ii$ entries like in the regular Pearson correlation.

We can do so by specifying a proper matrix $W$, and define the network Pearson
correlation as:

$\rho_{x,y,G}=\dfrac{\sum
W\times(\hat{x}\otimes\hat{y})}{\sigma_{x,W}\sigma_{y,W}},$ (2)

with $\sigma_{x,W}=\sqrt{\sum W\times(x\otimes x)}$.

The original paper [3] proposes $W=e^{-kP}$, where $P_{ij}$ is the shortest
path length between nodes $i$ and $j$ in $G$ and where the exponent is taken
entrywise. $k$ is a simple scaling factor, with default value $k=1$ – when it
applies, we omit $k$ for simplicity as it does not affect any of the arguments
in this note.

##  3 Problem of Negative Variances

Let us consider the formulation of $\sigma_{x,W}$. This is the square root of
the network variance of $x$ and it appears in the denominator of the network
Pearson correlation. It follows that $\sum W\times(x\otimes x)$ must be a
strictly positive value: if it were negative, Equation 2 evaluates as an
imaginary number, which would be hardly interpretable as a network correlation
and, if it were zero, Equation 2 would become infinity.

###  3.1 Conditions on the Weight Matrix $W$

The above observations lead to the following conditions on $W$ that make the
network correlation well-defined.

###### Proposition 1

The network Pearson correlation (2) is well-defined (real and finite) for all
non-constant input vectors $x,y$ if and only if the weight matrix $W$ is
positive definite on $\operatorname{span}(1)^{\perp}$. Furthermore, in this
case the network Pearson correlation is a real number in $[-1,1]$.

Proof By “well-defined” we mean that the network Pearson correlation
$\rho_{x,y,G}$ is real and finite for all real input vectors $x,y$ that are
not constant.

First, the numerator of the network Pearson correlation $\rho_{x,y,G}$ is a
quadratic form over the reals determined by a real, symmetric matrix $W$. This
produces a finite real number as necessary.

Second, the denominator of the network Pearson correlation equals

$\sigma_{x,W}\sigma_{y,W}=\sqrt{\left(\sum
W_{ij}\hat{x}_{i}\hat{x}_{j}\right)\left(\sum
W_{ij}\hat{y}_{i}\hat{y}_{j}\right)},$ (3)

i.e. the product of two quadratic forms determined by the matrix $W$. We note
that the normalization $x\rightarrow\hat{x}=x-\bar{x}$ leads to
$\sum\hat{x}=0\Rightarrow\hat{x}\perp 1$, which means that the quadratic forms
are defined on $\operatorname{span}(1)^{\perp}$. For $\rho_{x,y,G}$ to be
well-defined, both quadratic forms in (3) need to be nonnegative – if one were
negative, then the square root would yield an imaginary number – and nonzero –
if one were zero then this would yield a division by zero; in other words, the
quadratic form needs to be strictly positive on
$\operatorname{span}(1)^{\perp}$, which is equivalent to $W$ being positive
definite on $\operatorname{span}(1)^{\perp}$; see for instance [9, Def. 4.1.9
& Thm 4.1.10]. We note that the vectors $x$ and $y$ cannot be constant,
because then $\hat{x}=0$ results in a division by zero.

To prove the bounds when $W$ is positive definite on
$\operatorname{span}(1)^{\perp}$, we invoke the Cauchy-Schwarz inequality

$\left(\sum W_{ij}\hat{x}_{i}\hat{y}_{j}\right)^{2}\leq\left(\sum
W_{ij}\hat{x}_{i}\hat{x}_{j}\right)\left(\sum
W_{ij}\hat{y}_{i}\hat{y}_{j}\right).$

Taking the square root, we find that $-\sqrt{\sigma_{x,W}\sigma_{y,W}}\leq\sum
W_{ij}\hat{x}_{i}\hat{y}_{j}\leq\sqrt{\sigma_{x,W}\sigma_{y,W}}$ and thus
$\rho_{x,y,G}\in[-1,1]$ as required. This completes the proof. $\square$

To summarize, the proposition says that once we choose formula (2) then it is
necessary to require that $W$ is a positive definite matrix on
$\operatorname{span}(1)^{\perp}$ and, as a side-effect of this requirement, we
furthermore get that the network Pearson correlation is bounded in $[-1,1]$,
similar to the classical Pearson correlation.

For a given matrix $W$, one can determine whether it is positive definite on
$\operatorname{span}(1)^{\perp}$ or not as follows: first, calculate the
matrix $\hat{W}$ with entries
$\hat{W}_{ij}=W_{ij}-\tfrac{1}{n}\sum_{k}(W_{ik}+W_{kj})+\tfrac{1}{n^{2}}\sum_{kl}W_{kl}$,
where $n$ is the size of the matrix. Second, calculate the eigenvalues of
$\hat{W}$. If $\hat{W}$ has $n-1$ strictly positive eigenvalues and $1$ zero
eigenvalue, then $W$ is positive definite on $\operatorname{span}(1)^{\perp}$
and otherwise it is not.

###  3.2 Examples

We now give some examples where the matrix $W=e^{-kP}$ is not positive
definite on $\operatorname{span}(1)^{\perp}$ and should therefore not be used
to calculate network correlation coefficients. A first example is the complete
bipartite graph on $2$ and $3$ nodes, shown in Figure 1. Its adjacency matrix
$A$, distance matrix $P$ and the eigenvalues of $\hat{W}=\widehat{e^{-P/4}}$
are equal to:

$A=\left(\begin{smallmatrix}0&0&1&1&1\\\ 0&0&1&1&1\\\ 1&1&0&0&0\\\
1&1&0&0&0\\\ 1&1&0&0&0\\\ \end{smallmatrix}\right)\quad
P=\left(\begin{smallmatrix}0&2&1&1&1\\\ 2&0&1&1&1\\\ 1&1&0&2&2\\\ 1&1&2&0&2\\\
1&1&2&2&0\\\
\end{smallmatrix}\right)\quad\lambda\left(\hat{W}\right)=(0.3935,~{}0.3935,~{}0.3935,0,\textbf{-0.2}).$

The negative eigenvalue shows that $W$ is not positive semi-definite and thus
by Proposition 1 not a good weight matrix to measure the network Pearson
correlation.

Figure 1: A network with negative eigenvalues for $W=e^{-kP}$.

Examples are not limited to small and relatively simple graphs. A second and
more practical example comes from a Twitter network that records debates in
the US over some political issues – this is data from [8]. The network has
$|V|=4,458$ nodes and $|E|=7,024$ edges, which makes it far from trivial. We
calculate the eigenvalues of $\hat{W}=\widehat{e^{-P}}$ as described above and
verify that we obtain a few negative ones. For instance, the minimum
eigenvalue is $-5.46$. Thus, if we were to set $x$ to be the eigenvector
corresponding to this minimum eigenvalue, then $\sum W\times(x\otimes x)$
would be equal to $-5.46$, and give rise to a negative variance and an
imaginary correlation value.

##  4 Solution

As outlined in the introduction, one way to obtain a good weight matrix
$W=e^{-kP}$ is to use a negative type metric for $P$. We first prove this
formally and then describe two natural choices of negative type metrics on
networks. These give rise to good weight matrices to measure network Pearson
correlations.

###  4.1 Negative Type Metric Spaces

The proposal in [3] for a weighting matrix was $W=e^{-kP}$ where $P$ is the
shortest-path distance matrix of the network. While this choice will generally
not result in a well-defined correlation measure, it turns out that other
types of distance matrices can work. More precisely, this is the case for so-
called _negative type metrics_. A negative type metric (or distance) is
defined as a metric whose distance matrix $D$ is negative semidefinite on
$\operatorname{span}(1)^{\perp}$; in other words, $-\hat{D}$ has no strictly
negative eigenvalues. These metrics were introduced by Schoenberg in the
context of distance geometry [15] and they have many nice properties [11, 12].
Several examples of negative type metrics are listen in [12, Thm. 3.6].

Negative type metrics give rise to positive definite matrices as follows:

######  Proposition 2 ([12, Thm 3.3])

The matrix $e^{-kD}$ (with entrywise exponential) is positive definite for all
$k>0$ if $D$ is the distance matrix of a metric space of negative type.

If a matrix is positive definite, it is also positive definite on
$\operatorname{span}(1)^{T}$. This means that weight matrices $e^{-kD}$ for
negative type metrics $D$ can be used to measure network correlations. We also
remark that the statement is even stronger: the entrywise exponent $e^{-kD}$
of a distance matrix is positive definite for all $k>0$ if and only if if the
distance has negative type. Thus, if we choose the exponential of a distance
matrix as a weighting matrix, then negative type metrics are the only metrics
that lead to a well-defined correlation.

As noted before, we can check whether a distance matrix has negative type by
calculating the matrix $-\hat{D}$ and checking whether it has any negative
eigenvalues. In what follows, we mention two examples of negative type metrics
which are relevant in the context of networks.

###  4.2 Effective Resistance

A first option to obtain a good weight matrix $W$ is to use the effective
resistance distance [10, 4]. The effective resistance between two nodes is the
resistance of the total system when a unit voltage is connected across the
nodes, where the graph $G$ is interpreted as an electrical circuit with 1 Ohm
resistors as edges (in the case of unweighted undirected graphs) [6].

The effective resistance is a negative type metric. This was shown for
instance by Fiedler in [7] and was discussed in detail in [5]. It follows from
Proposition 2 that if $\Omega$ is our matrix recording all pairwise effective
resistance values, then $W=e^{-k\Omega}$ is positive definite and thus a valid
weight matrix.

###  4.3 Node Embeddings

A second example of negative type metrics are the distances between points in
Euclidean space $\mathbb{R}^{d}$; this example is included in the list of
negative type metric spaces in [12, Thm. 3.6] and a number of proofs are
summarized in [11]. This case of negative type metric spaces can be relevant
in the context of networks when an embedding of the network is given. In many
of today’s machine learning pipelines for analyzing networks and related data,
one of the first steps includes an _embedding_ of the nodes of the network in
Euclidean space (or some other spaces [1]). The goal of this embedding is that
nodes which are “close together” or “similar” in the network also end up close
together in the embedding space. After this embedding, the network data can
then be analysed in the much familiar setting of vectors in Euclidean space,
where many standard techniques are available.

It then follows from Proposition 2 that, if $\Delta$ is our matrix recording
all pairwise Euclidean distances between embedded nodes, then $W=e^{-k\Delta}$
is positive definite. Depending on the specific algorithm used to generate the
node embeddings, one would get a different (positive) estimate for $\sum
W\times(x\otimes x)$ for the bipartite $2\times 3$ graph and the network in
Figure 1.

Note that many algorithms to derive node embeddings – for instance DeepWalk
[13] – are not deterministic, because they are based on random walks. If one
needs a deterministic result, they can use effective resistance. In fact,
effective resistances can also be interpreted as coming from Euclidean
embeddings; this is often referred to as the commute time embedding [14].
However, as we pointed out above, one might already have calculated the
embeddings for other purposes. If that is the case, then they would obtain a
correlation measure “for free” without having to perform the computationally
intensive effective resistance calculation. So the two approaches we sketch
here – effective resistance and node embeddings – are both suitable for
different scenarios.

##  5 Conclusion

In this note we have shown that, if one wants to calculate the network
correlation proposed in [3], they need to choose a positive definite $W$
matrix when representing the graph’s topology. The original suggestion of
using the matrix of pairwise shortest path distances is invalid because such
choice leads to a $W$ that is not positive definite. We show that using
pairwise effective resistance or Euclidean distances between node embeddings
are valid alternatives.

## Acknowledgements

We thank Andrea Luppi for pointing the potential issue with negative variance
values, and for the fruitful discussion that followed.

## References

  * [1] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst.  Geometric deep learning: going beyond Euclidean data.  IEEE Signal Processing Magazine, 34(4):18–42, 2017.
  * [2] Michele Coscia.  The atlas for the aspiring network scientist.  arXiv preprint arXiv:2101.00863, 2021.
  * [3] Michele Coscia.  Pearson correlations on complex networks.  Journal of Complex Networks, 9(6):cnab036, 2021.
  * [4] Karel Devriendt.  Effective resistance is more than distance: Laplacians, simplices and the Schur complement.  Linear Algebra and its Applications, 639:24–49, 2022.
  * [5] Karel Devriendt.  Graph geometry from effective resistances.  PhD thesis, University of Oxford, 2022.
  * [6] Wendy Ellens, Floske M. Spieksma, Piet Van Mieghem, Almerima Jamakovic, and Robert E. Kooij.  Effective graph resistance.  Linear algebra and its applications, 435(10):2491–2506, 2011.
  * [7] Miroslav Fiedler.  Matrices and Graphs in Geometry.  Encyclopedia of mathematics and its applications ; 139. Cambridge University Press, Cambridge, UK, 2011.
  * [8] Marilena Hohmann, Karel Devriendt, and Michele Coscia.  Quantifying ideological polarization on a network using generalized Euclidean distance.  Science Advances, 9(9):eabq2044, 2023.
  * [9] Roger A. Horn and Charles R. Johnson.  Matrix Analysis.  Cambridge University Press, Cambridge, UK, 2nd edition, dec 2013.
  * [10] Douglas J. Klein and Milan Randić.  Resistance distance.  Journal of mathematical chemistry, 12(1):81–95, 1993.
  * [11] Russell Lyons.  Distance covariance in metric spaces.  The Annals of probability, 41(5):3284–3305, 2013.
  * [12] Mark W. Meckes.  Positive definite metric spaces.  Positivity, 17(3):733–757, 2013.
  * [13] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 701–710, 2014.
  * [14] Huaijun Qiu and Edwin R. Hancock.  Clustering and embedding using commute times.  IEEE transactions on pattern analysis and machine intelligence, 29(11):1873–1890, 2007.
  * [15] Isaac J. Schoenberg.  Metric spaces and completely monotone functions.  Annals of Mathematics, pages 811–841, 1938.