6
$\begingroup$

I am working on a computational project involving analysis of data. Each item of data that I have has a few hundred attributes; I have several million items of data. The attributes are essentially random variables and I am computing the correlation of each pair of variables. The formula to do that is:

$$ \rho_{xy} = \frac{\mathbb{E}( (X-\mu_{x})(Y-\mu_{y}) )}{\sigma_{x}\sigma_{y}}$$

where $X$ and $Y$ are the attributes. This value always lies between $+1$ and $-1$. Intuitively, if $\rho_{xy}\approx +1$ then $X$ and $Y$ typically differ from their respective means in the same way, i.e. if $X$ is above average then so is $Y$ and if $X$ is below average, then so is $Y$. This is called positive correlation. Similarly, if $\rho_{xy}\approx -1$ then $X$ and $Y$ typically differ from their means in opposite directions, i.e. if $X$ is above average, then $Y$ is below and vice versa. This is called negative correlation.

From all of my data, I build a correlation matrix $C=[\rho_{ij}]$ which contains the correlation coefficient of the $i^{\text{th}}$ and $j^{\text{th}}$ variable in the $ij$-entry. I want to view this matrix as an edge-weighted graph and perform clustering. A "positive" clique would correspond to a number of pairwise positively correlated variables. It is clear that many variables can be pairwise positively correlated; so I could potentially see large "positive" cliques in the graph.

My question is: How many variables could I see that are pairwise negatively correlated? Intuition tells me probably only 2. But I cannot prove this. Basically, I want to define "negative" cliques--a set of nodes all of whose edges are weighted with (nearly) $-1$, and I want to know how large my "negative" cliques could be.

Edit: Perhaps a better way to ask the question is: to what degree can "anti-correlation" be transitive? I.e. if $x$ is (strongly) anti-correlated to $y$, and $y$ is (strongly) anti-correlated to $z$, how strongly can $x$ and $z$ be anti-correlated?

Also, if there is a way to say how large this "negative" clique could be as a function of how near the edge weights are to $-1$ that would be helpful. The idea that there largest negative clique has 2 vertices is working on the assumption that I only have an edge when the weight is exactly $-1$. If I relax that to an edge when the weight is smaller than $-1+\epsilon$ (small $\epsilon$) then I can probably have slightly more than 2 vertices--how many more is the question (and how does that related to $\epsilon$).

$\endgroup$
  • $\begingroup$ Let's say that you have 100 attributes and that there are 50 pairs of linear relationships within those attributes. Couldn't all 50 lines have a negative slope? $\endgroup$ – MaxW Nov 4 '15 at 16:16
  • $\begingroup$ @MaxW, it is not so much the 50 pairs from 100 attributes. The question is more about transitivity: if $x$ and $y$ are anti-correlated (when $x>\mu_{x}$ then $y<\mu_{y}$, and vice versa) and $y$ and $z$ are anti-correlated (when $y>\mu_{y}$ then $z<\mu_{z}$), then can $x$ and $z$ be anti-correlated? Maybe not, since $x>\mu_{x}$ implies that $y<\mu_{y}$ and this implies that $z>\mu_{z}$ implying that $x$ and $z$ are positively correlated. $\endgroup$ – TravisJ Nov 4 '15 at 21:07
  • $\begingroup$ @MaxW, I am aware that there may be many pairs of anti-correlated variables. The question is: given a group of more than two attributes, can every pair of those attributes be anti-correlated? $\endgroup$ – TravisJ Nov 4 '15 at 21:09
  • $\begingroup$ Are you assuming some lower bound on the variances of the random variables? For instance as the variance tends to zero the correlation coefficient blows up and the problem becomes ill-defined. Once you've made such an assumption on the variance, you may be able to reduce to the case that all variances are the same. Then by shifting and scaling you can assume that all the random variables have mean 0, variance 1. This should ease some of the computations. $\endgroup$ – pre-kidney Jul 31 '16 at 7:28
  • 1
    $\begingroup$ Geometric intuition is somewhat reinforced by the following thought experiment involving three gaussians that we can individually assume to have $\mu=0,\sigma=1$ by adjusting the scales linearly. If they have pairwise correlations $-\rho$, then their joint pdf would have the form $$C_1e^{-C_2xAx^T}$$ for some positive constants $C_1,C_2$ and a matrix $$A=\pmatrix{1&-\rho&-\rho\cr-\rho&1&-\rho\cr-\rho&-\rho&1\cr}.$$ The eigenvalues of $A$ are then $1-2\rho,1+\rho,1+\rho$. All these need to be positive implying $\rho<1/2$. With more than three variables it becomes even more difficult. $\endgroup$ – Jyrki Lahtonen Jul 31 '16 at 7:52
6
+100
$\begingroup$

We can simplify the set-up a little by translating the variables to have mean $0$, and scaling them to have standard deviation $1$. If we label the variables $X_1, X_2, ..., X_m$, then we have $\rho_{ij} = \mathbb{E}[X_i X_j]$. Moreover, the normalisation gives $\mathbb{E}[X_i^2] = 1$ for every $i$.

Now suppose you consider a pair of variables to be strongly anticorrelated if $\rho_{ij} \le - \rho$ for some $0 < \rho \le 1$. Moreover, suppose $X_1, X_2, ..., X_k$ form a clique of strongly anticorrelated variables. We shall now bound $k$ in terms of $\rho$. We have $$ 0 \le \mathbb{E} \left[ \left( \sum_{i=1}^k X_i \right)^2 \right] = \mathbb{E} \left[ \sum_{i=1}^k X_i^2 + \sum_{i \neq j} X_i X_j \right].$$

Using linearity of expectation, $$ 0 \le \mathbb{E} \left[ \sum_{i=1}^k X_i^2 + \sum_{i \neq j} X_i X_j \right] = \sum_{i=1}^k \mathbb{E} \left[ X_i^2 \right] + \sum_{i \neq j} \mathbb{E} \left[ X_i X_j \right]. $$

We have $\mathbb{E} [X_i^2] = 1$ for all $i$, and by assumption $\mathbb{E}[X_i X_j] \le - \rho$, so $$ 0 \le \sum_{i=1}^k \mathbb{E} \left[ X_i^2 \right] + \sum_{i \neq j} \mathbb{E} \left[ X_i X_j \right] \le k - k(k-1)\rho.$$

In particular, $k(k-1)\rho \le k$, which can be solved to give $$ k \le 1 + \frac{1}{\rho}. $$

Hence, if $\rho$ is close to $1$, then as you suspected, you cannot have three pairwise-strongly-anticorrelated variables. In order to have such a set of three variables, you need $\rho \le \frac12$, as suggested in Jyrki's comment. More generally, I believe the following set of variables with $k$ attributes (additional attributes can be set to $0$ if needed) shows the bound is sharp: $$ X_1 = \begin{pmatrix} k-1 \\ -1 \\ -1 \\ \vdots \\ -1 \end{pmatrix}, X_2 = \begin{pmatrix} -1 \\ k-1 \\ -1 \\ \vdots \\ -1 \end{pmatrix}, ..., X_k = \begin{pmatrix} -1 \\ -1 \\ -1 \\ \vdots \\ k-1 \end{pmatrix}. $$ Here we have $k$ variables with $\rho_{ij} = \frac{-1}{k-1}$ for all $i \neq j$. Thus $\rho = \frac{1}{k-1}$, and the bound shows we cannot have more than $k$ such variables.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.