acceptodds
Under review as a conference paper at ICLR 2027

What Is Still Missing in Graph Homophily? Degree Regularity Matters

Abstract

Graph homophily, the tendency of connected nodes to share similar characteristics, is widely used to understand and predict the performance of Graph Neural Networks (GNNs). Most homophily metrics, however, capture only local similarity patterns, such as label or feature consistency across edges. In this paper, we study whether a global graph property, the dispersion of the degree distribution, carries performance-relevant information that local homophily misses. We introduce degree regularity, which quantifies how uniform the node degrees are, relate degree dispersion to aggregation noise through elementary results, and add it to a local homophily factor to obtain degree-aware glocal homophily. To study degree dispersion in a controlled setting, we develop a calibrated degree-aware synthetic graph generator, which reveals that varying degree dispersion can silently vary density; at nearly fixed density, the effect of dispersion on GNN accuracy changes sign with label homophily, as a stylized aggregation model explains. On 31 real-world datasets, with baseline metrics recomputed from their definitions, degree regularity is positively associated with GNN accuracy beyond local homophily. Degree-aware glocal homophily attains the highest correlation with the accuracy of GNNs among 24 metrics. These results suggest that global degree properties complement local homophily in explaining GNN performance.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
homophily, graph neural networks, graphs

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.80 over 5 reviews, above 27% of the others.
Reviewer_uM6XOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This work focuses on understanding whether degree dispersion informs GNN performance, going beyond what existing homophily measures enable. Building on prior work connecting degree and homophily to graph learning, the authors introduce degree regularity, which measures how concentrated the degree distribution is, and incorporate it into Tri-Hom to construct a degree-aware global homophily. Additionally, the authors develop a calibrated synthetic graph generator to investigate this relationship, finding that more uniform degrees can help or hurt performance depending on label homophily. On a large set of real-world datasets, the proposed metric achieves higher correlations with GNN accuracy than the evaluated alternatives.

Critical strengths
  1. I think the joint understanding of degree and homophily is very important for graph learning, and the authors do a good job of looking at a large set of metrics.
  2. I found the synthetic analysis useful and interesting, particularly the demonstration that changing degree dispersion can unintentionally change graph density. The finding that the direction of the effect depends on label homophily is also interesting, although it would benefit for further situation within the literature (see W1)
  3. The empirical results seem fairly comprehensive given the wide array of properties studied, as well as datasets covered.
Critical weaknesses
  1. One thing that remains unclear to me is the novelty of the work. I think the analysis is comprehensive, but several previous works already examine how degree and homophily interact to affect GNN behavior. For instance, [1] and [2] study these interactions, albeit at the node-level. Can the authors comment on what additional understanding is provided by this work? The authors should also consider ESNR [3], which already evaluates GNN performance across different connectivity and homophily settings. Comparing against ESNR would help establish whether the proposed metric captures additional information beyond existing approaches with a similar objective.
  2. I am also somewhat uncertain about how reliably the proposed metric improves on Tri-Hom. The gains in correlation are quite small, and, while the authors acknowledge the limited statistical power, the generalization results raise a related concern where performance on unseen benchmark families is mixed. I appreciate that the authors include these checks, but in total the results seem somewhat inconclusive. Perhaps this would be partially addressed by addressing W1 and clarifying novelty.
  3. Another question is whether the global degree adequately captures the interaction motivating the paper. For instance, two graphs can have the same degree distribution and homophily while differing in whether their high-degree nodes tend to have homophilous or heterophilous neighborhoods. Could the authors examine performance jointly by degree and node-level homophily, and investigate whether degree regularity remains informative after accounting for their relationship?

Minor point:

  1. While I appreciate the intention behind Table 43, the “claim/evidence/verdict” format reads more like an internal review checklist than part of a scientific paper. I think discussing their implications within the work itself would be more beneficial.

[1] Yan et al. "Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks" [2] Loveland et al. "On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks" [3] Dong and Kluger "Towards Understanding and Reducing Graph Structural Noise for GNNs"

Questions for authors

Please see weaknesses

Reviewer_pkwBOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies whether degree dispersion explains GNN performance beyond local homophily. It defines degree regularity rdeg=exp⁡(−γ CV2(d))r_{deg}=\exp(-\gamma\,\mathrm{CV}^2(d)) and incorporates it into Tri-Hom to obtain degree-aware glocal homophily. Elementary aggregation results motivate studying dispersion, and a degree-aware generator shows effects on GCN accuracy whose sign depends on label homophily. Across 31 benchmark graphs, the glocal factor correlates best with GCN, GraphSAGE and GAT scores among the compared metrics. The paper also tests conditional associations, sensitivity and predictive calibration.

Critical strengths
  1. The benchmark analysis is transparent. Per-dataset values allow the correlations to be checked, and the authors report power, family effects and limitations of their claims. Selecting γ\gamma inside each leave-one-dataset-out fold still improves predictive R2R^2 over Tri-Hom for all three GNNs, which provides some support beyond the raw correlations.

  2. The synthetic study shows why density needs to be monitored when varying degree dispersion. With reduced density variation, dispersion helps GCN in moderately heterophilic settings and hurts it in homophilic ones. This is informative even though the proposed glocal formula cannot represent the sign change, a limitation the authors acknowledge.

Critical weaknesses
  1. The target metric needs clarification. Table 19 labels all scores as accuracy, whereas the original benchmark paper (Platonov et al. 2023) reports ROC AUC for Minesweeper, Tolokers and Questions. If this convention was retained, the pooled correlations combine different performance measures. Their robustness to metric choice remains unresolved.

  2. Evidence for the specific regularity statistic and scoring rule is still limited. The correlation gain over Tri-Hom is small and not statistically significant; the study has low power at the observed effect size. Significance of the rdegr_{deg} association depends strongly on the MLP control and the family-adjustment specification. Positive results for the glocal factor and exploratory Gini analysis support studying degree dispersion, but do not establish a robust advantage of the chosen statistic. The abstract should reflect these qualifications, which the body discusses openly.

Questions for authors
  1. Which metric is reported for each binary dataset? If metrics differ, do the conclusions hold when datasets are analysed separately by metric? Please also report leave-one-dataset-out sensitivity of the conditional rdegr_{deg} association and the gain over Tri-Hom. Stability under these checks would strengthen my assessment.

  2. For target hLh_L between 0.1 and 0.4, does the negative effect of regularity in Table 14 persist after controlling for realized mean degree within that regime? The trained grid still has mean-degree variation of 10.5–12.3, while the reported partial correlations pool broader homophily ranges.

Reviewer_pv56OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper investigates whether degree dispersion provides information about GNN performance beyond existing homophily measures. It introduces degree regularity, an exponential transformation of the squared coefficient of variation of node degrees, and incorporates it into Tri-Hom to construct a degree-aware glocal homophily score. The paper also develops a degree-aware contextual stochastic block model and provides elementary theoretical analyses of aggregation noise and regime-dependent effects of degree dispersion. Validation includes controlled synthetic experiments and correlation analyses across 31 real-world datasets using GCN, GraphSAGE, GAT, and MLP. The results suggest that degree dispersion provides complementary information under certain controls, while the proposed score achieves modest, statistically non-significant correlation gains over Tri-Hom for the three GNNs.

Critical strengths
  1. Informative analysis of degree dispersion and density confounding. The synthetic experiments show that varying degree dispersion can inadvertently change graph density and that, with density variation reduced, the effect of dispersion on GCN accuracy can reverse across homophily regimes. This provides a useful qualification to the intuition that more uniform degrees consistently improve GNN performance.

  2. Extensive robustness checks and transparent reporting. The paper goes beyond reporting correlations by examining statistical significance, alternative degree statistics, hyperparameter sensitivity, dataset-family effects, and out-of-sample calibration. It also explicitly reports non-significant improvements and limitations of the theoretical explanations. These analyses make the empirical findings more interpretable and help distinguish conditional evidence for degree dispersion from support for the particular proposed formula.

Critical weaknesses
  1. Limited justification and distinctiveness of the proposed metric. The main methodological contribution adds a heuristic degree-dispersion penalty to Tri-Hom. Neither the exponential transformation nor the squared penalty follows from the theoretical results, and alternative statistics and functional forms achieve similar performance. More importantly, the score consistently penalizes degree dispersion, whereas the synthetic experiments show that dispersion can improve accuracy in some heterophilic regimes. This disconnect weakens the case that the proposed formula captures the phenomenon motivating the paper.

  2. Insufficient evidence of a robust, generalizable improvement over Tri-Hom. The correlation gains for GCN, GraphSAGE, and GAT are small and statistically non-significant (Williams’ test: p=0.57p=0.57–0.780.78). Although some conditional analyses and leave-one-dataset-out results are favorable, leave-one-family-out performance deteriorates substantially when the degree-regularity hyperparameter is selected within training folds. These results leave unresolved whether the proposed score offers a reliable improvement on unseen graph families, which is central to its value as a dataset-level performance indicator.

Questions for authors
  1. What evidence supports the specific exponential transformation and squared penalty over the alternatives evaluated in the appendix? How should the consistently negative effect of dispersion on the proposed score be reconciled with the positive effect on accuracy observed in some heterophilic regimes?

  2. Which design choices—including the degree statistic, functional form, normalization constants, and γ\gamma—were fixed independently of the 31 evaluation datasets? Given the deterioration in leave-one-family-out performance with in-fold γ\gamma selection, what evidence supports transfer to unseen graph families? Please distinguish validation of a fully fixed specification from analyses performed after examining these datasets.

Reviewer_nZzSOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies whether graph-level degree dispersion adds information beyond local homophily factors. It introduces degree regularity, a heuristic extension of Tri-Hom, elementary aggregation analyses, and a calibrated degree-aware graph generator. Synthetic experiments examine a density confound and changes in the relationship between degree dispersion and GCN accuracy across homophily regimes. An audit of 31 real benchmarks compares graph metrics while examining statistical uncertainty, benchmark families, control variables, design search, and out-of-sample calibration.

Critical strengths
  1. The synthetic analysis identifies a concrete density confound in the studied generator variant. Lemma 1 explains how square-root weighting compresses degree dispersion and couples it with mean degree. Table 2 reports a conditional Pearson correlation of 0.766 between regularity and accuracy for that variant, versus a within-slice partial correlation of 0.021 after adjusting for realized mean degree. Section 6.1 specifies conditional correlations with other factors fixed, averaged over slices, and partial correlations within slices; these are not pooled correlations over all generated graphs. The default construction gives a corresponding partial correlation of 0.324, with effects differing across homophily regimes. Calibration also documents imperfect target realization and residual density variation. These findings provide useful guidance for interpreting this generator without requiring the new metric to be superior.

  2. The real-data audit examines uncertainty rather than relying on a metric ranking alone. Section 6.2 reports dependent-correlation tests, bootstrap intervals, family effects, out-of-sample calibration, and a permutation analysis over the authors' design search. It also reports stronger conditional associations for Gini-based dispersion than for the proposed statistic. This supports a useful methodological contribution: apparent improvements on this benchmark collection require attention to family dependence and selection effects. The numerical power and effective-sample-size estimates apply to this analysis and should not be treated as universal properties of graph benchmarks.

Critical weaknesses
  1. The abstract could communicate the uncertainty already established in the body more clearly. The highest-correlation statement is supported as a descriptive ranking in Table 3. However, Table 4 reports GNN correlation gains of 0.013–0.029, Williams-test p-values of 0.57–0.78, and bootstrap intervals spanning zero. Section 6.2 further qualifies the evidence after design-search and family-sensitive analyses. These results establish neither a resolved improvement nor equivalence. Adding this qualification to the abstract would better distinguish the observed ranking from evidence of a superior metric.

  2. Evidence for a transferable scoring rule remains limited. Table 3 uses fixed C = 3 and spectral radius 10. Appendix D.6, Table 42, supplies the dataset-specific alternative and still reports a positive observed difference for the graph-aware factors, including GCN correlation 0.652 versus 0.612 for Tri-Hom. The main table would be easier to interpret alongside that setting and its uncertainty analysis. Separately, Table 4 reports weaker held-out-family calibration when gamma is selected within the training families. In my assessment, this limits the operational generalization claim, although the paper acknowledges the limitation and the methodological findings remain useful.

Questions for authors
  1. Can you qualify the abstract's highest-correlation statement with the uncertainty reported in Section 6.2?
  2. With dataset-specific C and spectral radius, do the dependent-correlation tests and family-sensitive, in-fold analyses support the same interpretation? Bringing these results together would clarify the metric's intended scope without requiring a new benchmark collection.
Reviewer_UDpDOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper analyzes the problem of homophilic versus heterophilic class relationships of connected vertices. It argues that the global degree distribution is an important factor to assess homophily. The authors argue that the degree "is positively associated with GNN accuracy beyond local homophily."

Critical strengths

Timely problem addressed Experiments on synthetic and real-world graphs

Critical weaknesses

Not entirely clear what the novelty is A lot of details that make it difficult to see the big picture

Questions for authors

The authors already identify that, e.g., GNN performance varies with the degree and with homophily. The next sentences should be rephrased to make it understandable: "What remains open is whether a graph-level summary of degree dispersion adds information beyond a performance-reflective homophily factor, how robust this is to the family structure of benchmark collections, and whether its effect has the same sign in all homophily regimes."

This continues with the contributions list, which the first one again refers to "family structure" (what is that?) and significance and power analyses, etc. -- it is unclear what this bullet item is about.

For the second bullet item: Please add that DA-CSBM is your contribution (first mentioned only in the related work). Why is the observation surprising, i.e., with a fixed degree, classifying homophilic graphs becomes easier for GCNs but harder on "moderately" heterophilic ones? A varying degree introduces obvious noise into the aggregation function, and a "fixed" degree in a homophilic structure will send homophilic messages into the aggregation.

The explanation is delivered by the authors themselves right in Section 4: "Nodes with different degrees aggregate information from different numbers of neighbors, and real- world graphs have broad, often right-skewed degree distributions (Appendix Table 18)."

It should be noted that the Tri-Hom (=CSBM-3H) feature of structural homophily is directly related (although not identical) to the degree distribution.

The condition of dmin ≥ 1 in Proposition 1 is likely to remove some vertices in datasets such as Cora.

Nevertheless, the introduction of the Degree-aware glocal homophily metric with line 183ff is very interesting. The argument that Eq. (4) is "an empirical scoring rule, not as a scientific mode" is fine for the reviewer, but the ad hoc extension should be explained: where does the "heuristic extension" come from, how is it motivated, etc. The procedure of developing this heuristic would be important to know.

The goal of the paper is quite fuzzy until Section 5. The statement here should be put directly into the abstract and intro: "To vary degree dispersion at fixed local-factor targets, we extend the CSBM-3H generator of TriHom with node-specific degree weights, in the spirit of the DC-SBM"

It is not clear what the novelty of the proposed CSBM is; at least it has not been clearly carved out by the authors. Given Eq. (7), the authors themselves acknowledge that this is a special case of the DC-SBM.

The sizes of the synthetic graphs should be reported. Also, it appears there is no hyperparamter optimization and reporting of hyperparamter values for the GNNs.

The Williams’ test should be properly reported using APA style, including, among others, the p-value and degrees of freedom.

Please explain your power analysis: "Williams’ test has 5–8% power with 31 datasets"; later one realizes the reason: Table 25 in the appendix. Thus, "depending on the GNN used" should be added.

A beta = 20% would be desirable. So why would one go for "roughly 400–800 datasets for 50–80% power"? The more important question is: Why would one want such a power?

The experiment in Section 6.3 is too brief. Does Figure 2 show the performance of those nodes in the datasets with a specific degree? Yes, so how many of the nodes are there with such a degree? In some cases (=degrees), there might be many samples; in others, very few. What does the n in the plots mean, and why is it approximate?

The statistics reported is incomplete: "A χ2 test of equal accuracy across the groups (Bonferroni over datasets) rejects for six of eight datasets in at least half of the seeds, but not for Cora or Texas". First, why would one conduct a chi-square test, since Accuracy is not a binary variable? Second, since there is an appendix, there is no reason to provide the statistics in proper format (APA style) and with the details.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.