Two metrics for attributed hypergraphs

Highlights

• We present two novel (normalized) distances measures between attributed hypergraphs.

• The measures are based on the notion of the maximal common subhypergraph.

• The two measures are normalized and differ by their normalization criterion.

Abstract

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.

Introduction

Graph models have long been ubiquitous tools for investigating systems of related objects. Given their versatility and effectiveness, novel, more powerful algorithms for efficient graph processing are continuously sought-after. It is often assumed that the relationship between such objects is pairwise, but many complex systems exhibit higher-order relations. By limiting the model of a system to the constraints of a graph-based one an information loss is inevitabile. On the other hand, hypergraphs, a generalization of graphs where the relationships can contain an arbitrary number of vertices, exhibit a much broader modelling capability. Their group relationships grant more expressiveness, which is more suitable for analytical purposes.

Nowadays, in many applied fields the use of hyper-graphical models to give an abstract representation of objects is well-established. Besides performing analytics on single instances, especially in fields such as computer vision, it is crucial to match and recognize different instances, and a lot of work has been put into developing novel, robust algorithms to perform these tasks. However, once we assign an abstract hyper-graphical representation to the objects to be processed we can reduce those problems to the problem of hypergraph matching.

One of the main applications of hypergraphs is the computer-aided design of very-large-scale integration (VLSI CAD, see [11]), i.e. the process of combining hundreds of thousands of transistors or devices into a single chip to create an integrated circuit using algorithms run by a computer.

Computer vision has also drawn a lot of benefits by employing hypergraph models on images in many applications. Motion segmentation [8], [15], matching [12], [13] and object detection [24] are among the most widespread tasks subject to active research, and many techniques for image clustering based on hypergraphs have also been developed [1], [25]. A lot of work has been done to find ways to embed hypergraphs in low-dimensional vector spaces, as their full representation is very sparse and high-dimensional. In [7] a hypergraph is leveraged to depict the attribute relations in the data, and an embedding scheme is proposed to perform clustering. In [20] the authors present a classification framework where low-level features of hyperspectral images are extracted as hypergraphs, which are embedded in a low dimensional space and fed to a SVM for classification. Many algorithms fail to keep the high-order relations in the embedding process. In [22] an algorithm to overcome this limitation is given. A powerful theoretical result for clustering $k$-regular hypergraphs was proven in Rota Bulò and Pelillo [18] for which an efficient heuristic based on a discrete-time high-order replicator dynamics can be used to perform the optimization.

Clearly, in order to assess the fitness of a match we must be able to tell how similar, or rather how different, two objects are. Many applications depend upon some properties of this distance measure $d$, and it is often desirable that it fulfills all the following properties: nonnegativity ($d(x,y)\ge 0)$, identity ($d(x,y)=0\iff x=y$), simmetry ($d(x,y)=d(y,x)$) and the triangle inequality ($d(x,z)\le d(x,y)+d(y,z)$). If it is the case, then the distance is called a metric and we are able to use it to perform numerical comparisons because it establishes a partial order over the set of objects. Moreover, if the distance is a metric then the set of all hypergraphs endowed with such distance is a metric space. This is relevant from a theoretical point of view because it enables the notion of convergence in such space, and allows us to interpret hypergraphs as points of a metric space. On the other hand, the importance of metrics has been clearly put forward in Chávez et al. [4], which shows how searching among unstructured data, a fundamental problem in modern applications, is possible if the set of objects can be given a metric structure. By the same token, another key benefit of the metric property is that it overcomes the necessity of performing embedding on hypergraphs, which is an expensive, lossy operation.

In this paper, we propose two metrics for attributed hypergraphs which naturally generalize the structure-based approach introduced in Hidović and Pelillo [6] in the context of graphs. These have been shown to be robust with respect to both structural distortions and perturbation of node attributes. The proposed metrics are based on the maximal similarity common subhypergraph of two hypergraphs.