Hypergraph Similarity Measures

—In this paper we present a novel framework for hypergraph similarity measures (HSMs) for hypergraph comparison. Hypergraphs are generalizations of graphs in which edges may connect any number of vertices, thereby representing multi-way relationships which are ubiquitous in many real world networks including neuroscience, social networks, and bioinformatics. We propose two approaches for developing HSMs. The first approach is based on transforming the hypergraph into a graph representation, e.g., clique and star expansion, and then invoking the standard graph similarity measures. The second approach relies on a tensor based representation of hypergraphs which intrinsically captures multi-way relations, and define similarity measures using tensor algebraic notions. Within each approach we present a collection of measures which either assess hypergraph similarity at a specific scale e.g. local, mesoscopic or global, or provide a more holistic multi-scale comparison. We discuss the advantages and disadvantages of the two proposed approaches, and demonstrate their performance on synthetic hypergraphs and hypergraphs derived from exper- imental biological datasets.