Signature Graphs - Fundamentals, Learning, and Clustering

Abstract

We introduce the novel concept of signature graphs. Contrary to conventional unsigned and signed graphs, signature graphs capture partial similarity/agreement or dissimilarity/disagreement between a collection of objects in an efficient and intuitive manner. We discuss basic properties of this type of graphs and establish a connection to multilayer graphs. Furthermore, we define the notion of balancedness for signature graphs and derive several equivalent conditions for balancedness. Finally, we develop a coherent framework for learning a signature graph from given data and for clustering the nodes of signature graphs. The latter has a complexity that scales only logarithmically in the number of clusters.