Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond

Summary

The main contribution of this paper is a new measure called label informativeness that characterizes how much information a neighbor’s label provides about a node’s label. The paper also discusses the expected properties of homophily. The experimental results are based on the relation between the performance of GNN and the proposed metric.

Strengths

1. The quality of the theoretical demonstrations. Most of the demonstrations seem correct, even though I did not go exhaustively through the details, as they are in the supplementary material. 2. Good discussion about homophily. The paper covers several aspects of homophily, mentioning the desired properties of this measure. 3. The clarity of the proposition. It is clearly stated the main contribution of the paper. 4. Readability. The paper is well-written, being very simple to read.

Weaknesses

1. The novelty of the work could be questionable. The measure is not novel, please refer to "On the Estimation of Relationships Involving Qualitative Variables", available at https://www.jstor.org/stable/2775440. The submitted paper presents an uncertainty coefficient that is closely related to the work proposed in this paper. Even though, that paper does not focus on graphs, the proposed measure seems to be the application of this measure over a particular distribution, rather than the proposition of a new measure. Second, the same formulas and equations are already published in [16]. Moreover, in [16], it is mentioned that LI was previously introduced. 2. The conclusion mentions "LI characterizes how much information a neighbor’s label provides about a node’s label". Unfortunately, this is not explained in the paper, except by the phrase "$LI \in [0, 1]$ If the label y_n allows for unique reconstruction of y_\epsilon , then LI = 1. If y_\epsilon and y_n are independent, LI = 0". 3. The paper mentions that "Through a series of experiments, we show that LI correlates well with the performance of GNNs.". Based on https://www.jstor.org/stable/2775440, I believe that this is related because the measure is based on the classification performance, rather than GNN. 4. The limitations mention "this measure to be both informative and simple to compute and interpret.". However, no interpretations are given besides the values of 0 and 1.

Questions

1. Regarding the analysis of the value. Does LI have a linear scale of the values? Does a value of 0.5 mean 50% of reconstruction? 2. Is the LI general enough to obtain similar correlations with other classification models (I think so)? 3. Could you explain the main difference between LI (the metric, not the way that is used) and https://www.jstor.org/stable/2775440? 4. Could you explain the difference between LI with respect to the LI metric used in the published paper [16]?

Rating

3: Reject: For instance, a paper with technical flaws, weak evaluation, inadequate reproducibility and incompletely addressed 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

3 good

Contribution

2 fair

Limitations

Yes, the authors clearly state the limitations of their work. However, there are some limitations that were omitted. As a suggestion, if the main contribution is the use of the JSTOR paper in graphs. Please state it this way, rather than saying that this is a new measure.

Summary

This paper analyzes homophily measures and proposes a new characteristic highly correlated with performance. Specifically, the authors suggest desirable properties for the metric and show that current homophily measures do not satisfy some important properties, so suggest a new homophily measure to satisfy them. Furthermore, beyond homophily arguments, the authors suggest a new characteristic that is more highly correlated with performance from the perspective of the usefulness of neighbor labels to predict the label of the corresponding center node. They demonstrate that the correlation between the values of proposed measures and performance is significantly higher than current homophily measures on various architectures and datasets.

Strengths

- The authors suggest the desirable properties for the metrics and show that current homophily measures do not satisfy important traits such as asymptotic constant baseline. - They suggest adjusted homophily to satisfy most of the important properties including the asymptotic constant baseline. - They propose a new characteristic describing the effectiveness of graph structure for performance. - The proposed characteristic exhibits a significantly higher correlation with performance compared to homophily measures.

Weaknesses

Although the authors provide the correlations between performance and a given metric on Cora and Citeseer by modifying graphs synthetically, it seems not enough to show the general applicability.

Questions

Could you provide the results when calculating the correlation only based on the values of metrics and performance in Appendix Table 4, without manipulating the original 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

3 good

Presentation

4 excellent

Contribution

3 good

Limitations

As the authors mentioned, LI only considers node label interaction in graphs.

Summary

This paper focuses on developing techniques to characterize graph node classification datasets. First, this paper has proposed a theoretical framework to develop measures of graph’s characteristics. Then two measures called “adjusted homophily” and “label informativeness” are proposed to easily characterize the connectivity patterns of graph datasets. And experimental results show the stronger correlation of proposed measures with GNNs’ performance.

Strengths

1. This paper has analysis the drawbacks of existing measures, like node homophily and edge homophily. 2. This paper has proposed a generic framework with theoretical analysis to develop techniques for characterizing graph node classification datasets, which will help to design more suitable models on certain datasets. And proposed minimal agreement, maximal agreement, and monotonicity is very useful. 3. The proposed adjusted homophily get rid of the number of class and class size on different datasets and is of broader applicability. 4. The proposed label informativeness have a strong correlation with the GNN’s performance, which is interesting and novel. Moreover, this can help to design more powerful development of heterophily-suited GNNs.

Weaknesses

1. Only Cora and Citeseer that be considered as homophilic graphs are used for showing the correlation between GNNs’ performance and LI, more heterophilic graphs should be tested. 2. Assortativity coefficient is mentioned in section 2.4, but there is not comparison with proposed measures.

Questions

1. More details about how to get the adjusted value in lines 183 and 184. 2. Edge label informativeness seems to be smaller than node label informativeness in most cases, any explanation about this?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed 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

3 good

Contribution

3 good

Limitations

Authors have adequately addressed the limitations in this paper.

Summary

The paper proposes new measures to characterize homophily and heterophily in graph datasets. First, some desirable properties are asserted for a good measure of homophily. It is discussed whether various prior measures of homophily satisfy these properties, then a new measure called *adjusted homophily* is proposed; this is a modification of the established measure of *edge homophily* using information about (degree-adjusted) class distributions of nodes. After this, to capture the fact that a node's class label can be, depending on the dataset, either informative or uninformative about its neighbor's class label, a measure called *label informativeness* (LI) is also proposed. When randomly sampling an edge $(u,v)$, this is the fraction of the information content of a $u$'s class label that is given by knowing $v$'s class label. After establishing these measures, the paper lists them for several real-world datasets. In experiments on synthetic SBM graphs and semi-synthetic modifications of the Cora graph, the authors show that LI is better correlated with GNN performance than homophily.

Strengths

- The homophily/heterophily topic has seen a lot of interest in the past few years, so this work is likely to get much attention. - The paper is very well-written. It is logically organized and easy to read. - The paper makes a compelling case that both the adjusted homophily and LI measures are the most sensible such measures.

Weaknesses

- While LI seems like a very sensible measure, it is rather straightforward, so I am left thinking: First, has it really not been proposed by some prior work, especially given that the general concept of normalized information measures is well-established (e.g., [this](https://en.wikipedia.org/wiki/Mutual_information#Normalized_variants))? I don't see this as a weakness on it's own, since I am not aware of such prior work. However, I do feel that some more graph-specific theoretical work addressing the first limitation listed in the paper (i.e., variants of homophily/LI that consider multiple hops in the graph) would significantly increase the contribution. The paper seems to state that this is beyond the scope of the work, but I feel the amount of contribution is a bit borderline as it is. - The experiments positing that LI is well correlated with GNN performance are on synthetic or semi-synthetic datasets only. Ideally, some trend could be shown across a variety of real-world datasets, though it is understandable that such a trend may not exist given various factors besides LI. ### Typos - Figure 8: "edge homopily"

Questions

My questions correspond to points from the prior section: - Assuming that LI is indeed a new measure, do you see some variant of it that could work for more than 1 hop across the graph? Or otherwise, do you think such measures are unlikely to be informative? - Do you expect there to be a general trend (even if it is a weak trend) that, across the usual benchmark graph datasets, higher LI corresponds to higher node classification performance? Or do you at least expect a higher correlation than with (adjusted) homophily? I think it would be interesting to see plots like the ones for the synthetic datasets, except for (some fraction of) the graphs in Table 4.

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

3 good

Presentation

4 excellent

Contribution

2 fair

Limitations

Limitations are adequately addressed in a designated section of the conclusion.

Thanks for the answer

I have read the author response. Thanks for agreeing that the measure is similar to previous work. This was one of my main issues.