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}$$


I can only think of one example of "simultaneous cut". It is known that we can get the spectral bisection of a graph from the Laplacian spectrum. A common heuristic is to partition the vertices of the graph based on the sign of the entries in the Fiedler Vector.

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} $.

That's because the commutativity of the Laplacian matrices guarantees a set of simultaneously diagonalizing eigenvectors, so the Fiedler vector is going to be the same. I am not sure if that's what you're looking for though.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.