Higher-order motif clustering. The motif-based graph clustering problem is studied from a spectral perspective in heterogeneous networks. Benson et al. [1]} introduced a nice generalized framework for clustering the networks based on the higher-order connectivity patterns. They defined the motif conductance as the ratio of the number of motifs cutting the border between two regions to the number of motif instance endpoints (i.e., nodes) in the subgraph or its complement, whichever is smaller. Since getting the optimal solution for motif conductance is NP-Hard, they proposed an approximate algorithm that finds the near-optimal cluster in a given network. Their method relies on the spectral clustering of motif adjacency matrix whose entry \(i, j\)  is the number of motifs where nodes \(i\)  and \(j\)  co-occur. The set of nodes in the spectral ordering that has the minimum conductance is reported as the optimal higher-order cluster.
Recursive bisection method iteratively finds the near-optimal clusters in the complement of the graph and k-means clustering on the motif adjacency matrix obtains a prespecified number of clusters.
Concurrently, Tsourakakis et al. [2]} proposed the same framework for motif-aware clustering and also introduced a random walk interpretation of the graph reweighting scheme which gives a principled approach to define the notion of conductance for other motifs.
More recently, Li et al. improved the motif-based clustering approach to handle the clustering of disconnected nodes [3]}.
Our framework differs from those approaches: we do not partition the graph but find dense subgraphs around nodes/edges.
We give an extensive comparison against the motif clustering [1]} in our experiments.
<FIGURE>