# Spectral graph theory: would “higher order” graph cuts make sense?

The problem of performing graph cuts is well known and has many algorithms for many different applications. Is it a concept that is possible to extend or generalize in some sense? Can we find second order graph cuts in some sense?

Since spectral graph theory provides us the tools to make matrices for distance, adjoint and laplacian et.c. for a single graph, then for multiple graphs or even a family of graphs maybe we can try and find simultaneous graph cuts a little bit like we in representation theory we can find a joint canonical basis where the canonical matrix is block-diagonal and corresponds to irreducible sub groups:

$${\bf M_i = TC_iT}^{-1} : {\bf C_i} \text{:s have the same block-diagonal structure } \forall {i}$$

Let $\mathbf{L}_{1},\mathbf{L}_2$ be Laplacian matrices of two graphs $G_{1},G_{2}$ respectively. If $$\mathbf{L}_{1} \mathbf{L}_{2}= \mathbf{L}_{2} \mathbf{L}_{1},$$ then the spectral bisection heuristic I mentioned above is going to partition the vertex sets in the exact same way. If $I_{1},I_{2}$ are the sets of vertex indices corresponding to the two partitions of $G_{1}$ and the index sets $I_{3},I_{4}$ for the two partitions of $G_{2}$, then $I_{1}=I_{3}$ and $I_{2} = I_{4}$.