提出一套可衡量异构图距离的通用度量方法，适合图结构不同时的比较分析。
A family of graph GOSPA metrics for graphs with different sizes
- 基于广义最优子模式分配思想，统一处理节点与边的匹配代价
- 支持不同规模图间的距离计算，且可通过线性规划近似求解
- 在真实数据集上提升分类性能，适用于图对比与聚类任务
本文提出一族用于衡量不同大小图之间距离的图度量方法。该度量族定义了图广义最优子模式分配（GOSPA）度量的一般形式，并证明其满足度量性质。与图GOSPA类似，该度量族对两图间已匹配节点的属性差异及未匹配节点数量进行惩罚；但相比原版，其对边不匹配提供了更灵活的惩罚机制。本文还表明，该度量族可通过线性规划近似计算。通过仿真实验展示了不同超参数下度量族的特性，并在真实数据集上验证了其在分类任务中的优势。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。