The novel concept of signature graphs extends signed graphs by admitting multiple types of partial similarity/agreement or dissimilarity/disagreement. Extending the concept of balancedness to signature graphs yields an explicit and efficient basis for multi-class clustering and classification. Contrary to existing two-stage approaches that consist of graph learning followed by graph clustering, we propose a one-step procedure that directly learns a perfectly clustered graph. We describe the algorithmic constituents for our approach and illustrate its superiority via numerical simulations.
