- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes Graph Actor-Critic (GAC), a reinforcement learning framework that rewires message passing to improve performance on heterophilic graphs. It casts each layer as a step of an MDP, in which a node-level "communication policy" decides whether each node sends, receives, both or neither. The policy acts over the original and k-nearest-neighbor candidate edges and is trained with a label-free reward that favors dissimilar neighbor embeddings.
Critical strengths
S1: I support the use of the heterophilic benchmark of Platonov et al. for node classification in place of older heterophilic datasets.
S2: The layer-wise visualizations on the toy graphs make the learned rewiring easy to inspect.
S3: The anonymized code is provided, which makes the results possible to check.
Critical weaknesses
W1: There are already many architectures designed for heterophily, and recent graph foundation models using standard message passing [1, 2, 3] also perform well on heterophilic datasets. I think the motivation needs to be stronger, as it is not clear what limitation of existing methods this paper addresses.
W2: I don't understand how the MDP formulation matches the actual method. The transitions seem to depend on the soft send/receive probabilities rather than the sampled actions. If so, the sampled actions do not affect the reward, and I don't see how the finite-action existence result applies. Please correct me if I'm missing something.
W3: The reward pushes connected node embeddings apart regardless of their labels. This might help on heterophilic graphs, but could hurt on homophilic ones. Why not learn the communication policy directly from the task loss, as in Co-GNN [4]?
W4: I think some important ablations are missing. In particular, how much of the improvement comes from the learned policy and how much from adding kNN edges? Also, the gain attributed to label-free rewiring is measured against GCN, rather than using the same backbone on the original graph.
W5: The main graph-level experiments use older datasets whose relevance has been questioned [5], and these are not specifically heterophilic benchmarks. I would like to see more evaluation on newer, larger graph-level benchmarks, such as [6, 7, 8].
References
[1] Fully-inductive Node Classification on Arbitrary Graphs, ICLR 2025.
[2] Equivariance Everywhere All at Once: A Recipe for Graph Foundation Models, NeurIPS 2025.
[3] GraphPFN: A Prior-Data Fitted Graph Foundation Model.
[4] Cooperative Graph Neural Networks, ICML 2024.
[5] Position: Graph Learning Will Lose Relevance Due To Poor Benchmarks, ICML 2025.
[6] GraphBench: Next-generation graph learning benchmarking.
[7] GraphLand: Evaluating Graph Machine Learning Models on Diverse Industrial Data, NeurIPS 2025.
[8] OgBench: A Framework for Evaluating Graph Neural Networks on Omics Data.
Questions for authors
Q1: Do the sampled actions or the soft send and receive probabilities determine the next state? If the latter, how does GAC compare with optimizing the same reward by backpropagating through the gates?
Q2: Can you report, per dataset, what fraction of the pruned and created edges connect same-class nodes?
Q3: Several baseline results on the heterophilic benchmarks do not match the original sources and are mostly lower. Can the authors report the baselines with the numbers from their original papers, or retune them with the same budget as GAC, including tuned classic GNNs?
5 comments
W5: The main graph-level experiments use older datasets..
We ran experiments on graphland dataset from pyg framework and report the following. In the original submission, please note that we have performed experiments on H2GB [1] (KDD'25) datasets where GAC achieves SOTA performance on that dataset (in the appendix table 11).
| Dataset | Metric | GAC | mean-gnn |
|---|---|---|---|
| Tolokers-2 | AUC-ROC ↑ | 0.8356 ± 0.0214 | 0.8061 ± 0.0154 |
| Artnet-exp | AUC-ROC ↑ | 0.7963 ± 0.0216 | 0.7800 ± 0.0354 |
| City-reviews | AUC-ROC ↑ | 0.9336 ± 0.0345 | 0.9122 ± 0.0154 |
| Artnet-views (Result 1) | MSE/MAE ↓ | 0.5650 ± 0.0163 | 0.5789 ± 0.0121 |
| City-roads | MSE/MAE ↓ | 0.4121 ± 0.0142 | 0.4398 ± 0.0221 |
| Artnet-views (Result 2) | MSE/MAE ↓ | 0.4826 ± 0.0182 | 0.5261 ± 0.0231 |
| Dataset | Task | Nodes | Edges | Features | Train / Val / Test | Edge Homophily |
|---|---|---|---|---|---|---|
| Tolokers-2 | AUC-ROC | 11,758 | 1,038,000 | 19 | 1,175 / 1,176 / 9,407 | 0.5945 |
| Artnet-exp | AUC-ROC | 50,405 | 560,696 | 75 | 5,040 / 5,041 / 40,324 | 0.8317 |
| City-reviews | AUC-ROC | 148,801 | 2,330,830 | 204 | 69,439 / 34,720 / 34,720 | 0.7392 |
| Artnet-views | MSE/MAE | 50,405 | 560,696 | 50 | 5,040 / 5,041 / 40,324 | — |
| City-roads | MSE/MAE | 57,073 | 214,208 | 68 | 18,053 / 9,027 / 9,027 | — |
We will run more experiments on the remaining datasets and other benchmarks you mentioned and will be available for the camera ready version.
[1] When Heterophily Meets Heterogeneity: Challenges and a New Large-Scale Graph Benchmark, Lin et al, KDD 2025
We again thank you for the review and feedback. We look forward to hearing back from you and answer any additional questions that you may have.
Best
The authors
Thank you for the rebuttal and new ablations.
Regarding W2/Q1, using the policy's continuous probabilities inside Eq. (4) makes state transitions depend on the policy itself rather than only the state and discrete action, so the standard finite-action MDP setup in Theorem 3.3 still does not hold, and the comparison against directly backpropagating the reward through the gates was not run.
Regarding Q2, Q3, and W5, Q2 was left unanswered, published Co-GNN results already match or beat GAC on the Platonov datasets (while GAC drops to 89.8 on Roman-Empire in the W4 ablation), and the added GraphLand tasks in W5 are node-level rather than graph-level benchmarks as mentioned in Q5.
Thus, the rebuttal partially address my concerns and I will keep my score of 2.
We thank the reviewer for reviewing our paper and providing valuable feedback. We have gone over comments carefully and address the key concerns below-
The issue with existing methods is that nearly all methods including heterophily specific architectures and the newer graph foundation models run message passing on a fixed communication graph. At every layer, every node exchanges messages with it’s neighbor regardless of the representation/embedding quality. Hence, we can’t train deeper gnn models as the representation collapses (oversmoothing). Heterophily specific architecture changes how the messages are combined by applying spectral filters or higher neighborhood aggregation but it remains fixed across the layers which again leads to oversmoothing. In both cases, the question of who should communicate with at which layer is fixed. This is the key question GAC addresses. GAC allows nodes to decide which nodes to share messages, how much message to share and at which layer. The work done by [1] is the closest to our approach, however [1] is unable to create new edges and the communication is learned by downstream task signal which provably makes the model to learn shortcut and hence the same phenomena of representation collapse happens. In GAC, we learn the communication policy based on a reward designed to keep diversity while maintaining similarity to some extent which is proved by GAC’s performance on homophilic graphs. We have updated our motivation in the manuscript based on your feedback.
MDP provides the base for our graph actor critic. Each node takes a soft send/receive action and their joint probability determines the transition to the next state. For example, for a given graph we have u-v pair, if node u’s send value is 1 and node v’s receive value is 0, then for the next state they won’t have any connectivity between them (drop edge from u→v). Similarly, if u’s receive value is 1 and v’s send value is 1 then for the next layer keep u←v edge (making it directional). The same idea applies to each node of the graph and we get a modified graph connectivity for the next layer. Each node’s action is determined by the reward to keep diversity in the node's representation. If neighbors' representation gets too similar, our reward penalizes each node’s action so that they don’t receive information from neighboring nodes.
We have performed experiments on homophilic graphs and have shown that GAC performance doesn’t degrade on such graphs. Please check table 9 in the appendix.
Learning communication policy directly encourages the model to learn shortcut and we have to learn the policy for each task. Rather we show that it is possible to learn label free communication policy and apply the learned policy for downstream task such as classification, line prediction.
To isolate the contribution of learned communication policy and topology augmentation with kNN neighbors, we perform ablation study on two datasets which are randomly chosen. We consider four configurations - 1. The backbone architecture (GCN with mean aggregation which is termed as mean gnn in literatures like [1] with the original graph, 2. Keep kNN edges only learned by the policy and drop existing edges from the original graph, 3. Remove kNN edges and keep the original edges learned by the policy, 4. Keep kNN edges and original edges with learned policy. The experiment configuration are kept the same and we used compute budge of 500 epochs.
From this ablation, it is clear that the learned communication policy is the primary contributor to performance improvements. Compared with the baseline (gcn with mean aggregation), actor critic policy-based reweighting improves the test metric from 0.7666 to 0.8775 on roman-empire and from 0.7579 to 0.7741 on questions datasets.
We ran all baselines using their official open-source implementations under the exact same experimental environment setup and compute budget (number of epochs, hyperparameter tuning range, and evaluation splits) to ensure a fair comparison. Under this uniform budget, we consistently reproduced the baseline performance numbers reported in our paper. For instance, methods like [1] also yield lower performance when strictly aligned with this standardized budget as shown in [2].
References:
[1] Cooperative Graph Neural Networks, Finkelshtein et. al, ICML 2024
[2] Cooperative sheaf neural networks. Ribeiro et.al. ICLR 2026