Given an adjacency matrix, how can we fit a covariance matrix based on that for a graph without running into a NON-positive definite matrix?

Question

Suppose that I generate a k-regular graph like the following:

game <- sample_k_regular(k, r)
game <- as.matrix(as_adj(game))

Then, based on this adjacency matrix, suppose I replace the $1$'s with a correlation parameter $\rho$ and replace all the $0$'s in the diagonal with $1$. Then, this is a covariance matrix for something that is like a multivariate normal. However, this way of creating a matrix results in a NON-positive definite matrix. Is there a way to create a covariance matrix structure based on an adjacency matrix based on putting a correlation parameter $\rho$ where there are ties and $1$'s in the diagonal for a common variance? In other words, is there a way to create covariance matrices without running into the positive definiteness problem? Thanks.

Answer 1

Yes, for example if you choose $\rho$ small enough to ensure that your matrix is strictly diagonally dominant, then it is guaranteed to be positive definite. In this case "small enough" means $|\rho|<1/r$, where $r$ is the valency of the regular graph.

But possibly you do not want to choose $\rho$ so small. A useful thing to remember here is that a symmetric matrix is positive definite if and only if its eigenvalues are all positive. And since you are constructing your matrix as $$ M = I + \rho A$$ where $A$ is the adjacency matrix of the graph, it follows that the eigenvalues of $M$ are of the form $1+\rho\lambda$ as $\lambda$ ranges over the eigenvalues of $A$. So if you have a particular $\rho>0$ in mind, then the graphs that will work are precisely those for which all eigenvalues (of the adjacency matrix) satisfy the bound $\lambda > -1/\rho$. In other words, you need graphs whose negative eigenvalues aren't too large in magnitude. Note that for a regular graph with valency $r$, all its eigenvalues satisfy $|\lambda| \leq r$, which leads to the same sufficient condition $|\rho| < 1/r$ described above.

There is quite a bit of information available about graphs whose most negative eigenvalue isn't too large in magnitude; this falls within the subject of spectral graph theory. In particular, the problem of characterizing graphs whose eigenvalues satisfy $\lambda \geq -2$ is treated in the book Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2. It contains the following result, showing that with fairly trivial exceptions the bound $\lambda\geq -2$ is the best that we can hope for a regular graph to satisfy:

Corollary 2.3.22. If G is a connected regular graph with least eigenvalue greater than −2 then G is either a complete graph or an odd cycle.

There are methods of constructing broad families of regular graphs which attain this bound, i.e. whose least eigenvalue is -2. The most basic one is the construction of a line graph. If you start with any graph $G$, you can construct a new graph $L(G)$, whose vertices correspond to the edges of $G$ and whose edges correspond to edge-incidences of $G$. This graph $L(G)$ is called the line graph of $G$, and it is guaranteed that its eigenvalues satisfy $\lambda \geq -2$, no matter which graph $G$ you start with. Moreover, if you start with a regular graph $G$ with valency $r$, then $L(G)$ will also be regular, with valency $2(r-1)$. This gives you a way to construct regular graphs for which you can take $\rho$ to be any value satisfying $|\rho|<1/2$ and end up with M being positive definite. In light of the result cited above, this is the best that is possible, unless you want to go with a complete graph (which allows $\rho$ to be arbitrarily close to 1) or an odd cycle (which allows $\rho$ to be a little larger than $1/2$, but by an amount which approaches zero as the size of the cycle increases), or a disjoint union of complete graphs and odd cycles.

If it is unsatisfactory to restrict to regular graphs with even valency, it's worth noting that you don't have to start with a regular graph $G$ in order for $L(G)$ to be regular. For instance, you could instead start with $G$ being a semiregular bipartite graph, where one of the two valencies is even and the other is odd, and this would result in $L(G)$ being regular with odd valency.

Answer 2

Here is an explanation which might provide some intuition about what is going on here. Suppose that in your graph you have three vertices where vertex 1 is adjacent to both vertices 2 and 3, but vertices 2 and 3 are not adjacent to each other. Let $X_1$, $X_2$, and $X_3$ be the corresponding random variables being modeled. In this case you are wanting to have \begin{align*} \text{Corr}(X_1,X_2) &= \rho \\ \text{Corr}(X_1,X_3) &= \rho \\ \text{Corr}(X_2,X_3) &= 0 \end{align*} There is some tension here, in the sense that these requirements become incompatible with each other as $|\rho|$ grows too large. Namely, if $X_1$ is strongly correlated with both $X_2$ and $X_3$, then at a certain point it is no longer possible for $X_2$ and $X_3$ to be uncorrelated with each other. In other words, there is some degree of transitivity that holds with correlations. This is quantified in general here, and in particular it can be shown that for $|\rho|>1/\sqrt 2$, the above conditions are incompatible. And as the other answer shows, in practice you will run into trouble even sooner, namely at the point $|\rho| \geq 1/2$, even for carefully chosen families of graphs.

An alternative approach would be to relax the constraint that the non-adjacent variables have exactly correlation 0. A natural way to do this is to change our focus away from directly modeling the covariance matrix $\Sigma$, to instead modeling the precision matrix $\Lambda = \Sigma^{-1}$. Namely, we model $\Lambda$ in basically the same way that we were modeling $\Sigma$ before: $$\Lambda = I - \rho A$$ where $A$ is the adjacency matrix of the graph. Here $\rho$ no longer represents the correlation between neighboring variables; instead it represents their partial correlation, after controlling for all the remaining variables. To ensure that $\Lambda$ is positive definite (which is equivalent to $\Sigma$ being positive definite), we need to impose the restriction $|\rho| < 1/r$, where $r$ is the valency of the (regular) graph. Although this restriction may appear superficially similar to the crude sufficient condition $|\rho| < 1/r$ that arises when modeling $\Sigma$ directly, the situation here is completely different. This time, as $\rho \to 1/r$ the random variables approach correlation 1 with one another (in each connected component of the graph), and we could not ask for more than that.

An example might help illustrate how this works. Consider the cycle graph on 10 vertices. Because of the symmetry of the graph, the value of the $(i,j)$ entry of $\Sigma$ only depends on the distance between vertices $i$ and $j$, so we can concisely summarize the resulting correlations for various choices of $\rho$:

\begin{array}{lllllll} \text{Distance}& 0& 1& 2& 3& 4& 5& \\ \rho = 0& \text{1}& \text{0}& \text{0}& \text{0}& \text{0}& \text{0}& \\ \rho = 0.1& \text{1}& \text{0.101}& \text{0.01021}& \text{0.001031}& \text{0.0001052}& \text{2.104e-05}& \\ \rho = 0.4& \text{1}& \text{0.5015}& \text{0.2537}& \text{0.1327}& \text{0.07805}& \text{0.06244}& \\ \rho = 0.49& \text{1}& \text{0.865}& \text{0.7654}& \text{0.697}& \text{0.657}& \text{0.6439}& \\ \rho = 0.499& \text{1}& \text{0.9826}& \text{0.9691}& \text{0.9596}& \text{0.9538}& \text{0.9519}& \\ \rho = 0.4999& \text{1}& \text{0.9982}& \text{0.9968}& \text{0.9958}& \text{0.9952}& \text{0.995}& \\\end{array}

Here the correlations shown in the table are defined by $\Sigma_{ij}/\sqrt{\Sigma_{ii}\Sigma_{jj}}$ where $\Sigma$ is given by $$\Sigma = \Lambda^{-1} = (I - \rho A)^{-1}$$ Again, the idea here is that even though non-neighboring variables are now correlated with each other, this correlation is only due to the mutual influence of neighbors connecting them. In the case of a multivariate Gaussian distribution this can be made more precise, as then each variable satisfies the Markov property that, given its direct neighbors, it is conditionally independent of all the non-neighboring variables (e.g., see here).

Answer 3

For the special case of precision matrixes $K = \Sigma^{-1}$, some approaches tend to use the condition number theory (Article Condition number on Wikipedia). It helps to find a constant by which diagonal elements can be multiplied when the obtained matrix is not positive defined. The graph2prec function in SpiecEasi (Sparse and Compositionally Robust Inference of Microbial Ecological Networks, Zachary Kurtz et al. 2015) R package implements that. Others are based on the laplacian matrix. The rNetwork function in simone(SIMoNe: Statistical Inference for MOdular NEtworks, Julien Chiquet et al. 2009) R package implements that.