{"id":"0a91c967-5bef-4bd7-b2c7-b188f91375bc","arxiv_id":"2506.17316","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"A generalized graph GOSPA metric family with tunable edge-mismatch penalties is proved to be a metric and is approximated by linear programming.","lead":"This paper defines a family of distance functions for comparing graphs with different numbers of nodes, generalizing the earlier graph GOSPA metric by adding separate penalties for three kinds of edge mismatch. The authors prove the triangle inequality for the exact metric, give a linear-programming approximation, and test the distance on graph classification benchmarks.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The triangle-inequality proof for Definition 2 has a false inequality at Eq. (41), so the central metric claim is not established as printed.","rationale":"The reader's weakest_assumption focuses on the LP relaxation being used as a proxy for the exact metric, which is a legitimate concern for the experimental claims. However, the paper's primary mathematical contribution is the exact metric family in Definition 2, and the appendix's Eq. (41) contains an inequality in the wrong direction. That makes the metric property unproven as printed, which is logically prior to any question of whether the relaxed LP is a faithful proxy. I therefore locate the load-bearing risk in the proof of the central claim rather than in the approximation gap. The concern is testable: an exhaustive exact check on small graphs can distinguish a false theorem from a fixable proof bug. If the check passes, the appropriate verdict remains conditional: the authors should correct the proof and also report exact versus relaxed LP gaps or variance in the empirical comparisons. If the check fails, the metric claim would need to be withdrawn or restricted. Because the reader already noted the invalid Eq. (41) in the rationale even though the formal weakest_assumption was the LP gap, my agreement is partial rather than full.","tokens_in":20604,"tokens_out":11201,"duration_ms":113716,"concrete_test":"Enumerate all triples of graphs with up to 4 nodes and node attributes from a small finite set (e.g., {0,1}^2), with p in {1,2}, c and epsilon in {0.5, 1, 2}, and beta, eta in {0.25, 0.5, 0.75, 1} with beta <= eta, computing the exact integer metric in Definition 2 by brute force over all assignment matrices. If any triple violates d(X,Y) <= d(X,Z) + d(Z,Y), the metric claim is false; if the full enumeration shows no violation, the Eq. (41) step is likely a fixable proof error rather than a false theorem.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The most load-bearing concern is not the LP relaxation but the proof of the central metric claim. In Appendix A, Eq. (41) asserts c^p/2 (|X|+|Y|-2|gamma_XY|) <= c^p/2 (|X|+|Y|-2|gamma_XZ|-2|gamma_ZY|). But because gamma_XZ = gamma^0_XZ union gamma^1_XZ and gamma_ZY = gamma^0_ZY union gamma^1_ZY with |gamma_XY| = |gamma^1_XZ| = |gamma^1_ZY|, one has |gamma_XZ|+|gamma_ZY| = |gamma_XY| + |gamma^0_XZ| + |gamma^0_ZY| >= |gamma_XY|. Therefore the right-hand side of the displayed inequality is smaller than the left, not larger, unless both gamma^0 sets are empty, which is not assumed. This step is the only place where the composed assignment is reconciled with the two unassignment cardinalities, so inequality (37) is not established. Since Definition 2's headline contribution is that d(.,.) is a metric and Appendix A is the only proof, the central claim is unproven as written. A separate, real issue is that the relaxed LP used in all experiments is admitted in Section III-E3 not to be a metric, but the exact metric property is logically prior.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a family of graph GOSPA metrics, generalizing the graph GOSPA metric of [19] to a wider range of edge-mismatch penalties controlled by hyperparameters β and η. The metric is defined in Definition 2 as the p-th root of an optimization over node assignments, combining node attribute costs, unassignment costs, and three types of edge mismatch costs. The paper claims the family satisfies the metric axioms, provides an equivalent assignment-matrix formulation, derives an integer linear programming form, and then relaxes it to a linear program that is used in all experiments. Simulation experiments illustrate the effect of β and η, and classification experiments on MUTAG, Letter, and PTC datasets report improved KNN accuracy relative to graph GOSPA, GCD, and GED.","tokens_in":20905,"tokens_out":17632,"duration_ms":166113,"significance":"If the metric claim is established, the family is a useful and interpretable extension of graph GOSPA: it allows separate penalties for assigned-assigned, assigned-unassigned, and unassigned-unassigned edge mismatches while retaining the assignment-based structure that permits LP-based computation. The paper is self-contained, the definitions are clear, and the matrix formulation appears internally consistent. The main theoretical contribution is the triangle-inequality proof in Appendix A; the main empirical contribution depends on the relaxed LP being a faithful proxy for the exact metric. Both points need attention before the results can be taken as stated.","major_comments":[{"comment":"The chain in Eq. (41) contains a false inequality. The paper asserts c^p/2 (|X|+|Y|-2|γXY|) ≤ c^p/2 (|X|+|Y|-2|γXZ|-2|γZY|). Since |γXZ| = |γ^1_XZ| + |γ^0_XZ|, |γZY| = |γ^1_ZY| + |γ^0_ZY|, and |γXY| = |γ^1_XZ| = |γ^1_ZY|, the right-hand side equals c^p/2(|X|+|Y|-4|γXY|-2|γ^0_XZ|-2|γ^0_ZY|), which is smaller than the left-hand side unless the γ^0 sets are empty. This is exactly the step that reconciles the unassignment counts, so inequality (37) is not established by the printed argument. The defect is repairable: because the Z-nodes used by γ^1_XZ and γ^1_ZY coincide and are disjoint from the Z-nodes used by γ^0_XZ and γ^0_ZY, one has |Z| ≥ |γXY|+|γ^0_XZ|+|γ^0_ZY|, and adding the nonnegative term 2(c^p/2)(|Z|-|γXY|-|γ^0_XZ|-|γ^0_ZY|) converts the false middle expression into the sum of the two GOSPA cardinality terms in (37). This corrected argument should be written out explicitly; as printed, the central triangle-inequality proof is invalid.","section":"Appendix A-A, Eq. (41)"},{"comment":"All simulation and classification results are computed with the relaxed LP, which Section III-E3 states is only a lower bound and in general does not satisfy the triangle inequality. The paper provides no relaxation-gap analysis, no integrality check, and no evidence that the relaxed values coincide with or are close to the exact metric d(·,·) of Definition 2 for the graphs used. Consequently Figures 2-3 and Tables I-II describe the relaxation, not necessarily the proposed metric family. This is load-bearing for the claims of improved flexibility and classification performance; the authors should either compute or bound the gap, or explicitly restrict the empirical claims to the approximation.","section":"Sections III-E3 and IV-A"}],"minor_comments":[{"comment":"Definition 2 requires 0<β≤η≤1, which excludes β=0, but the text after Eq. (3) and Section IV-B state that graph GOSPA is recovered with β=0, η=1/2 and that β is sampled from [0,1]. Please align the admissible range, either by allowing β=0 or by treating graph GOSPA as a limit, and check that the metric proof and LP nonnegativity condition cover the boundary case.","section":"Definition 2"},{"comment":"The third displayed line of Eq. (46) contains a typographical artifact 'β/2 β ε^p'; this should presumably read '(β/2)ε^p'.","section":"Appendix A-B, Eq. (46)"},{"comment":"The statement that the relaxed version 'does not meet the triangle inequality in general, as has been checked via simulations' is justified only by simulation; a concrete counterexample or a proof would be more appropriate for a mathematical claim.","section":"Section III-E3"}],"recommendation":"major_revision","confidential_remarks":"The paper has a sound and useful core, and the proof gap in Appendix A-A appears repairable with a short disjointness argument, so I would not reject on that basis. However, the revision must contain a corrected proof and should address the gap between the exact metric and the relaxed LP used in all experiments, ideally with an exact-versus-relaxed comparison on at least a subset of graphs. The novelty relative to graph GOSPA is incremental but is sufficient for the venue if the metric theorem is properly established."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a real but incremental extension of graph GOSPA, giving users a three-way control over edge-mismatch penalties. The metric claim is very likely true, but the printed proof in Appendix A has a wrong-direction bound in Eq. (41), and the experiments all use the relaxed LP lower bound, which is not a metric. Both are fixable, and the paper deserves serious peer review.\n\nThe genuinely new piece is Definition 2's edge cost: assigned-assigned, half-assigned, and unassigned-unassigned mismatches get separate coefficients, and the parameter range 0<β≤η≤1 is covered by the metric proof. That proof is self-contained and does not assume the conclusion. The LP formulation is also a real contribution, and the authors are honest that the relaxation is only a lower bound.\n\nThe stress-test note is correct about Eq. (41). The chain there bounds |X|+|Y|-2|γ_XY| above by the corresponding triangle terms, but a direct composition argument gives the opposite relation when the γ^0 sets are nonempty. So the printed appendix does not establish (37). That said, a referee can see how to repair it — split the unassigned counts by how they map through Z, and the inequality goes through. I would ask for the corrected proof rather than reject.\n\nThe empirical sections have a second issue, proportionate but real: all simulation and classification numbers come from the relaxed LP, which Section III-E3 says is generally not a metric and violates the triangle inequality. There's no relaxation-gap study and no integrality check, so the curves in Figures 2 and 3 and the accuracy in Table II describe the approximation, not necessarily the exact family. No code is released, and the classification gains over graph GOSPA are small enough that I'd want error bars or repeated train/test splits before trusting them.\n\nWho this is for: people working on graph distances and graph matching, especially those who use GOSPA-style assignment metrics. It's a subfield paper, but a meaningful one. I'd cite it only after the proof is corrected and the experiments are tightened.\n\nRecommendation: send to peer review with a request to fix Eq. (41) and add a relaxation-gap or integrality analysis. The core idea is sound.","headline":"Genuine but incremental metric-family work whose printed triangle-inequality proof has a fixable gap; deserves peer review after a corrected proof and a relaxation-gap check.","tokens_in":21458,"tokens_out":3083,"would_cite":false,"duration_ms":31010,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C12","68R10","90C35","90C05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper defines a family of true metrics for undirected, attributed graphs of different sizes, with tunable penalties for node and edge mismatches, and proves the triangle inequality for the family.","keywords":["graph matching","graph metrics","generalised optimal sub-pattern assignment (GOSPA)","linear programming","different-size graphs","edge mismatch penalties","graph classification","assignment matrices"],"falsifier":"Compute both the exact integer LP and its relaxed LP lower bound on small random graphs (e.g., 10 nodes) with $\\beta > 0$, and compare the two values and the fraction of fractional solutions; also test whether the relaxed values violate the triangle inequality on random triples. If the gap is frequently nonzero or the triangle inequality fails often on values used in the experiments, then the classification and simulation results describe the approximation, not the proposed metric family.","tokens_in":20414,"feed_emoji":"📐","tokens_out":6866,"duration_ms":65829,"temperature":0.7,"pith_summary":"This paper tries to establish that there is a whole family of metrics for undirected, attributed graphs of different sizes, parameterized by penalties for node mismatches, unassigned nodes, and three kinds of edge mismatch. The family generalizes the graph GOSPA metric by adding a separate tunable penalty for edges whose both endpoints are unassigned and by letting the half-assigned-edge penalty range freely, while still satisfying identity, symmetry, and the triangle inequality. A sympathetic reader would care because a provable metric with decomposable costs makes 'how different are these two graphs' a question with an interpretable, principled answer, useful for classification and error analysis. The paper also argues that the exact metric can be approximated by solving a linear program, at the price that the relaxed values are only a lower bound and generally not a metric.","feed_headline":"Graphs of different sizes now have a provable, tunable distance","feed_subtitle":"Three edge-mismatch penalties make distances interpretable, and linear programming keeps them computable.","key_machinery":"The load-bearing object is the assignment matrix $W$ with a dummy row and column (Lemma 1), which turns the combinatorial assignment set into a binary matrix satisfying row and column sum constraints. The edge cost $e^p_{X,Y}(W)$ is the mechanism that carries the metric: its three terms assign weights $\\epsilon^p$, $\\eta \\epsilon^p$, and $\\beta \\epsilon^p$ to assigned-assigned, assigned-unassigned, and unassigned-unassigned edge mismatches, and the condition $0 < \\beta \\le \\eta \\le 1$ is exactly what makes the triangle-inequality proof's term-by-term comparisons go through. The proof itself chains assignments through an intermediate graph $Z$ and splits the inequality into a localization part and an edge part, then combines them with Minkowski's inequality, so the whole metric family rests on that decomposition.","core_discovery":"For hyperparameters $c>0$, $1 \\le p < \\infty$, $\\epsilon > 0$, and $0 < \\beta \\le \\eta \\le 1$, the paper defines $d(X,Y)$ as the $p$-th root of the minimum over node assignments of assigned-node attribute distances, a $(c^p/2)$-penalty per unassigned node, and an edge mismatch term $e_p(\\gamma)$ with three cost levels: $\\epsilon^p$ per assigned-assigned edge mismatch, $\\eta \\epsilon^p$ per half-assigned edge, and $\\beta \\epsilon^p$ per unassigned-unassigned edge. The paper claims this expression is a metric on the space of undirected graphs with node attributes and different sizes, with identity and symmetry immediate and the triangle inequality proved in the appendix by composing optimal assignments through an intermediate graph and applying Minkowski's inequality. It further claims the minimization can be written as a binary quadratic program, linearized via Glover's method into an integer linear program, and relaxed to a fast LP lower bound; the relaxed version is not a metric in general, except at $\\beta = 0$, $\\eta = 1/2$, where it reduces to the LP relaxation of graph GOSPA. Simulation and real-data experiments illustrate the decomposition and show KNN classification accuracy at least matching and sometimes exceeding graph GOSPA, GCD, and GED on MUTAG, Letter, and PTC female-mice data.","pith_inferences":["We infer that the $\\beta$ and $\\eta$ sliders turn the metric into a tunable surrogate for application-specific structural cost: raising $\\beta$ punishes clutter of disconnected unassigned subgraphs, while raising $\\eta$ punishes dangling half-edges, letting practitioners encode prior knowledge without leaving the metric family.","A natural testable extension is to measure the relaxation gap directly on small random graphs by comparing exact integer LP values with the relaxed LP lower bound; if the gap stays small in practice, the cheap relaxed version can be trusted in large-scale experiments.","The same chained-assignment proof might extend to directed and weighted graphs if the absolute adjacency difference is replaced by a metric on edge attributes, though the paper only proves the undirected unweighted case.","Because the relaxed LP requires $\\eta \\ge 1/2$ for nonnegativity, the experimentally accessible parameter region excludes the lower half of the metric's allowed $\\eta$ range; exact computation would be needed to explore $0 < \\eta < 1/2$ behavior."],"forward_implications":["For any valid hyperparameters, users get a true metric whose value splits into five interpretable error types: assigned-node attribute error, missed nodes, false nodes, assigned edge mismatches, and the partial or unassigned edge mismatch classes.","The graph GOSPA metric is exactly the boundary case $\\beta = 0$, $\\eta = 1/2$, so methods built on graph GOSPA can be retuned continuously within the family without leaving metric space.","The integer LP formulation is exact, so on small graphs the metric can be computed to optimality; on larger graphs the relaxed LP gives a polynomial-time lower bound and coincides with the exact value whenever its solution happens to be integral.","Because the relaxed LP is not a metric away from the graph GOSPA boundary, using it as a plug-in distance in algorithms that assume the triangle inequality requires checking integrality or explicitly accepting approximation error.","The reported classification gains on the PTC (FM) dataset suggest that the extra $\\beta$ and $\\eta$ degrees of freedom matter most when structure beyond node attributes carries class information."],"supporting_citations":[{"why":"Defines the graph GOSPA metric that the proposed family generalizes and whose LP relaxation is the one special case that remains a metric.","marker":"[19]"},{"why":"Introduces the GOSPA set metric, supplying the node-assignment and unassigned-node penalty structure and the Minkowski-inequality step reused in the proof.","marker":"[17]"},{"why":"Provides the assignment-matrix formulation with dummy rows and columns that Lemma 1 uses to write the metric as a matrix optimization.","marker":"[21]"},{"why":"Is the Glover linearisation that converts the binary quadratic program into an integer linear program.","marker":"[24]"},{"why":"Documents the linearisation techniques used to write the integer LP that underlies the approximate computation.","marker":"[25]"},{"why":"Defines the generalised chemical distances used as a baseline, which require padding graphs to equal size and can break the triangle inequality.","marker":"[12]"},{"why":"Introduces assignment-based GTT metrics for attributed graphs that the paper contrasts for having only one edge-mismatch cost.","marker":"[18]"},{"why":"Gives the ADMM implementation of GCDs that pads smaller graphs with dummy nodes, motivating the dummy-node-free LP approach.","marker":"[13]"},{"why":"Establishes NP-hardness of non-convex quadratic programming, used to justify the need for the LP relaxation.","marker":"[23]"}],"fun_headline_variants":["Tunable graph distance proven for graphs of different sizes","Graph metric family with adjustable edge penalties now proven","New GOSPA family: provable distance for unequal graphs","Flexible edge costs in graph distance, now with metric proof","Graph distance with tunable edge mismatch penalties, proven"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The experimental sections compute the fast relaxed linear-programming lower bound rather than the exact integer metric, and the paper states this relaxed version is generally not a metric, so the simulations and classification results assume the lower bound is close enough to the exact metric to be a faithful proxy, with no reported analysis of how large the gap can be.","fun_headline_variants_meta":{"raw":{"variants":["Tunable graph distance proven for graphs of different sizes","Graph metric family with adjustable edge penalties now proven","New GOSPA family: provable distance for unequal graphs","Flexible edge costs in graph distance, now with metric proof","Graph distance with tunable edge mismatch penalties, proven"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000225,"raw_usage":{"total_tokens":1492,"prompt_tokens":1002,"completion_tokens":490,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":618,"completion_tokens_details":{"reasoning_tokens":410}},"tokens_in":618,"tokens_out":490,"duration_ms":5620,"temperature":1.0,"reasoning_tokens":410,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:35:31.337553+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute both the exact integer LP and its relaxed LP lower bound on small random graphs (e.g., 10 nodes) with $\\beta > 0$, and compare the two values and the fraction of fractional solutions; also test whether the relaxed values violate the triangle inequality on random triples. If the gap is frequently nonzero or the triangle inequality fails often on values used in the experiments, then the classification and simulation results describe the approximation, not the proposed metric family.","supporting_citations":[{"cited_title":"Graph GOSPA metric: A metric to measure the discrepancy between graphs of different sizes,","cited_arxiv_id":null,"evidence_quote":"Defines the graph GOSPA metric that the proposed family generalizes and whose LP relaxation is the one special case that remains a metric."},{"cited_title":"A metric on the space of finite sets of trajectories for evaluation of multi-target tracking algorithms,","cited_arxiv_id":null,"evidence_quote":"Provides the assignment-matrix formulation with dummy rows and columns that Lemma 1 uses to write the metric as a matrix optimization."},{"cited_title":"Improved linear integer programming formulations of nonlin- ear integer problems,","cited_arxiv_id":null,"evidence_quote":"Is the Glover linearisation that converts the binary quadratic program into an integer linear program."},{"cited_title":"Theoretical and computational study of several linearisation techniques for binary quadratic problems,","cited_arxiv_id":null,"evidence_quote":"Documents the linearisation techniques used to write the integer LP that underlies the approximate computation."},{"cited_title":"A family of tractable graph metrics,","cited_arxiv_id":null,"evidence_quote":"Defines the generalised chemical distances used as a baseline, which require padding graphs to equal size and can break the triangle inequality."},{"cited_title":"Massively distributed graph distances,","cited_arxiv_id":null,"evidence_quote":"Gives the ADMM implementation of GCDs that pads smaller graphs with dummy nodes, motivating the dummy-node-free LP approach."},{"cited_title":"Quadratic programming with one negative eigenvalue is np-hard,","cited_arxiv_id":null,"evidence_quote":"Establishes NP-hardness of non-convex quadratic programming, used to justify the need for the LP relaxation."}],"review_version":2}