{"id":"dcde9bed-49ce-460e-8671-f54b83347ed8","arxiv_id":"2412.09663","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":1,"one_line_summary":"A new 'unbiased homophily' measure satisfies all five previously proposed reliability axioms for undirected graphs, and an impossibility proof shows no such measure exists for directed graphs.","lead":"Homophily measures score how much a network's edges connect similar nodes, but existing scores disagree and are biased by class imbalance. This paper introduces 'unbiased homophily', a new score proven to satisfy every proposed reliability property for undirected graphs, and shows that for directed graphs no perfect score can exist.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Directed impossibility is only proven for edge-wise scale-invariant measures; the Appendix I extension sketch to arbitrary measures is invalid, so the abstract's unconditional 'no directed measure can satisfy all properties' claim is unsupported.","rationale":"The central undirected construction (Theorem 5.1) is correct: I hand-checked the proofs of maximal/minimal agreement, constant baseline, both monotonicities, empty-class tolerance, class symmetry, and continuity for h^α_unb with α>0. The α=0 recommendation is honestly caveated in Theorem 5.2 and Table 2, though the abstract overstates it; this is a wording issue, not a mathematical flaw. The weakest point is the directed section. The paper's abstract and conclusion claim an unconditional impossibility for all directed homophily measures, but the actual proof in Appendix I is confined to edge-wise, scale-invariant measures. The 'sketch' for non-edge-wise measures makes the unjustified step of treating a normalized class-adjacency matrix as if it determined the measure's value; constant baseline only pins down h on randomized graphs. Since the directed claim is prominent in the paper's stated contributions, this overclaim is load-bearing. It does not undermine the undirected existence result, so the reader's CONDITIONAL verdict remains appropriate: the paper should be accepted only if the claims are restricted or the extension is made rigorous.","tokens_in":21648,"tokens_out":20278,"duration_ms":193967,"concrete_test":"Take the two 4-class directed graphs G_K and G_L from Proposition I.1 and their configuration-model randomizations. Define a non-edge-wise measure h by h(G) = -1 for every graph with all edges heterophilic, h(rand(G)) = 0 for every randomized graph, and h(G_L) = 0 (or any value > -1) for graphs with at least one homophilic edge; verify that this h satisfies the formal properties restricted to these witnesses. If such an h exists, the Appendix I extension sketch fails and the directed impossibility must be restricted to edge-wise scale-invariant measures. This is a deterministic check on the definitions, requiring no computation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Appendix I proves Proposition I.1 (constant baseline contradicts minimal agreement) and Proposition I.2 (constant baseline contradicts hetero-monotonicity) for edge-wise, scale-invariant directed measures. The paper then claims the same examples work for any measure, but the argument is a sketch and it is not valid as written. The contradiction relies on the implication 'C = rand(C) implies h(C) = Rbase'. For an edge-wise measure this follows from constant baseline because h is a function of C alone. For a general measure, constant baseline constrains h on randomized graphs (or on expected class-adjacency matrices), not on an arbitrary deterministic realization whose normalized class matrix happens to be a fixed point of rand. The graphs with matrices K and L in Proposition I.1 are fully specified only up to their class adjacency matrices; a non-edge-wise measure can assign h(G_K) = Rmin (minimal agreement) and h(rand(G_K)) = Rbase (constant baseline) with no contradiction. Thus the abstract's statement 'we prove that some desirable properties contradict each other and thus a measure satisfying all of them cannot exist' is unproven for non-edge-wise measures. The formal theorems in the paper should be explicitly restricted to the edge-wise scale-invariant class, or the extension must be given a rigorous definition of constant baseline for arbitrary measures and a valid proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":1302,"tokens_out":2195,"duration_ms":191156,"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":[{"comment":"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.","section":"Appendix I, subsection 'Not necessarily edge-wise scalar-invariant measures'"}],"minor_comments":[{"comment":"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.","section":"Table 2"},{"comment":"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.","section":"Appendix E, homo-monotonicity proof"},{"comment":"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":"Appendix D, constant baseline verification"},{"comment":"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.","section":"Section 6.2"},{"comment":"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.","section":"Abstract and Section 5.2"},{"comment":"There is a typo in the title: 'Ajusted' should be 'Adjusted'.","section":"Appendix F title"},{"comment":"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.","section":"Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The undirected contribution is strong and likely correct; the main obstacle is the overclaimed directed impossibility for non-edge-wise measures. Restricting the formal claims to the edge-wise scale-invariant class would be a straightforward fix and would still match the paper's stated motivation via classification measures (the correspondence with [14]). No concerns about novelty or citation ethics; the relationship to [6] is transparent."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing to know: the undirected half of this paper is good and likely citable. The authors construct unbiased homophily h_unb, prove it satisfies all five (plus continuity and class symmetry) properties for α>0, and give a clean formula with an equivalent closed form. The proofs in Appendix E are hand-checkable and correct. They also show convincingly that existing measures fail the axioms, and the empirical section makes the practical case. This resolves the open question from Platonov et al. in the positive direction for undirected graphs. The α=0 version has a rare special case (at most one class with intra-edges) where minimal agreement and monotonicity fail; the paper states this in Theorem 5.2 and Table 2, though the abstract oversells it slightly.\n\nSecond thing: the directed impossibility is only proved for edge-wise, scale-invariant measures. The Appendix I propositions are fine for that class. But the 'Not necessarily edge-wise' subsection is a sketch, and as written it doesn't go through. For a general measure, constant baseline constrains h on randomized graphs, not on arbitrary graphs whose normalized class matrix happens to equal rand(C). A non-edge-wise measure can assign Rmin to the fully heterophilic graph K and Rbase to rand(K), with no contradiction. So the abstract's unconditional claim that 'a measure satisfying all of them cannot exist' is unsupported. The authors should either restrict the statement explicitly to edge-wise scale-invariant measures or give a rigorous definition of constant baseline for arbitrary measures and a real proof. This is a substantive flaw in the paper's framing, not a nitpick.\n\nAlso minor: the abstract says 'all the desirable properties' without the α>0 qualifier until Theorem 5.2; readers will catch it but it should be fixed.\n\nBottom line: the undirected construction is a real contribution and deserves to be published after the directed claims are corrected. I'd send it to review.","headline":"Solid, useful undirected homophily construction with a correct proof; the directed impossibility claim is overreaching beyond the edge-wise setting.","tokens_in":22424,"tokens_out":2280,"would_cite":true,"duration_ms":20761,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C82","68R10"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["graph homophily","homophily measures","unbiased homophily","class adjacency matrix","constant baseline","directed graphs","graph neural networks","assortativity"],"falsifier":"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.","tokens_in":21433,"feed_emoji":"🕸️","tokens_out":5738,"duration_ms":52168,"temperature":0.7,"pith_summary":"This paper answers an open question about how to measure homophily, the tendency of edges to connect similarly labeled nodes. Earlier measures (edge, node, class, and adjusted homophily) each fail at least one of five properties that a reliable measure should have, and they often disagree about which graph is more homophilic. The paper introduces unbiased homophily, $h_{\\mathrm{unb}}$, which satisfies all five properties plus continuity and class symmetry on undirected and weighted graphs, with limiting values of 1 for fully homophilic graphs, 0 for label-independent graphs, and $-1$ for fully heterophilic graphs. For directed graphs, it proves the properties are mutually inconsistent, so no measure can have all of them. If correct, the result gives researchers a defensible default measure for comparing homophily across datasets with different numbers of classes and different class-size balances.","feed_headline":"Unbiased homophily passes all five axioms for measuring homophily","feed_subtitle":"It fixes cross-dataset comparisons; for directed graphs, no such measure can exist.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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. "],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the five desirable properties and the open question about whether any homophily measure can satisfy all of them.","marker":"[6]"},{"why":"Defines the assortativity coefficient that equals adjusted homophily, the strongest prior measure whose lack of monotonicity motivates the new construction.","marker":"[10]"},{"why":"Introduces edge homophily, one of the existing measures that the paper shows to be inconsistent with other measures.","marker":"[2]"},{"why":"Introduces node homophily, another existing measure shown to fail constant baseline.","marker":"[8]"},{"why":"Introduces class homophily, shown to fail empty class tolerance and other properties.","marker":"[9]"},{"why":"Proposes adjusted nominal assortativity to handle class imbalance, which the paper proves still fails the desirable properties.","marker":"[16]"},{"why":"Establishes the correspondence between directed edge-wise homophily measures and classification evaluation measures, motivating the directed analysis.","marker":"[14]"}],"fun_headline_variants":["Unbiased homophily: first to satisfy all five properties","New homophily measure works across class counts and balances","For undirected graphs, unbiased homophily passes all tests","Unbiased homophily: undirected works, directed impossible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Unbiased homophily: first to satisfy all five properties","New homophily measure works across class counts and balances","For undirected graphs, unbiased homophily passes all tests","Unbiased homophily: undirected works, directed impossible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001185,"raw_usage":{"total_tokens":4939,"prompt_tokens":1040,"completion_tokens":3899,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":656,"completion_tokens_details":{"reasoning_tokens":3838}},"tokens_in":656,"tokens_out":3899,"duration_ms":27596,"temperature":1.0,"reasoning_tokens":3838,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T17:06:33.256540+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Characteriz- ing graph datasets for node classification: Homophily-heterophily dichotomy and beyond","cited_arxiv_id":null,"evidence_quote":"Supplies the five desirable properties and the open question about whether any homophily measure can satisfy all of them."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the assortativity coefficient that equals adjusted homophily, the strongest prior measure whose lack of monotonicity motivates the new construction."},{"cited_title":"Be- yond homophily in graph neural networks: Current limitations and effective designs","cited_arxiv_id":null,"evidence_quote":"Introduces edge homophily, one of the existing measures that the paper shows to be inconsistent with other measures."},{"cited_title":"Geom-GCN: Geo- metric graph convolutional networks","cited_arxiv_id":null,"evidence_quote":"Introduces node homophily, another existing measure shown to fail constant baseline."},{"cited_title":"Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods","cited_arxiv_id":null,"evidence_quote":"Introduces class homophily, shown to fail empty class tolerance and other properties."},{"cited_title":"On the inadequacy of nominal assortativity for assessing homophily in networks","cited_arxiv_id":null,"evidence_quote":"Proposes adjusted nominal assortativity to handle class imbalance, which the paper proves still fails the desirable properties."},{"cited_title":"Good classification measures and how to find them","cited_arxiv_id":null,"evidence_quote":"Establishes the correspondence between directed edge-wise homophily measures and classification evaluation measures, motivating the directed analysis."}],"review_version":1}