Two metrics for attributed hypergraphs

Sebastiano Smaniotto

doi:10.1016/j.patrec.2021.06.007

2021-09-01

PRE

Sebastiano Smaniotto *

Marcello Pelillo

DOI：10.1016/j.patrec.2021.06.007

原文链接

原文求助

摘要

En 中文

Modern quantitative challenges require to tackle problems on increasingly complex systems in which the relationships between the comprised entities cannot be modelled in a simple pairwise fashion, as graphs do. Such approximation of higher-order relations may lead to a substantial loss of information, hence the need to use more general models than graphs. The most natural choice is to use hypergraphs, discrete structures able to capture k-adic relationships among the entities participating in the problem, modelled as vertices, by grouping them in non-empty sets which constitute the hyperedges of the hypergraph. Since one of the most desirable abilities in this context is to quantify the difference between two such high-order systems, devising distance metrics between hypergraphs becomes of the utmost importance. In this paper, we aim at tackling precisely this problem. Motivated by our previous work on graphs, we propose two distance measures between attributed hypergraphs and we prove that they satisfy the properties of a metric. Both metrics are based on the notion of the maximal common subhypergraph. (c) 2021 Elsevier B.V. All rights reserved.

Keyword:

Hypergraph

Matching

Metric distance

Hypergraph isomorphism