Higher-order Spectral Clustering for Heterogeneous Graphs
  Higher-order connectivity patterns such as small induced sub-graphs called
graphlets (network motifs) are vital to understand the important components
(modules/functional units) governing the configuration and behavior of complex
networks. Existing work in higher-order clustering has focused on simple
homogeneous graphs with a single node/edge type. However, heterogeneous graphs
consisting of nodes and edges of different types are seemingly ubiquitous in
the real-world. In this work, we introduce the notion of typed-graphlet that
explicitly captures the rich (typed) connectivity patterns in heterogeneous
networks. Using typed-graphlets as a basis, we develop a general principled
framework for higher-order clustering in heterogeneous networks. The framework
provides mathematical guarantees on the optimality of the higher-order
clustering obtained. The experiments demonstrate the effectiveness of the
framework quantitatively for three important applications including (i)
clustering, (ii) link prediction, and (iii) graph compression. In particular,
the approach achieves a mean improvement of 43x over all methods and graphs for
clustering while achieving a 18.7% and 20.8% improvement for link prediction
and graph compression, respectively.
