SoLAR: Surrogate Label Aware GNN Rewiring

1. While the paper presents a well-executed study with solid empirical results, there are some limitations worth noting. The overall pipeline shares considerable similarity with existing graph structure learning approaches. As detailed in recent surveys on graph structure learning [1], the idea of iteratively refining graph structure using model predictions has been explored in various forms [2,3], making the core contribution somewhat incremental.

2. The theoretical analysis, while providing useful insights about homophily, could benefit from deeper investigation. Some recent works [4,5] in the field, such as those analyzing linear separability in graph convolution with contextual stochastic block models, offer examples of more comprehensive theoretical analysis and a more general setting.

3. While the authors position graph rewiring as a pre-processing step to address over-smoothing and over-squashing issues in GNNs, there is limited discussion or analysis of how the proposed method actually tackles these fundamental challenges. The paper demonstrates improved performance on standard metrics but doesn't explicitly show how the rewiring process mitigates over-smoothing or alleviates the information bottleneck causing over-squashing.

[1] Zhu, Yanqiao, et al. "A survey on graph structure learning: Progress and opportunities." arXiv preprint arXiv:2103.03036 (2021). [2] Dai, Enyan, et al. "Towards robust graph neural networks for noisy graphs with sparse labels." Proceedings of the Fifteenth ACM International Conference on Web Search and Data Mining. 2022. [3] Stretcu, Otilia, et al. "Graph agreement models for semi-supervised learning." Advances in Neural Information Processing Systems 32 (2019). [4] Baranwal, Aseem, Kimon Fountoulakis, and Aukosh Jagannath. "Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization." arXiv preprint arXiv:2102.06966 (2021). [5] Baranwal, Aseem, Kimon Fountoulakis, and Aukosh Jagannath. "Effects of graph convolutions in multi-layer networks." arXiv preprint arXiv:2204.09297 (2022).

-The intuition that increasing homophily may be only useful for homophilic graph. Maybe move Fig.4 to previous sections to give an intuition of what is happening.

1. The method appears to be primarily effective on homophilic graphs, which limits its applicability in domains with heterophilic or complex graph structures. A discussion on its performance across varying levels of homophily would strengthen the understanding of its generalizability.

2. The approach is computationally intensive, as it requires an additional surrogate GNN model, significantly increasing computational costs. The scalability of the proposed method is not thoroughly explored, particularly for large-scale graphs where such an approach might be impractical.

3. The novelty of the proposed method appears limited, as the idea of enhancing homophily by adding same-prediction edges or removing different-label edges has been explored in several previous works.

I have concerns about the novelty and soundness of the methods being proposed here.

The basic process of SoLAR is to do two-passes, the first-pass predicted labels are then used to add intra-class edges and/or delete inter-class edges to improve homophily. Then the second model learns from the rewired graph.

1. From another angel, the operation is a way to denoising: predict/impute (the first-pass predicted labels are only used on test/val because these labels are missing, and the authors use the ground truth label on the training set, ln176-177) the labels on the unknown nodes, then globally remove/add edges to improve homophily.

2. The analysis in the paper is circular as a lot of effects are expected if edges are added/removed to improve homophily. For example, the authors showed a variance reduction effect; intuitively, the process here will make the model more confident of its prediction by rewiring the graph systematically in a way in concordance with the labels predicted.

Theoretical:

1. Graph rewiring and graph structure learning are well-established areas of research, and more related work should be referenced. For example, the proposed technique resembles [1], where the graph is rewired after each convolution layer based on the features and trained end-to-end.
2. The rewiring technique is not explicitly described. It’s important to include details on how edges are added or removed, along with the relevant hyperparameters and their tuning process, in the main text.
3. In Table 9, the authors note that only the largest connected components are used for each dataset. Clarification is needed on why portions of the dataset were discarded, as this could greatly affect performance outcomes. This fact should also be highlighted in the main text.

Experimental:

4. The results are not reproducible with the provided code. After fixing minor errors, I attempted to replicate the results using the code in the appendix, but I could not achieve the reported outcomes. For instance, using GATv2+GATv2+Delete (n_layers=2 each, hidden_dim=32, lr=0.001, max_iters_delete=1700), I obtained a final test accuracy of $44.41 ± 2.32$, compared to $90.06 ± 3.31$ reported in Table 1. While I do not suspect unethical practices, the code quality requires improvement for reliable reproduction.
5. You state that predictions are used “only on the test and validation sets.” However, in the code (methods.py line 393) it appears that the true validation labels are also used during the rewiring process.

Minor:

The overall presentation of the paper could be improved. For instance, the parameters $(d, k)$ in Figure 2 are not defined. On page 5, "SoLAR pruning" is introduced and reused without explanation.

References:

[1] Wang, Yue, et al. "Dynamic graph cnn for learning on point clouds." ACM Transactions on Graphics (tog) 38.5 (2019): 1-12.