Introduction
Functional brain network analysis has emerged as an important approach both for diagnosing neurological disorders and for predicting cognitive characteristics. In this setting, the data typically consist of functional magnetic resonance imaging (fMRI) recordings, captured as time-series matrices Z i ∈ R T × p Z_i \in\mathbb{R}^{T \times p} Z i ∈ R T × p ; each matrix tracks how brain activity unfolds over T T T time points across p p p predefined regions of interest (ROIs) for a given patient. In this context, the primary research question typically concerns how interactions among brain regions, often measured as covariances or correlations between ROIs and often referred to as “the connectome”, relate to a subject-specific outcome, represented by y i y_i y i . This framework corresponds to positing an underlying model f ⋆ f^\star f ⋆ that links the connectome to the outcome: f ⋆ : Σ ( i ) → y i f^\star: \Sigma^{(i)} \to y_i f ⋆ : Σ ( i ) → y i .
Since brain functions are hypothesized to stem from a complex network of interconnected regions [1 ] , graph-based methods are increasingly adopted for modeling the brain connectome. Following the success of GNNs in other applications, algorithms based on GNN message-passing schemes have become prevalent in the field [2 , 3 ] , frequently serving as the backbone of state-of-the-art pipelines with an increasing range of variants created and customized for neuroscience applications.
Despite the popularity of graph-based methods, a growing body of evidence suggests that message passing does not actually help in analyzing the human brain connectome. In Figure 1 , we show that the performance of standard GNNs (GraphSAGE [4 ] , GCN [5 ] and GAT [6 ] ) and a popular brain connectomics graph methodology (Residual GNN [3 ] ) does not improve upon simpler (graph-agnostic) methods on three real-world datasets. This echoes the findings of [7 ] , who benchmarked graph deep learning models on large-scale functional connectome datasets and found that their message aggregation brings no gain over graph-agnostic baselines; we refer to their work for an exhaustive empirical demonstration of the problem. Similarly, [8 ] showed that basic classifiers using functional connectivity matrices consistently outperform message passing architectures. Finally, [9 ] showed that the message aggregation mechanisms characteristic of GNNs often have a detrimental effect on prediction performance from functional brain networks. From the broader GNNs landscape, the literature has focused on understanding the pitfalls of message passing in node-level tasks such as semi-supervised classification, with particular emphasis on the oversmoothing phenomenon [10 , 11 , 12 , 13 ] . However, these critiques are either predominantly empirical or in a non-applicable setting; hence our main question of interest:
Figure 1. Performance across regression and classification tasks on 3 datasets. Graph-based methods fail to outperform graph-agnostic baselines, both linear (Linear Model) and non-linear (Random Forest, SVM, MLP). Mean ± \pm ± 1 SD over 10 seeds. See Appendix § 11 for details.
Why do graph message passing algorithms fail in brain connectome analysis?
To answer this question, we study the traditional brain connectomics pipeline (Figure 2 ) as a statistical estimation problem. The true connectome of each subject is latent, and we only observe an empirical connectivity matrix estimated from a finite recording, so the analysis is naturally framed as an errors-in-variables (EIV) problem. The empirical connectivity matrix, either the sample covariance Σ ^ \widehat{\Sigma} Σ or the sample correlation C ^ \widehat{C} C , is used twice: as the node features and as the basis for the graph A ^ = f ( Σ ^ ) \widehat{A} = f(\widehat{\Sigma}) A = f ( Σ ) or A ^ = f ( C ^ ) \widehat{A} = f(\widehat{C}) A = f ( C ) .
Figure 2. Brain connectome GNN pipeline and statistical challenges. Top: the standard analytical pipeline, from ROI time series to prediction y ^ i \hat{y}_i y ^ i . Bottom: statistical challenges induced by the pipeline. The errors-in-variables component (red) is analyzed in this paper; the remaining challenges (gray, dashed) are left to future work.
Main contributions. Our contributions are summarized as follows:
An EIV formulation that allows untangling different effects. Under an errors-in-variables formulation, we show in Section 3 that the effect of graph convolution on the predictive performance of the method splits into three parts: (i) a graph smoothing effect that induces a bias-variance tradeoff even with a correctly specified (oracle) graph; (ii) the graph estimation error , which is the cost of smoothing over a wrongly estimated graph; and (iii) a double-dipping effect that couples the graph operator with the feature noise when both come from the same sample.
connectome, which describes how sharply ROIs group into communities; the predictive signal , which describes how the target aligns with these communities; and the threshold , which determines which connections become edges of the graph. We make all three explicit through a latent community model, building on the standard neuroscience assumption that ROIs belong to a small number of communities (§ 4 ). Under this model, convolution improves on the raw features only when its noise reduction outweighs the signal it distorts, which restricts the gains to short recordings. Simulations, where the true connectome is known, validate the theory (§ 5 ).
Practical relevance for real data. On fMRI data, we build proxies for the oracle and independent graphs to separate the three effects in practice, and we show how the theory can guide the choice of graph, threshold and window length (§ 6 , Appendix § 11 .§ 4 ).
Related literature
Graph neural networks for brain connectomes. The brain connectome is commonly modeled as a network of interconnected regions [1 ] whose activity is driven by a small number of latent components [14 , 15 , 16 ] . Message passing with GCN, GraphSAGE or GAT convolutions [5 , 4 , 6 ] underlies most connectome-specific models [17 , 18 , 19 , 20 ] and the standard benchmarks [2 , 3 ] . In these pipelines the graph is obtained by thresholding the same empirical connectivity matrix that serves as the node features.
Evidence against message passing. Graph-agnostic classifiers on the connectivity matrix match or outperform GNNs and graph transformers [8 , 7 ] . On the NeuroGraph benchmarks, accuracy is unchanged when edges are randomly removed, even when all of them are removed [9 ] . None of these studies explains the failure.
Theory of message passing. Analyses of message passing [21 ] have focused on node-level tasks. Once linearized, convolutions act as low-pass filters [22 , 23 ] . This explains why models without nonlinearities retain most of their accuracy [22 , 24 ] , while repeated aggregation leads to oversmoothing [10 , 13 ] . Closest to our setting, Keriven [11 ] shows on a latent-space random graph that a finite number of mean-aggregation steps improves node-level regression before oversmoothing sets in. Our setting differs in two ways: the task is graph-level, and the graph is estimated from the same noisy data as the features.
Measurement error and double dipping. Predicting from a noisy estimate of the connectome is an errors-in-variables problem. § 3 reviews the corrections for covariate measurement error and explains why they do not apply here. In the standard pipeline the same window also selects the edges, which we call double dipping, and we quantify its effect for graph convolutions.
Statistical framework
For each subject i = 1 , … , n i = 1,\ldots,n i = 1 , … , n , let Z ( i ) ∈ R T × p Z^{(i)} \in\mathbb{R}^{T \times p} Z ( i ) ∈ R T × p denote the centered fMRI time series measured at p p p regions of interest (ROIs) over T T T time points. To keep the analysis simple, we assume independent time-points Z t ( i ) ∼ i . i . d . N ( 0 , Σ ( i ) ) Z_t^{(i)} \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}(0,\Sigma^{(i)}) Z t ( i ) ∼ i.i.d. N ( 0 , Σ ( i ) ) , t = 1 , … , T t = 1,\ldots,T t = 1 , … , T , where Σ ( i ) ∈ R p × p \Sigma^{(i)} \in\mathbb{R}^{p \times p} Σ ( i ) ∈ R p × p is the subject’s latent functional connectome. The connectome is not observed directly. Instead, we observe the empirical covariance
Σ ^ ( i ) = 1 T ∑ t = 1 T Z t ( i ) Z t ( i ) T = Σ ( i ) + H ( i ) , (1) \widehat{\Sigma}^{(i)} = \frac{1}{T}\sum_{t=1}^{T} Z_t^{(i)} Z_t^{(i)\mathsf{T}} = \Sigma^{(i)} + H^{(i)}, \tag*{(1)} Σ ( i ) = T 1 t = 1 ∑ T Z t ( i ) Z t ( i ) T = Σ ( i ) + H ( i ) , (1)
where H ( i ) H^{(i)} H ( i ) is the finite-sample estimation error. For simplicity, we focus on the sample covariance Σ ^ ( i ) \widehat{\Sigma}^{(i)} Σ ( i ) throughout the theoretical analysis; extensions to the sample correlation matrix C ^ ( i ) \widehat{C}^{(i)} C ( i ) , which is the more common choice in fMRI pipelines, are analyzed computationally in Appendix § 10 and behave analogously. We study a simple supervised regression problem in which the patient-level target y i y_i y i depends on the latent connectome through some (potentially non-linear) function f ∗ f^* f ∗ :
y i = f ∗ ( Σ ( i ) ) + ϵ i , ϵ i ∼ N ( 0 , σ ϵ 2 ) . (2) y_i = f^*\left(\Sigma^{(i)}\right) + \epsilon_i,\qquad\epsilon_i \sim\mathcal{N}\left(0,\sigma_{\epsilon}^2\right). \tag*{(2)} y i = f ∗ ( Σ ( i ) ) + ϵ i , ϵ i ∼ N ( 0 , σ ϵ 2 ) . (2)
The purpose of brain connectomics analysis is thus to find the best approximation of f ⋆ f^\star f ⋆ within some function class F \mathcal{F} F , typically parametrized by a vector of parameters θ \theta θ :
θ ^ ∈ argmin f θ ∈ F 1 n ∑ i = 1 n ∥ y i − f θ ( Σ ( i ) ) ∥ 2 . (3) \hat{\theta} \in\underset{f_\theta\in\mathcal{F}}{\operatorname{argmin}} \frac{1}{n}\sum_{i=1}^{n}\lVert y_i-f_\theta(\Sigma^{(i)})\rVert^2. \tag*{(3)} θ ^ ∈ f θ ∈ F argmin n 1 i = 1 ∑ n ∥ y i − f θ ( Σ ( i ) ) ∥ 2 . (3)
An errors-in-variables regression problem. Since the true connectivity Σ ( i ) \Sigma^{(i)} Σ ( i ) is not observed, a simple solution is to use the estimated covariance matrix (also known as the plug-in estimator) Σ ^ ( i ) \hat{\Sigma}^{(i)} Σ ^ ( i ) and solve Eq. (3) . However, predicting y i y_i y i from Σ ^ ( i ) \hat{\Sigma}^{(i)} Σ ^ ( i ) rather than Σ ( i ) \Sigma^{(i)} Σ ( i ) places us in an errors-in-variables regression setting. For simplicity, we restrict the function class to linear maps, F = { f θ : x ↦ x ⊤ θ } \mathcal{F}=\{f_\theta:x\mapsto x^\top\theta\} F = { f θ : x ↦ x ⊤ θ } , so that y i = vec ( Σ ( i ) ) ⊤ β ⋆ + ϵ i y_i=\operatorname{vec}(\Sigma^{(i)})^\top\beta^\star+\epsilon_i y i = vec ( Σ ( i ) ) ⊤ β ⋆ + ϵ i . In this setting, the plug-in OLS estimator has a closed form. Write x i = vec ( Σ ( i ) ) x_i=\operatorname{vec}(\Sigma^{(i)}) x i = vec ( Σ ( i ) ) for the true features, η i = vec ( H ( i ) ) \eta_i=\operatorname{vec}(H^{(i)}) η i = vec ( H ( i ) ) for the noise, and x ^ i = x i + η i \hat{x}_i=x_i+\eta_i x ^ i = x i + η i for the observed features. Under the Gaussian model above, the noise η i \eta_i η i has conditional mean zero given Σ ( i ) \Sigma^{(i)} Σ ( i ) and its conditional covariance scales as T − 1 T^{-1} T − 1 :
E η i [ η i ∣ Σ ( i ) ] = 0 , Cov η i ( η i ∣ Σ ( i ) ) = 1 T Ψ ( i ) , Ψ ( i ) = ( I p 2 + K p , p ) ( Σ ( i ) ⊗ Σ ( i ) ) , (4) \mathbb{E}_{\eta_i}[\eta_i\mid\Sigma^{(i)}]=0,\qquad\operatorname{Cov}_{\eta_i}(\eta_i\mid\Sigma^{(i)})=\frac{1}{T}\Psi^{(i)},\qquad\Psi^{(i)}=(I_{p^2}+K_{p,p})(\Sigma^{(i)}\otimes\Sigma^{(i)}), \tag*{(4)} E η i [ η i ∣ Σ ( i ) ] = 0 , Cov η i ( η i ∣ Σ ( i ) ) = T 1 Ψ ( i ) , Ψ ( i ) = ( I p 2 + K p , p ) ( Σ ( i ) ⊗ Σ ( i ) ) , (4)
where K p , p K_{p,p} K p , p is the commutation matrix (Definition 1). Let S = E Σ [ x x ⊤ ] S=\mathbb{E}_{\Sigma}[xx^\top] S = E Σ [ x x ⊤ ] and Γ = E Σ [ Ψ ] \Gamma=\mathbb{E}_{\Sigma}[\Psi] Γ = E Σ [ Ψ ] , and write † \dagger † for the Moore–Penrose pseudo-inverse. A classical errors-in-variables computation (Remark 1 in Appendix A.2) gives the population OLS coefficient β r a w ⋆ ( T ) = Λ ( T ) β ⋆ \beta^\star_{\mathrm{raw}}(T)=\Lambda(T)\beta^\star β raw ⋆ ( T ) = Λ ( T ) β ⋆ , with Λ ( T ) : = ( S + 1 T Γ ) † S \Lambda(T):=(S+\frac{1}{T}\Gamma)^\dagger S Λ ( T ) := ( S + T 1 Γ ) † S . Its test error is
MSE r a w ( T ) = β ⋆ ⊤ ( I − Λ ( T ) ) ⊤ S ( I − Λ ( T ) ) β ⋆ + 1 T β ⋆ ⊤ Λ ( T ) ⊤ Γ Λ ( T ) β ⋆ + σ ϵ 2 . (5) \operatorname{MSE}_{\mathrm{raw}}(T)=\beta^{\star\top}(I-\Lambda(T))^\top S(I-\Lambda(T))\beta^\star+\frac{1}{T}\beta^{\star\top}\Lambda(T)^\top\Gamma\Lambda(T)\beta^\star+\sigma_\epsilon^2. \tag*{(5)} MSE raw ( T ) = β ⋆ ⊤ ( I − Λ ( T ) ) ⊤ S ( I − Λ ( T )) β ⋆ + T 1 β ⋆ ⊤ Λ ( T ) ⊤ ΓΛ ( T ) β ⋆ + σ ϵ 2 . (5)
The first term is a bias: the noise pulls the coefficient away from β ⋆ \beta^\star β ⋆ . The second is tied to the variance: the noise in the features is carried into the prediction. Both terms depend on T T T , not on n n n , so it is important to note that more subjects do not remove the error; only longer recordings do. MSE r a w \operatorname{MSE}_{\mathrm{raw}} MSE raw is the baseline we compare every graph against in the rest of the paper. A convolution is appealing because averaging neighboring entries of Σ ^ \hat{\Sigma} Σ ^ can reduce the noise term, but it can also distort the signal. The next sections quantify this trade-off.
A large literature has studied corrections for covariate measurement error, spanning corrected high-dimensional Lasso objectives [25 , 26 ] , score, likelihood, and deconvolution-based approaches for generalized and nonlinear models [27 , 28 , 29 ] , and recent nonparametric or neural approaches [30 ] . None of these are directly applicable here: the measurement error in vec ( Σ ^ ) \operatorname{vec}(\hat{\Sigma}) vec ( Σ ^ ) is not exogenous with fixed covariance but dense, entry-correlated, and dependent on the unobserved latent connectome (Eq. (4) ).
The appeal of the graph. An alternative is to exploit the inherent problem structure: in neuroscience, each ROI is typically assumed to participate in K ≤ p K\leq p K ≤ p latent neural communities [1 ] that can be represented by a graph. For this reason, GNN-based algorithms have been extensively used in this field as standalone standard convolutions [5 , 4 , 6 ] or as part of brain-connectome-tailored architectures [3 , 17 ] . Their goal is twofold: (a) obtaining a richer feature map and (b) denoising the empirical covariance matrix by averaging over appropriate neighborhoods. We postulate that the main appeal of these methods in our setting stems from the denoising effect: the usually reported strengths of GNNs as feature maps (such as learning permutation-invariant representations) do not apply here, since ROIs are aligned across patients and therefore non-exchangeable.
A graph message passing layer is defined as X ′ = σ ( R ( A ) X W ) X' = \sigma(R(A)XW) X ′ = σ ( R ( A ) X W ) , where A ∈ R p × p A \in\mathbb{R}^{p \times p} A ∈ R p × p is an adjacency matrix, X ∈ R p × m X \in\mathbb{R}^{p \times m} X ∈ R p × m a node feature matrix, W ∈ R m × m ′ W \in\mathbb{R}^{m \times m'} W ∈ R m × m ′ learnable weights, R ( A ) R(A) R ( A ) the graph operator induced by A A A (e.g. D ~ − 1 A ~ \widetilde{D}^{-1}\widetilde{A} D − 1 A for GraphSAGE [4 ] , D ~ − 1 / 2 A ~ D ~ − 1 / 2 \widetilde{D}^{-1/2}\widetilde{A}\widetilde{D}^{-1/2} D − 1/2 A D − 1/2 for GCN [5 ] , with A ~ = A + I \widetilde{A}=A+I A = A + I and D ~ = diag ( A ~ 1 ) \widetilde{D}=\operatorname{diag}(\widetilde{A}\mathbf{1}) D = diag ( A 1 ) ), and σ \sigma σ an activation function.
The brain connectomics pipeline (Figure 2 ) proceeds as follows. First, each subject’s time series is split into windows of length T T T , so that shorter windows yield more samples per subject. Second, a connectivity matrix is estimated from each window (usually the correlation C ^ ( i ) \widehat{C}^{(i)} C ( i ) rather than the covariance Σ ^ ( i ) \widehat{\Sigma}^{(i)} Σ ( i ) ). Third, this matrix is used twice: as the node features, X = Σ ^ ( i ) X=\widehat{\Sigma}^{(i)} X = Σ ( i ) or X = C ^ ( i ) X=\widehat{C}^{(i)} X = C ( i ) , and to build the graph A ^ \widehat{A} A through a non-linear function f f f (for instance, hard or absolute-value thresholding [3 ] , either at a fixed level, A ^ j k = 1 { Σ ^ j k > δ } \widehat{A}_{jk}=\mathbb{1}\{\widehat{\Sigma}_{jk}>\delta\} A j k = 1 { Σ j k > δ } with δ ∈ R \delta\in\mathbb{R} δ ∈ R , or at a fixed edge density, A ^ j k = 1 { Σ ^ j k > q 1 − τ ( Σ ^ ) } \widehat{A}_{jk}=\mathbb{1}\{\widehat{\Sigma}_{jk}>q_{1-\tau}(\widehat{\Sigma})\} A j k = 1 { Σ j k > q 1 − τ ( Σ )} with τ ∈ ( 0 , 1 ) \tau\in(0,1) τ ∈ ( 0 , 1 ) , where q 1 − τ q_{1-\tau} q 1 − τ is the ( 1 − τ ) (1-\tau) ( 1 − τ ) -quantile of the off-diagonal entries). Finally, one or more message-passing layers, usually with non-linear activations and followed by a readout, are trained on the n n n windows pooled across subjects, and n n n is often smaller than the number p ( p − 1 ) / 2 p(p-1)/2 p ( p − 1 ) /2 of pairwise interactions between the p p p ROIs.
We focus here on understanding the denoising effect and the bias–variance tradeoff induced by the convolution, which requires disentangling it from the other factors summarized at the bottom of Figure 2 . For the purposes of this paper, we therefore simplify the pipeline. We use the covariance and independent time points, as introduced above. We work in an infinite-n n n (asymptotic) regime, where T T T is a free parameter rather than tied to n n n through the windowing. We also restrict our analysis to linear models applied to the vectorized smoothed covariance, with the graph obtained by thresholding at a fixed level δ \delta δ rather than a fixed density τ \tau τ . The latter restriction aligns with much of the empirical work that uses only the message-passing component and does not incorporate additional non-linearities [22 , 23 , 24 ] . Under these simplifications, the population risk has a closed form, and the analysis still captures how the message-passing layer interacts with the measurement noise. Appendix C.3.1 relaxes these simplifications one at a time on real data.
We compare prediction based on the raw feature map x ^ = vec ( Σ ^ ( i ) ) \widehat{x}=\operatorname{vec}(\widehat{\Sigma}^{(i)}) x = vec ( Σ ( i ) ) with that on the smoothed feature map x ~ A = vec ( R ( A ) Σ ^ ( i ) ) \widetilde{x}_{A}=\operatorname{vec}(R(A)\widehat{\Sigma}^{(i)}) x A = vec ( R ( A ) Σ ( i ) ) , where R ( A ) Σ ^ ( i ) R(A)\widehat{\Sigma}^{(i)} R ( A ) Σ ( i ) is a linear message-passing convolution (e.g. R ( A ) = D ~ − 1 A ~ R(A)=\widetilde{D}^{-1}\widetilde{A} R ( A ) = D − 1 A for GraphSAGE). We consider four choices of A A A :
A population graph ( A p o p ) j k ( δ ) = 1 { ( Σ 0 ) j k > δ } (A^{\mathrm{pop}})_{jk}(\delta)=\mathbb{1}\{(\Sigma_{0})_{jk}>\delta\} ( A pop ) j k ( δ ) = 1 {( Σ 0 ) j k > δ } , where Σ 0 = E Σ [ Σ ( i ) ] \Sigma_{0}=\mathbb{E}_{\Sigma}[\Sigma^{(i)}] Σ 0 = E Σ [ Σ ( i ) ] , is the average brain connectivity, independent of each subject’s feature noise.
The oracle graph A j k o r a c l e ( δ ) = 1 { Σ j k ( i ) > δ } A^{\mathrm{oracle}}_{jk}(\delta)=\mathbb{1}\{\Sigma^{(i)}_{jk}>\delta\} A j k oracle ( δ ) = 1 { Σ j k ( i ) > δ } , constructed from the true Σ ( i ) \Sigma^{(i)} Σ ( i ) , which captures the “best-case” impact of smoothing under correct graph specification.
The same-sample graph A ^ j k ( i ) ( δ ) = 1 { Σ ^ j k ( i ) > δ } \widehat{A}^{(i)}_{jk}(\delta)=\mathbb{1}\{\widehat{\Sigma}^{(i)}_{jk}>\delta\} A j k ( i ) ( δ ) = 1 { Σ j k ( i ) > δ } , built from the same empirical covariance as the node features; the most common choice in practice [17 , 18 , 19 , 20 ] .
An independent graph A j k ⊥ ( i ) ( δ ) = 1 { Σ ^ j k ⊥ ( i ) > δ } A^{\perp(i)}_{jk}(\delta)=\mathbb{1}\{\widehat{\Sigma}^{\perp(i)}_{jk}>\delta\} A j k ⊥ ( i ) ( δ ) = 1 { Σ j k ⊥ ( i ) > δ } , where Σ ^ ⊥ ( i ) = Σ ( i ) + H ⊥ ( i ) \widehat{\Sigma}^{\perp(i)}=\Sigma^{(i)}+H^{\perp(i)} Σ ⊥ ( i ) = Σ ( i ) + H ⊥ ( i ) with H ⊥ ( i ) ⊥ ⊥ Σ ( i ) H^{\perp(i)} \perp\!\!\!\perp\Sigma^{(i)} H ⊥ ( i ) ⊥ ⊥ Σ ( i ) . It has graph-estimation error but the errors in the graph and features are independent.
Replacing x ^ \widehat{x} x with the smoothed features x ~ A = R A x ^ \widetilde{x}_{A}=\mathcal{R}_{A}\widehat{x} x A = R A x , where R A = I p ⊗ R ( A ) \mathcal{R}_{A}=I_{p}\otimes R(A) R A = I p ⊗ R ( A ) is the vectorized convolution, keeps us in an errors-in-variables regression, now with the convolution sitting between the noise and the coefficient. For any graph construction A A A , whether fixed or random, the population OLS test error is
MSE A ( T ) = E Σ [ h ( Σ ) 2 ] − c A T M A † c A + σ ε 2 , \operatorname{MSE}_{A}(T)=\mathbb{E}_{\Sigma}[h(\Sigma)^{2}]-c_{A}^{\mathsf{T}}M_{A}^{\dagger}c_{A}+\sigma_{\varepsilon}^{2}, MSE A ( T ) = E Σ [ h ( Σ ) 2 ] − c A T M A † c A + σ ε 2 ,
where h ( Σ ) = vec ( Σ ) T β ∗ h(\Sigma)=\operatorname{vec}(\Sigma)^{\mathsf{T}}\beta^{*} h ( Σ ) = vec ( Σ ) T β ∗ is the noiseless target, M A = E Σ , η , A [ x ~ A x ~ A T ] M_{A}=\mathbb{E}_{\Sigma,\eta,A}[\widetilde{x}_{A}\widetilde{x}_{A}^{\mathsf{T}}] M A = E Σ , η , A [ x A x A T ] and c A = E Σ , η , A [ x ~ A h ( Σ ) ] c_{A}=\mathbb{E}_{\Sigma,\eta,A}[\widetilde{x}_{A}h(\Sigma)] c A = E Σ , η , A [ x A h ( Σ )] . Writing x ^ = x + η \widehat{x}=x+\eta x = x + η , both split into a signal part, a noise part, and cross terms between the two:
M A = E Σ , η , A [ R A x x T R A T ] + E Σ , η , A [ R A x η T R A T ] + E Σ , η , A [ R A η x T R A T ] + E Σ , η , A [ R A η η T R A T ] , M_{A}=\mathbb{E}_{\Sigma,\eta,A}[\mathcal{R}_{A}xx^{\mathsf{T}}\mathcal{R}_{A}^{\mathsf{T}}]+\mathbb{E}_{\Sigma,\eta,A}[\mathcal{R}_{A}x\eta^{\mathsf{T}}\mathcal{R}_{A}^{\mathsf{T}}]+\mathbb{E}_{\Sigma,\eta,A}[\mathcal{R}_{A}\eta x^{\mathsf{T}}\mathcal{R}_{A}^{\mathsf{T}}]+\mathbb{E}_{\Sigma,\eta,A}[\mathcal{R}_{A}\eta\eta^{\mathsf{T}}\mathcal{R}_{A}^{\mathsf{T}}], M A = E Σ , η , A [ R A x x T R A T ] + E Σ , η , A [ R A x η T R A T ] + E Σ , η , A [ R A η x T R A T ] + E Σ , η , A [ R A η η T R A T ] ,
c A = E Σ , η , A [ R A x x T ] β ∗ + E Σ , η , A [ R A η x T ] β ∗ . c_{A}=\mathbb{E}_{\Sigma,\eta,A}[\mathcal{R}_{A}xx^{\mathsf{T}}]\beta^{*}+\mathbb{E}_{\Sigma,\eta,A}[\mathcal{R}_{A}\eta x^{\mathsf{T}}]\beta^{*}. c A = E Σ , η , A [ R A x x T ] β ∗ + E Σ , η , A [ R A η x T ] β ∗ .
How these terms behave depends on how the graph relates to the feature noise, which gives three cases (Proposition 4, Appendix A.3):
(i) For the same-sample graph A ^ \widehat{A} A , the graph is built from the same Σ ^ \widehat{\Sigma} Σ as the features, so it depends on the noise it is meant to average out. All terms are present, and the cross terms do not vanish due to this double-dipping effect.
(ii) For an independent graph that varies across subjects , such as A o r a c l e A^{\mathrm{oracle}} A oracle and A ⊥ A^{\perp} A ⊥ , the graph is independent of the feature noise given Σ \Sigma Σ , so the cross terms vanish.
(iii) For a fixed graph shared across samples , as for A p o p A^{\mathrm{pop}} A pop , the same convolution is applied to every subject, so R A R_A R A is a fixed linear map. A linear model on x ~ A \widetilde{x}_A x A is then still a linear model on x ~ \widetilde{x} x , and message passing can never improve on the raw features. It only ties with the raw features when R ( A ) R(A) R ( A ) is invertible and can only do worse otherwise (Proposition 5, Appendix A.3).
In the two cases where the graph varies across subjects, the sign of each effect is not determined in general. It depends on how the connectome Σ \Sigma Σ is structured, on how the target relates to that structure, and on how the graph is built. In the next section we introduce a latent community model that makes these three ingredients explicit.
Brain connectome inspired latent communities model
We now specialize the previous results to a simple connectome model, showing how the favorable regime changes as we move from the oracle graph A o r a c l e A^{\mathrm{oracle}} A oracle , to the independent graph A ⊥ A^{\perp} A ⊥ , and to the same-sample graph A ^ \widehat{A} A , with the goal of isolating respectively the graph smoothing effect , the graph estimation error , and the double-dipping effect .
The model represents brain activity through a small number of interacting latent components [14 , 15 , 16 , 31 ] . Let F ( i ) ∈ R p × d F^{(i)} \in\mathbb{R}^{p \times d} F ( i ) ∈ R p × d collect the ROIs’ loadings onto d d d latent dimensions. Each ROI j j j belongs to one community z j ∈ { 1 , … , K } z_j \in\{1,\ldots,K\} z j ∈ { 1 , … , K } , K ≤ min { p , d } K \le\min\{p,d\} K ≤ min { p , d } ; the communities are balanced, with ∣ C k ∣ = q = p / K |C_k| = q = p/K ∣ C k ∣ = q = p / K and C ( j ) : = C z j C(j) := C_{z_j} C ( j ) := C z j . Following Appendix A.4.1, we take fixed, orthogonal centroids μ k \mu_k μ k with ∥ μ k ∥ 2 = ϕ 2 d \lVert\mu_k\rVert^2 = \phi^2 d ∥ μ k ∥ 2 = ϕ 2 d . For each subject, let f j ( i ) = μ z j + ν j ( i ) f_j^{(i)} = \mu_{z_j} + \nu_j^{(i)} f j ( i ) = μ z j + ν j ( i ) , where ν j ( i ) ∼ i . i . d . N ( 0 , σ 2 I d ) \nu_j^{(i)} \overset{\mathrm{i.i.d.}}{\sim} \mathcal{N}(0,\sigma^2 I_d) ν j ( i ) ∼ i.i.d. N ( 0 , σ 2 I d ) across ROIs j j j and subjects i i i , and define Σ ( i ) = F ( i ) F ( i ) ⊤ + ψ 2 I p \Sigma^{(i)} = F^{(i)}F^{(i)\top} + \psi^2 I_p Σ ( i ) = F ( i ) F ( i ) ⊤ + ψ 2 I p , with f j ( i ) ⊤ f_j^{(i)\top} f j ( i ) ⊤ the j j j -th row of F ( i ) F^{(i)} F ( i ) and the perturbations are independent across ROIs and subjects. The ROI partition, centroids, latent dimension d d d , and parameters ϕ , ψ > 0 \phi,\psi> 0 ϕ , ψ > 0 are fixed across subjects. Under this model, we characterize three ingredients.
Community structure, σ \sigma σ . The parameter σ \sigma σ controls subject variability around the shared community pattern. For j ≠ k j \ne k j = k , the within- and between-community covariance means and common variance are μ W = ϕ 2 d \mu_W = \phi^2 d μ W = ϕ 2 d , μ B = 0 \mu_B = 0 μ B = 0 , and s 2 ( σ ) = 2 σ 2 ϕ 2 d + σ 4 d s^2(\sigma) = 2\sigma^2\phi^2 d + \sigma^4 d s 2 ( σ ) = 2 σ 2 ϕ 2 d + σ 4 d , respectively (Lemma 3). Increasing σ \sigma σ increases the spread around these fixed levels as shown in the heatmaps in Figure 3 .
Figure 3. Decoupling the effects for different values of β \beta β and latent structures. Center: true covariance Σ \Sigma Σ for two graph regimes (σ \sigma σ ); overlays mark the support of two coefficient patterns (β \beta β ). Left/right: normalized ValMSE vs. T T T for SageMean(A , Σ ^ A,\widehat{\Sigma} A , Σ ) and a no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. p = 20 p=20 p = 20 , K = 5 K=5 K = 5 , n = 25,000 n=25{,}000 n = 25 , 000 ; thresholds δ σ = 0.5 ≈ 9.10 \delta_{\sigma=0.5}\approx9.10 δ σ = 0.5 ≈ 9.10 , δ σ = 1.0 ≈ 10.20 \delta_{\sigma=1.0}\approx10.20 δ σ = 1.0 ≈ 10.20 .
Predictive signal, B ⋆ B^\star B ⋆ . The symmetric coefficient B ⋆ ∈ R p × p B^\star\in\mathbb{R}^{p \times p} B ⋆ ∈ R p × p specifies h ( Σ ) = ⟨ B ⋆ , Σ ⟩ h(\Sigma) = \langle B^\star,\Sigma\rangle h ( Σ ) = ⟨ B ⋆ , Σ ⟩ , with β ⋆ = vec ( B ⋆ ) \beta^\star= \operatorname{vec}(B^\star) β ⋆ = vec ( B ⋆ ) . We characterize its alignment with the same communities through max j max ℓ ∈ C ( j ) ∑ k = 1 p ( B j k ⋆ − B ℓ k ⋆ ) 2 ≤ κ β 2 \max_j\max_{\ell\in C(j)}\sum_{k=1}^p(B^\star_{jk}-B^\star_{\ell k})^2 \le\kappa_\beta^2 max j max ℓ ∈ C ( j ) ∑ k = 1 p ( B j k ⋆ − B ℓ k ⋆ ) 2 ≤ κ β 2 . Small κ β \kappa_\beta κ β describes community-smooth predictive profiles; the ideal case κ β = 0 \kappa_\beta= 0 κ β = 0 gives coefficients depending only on ( z j , z k ) (z_j,z_k) ( z j , z k ) . Community-level, single-edge, and concordant targets are defined in Appendix A.4.3.
Threshold, δ \delta δ . The threshold selects averaging neighborhoods from these connectomes. For oracle, A j k o r a c l e ( i ) ( δ ) = 1 { Σ j k ( i ) > δ } A_{jk}^{\mathrm{oracle}(i)}(\delta) = \mathbb{1}\{\Sigma_{jk}^{(i)} > \delta\} A j k oracle ( i ) ( δ ) = 1 { Σ j k ( i ) > δ } for j ≠ k j \ne k j = k , with mean aggregation R ( A ) = D ~ − 1 ( A + I p ) R(A) = \widetilde{D}^{-1}(A + I_p) R ( A ) = D − 1 ( A + I p ) . At the boundaries, δ = + ∞ \delta= +\infty δ = + ∞ gives the empty graph and R = I p R = I_p R = I p , the raw features, while δ = − ∞ \delta= -\infty δ = − ∞ gives the complete graph and R = 11 T / p R = \mathbf{1}\mathbf{1}^{\mathsf{T}}/p R = 1 1 T / p , the global average. The interesting case is an intermediate threshold, μ B < δ < μ W \mu_B < \delta< \mu_W μ B < δ < μ W , at distance γ δ : = min { μ W − δ , δ − μ B } \gamma_\delta:= \min\{\mu_W-\delta,\delta-\mu_B\} γ δ := min { μ W − δ , δ − μ B } from the two means. The graph then mostly links ROIs of the same community, and the operator splits as
R ( A o r a c l e ) = P C + Δ R δ , ( P C ) j ℓ = q − 1 1 { ℓ ∈ C ( j ) } . R(A^{\mathrm{oracle}}) = P_C + \Delta R_\delta,\qquad(P_C)_{j\ell} = q^{-1}\mathbb{1}\{\ell\in C(j)\}. R ( A oracle ) = P C + Δ R δ , ( P C ) j ℓ = q − 1 1 { ℓ ∈ C ( j )} .
Here P C P_C P C averages each ROI over its community, and Δ R δ \Delta R_\delta Δ R δ collects the subject-specific deviations, which depend on σ \sigma σ and δ \delta δ .
The following results examine how these three ingredients jointly affect prediction as the measurement length T T T varies.
Table 1. Graph constructions and prediction conclusions. Comparisons concern unregularized population linear prediction under the stated assumptions.
Result 1: Oracle graph smoothing effect. Smoothing over the oracle graph reduces measurement noise but also distorts the signal, and the balance between the two depends on the predictive signal B ⋆ B^\star B ⋆ , the community structure σ \sigma σ and the threshold δ \delta δ . If smoothing introduces prediction error that persists even after refitting the linear predictor on noiseless features, it cannot outperform raw features for sufficiently long recordings.
The following proposition is a more formal version of Result 1.
Proposition 1 (Oracle smoothing). Under the EIV assumptions of Remark 1 (Appendix § 9 .§ 2 ), fix any threshold δ \delta δ ; the oracle operator R ( A o r a c l e ( δ ) ) R\left(A^{\mathrm{oracle}}(\delta)\right) R ( A oracle ( δ ) ) is a function of Σ \Sigma Σ . Assume all displayed moments are finite and define the squared bias and the variance reduction:
B A o r a c l e ( δ ) : = E Σ [ ⟨ B ⋆ , R ( A o r a c l e ( δ ) ) Σ − Σ ⟩ 2 ] , B_{A^{\mathrm{oracle}}}(\delta) := \mathbb{E}_{\Sigma}\left[\left\langle B^\star,R\left(A^{\mathrm{oracle}}(\delta)\right)\Sigma-\Sigma\right\rangle^2\right], B A oracle ( δ ) := E Σ [ ⟨ B ⋆ , R ( A oracle ( δ ) ) Σ − Σ ⟩ 2 ] , Δ V A o r a c l e ( δ ) : = T E Σ [ Var η { ⟨ B ⋆ , H ⟩ ∣ Σ } − Var η { ⟨ B ⋆ , R ( A o r a c l e ( δ ) ) H ⟩ ∣ Σ } ] . \Delta V_{A^{\mathrm{oracle}}}(\delta) := T\mathbb{E}_{\Sigma}\left[\operatorname{Var}_{\eta}\left\{\left\langle B^\star,H\right\rangle\mid\Sigma\right\}-\operatorname{Var}_{\eta}\left\{\left\langle B^\star,R\left(A^{\mathrm{oracle}}(\delta)\right)H\right\rangle\mid\Sigma\right\}\right]. Δ V A oracle ( δ ) := T E Σ [ Var η { ⟨ B ⋆ , H ⟩ ∣ Σ } − Var η { ⟨ B ⋆ , R ( A oracle ( δ ) ) H ⟩ ∣ Σ } ] . Sufficient condition. The population MSEs satisfy, for every T > 0 T>0 T > 0 ,
MSE o r a c l e ( T , δ ) − MSE r a w ( T ) ≤ B A o r a c l e ( δ ) − Δ V A o r a c l e ( δ ) T + r r a w ( T ) , \operatorname{MSE}_{\mathrm{oracle}}(T,\delta)-\operatorname{MSE}_{\mathrm{raw}}(T)\le B_{A^{\mathrm{oracle}}}(\delta)-\frac{\Delta V_{A^{\mathrm{oracle}}}(\delta)}{T}+r_{\mathrm{raw}}(T), MSE oracle ( T , δ ) − MSE raw ( T ) ≤ B A oracle ( δ ) − T Δ V A oracle ( δ ) + r raw ( T ) , where
r r a w ( T ) : = T − 2 β ⋆ ⊤ Γ ( S + T − 1 Γ ) † Γ β ⋆ ≥ 0. r_{\mathrm{raw}}(T):=T^{-2}\beta^{\star\top}\Gamma(S+T^{-1}\Gamma)^{\dagger}\Gamma\beta^\star\ge0. r raw ( T ) := T − 2 β ⋆ ⊤ Γ ( S + T − 1 Γ ) † Γ β ⋆ ≥ 0. If the support of Σ \Sigma Σ spans the symmetric matrices (Remark 1), as in the latent community model with σ > 0 \sigma>0 σ > 0 , then r r a w ( T ) = O ( T − 2 ) r_{\mathrm{raw}}(T)=O(T^{-2}) r raw ( T ) = O ( T − 2 ) . Thus oracle smoothing improves whenever B A o r a c l e ( δ ) + r r a w ( T ) < Δ V A o r a c l e ( δ ) / T B_{A^{\mathrm{oracle}}}(\delta)+r_{\mathrm{raw}}(T)<\Delta V_{A^{\mathrm{oracle}}}(\delta)/T B A oracle ( δ ) + r raw ( T ) < Δ V A oracle ( δ ) / T .
Necessary condition. Let b δ : = min γ ∈ R p 2 E Σ [ { h ( Σ ) − γ ⊤ vec ( R ( A o r a c l e ( δ ) Σ ) ) } 2 ] b_{\delta}:=\min_{\gamma\in\mathbb{R}^{p^2}}\mathbb{E}_{\Sigma}\left[\left\{h(\Sigma)-\gamma^{\top}\operatorname{vec}\left(R\left(A^{\mathrm{oracle}}(\delta)\Sigma\right)\right)\right\}^{2}\right] b δ := min γ ∈ R p 2 E Σ [ { h ( Σ ) − γ ⊤ vec ( R ( A oracle ( δ ) Σ ) ) } 2 ] be the minimum noiseless prediction error, with γ \gamma γ shared across subjects. If b δ > 0 b_{\delta}>0 b δ > 0 , then
MSE o r a c l e ( T , δ ) < MSE r a w ( T ) ⟹ T < β ⋆ ⊤ Γ β ⋆ b δ . \operatorname{MSE}_{\mathrm{oracle}}(T,\delta)<\operatorname{MSE}_{\mathrm{raw}}(T)\quad\Longrightarrow\quad T<\frac{\beta^{\star\top}\Gamma\beta^\star}{b_{\delta}}. MSE oracle ( T , δ ) < MSE raw ( T ) ⟹ T < b δ β ⋆ ⊤ Γ β ⋆ .
The sufficient condition guarantees improvement when the variance reduction exceeds the squared bias plus r r a w ( T ) r_{\mathrm{raw}}(T) r raw ( T ) , which accounts for refitting the raw regression. If a positive error b δ b_{\delta} b δ remains even after fitting on noiseless smoothed features, sufficiently long recordings make raw prediction more accurate, giving the necessary upper limit on T T T .
For the intermediate threshold, μ B < δ < μ W \mu_B<\delta<\mu_W μ B < δ < μ W , the decomposition introduced above gives
B A o r a c l e ( δ ) : = E Σ [ { ⟨ B ⋆ , ( P C − I p ) Σ ⟩ + ⟨ B ⋆ , Δ R δ Σ ⟩ } 2 ] . B_{A^{\mathrm{oracle}}}(\delta):=\mathbb{E}_{\Sigma}\left[\left\{\left\langle B^\star,(P_C-I_p)\Sigma\right\rangle+\left\langle B^\star,\Delta R_{\delta}\Sigma\right\rangle\right\}^{2}\right]. B A oracle ( δ ) := E Σ [ { ⟨ B ⋆ , ( P C − I p ) Σ ⟩ + ⟨ B ⋆ , Δ R δ Σ ⟩ } 2 ] .
Exact community smoothness, P C B ⋆ = B ⋆ P_CB^\star=B^\star P C B ⋆ = B ⋆ , removes the first term, but not necessarily the second. Thus B ⋆ B^\star B ⋆ determines which information averaging must preserve, while σ \sigma σ and δ \delta δ jointly determine the subject-specific neighborhoods and their noise propagation. We also note that strong concentration relative to the threshold margins makes the oracle nearly fixed, unable to improve optimized prediction (Proposition 5). Clear communities and an aligned target therefore do not alone guarantee a gain. Concrete examples for community-strength and single-edge targets are given in Appendix § 9 .5.1.
We now ask whether a graph estimated from an independent sample of the same subject keeps the gain of the oracle.
Result 2: Graph estimation error. Replacing the oracle with a graph estimated from an independent sample adds a graph-estimation error bound E ( T , δ ) \mathcal{E}(T,\delta) E ( T , δ ) that vanishes with the probability of an edge error. The independent graph still improves on the raw features when this bound is smaller than the gain of the oracle. Recovering the community partition shared by all subjects is not enough, because the gain comes from the subject-specific neighborhoods.
The independent graph thresholds a second estimate of the same connectome, A j k ⊥ ( δ ) = 1 { Σ ^ j k ⊥ > δ } A_{jk}^{\perp}(\delta)=\mathbb{1}\{\widehat{\Sigma}_{jk}^{\perp}>\delta\} A j k ⊥ ( δ ) = 1 { Σ j k ⊥ > δ } with Σ ^ ⊥ = Σ + H ⊥ \widehat{\Sigma}^{\perp}=\Sigma+H^{\perp} Σ ⊥ = Σ + H ⊥ and H ⊥ ⊥ ⊥ H ∣ Σ H^{\perp}\perp\!\!\!\perp H\mid\Sigma H ⊥ ⊥ ⊥ H ∣ Σ . Its edges can be wrong, which adds graph-estimation error, but its noise is independent of the feature noise, so there is no double dipping.
Proposition 2 (Graph-estimation error for the independent graph). Under the assumptions of Proposition 1, let A ⊥ A^{\perp} A ⊥ be built from a conditionally independent copy H ⊥ H^{\perp} H ⊥ of H H H given Σ \Sigma Σ , and assume E Σ ∥ Σ ∥ F 2 < ∞ \mathbb{E}_{\Sigma}\|\Sigma\|_{F}^{2}<\infty E Σ ∥Σ ∥ F 2 < ∞ . Define the edge-error probability and the graph-estimation error:
ρ ( T , δ ) : = P ( A ⊥ ≠ A o r a c l e ) , E ( T , δ ) : = C ( 1 + T − 1 ) ρ ( T , δ ) , \rho(T,\delta):=\mathbb{P}(A^{\perp}\ne A^{\mathrm{oracle}}),\qquad\mathcal{E}(T,\delta):=C(1+T^{-1})\sqrt{\rho(T,\delta)}, ρ ( T , δ ) := P ( A ⊥ = A oracle ) , E ( T , δ ) := C ( 1 + T − 1 ) ρ ( T , δ ) , where C C C depends only on p p p , ∥ B ⋆ ∥ F \|B^{\star}\|_{F} ∥ B ⋆ ∥ F and E Σ ∥ Σ ∥ F 2 \mathbb{E}_{\Sigma}\|\Sigma\|_{F}^{2} E Σ ∥Σ ∥ F 2 , not on T T T or δ \delta δ . Then, for every T > 0 T>0 T > 0 ,
MSE i n d ( T , δ ) − MSE r a w ( T ) ≤ B A o r a c l e ( δ ) − Δ V A o r a c l e ( δ ) T + E ( T , δ ) + r r a w ( T ) . \operatorname{MSE}_{\mathrm{ind}}(T,\delta)-\operatorname{MSE}_{\mathrm{raw}}(T)\le B_{A^{\mathrm{oracle}}}(\delta)-\frac{\Delta V_{A^{\mathrm{oracle}}}(\delta)}{T}+\mathcal{E}(T,\delta)+r_{\mathrm{raw}}(T). MSE ind ( T , δ ) − MSE raw ( T ) ≤ B A oracle ( δ ) − T Δ V A oracle ( δ ) + E ( T , δ ) + r raw ( T ) . Thus the independent graph improves whenever B A o r a c l e ( δ ) + E ( T , δ ) + r r a w ( T ) < Δ V A o r a c l e ( δ ) / T B_{A^{\mathrm{oracle}}}(\delta)+\mathcal{E}(T,\delta)+r_{\mathrm{raw}}(T)<\Delta V_{A^{\mathrm{oracle}}}(\delta)/T B A oracle ( δ ) + E ( T , δ ) + r raw ( T ) < Δ V A oracle ( δ ) / T .
For μ B < δ < μ W \mu_{B}<\delta<\mu_{W} μ B < δ < μ W , graph estimation must recover the subject-specific neighborhoods P C + Δ R δ P_{C}+\Delta R_{\delta} P C + Δ R δ . The target B ⋆ B^{\star} B ⋆ determines how much a wrong edge costs, while δ \delta δ and σ \sigma σ determine how often one occurs. An edge is wrong when the noise in Σ ^ j k \widehat{\Sigma}_{jk} Σ j k , of size v / T \sqrt{v/T} v / T , exceeds the margin γ δ \gamma_{\delta} γ δ between δ \delta δ and the nearest community mean, where v v v bounds the scaled noise variance T Var η ( H j k ∣ Σ ) = Σ j j Σ k k + Σ j k 2 T\operatorname{Var}_{\eta}(H_{jk}\mid\Sigma)=\Sigma_{jj}\Sigma_{kk}+\Sigma_{jk}^{2} T Var η ( H j k ∣ Σ ) = Σ j j Σ k k + Σ j k 2 . Hence, when communities are well separated, ρ \rho ρ decays exponentially in T / T g r a p h ( δ ) T/T_{\mathrm{graph}}(\delta) T / T graph ( δ ) , with T g r a p h ( δ ) = v / γ δ 2 T_{\mathrm{graph}}(\delta)=v/\gamma_{\delta}^{2} T graph ( δ ) = v / γ δ 2 (Appendix A.5.2). Graph estimation is therefore reliable only once T ≫ T g r a p h ( δ ) T\gg T_{\mathrm{graph}}(\delta) T ≫ T graph ( δ ) . Edge errors of this kind are visible in data: thresholded connectivity graphs built from short recordings contain spurious between-network edges. Longer recordings improve edge estimation but also reduce the raw-feature noise that smoothing aims to remove, so the gain is confined to an intermediate range of T T T .
Result 3: Double-dipping effect. Using the same sample for graph and features adds a signed coupling term D d d ( T , δ ) D_{\mathrm{dd}}(T,\delta) D dd ( T , δ ) to the constraints of Result 2. When measurement noise rarely changes the oracle graph and the fitted regression coefficients remain bounded, the same-sample and independent graphs have similar prediction errors. The sign of D d d D_{\mathrm{dd}} D dd depends on the target.
The same-sample graph A j k b ( δ ) = 1 { Σ ^ j k b > δ } A_{jk}^{b}(\delta) = \mathbb{1}\{\widehat{\Sigma}_{jk}^{b} > \delta\} A j k b ( δ ) = 1 { Σ j k b > δ } uses the same noise H H H for edge selection and feature construction. We treat double dipping as a signed contribution because reusing the sample can either improve or worsen prediction compared with using an independent graph.
Proposition 3 (Double-dipping contribution for the same-sample graph). Under the assumptions of Proposition 2, define the double-dipping contribution D d d ( T , δ ) : = M S E s a m e ( T , δ ) − M S E i n d ( T , δ ) D_{\mathrm{dd}}(T,\delta) := \mathrm{MSE}_{\mathrm{same}}(T,\delta)-\mathrm{MSE}_{\mathrm{ind}}(T,\delta) D dd ( T , δ ) := MSE same ( T , δ ) − MSE ind ( T , δ ) . Then, for every T > 0 T > 0 T > 0 ,
M S E s a m e ( T , δ ) − M S E r a w ( T ) ≤ B A o r a c l e ( δ ) − Δ V A o r a c l e ( δ ) T + E ( T , δ ) + D d d ( T , δ ) + r r a w ( T ) . \mathrm{MSE}_{\mathrm{same}}(T,\delta)-\mathrm{MSE}_{\mathrm{raw}}(T) \le\mathcal{B}^{\mathrm{oracle}}_{A}(\delta)-\frac{\Delta\mathcal{V}^{\mathrm{oracle}}_{A}(\delta)}{T}+\mathcal{E}(T,\delta)+D_{\mathrm{dd}}(T,\delta)+r_{\mathrm{raw}}(T). MSE same ( T , δ ) − MSE raw ( T ) ≤ B A oracle ( δ ) − T Δ V A oracle ( δ ) + E ( T , δ ) + D dd ( T , δ ) + r raw ( T ) . Thus the same-sample graph improves whenever B A o r a c l e ( δ ) + E ( T , δ ) + D d d ( T , δ ) + r r a w ( T ) < Δ V A o r a c l e ( δ ) / T \mathcal{B}^{\mathrm{oracle}}_{A}(\delta)+\mathcal{E}(T,\delta)+D_{\mathrm{dd}}(T,\delta)+r_{\mathrm{raw}}(T)<\Delta\mathcal{V}^{\mathrm{oracle}}_{A}(\delta)/T B A oracle ( δ ) + E ( T , δ ) + D dd ( T , δ ) + r raw ( T ) < Δ V A oracle ( δ ) / T . The contribution D d d D_{\mathrm{dd}} D dd is signed: negative values favor the same-sample graph.
The two graphs have the same conditional law given Σ \Sigma Σ (Lemma 2), so D d d D_{\mathrm{dd}} D dd isolates noise reuse, not graph quality. For intermediate thresholds both estimate P C + Δ R δ \mathrm{PC}+\Delta R_{\delta} PC + Δ R δ , and genuine subject-specific variation is not double dipping. Under additional moment and spectral assumptions (Appendix A.5.3), ∣ D d d ∣ ≤ C d d p ρ / T \lvert D_{\mathrm{dd}}\rvert\le C_{\mathrm{dd}}p\rho/T ∣ D dd ∣ ≤ C dd pρ / T . Double dipping therefore vanishes at δ = ± ∞ \delta= \pm\infty δ = ± ∞ and is small whenever edge errors are rare, for instance once T ≫ T g r a p h ( δ ) T \gg T_{\mathrm{graph}}(\delta) T ≫ T graph ( δ ) with well-separated communities. In the intermediate regime an independent graph and same-sample graph have similar behavior.
Simulations
We validate the theoretical predictions of Section 4 under controlled conditions where the ground-truth covariance Σ ( i ) \Sigma^{(i)} Σ ( i ) is known. We generate synthetic data from the latent community model (Appendix A.4) to study how the five feature maps from Section 3 behave as we vary the community structure, the predictive signal, and the threshold. As in the theoretical proofs, we use balanced communities with fixed orthogonal centroids and fixed latent dimension, so that the main latent-structure knob is the subject-level variability σ \sigma σ : small σ \sigma σ gives strongly clustered connectomes, while large σ \sigma σ weakens the community structure. For each subject, we sample a time series of length T T T , compute Σ ^ ( i ) \widehat{\Sigma}^{(i)} Σ ( i ) (deferring results for C ^ ( i ) \widehat{C}^{(i)} C ( i ) to Appendix B), and evaluate the various feature maps at threshold level δ \delta δ : raw, oracle graph, independent graph, same-sample graph, and population graph. Each fit is by OLS with an intercept on standardized features (80/20 train/test split). The dependent variable is generated using regression coefficients that span a range of favorability to graph smoothing.
Results. We disentangle the three effects of Section 4 as gaps between the feature maps { Σ ^ , R ( A o r a c l e ) Σ ^ , R ( A ⊥ ) Σ ^ , R ( A ) Σ ^ , R ( A p o p ) Σ ^ } \{\widehat{\Sigma}, R(A^{\mathrm{oracle}})\widehat{\Sigma}, R(A^{\perp})\widehat{\Sigma}, R(A)\widehat{\Sigma}, R(A^{\mathrm{pop}})\widehat{\Sigma}\} { Σ , R ( A oracle ) Σ , R ( A ⊥ ) Σ , R ( A ) Σ , R ( A pop ) Σ } , normalized by the oracle MSE.
We start by isolating the graph smoothing effect. The population graph A p o p A^{\mathrm{pop}} A pop tracks Σ ^ \widehat{\Sigma} Σ closely in Figure 3 , consistent with Proposition 5, so the relevant comparison is A o r a c l e A^{\mathrm{oracle}} A oracle vs. raw. Proposition 1 predicts a bias-variance tradeoff whose benefit is confined to small T T T whenever the noiseless smoothed features leave residual error, and Figure 3 confirms this: for the community-smooth target (red overlay), B A o r a c l e ( δ ) \mathcal{B}_{A}^{\mathrm{oracle}}(\delta) B A oracle ( δ ) is small and R ( A o r a c l e ) Σ ^ R(A^{\mathrm{oracle}})\widehat{\Sigma} R ( A oracle ) Σ improves prediction across all T T T ; for the within-community contrast (blue overlay), smoothing averages together the ROIs whose difference is predictive, so the oracle helps only at small T T T . Increasing σ \sigma σ from 0.5 to 1.0 spreads the entries around the community levels and narrows the oracle gain. The threshold δ \delta δ modulates this gain: at sparse, high-margin thresholds the oracle preserves the community structure and the smoothing benefit is maximal, while as δ \delta δ moves toward the bulk the graph densifies and the oracle gain vanishes (Figure 4 , right).
Figure 4. Decoupling the effect of the threshold δ \delta δ . Each panel fixes a different threshold δ \delta δ on Σ \Sigma Σ and plots normalized ValMSE vs. T T T for SageMean( A , Σ ^ ) (A,\widehat{\Sigma}) ( A , Σ ) and the no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. β = community_aligned \beta= \texttt{community\_aligned} β = community_aligned , σ = 1.0 \sigma= 1.0 σ = 1.0 , p = 20 p = 20 p = 20 , K = 5 K = 5 K = 5 , n = 25,000 n = 25{,}000 n = 25 , 000 .
We next turn to the graph-estimation error, comparing A ⊥ A^{\perp} A ⊥ to A o r a c l e A^{\mathrm{oracle}} A oracle . When the oracle does not help, A ⊥ A^{\perp} A ⊥ tracks A o r a c l e A^{\mathrm{oracle}} A oracle trivially. When it does (top-left panel, Figure 3 ), a large fraction of the oracle gain is lost to mis-estimated edges, matching Proposition 2. Figure 4 traces this dependence in δ \delta δ : at a sparse, high-margin threshold (left), A o r a c l e A^{\mathrm{oracle}} A oracle delivers a large gain and A ⊥ A^{\perp} A ⊥ recovers part of it; as δ \delta δ moves toward the bulk (right), the graph approaches complete and the oracle ceases to help (Proposition 5 ).
Finally, the double-dipping effect is captured by the gap between A ^ \widehat{A} A and A ⊥ A^{\perp} A ⊥ . Across Figure 4 , R ( A ^ ) Σ ^ R(\widehat{A})\widehat{\Sigma} R ( A ) Σ tracks R ( A ⊥ ) Σ ^ R(A^{\perp})\widehat{\Sigma} R ( A ⊥ ) Σ closely, consistent with the high-margin regime of Proposition 3 where few entries of Σ \Sigma Σ lie within one Wishart noise scale of δ \delta δ . Pipelines with thresholds closer to the bulk, or weaker community separation, may incur a larger signed coupling penalty.
Extensions and additional results, including application to correlation matrices as well as tests of robustness under departures from the i.i.d. sampling assumption and at finite sample sizes, are presented in Appendix § 10 .
Real-data controlled experiments
We now show that the theoretical findings, already validated in the simulations, extend to real data. The traditional brain connectomics pipeline [3 , 2 ] is employed. From each subject’s ROI time series we extract rolling windows of length T T T and compute the per-window sample correlation matrix C ^ ( i ) \widehat{C}^{(i)} C ( i ) , which serves both as the node feature matrix and as the basis for graph construction; the correlation rather than the covariance matrix is used to stay close to practice. Thresholding it yields the four graphs of § 3 : A ^ \widehat{A} A from the same window (the standard pipeline), A e s t ⊥ A^{\perp}_{\mathrm{est}} A est ⊥ from an independent window of the same subject, A e s t o r a c l e A^{\mathrm{oracle}}_{\mathrm{est}} A est oracle from the full-length series (a low-noise proxy for the unobserved oracle), and the population graph A p o p A^{\mathrm{pop}} A pop . Each graph is paired with the same minimal architecture: a single convolution followed by an activation (identity or ReLU) and a readout (mean or vectorization).
Real data depart from the assumptions of the theory and the simulations. Table 2 retains three of them, which Appendix C relaxes one at a time. First, the theory treats R ( A ) R(A) R ( A ) as linear, whereas practice applies a non-linearity; we compare identity and ReLU activations. Second, n n n is finite and, with rolling windows, grows as T T T shrinks; we hold n n n fixed across T T T , isolating the window length, or let it vary as in practice. Third, the theory regresses on vectorized features, whereas practice pools node embeddings; we compare both readouts. In every experiment the oracle and independent graphs are estimated and training is regularized.
Table 2. Decoupling the effects on real data. Subject-level test accuracy for autism diagnosis on ABIDE (Harvard-Oxford, p = 106 p = 106 p = 106 ) with SageMean(A A A , C ^ \widehat{C} C ), one convolution, identity activation, n n n fixed across T T T , τ = 0.10 \tau= 0.10 τ = 0.10 . Mean ± 1 \pm1 ± 1 SD over 20 seeds; paired t t t -test over seeds against C ^ \widehat{C} C (left) or zero (right): ∗ p < 0.10 ^{*}p < 0.10 ∗ p < 0.10 , ∗ ∗ p < 0.05 ^{**}p < 0.05 ∗∗ p < 0.05 , ∗ ∗ ∗ p < 0.01 ^{***}p < 0.01 ∗∗∗ p < 0.01 . The majority-class predictor has accuracy 0.50.
Table 2 reproduces the simulation ordering on real data. The proxy oracle A e s t o r a c l e A^{\mathrm{oracle}}_{\mathrm{est}} A est oracle improves on the raw features at T = 5 T = 5 T = 5 and T = 25 T = 25 T = 25 but not at T = 40 T = 40 T = 40 , so the favorable window closes at finite T T T (Proposition 1); the population graph A p o p A^{\mathrm{pop}} A pop , shared by all subjects, never helps. Graph-estimation error is significant at every T T T and cancels the oracle gain (Proposition 2), whereas the double-dipping term is small, of no consistent sign and comparable to the estimation loss only at T = 40 T = 40 T = 40 (Proposition 3), so the same-sample graph never beats the raw features.
Table 5 in Appendix C relaxes these three assumptions cumulatively, and Tables 6 to 9 repeat the analysis with GAT, two other thresholds and two more datasets. The ReLU weakens the oracle gain without removing it, while freeing n n n removes it from T = 15 T = 15 T = 15 on and strengthens it at T = 5 T = 5 T = 5 , where short windows yield the most samples. Mean pooling then removes the gain left at T = 5 T = 5 T = 5 , so in the deployed pipeline no graph improves significantly on the raw features at any T T T , as in Figure 1 .
Conclusions
Contributions. We framed message passing on brain connectomes as an errors-in-variables regression and split its effect on prediction into three parts: graph smoothing, graph estimation error and double dipping. Under a latent community model, we showed how each part depends on the community structure, the predictive signal and the threshold. Even with the oracle graph, convolution helps only when its noise reduction outweighs the signal it distorts, which confines the gain to short recordings, and a graph shared by all subjects can never help. Simulations with the oracle, independent and same-sample graphs isolate each effect and confirm these predictions. On real data, proxies for the oracle and independent graphs reproduce the same picture: the proxy oracle improves on the raw correlation matrix at short windows and the gain disappears as T T T grows, the population graph never helps, most of the oracle gain is lost to graph-estimation error, and double dipping stays small. This answers the question we started from: the standard pipeline fails to beat graph-agnostic methods because the graph it can estimate from a short window is too noisy to deliver the smoothing gain that the true graph would offer.
Limitations: from simulations to real data. Our theory is stated for a linear model in the population scenario (n → ∞ n \to\infty n → ∞ ), the most favorable case for graph convolutions. Like the simulations, it relies on strict assumptions chosen to keep the mathematics tractable. ReLU and attention fall outside the linear theory but leave the real-data picture unchanged; a theory for them, for finite samples and for richer connectomes is left to future work. For the same reason, we do not provide an explicit rule for computing the minimum threshold on T T T . Finally, alternative methods for estimating the graph, beyond simple thresholding, are a relevant direction for future work.
Acknowledgments
Part of this work was done while T.C. and J.L. were at the Department of Statistics, University of Chicago. C.D. would like to acknowledge support for this project from the National Science Foundation (NSF grant IIS-2238616). J.L. would like to thank the support for this project from the National Science Foundation (NSF grant DMS-2515926). This work was completed in part with resources provided by the University of Chicago’s Research Computing Center.
Full theoretical analysis
Technical preliminaries
We state important definitions and technical preliminaries that we build on in the results that follow.
Lemma 1 (Wishart noise moments). Let Σ ∈ R p × p \Sigma\in\mathbb{R}^{p \times p} Σ ∈ R p × p be a positive-definite covariance matrix and let m Σ ^ ∼ W p ( m , Σ ) m\widehat{\Sigma} \sim W_p(m,\Sigma) m Σ ∼ W p ( m , Σ ) [32 ] . Then Σ ^ = Σ + H \widehat{\Sigma} = \Sigma+ H Σ = Σ + H with:
E η [ H j k ∣ Σ ] = 0 E_{\eta}[H_{jk} \mid\Sigma] = 0 E η [ H j k ∣ Σ ] = 0 ,
Cov η ( H j k , H l m ∣ Σ ) = Σ j l Σ k m + Σ j m Σ k l m \operatorname{Cov}_{\eta}(H_{jk}, H_{lm} \mid\Sigma) = \frac{\Sigma_{jl}\Sigma_{km} + \Sigma_{jm}\Sigma_{kl}}{m} Cov η ( H j k , H l m ∣ Σ ) = m Σ j l Σ k m + Σ j m Σ k l .
Next, we show that A ^ \widehat{A} A and A ⊥ A^{\perp} A ⊥ have the same marginal graph distribution. Their difference is the dependence between A ^ \widehat{A} A and the feature noise; see Proposition 3, where we isolate the remaining difference, namely their joint distribution with the feature noise.
Lemma 2 (Marginal equivalence). Let A ^ ( i ) = 1 { Σ ^ ( i ) > δ } \widehat{A}^{(i)} = \mathbb{1}\{\widehat{\Sigma}^{(i)} > \delta\} A ( i ) = 1 { Σ ( i ) > δ } and A ⊥ ( i ) = 1 { Σ ^ ⊥ ( i ) > δ } A^{\perp(i)} = \mathbb{1}\{\widehat{\Sigma}^{\perp(i)} > \delta\} A ⊥ ( i ) = 1 { Σ ⊥ ( i ) > δ } , where Σ ^ ⊥ ( i ) = Σ ( i ) + H ⊥ ( i ) \widehat{\Sigma}^{\perp(i)} = \Sigma^{(i)} + H^{\perp(i)} Σ ⊥ ( i ) = Σ ( i ) + H ⊥ ( i ) with H ⊥ ( i ) ⊥ ⊥ H ( i ) ∣ Σ ( i ) H^{\perp(i)} \perp\!\!\!\perp H^{(i)} \mid\Sigma^{(i)} H ⊥ ( i ) ⊥ ⊥ H ( i ) ∣ Σ ( i ) and H ⊥ ( i ) = d H ( i ) ∣ Σ ( i ) H^{\perp(i)} \overset{\mathrm{d}}{=} H^{(i)} \mid\Sigma^{(i)} H ⊥ ( i ) = d H ( i ) ∣ Σ ( i ) . Then:
A ^ ( i ) \widehat{A}^{(i)} A ( i ) and A ⊥ ( i ) A^{\perp(i)} A ⊥ ( i ) have the same conditional distribution given Σ ( i ) \Sigma^{(i)} Σ ( i ) .
A ⊥ ( i ) ⊥ ⊥ H ( i ) ∣ Σ ( i ) A^{\perp(i)} \perp\!\!\!\perp H^{(i)} \mid\Sigma^{(i)} A ⊥ ( i ) ⊥ ⊥ H ( i ) ∣ Σ ( i ) , whereas A ^ ( i ) \widehat{A}^{(i)} A ( i ) depends on H ( i ) H^{(i)} H ( i ) through the shared thresholding.
Consequently, all marginal quantities (edge probabilities, expected neighbor counts, expected degree) are identical for A ^ \widehat{A} A and A ⊥ A^{\perp} A ⊥ . The two differ only in their joint distribution with the feature noise η = vec ( H ) \eta= \operatorname{vec}(H) η = vec ( H ) .
With vec stacking columns, vec ( A B C ) = ( C T ⊗ A ) vec ( B ) \operatorname{vec}(ABC) = (C^{\mathsf{T}} \otimes A)\operatorname{vec}(B) vec ( A B C ) = ( C T ⊗ A ) vec ( B ) ; in particular, vec ( R Σ ^ ) = ( I p ⊗ R ) vec ( Σ ^ ) \operatorname{vec}(R\widehat{\Sigma}) = (I_p \otimes R)\operatorname{vec}(\widehat{\Sigma}) vec ( R Σ ) = ( I p ⊗ R ) vec ( Σ ) . We also define the commutation matrix as it plays a crucial role when working with vectorized covariance matrices.
Definition 1 (Commutation matrix). The commutation matrix K p , p ∈ R p 2 × p 2 K_{p,p} \in\mathbb{R}^{p^2 \times p^2} K p , p ∈ R p 2 × p 2 is the unique permutation matrix satisfying K p , p vec ( A ) = vec ( A T ) K_{p,p}\operatorname{vec}(A) = \operatorname{vec}(A^{\mathsf{T}}) K p , p vec ( A ) = vec ( A T ) for every A ∈ R p × p A \in\mathbb{R}^{p \times p} A ∈ R p × p [33 ] .
Writing Ψ ( Σ ) : = ( I p 2 + K p , p ) ( Σ ⊗ Σ ) \Psi(\Sigma) := (I_{p^2} + K_{p,p})(\Sigma\otimes\Sigma) Ψ ( Σ ) := ( I p 2 + K p , p ) ( Σ ⊗ Σ ) , from Lemma 1, we note:
K p , p K_{p,p} K p , p is symmetric and involutory (i.e. K p , p 2 = I p 2 K_{p,p}^{2} = I_{p^2} K p , p 2 = I p 2 ), and K p , p ( B ⊗ C ) = ( C ⊗ B ) K p , p K_{p,p}(B \otimes C) = (C \otimes B)K_{p,p} K p , p ( B ⊗ C ) = ( C ⊗ B ) K p , p for all B , C ∈ R p × p B,C \in\mathbb{R}^{p \times p} B , C ∈ R p × p [33 ] ; in particular K p , p K_{p,p} K p , p commutes with Σ ⊗ Σ \Sigma\otimes\Sigma Σ ⊗ Σ , so Ψ ( Σ ) \Psi(\Sigma) Ψ ( Σ ) is symmetric.
Ψ ( Σ ) ⪰ 0 \Psi(\Sigma) \succeq0 Ψ ( Σ ) ⪰ 0 , since T − 1 Ψ ( Σ ) T^{-1}\Psi(\Sigma) T − 1 Ψ ( Σ ) is a conditional covariance matrix (Lemma 1).
Ψ ( Σ ) vec ( W ) = 0 \Psi(\Sigma)\operatorname{vec}(W) = 0 Ψ ( Σ ) vec ( W ) = 0 for every antisymmetric W = − W T W = -W^{\mathsf{T}} W = − W T : indeed Σ W Σ \Sigma W \Sigma Σ W Σ is again antisymmetric, and ( I p 2 + K p , p ) vec ( M ) = vec ( M ) + vec ( M T ) = 0 (I_{p^2} + K_{p,p})\operatorname{vec}(M) = \operatorname{vec}(M) + \operatorname{vec}(M^{\mathsf{T}}) = 0 ( I p 2 + K p , p ) vec ( M ) = vec ( M ) + vec ( M T ) = 0 for antisymmetric M M M . Hence Ψ ( Σ ) \Psi(\Sigma) Ψ ( Σ ) is singular, with rank Ψ ( Σ ) ≤ p ( p + 1 ) / 2 \Psi(\Sigma) \leq p(p+1)/2 Ψ ( Σ ) ≤ p ( p + 1 ) /2 .
Statistical framework
For each subject i = 1 , … , n i = 1,\ldots,n i = 1 , … , n , the centered time series Z ( i ) ∈ R T × p Z^{(i)} \in\mathbb{R}^{T \times p} Z ( i ) ∈ R T × p has rows Z t ( i ) ∼ i . i . d . N ( 0 , Σ ( i ) ) Z_t^{(i)} \overset{\mathrm{i.i.d.}}{\sim} N(0,\Sigma^{(i)}) Z t ( i ) ∼ i.i.d. N ( 0 , Σ ( i ) ) , t = 1 , … , T t = 1,\ldots,T t = 1 , … , T , and we observe the empirical covariance
Σ ^ ( i ) = 1 T ∑ t = 1 T Z t ( i ) Z t ( i ) T = Σ ( i ) + H ( i ) . \widehat{\Sigma}^{(i)} = \frac{1}{T}\sum_{t=1}^{T} Z_t^{(i)}Z_t^{(i)\mathsf{T}} = \Sigma^{(i)} + H^{(i)}. Σ ( i ) = T 1 t = 1 ∑ T Z t ( i ) Z t ( i ) T = Σ ( i ) + H ( i ) .
The analysis is in the population regime, n → ∞ n \to\infty n → ∞ . Let
x : = vec ( Σ ) , x ^ : = vec ( Σ ^ ) = x + η , η : = vec ( H ) . x := \operatorname{vec}(\Sigma), \qquad\widehat{x} := \operatorname{vec}(\widehat{\Sigma}) = x + \eta, \qquad\eta:= \operatorname{vec}(H). x := vec ( Σ ) , x := vec ( Σ ) = x + η , η := vec ( H ) .
By Lemma 1,
E η [ η ∣ Σ ] = 0 , Cov η ( η ∣ Σ ) = T − 1 Ψ ( Σ ) , Ψ ( Σ ) : = ( I p 2 + K p , p ) ( Σ ⊗ Σ ) . E_{\eta}[\eta\mid\Sigma] = 0, \qquad\operatorname{Cov}_{\eta}(\eta\mid\Sigma) = T^{-1}\Psi(\Sigma), \qquad\Psi(\Sigma) := (I_{p^2} + K_{p,p})(\Sigma\otimes\Sigma). E η [ η ∣ Σ ] = 0 , Cov η ( η ∣ Σ ) = T − 1 Ψ ( Σ ) , Ψ ( Σ ) := ( I p 2 + K p , p ) ( Σ ⊗ Σ ) .
The demeaned estimator has T − 1 T-1 T − 1 degrees of freedom; every statement below holds with T − 1 T-1 T − 1 in place of T T T . The target depends on the latent connectome, Y = f ⋆ ( Σ ) + ε Y=f^\star(\Sigma)+\varepsilon Y = f ⋆ ( Σ ) + ε , with ε \varepsilon ε independent of ( Σ , H ) (\Sigma,H) ( Σ , H ) and of any randomness used to build a graph, and E Σ ∥ Σ ∥ F 2 < ∞ \mathbb{E}_{\Sigma}\lVert\Sigma\rVert_{F}^{2}<\infty E Σ ∥ Σ ∥ F 2 < ∞ . We restrict f ⋆ f^\star f ⋆ to the linear class F = { x ↦ x T θ } \mathcal{F}=\{x\mapsto x^{\mathsf{T}}\theta\} F = { x ↦ x T θ } , so that
Y = h ( Σ ) + ε , h ( Σ ) : = x T β ⋆ = ⟨ Σ , B ⋆ ⟩ , vec ( B ⋆ ) = β ⋆ , ε ∼ N ( 0 , σ ε 2 ) , Y=h(\Sigma)+\varepsilon,\qquad h(\Sigma):=x^{\mathsf{T}}\beta^\star=\langle\Sigma,B^\star\rangle,\qquad\operatorname{vec}(B^\star)=\beta^\star,\qquad\varepsilon\sim N(0,\sigma_{\varepsilon}^{2}), Y = h ( Σ ) + ε , h ( Σ ) := x T β ⋆ = ⟨ Σ , B ⋆ ⟩ , vec ( B ⋆ ) = β ⋆ , ε ∼ N ( 0 , σ ε 2 ) ,
with B ⋆ B^\star B ⋆ symmetric without loss of generality, since ⟨ Σ , B ⋆ ⟩ \langle\Sigma,B^\star\rangle ⟨ Σ , B ⋆ ⟩ only sees the symmetric part of B ⋆ B^\star B ⋆ .
Since Σ ^ \widehat{\Sigma} Σ is symmetric, the second-moment matrix of x ~ \widetilde{x} x and the Gram matrices below are singular by Definition 1; all inverses are Moore–Penrose pseudo-inverses. For the raw feature map x ~ \widetilde{x} x we write
S 0 : = E Σ [ x ~ x ~ T ] , Γ 0 : = E Σ [ Ψ ( Σ ) ] , c 0 : = E Σ [ x ~ h ( Σ ) ] = S 0 β ⋆ . S_0:=\mathbb{E}_{\Sigma}[\widetilde{x}\widetilde{x}^{\mathsf{T}}],\qquad\Gamma_0:=\mathbb{E}_{\Sigma}[\Psi(\Sigma)],\qquad c_0:=\mathbb{E}_{\Sigma}[\widetilde{x}h(\Sigma)]=S_0\beta^\star. S 0 := E Σ [ x x T ] , Γ 0 := E Σ [ Ψ ( Σ )] , c 0 := E Σ [ x h ( Σ )] = S 0 β ⋆ .
Thus
MSE r a w ( T ) = E Σ [ h ( Σ ) 2 ] − c 0 T ( S 0 + T − 1 Γ 0 ) † c 0 + σ ε 2 . \operatorname{MSE}_{\mathrm{raw}}(T)=\mathbb{E}_{\Sigma}[h(\Sigma)^2]-c_0^{\mathsf{T}}(S_0+T^{-1}\Gamma_0)^\dagger c_0+\sigma_{\varepsilon}^{2}. MSE raw ( T ) = E Σ [ h ( Σ ) 2 ] − c 0 T ( S 0 + T − 1 Γ 0 ) † c 0 + σ ε 2 .
We now state and prove Remark 1, whose S , Γ S,\Gamma S , Γ are the S 0 , Γ 0 S_0,\Gamma_0 S 0 , Γ 0 above and whose MSE r a w ( T ) \operatorname{MSE}_{\mathrm{raw}}(T) MSE raw ( T ) is the display above written through Λ ( T ) \Lambda(T) Λ ( T ) .
A linear graph convolution replaces Σ ^ \widehat{\Sigma} Σ by R ( A ) Σ ^ R(A)\widehat{\Sigma} R ( A ) Σ , where A ∈ { 0 , 1 } p × p A\in\{0,1\}^{p\times p} A ∈ { 0 , 1 } p × p is a symmetric adjacency matrix and R ( A ) R(A) R ( A ) its message-passing operator; the layer X ′ = σ ( R ( A ) X W ) X^\prime=\sigma(R(A)XW) X ′ = σ ( R ( A ) X W ) with the weights and the activation removed. The smoothed feature map is
x ~ A : = vec ( R ( A ) Σ ^ ) = R A x ^ , R A : = I p ⊗ R ( A ) , \widetilde{x}_A:=\operatorname{vec}(R(A)\widehat{\Sigma})=\mathcal{R}_A\widehat{x},\qquad\mathcal{R}_A:=I_p\otimes R(A), x A := vec ( R ( A ) Σ ) = R A x , R A := I p ⊗ R ( A ) ,
and, for a graph A A A , MSE A ( T ) : = min γ E Σ , η , ε , A [ ( Y − γ T x ~ A ) 2 ] \operatorname{MSE}_A(T):=\min_{\gamma}\mathbb{E}_{\Sigma,\eta,\varepsilon,A}[(Y-\gamma^{\mathsf{T}}\widetilde{x}_A)^2] MSE A ( T ) := min γ E Σ , η , ε , A [( Y − γ T x A ) 2 ] is the optimized population risk, the object compared throughout; MSE r a w ( T ) \operatorname{MSE}_{\mathrm{raw}}(T) MSE raw ( T ) above is its value for the raw features x ~ \widetilde{x} x . For a binary adjacency matrix A A A , the SAGE mean-aggregation operator R = R ( A ) R=R(A) R = R ( A ) is
A ~ = A + I p , D ~ = diag ( A ~ 1 ) , R = D ~ − 1 A ~ . \widetilde{A}=A+I_p,\qquad\widetilde{D}=\operatorname{diag}(\widetilde{A}\mathbf{1}),\qquad R=\widetilde{D}^{-1}\widetilde{A}. A = A + I p , D = diag ( A 1 ) , R = D − 1 A .
We compare four graphs, thresholded entrywise off the diagonal at a fixed δ \delta δ :
the population graph A p o p = 1 { Σ 0 > δ } A^{\mathrm{pop}}=\mathbb{1}\{\Sigma_0>\delta\} A pop = 1 { Σ 0 > δ } , with Σ 0 = E Σ [ Σ ] \Sigma_0=\mathbb{E}_{\Sigma}[\Sigma] Σ 0 = E Σ [ Σ ] ;
the oracle graph A o r a c l e = 1 { Σ > δ } A^{\mathrm{oracle}}=\mathbb{1}\{\Sigma>\delta\} A oracle = 1 { Σ > δ } ;
the same-sample graph A ^ = 1 { Σ ^ > δ } \widehat{A}=\mathbb{1}\{\widehat{\Sigma}>\delta\} A = 1 { Σ > δ } ;
the independent graph A ⊥ = 1 { Σ ^ ⊥ > δ } A^\perp=\mathbb{1}\{\widehat{\Sigma}^{\perp}>\delta\} A ⊥ = 1 { Σ ⊥ > δ } , Σ ^ ⊥ = Σ + H ⊥ \widehat{\Sigma}^{\perp}=\Sigma+H^\perp Σ ⊥ = Σ + H ⊥ , with H ⊥ ⊥ H ∣ Σ H^\perp\perp H\mid\Sigma H ⊥ ⊥ H ∣ Σ and H ⊥ = d H ∣ Σ H^\perp\overset{d}{=}H\mid\Sigma H ⊥ = d H ∣ Σ .
General errors-in-variables analysis
Predicting from the smoothed features x ~ A = R A x ^ \widetilde{x}_{A}=\mathcal{R}_{A}\widehat{x} x A = R A x rather than from x ^ \widehat{x} x is still an errors-in-variables regression, now with the operator R A \mathcal{R}_{A} R A sitting between the noise and the coefficient. We characterize its population MSE without assumptions on Σ \Sigma Σ , B ⋆ B^{\star} B ⋆ or A A A , distinguishing the case where the graph is independent of the feature noise from the case where graph and features are derived from the same sample. The fixed-operator case, in which the graph does not vary across subjects, is treated separately: there message passing cannot improve on raw features.
Proposition 4. (Population MSE under message passing). For a graph A A A , let R ( A ) ∈ R p × p R(A)\in\mathbb{R}^{p\times p} R ( A ) ∈ R p × p denote its convolution operator (R ( A ) = D ~ − 1 A ~ R(A)=\widetilde{D}^{-1}\widetilde{A} R ( A ) = D − 1 A for GraphSAGE), R A : = I p ⊗ R ( A ) \mathcal{R}_{A}:=I_{p}\otimes R(A) R A := I p ⊗ R ( A ) the corresponding vectorized operator, so that vec ( R ( A ) Σ ^ ) = R A x ^ \operatorname{vec}(R(A)\widehat{\Sigma})=\mathcal{R}_{A}\widehat{x} vec ( R ( A ) Σ ) = R A x , and x ~ A : = R A ( x + η ) \widetilde{x}_{A}:=\mathcal{R}_{A}(x+\eta) x A := R A ( x + η ) the smoothed feature map, where h ( Σ ) : = vec ( Σ ) ⊤ β ⋆ h(\Sigma):=\operatorname{vec}(\Sigma)^{\top}\beta^{\star} h ( Σ ) := vec ( Σ ) ⊤ β ⋆ is the noiseless regression target and Ψ \Psi Ψ is as in Remark 1.
(a) Conditionally independent graph. Suppose A ⊥ ⊥ H ∣ Σ A\perp\!\!\!\perp H\mid\Sigma A ⊥ ⊥ H ∣ Σ , as for A p o p A^{\mathrm{pop}} A pop , A o r a c l e A^{\mathrm{oracle}} A oracle , and A ⊥ A^{\perp} A ⊥ , and ε ⊥ ⊥ ( Σ , η , A ) \varepsilon\perp\!\!\!\perp(\Sigma,\eta,A) ε ⊥ ⊥ ( Σ , η , A ) . Define
S A : = E Σ , A [ R A x x ⊤ R A ⊤ ] , Γ A : = E Σ , A [ R A Ψ R A ⊤ ] , c A : = E Σ , A [ R A x h ( Σ ) ] . S_{A}:=\mathbb{E}_{\Sigma,A}[\mathcal{R}_{A}xx^{\top}\mathcal{R}_{A}^{\top}],\qquad\Gamma_{A}:=\mathbb{E}_{\Sigma,A}[\mathcal{R}_{A}\Psi\mathcal{R}_{A}^{\top}],\qquad c_{A}:=\mathbb{E}_{\Sigma,A}[\mathcal{R}_{A}x h(\Sigma)]. S A := E Σ , A [ R A x x ⊤ R A ⊤ ] , Γ A := E Σ , A [ R A Ψ R A ⊤ ] , c A := E Σ , A [ R A x h ( Σ )] . Then the population OLS coefficient and test MSE are
β A ⋆ ( T ) = ( S A + T − 1 Γ A ) † c A , MSE A ( T ) = E Σ [ h ( Σ ) 2 ] − c A ⊤ ( S A + T − 1 Γ A ) † c A + σ ε 2 . \beta_{A}^{\star}(T)=(S_{A}+T^{-1}\Gamma_{A})^{\dagger}c_{A},\qquad\operatorname{MSE}_{A}(T)=\mathbb{E}_{\Sigma}[h(\Sigma)^{2}]-c_{A}^{\top}(S_{A}+T^{-1}\Gamma_{A})^{\dagger}c_{A}+\sigma_{\varepsilon}^{2}. β A ⋆ ( T ) = ( S A + T − 1 Γ A ) † c A , MSE A ( T ) = E Σ [ h ( Σ ) 2 ] − c A ⊤ ( S A + T − 1 Γ A ) † c A + σ ε 2 . (b) Same-sample graph. Suppose A = A ^ ( Σ ^ ) A=\widehat{A}(\widehat{\Sigma}) A = A ( Σ ) is the same-sample graph, so that R A ^ \mathcal{R}_{\widehat{A}} R A is Σ ^ \widehat{\Sigma} Σ -measurable and no longer independent of η \eta η given Σ \Sigma Σ , and ε ⊥ ⊥ ( Σ , η ) \varepsilon\perp\!\!\!\perp(\Sigma,\eta) ε ⊥ ⊥ ( Σ , η ) . Define M A ^ : = E Σ , η [ x ~ A ^ x ~ A ^ ⊤ ] M_{\widehat{A}}:=\mathbb{E}_{\Sigma,\eta}[\widetilde{x}_{\widehat{A}}\widetilde{x}_{\widehat{A}}^{\top}] M A := E Σ , η [ x A x A ⊤ ] , c A ^ : = E Σ , η [ x ~ A ^ h ( Σ ) ] c_{\widehat{A}}:=\mathbb{E}_{\Sigma,\eta}[\widetilde{x}_{\widehat{A}}h(\Sigma)] c A := E Σ , η [ x A h ( Σ )] . Then β A ^ ⋆ ( T ) = M A ^ † c A ^ \beta_{\widehat{A}}^{\star}(T)=M_{\widehat{A}}^{\dagger}c_{\widehat{A}} β A ⋆ ( T ) = M A † c A and MSE s a m e ( T ) = E Σ [ h ( Σ ) 2 ] − c A ^ ⊤ M A ^ † c A ^ + σ ε 2 \operatorname{MSE}_{\mathrm{same}}(T)=\mathbb{E}_{\Sigma}[h(\Sigma)^{2}]-c_{\widehat{A}}^{\top}M_{\widehat{A}}^{\dagger}c_{\widehat{A}}+\sigma_{\varepsilon}^{2} MSE same ( T ) = E Σ [ h ( Σ ) 2 ] − c A ⊤ M A † c A + σ ε 2 , where
M A ^ = E Σ , η [ R A ^ x x ⊤ R A ^ ⊤ ] + E Σ , η [ R A ^ x η ⊤ R A ^ ⊤ ] + E Σ , η [ R A ^ η x ⊤ R A ^ ⊤ ] + E Σ , η [ R A ^ η η ⊤ R A ^ ⊤ ] , M_{\widehat{A}}=\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}xx^{\top}\mathcal{R}_{\widehat{A}}^{\top}]+\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}x\eta^{\top}\mathcal{R}_{\widehat{A}}^{\top}]+\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}\eta x^{\top}\mathcal{R}_{\widehat{A}}^{\top}]+\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}\eta\eta^{\top}\mathcal{R}_{\widehat{A}}^{\top}], M A = E Σ , η [ R A x x ⊤ R A ⊤ ] + E Σ , η [ R A x η ⊤ R A ⊤ ] + E Σ , η [ R A η x ⊤ R A ⊤ ] + E Σ , η [ R A η η ⊤ R A ⊤ ] , with the middle two terms labelled cross terms , and
c A ^ = E Σ , η [ R A ^ x x ⊤ ] β ⋆ + E Σ , η [ R A ^ η x ⊤ ] β ⋆ . c_{\widehat{A}}=\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}xx^{\top}]\beta^{\star}+\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}\eta x^{\top}]\beta^{\star}. c A = E Σ , η [ R A x x ⊤ ] β ⋆ + E Σ , η [ R A η x ⊤ ] β ⋆ .
Proof of (a). Since A ⊥ ⊥ H ∣ Σ A\perp\!\!\!\perp H\mid\Sigma A ⊥ ⊥ H ∣ Σ and ε ⊥ ⊥ ( Σ , η , A ) \varepsilon\perp\!\!\!\perp(\Sigma,\eta,A) ε ⊥ ⊥ ( Σ , η , A ) , we have E η [ η ∣ Σ , A ] = 0 \mathbb{E}_{\eta}[\eta\mid\Sigma,A]=0 E η [ η ∣ Σ , A ] = 0 and Cov η ( η ∣ Σ , A ) = T − 1 Ψ \operatorname{Cov}_{\eta}(\eta\mid\Sigma,A)=T^{-1}\Psi Cov η ( η ∣ Σ , A ) = T − 1 Ψ . By the tower property,
E Σ , η , A [ x ~ A x ~ A ⊤ ] = S A + T − 1 Γ A , E Σ , η , ε , A [ x ~ A Y ] = c A , \mathbb{E}_{\Sigma,\eta,A}[\widetilde{x}_{A}\widetilde{x}_{A}^{\top}]=S_{A}+T^{-1}\Gamma_{A},\qquad\mathbb{E}_{\Sigma,\eta,\varepsilon,A}[\widetilde{x}_{A}Y]=c_{A}, E Σ , η , A [ x A x A ⊤ ] = S A + T − 1 Γ A , E Σ , η , ε , A [ x A Y ] = c A ,
and the normal equations ( S A + T − 1 Γ A ) γ = c A (S_{A}+T^{-1}\Gamma_{A})\gamma=c_{A} ( S A + T − 1 Γ A ) γ = c A are solvable as in Remark 1, and the minimal-norm solution ( S A + T − 1 Γ A ) † c A (S_{A}+T^{-1}\Gamma_{A})^{\dagger}c_{A} ( S A + T − 1 Γ A ) † c A yields MSE A ( T ) \operatorname{MSE}_{A}(T) MSE A ( T ) .
Proof of (b). The expansions follow by linearity from x ~ A ^ = R A ^ ( x + η ) \widetilde{x}_{\widehat{A}}=\mathcal{R}_{\widehat{A}}(x+\eta) x A = R A ( x + η ) , with E Σ , η , ε [ x ~ A ^ ε ] = 0 \mathbb{E}_{\Sigma,\eta,\varepsilon}[\widetilde{x}_{\widehat{A}}\varepsilon]=0 E Σ , η , ε [ x A ε ] = 0 . No term vanishes in the general case because R A ^ \mathcal{R}_{\widehat{A}} R A is not conditionally independent of η \eta η given Σ \Sigma Σ . The coefficient and MSE follow as in Remark 1. If R A ^ ⊥ ⊥ η ∣ Σ \mathcal{R}_{\widehat{A}}\perp\!\!\!\perp\eta\mid\Sigma R A ⊥ ⊥ η ∣ Σ , then E η [ η ∣ Σ , A ^ ] = 0 \mathbb{E}_{\eta}[\eta\mid\Sigma,\widehat{A}]=0 E η [ η ∣ Σ , A ] = 0 , so the cross terms and E Σ , η [ R A ^ η x ⊤ ] β ⋆ \mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}\eta x^{\top}]\beta^{\star} E Σ , η [ R A η x ⊤ ] β ⋆ vanish, while the tower property gives E Σ , η [ R A ^ η η ⊤ R A ^ ⊤ ] = T − 1 E Σ , η [ R A ^ Ψ R A ^ ⊤ ] \mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}\eta\eta^{\top}\mathcal{R}_{\widehat{A}}^{\top}]=T^{-1}\mathbb{E}_{\Sigma,\eta}[\mathcal{R}_{\widehat{A}}\Psi\mathcal{R}_{\widehat{A}}^{\top}] E Σ , η [ R A η η ⊤ R A ⊤ ] = T − 1 E Σ , η [ R A Ψ R A ⊤ ] , recovering case (a).
For the same-sample graph, the operator depends on the same noise used in the features. The previous cancellation no longer occurs.
Proposition 5. (No linear gain from fixed message passing). For any fixed R ∈ R p 2 × p 2 \mathcal{R}\in\mathbb{R}^{p^{2}\times p^{2}} R ∈ R p 2 × p 2 ,
F M P ( R ) : = { x ↦ θ ⊤ R x : θ ∈ R p 2 } ⊆ { x ↦ β ⊤ x : β ∈ R p 2 } = : F r a w , θ ⊤ R x = ( R ⊤ θ ) ⊤ x . \mathcal{F}_{\mathrm{MP}}(\mathcal{R}):=\{x\mapsto\theta^{\top}\mathcal{R}x:\theta\in\mathbb{R}^{p^{2}}\}\subseteq\{x\mapsto\beta^{\top}x:\beta\in\mathbb{R}^{p^{2}}\}=:\mathcal{F}_{\mathrm{raw}},\qquad\theta^{\top}\mathcal{R}x=(\mathcal{R}^{\top}\theta)^{\top}x. F MP ( R ) := { x ↦ θ ⊤ R x : θ ∈ R p 2 } ⊆ { x ↦ β ⊤ x : β ∈ R p 2 } =: F raw , θ ⊤ R x = ( R ⊤ θ ) ⊤ x . Consequently, for any loss ℓ \ell ℓ , including ℓ ( y , y ~ ) = ( y − y ~ ) 2 \ell(y,\widetilde{y})=(y-\widetilde{y})^{2} ℓ ( y , y ) = ( y − y ) 2 :
inf β E Y , x ℓ ( Y , β ⊤ x ) ≤ inf θ E Y , x ℓ ( Y , θ ⊤ R x ) . \inf_{\beta}\mathbb{E}_{Y,x}\ell(Y,\beta^{\top}x)\leq\inf_{\theta}\mathbb{E}_{Y,x}\ell(Y,\theta^{\top}\mathcal{R}x). β inf E Y , x ℓ ( Y , β ⊤ x ) ≤ θ inf E Y , x ℓ ( Y , θ ⊤ R x ) .
Proof. As θ \theta θ ranges over R p 2 \mathbb{R}^{p^{2}} R p 2 , R ⊤ θ \mathcal{R}^{\top}\theta R ⊤ θ ranges over range ( R ⊤ ) \operatorname{range}(\mathcal{R}^{\top}) range ( R ⊤ ) , so F M P ( R ) = { x ↦ β ⊤ x : β ∈ range ( R ⊤ ) } ⊆ F r a w \mathcal{F}_{\mathrm{MP}}(\mathcal{R})=\{x\mapsto\beta^{\top}x:\beta\in\operatorname{range}(\mathcal{R}^{\top})\}\subseteq\mathcal{F}_{\mathrm{raw}} F MP ( R ) = { x ↦ β ⊤ x : β ∈ range ( R ⊤ )} ⊆ F raw , and the infimum over a subset is at least the infimum over the set. For squared loss the raw minimizers form the solution set of E x [ x x ⊤ ] β = E Y , x [ x Y ] \mathbb{E}_{x}[xx^{\top}]\beta=\mathbb{E}_{Y,x}[xY] E x [ x x ⊤ ] β = E Y , x [ x Y ] (consistent, as in Remark 1); the inequality is strict iff this set is disjoint from range ( R ⊤ ) \operatorname{range}(\mathcal{R}^{\top}) range ( R ⊤ ) .
Corollary 1 (Equality when the fixed operator is invertible). If R \mathcal{R} R is invertible, then
F M P ( R ) = F r a w . \mathcal{F}_{\mathrm{MP}}(\mathcal{R})=\mathcal{F}_{\mathrm{raw}}. F MP ( R ) = F raw . Hence the optimal unregularized linear prediction risks are equal:
inf β E Y , x [ ( Y − β T x ) 2 ] = inf θ E Y , x [ ( Y − θ T R x ) 2 ] . \inf_{\beta}\mathbb{E}_{Y,x}\left[(Y-\beta^{\mathsf{T}}x)^2\right]=\inf_{\theta}\mathbb{E}_{Y,x}\left[(Y-\theta^{\mathsf{T}}\mathcal{R}x)^2\right]. β inf E Y , x [ ( Y − β T x ) 2 ] = θ inf E Y , x [ ( Y − θ T R x ) 2 ] . Proof. Proposition 5 gives
F M P ( R ) ⊆ F r a w . \mathcal{F}_{\mathrm{MP}}(\mathcal{R})\subseteq\mathcal{F}_{\mathrm{raw}}. F MP ( R ) ⊆ F raw . If R \mathcal{R} R is invertible, then for every β \beta β we may choose
θ = R − T β , \theta=\mathcal{R}^{-\mathsf{T}}\beta, θ = R − T β , so that
θ T R x = β T x . \theta^{\mathsf{T}}\mathcal{R}x=\beta^{\mathsf{T}}x. θ T R x = β T x . Therefore
F r a w ⊆ F M P ( R ) , \mathcal{F}_{\mathrm{raw}}\subseteq\mathcal{F}_{\mathrm{MP}}(\mathcal{R}), F raw ⊆ F MP ( R ) , and the two classes are identical.
Beyond Proposition 5, neither case of Proposition 4 yields a conclusion without assumptions: the population risks depend on three ingredients the propositions leave free. We fix each under the latent community model of Appendix § 9 .§ 4 and study their interaction as T T T varies.
Community structure, Σ \Sigma Σ . S S S , Γ = E Σ [ Ψ ( Σ ) ] \Gamma=\mathbb{E}_{\Sigma}[\Psi(\Sigma)] Γ = E Σ [ Ψ ( Σ )] and c c c , hence every MSE above, are functionals of the law of Σ \Sigma Σ : its community organization and subject-level variability decide what a neighborhood average can remove (Appendix § 9 .4.1).
Predictive signal, B ⋆ B^{\star} B ⋆ . The signal enters through R ( A ) T B ⋆ R(A)^{\mathsf{T}}B^{\star} R ( A ) T B ⋆ , so smoothing preserves it when B ⋆ B^{\star} B ⋆ is nearly constant over the averaged neighborhoods and distorts it when the signal lies in differences between entries: community-smooth versus edge or contrast targets (Appendix § 9 .4.3).
Graph and threshold, A A A and δ \delta δ . Which matrix is thresholded (Σ \Sigma Σ , Σ ^ ⊥ \widehat{\Sigma}^{\perp} Σ ⊥ , Σ ^ \widehat{\Sigma} Σ , Σ 0 \Sigma_0 Σ 0 ) fixes the coupling between graph and feature noise, the split of Proposition 4(a)/(b); the threshold δ \delta δ fixes the neighborhoods, so for graphs 1 { ⋅ > δ } \mathbf{1}\{\cdot>\delta\} 1 { ⋅ > δ } the structure reduces to the position of δ \delta δ relative to the between- and within-community levels of Σ \Sigma Σ (Appendix § 9 .4.2).
Latent community model
In order to get more insight into the intractable problem defined in the previous section, we place assumptions on all three ingredients at once: Σ \Sigma Σ is generated by a latent community model, δ \delta δ is set relative to its community levels, and B ⋆ B^{\star} B ⋆ is characterized by its alignment with the communities.
Community structure
We model the p p p ROIs through K ≤ min { p , d } K\leq\min\{p,d\} K ≤ min { p , d } latent communities [1 ] , motivated by low-dimensional representations of brain activity [14 , 15 , 16 ] . Let F ∈ R p × d F\in\mathbb{R}^{p\times d} F ∈ R p × d collect their latent loadings. The structural parameter is the subject-level variability σ \sigma σ ; all other model parameters are held fixed.
For each subject i i i , the connectome is generated as follows.
Node assignment: each ROI j j j belongs to z j ∈ { 1 , … , K } z_j\in\{1,\ldots,K\} z j ∈ { 1 , … , K } , with balanced communities ∣ C k ∣ = q = p / K ∈ N \lvert C_k\rvert=q=p/K\in\mathbb{N} ∣ C k ∣ = q = p / K ∈ N and C ( j ) : = C z j C(j):=C_{z_j} C ( j ) := C z j .
Community centroids: the vectors μ k ∈ R d \mu_k\in\mathbb{R}^{d} μ k ∈ R d are fixed across subjects, orthogonal, and satisfy ∥ μ k ∥ 2 = ϕ 2 d \lVert\mu_k\rVert^2=\phi^2d ∥ μ k ∥ 2 = ϕ 2 d .
Subject-level variability: ν j ( i ) ∼ N ( 0 , σ 2 I d ) \nu_j^{(i)}\sim\mathcal{N}(0,\sigma^2I_d) ν j ( i ) ∼ N ( 0 , σ 2 I d ) independently across ROIs and subjects.
Latent features: f j ( i ) = μ z j + ν j ( i ) f_j^{(i)}=\mu_{z_j}+\nu_j^{(i)} f j ( i ) = μ z j + ν j ( i ) , with f j ( i ) T f_j^{(i)\mathsf{T}} f j ( i ) T the j j j -th row of F ( i ) F^{(i)} F ( i ) .
Connectome: Σ ( i ) = F ( i ) F ( i ) T + ψ 2 I p \Sigma^{(i)}=F^{(i)}F^{(i)\mathsf{T}}+\psi^2I_p Σ ( i ) = F ( i ) F ( i ) T + ψ 2 I p .
We assume ϕ , ψ > 0 \phi,\psi>0 ϕ , ψ > 0 and σ ≥ 0 \sigma\geq0 σ ≥ 0 . All expectations below keep the partition and centroids fixed.
Lemma 3 (Community levels and fluctuations). For j ≠ k j \ne k j = k ,
E Σ Σ j k = { μ W : = ϕ 2 d , z j = z k , μ B : = 0 , z j ≠ z k , Var Σ ( Σ j k ) = s 2 : = 2 σ 2 ϕ 2 d + σ 4 d . \mathbb{E}_{\Sigma}\Sigma_{jk} =
\begin{cases}
\mu_W := \phi^2 d, & z_j = z_k,\\
\mu_B := 0, & z_j \ne z_k,
\end{cases}
\qquad
\operatorname{Var}_{\Sigma}(\Sigma_{jk}) = s^2 := 2\sigma^2\phi^2d+\sigma^4d. E Σ Σ j k = { μ W := ϕ 2 d , μ B := 0 , z j = z k , z j = z k , Var Σ ( Σ j k ) = s 2 := 2 σ 2 ϕ 2 d + σ 4 d . On the diagonal,
m D : = E Σ Σ j j = d ( ϕ 2 + σ 2 ) + ψ 2 , Var Σ ( Σ j j ) = 2 s 2 . m_D := \mathbb{E}_{\Sigma}\Sigma_{jj}=d(\phi^2+\sigma^2)+\psi^2,
\qquad
\operatorname{Var}_{\Sigma}(\Sigma_{jj})=2s^2. m D := E Σ Σ j j = d ( ϕ 2 + σ 2 ) + ψ 2 , Var Σ ( Σ j j ) = 2 s 2 . For any u > 0 u>0 u > 0 , with probability at least 1 − ( p 2 ) s 2 / u 2 + 2 p s 2 / u 2 1-\binom{p}{2}s^2/u^2+2ps^2/u^2 1 − ( 2 p ) s 2 / u 2 + 2 p s 2 / u 2 , simultaneously
max j < k ∣ Σ j k − E Σ Σ j k ∣ ≤ u , max j Σ j j ≤ m D + u . \max_{j<k}\lvert\Sigma_{jk}-\mathbb{E}_{\Sigma}\Sigma_{jk}\rvert\le u,
\qquad
\max_j\Sigma_{jj}\le m_D+u. j < k max ∣ Σ j k − E Σ Σ j k ∣ ≤ u , j max Σ j j ≤ m D + u . On this event, the measurement-noise factors satisfy
v j k : = Σ j j Σ k k + Σ j k 2 ≤ 2 ( m D + u ) 2 . v_{jk}:=\Sigma_{jj}\Sigma_{kk}+\Sigma_{jk}^2\le2(m_D+u)^2. v j k := Σ j j Σ k k + Σ j k 2 ≤ 2 ( m D + u ) 2 . Proof. Expanding f j T f k f_j^\mathsf{T}f_k f j T f k and ∥ f j ∥ 2 \lVert f_j\rVert^2 ∥ f j ∥ 2 gives the moments by independence and Gaussianity. Chebyshev’s inequality and union bound give the probability bound. Finally, positive semidefiniteness gives Σ j k 2 ≤ Σ j j Σ k k \Sigma_{jk}^2\le\Sigma_{jj}\Sigma_{kk} Σ j k 2 ≤ Σ j j Σ k k .
At σ = 0 \sigma=0 σ = 0 , every subject has the same connectome. Increasing σ \sigma σ introduces subject-level variation and increases the spread s s s relative to the fixed community separation ϕ 2 d \phi^2d ϕ 2 d .
Graph construction and threshold regimes
All four graphs are entrywise thresholdings 1 { ⋅ > δ } \mathbb{1}\{\cdot>\delta\} 1 { ⋅ > δ } of a matrix ( Σ , Σ ^ ⊥ , Σ ^ or Σ 0 ) (\Sigma,\widehat{\Sigma}^{\perp},\widehat{\Sigma}\text{ or }\Sigma_0) ( Σ , Σ ⊥ , Σ or Σ 0 ) , so their structure is set by where δ \delta δ sits relative to the between- and within-community levels μ B \mu_B μ B and μ W \mu_W μ W of Σ \Sigma Σ . We distinguish:
Disconnected graph, δ = + ∞ \delta=+\infty δ = + ∞ . A = 0 A=0 A = 0 ; after adding self-loops R = I p R=I_p R = I p , and the smoothed map is the raw map.
Complete graph, δ = − ∞ \delta=-\infty δ = − ∞ . A ~ = 11 T \widetilde{A}=\mathbf{1}\mathbf{1}^{\mathsf{T}} A = 1 1 T and R = P 1 : = 1 p 11 T R=P_1:=\frac{1}{p}\mathbf{1}\mathbf{1}^{\mathsf{T}} R = P 1 := p 1 1 1 T , so P 1 Σ ^ = 1 s ^ T P_1\widehat{\Sigma}=\mathbf{1}\widehat{s}^{\mathsf{T}} P 1 Σ = 1 s T with s ^ : = 1 p Σ ^ 1 \widehat{s}:=\frac{1}{p}\widehat{\Sigma}\mathbf{1} s := p 1 Σ 1 : the p 2 p^2 p 2 entries collapse to the p p p ROI averages.
Intermediate threshold in the regime, μ B < δ < μ W \mu_B<\delta<\mu_W μ B < δ < μ W , with margin γ δ : = min { μ W − δ , δ − μ B } > 0 \gamma_\delta:=\min\{\mu_W-\delta,\delta-\mu_B\}>0 γ δ := min { μ W − δ , δ − μ B } > 0 . The oracle graph selects mostly within-community neighbors and
R ( A o r a c l e ) = P C + Δ R δ , ( P C ) j ℓ = 1 q 1 { ℓ ∈ C ( j ) } , R(A^{\mathrm{oracle}})=P_C+\Delta R_\delta,
\qquad
(P_C)_{j\ell}=\frac{1}{q}\mathbb{1}\{\ell\in C(j)\}, R ( A oracle ) = P C + Δ R δ , ( P C ) j ℓ = q 1 1 { ℓ ∈ C ( j )} ,
where P C P_C P C depends only on the community partition and Δ R δ \Delta R_\delta Δ R δ collects the subject-specific deviations of the oracle neighborhoods.
Finite threshold outside the regime. If δ < μ B \delta<\mu_B δ < μ B , most between-community pairs are also connected: the graph is dense and R R R approaches P 1 P_1 P 1 . If δ > μ W \delta>\mu_W δ > μ W , most within-community pairs are dropped: the graph is sparse and R R R approaches I p I_p I p , the surviving edges being the largest entries of Σ ( i ) \Sigma^{(i)} Σ ( i ) rather than the partition. In neither case does R R R split into a community and a subject-specific component.
We focus on case 3 when interpreting the results through community structure. The oracle-smoothing bounds themselves hold for any fixed threshold.
Predictive signal
Let B ⋆ ∈ R p × p B^\star\in\mathbb{R}^{p\times p} B ⋆ ∈ R p × p be the matrix form of the regression coefficient, β ⋆ = vec ( B ⋆ ) \beta^\star=\operatorname{vec}(B^\star) β ⋆ = vec ( B ⋆ ) , so that h ( Σ ) = ⟨ B ⋆ , Σ ⟩ h(\Sigma)=\langle B^\star,\Sigma\rangle h ( Σ ) = ⟨ B ⋆ , Σ ⟩ . We say that B ⋆ B^\star B ⋆ is community-smooth if rows from the same community have similar predictive profiles,
max j max ℓ ∈ C ( j ) ∑ k = 1 p ( B j k ⋆ − B ℓ k ⋆ ) 2 ≤ κ β 2 \max_j\max_{\ell\in C(j)}\sum_{k=1}^{p}(B^\star_{jk}-B^\star_{\ell k})^2\le\kappa_\beta^2 j max ℓ ∈ C ( j ) max k = 1 ∑ p ( B j k ⋆ − B ℓ k ⋆ ) 2 ≤ κ β 2
for some κ β ≥ 0 \kappa_\beta\ge0 κ β ≥ 0 ; the ideal case κ β = 0 \kappa_\beta=0 κ β = 0 has B j k ⋆ B^\star_{jk} B j k ⋆ depending only on ( z j , z k ) (z_j,z_k) ( z j , z k ) . We study two families of targets.
Targets constant over communities: the within-community strength of a fixed ROI a a a , with e a e_a e a the a a a -th standard basis vector and 1 C ( a ) \mathbf{1}_{C(a)} 1 C ( a ) the indicator of the community containing a a a ,
B a , C ⋆ : = 1 2 ( e a 1 C ( a ) ⊤ + 1 C ( a ) e a ⊤ ) , h a , C ( Σ ) = e a ⊤ Σ 1 C ( a ) ; B^\star_{a,C} := \frac{1}{2}\left(e_a\mathbf{1}_{C(a)}^\top+\mathbf{1}_{C(a)}e_a^\top\right), \qquad h_{a,C}(\Sigma)=e_a^\top\Sigma\mathbf{1}_{C(a)}; B a , C ⋆ := 2 1 ( e a 1 C ( a ) ⊤ + 1 C ( a ) e a ⊤ ) , h a , C ( Σ ) = e a ⊤ Σ 1 C ( a ) ; and the total within-community connectivity h C ( Σ ) = ∣ C ∣ − 2 1 C ⊤ Σ 1 C h_C(\Sigma)=|C|^{-2}\mathbf{1}_C^\top\Sigma\mathbf{1}_C h C ( Σ ) = ∣ C ∣ − 2 1 C ⊤ Σ 1 C .
Targets supported on single edges or on within-community differences: the single edge h a b ( Σ ) = Σ a b h_{ab}(\Sigma)=\Sigma_{ab} h ab ( Σ ) = Σ ab , and the within-community contrast
B c o n t r a s t ⋆ : = 1 2 { ( e a − e b ) v ⊤ + v ( e a − e b ) ⊤ } , v = 1 C ( a ) . B^\star_{\mathrm{contrast}}:=\frac{1}{2}\left\{(e_a-e_b)v^\top+v(e_a-e_b)^\top\right\},\qquad v=\mathbf{1}_{C(a)}. B contrast ⋆ := 2 1 { ( e a − e b ) v ⊤ + v ( e a − e b ) ⊤ } , v = 1 C ( a ) .
Case 1: oracle graph
The oracle graph is constructed from the true connectome. Specifically,
A o r a c l e = 1 { Σ > δ } , R ( A o r a c l e ) = D ~ − 1 ( A o r a c l e + I p ) . A^{\mathrm{oracle}}=\mathbf{1}\{\Sigma>\delta\},\qquad R(A^{\mathrm{oracle}})=\widetilde{D}^{-1}(A^{\mathrm{oracle}}+I_p). A oracle = 1 { Σ > δ } , R ( A oracle ) = D − 1 ( A oracle + I p ) .
Proposition 4 (a) applies directly to this type of graph construction.
Proposition 1 (Oracle smoothing). Under the EIV assumptions of Remark 1, fix any threshold δ \delta δ ; the oracle operator R ( A o r a c l e ) R(A^{\mathrm{oracle}}) R ( A oracle ) is a function of Σ \Sigma Σ . Assume all displayed moments are finite and define the squared bias and the variance reduction:
B A o r a c l e ( δ ) : = E Σ [ ⟨ B ⋆ , R ( A o r a c l e ) Σ − Σ ⟩ 2 ] , \mathcal{B}_{A^{\mathrm{oracle}}}(\delta):=\mathbb{E}_{\Sigma}\left[\left\langle B^\star,R(A^{\mathrm{oracle}})\Sigma-\Sigma\right\rangle^2\right], B A oracle ( δ ) := E Σ [ ⟨ B ⋆ , R ( A oracle ) Σ − Σ ⟩ 2 ] , Δ V A o r a c l e ( δ ) : = T E Σ [ Var η { ⟨ B ⋆ , H ⟩ ∣ Σ } − Var η { ⟨ B ⋆ , R ( A o r a c l e ) H ⟩ ∣ Σ } ] . \Delta\mathcal{V}_{A^{\mathrm{oracle}}}(\delta):=T\mathbb{E}_{\Sigma}\left[\operatorname{Var}_{\eta}\left\{\left\langle B^\star,H\right\rangle\mid\Sigma\right\}-\operatorname{Var}_{\eta}\left\{\left\langle B^\star,R(A^{\mathrm{oracle}})H\right\rangle\mid\Sigma\right\}\right]. Δ V A oracle ( δ ) := T E Σ [ Var η { ⟨ B ⋆ , H ⟩ ∣ Σ } − Var η { ⟨ B ⋆ , R ( A oracle ) H ⟩ ∣ Σ } ] . Sufficient condition. The optimized population MSEs satisfy, for every T > 0 T>0 T > 0 ,
MSE o r a c l e ( T , δ ) − MSE r a w ( T ) ≤ B A o r a c l e ( δ ) − Δ V A o r a c l e ( δ ) T + r r a w ( T ) , \operatorname{MSE}_{\mathrm{oracle}}(T,\delta)-\operatorname{MSE}_{\mathrm{raw}}(T)\leq\mathcal{B}_{A^{\mathrm{oracle}}}(\delta)-\frac{\Delta\mathcal{V}_{A^{\mathrm{oracle}}}(\delta)}{T}+r_{\mathrm{raw}}(T), MSE oracle ( T , δ ) − MSE raw ( T ) ≤ B A oracle ( δ ) − T Δ V A oracle ( δ ) + r raw ( T ) , where
r r a w ( T ) : = T − 2 β ⋆ ⊤ Γ ( S + T − 1 Γ ) † Γ β ⋆ ≥ 0. r_{\mathrm{raw}}(T):=T^{-2}\beta^{\star\top}\Gamma(S+T^{-1}\Gamma)^\dagger\Gamma\beta^\star\geq0. r raw ( T ) := T − 2 β ⋆ ⊤ Γ ( S + T − 1 Γ ) † Γ β ⋆ ≥ 0. If the support of Σ \Sigma Σ spans the symmetric matrices (Remark 1), as in the latent community model with σ > 0 \sigma>0 σ > 0 , then r r a w ( T ) = O ( T − 2 ) r_{\mathrm{raw}}(T)=O(T^{-2}) r raw ( T ) = O ( T − 2 ) . Thus oracle smoothing improves whenever B A o r a c l e ( δ ) + r r a w ( T ) < Δ V A o r a c l e ( δ ) / T \mathcal{B}_{A^{\mathrm{oracle}}}(\delta)+r_{\mathrm{raw}}(T)<\Delta\mathcal{V}_{A^{\mathrm{oracle}}}(\delta)/T B A oracle ( δ ) + r raw ( T ) < Δ V A oracle ( δ ) / T .
Necessary condition. Let
b δ : = min γ ∈ R p 2 E Σ [ { h ( Σ ) − γ ⊤ vec ( R ( A o r a c l e ) Σ ) } 2 ] b_\delta:=\min_{\gamma\in\mathbb{R}^{p^2}}\mathbb{E}_{\Sigma}\left[\left\{h(\Sigma)-\gamma^\top\operatorname{vec}(R(A^{\mathrm{oracle}})\Sigma)\right\}^2\right] b δ := γ ∈ R p 2 min E Σ [ { h ( Σ ) − γ ⊤ vec ( R ( A oracle ) Σ ) } 2 ] be the minimum noiseless prediction error, with γ \gamma γ shared across subjects. If b δ > 0 b_\delta>0 b δ > 0 , then
MSE o r a c l e ( T , δ ) < MSE r a w ( T ) ⟹ T < β ⋆ ⊤ Γ β ⋆ b δ . \operatorname{MSE}_{\mathrm{oracle}}(T,\delta)<\operatorname{MSE}_{\mathrm{raw}}(T)\quad\Longrightarrow\quad T<\frac{\beta^{\star\top}\Gamma\beta^\star}{b_\delta}. MSE oracle ( T , δ ) < MSE raw ( T ) ⟹ T < b δ β ⋆ ⊤ Γ β ⋆ .
Proof. Write R = R ( A o r a c l e ) R=R(A^{\mathrm{oracle}}) R = R ( A oracle ) and x ~ A o r a c l e = vec ( R Σ ^ ) = vec ( R Σ ) + vec ( R H ) \widetilde{x}_{A^{\mathrm{oracle}}}=\operatorname{vec}(R\widehat{\Sigma})=\operatorname{vec}(R\Sigma)+\operatorname{vec}(RH) x A oracle = vec ( R Σ ) = vec ( R Σ ) + vec ( R H ) . Since R R R is a function of Σ \Sigma Σ and E η [ η ∣ Σ ] = 0 \mathbb{E}_{\eta}[\eta\mid\Sigma]=0 E η [ η ∣ Σ ] = 0 , E η [ vec ( R H ) ∣ Σ ] = 0 \mathbb{E}_{\eta}[\operatorname{vec}(RH)\mid\Sigma]=0 E η [ vec ( R H ) ∣ Σ ] = 0 , and ε \varepsilon ε is independent of ( Σ , H ) (\Sigma,H) ( Σ , H ) , so for any γ ∈ R p 2 \gamma\in\mathbb{R}^{p^2} γ ∈ R p 2 the cross terms vanish and
E Σ , η , ε [ ( Y − γ ⊤ x ~ A o r a c l e ) 2 ] = E Σ [ { h ( Σ ) − γ ⊤ vec ( R Σ ) } 2 ] + E Σ [ Var η ( γ ⊤ vec ( R H ) ∣ Σ ) ] + σ ε 2 . (6) \mathbb{E}_{\Sigma,\eta,\varepsilon}\left[(Y-\gamma^\top\widetilde{x}_{A^{\mathrm{oracle}}})^2\right]=\mathbb{E}_{\Sigma}\left[\{h(\Sigma)-\gamma^\top\operatorname{vec}(R\Sigma)\}^2\right]+\mathbb{E}_{\Sigma}\left[\operatorname{Var}_{\eta}(\gamma^\top\operatorname{vec}(RH)\mid\Sigma)\right]+\sigma_\varepsilon^2. \tag*{(6)} E Σ , η , ε [ ( Y − γ ⊤ x A oracle ) 2 ] = E Σ [ { h ( Σ ) − γ ⊤ vec ( R Σ ) } 2 ] + E Σ [ Var η ( γ ⊤ vec ( R H ) ∣ Σ ) ] + σ ε 2 . (6)
Evaluating at γ = β ⋆ \gamma=\beta^\star γ = β ⋆ , rather than at the fitted coefficient, the first term is B A o r a c l e \mathcal{B}_{A^{\mathrm{oracle}}} B A oracle and the second is T − 1 ( β ⋆ ⊤ Γ β ⋆ − Δ V A o r a c l e ) T^{-1}(\beta^{\star\top}\Gamma\beta^\star-\Delta\mathcal{V}_{A^{\mathrm{oracle}}}) T − 1 ( β ⋆ ⊤ Γ β ⋆ − Δ V A oracle ) , by definition of Δ V A o r a c l e \Delta\mathcal{V}_{A^{\mathrm{oracle}}} Δ V A oracle and T E Σ [ Var η ( ⟨ B ⋆ , H ⟩ ∣ Σ ) ] = β ⋆ ⊤ Γ β ⋆ T\mathbb{E}_{\Sigma}[\operatorname{Var}_{\eta}(\langle B^\star,H\rangle\mid\Sigma)]=\beta^{\star\top}\Gamma\beta^\star T E Σ [ Var η (⟨ B ⋆ , H ⟩ ∣ Σ )] = β ⋆ ⊤ Γ β ⋆ . Hence
MSE o r a c l e − σ ε 2 ≤ B A o r a c l e + T − 1 ( β ⋆ ⊤ Γ β ⋆ − Δ V A o r a c l e ) . \operatorname{MSE}_{\mathrm{oracle}}-\sigma_\varepsilon^2\leq\mathcal{B}_{A^{\mathrm{oracle}}}+T^{-1}\left(\beta^{\star\top}\Gamma\beta^\star-\Delta\mathcal{V}_{A^{\mathrm{oracle}}}\right). MSE oracle − σ ε 2 ≤ B A oracle + T − 1 ( β ⋆ ⊤ Γ β ⋆ − Δ V A oracle ) .
For raw features, Remark 1, with M = S + T − 1 Γ M=S+T^{-1}\Gamma M = S + T − 1 Γ , gives MSE r a w − σ ε 2 = β ⋆ ⊤ ( S − S M † S ) β ⋆ \operatorname{MSE}_{\mathrm{raw}}-\sigma_\varepsilon^2=\beta^{\star\top}(S-SM^\dagger S)\beta^\star MSE raw − σ ε 2 = β ⋆ ⊤ ( S − S M † S ) β ⋆ . Substituting S = M − T − 1 Γ S=M-T^{-1}\Gamma S = M − T − 1 Γ , valid since M ⪰ T − 1 Γ M\succeq T^{-1}\Gamma M ⪰ T − 1 Γ , gives
S − S M † S = T − 1 Γ − T − 2 Γ M † Γ , hence MSE r a w − σ ε 2 = T − 1 β ⋆ ⊤ Γ β ⋆ − r r a w ( T ) , (7) S-SM^\dagger S=T^{-1}\Gamma-T^{-2}\Gamma M^\dagger\Gamma,\qquad\text{hence}\qquad\operatorname{MSE}_{\mathrm{raw}}-\sigma_\varepsilon^2=T^{-1}\beta^{\star\top}\Gamma\beta^\star-r_{\mathrm{raw}}(T), \tag*{(7)} S − S M † S = T − 1 Γ − T − 2 Γ M † Γ , hence MSE raw − σ ε 2 = T − 1 β ⋆ ⊤ Γ β ⋆ − r raw ( T ) , (7)
with r r a w ( T ) ≥ 0 r_{\mathrm{raw}}(T) \ge0 r raw ( T ) ≥ 0 because M † ⪰ 0 M^{\dagger} \succeq0 M † ⪰ 0 . Subtracting proves the sufficient comparison.
By (6), M S E o r a c l e − σ ε 2 ≥ b δ \mathrm{MSE}_{\mathrm{oracle}}-\sigma_{\varepsilon}^{2} \ge b_{\delta} MSE oracle − σ ε 2 ≥ b δ , while M S E r a w − σ ε 2 ≤ T − 1 β ⋆ ⊤ Γ β ⋆ \mathrm{MSE}_{\mathrm{raw}}-\sigma_{\varepsilon}^{2} \le T^{-1}\beta^{\star\top}\Gamma\beta^{\star} MSE raw − σ ε 2 ≤ T − 1 β ⋆ ⊤ Γ β ⋆ . Strict improvement therefore gives b δ < T − 1 β ⋆ ⊤ Γ β ⋆ b_{\delta}<T^{-1}\beta^{\star\top}\Gamma\beta^{\star} b δ < T − 1 β ⋆ ⊤ Γ β ⋆ , the necessary bound on T T T .
Finally, under the spanning condition S S S is invertible on the symmetric subspace, which contains range ( Γ ) \operatorname{range}(\Gamma) range ( Γ ) (Definition 1). There M ⪰ S M \succeq S M ⪰ S , so M † ⪯ S † M^{\dagger}\preceq S^{\dagger} M † ⪯ S † and
r r a w ( T ) ≤ T − 2 β ⋆ ⊤ S † Γ S † β ⋆ = O ( T − 2 ) . r_{\mathrm{raw}}(T) \le T^{-2}\beta^{\star\top}S^{\dagger}\Gamma S^{\dagger}\beta^{\star}=O(T^{-2}). r raw ( T ) ≤ T − 2 β ⋆ ⊤ S † Γ S † β ⋆ = O ( T − 2 ) .
In the latent community model with σ > 0 \sigma>0 σ > 0 , taking F = u e 1 ⊤ F=u e_{1}^{\top} F = u e 1 ⊤ shows that the support of Σ \Sigma Σ contains u u ⊤ + ψ 2 I p u u^{\top}+\psi^{2}I_{p} u u ⊤ + ψ 2 I p for every u ∈ R p u\in\mathbb{R}^{p} u ∈ R p , and these matrices span the symmetric matrices.
The sufficient condition above can now be interpreted through the three ingredients that determine its bias and variance terms.
Predictive signal, B ⋆ B^{\star} B ⋆ . Since the rows of R ( A o r a c l e ) R(A^{\mathrm{oracle}}) R ( A oracle ) sum to one,
⟨ B ⋆ , R ( A o r a c l e ) Σ − Σ ⟩ = ∑ j , k B j k ⋆ ∑ ℓ R ( A o r a c l e ) j ℓ ( Σ ℓ k − Σ j k ) . \langle B^{\star},R(A^{\mathrm{oracle}})\Sigma-\Sigma\rangle
=\sum_{j,k}B_{jk}^{\star}\sum_{\ell}R(A^{\mathrm{oracle}})_{j\ell}(\Sigma_{\ell k}-\Sigma_{jk}). ⟨ B ⋆ , R ( A oracle ) Σ − Σ ⟩ = j , k ∑ B j k ⋆ ℓ ∑ R ( A oracle ) j ℓ ( Σ ℓ k − Σ j k ) .
so the bias is small when the ROIs averaged with j j j have rows close to Σ j ⋅ \Sigma_{j\cdot} Σ j ⋅ on the support of B ⋆ B^{\star} B ⋆ : community-level targets depend on sums of entries, whereas edge targets depend on specific entries.
Threshold, δ \delta δ . For a given target, the threshold determines which ROIs enter this average. Lowering δ \delta δ adds neighbors while raising it removes them. These changes affect both bias and noise propagation, so more averaging is not automatically better.
Disconnected graph. For δ = + ∞ \delta=+\infty δ = + ∞ , R ( A o r a c l e ) = I p R(A^{\mathrm{oracle}})=I_{p} R ( A oracle ) = I p (Appendix A.4.2): the smoothed and raw features coincide, so M S E o r a c l e ( T , + ∞ ) = M S E r a w ( T ) \mathrm{MSE}_{\mathrm{oracle}}(T,+\infty)=\mathrm{MSE}_{\mathrm{raw}}(T) MSE oracle ( T , + ∞ ) = MSE raw ( T ) for every T T T , and B A o r a c l e = Δ V A o r a c l e = 0 \mathcal{B}_{A^{\mathrm{oracle}}}=\Delta\mathcal{V}_{A^{\mathrm{oracle}}}=0 B A oracle = Δ V A oracle = 0 .
Complete graph. For δ = − ∞ \delta=-\infty δ = − ∞ , R ( A o r a c l e ) = P 1 R(A^{\mathrm{oracle}})=P_{1} R ( A oracle ) = P 1 (Appendix A.4.2) is the same for every subject and P 1 Σ ^ = 1 s ^ ⊤ P_{1}\widehat{\Sigma}=\mathbf{1}\widehat{s}^{\top} P 1 Σ = 1 s ⊤ , so the smoothed class is the set of linear functions of the degree vector s ^ = Σ ^ 1 / p \widehat{s}=\widehat{\Sigma}\mathbf{1}/p s = Σ 1 / p . By Proposition 5, M S E J ( T ) ≥ M S E r a w ( T ) \mathrm{MSE}_{J}(T)\ge\mathrm{MSE}_{\mathrm{raw}}(T) MSE J ( T ) ≥ MSE raw ( T ) for every T T T , with J = 11 ⊤ J=\mathbf{1}\mathbf{1}^{\top} J = 1 1 ⊤ .
Intermediate threshold. For μ B < δ < μ W \mu_{B}<\delta<\mu_{W} μ B < δ < μ W , the population operator is P C P_{C} P C . Writing R ( A o r a c l e ) = P C + Δ R δ R(A^{\mathrm{oracle}})=P_{C}+\Delta R_{\delta} R ( A oracle ) = P C + Δ R δ gives
B A o r a c l e ( δ ) = E Σ [ { ⟨ B ⋆ , ( P C − I p ) Σ ⟩ + ⟨ B ⋆ , Δ R δ Σ ⟩ } 2 ] . \mathcal{B}_{A^{\mathrm{oracle}}}(\delta)=\mathbb{E}_{\Sigma}\left[\left\{\langle B^{\star},(P_{C}-I_{p})\Sigma\rangle+\langle B^{\star},\Delta R_{\delta}\Sigma\rangle\right\}^{2}\right]. B A oracle ( δ ) = E Σ [ { ⟨ B ⋆ , ( P C − I p ) Σ ⟩ + ⟨ B ⋆ , Δ R δ Σ ⟩ } 2 ] .
The first term concerns fixed community averaging; the second captures the effect of subject-specific neighborhoods. For exact community smoothness, P C B ⋆ = B ⋆ P_{C}B^{\star}=B^{\star} P C B ⋆ = B ⋆ , the first term vanishes, but the second need not. Since fixed averaging cannot improve optimized prediction (Proposition 5), any oracle gain requires subject-specific variation in the operator and not merely an aligned target.
Community structure, σ \sigma σ . At a given threshold, changing σ \sigma σ changes the connectomes being thresholded. It controls deviations from the shared community loadings, affecting both the selected neighborhoods and the measurement-noise factors. For intermediate thresholds, concentration around the community levels relative to the threshold margins makes the oracle close to P C P_{C} P C . Thus clear communities and an aligned target alone do not guarantee improvement: the prediction effect depends on how σ \sigma σ , δ \delta δ , and B ⋆ B^{\star} B ⋆ interact.
Together, these ingredients determine whether the noise reduction outweighs the squared bias and the raw-regression correction. The two targets below illustrate this interaction.
Concrete examples. Consider h a , v ( Σ ) = e a ⊤ Σ v h_{a,v}(\Sigma)=e_{a}^{\top}\Sigma v h a , v ( Σ ) = e a ⊤ Σ v , taking v = 1 C ( a ) v=\mathbf{1}_{C(a)} v = 1 C ( a ) for the within-community strength or v = e b v=e_{b} v = e b for a single edge. On the oracle-smoothed features, consider the candidate predictor
h ^ δ = e a ⊤ R ( A o r a c l e ) Σ ^ v = w a , δ ⊤ Σ ^ v , w a , δ : = R ( A o r a c l e ) ⊤ e a . \widehat{h}_{\delta}=e_{a}^{\top}R(A^{\mathrm{oracle}})\widehat{\Sigma}v=w_{a,\delta}^{\top}\widehat{\Sigma}v,\qquad w_{a,\delta}:=R(A^{\mathrm{oracle}})^{\top}e_{a}. h δ = e a ⊤ R ( A oracle ) Σ v = w a , δ ⊤ Σ v , w a , δ := R ( A oracle ) ⊤ e a .
This is a linear predictor on vec ( R ( A o r a c l e ) Σ ^ ) \operatorname{vec}(R(A^{\mathrm{oracle}})\widehat{\Sigma}) vec ( R ( A oracle ) Σ ) with fixed coefficient vec ( e a v ⊤ ) \operatorname{vec}(e_{a}v^{\top}) vec ( e a v ⊤ ) ; it need not be the optimal fitted coefficient. Its conditional bias and measurement-noise variance factor are
b δ ( a , v ; Σ ) = ( w a , δ − e a ) ⊤ Σ v , b_{\delta}(a,v;\Sigma)=(w_{a,\delta}-e_{a})^{\top}\Sigma v, b δ ( a , v ; Σ ) = ( w a , δ − e a ) ⊤ Σ v ,
V δ ( a , v ; Σ ) = ( w a , δ ⊤ Σ w a , δ ) ( v ⊤ Σ v ) + ( w a , δ ⊤ Σ v ) 2 . V_{\delta}(a,v;\Sigma)=(w_{a,\delta}^{\top}\Sigma w_{a,\delta})(v^{\top}\Sigma v)+(w_{a,\delta}^{\top}\Sigma v)^{2}. V δ ( a , v ; Σ ) = ( w a , δ ⊤ Σ w a , δ ) ( v ⊤ Σ v ) + ( w a , δ ⊤ Σ v ) 2 .
Write V 0 V_0 V 0 for the same expression with w a , δ = e a w_{a,\delta}=e_a w a , δ = e a . Conditional centering and the Wishart moments give
E η , ϵ [ ( y − h ^ δ ) 2 ∣ Σ ] = b δ ( a , v ; Σ ) 2 + V δ ( a , v ; Σ ) T + σ ϵ 2 . \mathbb{E}_{\eta,\epsilon}\left[(y-\widehat{h}_{\delta})^2\mid\Sigma\right]=b_{\delta}(a,v;\Sigma)^2+\frac{V_{\delta}(a,v;\Sigma)}{T}+\sigma_{\epsilon}^2. E η , ϵ [ ( y − h δ ) 2 ∣ Σ ] = b δ ( a , v ; Σ ) 2 + T V δ ( a , v ; Σ ) + σ ϵ 2 .
Optimizing the oracle regression can only decrease this risk. Since the optimized raw risk is σ ϵ 2 + T − 1 E Σ [ V 0 ] − r r a w ( T ) \sigma_{\epsilon}^2+T^{-1}\mathbb{E}_{\Sigma}[V_0]-r_{\mathrm{raw}}(T) σ ϵ 2 + T − 1 E Σ [ V 0 ] − r raw ( T ) , the argument of Proposition 1 guarantees improvement whenever
E Σ [ b δ ( a , v ; Σ ) 2 ] + r r a w ( T ) < E Σ [ V 0 ( a , v ; Σ ) − V δ ( a , v ; Σ ) ] T , \mathbb{E}_{\Sigma}\left[b_{\delta}(a,v;\Sigma)^2\right]+r_{\mathrm{raw}}(T)<\frac{\mathbb{E}_{\Sigma}\left[V_0(a,v;\Sigma)-V_{\delta}(a,v;\Sigma)\right]}{T}, E Σ [ b δ ( a , v ; Σ ) 2 ] + r raw ( T ) < T E Σ [ V 0 ( a , v ; Σ ) − V δ ( a , v ; Σ ) ] ,
where r r a w ( T ) r_{\mathrm{raw}}(T) r raw ( T ) is evaluated for the chosen target.
Case 2: independent-copy graph and graph-estimation error
The independent graph is built from a second estimate Σ ^ ⊥ = Σ + H ⊥ \widehat{\Sigma}^{\perp}=\Sigma+H^{\perp} Σ ⊥ = Σ + H ⊥ with H ⊥ ⊥ ⊥ H ∣ Σ H^{\perp}\perp\!\!\perp H\mid\Sigma H ⊥ ⊥ ⊥ H ∣ Σ so that A ⊥ = 1 { Σ ^ ⊥ > δ } A^{\perp}=1\{\widehat{\Sigma}^{\perp}>\delta\} A ⊥ = 1 { Σ ⊥ > δ } . By Lemma 2 it has the same conditional law as A ^ \widehat{A} A given Σ \Sigma Σ but is independent of the feature noise, so Proposition 4(a) applies with A = A ⊥ A=A^{\perp} A = A ⊥ . The graph-estimation contribution is M S E i n d ( T ) − M S E o r a c l e ( T ) \mathrm{MSE}_{\mathrm{ind}}(T)-\mathrm{MSE}_{\mathrm{oracle}}(T) MSE ind ( T ) − MSE oracle ( T ) : all differences relative to the oracle come from smoothing over the wrong neighborhoods and not from coupling with H H H .
Proposition 2 (Graph-estimation error for the independent graph). Under the assumptions of Proposition 1, let A ⊥ A^{\perp} A ⊥ be built from a conditionally independent copy H ⊥ H^{\perp} H ⊥ of H H H given Σ \Sigma Σ , and assume E Σ ∥ Σ ∥ F 4 < ∞ \mathbb{E}_{\Sigma}\|\Sigma\|_{F}^{4}<\infty E Σ ∥Σ ∥ F 4 < ∞ . Define the edge-error probability and the graph-estimation error:
ρ ( T , δ ) : = P ( A ⊥ ≠ A o r a c l e ) , E ( T , δ ) : = C ( 1 + T − 1 ) ρ ( T , δ ) , \rho(T,\delta):=\mathbb{P}(A^{\perp}\ne A^{\mathrm{oracle}}),\qquad\mathcal{E}(T,\delta):=C(1+T^{-1})\sqrt{\rho(T,\delta)}, ρ ( T , δ ) := P ( A ⊥ = A oracle ) , E ( T , δ ) := C ( 1 + T − 1 ) ρ ( T , δ ) , where C C C depends only on p p p , ∥ B ⋆ ∥ F \|B^\star\|_{F} ∥ B ⋆ ∥ F and E Σ ∥ Σ ∥ F 4 \mathbb{E}_{\Sigma}\|\Sigma\|_{F}^{4} E Σ ∥Σ ∥ F 4 , not on T T T or δ \delta δ . Then, for every T > 0 T>0 T > 0 ,
M S E i n d ( T , δ ) − M S E r a w ( T ) ≤ B A o r a c l e ( δ ) − Δ V A o r a c l e ( δ ) T + E ( T , δ ) + r r a w ( T ) . \mathrm{MSE}_{\mathrm{ind}}(T,\delta)-\mathrm{MSE}_{\mathrm{raw}}(T)\le\mathcal{B}_{A^{\mathrm{oracle}}}(\delta)-\frac{\Delta V_{A^{\mathrm{oracle}}}(\delta)}{T}+\mathcal{E}(T,\delta)+r_{\mathrm{raw}}(T). MSE ind ( T , δ ) − MSE raw ( T ) ≤ B A oracle ( δ ) − T Δ V A oracle ( δ ) + E ( T , δ ) + r raw ( T ) . Thus the independent graph improves whenever B A o r a c l e ( δ ) + E ( T , δ ) + r r a w ( T ) < Δ V A o r a c l e ( δ ) / T \mathcal{B}_{A^{\mathrm{oracle}}}(\delta)+\mathcal{E}(T,\delta)+r_{\mathrm{raw}}(T)<\Delta V_{A^{\mathrm{oracle}}}(\delta)/T B A oracle ( δ ) + E ( T , δ ) + r raw ( T ) < Δ V A oracle ( δ ) / T .
Proof. As in the proof of Proposition 1, we evaluate both graphs at the true coefficient β ⋆ \beta^\star β ⋆ instead of the fitted one. Given Σ \Sigma Σ and the graph A A A , the resulting error, excluding the response noise, is
L A = ⟨ B ⋆ , R ( A ) Σ − Σ ⟩ 2 + Var η { ⟨ B ⋆ , R ( A ) H ⟩ ∣ Σ , A } . L_A=\left\langle B^\star,R(A)\Sigma-\Sigma\right\rangle^2+\operatorname{Var}_{\eta}\left\{\left\langle B^\star,R(A)H\right\rangle\mid\Sigma,A\right\}. L A = ⟨ B ⋆ , R ( A ) Σ − Σ ⟩ 2 + Var η { ⟨ B ⋆ , R ( A ) H ⟩ ∣ Σ , A } .
For the oracle, its expectation is B A o r a c l e + T − 1 ( β ⋆ ⊤ Γ β ⋆ − Δ V A o r a c l e ) \mathcal{B}_{A^{\mathrm{oracle}}}+T^{-1}(\beta^{\star\top}\Gamma\beta^\star-\Delta V_{A^{\mathrm{oracle}}}) B A oracle + T − 1 ( β ⋆ ⊤ Γ β ⋆ − Δ V A oracle ) . Hence
M S E i n d − σ ϵ 2 ≤ E Σ , H ⊥ [ L A ⊥ ] = E Σ [ L A o r a c l e ] + E Σ , H ⊥ [ L A ⊥ − L A o r a c l e ] . \mathrm{MSE}_{\mathrm{ind}}-\sigma_{\epsilon}^2\le\mathbb{E}_{\Sigma,H^{\perp}}[L_{A^{\perp}}]=\mathbb{E}_{\Sigma}[L_{A^{\mathrm{oracle}}}]+\mathbb{E}_{\Sigma,H^{\perp}}[L_{A^{\perp}}-L_{A^{\mathrm{oracle}}}]. MSE ind − σ ϵ 2 ≤ E Σ , H ⊥ [ L A ⊥ ] = E Σ [ L A oracle ] + E Σ , H ⊥ [ L A ⊥ − L A oracle ] .
The last term is the graph-estimation error. It is zero when A ⊥ = A o r a c l e A^{\perp}=A^{\mathrm{oracle}} A ⊥ = A oracle . Since ∥ R ( A ) ∥ o p ≤ p \|R(A)\|_{\mathrm{op}}\le\sqrt{p} ∥ R ( A ) ∥ op ≤ p and ∥ Ψ ∥ o p ≤ 2 ∥ Σ ∥ F 2 \|\Psi\|_{\mathrm{op}}\le2\|\Sigma\|_{F}^{2} ∥Ψ ∥ op ≤ 2∥Σ ∥ F 2 , each loss is at most C 0 ( 1 + T − 1 ) ∥ Σ ∥ F 4 C_0(1+T^{-1})\|\Sigma\|_{F}^{4} C 0 ( 1 + T − 1 ) ∥Σ ∥ F 4 with C 0 = 4 p ∥ B ⋆ ∥ F 2 C_0=4p\|B^\star\|_{F}^{2} C 0 = 4 p ∥ B ⋆ ∥ F 2 , and Cauchy–Schwarz bounds the last term by E \mathcal{E} E with C = C 0 ( E Σ ∥ Σ ∥ F 4 ) 1 / 2 C=C_0(\mathbb{E}_{\Sigma}\|\Sigma\|_{F}^{4})^{1/2} C = C 0 ( E Σ ∥Σ ∥ F 4 ) 1/2 . Subtracting M S E r a w − σ ϵ 2 = T − 1 β ⋆ ⊤ Γ β ⋆ − r r a w ( T ) \mathrm{MSE}_{\mathrm{raw}}-\sigma_{\epsilon}^2=T^{-1}\beta^{\star\top}\Gamma\beta^\star-r_{\mathrm{raw}}(T) MSE raw − σ ϵ 2 = T − 1 β ⋆ ⊤ Γ β ⋆ − r raw ( T ) (proof of Proposition 1) gives the bound.
Proposition 2 asks whether graph estimation is accurate enough to retain the improvement certified for the oracle.
Predictive signal, B ⋆ B^\star B ⋆ . The target determines the oracle bias-variance tradeoff and the predictive consequences of changing its neighborhoods, but not the edge-error probabilities. In the preceding examples, neighborhood errors change averages of community strengths or individual connectivity entries. The same graph-estimation accuracy therefore need not give the same prediction benefit for different targets.
Threshold, δ \delta δ . The threshold determines both the oracle neighborhoods and how reliably they can be estimated. For the following calculation, adopt the Gaussian surrogate Σ ^ j k ⊥ ∣ Σ ∼ N ( Σ j k , v j k / T ) \widehat{\Sigma}^{\perp}_{jk}\mid\Sigma\sim\mathcal{N}(\Sigma_{jk},v_{jk}/T) Σ j k ⊥ ∣ Σ ∼ N ( Σ j k , v j k / T ) , where v j k = Σ j j Σ k k + Σ j k 2 > 0 v_{jk}=\Sigma_{jj}\Sigma_{kk}+\Sigma_{jk}^{2}>0 v j k = Σ j j Σ k k + Σ j k 2 > 0 . Standardizing the threshold-crossing event gives
π j k : = P ( A j k ⊥ ≠ A j k o r a c l e ∣ Σ ) = Φ ( − ∣ Σ j k − δ ∣ T v j k ) \pi_{jk}:=\mathbb{P}(A_{jk}^{\perp}\ne A_{jk}^{\mathrm{oracle}}\mid\Sigma)=\Phi\left(-\frac{|\Sigma_{jk}-\delta|\sqrt{T}}{\sqrt{v_{jk}}}\right) π j k := P ( A j k ⊥ = A j k oracle ∣ Σ ) = Φ ( − v j k ∣ Σ j k − δ ∣ T )
where Φ \Phi Φ is the standard normal CDF. Reliability therefore depends on actual threshold margins relative to measurement noise, not on graph density alone.
Disconnected and complete graphs. At δ = + ∞ \delta=+\infty δ = + ∞ both operators equal I p I_p I p ; at δ = − ∞ \delta=-\infty δ = − ∞ both equal P 1 P_1 P 1 . In either case, ρ = E = 0 \rho=\mathcal{E}=0 ρ = E = 0 . These graphs are perfectly estimated, but cannot improve optimized prediction over raw features.
Intermediate thresholds. For μ B < δ < μ W \mu_B<\delta<\mu_W μ B < δ < μ W , the oracle decomposition gives
R ( A ⊥ ) = P C + Δ R δ + { R ( A ⊥ ) − R ( A o r a c l e ) } . R(A^\perp)=P_C+\Delta R_\delta+\left\{R(A^\perp)-R(A^{\mathrm{oracle}})\right\}. R ( A ⊥ ) = P C + Δ R δ + { R ( A ⊥ ) − R ( A oracle ) } .
The last term is the graph-estimation change; Δ R δ \Delta R_\delta Δ R δ is genuine subject-specific variation, not estimation error. The aim is therefore to recover the oracle neighborhoods, not merely the population partition.
Set γ δ = min { μ W − δ , δ − μ B } \gamma_\delta=\min\{\mu_W-\delta,\delta-\mu_B\} γ δ = min { μ W − δ , δ − μ B } . Suppose an event G G G , with P ( G c ) ≤ ϵ 0 \mathbb{P}(G^c)\le\epsilon_0 P ( G c ) ≤ ϵ 0 , ensures that all off-diagonal entries lie within γ δ / 2 \gamma_\delta/2 γ δ /2 of their community levels and v j k ≤ v max : = max { v W , v B } v_{jk}\le v_{\max}:=\max\{v_W,v_B\} v j k ≤ v m a x := max { v W , v B } , with deterministic bounds independent of T T T . On G G G , the actual margins are at least γ δ / 2 \gamma_\delta/2 γ δ /2 , so the Gaussian tail bound gives
π j k ≤ e − T / ( 8 T g r a p h ( δ ) ) , T g r a p h ( δ ) : = v max γ δ 2 . \pi_{jk}\le e^{-T/(8T_{\mathrm{graph}}(\delta))},\qquad T_{\mathrm{graph}}(\delta):=\frac{v_{\max}}{\gamma_\delta^2}. π j k ≤ e − T / ( 8 T graph ( δ )) , T graph ( δ ) := γ δ 2 v m a x .
A union bound over edges, including the exceptional event, yields
ρ ( T , δ ) ≤ min { 1 , ϵ 0 + ( p 2 ) e − T / ( 8 T g r a p h ( δ ) ) } . \rho(T,\delta)\le\min\left\{1,\epsilon_0+\binom{p}{2}e^{-T/(8T_{\mathrm{graph}}(\delta))}\right\}. ρ ( T , δ ) ≤ min { 1 , ϵ 0 + ( 2 p ) e − T / ( 8 T graph ( δ )) } .
Community structure, σ \sigma σ . With fixed centroids, changing σ \sigma σ leaves μ W \mu_W μ W , μ B \mu_B μ B and γ δ \gamma_\delta γ δ unchanged, but changes concentration around those levels and the measurement-noise scales. Lemma 3 makes this dependence explicit: the preceding event can be obtained with
ϵ 0 = min { 1 , 4 ( ( p 2 ) + 2 p ) s 2 γ δ 2 } , v W = v B = 2 ( m D + γ δ / 2 ) 2 . \epsilon_0=\min\left\{1,\frac{4\left(\binom{p}{2}+2p\right)s^2}{\gamma_\delta^2}\right\},\qquad v_W=v_B=2(m_D+\gamma_\delta/2)^2. ϵ 0 = min { 1 , γ δ 2 4 ( ( 2 p ) + 2 p ) s 2 } , v W = v B = 2 ( m D + γ δ /2 ) 2 .
The community-margin guarantee is useful only when its exceptional probability is small; an intermediate threshold alone does not ensure reliable graph estimation.
Together, these ingredients determine whether the graph-estimation bound fits within the oracle’s sufficient improvement margin. Increasing T T T improves edge estimation under the surrogate, but also reduces the raw-feature noise available to denoise. An intermediate favorable range may therefore arise, but is not guaranteed. Failure of the sufficient condition remains inconclusive.
Case 3: same-sample graph and double dipping
The standard pipeline thresholds the same empirical covariance that serves as node features, A ^ = 1 { Σ ^ > δ } \widehat{A}=1\{\widehat{\Sigma}>\delta\} A = 1 { Σ > δ } , so R A ^ R_{\widehat{A}} R A depends on H H H . By Lemma 2 the independent graph has the same conditional law given Σ \Sigma Σ but none of the couplings, so D d d ( T , δ ) = M S E s a m e ( T ) − M S E i n d ( T ) \mathcal{D}_{\mathrm{dd}}(T,\delta)=\mathrm{MSE}_{\mathrm{same}}(T)-\mathrm{MSE}_{\mathrm{ind}}(T) D dd ( T , δ ) = MSE same ( T ) − MSE ind ( T ) isolates the double-dipping contribution.
Proposition 3 (Double-dipping contribution for the same-sample graph). Under the assumptions of Proposition 2, define the double-dipping contribution D d d ( T , δ ) : = M S E s a m e ( T , δ ) − M S E i n d ( T , δ ) \mathcal{D}_{\mathrm{dd}}(T,\delta):=\mathrm{MSE}_{\mathrm{same}}(T,\delta)-\mathrm{MSE}_{\mathrm{ind}}(T,\delta) D dd ( T , δ ) := MSE same ( T , δ ) − MSE ind ( T , δ ) . Then, for every T > 0 T>0 T > 0 ,
M S E s a m e ( T , δ ) − M S E r a w ( T ) ≤ B A o r a c l e ( δ ) − Δ V A o r a c l e ( δ ) T + E ( T , δ ) + D d d ( T , δ ) + r r a w ( T ) . \mathrm{MSE}_{\mathrm{same}}(T,\delta)-\mathrm{MSE}_{\mathrm{raw}}(T)\le\mathcal{B}_{\mathcal{A}^{\mathrm{oracle}}}(\delta)-\frac{\Delta\mathcal{V}_{\mathcal{A}^{\mathrm{oracle}}}(\delta)}{T}+\mathcal{E}(T,\delta)+\mathcal{D}_{\mathrm{dd}}(T,\delta)+r_{\mathrm{raw}}(T). MSE same ( T , δ ) − MSE raw ( T ) ≤ B A oracle ( δ ) − T Δ V A oracle ( δ ) + E ( T , δ ) + D dd ( T , δ ) + r raw ( T ) . Thus the same-sample graph improves whenever B A o r a c l e ( δ ) + E ( T , δ ) + D d d ( T , δ ) + r r a w ( T ) < Δ V A o r a c l e ( δ ) / T \mathcal{B}_{\mathcal{A}^{\mathrm{oracle}}}(\delta)+\mathcal{E}(T,\delta)+\mathcal{D}_{\mathrm{dd}}(T,\delta)+r_{\mathrm{raw}}(T)<\Delta\mathcal{V}_{\mathcal{A}^{\mathrm{oracle}}}(\delta)/T B A oracle ( δ ) + E ( T , δ ) + D dd ( T , δ ) + r raw ( T ) < Δ V A oracle ( δ ) / T . The contribution D d d \mathcal{D}_{\mathrm{dd}} D dd is signed: negative values favor the same-sample graph.
Proof. Since M S E s a m e = M S E i n d + D d d \mathrm{MSE}_{\mathrm{same}}=\mathrm{MSE}_{\mathrm{ind}}+\mathcal{D}_{\mathrm{dd}} MSE same = MSE ind + D dd by definition, the bound follows from Proposition 2. □ \square □
Size of the double-dipping contribution. Suppose in addition that E Σ , η ∥ H ∥ F 4 ≤ C H 4 T − 2 \mathbb{E}_{\Sigma,\eta}\lVert H\rVert_F^4\le C_H^4T^{-2} E Σ , η ∥ H ∥ F 4 ≤ C H 4 T − 2 and that the positive eigenvalues of M A ^ M_{\widehat{A}} M A and M A ⊥ M_{A_\perp} M A ⊥ are at least λ > 0 \lambda>0 λ > 0 for all T ≥ 1 T\ge1 T ≥ 1 . Then, for T ≥ 1 T\ge1 T ≥ 1 ,
∣ D d d ( T , δ ) ∣ ≤ C d d ρ ( T , δ ) T . \left|\mathcal{D}_{\mathrm{dd}}(T,\delta)\right|\le C_{\mathrm{dd}}\sqrt{\frac{\rho(T,\delta)}{T}}. ∣ D dd ( T , δ ) ∣ ≤ C dd T ρ ( T , δ ) .
where C d d C_{\mathrm{dd}} C dd depends only on p p p , ∥ B ∗ ∥ F \lVert B^*\rVert_F ∥ B ∗ ∥ F , C H C_H C H , λ \lambda λ and E Σ ∥ Σ ∥ F 4 \mathbb{E}_{\Sigma}\lVert\Sigma\rVert_F^4 E Σ ∥ Σ ∥ F 4 , not on T T T .
Proof. Let F A ( γ ) : = E Σ [ h 2 ] − 2 γ ⊤ c A + γ ⊤ M A γ F_A(\gamma) := \mathbb{E}_{\Sigma}[h^2] - 2\gamma^{\top}c_A + \gamma^{\top}M_A\gamma F A ( γ ) := E Σ [ h 2 ] − 2 γ ⊤ c A + γ ⊤ M A γ , with c A c_A c A and M A M_A M A as in Proposition 4 and M A ⊥ = S A ⊥ + T − 1 Γ A ⊥ M_{A^\perp} = S_{A^\perp} + T^{-1}\Gamma_{A^\perp} M A ⊥ = S A ⊥ + T − 1 Γ A ⊥ , so that MSE A = σ ε 2 + min γ F A ( γ ) \operatorname{MSE}_A = \sigma_{\varepsilon}^2 + \min_{\gamma} F_A(\gamma) MSE A = σ ε 2 + min γ F A ( γ ) . Evaluating each risk at the other graph’s minimizer gives
q ( β A ∗ ) ≤ D d d ≤ q ( β A ⊥ ∗ ) , q ( γ ) : = F A ^ ( γ ) − F A ⊥ ( γ ) = γ ⊤ Δ M γ − 2 γ ⊤ Δ c , q(\beta_A^*) \le D_{\mathrm{dd}} \le q(\beta_{A^\perp}^*), \qquad q(\gamma) := F_{\widehat{A}}(\gamma) - F_{A^\perp}(\gamma) = \gamma^{\top}\Delta_M\gamma- 2\gamma^{\top}\Delta_c, q ( β A ∗ ) ≤ D dd ≤ q ( β A ⊥ ∗ ) , q ( γ ) := F A ( γ ) − F A ⊥ ( γ ) = γ ⊤ Δ M γ − 2 γ ⊤ Δ c ,
with Δ M : = M A ^ − M A ⊥ \Delta_M := M_{\widehat{A}} - M_{A^\perp} Δ M := M A − M A ⊥ and Δ c : = c A ^ − c A ⊥ \Delta_c := c_{\widehat{A}} - c_{A^\perp} Δ c := c A − c A ⊥ . The graphs A ^ \widehat{A} A and A ⊥ A^\perp A ⊥ have the same law given Σ \Sigma Σ (Lemma 2), so every term without η \eta η cancels and only the noise reuse remains:
Δ c = E Σ , η [ ( R A ^ − R A o r a c l e ) η h ] , Δ M = E Σ , η [ R A ^ Q T R A ^ ⊤ − R A o r a c l e Q T R A o r a c l e ⊤ ] , \Delta_c = \mathbb{E}_{\Sigma,\eta}\left[(R_{\widehat{A}} - R_{A^{\mathrm{oracle}}})\eta h\right], \qquad\Delta_M = \mathbb{E}_{\Sigma,\eta}\left[R_{\widehat{A}}Q_T R_{\widehat{A}}^{\top} - R_{A^{\mathrm{oracle}}}Q_T R_{A^{\mathrm{oracle}}}^{\top}\right], Δ c = E Σ , η [ ( R A − R A oracle ) η h ] , Δ M = E Σ , η [ R A Q T R A ⊤ − R A oracle Q T R A oracle ⊤ ] ,
where Q T : = x ^ x ^ ⊤ − x x ⊤ − T − 1 Ψ Q_T := \widehat{x}\widehat{x}^{\top} - xx^{\top} - T^{-1}\Psi Q T := x x ⊤ − x x ⊤ − T − 1 Ψ . The oracle terms have mean zero because E η [ η ∣ Σ ] = 0 \mathbb{E}_{\eta}[\eta\mid\Sigma] = 0 E η [ η ∣ Σ ] = 0 and E η [ Q T ∣ Σ ] = 0 \mathbb{E}_{\eta}[Q_T \mid\Sigma] = 0 E η [ Q T ∣ Σ ] = 0 . Both integrands vanish unless A ^ ≠ A o r a c l e \widehat{A} \ne A^{\mathrm{oracle}} A = A oracle , an event of probability ρ \rho ρ . Cauchy–Schwarz with ∥ R A ∥ o p ≤ p \lVert R_A\rVert_{\mathrm{op}} \le\sqrt{p} ∥ R A ∥ op ≤ p and the fourth moments gives ∥ Δ c ∥ + ∥ Δ M ∥ o p ≤ C 1 ρ / T \lVert\Delta_c\rVert+ \lVert\Delta_M\rVert_{\mathrm{op}} \le C_1\sqrt{\rho/T} ∥ Δ c ∥ + ∥ Δ M ∥ op ≤ C 1 ρ / T . Finally, λ ∥ β A ∗ ∥ 2 ≤ β A ∗ ⊤ M A β A ∗ ≤ E Σ [ h 2 ] \lambda\lVert\beta_A^*\rVert^2 \le\beta_A^{*\top}M_A\beta_A^* \le\mathbb{E}_{\Sigma}[h^2] λ ∥ β A ∗ ∥ 2 ≤ β A ∗ ⊤ M A β A ∗ ≤ E Σ [ h 2 ] for both graphs, hence
∣ q ( β A ∗ ) ∣ ≤ E Σ [ h 2 ] λ ∥ Δ M ∥ o p + 2 E Σ [ h 2 ] λ ∥ Δ c ∥ , \lvert q(\beta_A^*)\rvert\le\frac{\mathbb{E}_{\Sigma}[h^2]}{\lambda}\lVert\Delta_M\rVert_{\mathrm{op}} + 2\sqrt{\frac{\mathbb{E}_{\Sigma}[h^2]}{\lambda}}\lVert\Delta_c\rVert, ∣ q ( β A ∗ )∣ ≤ λ E Σ [ h 2 ] ∥ Δ M ∥ op + 2 λ E Σ [ h 2 ] ∥ Δ c ∥ ,
which gives the bound.
Since A ^ \widehat{A} A and A ⊥ A^\perp A ⊥ have the same law given Σ \Sigma Σ , D d d D_{\mathrm{dd}} D dd isolates noise reuse, not a difference in graph quality. For μ B < δ < μ W \mu_B < \delta< \mu_W μ B < δ < μ W , both graphs estimate R ( A o r a c l e ) = P C + Δ R δ R(A^{\mathrm{oracle}}) = P_C + \Delta R_\delta R ( A oracle ) = P C + Δ R δ . The subject-specific part Δ R δ \Delta R_\delta Δ R δ is not double dipping. What differs is that R ( A ^ ) − R ( A o r a c l e ) R(\widehat{A}) - R(A^{\mathrm{oracle}}) R ( A ) − R ( A oracle ) depends on the feature noise H H H , while R ( A ⊥ ) − R ( A o r a c l e ) R(A^\perp) - R(A^{\mathrm{oracle}}) R ( A ⊥ ) − R ( A oracle ) does not. The bound shows that double dipping lives on edge flips: it is zero at δ = ± ∞ \delta= \pm\infty δ = ± ∞ , where both operators equal I p I_p I p or P 1 P_1 P 1 , and small whenever ρ \rho ρ is small. Its sign depends on B ∗ B^* B ∗ , and community smoothness alone fixes neither its sign nor its size. When the bound is small, the two optimized errors are close: removing noise reuse changes little, and the shared graph-estimation error remains.
Additional simulation results
In this section we report additional simulation experiments that further validate our theoretical findings and extend them to settings beyond the scope of the main analysis.
We begin by showing that the same conclusions hold when the feature map is the sample correlation C ^ \widehat{C} C rather than the sample covariance Σ ^ \widehat{\Sigma} Σ , the more common choice in fMRI pipelines. We then provide ablations along the latent structure σ \sigma σ , the threshold δ \delta δ , and the regression target β \beta β , isolating how each axis modulates the three effects identified in § 4 . Departing from the population regime (n → ∞ n \to\infty n → ∞ ), we show that at small n n n even smoothing with the correct graph topology may fail to improve over raw features. We further demonstrate that the same statistical framework applies to GCN [5 ] without changing the qualitative ordering between feature maps. Finally, we extend the analysis from i.i.d. samples to autoregressive time series, which more faithfully reflect the temporal structure of real fMRI signals [34 ] ; this departure preserves the framework and amounts to a shift along the T T T axis driven by the reduction in effective sample size.
Extension to correlation matrices: C C C
The theoretical analysis in § 3 is stated for the sample covariance Σ ^ \widehat{\Sigma} Σ , but fMRI pipelines almost always operate on the sample correlation C ^ = D − 1 / 2 Σ ^ D − 1 / 2 \widehat{C} = D^{-1/2}\widehat{\Sigma}D^{-1/2} C = D − 1/2 Σ D − 1/2 . Figure 5 reproduces the experiment of Figure 3 with C ^ \widehat{C} C as the feature map and confirms that the ordering between feature maps is preserved.
Figure 5. Decoupling the effects for different values of β \beta β and latent structures, with C C C in place of Σ \Sigma Σ . Center: true correlation C C C for two graph regimes (σ ∈ { 0.5 , 1.0 } \sigma\in\{0.5,1.0\} σ ∈ { 0.5 , 1.0 } ); overlays mark the support of β = single_community_aligned \beta= \texttt{single\_community\_aligned} β = single_community_aligned (red, full community block) and β = within_community_contrast \beta= \texttt{within\_community\_contrast} β = within_community_contrast (blue, single in-community edge). Left/right: normalized ValMSE vs. T T T for SageMean( A , C ^ ) (A,\hat{C}) ( A , C ^ ) under A ∈ { A o r a c l e , A ^ , A ⊥ , A p o p } A \in\{A^{\mathrm{oracle}}, \hat{A}, A^{\perp}, A^{\mathrm{pop}}\} A ∈ { A oracle , A ^ , A ⊥ , A pop } and a no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. p = 20 p=20 p = 20 , K = 5 K=5 K = 5 , n = 25,000 n=25{,}000 n = 25 , 000 ; thresholds δ σ = 0.5 ≈ 0.79 \delta_{\sigma=0.5}\approx0.79 δ σ = 0.5 ≈ 0.79 , δ σ = 1.0 ≈ 0.53 \delta_{\sigma=1.0}\approx0.53 δ σ = 1.0 ≈ 0.53 .
The role of the coefficient: β \beta β
Fixing the latent structure (σ = 1.0 \sigma= 1.0 σ = 1.0 ) and a sparse threshold (δ ≈ 10.20 \delta\approx10.20 δ ≈ 10.20 ), we vary the regression target β \beta β . Figure 6 shows that smoothing helps when β \beta β is community-smooth (community_aligned): the within-community averaging operator induces little bias and reduces variance, so A o r a c l e A^{\mathrm{oracle}} A oracle improves over raw features across all T T T . For the within_community_contrast and edge_specific targets, smoothing averages together precisely the entries whose differences carry the predictive signal, and the bias dominates the variance reduction except at very small T T T .
Figure 6. Decoupling the effect of the regression target β \beta β . Each panel fixes a different β \beta β pattern (ones, community_aligned \texttt{community\_aligned} community_aligned , within_community_contrast \texttt{within\_community\_contrast} within_community_contrast , edge_specific \texttt{edge\_specific} edge_specific ) and plots normalized ValMSE vs. T T T for SageMean( A , Σ ^ ) (A,\hat{\Sigma}) ( A , Σ ^ ) under A ∈ { A o r a c l e , A ^ , A ⊥ , A p o p } A \in\{A^{\mathrm{oracle}}, \hat{A}, A^{\perp}, A^{\mathrm{pop}}\} A ∈ { A oracle , A ^ , A ⊥ , A pop } and the no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. σ = 1.0 \sigma=1.0 σ = 1.0 , p = 20 p=20 p = 20 , K = 5 K=5 K = 5 , n = 25,000 n=25{,}000 n = 25 , 000 , threshold δ ≈ 10.20 \delta\approx10.20 δ ≈ 10.20 .
Different types of convolutions
The analysis in Section 4 uses the SageMean operator R S A G E = D ~ − 1 A ~ R_{\mathrm{SAGE}}=\tilde{D}^{-1}\tilde{A} R SAGE = D ~ − 1 A ~ [4 ] . We consider its linearized GCN counterpart R G C N = D ~ − 1 / 2 A ~ D ~ − 1 / 2 R_{\mathrm{GCN}}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} R GCN = D ~ − 1/2 A ~ D ~ − 1/2 [5 ] . Figure 7 shows that SageMean and GCN behave near-identically: with balanced communities and a moderate δ \delta δ , neighborhoods have roughly equal cardinality, so row- and symmetric-normalization coincide up to a constant. The qualitative ordering between A o r a c l e A^{\mathrm{oracle}} A oracle , A ⊥ A^{\perp} A ⊥ , A ^ \hat{A} A ^ , and A p o p A^{\mathrm{pop}} A pop is preserved across both operators.
The analysis in Section 4 assumes i.i.d. samples Z t ∼ N ( 0 , Σ ) Z_t\sim\mathcal{N}(0,\Sigma) Z t ∼ N ( 0 , Σ ) , but real fMRI time series are temporally autocorrelated [34 ] . We replace the i.i.d. samples with AR(1) processes at ρ ∈ { 0.4 , 0.7 } \rho\in\{0.4,0.7\} ρ ∈ { 0.4 , 0.7 } .
Figure 7. Decoupling the effect of the convolution operator. Each panel fixes a different graph convolution (SAGEMEAN, GCN) and plots normalized ValMSE vs. T T T for Conv ( A , Σ ^ ) \operatorname{Conv}(A,\hat{\Sigma}) Conv ( A , Σ ^ ) under A ∈ { A o r a c l e , A ^ , A ⊥ , A p o p } A \in\{A^{\mathrm{oracle}}, \hat{A}, A^{\perp}, A^{\mathrm{pop}}\} A ∈ { A oracle , A ^ , A ⊥ , A pop } and the no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. β \beta β = single_community_aligned, σ \sigma σ = 1.0, p p p = 20, K K K = 5, n n n = 25,000, k k k = 1 convolution layer, threshold δ ≈ 10.20 \delta\approx10.20 δ ≈ 10.20 .
For an AR(1) process the effective sample size is T e f f ≈ T ( 1 − ρ 2 ) / ( 1 + ρ 2 ) T_{\mathrm{eff}} \approx T(1-\rho^2)/(1+\rho^2) T eff ≈ T ( 1 − ρ 2 ) / ( 1 + ρ 2 ) , so Σ ^ \hat{\Sigma} Σ ^ is noisier at fixed T T T . Figure 8 confirms this: the curves for ρ = 0.4 \rho= 0.4 ρ = 0.4 and ρ = 0.7 \rho= 0.7 ρ = 0.7 are shifted to the right relative to the i.i.d. panel, while the relative ordering between A o r a c l e A^{\mathrm{oracle}} A oracle , A ⊥ A^{\perp} A ⊥ , A ^ \hat{A} A ^ , and A p o p A^{\mathrm{pop}} A pop is preserved. Temporal correlation therefore rescales rather than reshapes the bias-variance tradeoff identified in the main analysis.
Figure 8. Decoupling the effect of temporal correlation. Each panel fixes a different temporal-noise regime for the time series used to estimate Σ ^ \hat{\Sigma} Σ ^ , iid samples (left), AR(1) with ρ = 0.4 \rho= 0.4 ρ = 0.4 (center), AR(1) with ρ = 0.7 \rho= 0.7 ρ = 0.7 (right), and plots normalized ValMSE vs. T T T for SageMean ( A , Σ ^ ) \operatorname{SageMean}(A,\hat{\Sigma}) SageMean ( A , Σ ^ ) under A ∈ { A o r a c l e , A ^ , A ⊥ , A p o p } A \in\{A^{\mathrm{oracle}}, \hat{A}, A^{\perp}, A^{\mathrm{pop}}\} A ∈ { A oracle , A ^ , A ⊥ , A pop } and the no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. β \beta β = single_community_aligned, σ \sigma σ = 1.0, p p p = 20, K K K = 5, n n n = 25,000, k k k = 1 convolution layer, threshold δ ≈ 10.20 \delta\approx10.20 δ ≈ 10.20 .
Small sample size
Our analysis restricts to the population regime n → ∞ n \to\infty n → ∞ . Figure 9 departs from this assumption and varies n ∈ { 400 , 800 , 25,000 } n \in\{400, 800, 25{,}000\} n ∈ { 400 , 800 , 25 , 000 } . At n = 25,000 n = 25{,}000 n = 25 , 000 the population predictions of the main analysis are recovered cleanly. At smaller n n n , finite-sample estimation variance becomes the dominant source of error and the ordering between feature maps is no longer well predicted by the EIV decomposition: smoothing with the correct topology no longer guarantees an improvement over raw features.
Figure 9. Decoupling the effect of the sample size n n n . Each panel fixes a different number of training samples n ∈ { 400 , 800 , 25000 } n \in\{400, 800, 25000\} n ∈ { 400 , 800 , 25000 } and plots normalized ValMSE vs. T T T for SageMean(A A A , Σ ^ \hat{\Sigma} Σ ^ ) under A ∈ { A o r a c l e , A , A ⊥ , A ^ , A p o p } A \in\{A^{\mathrm{oracle}}, A, A^{\perp}, \hat{A}, A^{\mathrm{pop}}\} A ∈ { A oracle , A , A ⊥ , A ^ , A pop } and the no-conv baseline. Mean ± \pm ± 1 SD over 5 seeds. β \beta β = single_community_aligned, σ = 1.0 \sigma= 1.0 σ = 1.0 , p = 20 p = 20 p = 20 , K = 5 K = 5 K = 5 , threshold δ ≈ 10.20 \delta\approx10.20 δ ≈ 10.20 .
Real data
Datasets
ADHD dataset
The ADHD-200 dataset is a multi-site collection of resting-state functional magnetic resonance imaging data targeting attention deficit hyperactivity disorder identification and cognitive assessment [35 ] . We utilized the preprocessed data provided by the Neuro Bureau ADHD-200 Preprocessed repository [36 ] . Specifically, the imaging data were processed using the Athena pipeline. Regional mean time series were extracted using the Craddock 200 (CC200) atlas [37 ] , with 190 retained regions and scan lengths ranging from 55 to 257 time points across 1,198 scans from 768 subjects. Acquisition parameters vary by site, with repetition times (TR) ranging from 1.96 to 2.5 seconds [36 ] . For our analysis, we focus on the following target variables:
Diagnosis: The primary clinical label used for classification, distinguishing between individuals with attention deficit hyperactivity disorder and typical controls.
Inattentive: The inattention symptom score reported in the ADHD-200 phenotypic file, used for regression.
ABIDE dataset
The Autism Brain Imaging Data Exchange (ABIDE) aggregates resting-state functional magnetic resonance imaging data from 17 international sites to investigate Autism Spectrum Disorder (ASD) [38 ] . We utilized the preprocessed data provided by the Preprocessed Connectomes Project (PCP) [39 ] . Specifically, imaging data were processed using the Configurable Pipeline for the Analysis of Connectomes (C-PAC) [40 ] . Based on our preprocessing selection, the signals underwent band-pass filtering and global signal regression. Regional mean time series were obtained via the Nilearn library [41 ] . The benchmark uses the Craddock 200 atlas [37 ] with 200 regions, while the controlled experiments use Harvard-Oxford with 106 retained regions. Acquisition parameters vary across the 17 sites, with the most common repetition time (TR) being 2.0 seconds and a typical scan duration of approximately 5–8 minutes per subject [38 ] . For our analysis, we focus on the following target variables:
DX_GROUP: The primary diagnostic label used for binary classification, distinguishing between individuals with ASD and Typical Controls (TC).
AGE_AT_SCAN: The age of the subject at the time of the scan, in years, used for regression.
Frankfurt dataset
The dataset consists of concurrent EEG-fMRI recordings from 72 healthy adults, comprising 45 females and 27 males with an age range of 19 to 48 years. Participants underwent 52-minute resting-state scans where they were instructed to remain still with their eyes closed. Despite these instructions, many participants transitioned through various stages of NREM sleep, with 64 subjects entering stage N1, 43 entering N2, and 17 reaching stage N3. The imaging data were acquired with a repetition time (T R TR T R ) of 2080 ms [42 ] . The supplied regional time series contain 1,505 frames. Our loader removes the first five frames, leaving 1,500 frames aligned with the supplied hypnograms. For spatial definition, we utilized a parcellation consisting of 294 regions of interest, which included 286 cortical nodes and 8 subcortical nodes [43 ] . The benchmark uses all 294 regions. The controlled experiments average regional time series within the 15 groups specified by the supplied atlas mapping. For each multidimensional brain time series, an associated time series indicates the sleep stage at each time point, categorized as Wake (N0), N1, N2, and N3. A distinct characteristic of this dataset is that the target variable (y y y ) is also time-dependent. Consequently, when applying the rolling window approach with a specific window length and stride, the target variable must be aggregated within the same temporal window. We construct the window-level targets separately for the two tasks:
sleep_frac: The fraction of time points in the window spent asleep (N1 to N3), used for controlled regression.
sleep_wake: The benchmark classification label indicates whether the most frequent original sleep stage in the window is sleep (N1 to N3) or wake (N0).
Benchmark experiments
Experiment set-up
For each scan, we use the supplied regional mean time series from the chosen parcellation and apply a rolling-window approach: ABIDE and Frankfurt use overlapping windows of length T T T with stride s s s , while ADHD uses the full series as one window. Within each window we compute the sample correlation matrix C ^ ∈ R p × p \hat{C} \in\mathbb{R}^{p \times p} C ^ ∈ R p × p , where p p p is the number of regions. These correlation matrices serve as input features for all downstream models, used both as node features and as the basis for graph construction in the GNN baselines. We report window-level test metrics, with means and standard deviations over 10 random seeds.
Dataset-specific settings. Table 3 reports the parcellation, number of ROIs, window length T T T , stride, and number of subjects for each dataset.
Table 3. Dataset-specific experimental settings. Subjects are those with the target available, split 60/20/20 by subject. For ABIDE and Frankfurt, the stride is set to [ 0.10 ⋅ T ] [0.10 \cdot T] [ 0.10 ⋅ T ] ; ABIDE uses 4 windows per subject and Frankfurt all 66. For ADHD, a single window is used, corresponding to the maximum available time-series length. Targets: age at scan (ABIDE), diagnosis (ADHD), sleep versus wake per window (Frankfurt).
Model hyperparameters. Table 4 reports the most frequently selected hyperparameters for each model across benchmark runs. Hyperparameters are tuned separately for each model, dataset–task panel, and seed.
Table 4. Most frequently selected hyperparameters across benchmark runs. All neural models were trained with 10 seeds per dataset–task panel; GAT uses a single attention head. Graph density is τ = 0.10 \tau= 0.10 τ = 0.10 for all graph-based benchmark models.
Controlled experiments
We provide further details of the controlled experiments introduced in § 6 , followed by the full results for the progressive relaxation of assumptions, the comparisons of convolution operators and graph densities on ABIDE, and the extensions to the ADHD and Frankfurt datasets. Throughout, the independent graph A e s t ⊥ A_{\mathrm{est}}^{\perp} A est ⊥ is built from the furthest non-overlapping window of the same subject, to limit the effect of autocorrelation.
Progressive relaxation of assumptions
Starting from the configuration in the main text, we first introduce ReLU while retaining the vectorized readout and a fixed number of windows across T T T . The first block of Table 5 shows that the oracle proxy remains the strongest graph construction at every T T T . Its mean accuracy exceeds that of the no-convolution baseline at T = 5 , 15 , 25 T = 5, 15, 25 T = 5 , 15 , 25 , but none of these gains reaches significance at the 5% level. At T = 40 T = 40 T = 40 , even the oracle proxy falls below the baseline. Thus, the broad ordering persists after introducing the nonlinearity, although the evidence for a smoothing benefit is weaker. Neither estimated graph significantly improves on the baseline.
Table 5: Progressive relaxation of the assumptions of Table 2. Same cell and conventions, SageMean, τ = 0.10 \tau= 0.10 τ = 0.10 ; each block adds one relaxation to the previous one, starting from Table 2. Mean ± 1 \pm1 ± 1 SD over 20 seeds; paired t t t -test over seeds against C ^ \hat{C} C ^ (left) or zero (right): ∗ p < 0.10 ^{*}p < 0.10 ∗ p < 0.10 , ∗ ∗ p < 0.05 ^{**}p < 0.05 ∗∗ p < 0.05 , ∗ ∗ ∗ p < 0.01 ^{***}p < 0.01 ∗∗∗ p < 0.01 .
Table 5.
We next retain all available windows, allowing n n n to vary with T T T . The no-convolution baseline improves at shorter window lengths: at T = 5 T = 5 T = 5 , its accuracy rises from 0.558 to 0.593. The oracle advantage is now confined to this shortest window, where it reaches +0.037 accuracy (p < 0.01 p < 0.01 p < 0.01 ); at T ≥ 15 T \ge15 T ≥ 15 , the oracle proxy no longer improves on the baseline. The remaining advantage is substantially reduced when the graph must be estimated from a separate window: at T = 5 T = 5 T = 5 , this replacement lowers accuracy by 0.030 (p < 0.05 p < 0.05 p < 0.05 ). Neither the separate-window nor the same-window graph significantly outperforms the no-convolution baseline.
Finally, replacing vectorization with mean pooling removes the remaining oracle advantage at T = 5 T = 5 T = 5 : the oracle-minus-baseline difference changes from +0.037 to −0.003. In this final configuration, no graph construction significantly improves on the corresponding no-convolution baseline at any tested T T T . For ABIDE, the benefit observed under the initial restrictions therefore does not survive the full progression toward the deployed pipeline, connecting the controlled experiments to the benchmark findings.
Extensions to other convolutions and datasets
GAT lies outside our linear theory, because its attention weights are computed from the same noisy matrix as the features and therefore inherit its noise. GAT follows the same qualitative pattern as SageMean: in the simulation-like setting, the oracle proxy helps at short windows, but neither estimated graph significantly outperforms its matched no-convolution baseline. In the deployed setting, neither operator benefits significantly from any graph construction.
Table 6: GAT in place of SageMean. Same cell and conventions as Table 2, τ = 0.10 \tau= 0.10 τ = 0.10 , with one GAT convolution (8 heads of 8); the C ^ \hat{C} C ^ column is the same architecture with message passing removed. Mean ± 1 \pm1 ± 1 SD over 20 seeds; paired t t t -test over seeds against C ^ \hat{C} C ^ (left) or zero (right): ∗ p < 0.10 ^{*}p < 0.10 ∗ p < 0.10 , ∗ ∗ p < 0.05 ^{**}p < 0.05 ∗∗ p < 0.05 , ∗ ∗ ∗ p < 0.01 ^{***}p < 0.01 ∗∗∗ p < 0.01 .
Table 6.
On ADHD, the oracle proxy provides a modest benefit at T = 7 T = 7 T = 7 , which is lost when the graph is estimated from a separate window; at T = 40 T = 40 T = 40 , even the oracle proxy falls below the baseline. In the deployed setting, no subject-specific graph significantly improves prediction, although the population graph provides a small gain at T = 40 T = 40 T = 40 .
Frankfurt differs because sleep state changes within a scan: changing T T T changes both connectivity-estimation noise and the window-level sleep fraction being predicted. The full-series graph also averages across sleep states and may therefore poorly represent an individual window. In the simulation-like setting, the oracle proxy is strongest at the shortest windows but weakest at T = 45 T = 45 T = 45 , while the separate-window graph performs best from T = 14 T = 14 T = 14 onward. Graph benefits persist in the deployed setting, with all four constructions significantly improving prediction at T = 25 T = 25 T = 25 and 45.
Table 7. ADHD. Subject-level test R 2 R^2 R 2 for the inattention score on ADHD-200 (CC200, p = 190 p=190 p = 190 ) with SageMean(A , C ^ A,\widehat{C} A , C ), one convolution, τ = 0.10 \tau=0.10 τ = 0.10 , in the simulation-like scenario and the deployed pipeline. Mean ± \pm ± 1 SD over 20 seeds; paired t t t -test over seeds against C ^ \widehat{C} C (left) or zero (right): ∗ p < 0.10 {}^{*}p<0.10 ∗ p < 0.10 , ∗ ∗ p < 0.05 {}^{**}p<0.05 ∗∗ p < 0.05 , ∗ ∗ ∗ p < 0.01 {}^{***}p<0.01 ∗∗∗ p < 0.01 . The train-mean predictor has R 2 = − 0.03 R^2=-0.03 R 2 = − 0.03 .
Table 8. Frankfurt. Window-level test R 2 R^2 R 2 for the fraction of the window spent asleep on the Frankfurt dataset (15 networks) with SageMean(A , C ^ A,\widehat{C} A , C ), one convolution, τ = 0.10 \tau=0.10 τ = 0.10 , in the simulation-like scenario and the deployed pipeline. The target is defined per window, so A e s t o r a c l e A_{\mathrm{est}}^{\mathrm{oracle}} A est oracle is built from a series whose label changes within the scan. Mean ± \pm ± 1 SD over 20 seeds; paired t t t -test over seeds against C ^ \widehat{C} C (left) or zero (right): ∗ p < 0.10 {}^{*}p<0.10 ∗ p < 0.10 , ∗ ∗ p < 0.05 {}^{**}p<0.05 ∗∗ p < 0.05 , ∗ ∗ ∗ p < 0.01 {}^{***}p<0.01 ∗∗∗ p < 0.01 . The train-mean predictor has R 2 = − 0.03 R^2=-0.03 R 2 = − 0.03 .
Effect of graph density
We repeat the ABIDE simulation-like experiment at graph densities τ = 0.05 \tau=0.05 τ = 0.05 and 0.20 0.20 0.20 , comparing them with τ = 0.10 \tau=0.10 τ = 0.10 in the main text. At T = 5 T=5 T = 5 , the oracle proxy significantly improves accuracy at all three densities, with gains of 0.019, 0.022, and 0.024 for τ = 0.05 \tau=0.05 τ = 0.05 , 0.10, and 0.20, respectively. However, neither the separate-window nor the same-window graph significantly outperforms the no-convolution baseline at any tested density or T T T . The oracle benefit also varies with density: at T = 25 T=25 T = 25 , it is significant only for τ = 0.10 \tau=0.10 τ = 0.10 , while at T = 40 T=40 T = 40 its mean performance falls below the baseline at every density. Thus, making the graph sparser or denser does not consistently recover a predictive advantage in this setting.
Practical recommendations
Our results suggest a few guidelines for connectome GNN pipelines. First, convolutions help only at short windows: when longer recordings are available, longer windows combined with graph-agnostic models are likely to perform better, so convolutions should be used with care. Second, estimating the graph from a longer series than the window, as the oracle proxy does, extends the range of T T T over which convolutions help, provided the target does not change within the scan. Third, building the graph from the same window as the features adds a double-dipping term of no consistent sign, which makes results less stable rather than systematically worse; cross-fitting removes this term but not the graph-estimation error, which is the main bottleneck. Fourth, smoothing can only help when the target is community-smooth: if the signal sits in single edges or in contrasts within a community, smoothing removes it. Finally, when these conditions are met, the graph density must be tuned; otherwise, no choice of density recovers a gain.
Table 9. Threshold ablation of Table 2 . Same cell and conventions, SageMean, simulation-like scenario, at τ = 0.05 \tau=0.05 τ = 0.05 and τ = 0.20 \tau=0.20 τ = 0.20 (τ = 0.10 \tau=0.10 τ = 0.10 is Table 2 ); the C ^ \widehat{C} C column does not depend on τ \tau τ . Mean ± 1 \pm1 ± 1 SD over 20 seeds; paired t t t -test over seeds against C ^ \widehat{C} C (left) or zero (right): ∗ p < 0.10 ^{*}p<0.10 ∗ p < 0.10 , ∗ ∗ p < 0.05 ^{**}p<0.05 ∗∗ p < 0.05 , ∗ ∗ ∗ p < 0.01 ^{***}p<0.01 ∗∗∗ p < 0.01 .
Compute resources
All experiments were run on CPU nodes equipped with Intel Broadwell (28 cores at 2.4 GHz, 64 GB memory) and Intel Skylake (40 cores at 2.4 GHz, 96 GB memory) processors, for a total of approximately 3,000 CPU hours.
Broader impacts
Our work is a theoretical and methodological analysis of when graph neural network methods provide statistical benefits over simpler baselines in brain connectome analysis. By clarifying the regimes in which these methods help versus hurt, we hope to inform more reliable use of machine learning in clinical neuroscience applications such as the diagnosis of psychiatric and neurological disorders. We do not introduce new models, datasets, or deployment ready systems, and we do not foresee direct negative societal impacts of this work.
LLM usage declaration
We used large language models (LLMs) as coding assistants to help implement and run some of the experimental pipelines, and as writing assistants to copy edit and improve the clarity of the manuscript.