acceptodds
Under review as a conference paper at ICLR 2027

Understanding Feature Learning in Graph Contrastive Learning: Neighborhood Correlation and Theory-Guided Augmentation

Abstract

Graph contrastive learning (GCL) learns representations by contrasting augmented graph views, where each node representation aggregates information from its local neighborhood. Despite the empirical success of GCL, how neighborhood structure shapes the feature-learning process remains theoretically underexplored. This paper provides a theoretical characterization of feature learning in GCL under a sparse coding model that separates task-relevant features with stronger neighborhood correlation from task-irrelevant features with weaker neighborhood correlation. Our analysis reveals a selective feature-learning mechanism: neighborhood aggregation preferentially amplifies features with stronger neighborhood correlation while suppressing less correlated features. We quantitatively characterize how feature learning and downstream performance depend on feature overlap, the fraction of correlated neighbors, and neighborhood size. Guided by these theoretical insights, we propose a plug-in augmentation strategy, Theory-Guided Neighborhood Augmentation (TGNA), that constructs and selects graph views using an empirical measure of neighborhood correlation. Experiments on synthetic and real-world graphs support our theoretical predictions and show that TGNA generally improves downstream performance across various GCL frameworks while reducing contrastive training cost.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph Contrastive Learning, Graph Augmentation, Feature Learning, Generalization, Neighborhood Aggregation

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_xBnCOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper studies feature learning dynamics in graph contrastive learning (GCL). Under a sparse-coding model with neighborhood-correlated task-relevant features and weakly correlated task-irrelevant features, the authors derive training-dynamics results suggesting that neighborhood aggregation preferentially amplifies correlated features. Based on these insights, they propose Theory-Guided Neighborhood Augmentation (TGNA), which selects graph views according to a neighborhood-correlation criterion. Experiments on synthetic and real-world datasets demonstrate improved downstream performance and reduced training cost across several GCL frameworks.

Critical strengths

The paper tackles an interesting and underexplored question: how neighborhood aggregation affects feature-learning dynamics in graph contrastive learning. The distinction between strongly and weakly neighborhood-correlated latent features provides an intuitive perspective on representation learning in GCL.

The proposed TGNA plug-in is simple and broadly applicable. Empirical evaluation across multiple GCL frameworks and datasets suggests that the method can often improve downstream performance while reducing training cost.

Critical weaknesses

The key theoretical assumptions do not appear sufficient for the claimed selective feature-learning mechanism. Assumption 3.1 defines neighborhood correlation through latent support overlap, but the nonzero coefficients take values in {-1,1}; shared support therefore does not guarantee positive correlation and may instead cause cancellation under aggregation. In addition, the proof appears to treat the aggregated noise terms of the two augmented views as independent, although both views contain the same center node and thus share its noise. The paper should state the required sign-dependence assumption and explicitly account for the cross-view covariance induced by the shared center. These issues directly affect the feature-growth analysis underlying Theorem 3.1.

The connection between the latent theory and the practical TGNA method is insufficiently established. The theory relies on task-conditioned latent support-overlap parameters, whereas TGNA replaces them with cosine similarity of raw features without showing that the proxy preserves the relevant latent correlation. Moreover, TGNA simultaneously changes neighborhood selection, anchor retention, and the negative-sampling pool, so the reported gains cannot be attributed specifically to the proposed theoretical criterion. Matched controls using random and similarity-based sampling at the same anchor ratio, neighborhood size, negative-set size, and computational budget are needed to validate the “theory-guided” claim.

Questions for authors
  1. Assumption 3.1 constrains overlap between latent feature supports, but the active coefficients can have opposite signs. What assumption ensures positive correlation between shared feature coefficients across neighboring nodes and augmented views? Would Theorem 3.1 still hold if the signs were conditionally independent given support overlap?

  2. Although the two augmented views have disjoint neighbor sets, both include the same center node. How does the proof account for the resulting covariance between their aggregated noise terms? Can the authors show that the shared-center term is negligible under the theorem’s parameter scaling?

  3. Under what conditions does raw-feature cosine similarity provide a valid proxy for the latent task-relevant support-overlap quantity α_1? Could the authors report correlations between the empirical TGNA score and the corresponding latent quantity in the synthetic experiments?

  4. Can the authors provide matched ablations that separate the effects of the TGNA score, similarity-based neighborhood filtering, anchor-set reduction, and the changed negative-sampling pool?

7 comments
AuthorsOpenReview ↗

Response to Reviewer xBnC Part I

Q1 (Weakness 1): The key theoretical assumptions do not appear sufficient for the claimed selective feature-learning mechanism. Assumption 3.1 defines neighborhood correlation through latent support overlap, but the nonzero coefficients take values in {-1,1}; shared support therefore does not guarantee positive correlation and may instead cause cancellation under aggregation. In addition, the proof appears to treat the aggregated noise terms of the two augmented views as independent, although both views contain the same center node and thus share its noise. The paper should state the required sign-dependence assumption and explicitly account for the cross-view covariance induced by the shared center. These issues directly affect the feature-growth analysis underlying Theorem 3.1.

A1: We thank the reviewer for identifying these important points.

1. Sign-consistent neighborhood correlation. We agree that support overlap alone does not guarantee positive feature correlation. Our intended data model assumes that shared active latent features have matching signs, rather than independently resampled signs. We will explicitly incorporate this condition into Assumption 3.1 as follows.

Assumption 3.1 (Neighborhood structure and sign-consistent feature correlation). For every center node vkv_k, the two augmented views satisfy $ |\mathcal N_A(k)|=|\mathcal N_B(k)|=K,\qquad \mathcal N_A(k)\cap\mathcal N_B(k)=\varnothing. $ For each q∈A,Bq\in{A,B} and r∈1,2r\in{1,2}, there exists Nq,r(k)⊆Nq(k)\mathcal N_{q,r}(k)\subseteq\mathcal N_q(k) such that $ |\mathcal N_{q,r}(k)|\geq\rho_r K, \qquad |S_k^r\cap S_j^r|\geq\alpha_r|S_k^r|, \quad \forall v_j\in\mathcal N_{q,r}(k), $ with the additional sign-consistency condition $ z_{k,l}^r=z_{j,l}^r,\qquad \forall l\in S_k^r\cap S_j^r. $ The correlation parameters satisfy α1ρ12>α2ρ22\alpha_1\rho_1^2>\alpha_2\rho_2^2.

2. Cross-view covariance induced by the shared center node.

We thank the reviewer for pointing out that the two augmented views share the same center-node noise and are therefore not independent, even though their sampled neighborhoods are disjoint. We agree that this cross-view dependence should be explicitly accounted for in the analysis. Specifically, the shared center node introduces the following nonzero covariance term: $\frac{\sigma^2}{(K+1)^2} \langle w_i,M_j\rangle. $ Under our theoretical scaling K=Θ(log⁡d)K=\Theta(\log d), this term is o(1)o(1), provided that σ2⟨wi,Mj⟩=o((log⁡d)2)\sigma^2\langle w_i,M_j\rangle=o((\log d)^2). We will revise the proof to explicitly account for this cross-view covariance and establish that its contribution is negligible relative to the leading feature-growth terms, rather than assuming independence between the two views.

AuthorsOpenReview ↗

Response to Reviewer xBnC Part II

Q2 (Weakness 2): The connection between the latent theory and the practical TGNA method is insufficiently established. The theory relies on task-conditioned latent support-overlap parameters, whereas TGNA replaces them with cosine similarity of raw features without showing that the proxy preserves the relevant latent correlation. Moreover, TGNA simultaneously changes neighborhood selection, anchor retention, and the negative-sampling pool, so the reported gains cannot be attributed specifically to the proposed theoretical criterion. Matched controls using random and similarity-based sampling at the same anchor ratio, neighborhood size, negative-set size, and computational budget are needed to validate the “theory-guided” claim.

A2: We thank the reviewer for this constructive suggestion. We address the connection between the theoretical correlation criterion and its practical approximation, followed by additional ablations that disentangle the components of TGNA.

1. Theoretical motivation for using raw-feature cosine similarity.*

Under our sparse-coding model, the raw node features satisfy xk=Mzk+ξkx_k=Mz_k+\xi_k, where M=[M1∣M2]M=[M^1\mid M^2]. Since the dictionary columns are orthonormal, the inner product between two node features can be decomposed as

+ \langle z_k^{(2)},z_j^{(2)}\rangle + \varepsilon_{kj},$$ where $\varepsilon_{kj}$collects the noise-related terms. Under the sign-consistency condition clarified in our response to Weakness 1, shared active latent coordinates contribute positively to the corresponding inner product. Thus, raw-feature similarity contains information about latent support overlap. When the contribution from strongly neighborhood-correlated features is sufficiently distinguishable from the contributions of weakly correlated features and noise, cosine similarity can serve as an observable proxy for latent neighborhood correlation. We emphasize that this does not imply that thresholding raw cosine similarity always isolates $M^1$-correlated neighbors. Rather, the proxy is motivated by the relationship between observable similarity and latent overlap under the considered data model. We further validate this relationship using synthetic data, where the latent features and correlation parameters are known. The resulting empirical correlation is strong (Pearson correlation 0.9814 and Spearman correlation 0.9970), supporting the use of this proxy in the considered setting. Our Experimental settings are $d=10, d'=20, d_1=200$, and additive Gaussian noise $\xi\sim\mathcal N(0,0.01I_{d_1})$, with (K=15) and $\rho_1=0.7$. We fixed $\alpha_2=0.2$ and \$\rho_2=0.25 \$while varying the latent feature-overlap ratio $\alpha_1$ from 0.1 to 1.0 . See Figure 1 at the link https://storage.googleapis.com/iclr2027_figures/ICLR27_Ablations.pdf **2. Ablation studies separating anchor selection and view construction.** TGNA involves two components: selecting eligible anchor nodes according to the proposed criterion and constructing augmented views based on neighborhood similarity. We agree that evaluating these components only in combination makes it difficult to identify their individual contributions. We therefore conducted two additional ablations using GRACE as the backbone: - **Anchors only:** Retain the anchors selected by TGNA, but use the baseline GRACE augmentation procedure to construct views. - **Views only:** Retain the original anchor set. Apply TGNA view construction to eligible nodes and baseline augmentation to the remaining nodes. The downstream classification results are summarized below. | Method | Cora | AmazonPhoto | AmazonComputers | PubMed | CS | |:---|:---:|:---:|:---:|:---:|:---:| | anchors_only | **84.24±0.31** | 91.91±0.17 | 83.18±0.22 | 85.67±0.05 | 92.01±0.15 | | views_only | 83.92±0.06 | 92.28±0.21 | 85.59±0.51 | **86.59±0.04** | 91.99±0.07 | | GRACE+TGNA | 84.04±0.17 | **92.51±0.23** | **85.69±0.29** | 86.10±0.22 | 92.36±0.05 | | GRACE | 83.54±0.64 | 91.29±0.19 | 82.23±0.25 | 85.90±0.04 | **92.65±0.22** | The results show that both components can independently contribute to improved downstream performance. Anchor selection alone achieves the best result on Cora, while view construction alone performs best on PubMed. Combining both components yields the highest accuracy on Amazon Photo and Amazon Computers. These findings suggest that TGNA's benefits are not solely due to anchor-set reduction, although the relative importance of the two components varies across datasets.
AuthorsOpenReview ↗

Response to Reviewer xBnC Part III

Q3 (Question 1): Assumption 3.1 constrains overlap between latent feature supports, but the active coefficients can have opposite signs. What assumption ensures positive correlation between shared feature coefficients across neighboring nodes and augmented views? Would Theorem 3.1 still hold if the signs were conditionally independent given support overlap?

A3: As clarified in our response to Weakness 1 (A1), our intended data model assumes sign consistency on shared active latent coordinates, and we will explicitly incorporate this condition into Assumption 3.1.

If the signs were conditionally independent given support overlap, the shared feature contributions could cancel during neighborhood aggregation. Therefore, support overlap alone would not guarantee the selective feature amplification required by Theorem 3.1, and the theorem would not necessarily hold under the current assumptions. Please refer to A1 for the revised assumption and further details.

Q4 (Question 2): Although the two augmented views have disjoint neighbor sets, both include the same center node. How does the proof account for the resulting covariance between their aggregated noise terms? Can the authors show that the shared-center term is negligible under the theorem’s parameter scaling?

A4: We thank the reviewer for this question. Please refer to our response to Weakness 1 (A1),

Q5 (Question 3): Under what conditions does raw-feature cosine similarity provide a valid proxy for the latent task-relevant support-overlap quantity α_1? Could the authors report correlations between the empirical TGNA score and the corresponding latent quantity in the synthetic experiments?

A5: We thank the reviewer for this question. Under our sparse-coding model, xk=Mzk+ξkx_k=Mz_k+\xi_k, where M=[M1∣M2]M=[M^1\mid M^2] is an orthonormal dictionary, we have

=\langle z_k^{(1)},z_j^{(1)}\rangle + \langle z_k^{(2)},z_j^{(2)}\rangle + \varepsilon_{kj},$$ where $\varepsilon_{kj}$ collects the noise-related terms. Under the sign-consistency condition clarified in A1, shared active latent coordinates contribute positively to the inner product. When the contribution from $M^1$ is sufficiently distinguishable from those of $M^2$ and dense noise, raw-feature cosine similarity $s_{kj}=\langle x_k,x_j\rangle/(|x_k|_2|x_j|_2)$ can serve as a practical proxy for latent neighborhood correlation. **Synthetic validation.** We conduct controlled experiments using the sparse-coding model with $d=10, d'=20, d_1=200,$ neighborhood size $K=15, \rho_1=0.7$, and Gaussian noise covariance $0.01Id_1$. We vary the latent support-overlap parameter $\alpha_1$ from 0.1 to 1.0 while keeping the remaining parameters fixed. For each configuration, we compute the empirical neighborhood similarity $\hat{\alpha}$ by averaging the raw-feature cosine similarities $s_{kj}$ over the selected anchor-neighbor pairs, and compare $\hat{\alpha}$ with the corresponding ground-truth $\alpha_1$. The resulting correlations are Pearson 0.9814, Spearman 0.9970, and R2=0.9632. See Figure 1 at the link https://storage.googleapis.com/iclr2027_figures/ICLR27_Ablations.pdf. **Additional validation of the full TGNA criterion.** We will further compare the empirical TGNA score $\hat{S}_{\mathrm{TGNA}} = \hat{\alpha}\hat{\rho}^2(\hat{K}+1)$ with the corresponding latent criterion $S_{latent} = \alpha_1\rho_1^2(K+1)$, Our model configuration settings for this experiment is $d=10, d'=20, d_1=200$, and additive Gaussian noise $\xi\sim\mathcal N(0,0.01I_{d_1})$, with K=15. We fixed $\alpha_2=0.2$ and $\rho_2=0.25$ while varying the both latent feature-overlap ratio $\alpha_1$ and the fraction of simila neighbors $\rho_1$ from 0.1 to 1.0 . The resultant correlations are Pearson 0.9776, Spearman 0.9798 and R2=0.9557. See Figure 2 at the link https://storage.googleapis.com/iclr2027_figures/ICLR27_Ablations.pdf **Q6 (Question 4):** Can the authors provide matched ablations that separate the effects of the TGNA score, similarity-based neighborhood filtering, anchor-set reduction, and the changed negative-sampling pool? **A6:** We thank the reviewer for the constructive suggestion. To disentangle the effects of TGNA's anchor selection and view construction, we conducted two additional ablation studies, Anchor selection only and View construction only, as discussed in A2 to weakness 2. Regarding negative sampling, TGNA does not introduce a separate negative-sampling algorithm. However, restricting the anchor set can change the set of representations participating in the contrastive objective. We will clarify this distinction and the corresponding implementation details in the revised manuscript.
Reviewer_gUSWOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

The paper aims to contribute some theory on how Graph Contrastive learning (GCL) learns features. Mainly, they aim to proove that GCL learns features that are overlaping in a shared neighbourbood more than those that do not i.e., given feature F it can be divided into features that overlap more in different neighbourhoods (F1) and those that donot (F2) such that F = [F1, F2], then GCL will tend to learn more F1 and not F2.

Critical strengths
  • The paper aims to address a real topic: namely explainable AI
  • The paper then tries to build a framework for improving existing baselines based on the theory
Critical weaknesses

Major

  • theory was hard to follow, tried to have a look though, but cannot assert complete correctness due to hardness to follow
  • seems some assumptions where a little too strict e.g., K, assumption, and disjoint assumption in lines 227-228 seem too strict and generally not the case?
  • other assumptions seem to already assume what the paper sets out to proove? e.g., a little stange the inequality assumption in 230 as this basically is one of the points to be proven?
  • Figure 1a shows epochs vs the ratio, but we will also like to know the losses corresponding to each data point
  • Figure 1b shows a flat point at some point before decreasing again, would have been goo to see more data points on this linear scale to support the claim
  • the baselines in table 1 can also take the tgna right? would like to see its impact on them.

Minor

  • Line 211 missing link on Remark
  • line 202 claim is not consistent with line 086, should this not be the reciprocal
  • Some notation description not well defineed eg q in {A, B} neither, q, nor A nor B are defined so hard to follow
Questions for authors
  • please see weakness questions above
3 comments
AuthorsOpenReview ↗

Response to Reviewer gUSW Part I

Q1 (Weakness 1): theory was hard to follow, tried to have a look though, but cannot assert complete correctness due to hardness to follow

A1: We thank the reviewer for taking the time to examine our theoretical analysis. We acknowledge that the presentation can be improved and will revise the manuscript to make the main results and proof structure easier to follow. Below, we clarify our two main theoretical contributions.

1. Theorem 3.1: Selective feature learning during GCL pretraining. Under Assumption 3.1, Theorem 3.1 establishes that the time-averaged GCL objective becomes o(1) (Eq. 11). More importantly, it characterizes selective feature learning at the neuron level (Eq. 12). Specifically, for each neuron, the coefficients of its selected M1M^1 features have nontrivial lower bounds, whereas those of M2M^2 features have substantially smaller upper bounds. Furthermore, for every strongly neighborhood-correlated feature Mj1M_j^1, at least (1) neurons selectively learn this feature, with negligible alignment with other M1 features and suppressed contributions from M2M^2 features and noise directions. Together, these results demonstrate that GCL preferentially learns strongly neighborhood-correlated features while suppressing weaker ones.

2. Theorem 3.2: Downstream learning using pretrained representations. Theorem 3.2 considers a downstream binary node-classification task, where each node's label is determined solely by its task-relevant latent features zk(1)z_k^{(1)}, i.e., yk=sign⁡(⟨u⋆,zk1⟩)y_k=\operatorname{sign}(\langle u^\star,z_k^1\rangle), while the task-irrelevant features zk(2)z_k^{(2)} do not affect the label. We train a linear classifier on the pretrained GCL representations to predict these labels. Theorem 3.2 establishes a bound on the downstream training objective (Eq. 14), showing that the learned representations support successful classification under the stated assumptions. Moreover, the bound explicitly depends on α1ρ12(K+1)\alpha_1\rho_1^2(K+1), demonstrating how stronger neighborhood correlation improves the downstream learning guarantee.

If there are other specific parts of the theoretical results or proofs that the reviewer finds difficult to follow, we would be happy to provide further explanations and clarifications to address your concerns.

Q2 (Weakness 2): seems some assumptions where a little too strict e.g., K, assumption, and disjoint assumption in lines 227-228 seem too strict and generally not the case?

A2 (Weakness 2): Assumptions on neighborhood size and disjointness.

A2: We thank the reviewer for raising these concerns. We agree that real-world graphs generally have heterogeneous node degrees and that graph views may have overlapping neighborhoods. The fixed neighborhood size and disjointness assumptions are introduced to make the theoretical analysis tractable, rather than imposing restrictions on the original graph. Our main theoretical insight is that neighborhood aggregation preferentially amplifies strongly correlated features, leading to selective feature learning.

Fixed neighborhood size K. A natural theoretical extension is to allow node- and view-dependent neighborhood sizes Kk,q∈[Kmin,Kmax]K_{k,q}\in [K_{min},K_{max}]. When KminK_{min} and KmaxK_{max} are of the same order, we expect the main feature-selection mechanism and its scaling behavior to remain unchanged, with modified bounds and training intervals. More specifically, the unwanted-feature coefficient bound in Eq. (12), which scales with 1/K+11/\sqrt{K+1}, suggests a conservative dependence on $ 1/\sqrt{K_{min}+1}$under heterogeneous neighborhood sizes. Other parts of the proof, including the gradient bounds and admissible training interval, may additionally depend on K. A formal extension would require corresponding modifications to the supporting lemmas. Importantly, TGNA already accommodates heterogeneous degrees in the original graph by selecting eligible anchors and sampling neighborhoods of a prescribed size (Section 4).

Disjoint neighborhoods across views. Our proposed TGNA algorithm explicitly constructs two views with disjoint neighborhoods for each anchor (Section 4). Thus, this assumption is consistent with our proposed augmentation strategy and does not require the original graph to have disjoint neighborhoods. We do not claim that disjoint views are optimal or that overlapping views are ineffective. Rather, our theoretical guarantees are established for the disjoint setting, while extending the analysis to overlapping views is beyond the scope of the present work and we will leave it for future work.

We will clarify the distinction between assumptions on the constructed graph views and properties of the original graph, as well as the scope of our theoretical guarantees, in the revised manuscript.

AuthorsOpenReview ↗

Response to Reviewer gUSW Part II

Q3(Weakness 3): other assumptions seem to already assume what the paper sets out to proove? e.g., a little stange the inequality assumption in 230 as this basically is one of the points to be proven?

A3: We thank the reviewer for raising this concern. We would like to clarify that the condition α1ρ12>α2ρ22\alpha_1\rho_1^2>\alpha_2\rho_2^2 is an assumption about the underlying data distribution, not about the learned representations or training dynamics. It specifies that features in M1M^1 exhibit stronger neighborhood correlation than those in M2M^2, but does not assume that GCL will preferentially learn M1M^1.

What we prove in Theorem 3.1 is that this difference in neighborhood correlation leads to selective feature learning through GCL training: neurons preferentially learn features in M1 while suppressing those in M2M^2. We further quantify how neighborhood correlation affects training efficiency and downstream learning in Theorems 3.1 and 3.2. Thus, the assumption characterizes the data structure, whereas our theoretical results establish its consequences for GCL learning dynamics and downstream performance. We will clarify this distinction in the revised manuscript.

Q4 (Weakness 4): Figure 1a shows epochs vs the ratio, but we will also like to know the losses corresponding to each data point

A4: We thank the reviewer for the suggestion. In Figure 1a, we set a fixed target training loss and measure the number of epochs required to reach this target under different neighborhood-correlation settings. The purpose is to examine how the training time depends on the theoretical scaling factor 1/α1ρ12(K+1)1/\sqrt{\alpha_1\rho_1^2(K+1)}

To provide the requested information, we additionally report the actual training losses recorded when each run first reaches the target. As shown in the table below, these losses range from 0.0046 to 0.0059, remaining close to the common target loss of 0.005. Thus, the differences in training epochs in Figure 1a reflect the time required to reach approximately the same training objective, rather than comparisons at substantially different loss levels.

We will include these loss values and clarify the stopping criterion in the revised manuscript.

Table: Exact loss values across different settings, evaluated at x=1/α1ρ12(K+1)x=1/\sqrt{\alpha_1\rho_1^2(K+1)}.

α1\alpha_1=0.6α1\alpha_1=0.7α1\alpha_1=0.8α1\alpha_1=0.9
xLossxLossxLossxLoss
0.29880.00560.27950.00560.26350.00570.25000.0049
0.32940.00530.31250.00580.29280.00520.27770.0050
0.35350.00460.33200.00590.32270.00580.31050.0054
0.43240.00560.42680.00560.37350.00540.34930.0056

Q5 (Weakness 5): Figure 1b shows a flat point at some point before decreasing again, would have been goo to see more data points on this linear scale to support the claim

A5: Thank you for the great suggestion. We have added more points. Please see Figure 3 at this link: https://storage.googleapis.com/iclr2027_figures/ICLR27_Ablations.pdf

Q6 (Weakness 6): the baselines in table 1 can also take the tgna right? would like to see its impact on them.

A6: We thank the reviewer for this suggestion. TGNA is designed as a plug-in replacement for graph augmentation, and Table 1 already evaluates its impact on five representative GCL frameworks: GRACE, GCA, HomoGCL, Str-GCL, and SpikeGCL.

The three additional baselines, AS-GCL, NDSCL, and NCLA, also employ graph views, but their augmentation mechanisms are more closely integrated with other components of their frameworks. Specifically, AS-GCL combines spectral augmentation with asymmetric diffusion encoders, NDSCL combines diffusion augmentation with debiased negative sampling and semi-supervised learning, and NCLA jointly learns graph augmentations and representations through multi-head attention. Therefore, incorporating TGNA into these methods would require method-specific modifications rather than a direct replacement of an independent augmentation module.

We also found that NCLA provides publicly available implementation code, whereas we could not locate official implementations for AS-GCL and NDSCL. We agree that investigating TGNA's compatibility with these methods would be valuable for future work, and will clarify the distinction between the five plug-in evaluations and the three additional standalone baselines in Table 1.

AuthorsOpenReview ↗

Looking forward to re-evaluation

Dear Reviewer gUSW

As the author discussion period is coming to an end, we kindly invite you to review our rebuttal and let us know whether our responses have adequately addressed your concerns. If so, would you consider updating your review? Many thanks.

Best regards, Authors

Reviewer_4Yf9OpenReview ↗
Rating
3(+2)
Confidence
4
Informativeness
2(+1)
Presentation
2
Soundness
2(+1)
Read review
Paper summary

This paper investigates the feature-learning dynamics of graph contrastive learning (GCL) based on the sparse coding framework of Wen&Li (2021), the authors partition the latent feature dictionary into two blocks: task-relevant features with stronger neighborhood correlations and task-irrelevant features with weaker neighborhood correlation. The theoretical analysis shows that gradient-based contrastive learning amplifies M1 while suppressing M2, accelerating convergence and reducing downstream classification error by a factor. Motivated by this scaling law, the authors propose theory-guided neighborhood augmentation method. Experiments on synthetic data and widely adopted benchmarks are provided to support the findings.

Critical strengths
  • Timely theoretical analysis on contrastive learning extended to graph structured data.
  • Generally well written *The proposed TGNA is plug and play applicable to existing GCL baselines.
Critical weaknesses

Major:

  • The paper conflates the effect of linear graph smoothing with contrastive learning dynamics. A central claim of the paper is that GCL training dynamics induce a selective feature-learning mechanism via neighborhood correlation. However, looking closely at the encoder formulation in Eq. (1), the GNN first computes a linear neighborhood average before applying any learnable weights or contrastive loss. From a graph signal processing perspective, linear neighborhood averaging is inherently a low-pass filter (graph smoothing) that amplifies low-frequency, neighborhood-correlated signals, while averaging out uncorrelated high-frequency components and independent noise. As a result, the variance seperation between M1 and M2 is already established prior to contrastive optimization simply by the linaear smoothing step. In effect, any standard variance-sensitive unsupervised objective (even PCA) would preferentially capture M1. The paper overstates the role of GCL .

  • The theoretical framework relies on a flawed binary dichotomy: features are either both task-relevant and strongly neighborhood-correlated( M1) or both task-irrelevant and weakly correlated coupled (M2) with the assumption that downstream labels depend exclusively on M1. This essentially bakes the desired conclusion into the assumptions and ignores two critical, ubiquitous regimes in real-world graphs: (1) Task-relevant features with weak neighborhood correlation (e.g., Heterophilic graphs or center-node-specific signals). In many graphs, discriminative task signals reside in high-frequency feature components or heterophilic connections where αtaskρtask\alpha_{task}\rho_{task} is small. According to Theorem 3.1, GCL neighborhood aggregation actively suppresses these features (treating them as M2 which would lead to severe performance degradation. Case 2 is task-irrelevant features with strong neighborhood correlation ( Spurious homophily): Real-world graphs frequently exhibit strong neighborhood correlation along background/environmental attributes that are orthogonal to the downstream task. But the paper partition the feature space into only two orthogonal parts.

  • There is a fundamental disconnect between unsupervised GCL and "Task-relevance", a theory to algorithm gap. GCL is strictly unsupervised/self-supervised, where downstream tasks and labels are unknown during pre-training. How can the model or augmentation algorithm identify which features are 'task-relevant'? The paper acknowledges this and therefore resort to raw node-feature cosine similarity in their proposed method. However, under the paper's own data model (eq.7) in sectioin 5.1, the raw inner product between node k and j and norm are heavily contaminated and often dominated by the task-irrelevant dictionary M2 and high-dimensional noise (see the setup for parameters d, d′d'. Using raw cosine similarity as proxy for the first feature partition contradicts the latent sparse coding setup.

  • Design of the proposed TGNA is questionable. The algorithm sample a portion of dissimilar neighbors from negative set to construct the views, while the theory dictates that higher neighborhood correlatioin is strictly better. Why not only sample from positive? Furthermore, since K^\hat{K} is roughly constant, this implies that \hat{S}_{TGNA} almost monotonically increases with ρ\rho. Maximizing S^\hat{S} over ρ\rho is equivalent to trivivally picking the largest ρ\rho candidate.

  • Evaluation of TGNA is also questionable. According to Eq. (15) and Table2, TGNA discards 31% to 69% of the nodes in the graph, leaving up to 70% nodes untrained in self-supervised representation learning is a severe limitation. Additionally, the claimed training time reduction in Table 2 is largely a byproduct of training on fewer nodes and negative pairs, and Table 2 explicitly omits the preprocessing overhead of computing all-pair neighborhood similarities and evaluating multiple view trials.

  • Lack of heterophilic benchmarks.

Minor: *Line211: Unresolved Latex reference *LIne 468: Broken/hardcoded equation reference

Questions for authors
  • If we simply pre-compute the smoothed features and feed it into standard non-graph contrastive learning, wouldn't we obtain the exact same scaling provide in the paper? In what sense is this selective mechanism an intrinsic property of GCL rather than a direct consequence of linear low-pass graph filtering?

  • How does the theory behave wehen a subset of task-relevant featurres havs weaker neighborhood correlation than a subset of task-irrelevant background features?

  • Given that raw features contain M2 and dense noise, under what theoretical conditions does thresholding the raw cosine similarity guarantee the isolation of M1-correlated neighbors rather than M2-correlated ones?

  • Regarding the anchoring, since 31%-69% nodes are excluded from VancV_{anc} and neveer receive positive-pair alignment gradients during GCL training (Table 2), how well does the model perfom specifically on the excluded non-anchor nodes vs. the retained anchor nodes? What is the wall-clock time required for TGNA's view construction and selection prior to training?

9 comments
AuthorsOpenReview ↗

Response to Reviewer 4Yf9 Part I

Q1 (Weakness 1) : The paper conflates the effect of linear graph smoothing with contrastive learning dynamics. A central claim of the paper is that GCL training dynamics induce a selective feature-learning mechanism via neighborhood correlation. However, looking closely at the encoder formulation in Eq. (1), the GNN first computes a linear neighborhood average before applying any learnable weights or contrastive loss. From a graph signal processing perspective, linear neighborhood averaging is inherently a low-pass filter (graph smoothing) that amplifies low-frequency, neighborhood-correlated signals, while averaging out uncorrelated high-frequency components and independent noise. As a result, the variance seperation between M1 and M2 is already established prior to contrastive optimization simply by the linaear smoothing step. In effect, any standard variance-sensitive unsupervised objective (even PCA) would preferentially capture M1. The paper overstates the role of GCL .

A1: First, we agree that neighborhood aggregation introduces a low-pass filtering effect that favors neighborhood-correlated features. Indeed, this is precisely the mechanism through which graph structure influences feature learning in our analysis. However, the statistical separation induced by graph smoothing does not, by itself, characterize how individual neural-network features are learned through gradient-based contrastive optimization. Our theoretical contribution is to establish how this filtering effect translates into selective feature-learning dynamics. Specifically, Theorem 3.1 demonstrates that individual neurons preferentially align with latent dictionary atoms in M1M^1, while their components along M2M^2 are suppressed, and quantifies how neighborhood correlation affects the convergence of this learning process. These neuron-level guarantees go beyond the well-known low-pass filtering interpretation of graph aggregation. Our primary comparison is between GCL and conventional CL, rather than between GCL and other graph-based learning methods.

Second, we appreciate the reviewer's connection to PCA and spectral methods. However, recovering a dominant feature subspace does not necessarily guarantee recovery of individual latent dictionary atoms. Specifically, while PCA may recover the subspace spanned by M1M^1 and M2M^2, it does not necessarily identify their individual feature directions. This distinction is crucial because each individual feature direction corresponds to a specific atom of the underlying latent dictionary, whereas an arbitrary basis of the recovered subspace may consist of mixtures of multiple dictionary atoms. Therefore, recovering the subspace alone does not guarantee that individual neurons learn these underlying features. Importantly, learning individual latent features rather than entangled mixtures of multiple features is a key aspect of representation learning examined in our theoretical analysis. This is one of the central conclusions of our work.

We will clarify these distinctions in the revised manuscript to better distinguish the established graph filtering effect from our theoretical contributions to GCL feature learning.

Jingyu Chen, Runlin Lei, and Zhewei Wei. “PolyGCL: Graph Contrastive Learning via Learnable Spectral Polynomial Filters.” Proceedings of the Twelfth International Conference on Learning Representations (ICLR), 2024.

Wenhan Yang and Baharan Mirzasoleiman.“Graph Contrastive Learning under Heterophily via Graph Filters.” Proceedings of the Fortieth Conference on Uncertainty in Artificial Intelligence (UAI), Proceedings of Machine Learning Research, vol. 244, pp. 3936–3955, 2024.

AuthorsOpenReview ↗

Response to Reviewer 4Yf9 Part II

Q2 (Weakness 2): The theoretical framework relies on a flawed binary dichotomy: features are either both task-relevant and strongly neighborhood-correlated$M^1$ or both task-irrelevant and weakly correlated coupled M2M^2 with the assumption that downstream labels depend exclusively on M1M^1. This essentially bakes the desired conclusion into the assumptions and ignores two critical, ubiquitous regimes in real-world graphs: (1) Task-relevant features with weak neighborhood correlation (e.g., Heterophilic graphs or center-node-specific signals). In many graphs, discriminative task signals reside in high-frequency feature components or heterophilic connections where αtaskρtask2 is small. According to Theorem 3.1, GCL neighborhood aggregation actively suppresses these features (treating them as M2M^2 which would lead to severe performance degradation. Case 2 is task-irrelevant features with strong neighborhood correlation ( Spurious homophily): Real-world graphs frequently exhibit strong neighborhood correlation along background/environmental attributes that are orthogonal to the downstream task. But the paper partition the feature space into only two orthogonal parts.

A2: We thank the reviewer for highlighting the distinction between neighborhood correlation and downstream task relevance. We agree that our current terminology is imprecise, as strongly neighborhood-correlated features are not necessarily task-relevant, while weakly correlated features may still contain discriminative information. We will revise the terminology throughout the paper, referring to M1M^1 and M2M^2 as strongly and weakly neighborhood-correlated features, respectively.

Our theoretical framework aims to characterize how neighborhood correlation affects feature learning in GCL, rather than assuming that neighborhood correlation necessarily implies task relevance. Specifically, Theorem 3.1 establishes that GCL preferentially learns features in M1M^1 while suppressing those in M2M^2, independently of their relevance to downstream tasks.

Regarding task-irrelevant features with strong neighborhood correlation (Case 2), we acknowledge that our orginial downstream assumption, ∣uj⋆∣=Θ(1)|u_j^\star|=\Theta(1) for all j∈[d]j\in[d], is unnecessarily restrictive, as it requires every feature in M1M^1 to contribute to downstream prediction. A more general formulation allows u⋆u^\star to have zero coefficients for some task-irrelevant features, while maintaining ∣supp⁡(u⋆)∣=Θ(d)|\operatorname{supp}(u^\star)|=\Theta(d) and ∣uj⋆∣=Θ(1)|u_j^\star|=\Theta(1) for nonzero coefficients. This allows a constant fraction of strongly neighborhood-correlated features in M1M^1 to be irrelevant to the downstream task. Thus, our results apply the Case 2 scenario mentioned by the reviewer. We will revise the assumption and corresponding downstream analysis to reflect this more general setting.

Regarding task-relevant features with weak neighborhood correlation (Case 1), we agree that neighborhood aggregation may suppress such features, potentially degrading downstream performance. This reflects an inherent limitation of neighborhood-aggregation-based GCL, rather than an assumption that weakly correlated features cannot be task-relevant. Indeed, prior studies have reported that GCL methods may struggle on heterophilic graphs, where high-frequency information can be important for downstream tasks (Chen et al., 2024; Yang & Mirzasoleiman, 2024). Our theoretical analysis provides a quantitative characterization of this inductive bias by explicitly showing how feature learning depends on neighborhood correlation.

We will revise the terminology and downstream assumptions to clarify that neighborhood correlation and task relevance are distinct properties, and that our downstream guarantees apply when the task-relevant information is sufficiently represented among the strongly neighborhood-correlated features.

AuthorsOpenReview ↗

Response to Reviewer 4Yf9 Part III

Q3 (Weakness 3): There is a fundamental disconnect between unsupervised GCL and "Task-relevance", a theory to algorithm gap. GCL is strictly unsupervised/self-supervised, where downstream tasks and labels are unknown during pre-training. How can the model or augmentation algorithm identify which features are 'task-relevant'? The paper acknowledges this and therefore resort to raw node-feature cosine similarity in their proposed method. However, under the paper's own data model (eq.7) in sectioin 5.1, the raw inner product between node k and j and norm are heavily contaminated and often dominated by the task-irrelevant dictionary M2 and high-dimensional noise (see the setup for parameters d, . Using raw cosine similarity as proxy for the first feature partition contradicts the latent sparse coding setup.

A3: We thank the reviewer for raising this important question regarding the connection between latent neighborhood correlation and its observable proxy. We agree that downstream task relevance is unknown during unsupervised GCL training. As clarified in A2, our theoretical analysis distinguishes features according to their neighborhood correlation rather than their downstream task relevance. Accordingly, TGNA does not attempt to identify task-relevant features, but uses observable node-feature similarity as a proxy for neighborhood correlation.

The use of raw-feature cosine similarity is motivated by the orthogonal sparse-coding structure in Eq. (7). Since M=[M1∣M2]M=[M^1\mid M^2] has orthonormal columns, the inner product between two node features can be decomposed as $\langle z_k^1,z_j^1\rangle + \langle z_k^2,z_j^2\rangle + \varepsilon_{kj}, $ where εkj\varepsilon_{kj} collects the noise-related terms. We clarify that our neighborhood-correlation assumption requires shared latent features to have identical nonzero coefficients, not merely overlapping supports. Since these coefficients take values in −1,1{-1,1}, their contribution to the latent inner product is positive, yielding ⟨zkr,zjr⟩=∣Skr∩Sjr∣\langle z_k^r,z_j^r\rangle=|S_k^r\cap S_j^r| for correlated node pairs. Consequently, stronger overlap in M1M^1 directly increases its contribution to the observed inner product. When this signal is sufficiently strong relative to the M2M^2 contribution and noise fluctuations, raw-feature cosine similarity provides an informative proxy for latent neighborhood correlation.

We further conducted a synthetic experiment to validate this relationship. Following the setting in Section 5.1, we use d=10,d′=20,d1=200d=10, d'=20, d_1=200, and additive Gaussian noise (\xi\sim\mathcal N(0,0.01I_{d_1})), with (K=15) and (\rho_1=0.7). By varying the latent feature-overlap ratio α1\alpha_1 from 0.1 to 1.0 while fixing α2=0.2\alpha_2=0.2 and ρ2=0.25\rho_2=0.25 , we observe a strong positive relationship between α1\alpha_1 and the average center-neighbor cosine similarity (Figure 1), with Pearson r=0.9814r=0.9814, Spearman rs=0.9970r_s=0.9970, and R2=0.9632R^2=0.9632. This supports the effectiveness of raw-feature similarity as an empirical proxy for latent neighborhood correlation under our synthetic-data setting, despite the presence of M2M^2 features and additive noise. See Figure 1 at this link
https://storage.googleapis.com/iclr2027_figures/ICLR27_Ablations.pdf

We will correct the neighborhood-correlation assumption to explicitly require coefficient agreement on shared features and clarify the conditions under which raw-feature similarity serves as a useful proxy.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Rebuttal Summary and Request for Follow-Up Discussion

Dear Area Chair,

We would like to briefly summarize our rebuttal progress and provide an update on the reviewer discussions for our paper, “Understanding Feature Learning in Graph Contrastive Learning: Neighborhood Correlation and Theory-Guided Augmentation.”

Our paper theoretically characterizes how neighborhood correlation influences feature-learning dynamics in graph contrastive learning (GCL), and proposes Theory-Guided Neighborhood Augmentation (TGNA), a plug-in augmentation strategy motivated by these theoretical findings.

During the rebuttal period, we made substantial efforts to address the reviewers' concerns through additional theoretical clarifications and experiments. In particular:

• Theoretical clarifications: We clarified the distinction between neighborhood correlation and downstream task relevance, explicitly introduced the sign-consistency condition for correlated latent features, and further explained the role of contrastive optimization beyond neighborhood aggregation. We also derived the cross-view noise covariance induced by the shared center node and quantified its scaling relative to the leading feature-correlation terms.

• Validation of the theory-guided criterion: We conducted additional synthetic experiments to examine whether raw-feature cosine similarity serves as a reasonable proxy for latent feature overlap. We further validated the complete TGNA selection criterion against its latent counterpart, obtaining Pearson and Spearman correlations of 0.9776 and 0.9798, respectively.

• Additional ablation studies: We separated the contributions of TGNA's anchor selection and view construction. In particular, we introduced two further controlled baselines: random anchor selection with the same number of anchors as TGNA, and cosine-similarity-based neighborhood sampling. These comparisons provide additional evidence that TGNA's improvements are not merely due to anchor reduction or selecting highly similar neighbors.

• Additional empirical evaluation: We conducted experiments on four heterophilic graph benchmarks (Texas, Wisconsin, Chameleon, and Squirrel) to examine the applicability of TGNA beyond homophilic graphs. We also provided end-to-end runtime comparisons that explicitly account for preprocessing and view generation, clarifying the computational benefits and limitations of TGNA.

The initial reviewer scores were 1, 2, and 3. We would like to highlight the following developments during the discussion:

• Reviewer 4Yf9 (1 → 3) acknowledged that some major concerns had been addressed and increased the score from strong rejection to weak acceptance.

• Reviewer gUSW (3) has not yet responded to our rebuttal.

• Reviewer xBnC (2) provided follow-up feedback about six hours before the end of the discussion period, acknowledging improvements from our rebuttal but requesting further clarification regarding shared-center covariance and matched ablation controls.

In response to Reviewer xBnC's follow-up, we submitted additional theoretical derivations and new controlled experimental results approximately 40 minutes before the discussion deadline. Given the limited time remaining, we are concerned that the reviewer may not have had an opportunity to examine these final additions.

We would greatly appreciate it if you could encourage Reviewer xBnC to review our latest response during the subsequent AC-reviewer discussion, so that these additional clarifications and experimental findings can be considered in the final assessment.

Thank you very much for your time and consideration.

Best regards,

The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.