Algorithm for breaking a graph into sub-graphs based on an attribute
This seems to be the "minimum weight orthogonal partition problem", which has been studied among others by Zheng et al. [1]. Computer scientists have also studied it under the name "colourful components", though it sometimes refer to an unweighted variant. The problem is known to be NP-hard, and some approximations exist [2]. There are probably more recent results, these two references should help you find them.

[1]: Chunfang Zheng, Krister M. Swenson, Eric Lyons, David Sankoff:
OMG! Orthologs in Multiple Genomes - Competing Graph-Theoretical Formulations. WABI 2011: 364-375 -- http://albuquerque.bioinformatics.uottawa.ca/kms/files/papers/2011-ZhengOMG.pdf

[2]: G. He, J. Liu and C. Zhao: Approximation Algorithms for Some Graph Partitioning Problems. Graph Algorithms and Applications 2, pp. 21-31 (2004) -- https://www.researchgate.net/publication/220639657_Approximation_Algorithms_for_Some_Graph_Partitioning_Problems