Summary
This paper aims to address the question of "why does message passing remain effective on heterophilous graphs" and proposes a unified framework called heterophilous message-passing (HTMP) mechanism. It extensively reviews the architecture of existing heterophilous GNNs under this framework. It then moves on to discuss the empirical observation that the success of message passing in existing heterophilous GNNs is attributed to their implicitly enhancement of the compatibility matrix among classes, and proposed a new GNN approach called CMGNN to further enhance the separability of the compatibility matrix for different classes in the message passing process. The paper includes an extensive empirical analysis involving 10 benchmark datasets and 13 well-established baseline GNNs, and show that the proposed CMGNN approach has the best overall performance against the baselines.
Strengths
- The writing is clear and well-organized for most parts of the paper;
- The paper gives an extensive survey of existing message-passing GNNs under the HTMP mechanism in Table 1 and Appendix A.
- The experiments are well-thought and extensive: it addresses the drawbacks of the previous homophilous and heterophilous node classification benchmarks identified in previous works by using more recent benchmark datasets, and include 13 baselines for a comprehensive evaluation of the proposed method.
- The proposed approach, CMGNN, has the best overall performance against 13 baselines on 10 benchmark datasets.
Weaknesses
- This work builds upon the findings of several previous works regarding the effective designs for GNNs under heterophily and when is heterophily challenging (or in other words, "bad") for GNNs. While the authors cited these works in some parts of the paper ([6,9,12,18] in References), I feel that **some of the observations in the paper overlapped with the findings in previous works, and their connections and differences are not clearly stated in the paper**.
- For example, Observation 1 seems to overlap with the previous observations made in [6] ("to ensure that the neighborhood patterns for nodes with different labels are distinguishable, the inter- class similarity should be low") and [9] ("two key factors, low-degree nodes and complex compatibility matrices, deteriorate the distinguishability of the neighborhood label distributions when coupled with heterophily, thus making heterophily a unique challenge for GNNs in most cases").
- Given this, I also think that the claim in the related work section (line 732-734) that "these reviews ... not exploring the reason behind the effectiveness of message passing in heterophilous graphs" is inaccurate, as this paper is in fact built upon these analyses regarding the effectiveness of message passing in heterophilous graphs.
- Section 5 (method) is too condensed to present a clear picture of how the proposed Compatibility Matrix-Aware GNN (CMGNN) works for the readers. For example, it is unclear what "topology structure" that the authors are considering as "additional available node features", and the term in Eq. 7 is not well explained. The authors also didn't explain clearly in the main paper how is the "soft pseudo labels" being generated for the model. It will help with the understanding if the authors can include a figure showing the architecture of the proposed CMGNN model. I feel the "method" section is the most novel part in the paper and deserves more length in the paper.
- It would be good to analyze the computational complexity and/or compare the empirical runtime of the model with the baselines.
- As a minor point, the "Norm" term in Eq. 3 should be explained as "L1 normalization for matrix row vectors" to avoid the confusion that the normalization is done with the L1 norm for *matrix* (instead of for vectors).
Questions
- As per Weakness point 1, can you describe how the observations in the paper are connected to, and different with, prior observations in [6,9,12,18]?
- As per Weakness point 2, what is the "topology structure" that you considered as "additional available node features"? How does the use of these features affect the performance of the proposed model?
- Can you provide some analysis regarding the computational complexity and/or the empirical runtime of the model?
Limitations
The authors acknowledged the limitation that the proposed HTMP framework is only applicable to GNNs following the message-passing mechanism. One additional limitation is that the paper is mostly empirical and does not give theoretical underpinnings.