Propagation Alone is Enough for Graph Contrastive Learning

Q3. Theorem 4.1 shows propagation minimizes the alignment loss, this actually corresponds to a mode collapse scenario where all node representations become identical - a situation that contrastive learning typically aims to avoid.

A3. When the propagation step $K$ approaches infinity, node representations indeed collapse to identical values, a phenomenon known as over-smoothing. However, in practice, we limit $K$ to a finite range, typically fewer than five. This ensures that representation collapse does not occur, as supported by our experimental results.

---

Q4. In Section 4.1, the notation ( $x^{+}$ ) appears in the alignment loss equation. Could you clarify what ( $x^{+}$ ) specifically represents in this context? Explicitly defining this and other notations throughout would enhance clarity and help readers follow your ideas more smoothly.

A4. The notation $(x, x^{+})$ represents positive pairs. To enhance clarity and maintain consistency with the definition of $A_{ij}$, we have updated the notation in the revised version to $(x_i, x_j)$. The revised alignment loss equation is: $L_{align}(f)=-E_{x_i, x_j \sim p(x_i, x_j)}[f(x_i)^\top f(x_j)],$ where $p(x_i, x_j)=A_{ij}/\sum_{i,j}A_{ij}$ denotes the normalized edge weight between nodes $v_i$ and node $v_j$.

---

Q5. Suggestion: The paper currently presumes familiarity with the standard Graph Contrastive Learning (GCL) pipeline. Including a brief overview of the GCL pipeline in the main text would benefit readers who may not have a deep background in GCL.

A5. Thank you for the suggestion. We have added a brief overview of GCL pipeline in the background section in the revised version.

---

Q6. Suggestion: The computational efficiency appears to be a major advantage of PROP/PROPGCL, but this important result is placed in the appendix instead of main context.

A6. Thank you for this valuable suggestion. In the revised paper, we have moved the efficiency analysis to Section 6.3 of the main body, while the original ablation study on filter choices has been relocated to the appendix.

---

Thanks for your comments and hope our answers could address your concerns. Please let us know if you have additional questions.

We thank Reviewer xD6G for their kind recognition of our contributions and for raising insightful points, which we address below.

---

Q1. In Section 4.1, where the authors present propagation as a non-parametric learning approach, the theoretical foundation could be more rigorous. The claim that propagation corresponds to gradient descent on Dirichlet energy lacks rigorous mathematical proof, and the cited papers (Zhu et al., 2021a) don't very clearly support this interpretation. The connection between propagation and non-parametric unsupervised learning remains more of an intuitive argument than a mathematically grounded one.

A1. We establish a formal connection between the Dirichlet energy objective and the propagation procedure in the following theorem. For reference, we reproduce Equation 1 and Equation 2 from the paper:

$ & H^{(K+1)} =\hat{A}H^{(K)} \quad (1) \\\\ & \mathcal{L}(H)=H^\top \hat{L}H = \sum_{ij} \hat{A}_{ij} \Vert H_i- H_j \Vert ^2 \quad (2). $

Theorem. For a learning step size of $\alpha=0.5$, the propagation procedure (Equation 1) optimizes the Dirichlet energy objective (Equation 2) and converges to a state where the energy $\mathcal{L}(H^{(K)}) \to 0$ as $K \to +\infty$ for non-bipartite graphs.

Proof. The gradient update of the Dirichlet energy objective (Equation 2) gives the following update rule of node features $H$,

$$H-\alpha\frac{\partial \mathcal{L}(H)}{\partial H} = H-2\alpha\hat{L}H = ((1-2\alpha)I + 2\alpha\hat{A})H,$$

where the $\alpha$ is the step size. By choosing the learning rate $\alpha=0.5$, the update rule simplifies to $H_{new}=\hat{A}H$, which recovers the propagation operation in Equation 1. To analyze convergence, we consider the Dirichlet energy objective after $K$ propagation steps:

$$\mathcal{L}(H^{(K)}) = (\hat{A}^KH^{(0)})^\top\hat{L}(\hat{A}^KH^{(0)}) =H^{{(0)}^\top}\hat{A}^K\hat{L}\hat{A}^KH^{(0)} =H^{{(0)}^\top}(\hat{A}^{2K}-\hat{A}^{2K+1})H^{(0)}.$$

The eigenvalues of $\hat{L}$ lie in the range $[0,2]$, which implies the eigenvalues of $\hat{A}$ lie in $[-1,1]$. The eigenvalue of $\hat{L}$ equals 2 if and only if the graph is bipartite. For non-bipartite graphs—common for complex real-world graphs—the eigenvalues of $\hat{A}$ lie in $(-1,1]$. As $K \to +\infty$ , the contribution of higher powers of $\hat{A}$ diminishes, and we have $\lim_{K \to +\infty}\mathcal{L}(H^{(K)})=0$, which ends the proof.

---

Q2. The claim "the propagation operator can also be understood as a special GCL method, where the positive samples are randomly drawn from neighboring nodes" lacks rigorous proof. The authors directly make this connection without formal mathematical justification, and do not explain how propagation's deterministic neighbor aggregation truly corresponds to random sampling of positive pairs in contrastive learning.

A2.

Using neighboring nodes can be understood as a form of view generation in GCL. Formally, this involves designing a permutation matrix $P$ that transforms the graph such that $A'=P^\top AP$ and $X'=PX$. The same row of $X$ (or $A$) and $X'$ (or $A'$) corresponds to neighboring nodes in the original graph. This kind of view generation is also applied in the previous work and shows satisfying experimental performance [1,2].

Consider a simple example of a triangle graph with three nodes $v_1$, $v_2$, and $v_3$, connected as $(v_1,v_2)$, $(v_1,v_3)$ $(v_2,v_3)$. A specific permutation $P=\begin{pmatrix}0 & 1&0\\\\0&0&1\\\\1&0&0\end{pmatrix}$ transforms the original graph's adjacency matrix $A=\begin{pmatrix}0&1&1\\\\1&0&1\\\\1&1&0\end{pmatrix}$, $X=\begin{pmatrix}x_1\\\\ x_2\\\\x_3\end{pmatrix}$ into $A'=P^\top A P=\begin{pmatrix}0&1&1\\\\1&0&1\\\\1&1&0\end{pmatrix}$, $X'=PX=\begin{pmatrix}x_2\\\\ x_3\\\\x_1\end{pmatrix}$. The corresponding nodes in $G=(A,X)$ and $G'=(A', X')$ form positive pairs.

Based on random sampling, other choices of $P$ are possible, such as transforming $X$ to $X'=(x_3, x_1, x_2)^\top$. For node $v_1$, the probabilities of transferring to $v_2$ and $v_3$ are equal. When the sampling process is repeated sufficiently, the positive samples $(v_1,v_2)$ and $(v_1,v_3)$ are sampled with approximately equal frequency, corresponding to the neighboring set in propagation.

More formally, consider the alignment loss defined in the paper:

$L_{align}(f)=-E_{{x_{i}, x_{j} \sim p(x_i, x_j)}} [f(x_i)^\top f(x_j)].$ (The expectation $\mathbb{E}$ is written as $E$ for rendering problems of OpenReview.)

Here, the probability distribution $p(x_i, x_j)=A_{ij}/\sum_{i,j}A_{ij}$ is defined as the normalized edge weight between nodes $v_i$ and $v_j$. When the sampling process is efficient, we can approximate the neighbor sets in propagation as positive pairs.

[1]. Augmentation-Free Self-Supervised Learning on Graphs. Lee et al., AAAI 2022.
[2]. Neighbor Contrastive Learning on Learnable Graph Augmentation. Shen et al., AAAI 2023.

Dear Reviewer xD6G,

Thanks for your constructive and valuable comments on our paper. We have tried our best to address your concerns and revised our paper accordingly. Could you please to have a check if there are any unclear points? We are certainly happy to answer your any further questions.

Thank you for your insightful comments. It is precisely our key contribution to discover (with rigorous evidence) that the GCL paradigm itself appears less meaningful. As shown in the paper, one of our main contributions is illustrating the inferiority of many existing GCL methods compared to the propagation-only PROP. To the best of our knowledge, this has not been revealed in the literature before. Regarding the evaluation protocol, linear-probing remains the most popular (and dominant) evaluation tool in GCL, and we conduct fair comparisons under this common setting. As you suggest, more alternatives should be adopted in GCL evaluation based on our work, and we plan to explore this in future work on advanced evaluation protocols for GCL.

For the suggestion that focus on arguing how the GCL paradigm fails to improve performance compared to supervised GNNs. We accordingly revise our paper (Introduction, Section 5) by underscoring the findings that GCL learns smooth, nearly Gaussian transformation weights compared to supervised learning, causing a degenerative performance.

We thank Reviewer FGWU for the thoughtful feedback and valuable comments on our work.

---

Q1. 1). The authors claim the PROP is a special GCL because it has an alignment operation between the node and its neighbors. However, the GCL is aligned node with itself on another view, this is different. 2). Moreover, the commonly used infoNCE also includes the comparison part of negative samples. Therefore, I can't entirely agree that PROP is a special GCL.

A1. View generation is a broad research topic in GCL and is not limited to operations like randomly dropping edges or masking features. Neighboring nodes can also be considered a type of generated view by applying a specific permutation matrix $P$ to the graph, i.e., $A'=P^\top AP$, $X'=PX$. This type of neighboring-node view generation has been used in previous works and has demonstrated strong experimental performance [1, 2].

In contrastive learning, negative samples are not always necessary. For example, methods such as BGRL [3] and CCA-SSG [4] exclude negative samples for efficiency. In InfoNCE, negative samples are typically introduced to prevent representation collapse when aligning positive pairs. However, in PROP, the alignment occurs over a finite number of propagation steps (usually fewer than 5 in practice), which inherently avoids collapse. Therefore, there is no need to include negative samples in this case.

[1]. Augmentation-Free Self-Supervised Learning on Graphs. Lee et al., AAAI 2022.
[2]. Neighbor Contrastive Learning on Learnable Graph Augmentation. Shen et al., AAAI 2023.
[3]. Large-scale Representation Learning on Graphs via Bootstrapping. Thakoor et al., ICLR 2022.
[4]. From Canonical Correlation Analysis to Self-Supervised Graph Neural Networks. Zhang et al., NeurIPS 2021.

---

Q2. The PROP without a transformation matrix means that can not transform the node feature from the feature space to the class space. How to make PROP to make the prediction?

A2. GCL methods typically involve two stages: pretraining and evaluation. During the pretraining stage, node representations are learned using self-supervised signals without access to downstream labels. In the evaluation stage, a linear classifier is trained in a supervised manner to make predictions for downstream tasks. The projection from the representation space to the class space occurs during the evaluation stage and follows the same procedure across different GCL methods to ensure fair comparison.

For PROP, node features are propagated during pretraining to generate node representations. In the evaluation stage, these representations are then input into a linear classifier, which is trained to make predictions.

In the revised version of the paper, we have added a detailed description of the GCL pipeline to the background section for greater clarity.

---

Q3. The PROP form has been proposed in many previous works, such as SGC, PMLP[1], etc. What is the difference between PROP and SGC?

[1] Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs

A3. SGC was primarily introduced and discussed in the context of supervised learning. In the GCL framework, SGC is often used as an encoder with the formulation $H_{\rm SGC}=\hat{A}^KXW$, where $W$ represents trainable weights. In contrast, PROP removes the trainable weights entirely, resulting in the formulation $H_{\rm PROP}=\hat{A}^KX$.

This distinction is crucial because our findings (Section 5.1) reveal that the weights $W$ learned during GCL pretraining tend to be overly smoothing and less informative, which can harm downstream performance (Section 4.2).

We emphasize that our contribution is not focused on introducing PROP as a new formulation, but rather on investigating the role of different components in existing GCL methods. Through comprehensive experiments, we demonstrate the strong competitiveness of the propagation-only baseline for node classification tasks. Despite its simplicity, the baseline has been largely overlooked in the GCL literature, and our work aims to shed light on its effectiveness.

---

Q4. The details of the proposed method should be provided, such as PROP-GRACE.

A4. We have revised the overview of PROPGCL in Section 6.1 and provided detailed explanations of PROP-GRACE in the baselines section of Section 6.2.

---

We hope our responses address your concerns, and we are happy to provide further clarification if needed.

Dear Reviewer FGWU,

Thanks for your constructive and detailed comments on our paper. We have tried our best to address your concerns and revised our paper accordingly. Could you please have a check if there are any unclear points? We are certainly happy to answer your any further questions.

Q3. Is A including self-loops? If not, $A^K$ or $\hat{A}$ might not include all K-hops neighboring nodes as described in the text.

A3. Yes, $A$ includes self-loops in practice. Specifically, we use the normalization approach from GCN, where $A'=A+I$, $\hat{A}=D'^{-\frac{1}{2}}A'D'^{-\frac{1}{2}}$. For further details, please refer to the implementation in prop.py. We have revised the paper to provide a more precise description.

---

Q4. Is it possible to extend the PROP-DGI to multiple graph settings, such as the datasets in [1]? Any specific reasons that PROP-DGI is only evaluated in transductive setting?

[1] Benchmarking Graph Neural Networks. Dwivedi et. al. 2022

A4. PROP-DGI builds on PROP by introducing learnable propagation through spectral filters. However, the spectral characteristics of graphs can vary significantly, making it challenging for a filter learned on one graph to generalize effectively to another. This limitation also explains why spectral GNNs like BernNet, GPRGNN, and ChebNetII are primarily applied to single-graph tasks. We made preliminary attempts to apply PROP-DGI in inductive settings with multiple-graph datasets, but the results were not satisfactory. We have discussed this limitation in the revised paper’s Limitation Section, acknowledging the need for further exploration to adapt PROP-DGI to such settings.

---

Hope our answers could address your concerns. Please let us know if you have additional questions.

We thank Reviewer H333 for their careful reading and for appreciating the thorough analysis and impactful findings of our work. Below, we summarize and address your main concerns.

---

Q1. The proposed method is only verified on node-level tasks with strong feature-connection relationships (i.e., strong homophily and heterophily). No study on the more complicated scenario, for example:

• complex relationship between node features and edges, e.g., partial multidimensional homophily (Block & Grund, 2014)
• graph structures introduce extra information instead of hinting homophily/heterophily, e.g., superpixel datasets (CIFAR10, MNIST) in Dwivedi et al. (2022).

Without this, the work can only show that previous GCL methods cannot adequately learn feature transformation. However, it cannot demonstrate that learning feature transformation is unnecessary or harmful if we can manage to learn adequately. A further study on it might lead to a stronger statement on the proposed method.

A1. For datasets with multidimensional homophily, we could not locate the dataset mentioned in Block & Grund (2014). If you know where to access this dataset, we would be happy to conduct additional experiments and include the results in our study.

For superpixel datasets (CIFAR10, MNIST) from Dwivedi et al. (2022), we note that these are graph classification benchmarks with less informative node features (e.g., CIFAR10 has 3-dimensional node features, and MNIST has 5-dimensional node features). We evaluate PROP on similar graph classification tasks (Appendix A), where graph structures introduce extra information instead of hinting homophily/heterophily. Across datasets, the mean performance gap between PROP and the best-performing methods is 2.82%. Considering PROP’s training-free advantage, we believe these results are still noteworthy. We hypothesize that the less competitive performance is due to the limited or even null node features typically found in common graph classification benchmarks, which hinder PROP's effectiveness. In the revised paper, we have narrowed the scope of our study to GCL for node classification tasks and will explore graph classification scenarios in future work.

Our work highlights a critical issue in existing GCL methods: the inadequate learning of transformation weights, which has been largely overlooked in the literature. We address this problem with a simple yet effective solution—removing the transformation stage entirely—demonstrating surprising effectiveness. While we acknowledge that carefully designed methods or advanced contrastive principles may eventually overcome these limitations, our study makes a meaningful contribution by exposing this overlooked problem and opening new avenues for developing more effective GCL methods. To ensure clarity and avoid overstatement, we have carefully revised the paper to refine our claims and contributions.

---

Q2. There is no evaluation of the inductive setting, including the single-graph datasets (e.g., datasets in Hamilton et al. (2017)) and multiple-graph datasets (i.e., a dataset containing multiple graphs, such as those in Dwivedi et al. (2022)).

A2. We conducted experiments in the inductive setting on the single-graph dataset Reddit and the multiple-graph dataset PPI. The experimental settings, including data splitting and training hyperparameters, follow those in Hamilton et al. (2017). The results are summarized in the table below:

• For PPI (a multi-graph benchmark with 50-dimensional node features), PROP (K=2) achieves an F1 score of 0.7527, which is comparable to GRACE's score of 0.7548.
• For Reddit, PROP (K=2) achieves an F1 score of 0.8452, outperforming GRACE which achieves 0.8185.

These results validate the effectiveness of PROP in node classification tasks under the inductive setting.

F1 score comparison on PPI

F1 score comparison on Reddit

---

We thank Reviewer 3pXN for careful reading and constructive comments. We summarize and address your main concerns in the following.

---

Q1. While the experiments are well done, the main claim is not fully supported / backed up. For e.g., in the graph level tasks (Appendix A), the proposed paradigm of only "PROP" is inferior to other GCL focused methods from literature and performance is not comparable. So why is it effective only for node level tasks?

A1. As shown in Appendix Table 9, for graph classification tasks, the mean performance gap between PROP and the best methods across datasets is 2.82% (as comparison, with the best gap among methods being 1.52%). Considering PROP’s training-free advantage, we believe these results are still noteworthy. However, PROP does not surpass classical graph SSL baselines in graph classification tasks. We hypothesize that this limitation arises because common graph classification benchmarks often have less informative or even null node features, which likely hinder PROP's effectiveness.

Our theoretical analysis of PROP’s effectiveness is primarily based on the connections between nodes within a single graph (Section 4.1), which aligns closely with node classification tasks. In the revised version, we have explicitly narrowed the scope of our study to GCL for node classification tasks and clarified that further research will explore the application of PROP to graph classification tasks.

---

Q2. The heterophilic graph datasets chosen in the paper are known to be problematic, choosing recent heterophilic datasets (for e.g., from [1] will provide a more robust argument. IMO the chosen datasets for node level tasks are quite small and limited to meaningfully test GCL in a realistic setting.

Investigating the proposed paradigm of "PROP" and "PROPGCL" on large scale graphs from OGB (Open graph benchmark) will provide a more convincing argument.

[1]. A critical look at the evaluation of GNNs under heterophily: Are we really making progress. Platonov et,al. 2023.

A2. We acknowledge the reviewer's concern and appreciate the suggestion. We have already shown results of PROP and PROPGCL on the benchmark proposed by [1] in Appendix Table 19. As is observed, PROP-DGI achieves the best results in 2 out of 5 benchmarks and attains an average performance of 70.22%, second only to PolyGCL’s 71.68%. Notably, PolyGCL is specifically optimized for heterophily graphs, whereas PROP-DGI builds on a simpler DGI framework.

Currently the datasets in the main paper are still the widely used with recent citations. That's why we report them in the main paper and put others in appendix for comprehensive study. We understand that locating these results in the appendix may be less direct for readers. In the revised version, we moved these benchmark results to the main body for clarity and emphasis.

Additionally, we have evaluated PROPGCL on the ogbn-arxiv dataset, with results presented in Table 4. To strengthen our analysis, we further conduct experiments on the ogbn-products dataset, which includes 2,449,029 nodes and 61,859,140 edges. The results are as follows:

Due to time constraints, we did not perform hyperparameter tuning for PROP-GGD. Despite this, PROP-GGD achieves competitive performance, with a test accuracy of 73.57% compared to the baseline GGD's 75.49%. Moreover, by removing the transformation stage, PROP-GGD provides significant advantages in computational efficiency and memory consumption. We will refine these experiments further and present the complete results and analysis in the revised version of our paper.

---

Q7. Why is PROPGCL not evaluated for graph level tasks.?

A7. PROPGCL enhances PROP by replacing uniform propagation with learnable propagation through spectral filters. However, the spectral characteristics of graphs can vary significantly, meaning that a filter learned on one graph may not generalize well to another. This limitation is also why spectral GNNs, such as BernNet, GPRGNN, and ChebNetII, are predominantly applied to node-level tasks.

To align with these characteristics and to ensure the applicability of our method, we revised the paper to focus on node classification tasks, where PROPGCL demonstrates strong performance.

---

Q8. How is PROP setup for graph level tasks?. Are resulting node feature after feature aggregation pooled into a single feature for downstream classification?

A8.

Yes, we use mean pooling of node features to obtain the global graph representation. Specifically, this is implemented as:

x = scatter(x, data.batch, dim=0, reduce="mean")

For further details, please refer to the prop.py implementation.

In the revised paper, we have added a detailed explanation of the PROP setup for graph-level tasks to ensure clarity.

---

Thanks for your comments and hope our answers could address your concerns. Please let us know if you have additional questions.

Dear Reviewer 3pXN,

Thanks for your constructive and valuable comments on our paper. We have tried our best to address your concerns and revised our paper accordingly. Could you please to have a check if there are any unclear points? We are certainly happy to answer your any further questions.

We thank Reviewer qb5w for carefully reading and appreciating the novelty and significance of our work on the designs in GCL. Below, we summarize and address your main concerns.

---

Q1. The title and narrative in this paper have been talking about GCL in general. However, this paper is more about GCL for node classification tasks only. Will these conclusions in the paper hold true for other tasks, especially graph classification tasks? It would be better if the authors could conduct further investigations. If not, it might be better if the authors could narrow their scope to GCL for node classification tasks.

A1. We present evaluation results on graph classification tasks in Appendix Table 9. Across datasets, the mean performance gap between PROP and the best-performing methods is 2.82% (as comparison, the best gap among methods being 1.52%). Considering PROP’s training-free advantage, we believe these results are still noteworthy. PROP's performance on graph classification tasks is relatively less competitive compared to its strong results on node classification tasks. We hypothesize that this is due to the limited or even null node features typically found in common graph classification benchmarks, which hinder PROP's effectiveness.

The methods and theories proposed in our paper primarily focus on connections between nodes within a single graph, which aligns with node classification tasks. While PROP demonstrates some promise in graph classification, its potential in this area warrants further investigation. Follow your suggestion, we have narrowed the scope of our study to GCL for node classification tasks and included a clear statement that graph classification will be explored in future work.

---

Q2. It would be more convincing if the authors could conduct experiments on larger datasets in addition to the adopted ogbn-arxiv dataset.

A2. We conducted additional experiments on the ogbn-products dataset, which consists of 2,449,029 nodes and 61,859,140 edges. The results are summarized below:

Due to time constraints, we did not perform hyperparameter tuning for PROP-GGD. Despite this, it achieves a satisfying performance with a test accuracy of 73.57%, compared to the baseline GGD's 75.49%. Additionally, by eliminating the transformation stage, PROP-GGD offers significant advantages in terms of computational efficiency and memory consumption. We will further refine this experiment and include detailed results and analysis in the revised version of our paper.

---

Thanks for your comments and hope our answers could address your concerns. Please let us know if there is more to clarify. We are happy to address them during the discussion stage.

Dear Reviewer qb5w,

Thanks for your constructive and encouraging comments on our paper. We have tried our best to address your concerns and revised our paper accordingly. Could you please have a check if there are any unclear points? We are certainly happy to answer any further questions.