A family of graph GOSPA metrics for graphs with different sizes

\'Angel F. Garc\'ia-Fern\'andez; Jinhao Gu; Lennart Svensson; Robert E. Firth

REVIEW 2 major objections 3 minor 41 references

A family of graph GOSPA metrics for graphs with different sizes

T0 review · 2 major / 3 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2506.17316 v1 pith:VEWNUTBM submitted 2025-06-18 cs.SI cs.LGeess.SP

Jinhao Gu , Ángel F. García-Fernández , Robert E. Firth , Lennart Svensson This is my paper · ORCID

classification cs.SIcs.LGeess.SP MSC 05C1268R1090C3590C05

keywords graphmatchingmetricsgeneralisedoptimalsub-patternassignment(GOSPA)linearprogrammingdifferent-sizegraphsedgemismatchpenaltiesclassificationmatrices

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

The 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.

The 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.

The 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.

Who 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.

Recommendation: send to peer review with a request to fix Eq. (41) and add a relaxation-gap or integrality analysis. The core idea is sound.

Referee Report

2 major / 3 minor

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.

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 (2)

[Appendix A-A, Eq. (41)] 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.
[Sections III-E3 and IV-A] 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.

minor comments (3)

[Definition 2] 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.
[Appendix A-B, Eq. (46)] The third displayed line of Eq. (46) contains a typographical artifact 'β/2 β ε^p'; this should presumably read '(β/2)ε^p'.
[Section III-E3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the metric properties are derived from the definition via Appendix A, not imported from the target result or from fitted inputs.

full rationale

The paper's central claim is that Definition 2 defines a metric. The proof in Appendix A constructs an assignment γXY by composition through Z, splits the localisation and edge costs, and applies Minkowski's inequality together with the parameter ordering 0<β≤η≤1. None of these ingredients assumes the triangle inequality being proved; the argument is self-contained from the definition. The graph GOSPA metric of [19] is cited as a special case (β=0, η=1/2) and as a building block for the LP linearisation, but it is not used to establish the metric property of the new family, so the self-citation is not load-bearing. The hyperparameters c,p,ε,β,η are user-chosen and are not fitted to force the theorem. The LP relaxation in Section III-E3 is explicitly identified as a lower bound that is not a metric in general, so the experiments do not rename an approximation as the exact metric; they evaluate the proposed quantity only through the acknowledged relaxation. The possible inequality-direction issue at Eq. (41) identified by a skeptical reading is a correctness or proof-gap concern, not circularity: a false step in a proof does not mean the claim was assumed as an input. No step in the derivation chain reduces by construction to the result it purports to establish.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The metric theorem holds for all allowed values of c, p, epsilon, beta, eta, so these are not fit parameters for the core mathematical claim. They are listed because the classification experiments tune them by random search and cross-validation, and the beta,eta pair is the paper's main new flexibility. The axioms are standard metric-space and optimization facts plus the stated scope restriction to undirected unweighted graphs.

free parameters (5)

c (unassignment and node location cost) = c=3 in simulations; cross-validated from [1,10] in classification
Hyperparameter in Definition 2; not fitted to prove the metric theorem, but tuned for the empirical claims.
p (exponent) = 1 in all experiments
Hyperparameter in Definition 2; fixed to 1 for the experiments.
epsilon (assigned edge mismatch base cost) = 1 in simulations; cross-validated from [0.1,5] in classification
Hyperparameter controlling edge mismatch penalties; tuned for the empirical claims.
beta (unassigned edge penalty factor) = 0.3 in simulations; sampled from [0,1] in classification
New hyperparameter introduced in this paper; controls unassigned-unassigned edge cost.
eta (half-assigned edge penalty factor) = 0.7 in simulations; sampled from [0,1] in classification
New hyperparameter introduced in this paper; controls assigned-unassigned edge cost.

assumptions (6)

domain assumption The node attribute space X carries a base metric d.
Definition 2 and the localisation-cost part of the triangle inequality proof apply the triangle inequality to node attributes.
standard math Minkowski's inequality holds for p≥1.
Used after Eq. (39) to split the p-th power costs between X-to-Z and Z-to-Y terms.
domain assumption Graphs are finite, undirected, unweighted simple graphs with 0/1 adjacency matrices.
The metric definition and proof use 0/1 adjacency entries and do not treat weighted or directed edges.
standard math The composition of assignments through an intermediate graph is a feasible assignment.
Appendix A constructs gamma_XY from gamma_XZ and gamma_ZY and relies on the induced decomposition of unassigned node sets in Eq. (42).
standard math Glover's linearization correctly converts the binary quadratic program to an integer linear program.
Section III-E2 invokes Glover's method [24] and the survey [25] without reproving the transformation.
standard math Relaxing binary assignment constraints to nonnegativity gives a lower bound.
Section III-E3 uses this standard continuous-relaxation fact to obtain a faster approximate value.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A family of graph GOSPA metrics for graphs with different sizes." pith.science (2026). https://pith.science/paper/VEWNUTBM

@misc{pith2026250617316,
  author       = {Pith},
  title        = {Pith review of: A family of graph GOSPA metrics for graphs with different sizes},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/VEWNUTBM}},
  note         = {Machine review of arXiv:2506.17316}
}

read the original abstract

This paper proposes a family of graph metrics for measuring distances between graphs of different sizes. The proposed metric family defines a general form of the graph generalised optimal sub-pattern assignment (GOSPA) metric and is also proved to satisfy the metric properties. Similarly to the graph GOSPA metric, the proposed graph GOSPA metric family also penalises the node attribute costs for assigned nodes between the two graphs, and the number of unassigned nodes. However, the proposed family of metrics provides more general penalties for edge mismatches than the graph GOSPA metric. This paper also shows that the graph GOSPA metric family can be approximately computed using linear programming. Simulation experiments are performed to illustrate the characteristics of the proposed graph GOSPA metric family with different choices of hyperparameters. The benefits of the proposed graph GOSPA metric family for classification tasks are also shown on real-world datasets.

Figures

Figures reproduced from arXiv: 2506.17316 by the authors.

**Figure 2.** Plots of average graph GOSPA metric family errors, GCD, GED and [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

**Figure 3.** Plots of average graph GOSPA metric family with different hyperpa [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

41 extracted references · 35 canonical work pages

[19]

Graph GOSPA metric: A metric to measure the discrepancy between graphs of different sizes,

J. Gu, A. F. García-Fernández, R. E. Firth, and L. Svensson, “Graph GOSPA metric: A metric to measure the discrepancy between graphs of different sizes,”IEEE Transactions on Signal Processing, vol. 72, pp. 4037–4049, 2024

work page 2024
[1]

Spline-like wavelet filterbanks for multiresolution analysis of graph- structured data,

V. N. Ekambaram, G. C. Fanti, B. Ayazifar, and K. Ramchandran, “Spline-like wavelet filterbanks for multiresolution analysis of graph- structured data,”IEEE Transactions on Signal and Information Process- ing over Networks, vol. 1, no. 4, pp. 268–278, 2015

work page 2015
[2]

Predicting graph signals using kernel regression where the input signal is agnostic to a graph,

A. Venkitaraman, S. Chatterjee, and P. Händel, “Predicting graph signals using kernel regression where the input signal is agnostic to a graph,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 4, pp. 698–710, 2019

work page 2019
[3]

When to make a topic popular again? a temporal model for topic rehotting prediction in online social networks,

C. Wang, X. Xin, and J. Shang, “When to make a topic popular again? a temporal model for topic rehotting prediction in online social networks,” IEEE Transactions on Signal and Information Processing over Networks, vol. 4, no. 1, pp. 202–216, 2018

work page 2018
[4]

The graph neural network model,

F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfar- dini, “The graph neural network model,”IEEE transactions on neural networks, vol. 20, no. 1, pp. 61–80, 2008

2008
[5]

T. M. Apostol,Mathematical Analysis. Addison Wesley, 1974

work page 1974
[6]

Agraphdistancemetricbasedonthemaximal common subgraph,

H.BunkeandK.Shearer,“Agraphdistancemetricbasedonthemaximal common subgraph,”Pattern recognition letters, vol. 19, no. 3-4, pp. 255–259, 1998

work page 1998
[7]

A distance measure between attributed relational graphs for pattern recognition,

A. Sanfeliu and K.-S. Fu, “A distance measure between attributed relational graphs for pattern recognition,”IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-13, no. 3, pp. 353–362, 1983

work page 1983

Show all 41 references

[8]

A binary linear programming formulation of the graph edit distance,

D. Justice and A. Hero, “A binary linear programming formulation of the graph edit distance,”IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 28, no. 8, pp. 1200–1214, 2006

2006
[9]

Approx- imation of graph edit distance based on Hausdorff matching,

A. Fischer, C. Y. Suen, V. Frinken, K. Riesen, and H. Bunke, “Approx- imation of graph edit distance based on Hausdorff matching,”Pattern Recognition, vol. 48, no. 2, pp. 331–343, 2015

2015
[10]

Graph edit distance optimizedwithgreedyalgorithmforsimilaritysearchinbusinessprocess graphs,

S. Saadah, M. F. E. Saputro, and K. R. S. Wiharja, “Graph edit distance optimizedwithgreedyalgorithmforsimilaritysearchinbusinessprocess graphs,” in2020 International Conference on Data Science and Its Applications (ICoDSA), 2020, pp. 1–7

2020
[11]

Reaction and chemical distances and reaction graphs,

V. Kvasnička, J. Pospíchal, and V. Baláž, “Reaction and chemical distances and reaction graphs,”Theoretica chimica acta, vol. 79, no. 1, pp. 65–79, 1991

1991
[12]

A family of tractable graph metrics,

J. Bento and S. Ioannidis, “A family of tractable graph metrics,”Applied Network Science, vol. 4, no. 107, 2019

2019
[13]

Massively distributed graph distances,

A. Moharrer, J. Gao, S. Wang, J. Bento, and S. Ioannidis, “Massively distributed graph distances,”IEEE Transactions on Signal and Informa- tion Processing over Networks, vol. 6, pp. 667–683, 2020

2020
[14]

Distributed optimization and statistical learning via the alternating direction method of multipliers,

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,”Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1–125, 2011

2011
[15]

A new metric between distributions of point processes,

D. Schuhmacher and A. Xia, “A new metric between distributions of point processes,”Advances in applied probability, vol. 40, no. 3, pp. 651–672, 2008

2008
[16]

Metrics and barycenters for point pattern data,

R. Müller, D. Schuhmacher, and J. Mateu, “Metrics and barycenters for point pattern data,”Statistics and Computing, vol. 30, pp. 953–972, 2020

2020
[17]

Gen- eralized optimal sub-pattern assignment metric,

A. S. Rahmathullah, A. F. García-Fernández, and L. Svensson, “Gen- eralized optimal sub-pattern assignment metric,” in20th International Conference on Information Fusion, 2017, pp. 1–8

2017
[18]

Assignment based metrics for attributed graphs,

D. Schuhmacher and L. C. Wirth, “Assignment based metrics for attributed graphs,”arXiv preprint arXiv:2308.12165, 2023. 9

2023 arXiv
[20]

Nearest neighbor pattern classification,

T. Cover and P. Hart, “Nearest neighbor pattern classification,”IEEE transactions on information theory, vol. 13, no. 1, pp. 21–27, 1967

1967
[21]

A metric on the space of finite sets of trajectories for evaluation of multi-target tracking algorithms,

A. F. García-Fernández, A. S. Rahmathullah, and L. Svensson, “A metric on the space of finite sets of trajectories for evaluation of multi-target tracking algorithms,”IEEE Transactions on Signal Processing, vol. 68, pp. 3917–3928, 2020

2020
[22]

A metric for sets of trajectories that is practical and mathematically consistent,

J. Bento and J. J. Zhu, “A metric for sets of trajectories that is practical and mathematically consistent,”arXiv preprint arXiv:1601.03094, 2016

2016 arXiv
[23]

Quadratic programming with one negative eigenvalue is np-hard,

P. M. Pardalos and S. A. Vavasis, “Quadratic programming with one negative eigenvalue is np-hard,”Journal of Global optimization, vol. 1, no. 1, pp. 15–22, 1991

1991
[24]

Improved linear integer programming formulations of nonlin- ear integer problems,

F. Glover, “Improved linear integer programming formulations of nonlin- ear integer problems,”Management science, vol. 22, no. 4, pp. 455–460, 1975

1975
[25]

Theoretical and computational study of several linearisation techniques for binary quadratic problems,

F. Furini and E. Traversi, “Theoretical and computational study of several linearisation techniques for binary quadratic problems,”Annals of Operations Research, vol. 279, pp. 387–411, 2019

2019
[26]

D. G. Luenberger and Y. Ye,Linear and Nonlinear Programming. Springer Publishing Company, Incorporated, 2015

2015
[27]

RDKit: Open-source cheminformatics

“RDKit: Open-source cheminformatics.” 2010. [Online]. Available: https://www.rdkit.org/

2010
[28]

Exploring network structure, dynamics, and function using NetworkX,

A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using NetworkX,” inProceedings of the 7th Python in Science Conference, G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11–15

2008
[29]

and A. Rényi, “On random graphs I,

P. Erdös" and A. Rényi, “On random graphs I,”Publ. math. debrecen, vol. 6, no. 290-297, p. 18, 1959

1959
[30]

Exploring network structure, dynamics, and function using networkx,

A. A. Hagberg, D. A. Schult, and P. J. Swart, “Exploring network structure, dynamics, and function using networkx,” inProceedings of the 7th Python in Science Conference, G. Varoquaux, T. Vaught, and J. Millman, Eds., Pasadena, CA USA, 2008, pp. 11 – 15

2008
[31]

Tudataset: A collection of benchmark datasets for learning with graphs,

C. Morris, N. M. Kriege, F. Bause, K. Kersting, P. Mutzel, and M. Neumann, “Tudataset: A collection of benchmark datasets for learning with graphs,” inICML 2020 Workshop on Graph Representation Learning and Beyond (GRL+ 2020), 2020. [Online]. Available: www.graphlearning.io

2020
[32]

Iam graph database repository for graph basedpatternrecognitionandmachinelearning,

K. Riesen and H. Bunke, “Iam graph database repository for graph basedpatternrecognitionandmachinelearning,”inStructural,Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings. Springer,...

2008
[33]

The predictive toxicology challenge 2000–2001,

C. Helma, R. D. King, S. Kramer, and A. Srinivasan, “The predictive toxicology challenge 2000–2001,”Bioinformatics, vol. 17, no. 1, pp. 107–108, 2001

2000
[34]

C. S. Kubrusly,Elements of operator theory. Springer, 2011. 10 Supplementary material: A family of graph GOSPA metrics for graphs with different sizes Appendix A In this appendix, we give the proof of the triangle inequality of the graph GOSPA metric family in (2). We can writ...

2011
[35]

The first one is the proof of the triangle inequality for the localisation cost (including missed and false nodes). That is, we want X (i,j)∈γXY dp (xi,yj) +cp 2 (|X|+|Y|−2|γ XY|) ≤ X (i,k)∈γ 1 XZ,(k,j)∈γ 1 ZY (d(xi,zk) +d(z k,yj))p + X (i,k)∈γ 0 XZ dp (xi,zk) + X (k,j)∈γ 0 ZY...
[36]

The second part of the proof is the proof of the triangle inequality for the edge cost (to thep-th power): ep XY (γXY )≤e p XZ (γXZ ) +ep ZY (γZY )..(38) This result is proved in Appendix A-B. To prove (33), we start withd(X,Y,γ XY )and apply the inequalities in (37) and (38) ...
[37]

to obtain d(X,Y,γ XY ) ≤   X (i,k)∈γ 1 XZ,(k,j)∈γ 1 ZY dp (xi,zk) + X (i,k)∈γ 0 XZ dp (xi,zk) +cp 2 (|X|+|Z|−2|γ XZ|) +ep XZ (γXZ ) 1/p +   X (i,k)∈γ 1 XZ,(k,j)∈γ 1 ZY dp (zk,yj) + X (k,j)∈γ 0 ZY dp (zk,yj) +cp 2 (|Z|+|Y|−2|γ ZY|) +ep ZY (γZY ) 1/p =d(X,Z,γ XZ ) +d(Z,Y,γ Z...
[38]

Cost for assigned edges:The cost for the assigned edges in (42) meets ϵp 2 X (i1,j1)∈γ1 XZ◦γ1 ZY X (i2,j2)∈γ1 XZ◦γ1 ZY |AX(i1,i 2)−A Y (j1,j 2)| =ϵp 2 X (i1,k1)∈γ1 XZ,(k1,j1)∈γ1 ZY X (i2,k2)∈γ1 XZ,(k2,j2)∈γ1 ZY |AX(i1,i 2)−A Y (j1,j 2) +AZ(k1,k 2)−A Z(k1,k 2)| ≤ϵp 2 X (i1,k1)∈...
[39]

Cost for half-assigned edges:We first consider the terms for the half-assigned edges inXin (42) to yield the following inequality. ηϵp X (i1,j1)∈γ1 XZ◦γ1 ZY   X i2∈UX(γXZ ) AX(i1,i 2) + X (i2,k2)∈γ0 XZ AX(i1,i 2)   =ηϵp X (i1,j1)∈γ1 XZ◦γ1 ZY X i2∈UX(γXZ ) AX(i1,i 2) +ηϵp X...
[40]

Cost for unassigned edges:Operating with the cost for unassigned edges inX, we obtain the following inequality β 2ϵp X i1∈UX(γXZ ) X i2∈UX(γXZ ) AX(i1,i 2) +βϵ p X i1∈UX(γXZ ) X (i2,k2)∈γ0 XZ AX(i1,i 2) β 2βϵp X (i1,k1)∈γ0 XZ X (i2,k2)∈γ0 XZ AX(i1,i 2) =β 2ϵp X i1∈UX(γXZ ) X i...
[41]

Combination of all edge costs:By combining the in- equalities in (43), (44), (45), (46), and (47), we obtain ep XY (γXY ) ≤ϵp 2 X (i1,k1)∈γ1 XZ, X (i2,k2)∈γ1 XZ |AX(i1,i 2)−A Z(k1,k 2)| + ϵp 2 X (k1,j1)∈γ1 ZY X (k2,j2)∈γ1 ZY |AZ(k1,k 2)−A Y (j1,j 2)| +ηϵp X (i1,k1)∈γ1 XZ X i2∈...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [19]

Graph GOSPA metric: A metric to measure the discrepancy between graphs of different sizes,

J. Gu, A. F. García-Fernández, R. E. Firth, and L. Svensson, “Graph GOSPA metric: A metric to measure the discrepancy between graphs of different sizes,”IEEE Transactions on Signal Processing, vol. 72, pp. 4037–4049, 2024

work page 2024

[2] [1]

Spline-like wavelet filterbanks for multiresolution analysis of graph- structured data,

V. N. Ekambaram, G. C. Fanti, B. Ayazifar, and K. Ramchandran, “Spline-like wavelet filterbanks for multiresolution analysis of graph- structured data,”IEEE Transactions on Signal and Information Process- ing over Networks, vol. 1, no. 4, pp. 268–278, 2015

work page 2015

[3] [2]

Predicting graph signals using kernel regression where the input signal is agnostic to a graph,

A. Venkitaraman, S. Chatterjee, and P. Händel, “Predicting graph signals using kernel regression where the input signal is agnostic to a graph,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 4, pp. 698–710, 2019

work page 2019

[4] [3]

When to make a topic popular again? a temporal model for topic rehotting prediction in online social networks,

C. Wang, X. Xin, and J. Shang, “When to make a topic popular again? a temporal model for topic rehotting prediction in online social networks,” IEEE Transactions on Signal and Information Processing over Networks, vol. 4, no. 1, pp. 202–216, 2018

work page 2018

[5] [4]

The graph neural network model,

F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfar- dini, “The graph neural network model,”IEEE transactions on neural networks, vol. 20, no. 1, pp. 61–80, 2008

2008

[6] [5]

T. M. Apostol,Mathematical Analysis. Addison Wesley, 1974

work page 1974

[7] [6]

Agraphdistancemetricbasedonthemaximal common subgraph,

H.BunkeandK.Shearer,“Agraphdistancemetricbasedonthemaximal common subgraph,”Pattern recognition letters, vol. 19, no. 3-4, pp. 255–259, 1998

work page 1998

[8] [7]

A distance measure between attributed relational graphs for pattern recognition,

A. Sanfeliu and K.-S. Fu, “A distance measure between attributed relational graphs for pattern recognition,”IEEE Transactions on Systems, Man, and Cybernetics, vol. SMC-13, no. 3, pp. 353–362, 1983

work page 1983