Assuming I have a graph with nodes that are of two classes ("circles" and "boxes") and that have connections between all circles and boxes ("black") and within each node group ("red"), where intra-class weights ("red") must be positive while inter-class weights can be any real number: I would like to find a unknown number of clusters in the graph where a cluster must consist of at least one "circle" and one "box". In the graph below the following clusters would be expected:
$$ \big\{[a],[b],d,e,f\big\}, \ \ \big\{[c],g,h \big\} $$
$$V = \{[a],[b],[c],d,e,f,g,h \}$$
$$ E_1 =\begin{bmatrix} & d & e & f & g & h\\ [a]& \ddots & & & & \vdots \\ [b] & & &\ddots & & \\ [c] & \cdots & & & & \cdots \\ \end{bmatrix}\\ E_2 =\begin{bmatrix} & [a] & [b] & [c]& d & e & f & g & h \\ [a] & \ddots & & & 0 & 0 & 0 & 0 & 0 \\ [b] & \ddots & & & 0 & 0 & 0 & 0 & 0 \\ [c] & & & & 0 & 0 & 0 & 0 & 0 \\ d & 0 & 0 & 0& & & & & \vdots \\ e & 0 & 0 & 0& & \ddots & & & \\ f & 0 & 0 & 0& & & & \ddots & \\ g & 0 & 0 & 0& & & & & \\ h & 0 & 0 & 0& & & \cdots & & \\ \end{bmatrix} $$
The inter-class graph is defined as $G_1=(V,E_1)$ while the intra-class graph is defined as $G_2=(V,E_2)$.
Are there algorithms that let me jointly cluster such a graph? I was thinking of merging the two graphs and simply apply a multi-cut. However, this might violate my condition of clusters consisting of at least one element per class.
What would be a sufficient optimization formulation for this problem?