Sparse Covariance Neural Networks

We thank the reviewer for their analysis. We respond to the comments in the following.

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.

We refer the reviewer to the general comment of the rebuttal, where we reiterate the relevance of our contributions. Mostly, our contributions do not lie only in the proposed sparsification strategies, but also in their theoretical connection with VNN stability, which is new and unexplored.

Furthermore, our approach is different from dropout and pruning techniques, since the latter remove neural network weights to increase efficiency or prevent overfitting. We, instead, consider the sparsification of the covariance matrix, but the number of neural network weights stays the same. There exist graph sparsification approaches akin to dropout (e.g., [3,4]), which we discuss briefly in our Related Works, but they mainly focus on oversmoothing or expressivity, meanwhile our focus is on stability and computation efficiency.

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.

We are not sure what the reviewer refers to with "covariance with sparsity regularizer", since the thresholding techniques in Def. 2,3 can also be interpreted as sparsity regularizers. If the reviewer refers to covariance estimation strategies that enforce sparsity in the objective function of the covariance estimation problem (e.g., [1,2]), we opted for not including them as they might incur in the significant overhead of solving an optimization problem, thus defeating the purpose of increased time and computation efficiency. Furthermore, it might be harder to theoretically characterize the impact of these sparsity strategies on the VNN behavior.

Conclusion

We hope to have made the relevance of our contributions more clear, and we remain available for further discussion.

References

[1] Bien et al. Sparse Estimation of a Covariance Matrix, Biometrika 2011.

[2] Friedman et al., "Sparse inverse covariance estimation with the graphical lasso", Biostatistics, 2008.

[3] Pál András Papp, Karolis Martinkus, Lukas Faber, and Roger Wattenhofer. Dropgnn: Random dropouts increase the expressiveness of graph neural networks. Advances in Neural Information Processing Systems, 2021.

[4] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.

We thank the reviewer for analyzing our paper. We address the comments in the following.

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.

While this is true for unscaled data, in practice it is very common to rescale data to feature-wise unit variance before applying machine learning techniques, which allows to set a common threshold for different elements. The hard and soft thresholding in Def. 2,3 are also common in related works [1,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.

The definition of the sparse covariance class $\mathcal{C}$ in Thm. 2 considers matrixes with at most $c_0$ non-zero elements in each row. Sparsifying the estimate through thresholding reduces the number of non-zero elements according to the threshold, which leads to better estimates as shown in [1,2].

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

We refer the reviewer to our general comment, where we reiterate why we believe our contribution to be more than incremental.

Conclusion

We believe to have effectively addressed the concerns of the reviewer about the weaknesses 1 and 2, and we hope that the relevance of our contributions are more clear through our general comment. We remain available for further discussion.

References

[1] Peter J Bickel and Elizaveta Levina. Covariance regularization by thresholding. The Annals of Statistics, 2008.

[2] Yash Deshpande and Andrea Montanari. Sparse pca via covariance thresholding. Journal of Machine Learning Research, 2016.

We wish to thank the reviewer for the comments on our paper. We regret to see that our contributions have not been appreciated, and we hope to make them more explicit and effectively address the reviewer's concerns in the following.

Weakness 1: the paper is hard to follow

We believe this weakness is due to some notation conventions that are common in some related works [1,2,3], but might lead to confusion. We have taken care of clarifying the meaning of each variable in the revised manuscript. More precisely:

• Several variables are not defined ($\mathbf{V}, \mathbf{u}, \mathbf{u_g}, h_{klfg}$, ... ). We have defined all these variables in the revised manuscript. In particular, $\mathbf{V}=[\mathbf{v}\_0,...,\mathbf{v}\_{N-1}]$ contains the eigenvectors of the true covariance matrix. We modified eq. (1) to clarify that $\\{\mathbf{u}^{l}\_f\in\mathbb{R}^{N}\\}\_{f=1}^{F\_l}$ are the outputs of the $l$-th VNN layer, each produced by the $f$-th covariance filter bank. This filter bank is composed of $F_{l-1}$ covariance filters, each processing the signals at the previous layer $\\{\mathbf{u}\_g^{l-1}\in\mathbb{R}^{N}\\}\_{g=1}^{F\_{l-1}}$ separately. At the first layer, we have $\\{\mathbf{u}\_g^0 = \mathbf{x}\_g\\}\_{g=1}^{F\_0}$ where $F_0$ is the node feature size. $h_{klfg}$ are the network learnable parameters for the $k$th order, $l$th layer, $g$th input signal and $f$th filter output in eq. (1).

• What are the covariance filters? We have defined covariance filters in line 88 of the original manuscript (line 86 in the revised one).

• How does $\mathbf{u}$ relate to $\mathbf{u_g}$ in eq. 1? We have clarified this in the answer above.

• What are the per covariance filters in theorem 1? The covariance filters in Theorem 1 are those defined in eq. (1) at each layer, which compose a VNN.

Weakness 2: minor novelty

We refer the reviewer to the general comment of this rebuttal, in which we reiterate our contributions and novelty. Specifically, in the section "Significance of covariance neural networks" we point out why VNNs are not "seldom used in practice", as they represent a general framework which encompasses several methods that commonly applied in practice.

Questions

• How can we know in practice if the covariance of the dataset is sparse? The sparsity of the covariance matrix is a common and reasonable assumption in a variety of applications. For example, in brain signal processing, it is known that only some areas of the brain activate simultaneously for different tasks, which leads to sparse correlations [7]. In financial data, only some stocks are affected by similar factors and therefore present analogous variations, which again leads to sparse correlations [8]. In all these cases, the sample covariance matrix might still be dense due to spurious correlations, which hinder the quality of the VNN performance and motivate the proposed S-VNN. Furthermore, even in other cases in which it is difficult to assume covariance sparsity a priori, the improved performance of sparsity-based regularizers leads to a belief that it is a good assumption [4,5]. We have clarified this aspect in the revised manuscript.

• How does $\nu$ in thm.1 depends on the data distribution? I only see one data distribution, which depends only on $\mathbf{C}$, so $\nu$ is only a function of $\mathbf{C}$? We thank the reviewer for pointing out this inconsistency. The assumption that $\mathbf{x}$ is Gaussian is actually not needed for the proof and we have removed it from the revised manuscript. The relation between $\nu$ and the data distribution is analyzed in [1] and we did not report details in our paper as it is not the focus of our analysis. Briefly, $\nu$ relates to the kurtosis of the data distribution, which in turns relates to the tail of the covariance eigenvalues distribution.

• In def. 1, is it for a fixed matrix? In which set do the eigenvalue pairs $\lambda_i,\lambda_j$ belong? This is unclear. We have clarified in the revised manuscript that the Lipschitz condition is for any $\lambda_i, \lambda_j \in [0,\lambda_\textnormal{max}], \lambda_i \neq \lambda_j$, where $\lambda_\textnormal{max}$ identifies a suitable range in which the covariance eigenvalues lie and can be application-specific (e.g., $\lambda_\textnormal{max}=1$ in case the covariances are normalized by their largest eigenvalue).

• Is lemma 1 an original result? If not then a citation is needed here. Lemma 1 is an original result derived based on the results in [1] and [6], so we did not report a citation for it.

• Should $F_{in}=F_{out}$ in (1)? since it seems like $u^l$ is both of size $F_{out}$ and $F_{in}$.

We clarified this aspect by replacing $F_{in}, F_{out}$ in eq. (1) with $F_{l-1}, F_{l}$, i.e., the embedding sizes at the $l-1$ and $l$-th layer. $F_{l-1}$ can be different from $F_{l}$.

We thank the reviewer for the thorough comments provided on our work. We address them in the following.

Where are the parameters $\mathcal{H}$ in the stability bound?

The parameters $\mathcal{H}$ are filter coefficients that determine the frequency response of the covariance filter (lines 167-171). Shortly, the operation of the covariance filter can be modeled by a polynomial of the covariance eigenvalues $\lambda$ in the spectral domain, where $\mathcal{H}$ are the polynomial coefficients. The variability of the filter frequency response is bounded by the Lipschitz constant $P$ as per Def. 1. Therefore, the filter coefficients $\mathcal{H}$ as well as the eigenvalue gap $\min_i|\lambda_i-\lambda_{i+1}|$ are "absorbed" by the Lipschitz constant $P$ in Thm. 1 and they are not in the term within $\mathcal{O}$.

This leads to a similar expressivity vs stability tradeoff as that in GNNs [1]. A larger $P$ allows for a more expressive polynomial with larger variability for close eigenvalues, but corresponds to more different responses when the input is perturbed, while a smaller $P$ guarantees close responses in case of perturbations but lowers the model expressivity.

Theorem 1 explicitly writes the probability of the event. The later results only state with high probability. What does with high probability mean?

We thank the reviewer for pointing this out. The bounds in Thm. 2 and 3 hold stochastically, i.e., with a probability $1 - o(1)$ where $o(1)$ gets smaller as the number of data samples $t$ increases. We do not provide an explicit expression for the term $o(1)$ due to its complexity, as done also in [2,3] which we base our stability analysis upon. We refer to the proofs in [2,3] for additional details on the probability terms. We have clarified this in the revised manuscript.

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?

As we elaborate in Remark 2, both thresholding and covariance sparsification do not ensure that the resulting matrix is PSD. This is not needed for our theoretical results and is common in related works (e.g., [2,3]). We also report in Appendix G a sufficient condition for a hard-thresholded covariance matrix to be PSD.

What happens when the true data distribution is heavy tailed

The theoretical results hold for any random variable $\mathbf{x}$, and the Gaussian assumption is Thm. 1 is actually not needed (we have removed it from the revised manuscript). In particular, we always compute the covariance matrix $\mathbf{C}$ for the random variable $\mathbf{x}$ regardless of its distribution. We are not sure what the reviewer refers to with a random variable not having a finite covariance matrix, and we are happy to discuss this further if the reviewer can point us to a reference to understand this concept.

Wrong claim about increased stability

The reviewer is right that our analysis under hard thresholding leads to a smaller bound, but not definitely guarantees better stability. We have rephrased this in the revised manuscript.

Distribution of $\mathbf{x}$ in Thm. 1

$\mathbf{x}$ does not need to follow a Gaussian distribution but only needs to have covariance $\mathbf{C}$. The assumption on its norm, $\\|\mathbf{x}\\| \leq 1$, is only used to make the bound more concise and we can derive a similar bound by replacing $1$ with some constant $C_\text{norm}$ without loss of generality. Furthermore, we can always rescale data to have a unit bound on the norm. We have clarified this in the revised manuscript.

Incorrect grammar for paragraph starting line 167/168.

We have rephrased this sentence as follows: "We now define the frequency response of a covariance filter, which will be instrumental for our analysis."

Do advanced PCA variants overcome instability issues w.r.t. sample estimation?

The instability issues related to sample estimation of PCA are present in kernel PCA as well. Indeed, kernel PCA also estimates a sample covariance matrix after mapping the samples to a kernel space, and this estimation is prone to errors. Other extensions of PCA, such as exponential PCA, on the other hand, might be less prone to estimation errors, but their convergence properties as the number of samples increases are more difficult to characterize. Nevertheless, standard PCA remains highly popular in practice, which justifies it being the main focus of our analysis.

Conclusion

We thank the reviewer for pointing out unclear passages in our work. We have revised the manuscript accordingly and we believe that now clarity is improved, and we hope to have effectively addressed the reviewer's concerns. We remain available for further discussions and questions.

References

[1] Saurabh Sihag, Gonzalo Mateos, Corey McMillan, and Alejandro Ribeiro. Covariance neural networks. Advances in neural information processing systems, 2022.

[2] Peter J. Bickel and Elizaveta Levina. Regularized estimation of large covariance matrices. The Annals of Statistics 2008.

[3] Peter J Bickel and Elizaveta Levina. Covariance regularization by thresholding. The Annals of Statistics, 2008.

[4] Yash Deshpande and Andrea Montanari. Sparse pca via covariance thresholding. Journal of Machine Learning Research, 2016.

[5] Alaa Bessadok, Mohamed Ali Mahjoub, and Islem Rekik. Graph neural networks in network neuroscience. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.

[6] Lishan Qiao, Han Zhang, Minjeong Kim, Shenghua Teng, Limei Zhang, and Dinggang Shen. Estimating functional brain networks by incorporating a modularity prior. NeuroImage, 2016.

[7] José Vinícius de Miranda Cardoso, Jiaxi Ying, and Daniel Perez Palomar. Algorithms for learning graphs in financial markets, 2020.

[8] Yuanrong Wang and Tomaso Aste. Network filtering of spatial-temporal gnn for multivariate timeseries prediction. In Proceedings of the Third ACM International Conference on AI in Finance, 2022

[9] Tianzheng Liao, Jinjin Zhao, Yushi Liu, Kamen Ivanov, Jing Xiong, and Yan Yan. Deep transfer learning with graph neural network for sensor-based human activity recognition. IEEE International Conference on Bioinformatics and Biomedicine, 2022.

[10] Yan Wang, Xin Wang, and Hongmei Yang et al. Mhagnn: A novel framework for wearable sensorbased human activity recognition combining multi-head attention and graph neural networks. IEEE Transactions on Instrumentation and Measurement, 2023.

[11] Zhan Gao, Elvin Isufi, and Alejandro Ribeiro. Stability of graph convolutional neural networks to stochastic perturbations. Signal Processing, 2021.

[12] Saurabh Sihag, Gonzalo Mateos, Corey McMillan, and Alejandro Ribeiro. Explainable brain age prediction using covariance neural networks. Advances in Neural Information Processing Systems, 2024.

[13] Andrea Cavallo, Mohammad Sabbaqi, and Elvin Isufi. Spatiotemporal covariance neural networks. Machine Learning and Knowledge Discovery in Databases. 2024.

[14] Andrea Cavallo, Madeline Navarro, Santiago Segarra, and Elvin Isufi. Fair covariance neural networks, 2024.

[15] Sihag, Saurabh, et al. Transferability of Covariance Neural Networks. IEEE Journal of Selected Topics in Signal Processing, 2024.

[16] Khalafi, Shervin, Saurabh Sihag, and Alejandro Ribeiro. Neural Tangent Kernels Motivate Cross-Covariance Graphs in Neural Networks. Forty-first International Conference on Machine Learning 2024.

[17] Andreas Loukas. How close are the eigenvectors of the sample and actual covariance matrices? International Conference on Machine Learning, 2017.