Two metrics for attributed hypergraphs

doi:10.1016/j.patrec.2021.06.007

Return

Two metrics for attributed hypergraphs

2021-09-01

PRE

Sebastiano Smaniotto *

Marcello Pelillo

DOI：10.1016/j.patrec.2021.06.007

Original

Original request for help

Save

Abstract

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.

Keywords:

Hypergraph

Matching

Metric distance

Hypergraph isomorphism

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.