Pearson Correlations on Networks: Corrigendum

Michele Coscia, Karel DevriendtarXiv 2024 · DOI · arXiv

TL;DR

A previous method for calculating Pearson correlations on networks was found to produce "impossible" results, like imaginary numbers or infinite values. This paper identifies the mathematical culprit—non-positive definite weight matrices—and provides a robust fix using "negative type metrics" like effective resistance and Euclidean embeddings.

What Problem Does This Paper Address?

In standard statistics, the Pearson correlation coefficient measures how two variables move together. When those variables are values assigned to nodes in a network (like the income and education levels of people in a social graph), we often want a "network-aware" correlation. This means comparing a node’s value not just to the corresponding value in the other vector, but also to the values of its neighbors, weighted by their distance in the graph.

In 2021, Michele Coscia (the first author of this note) proposed a way to do exactly this. However, it turned out that the original suggestion—using a weight matrix based on the shortest path distances between nodes—contained a mathematical trap. Under certain conditions, this approach could lead to negative variances, resulting in imaginary correlation values or correlations that exceed the logical bounds of $[-1, 1]$. This technical note serves as a "corrigendum" to fix that framework.

Methods

The authors re-examine the formula for network correlation: $$\rho_{x,y,G} = \frac{\sum W \times (\hat{x} \otimes \hat{y})}{\sigma_{x,W} \sigma_{y,W}}$$ Where $W$ is a weight matrix reflecting the network structure.

The key contribution is a formal proof (Proposition 1) stating that for the correlation to be well-defined, real, and bounded between -1 and 1, the weight matrix $W$ must be positive definite on the space of vectors with a zero sum ($\text{span}(1)^\perp$).

To achieve this, the authors reach into the field of distance geometry. They show that if you define $W$ as $e^{-kD}$ (where $D$ is a distance matrix), the math only works if $D$ is a negative type metric. They then identify two specific metrics that satisfy this requirement for networks:

  1. Effective Resistance: Treating the graph like an electrical circuit.
  2. Euclidean Node Embeddings: Mapping nodes into a multi-dimensional space where distances are naturally Euclidean.

Datasets

The authors use two examples to demonstrate how the original "shortest path" method fails:

  • Synthetic Dataset: A complete bipartite graph ($K_{2,3}$). Despite its simplicity, the shortest-path distance matrix for this graph yields a negative eigenvalue, proving it can produce invalid correlations.
  • Real-World Dataset: A Twitter network representing US political debates (4,458 nodes and 7,024 edges). They show that even in complex, real-world topologies, the shortest-path approach fails, yielding a minimum eigenvalue of -5.46.

Key Insights and Ideas

  • The "Shortest Path" Trap: Intuitively, shortest paths seem like the most natural way to measure distance on a graph. However, the shortest-path metric is not of "negative type." This means it doesn't play nicely with the exponential functions used to create weight matrices, leading to the "negative variance" problem.
  • The Schoenberg Connection: The paper bridges network science with classical results from Isaac Schoenberg (1938). By identifying that network correlation requires positive definite kernels, the authors can tap into decades of established distance geometry.
  • Effective Resistance as a Superior Metric: Unlike shortest paths, effective resistance considers all possible paths between nodes. Mathematically, it is a negative type metric, making it a "safe" and robust choice for network statistics.

Key Results

  • Mathematical Guardrails: The paper establishes the strict criteria ($W$ must be positive definite on $\text{span}(1)^\perp$) required for any future network correlation measure.
  • Proof of Bounds: Using the Cauchy-Schwarz inequality, the authors prove that as long as $W$ meets the new criteria, the network correlation will always fall within the interpretable range of $[-1, 1]$.
  • Practical Alternatives: The authors successfully demonstrate that replacing shortest paths with effective resistance or Euclidean distances resolves the issues in both the toy $K_{2,3}$ graph and the large-scale Twitter network.

Limitations and Future Work

  • Computational Complexity: While effective resistance is mathematically superior, calculating it for extremely large graphs (millions of nodes) can be computationally expensive compared to simple shortest paths.
  • Parameter Sensitivity: The formula uses a scaling factor $k$. While the paper proves the correlation is well-defined for any $k > 0$, it doesn't explore how different values of $k$ change the "sensitivity" or interpretation of the correlation in practical applications.
  • Embedding Choice: For node embeddings, the result depends on the specific embedding algorithm used (e.g., DeepWalk). Since many of these are stochastic, the resulting correlation might not be perfectly deterministic unless a fixed embedding is used.

Summary updated

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.
BibTeX
@misc{coscia2024pearson,
  author = {Michele Coscia and Karel Devriendt},
  title = {{Pearson Correlations on Networks: Corrigendum}},
  year = {2024},
  eprint = {2402.09489},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2402.09489},
}
Figure