REVIEW 1 major objections 7 minor 27 references
Revisiting Graph Homophily Measures
T0 review · 1 major / 7 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper constructs a graph homophily measure — called unbiased homophily — that provably satisfies every desirable property previously proposed, and proves that for directed graphs such a measure cannot exist.
desk verdict Solid, useful undirected homophily construction with a correct proof; the directed impossibility claim is overreaching beyond the edge-wise setting. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The object carrying the argument is the normalized class adjacency matrix $C$, with entry $c_{ij}$ equal to the fraction of edges joining classes $i$ and $j$, together with the label-independent baseline $\mathrm{rand}(C)$ defined through the configuration-model expectation $\mathrm{rand}(C)_{ij}=a_i a_j$, where $a_i$ is the share of edges incident to class $i$. Unbiased homophily compares observed fractions of heterophilic edges $c_{ij}$ with the expected values $\sqrt{c_{ii}c_{jj}}$ under that baseline: the numerator sums $\sqrt{c_{ii}c_{jj}}-c_{ij}$, and the denominator normalizes the ratio so the measure lies between $-1$ and $1$, with an extra term $\alpha\min(\sum_i\sqrt{c_{ii}},1)$ that resolves sensitivity in rare degenerate cases. The proof verifies each axiom directly against this formula: the square-root term makes the constant baseline exact because $\mathrm{rand}(C)$ has $c_{ii}=a_i^2$, and the ratio form makes the measure scale-invariant. The directed impossibility result is carried by two explicit matrices showing that the same normalized matrix can be simultaneously fully heterophilic and label-independent, and that deleting heterophilic edges can preserve the label-independent baseline.
What would settle it
Enumerate all small rational normalized class adjacency matrices, say all symmetric nonnegative matrices with entries summing to 1 and denominators up to 20, and check whether $h^1_{\mathrm{unb}}$ satisfies homo-monotonicity, hetero-monotonicity, minimal agreement, and constant baseline on every matrix with at least two nonzero entries; any violation would disprove Theorem 5.1. For the directed claim, exhibit a single directed homophily measure satisfying all five properties, since the paper proves that no such measure can exist.
Extended reading notes
Core claim
The central claim is that the normalized class adjacency matrix $C$, whose entries are the fractions of edges joining each pair of classes, supports a measure of the form $$h^\alpha_{\mathrm{unb}}(C)=\frac{\sum_{i<j}\bigl(\sqrt{c_{ii}c_{jj}}-c_{ij}\bigr)}{\sum_{i<j}\bigl(\sqrt{c_{ii}c_{jj}}+c_{ij}\bigr)+\$\alpha$\,\min\bigl(\sum_i\sqrt{c_{ii}},1\bigr)},$$ where $\alpha>0$ is any positive constant. Theorem 5.1 proves that for every $\alpha>0$ this measure is continuous, has all the desirable properties listed in the paper, and has $R_{\max}=1+\alpha$, $R_{\mathrm{base}}=\alpha$, $R_{\min}=-1$, resolving the open question of whether any homophily measure can satisfy the full set of properties. The practical recommendation is $\alpha=0$, giving $$h_{\mathrm{unb}}(C)=\frac{\sum_{i<j}\bigl(\sqrt{c_{ii}c_{jj}}-c_{ij}\bigr)}{\sum_{i<j}\bigl(\sqrt{c_{ii}c_{jj}}+c_{ij}\bigr)},$$ which has all the properties except in the rare special case where at most one class has intra-edges. For directed graphs, the paper proves two contradictions: constant baseline conflicts with minimal agreement, and constant baseline conflicts with hetero-monotonicity, so the full set of properties is unsatisfiable in the directed setting.
Load-bearing premise
The load-bearing premise is that a label-independent graph is one whose edges are redrawn randomly while preserving node degrees, captured by the baseline $\mathrm{rand}(C)_{ij}=a_i a_j$; every claim in the paper is measured against that specific baseline.
Editorial extensions
If this is right
- Unbiased homophily can be used to compare homophily levels across datasets with different numbers of classes and class-size balances, because its baseline value is fixed at 0 for label-independent structure.
- On fully heterophilic graphs, any measure satisfying minimal agreement, including $h^\alpha_{\mathrm{unb}}$, returns the same minimum of $-1$, correcting the known failure of adjusted homophily to score such graphs as strongly heterophilic.
- The equivalent formula $h_{\mathrm{unb}}(C)=\frac{(\sum_i\sqrt{c_{ii}})^2-1}{(\sum_i\sqrt{c_{ii}})^2+1-2\sum_i c_{ii}}$ requires only the fractions of intra-class edges, making the measure cheap to evaluate on large graphs.
- For directed graphs, no edge-wise scale-invariant measure can satisfy all five properties, so future work must relax or redefine the axioms, for instance through the randomization monotonicity property proposed in the paper.
- Weighted undirected graphs inherit the same guarantees by replacing edge counts with total edge weights in the class adjacency matrix.
Reading between the lines
- If the configuration-model baseline were replaced by a different notion of label independence, such as uniform random relabeling, the axiomatic results would not automatically transfer; the existence and impossibility claims are tied to the degree-preserving randomization baseline.
- The ratio construction, which compares baseline-minus-observed to baseline-plus-observed using square-root terms, could serve as a template for building other axiomatic graph measures by varying the baseline or the aggregation over class pairs.
- Because directed edge-wise homophily measures correspond one-to-one to classification evaluation measures, the directed impossibility result suggests that classification evaluation measures cannot simultaneously satisfy the analogous five properties, which may explain known trade-offs in that setting.
- One could test how often the special-case failure of $h_{\mathrm{unb}}$ (at most one class with intra-edges) actually occurs in real datasets; the paper asserts the case is rare but does not quantify its frequency.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper proposes a new homophily measure, unbiased homophily, for undirected (and weighted positive) graphs. Given the normalized class adjacency matrix C, the measure is h^alpha_unb(C) = (sum over i<j of (sqrt(c_ii c_jj) - c_ij)) / (sum over i<j of (sqrt(c_ii c_jj) + c_ij)) + alpha * min(sum_i sqrt(c_ii), 1), for alpha > 0. The authors prove (Theorem 5.1) that for any alpha > 0 this measure is continuous, satisfies the five desirable properties from Platonov et al. [6] (maximal agreement, minimal agreement, constant baseline, monotonicity, empty class tolerance) plus class symmetry, with Rmax = 1 + alpha, Rbase = alpha, Rmin = -1. They recommend the simpler alpha = 0 version hunb, explicitly noting that it fails minimal agreement and monotonicity in the rare case when at most one class has intra-edges. The paper also empirically demonstrates inconsistencies among existing measures and provides an impossibility result for directed graphs: for edge-wise scale-invariant measures, constant baseline contradicts minimal agreement and also contradicts hetero-monotonicity (Appendix I). The paper claims these contradictions hold for arbitrary measures, but the extension proof is only a sketch.
Significance. If the undirected results hold, the paper resolves the open question from [6] in the positive direction and provides a simple, interpretable, parameter-light measure with strong axiomatic guarantees. Appendix E contains detailed proofs that appear correct, and the empirical examples are useful illustrations of the failure modes of existing measures. The directed impossibility results are interesting but only established for the edge-wise scale-invariant class; the stronger unconditional claim in the abstract is not supported by the proof as written.
major comments (1)
- [Appendix I, subsection 'Not necessarily edge-wise scalar-invariant measures'] The attempted extension of the directed impossibility from edge-wise scale-invariant measures to arbitrary measures is not a valid proof. Constant baseline is defined (Definitions 9-10) only on normalized class adjacency matrices, and for a non-edge-wise measure h the expression h(rand(C_G)) is not defined because rand(C_G) is a matrix rather than a graph; the property must instead be stated on randomized graphs. The argument that a graph with normalized matrix K and satisfying constant baseline must have h(K) = R_base has no basis. Therefore, Propositions I.1 and I.2 establish contradictions only for edge-wise scale-invariant measures. The abstract's unconditional statement 'we prove that some desirable properties contradict each other and thus a measure satisfying all of them cannot exist' is unsupported for non-edge-wise measures. The formal claims should be explicitly restricted to the edge-wise scale-invariant class, or a rigorous definition of constant baseline for general measures together with a valid proof should be supplied.
minor comments (7)
- [Table 2] The entry for node homophily marks monotonicity with a checkmark, but the example in Section 4 explicitly shows that deleting a heterophilic edge between two nodes that have no same-class neighbors leaves node homophily unchanged; the entry should be a cross, not a check.
- [Appendix E, homo-monotonicity proof] The displayed derivative expression for the second term is misprinted: the term for c_11 is written as 1/sqrt(c_11), but the other entries are written as c_ii/sqrt(c_ii) instead of sqrt(c_ii). The correct derivative is (1/2)(1/sqrt(c_11) - sum_i sqrt(c_ii)). The conclusion is unaffected.
- [Appendix D, constant baseline verification] The text says 'h(C) = sum_i sqrt(c_ii) = 1' for C = rand(C), which is inconsistent with the stated Rbase = 0. The intended statement is h(C) = sum_i sqrt(c_ii) - 1 = 0.
- [Section 6.2] The claim that h_class, h_adj, and h_unb 'have been motivated by the constant baseline property' is inaccurate because h_class does not satisfy constant baseline (see Table 2). The sentence should be rephrased.
- [Abstract and Section 5.2] The term 'unbiased homophily' is used both for the family h^alpha_unb, which has all desirable properties for alpha > 0, and for the recommended default h_unb with alpha = 0, which fails minimal agreement and monotonicity in a rare degenerate case. This conflation should be clarified, especially in the abstract.
- [Appendix F title] There is a typo in the title: 'Ajusted' should be 'Adjusted'.
- [Section 5.2] The statement that 'the denominator of the first term is always greater than zero' should be qualified by the standing assumption that C has at least two non-zero elements; for a graph with a single class (c_11 = 1) the denominator of the first term is zero.
Circularity Check
No circularity: the undirected construction is self-contained and the axioms are external inputs; the only flagged issue is a non-circular proof-skeleton gap in the directed generalization.
full rationale
The paper's central claims are (i) an explicit formula h^alpha_unb satisfies the axiomatic properties, and (ii) the directed axioms are contradictory. The proof of (i) is self-contained: the properties are stated in Appendix C as definitions, the measure is given in Eqs. (2)/(3), and the proof in Appendix E verifies each property by direct substitution and inequalities without assuming the conclusion. The constant-baseline check is h(rand(C)) = 0 + alpha because sqrt(a_i^2 a_j^2) = a_i a_j, which is a proof, not a restatement. The axioms themselves are imported from Platonov et al. [6], whose author list overlaps with the present paper (L. Prokhorenkova), but this is not load-bearing circularity: the prior work is cited as the source of the property list and the open problem, not as a theorem whose content is reused; the existence of a satisfying measure is exactly what the present proof establishes. The footnote on page 6 explicitly disclaims uniqueness, so no uniqueness is imported from the authors. The only passage that should be flagged is Appendix I.2, 'Not necessarily edge-wise scalar-invariant measures': the generalization of the directed contradiction to arbitrary measures is presented only as a 'sketch of the proof' ('Let us give a sketch of the proof that the same examples work for any measure that is not necessarily scalar-invariant or even edge-wise'), and as written it does not completely bridge from normalized class-adjacency matrices to arbitrary non-edge-wise measures. That is a rigor/completeness concern, not circularity, and it does not affect the undirected construction or the formal directed propositions for the edge-wise scale-invariant class. Overall, no step in the derivation reduces to its own input.
Assumptions & free parameters
free parameters (1)
- α =
not fitted; any α > 0, recommended α = 0
assumptions (3)
- domain assumption The five desirable properties (binary monotonicity by edge type, minimal/maximal agreement, empty class tolerance, constant baseline) from Platonov et al. are the correct criteria for a homophily measure.
- domain assumption The configuration-model baseline rand(C)_ij = a_i a_j (undirected) and rand(C)_ij = a_i b_j (directed) correctly represents 'graph structure independent of labels'.
- ad hoc to paper A homophily measure should be edge-wise, scale-invariant, and continuous.
Cite this review
Pith. "Pith review of Revisiting Graph Homophily Measures." pith.science (2026). https://pith.science/paper/DTXG465M
@misc{pith2026241209663,
author = {Pith},
title = {Pith review of: Revisiting Graph Homophily Measures},
year = {2026},
howpublished = {\url{https://pith.science/paper/DTXG465M}},
note = {Machine review of arXiv:2412.09663}
}
read the original abstract
Homophily is a graph property describing the tendency of edges to connect similar nodes. There are several measures used for assessing homophily but all are known to have certain drawbacks: in particular, they cannot be reliably used for comparing datasets with varying numbers of classes and class size balance. To show this, previous works on graph homophily suggested several properties desirable for a good homophily measure, also noting that no existing homophily measure has all these properties. Our paper addresses this issue by introducing a new homophily measure - unbiased homophily - that has all the desirable properties and thus can be reliably used across datasets with different label distributions. The proposed measure is suitable for undirected (and possibly weighted) graphs. We show both theoretically and via empirical examples that the existing homophily measures have serious drawbacks while unbiased homophily has a desirable behavior for the considered scenarios. Finally, when it comes to directed graphs, we prove that some desirable properties contradict each other and thus a measure satisfying all of them cannot exist.
Figures
Reference graph
Works this paper leans on
-
[6]
Characteriz- ing graph datasets for node classification: Homophily-heterophily dichotomy and beyond
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characteriz- ing graph datasets for node classification: Homophily-heterophily dichotomy and beyond. In Advances in Neural Information Processing Systems, volume 36, pages 523–548, 2023. 1, 2, 3, 5
work page 2023
-
[1]
Sitao Luan, Chenqing Hua, Qincheng Lu, Liheng Ma, Lirong Wu, Xinyu Wang, Minkai Xu, Xiao-Wen Chang, Doina Precup, Rex Ying, et al. The heterophilic graph learning hand- book: Benchmarks, models, theoretical analysis, applications and challenges. arXiv preprint arXiv:2407.09618, 2024. 1
arXiv 2024
-
[2]
Be- yond homophily in graph neural networks: Current limitations and effective designs
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33:7793–7804, 2020. 1, 2
work page 2020
-
[3]
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022
work page 2022
-
[4]
Revisiting heterophily for graph neural networks
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wen Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in Neural Information Processing Systems, 35:1362–1375, 2022. 3
work page 2022
-
[5]
A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? 2023
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? 2023. 1, 12, 22
work page 2023
-
[7]
Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In International Conference on Machine Learning, pages 21–29. PMLR, 2019. 2
work page 2019
-
[8]
Geom-GCN: Geo- metric graph convolutional networks
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geo- metric graph convolutional networks. In International Conference on Learning Representations,
Show all 27 references
-
[9]
Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887–20902, 2021. 2
2021
-
[10]
Mark E.J. Newman. Mixing patterns in networks. Physical review E, 67(2), 2003. 2, 12
2003
-
[11]
What is missing in homophily? Disentangling graph homophily for graph neural networks
Yilun Zheng, Sitao Luan, and Lihui Chen. What is missing in homophily? Disentangling graph homophily for graph neural networks. arXiv preprint arXiv:2406.18854, 2024. 3
2024 arXiv
-
[12]
When do graph neural networks help with node classification? In- vestigating the homophily principle on node distinguishability
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang, Jie Fu, Jure Leskovec, and Doina Precup. When do graph neural networks help with node classification? In- vestigating the homophily principle on node distinguishability. Advances in Neural Information...
2024
-
[13]
Graph database repository for graph based pattern recognition and machine learning
Kaspar Riesen and Horst Bunke. Graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition, 2008. 3, 13
2008
-
[14]
Good classification measures and how to find them
Martijn Gösgens, Anton Zhiyanov, Aleksey Tikhonov, and Liudmila Prokhorenkova. Good classification measures and how to find them. In Advances in Neural Information Processing Systems, volume 34, pages 17136–17147, 2021. 9
2021
-
[15]
Higher-order homophily on simplicial complexes
Arnab Sarker, Natalie Northrup, and Ali Jadbabaie. Higher-order homophily on simplicial complexes. Proceedings of the National Academy of Sciences, 121(12), 2024. 9
2024
-
[16]
On the inadequacy of nominal assortativity for assessing homophily in networks
Fariba Karimi and Marcos Oliveira. On the inadequacy of nominal assortativity for assessing homophily in networks. Scientific Reports, 13(1):21053, 2023. 12
2023
-
[17]
Lee Giles, Kurt D
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. CiteSeer: An automatic citation indexing system. In Proceedings of the third ACM conference on Digital libraries, pages 89–98, 1998. 22
1998
-
[18]
Automating the construction of internet portals with machine learning
Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127–163, 2000. 10 Revisiting Graph Homophily Measures
2000
-
[19]
Collective classification in network data
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. AI magazine, 29(3):93–93, 2008
2008
-
[20]
Query-driven active surveying for collective classification
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and U Edu. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, volume 8, page 1, 2012
2012
-
[21]
Revisiting semi-supervised learning with graph embeddings
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning , pages 40–48. PMLR, 2016. 22
2016
-
[22]
Pitfalls of graph neural network evaluation
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. In Relational Representation Learning Workshop,
-
[23]
Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models
Benedek Rozemberczki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1325–1334, 2020. 22
2020
-
[24]
Multi-scale attributed node embedding
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2), 2021. 22
2021
-
[25]
Social influence analysis in large-scale networks
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 807–816, 2009. 22
2009
-
[26]
GraphSAINT: Graph sampling based inductive learning method
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020. 22
2020
-
[27]
1 4 1 4 1 4 1 4 # , L 2 =
Derek Lim and Austin R. Benson. Expertise and dynamics within crowdsourced musical knowledge curation: A case study of the genius platform. In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 373–384, 2021. 22 11 Revisiting Graph Homop...
2021
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.