Sparse Covariance Neural Networks

Authors: Andrea Cavallo, Zhan Gao, Elvin Isufi
Primary area: learning theory
Keywords: Principal Component Analysis, Stability property, Covariance Neural Networks, Graph sparsification

Abstract:
Covariance Neural Networks (VNNs) perform graph convolutions on the covariance matrix of tabular data and achieve success in a variety of applications. However, the empirical covariance matrix on which the VNNs operate may contain many spurious correlations, making VNNs’ performance inconsistent due to these noisy estimates and decreasing their computational efficiency. To tackle this issue, we put forth Sparse coVariance Neural Networks (S-VNNs), a framework that applies sparsification techniques on the sample covariance matrix before convolution. When the true covariance matrix is sparse, we propose hard and soft thresholding to improve covariance estimation and reduce computational cost. Instead, when the true covariance is dense, we propose stochastic sparsification where data correlations are dropped in probability according to principled strategies. We show that S-VNNs are more stable than nominal VNNs as well as sparse principal component analysis. By analyzing the impact of sparsification on their behavior, we provide novel connections between S-VNN stability and data distribution. We support our theoretical findings with experimental results on various application scenarios, ranging from brain data to human action recognition, and show an improved task performance, stability, and computational efficiency of S-VNNs compared with nominal VNNs.

Decision: reject
Reviewer scores: 1, 3, 3, 5

Reviews and discussion:
<thread>
creation date:
1730630577522

thread_type:
official_review

<thread_object>
creator: reviewer_rryr

<content>
summary:
This paper studies the sparsification strategy upon the spurious correlation and computation efficiency issues for the covariance matrix used in the coVariance Neural Networks (VNN), which is more stable than the Principal component analysis (PCA) methods in the previous studies. This paper proposes hard and soft thresholding strategies if the true covariance matrix is sparse, and two stochastic sparsification techniques, including Absulute covariance values (ACV) and Ranked covariance values (RCV) when the covariance matrix is dense, and theoretically analyze the sparsification error and covariance uncertainty for the stability of VNN. The effectiveness of sparsity techniques is validated through synthetic and real datasets in contrast to the dense-VNN and sparse-PCA on the performance and computational time.

strengths:
Quality: The paper is well-written, the motivation sounds reasonable, and the proposed sparsification strategies seem good with a theoretical analysis of the stability.
Originality: The paper proposes several sparsification strategies to tackle the spurious correlation and computation cost issues for the VNN. Although the theoretical analysis of the stability of VNN is good, the originality of the proposed solutions is limited. 
Significance: Spurious correlation and sparsity techniques are important.

weaknesses:
The novelty of the proposed strategies is limited, similar strategies have been used in the study of neural networks like dropout or pruning, and the current results are not enough strong.

questions:
Although current results can validate the effectiveness of the proposed strategies, the results should be compared with the covariance with sparsity regularizer, not just dense-VNN and robust-PCA.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730668771483

thread_type:
official_review

<thread_object>
creator: reviewer_ksmg

<content>
summary:
This paper presents a sparse version of covariance neural networks (VNNs), showing that the sparse-VNNs are more stable than nomial VNNs and sparse component analysis.

strengths:
The presentation of the paper is clear.

weaknesses:
1. It is well known that the covariance matrix is not invariant to the scale of the data, making it impractical to set a common threshold for different elements of c_{ij}. Thus, the rationale behind Definition 2 is difficult to justify.

2. From a sparsity perspective, the elements c_{ij}'s should be classified into two categories: zero and nonzero. However, this key point is obscured in Theorem 2, making the results difficult to interpret. In other words, it is challenging to justify that the proposed method effectively denoises the data.

3. The contribution of the paper appears incremental in light of the existing work by Sihag et al. (2022).

questions:
1. See weakness. 

2. Additionally, using t to represent the sample size is somewhat unusual to me, though this is merely a notation issue.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730766163170

thread_type:
official_review

<thread_object>
creator: reviewer_9p73

<content>
summary:
**Summary:**
Graph convolutions on the covariance matrix of tabular data are performed by a architecture called Covariance Neural Networks (VNNs). These rely an empirical estimates of the covariance matrix, which is notoriously difficult. The authors propose Sparse VNNs, which sparsifies the covariance matrix before convolution is applied. This is advantageous when the true covariance is sparse, and also when the true covariance is dense, and different techniques are investigated. S-VNNs are compared against VNNs and PCA. Experiments are provided on brain data and human action reconition, showing performance, sensitivity and efficiency benefits over VNNs.

strengths:
**Strengths:**
- The proposed architectures come with apparent theoretical guarantees on the closeness of hidden representations or predictions when applied to the approximate versus true covariance matrices. These distances become smaller as the number of samples increase, at a rate of $\mathcal{O}(t^{-1/2})$, ignoring some parameter-dpendent constants.
- Experiments are provided showing the predictive performance and stability of the proposed methods. This experiments agree with the theory, and nicely demonstrate the approach. 
- A very large amount of related literature is cited, and this seems appropriate.
- The theory appears to be mostly sound, roughly based on a Lipschitz assumption. (although there are some isolated places where precision could be improved, see weaknesses below).

weaknesses:
**Weaknesses:**
- Comparing Lemma 1 and Thoerem 1. I am guessing (please correct me if I am wrong!) that somehow hidden inside $\mathcal{O}$ in Theorem 1 are the parameters $\mathcal{H}$. Intuitively, these should learn something similar to PCA, and if the eigenvalues of PCA are close, this constant term in $\mathcal{O}$ will be bad but in terms of $\mathcal{H}$. In Lemma 1, the constant term in terms of the small gap eigenvalues is explicitly given, and it is obvious how this causes instability. Whether my guess about Theorem 1 is correct or not, the authors should state either way about the possibility of dependent of $\mathcal{H}$ on the factors in $\mathcal{O}$. Right now the claim that " VNNs do not suffer from this as the covariance filter can exhibit a stable response to close eigenvalues at the expense of lower discriminability" is not clear, as are similar repeated claims throughout the paper. It seems as though this is also an important consideration for later derived theoretical results (Theorem 2, Proposition 1, ...). **This is my most major important concern.**
- Theorem 1 explicitly writes the probability of the event. The later results only state with high probability. What does with high probability mean?
- In definition 3, how does one ensure that the resulting soft-thresholded matrix is PSD? 
- In definition 4, how does one ensure that the matrix is PSD after dropout? 
- What happens when the true data distribution is heavy tailed, and does not have a (finite) covariance matrix? I guess there should be some condition in the theoretical results, which is currently absent, on the distribution of $x$. In Theorem 1 a Gaussian distribution is used (which has finite variance), and it is not clear in the presentation of later results if a Gausssian is also being used. 
- It is claimed that "For sparse covariance, ... the hard thresholding improves stability." According to my understanding, the authors are able to derive bounds which are tighter for sparse covariances than for dense covariances with hard thresholding. This does not necessarily show that hard thresholding definitively improves stability, only the bound is tighter. If I have understood correctly, perhaps the authors should rephrase their claim (otherwise, am happy to be corrected).



**Minor:**
- I don't understand one sentence in Theorem 1. "Consider a generic data sample $x \sim \mathcal{N} (0, C)$ such that $\Vert x \Vert \leq 1$". Does this mean $x$ is drawn from the conditional distribution obtained by conditioning a Gaussian random vector on the event that the norm is less than or equal to 1? I believe this should be phrased better, in terms of the distribution x is actually drawn from. (I understand this is from another paper, but still it would be nice to improve clarity here).
- Incorrect grammar for paragraph starting line 167/168.
- Limitations of PCA in terms of unstable or poor estimation of eigenvalues is discussed. Do the authors know where does this fit into more robust variants of PCA, exponential family PCA, kernel PCA, etc.? Do such advanced variants of PCA overcome these issues? Either way, it would be nice to mention in the discussion in a sentence around line 39/40.

questions:
Please address each of the weaknesses above. In particular:
- In Theorem 1 and related results, is it true that $\mathcal{O}$ hides dependence on $\mathcal{H}$, which as in the case of PCA, could be arbitrarily bad?
- What does with high probability mean exactly?
- How are matrices ensured to be PSD?
- What happens in the case of undefined / infinite variance? How should this be reflected in the theorems? Is a Gaussian assumption on x used throughout, or only in the first result?
- Does the theoretical result really show a guaranteed improvement in stability? Or does it only fail to show a decrease in stability?
- Please clarify whether $x$ is drawn from an (unconditional) Gaussian or from a "truncated" Gaussian conditioned on its norm.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730770285591

thread_type:
official_review

<thread_object>
creator: reviewer_g6qo

<content>
summary:
This paper builds upon covariance neural networks, which are constructed to process covariance matrices. The authors study the impact of sparsifying the covariance matrix with hard or soft thresholding before feeding it to the network. They demonstrate that this improves the estimation when the true covariance matrix is sparse, and explain how to drop coefficients at random when it is not the case. The authors demonstrate some improvements compared to no thresholding in several experiments.

strengths:
- The idea of sparsifying the covariance before feeding it to the network is sound.

weaknesses:
- This paper is very hard to follow. Several variables are not defined ($V$, $u$, $u_g$, $h_{klfg}$, etc...). Several concepts must be guessed from the text (what are the covariance filters? how does $u$ relate to the $u_g$ in eq. 1? what are the per covariance filters in theorem 1?). Overall, it is hard to understand this paper alone without reading the original paper on covariance neural networks. This paper needs a major rewriting before being ready for publication, which explains my note.
- The novelty is minor. This paper builds upon covariance networks, which are seldom used in practice, and incrementally improves on them by pre-processing the covariances.

questions:
- How can we know in practice if the covariance of the dataset is sparse?
- How does $\nu$ in thm.1 depends on the data distribution? I only see one data distribution, which depends only on $C$, so $\nu$ is only a function of $C$?
- In def. 1, is it for a fixed matrix? In which set do the eigenvalue pairs $\lambda_i, \lambda_j$ belong? This is unclear.
- Is lemma 1 an original result? If not then a citation is needed here.
- Should $F_{in} = F_{out}$ in (1)? since it seems like $u^l$ is both of size $F_{out}$ and $F_{in}$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732109196683

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We wish to thank the reviewers for their effort in reading and analyzing our paper. We are happy to notice that the following strengths of our work have been appreciated:
- The theoretical analysis of the model stability is sound (reviewers rRYr, 9p73)
- The problem of reducing the impact of spurious correlations and improving computational efficiency is significant and our covariance sparsification techniques solve it with theoretical guarantees and experimental evidence (reviewers G6qo, 9p73, rRYr)
- The paper is well-written (reviewers KsmG, rRYr), although some clarifications are needed as we detail in the rebuttals to reviewers 9p73 and G6qo, that we thank for pointing out these unclear passages

Overall, we notice that the weaknesses listed by the reviewers fall under two main categories:
- The first one is related to misunderstandings due to condensed formulations and explanations to fit the page limit. We have addressed these in each specific rebuttal and clarified them in the revised manuscript.
- The second concern, shared by reviewers G6qo, KsmG, rRYr, relates to the novelty of the paper. We would like to present here our motivations why we believe that the contributions of this paper are significant and impactful, not merely incremental.


**Significance of covariance neural networks.** 
VNNs [1] are receiving increasing attention [12,13,14,15,16], which makes them an important and relevant topic to study. Furthermore, the VNNs defined in [1] represent a general framework that encompasses several methods commonly applied in practice; indeed, estimating a graph from data correlations and applying a GNN on it is extremely common in fields such as brain connectivity estimation [5,6], financial data processing [7,8] and human action recognition [9,10]. Therefore, the proposed sparsification mechanism of the VNNs can be applied to all these methods for computation reduction and performance improvement in challenging scenarios.


**Significance of sparse settings.**
The problem of estimating a covariance matrix in low-sample regimes, potentially in a sparse setting, is notoriously difficult, and in several cases the basic sample covariance estimator provides very noisy estimates [2,3,4], which hinders the performance of the original VNN in [1]. Since sparsifying the covariance matrix of the data has been shown capable of improving estimation accuracy [2,3,4], and in various applications the data correlations are generally sparse [6,7,8,9,10], we propose sparse covariance neural networks (S-VNNs) that leverage sparsification mechanisms to improve the VNN performance and, in the meantime, enhance the stability and reduce the computation. These findings are corroborated in our experiments in both synthetic and real data.

**Significance of stability analysis.** 
Although it is known that the sparsification mechanism has the potential to improve the estimation accuracy of the covariance matrix, its explicit impact on the VNN stability is unknown. Therefore, in addition to proposing S-VNNs, we perform stability analysis to characterize the impact of different sparsification mechanisms on the VNN outputs. The results show that S-VNNs achieve stability to covariance perturbations with a smaller bound compared with the original VNN (see Theorems 2 and 3), and suggest which sparsification to apply based on the problem setting and desired stability. This stability analysis is non-trivial. Indeed, the thresholded covariance estimators in Section 3 do not allow to use convergence results in [17], which are at the basis of the proof in the VNN paper [1], thus calling for a reformulation of the proof. Moreover, the stochastic sparsification in Section 4 requires generalizing the concepts of covariance filter frequency response and integral Lipschitz condition to the case of stochastic filters (see Section 4.1) and extending the stability of GNNs to stochastic perturbations in [11] to the case in which edges are dropped with different probabilities, which is not considered in [11] and significantly changes the problem setting.

**Conclusion**
We believe to have addressed the concerns of the reviewers related to unclear passages in the text, and we hope that our work's contributions are now more clear and evident. We remain available for further questions and discussion.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper proposes Sparse coVariance Neural Networks (S-VNNs), built upon previous work on VNNs, which applies sparsification techniques on the sample covariance matrix before convolution. When the true covariance matrix is sparse, hard and soft thresholdings are proposed to improve covariance estimation and reduce computational cost. When the true covariance is dense, stochastic sparsification is proposed, where data correlations are dropped in probability according to principled strategies. The proposed method is accompanied by numerical experiments.

While reviewers appreciate that the idea of sparsifying the covariance matrix before convolution is sound, they also have concerns about the limited novelty compared to prior work, the weakness of the theoretical results, and the quality of presentation of the current manuscript (see further below).