GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation

Summary

This paper addresses the issue of degree bias in node classification, which refers to the poorer performance of Graph Neural Network (GNN) models on nodes with lower degrees compared to the average level. While previous works have attempted to mitigate this bias, they often trade off the performance on higher-degree nodes for improvements on low-degree nodes. In light of this, the authors propose GraphPatcher, a method that introduces virtual nodes during the test phase to tackle this problem. To make the approach computationally feasible, the authors limit the search space to 1-order neighbors and devise an iterative procedure to repair a series of corrupted ego graphs by adding one virtual node at each step. Additionally, the authors provide theoretical results that establish the relationship between the number of sampled ego graphs and the accuracy of the estimated patching loss. The proposed GraphPatcher is extensively evaluated through experiments, demonstrating its effectiveness in addressing the degree bias issue.

Strengths

1. The paper is well-written, allowing readers to easily grasp the core ideas and delve into the authors' detailed explanations. 2. The motivation behind the proposed GraphPatcher is well-founded, as it intuitively aims to enhance overall performance rather than compromising it through trade-offs. 4. The empirical evaluations consistently demonstrate the effectiveness of GraphPatcher, with statistically significant improvements observed. Furthermore, the increasing number of patched virtual nodes correlates with increasingly noticeable enhancements, providing strong support for the rationale behind the iterative procedure designed for GraphPatcher.

Weaknesses

1. While the theoretical analysis provided in the paper is logically sound, its relevance to the community's primary concern of reducing the generalization risk of the original GNN model is unclear. Consequently, the presented theoretical results may not be perceived as a significant contribution. 2. Although the experiments in the paper are well-designed, there is room for improvement in terms of comprehensiveness. For instance, the inclusion of more visually informative figures/tables showcasing the improvements across different degree levels would enhance the clarity of the results. Additionally, comparisons on heterophilic graphs would provide a more comprehensive evaluation. It is also important to consider evaluating the efficiency of GraphPatcher since it introduces additional computational overhead.

Questions

When working with graph samplers that are necessary for training on large graphs, whether we need a larger/smaller L?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

None

Summary

This paper addresses degree bias in node classification. The authors show that current methods suffer performance degradation for high-degree nodes. Thus, they freeze the original GNN and train GraphPatcher to enhance low-degree nodes with node patching in the testing stage. In the experiments, they demonstrate that their approach significantly improves performance without performance drop in high-degree nodes on various homophilous graphs.

Strengths

- They exhibit that the existing approaches suffer performance drops in high-degree nodes. - Their method improves performance without performance degradation in high-degree nodes.

Weaknesses

- [W1] From my understanding, it seems difficult to train in a node-parallel manner with a single large graph, as the graphs used by each node differ, unlike vanilla GNN training. Then, I’m concerned that training GraphPatcher might take an excessively long time. - [W2] The validation is only conducted on homophilous graphs. - [W3] I found that there is a performance drop for high-degree nodes on CiteSeer in Table 1. Is there any reason for this phenomenon?

Questions

- Following [W1], could you provide the comparison with baselines from the perspective of the training time (including vanilla GNN)? Also, it would be better to show memory usage in GPU when training GraphPatcher and baselines. - Following [W2], could you provide a performance comparison on heterophilous graphs?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

As the authors mentioned, the additional computational cost might be considerable.

Summary

This paper introduces GraphPatcher, a novel test-time augmentation framework designed to mitigate degree bias in graph neural networks (GNNs). Degree bias causes GNNs to perform well with high-degree nodes (rich neighbor information) and poorly with low-degree nodes. Current strategies tend to focus on low-degree nodes during training, which can compromise performance on high-degree nodes. To overcome this, GraphPatcher creates virtual nodes to progressively 'patch' low-degree nodes, enhancing performance without sacrificing the capabilities of GNNs on high-degree nodes. The framework is model-agnostic, applicable to self-supervised or supervised GNNs, and shows significant improvement in overall and low-degree node performance across multiple benchmark datasets.

Strengths

- I like the reasoning of the paper, which makes the proposed method well motivated and natural. - The proposed method is more "adaptive" to both low-degree and high-degree nodes, without special treatments that is only for low degree node. The iterative patching sounds like denoising diffusion models, which is interesting. - There are enough details for reproducibility and the code is attached to the supplementary.

Weaknesses

**Concern About Weak Model Performances**: Though the experiment results show the GraphPatcher sometimes is more accurate than the baselines, it is less convincing because the baselines does not look strong enough. For example, for citation networks like Cora, Citeseer and Pubmed, the SOTA accuracy are much better than the best performance shown in Table 1. I recommend the authors to check https://paperswithcode.com/area/graphs for SOTA performances. It is very important because there are non-negligible accuracy gaps. For example, for Citeseer, there are a lot of models achieved more than 80% accuracy, but in Table 1, the best model achieved only around 71% accuracy. Same for Cora (90% vs 84%), Pubmed (91% vs 81%). I feel it would be better that the authors can evaluate the GraphPatcher on some SOTA models and evaluate the effect (improvement) of the proposed graph patching methods, rather than demonstrating improvements over some well-established models that is proposed years ago. It is crucial to understand the real-world value of the proposed methods in this fast-moving community.

Questions

**Some Connections to Iterative Graph Generation And Diffusion Models**: The proposed GraphPatcher is conceptually to iterative graph generation framework, only the training objective is different. The way KL-divergence is used is also similar to a lot of graph generation methods. It is recommended to consider the connection to the graph generation works to see what can be adopted. I feel an autoregressive model like autoregressive transformer or LSTM can be a good candidate for generating the sequence of patched node. The main idea is that it could be possible to know when to stop (predict stop token). The recent works on graph generation using diffusion models could also be a very relevant. These are just some random thoughts, I will appreciate the thoughts from the authors on how this could relate to this work, and maybe adding some future directions into the discussion section if it is indeed relevant.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

No limitations are left unaddressed.

Summary

The paper proposes GRAPHPATCHER, a test-time augmentation framework for graphs, to mitigate the degree biases in Graph Neural Networks. GRAPHPATCHER adopts a corruption function with increasing strength to simulate low-degree ego-graphs from a high-degree one. From the most corrupted graph, it then iteratively generates virtual nodes to the anchor node, such that the frozen GNN model behaves similarly given the currently patched graph or the corrupted graph next in the hierarchy. The authors then examine the effectiveness on seven real-world benchmark datasets, and observe that GRAPHPATCHER enhances the low-degree performance up to 6.5%, when enhancing the overall performance by up to 3.6% at the same time.

Strengths

1. The proposed GRAPHPATCHER avoids creating an artificial out-of-distribution scenario when focusing only on low-degree nodes, and hence avoids significantly sacrificing the performance on high-degree nodes. 2. The modelling and optimization are conducted through aligning the ego-graph sequence and its reconstruction. The test-time augmentation framework avoids changing model architectures and the expensive re-training cost. The structure is simple with good performance.

Weaknesses

1. The way GRAPHPATCHER patches the corrupted ego-graph (adding one node and the corresponding edge at a time) might limit the expressive ability of the model, as it could be difficult for this strategy to reflect more complex structures between the anchor node's neighbors. 2. The continuous corruption and patching on ego-graph share some similarities to the diffusion model. It would be more insightful if the theory behind the methodology and the similarity/dissimilarity with the diffusion model are discussed. 3. In the experimental part, Tail-GNN performs worse than GCN in almost all cases. Even for the low-degree nodes, Tail-GNN cannot always beat GCN, which is unexpected since Tail-GNN is specially designed for low-degree nodes. If there is a problem with the baseline tuning, some conclusions cannot be well supported (e.g., Tail-GNN falls short on the high-degree nodes). This also affects the convincingness of the superiority of GRAPHPATHCER over baselines. 4. It is claimed that the chosen datasets cover graphs with distinctive characteristics, but all datasets used are homophilic ones. It is expected to have more experiments on heterophilic datasets. Since heterophilic graphs often have more complex topologies, they are more susceptible to node adding and dropping. Other minor issues: Typo in row 8: "orizinally".

Questions

Please refer to the weaknesses part.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The paper has properly addressed the limitations of the proposed method. One limitation is the additional computational cost entailed by generating ego-graphs. The authors provide solutions to mitigate the problem.

Response after rebuttal

Thank you for the rebuttal. It has addressed my concerns. I have raised my rating.