# Introduction

- The paper presents a generalized framework for graph clustering (clusters of network motifs) on the basis of higher-order connectivity patterns.
- Link to the paper

# Approach

- Given a motif M, the framework aims to find a cluster of the set of nodes S such that nodes of S participate in many instances of M and avoid cutting instances of M (that is only a subset of nodes in instances of M appears in S).
- Mathematically, the aim is to minimise the motif conductance metric given as
*cut*where_{M}(S, S’) / min[vol_{M}(S), vol_{M}(S’)]*S’*is complement of*S*,*cut*= number of instances of M which have atleast one node from both_{M}(S, S’)*S*and*S’*and*vol*= Number of nodes in instances of M that belong only to S._{M}(S) - Solving the above equation is computationally infeasible and an approximate solution is proposed using eigenvalues and matrices.
- The approximate solution is easy to implement, efficient and guaranteed to find clusters that are at most a quadratic factor away from the optimal.

# Algorithm

- Given the network and motif M, form a motif adjacency matrix W
_{M}where W_{M}(i, j) is the number of instances of M that contains i and j. - Compute spectral ordering of the nodes from normalized motif laplacian matrix.
- Compute prefix set of spectral ordering with small motif conductance.

# Scalability

- Worst case
*O(m*, based on experiments^{1.5})*O(m*where^{1.2})*m*is the number of edges.

# Advantages

- Applicable to directed, undirected and weighted graphs (allows for negative edge weights as well).
- In case the motif is not known beforehand, the framework can be used to compute significant motifs.
- The proposed framework unifies the two fundamental tools of network science (motif analysis and network partitioning) along with some worst-case guarantees for the approximations employed and can be extended to identify higher order modular organization of networks.