A number of recent studies have focused on discovering genetic functional or transcriptional modules by integrating information from the rapidly accumulating large-scale microarray expression datasets. Such studies commonly model each microarray as a co-expression network, and detect the conserved gene co-expression clusters from these co-expression networks. Currently, the commonly used method is mining conserved co-expression clusters directly from a “summary network”, which is obtained by aggregating all the co-expression networks derived from different microarrays. However, this method may generate false conserved clusters, which never occur in any of the original individual co-expression networks. Here a scalable and efficient method were proposed to detect the truly conserved gene co-expression clusters from multiple microarrays. This problem is formulated as mining frequently occurring subgraphs across multiple co-expression networks, and involves three steps: (1) Translating each microarray into co-expression network; (2) Clustering edges which occur in the similar co-expression networks by min-hashing and locality-sensitive hashing techniques to obtain the candidate clusters; (3) Applying graph clustering method to the candidate clusters to detect the conserved co-expressed clusters. This method was applied to yeast microarrays and the results demonstrate that, compared to the previous study, the conserved co-expressed clusters detected by the method were more likely to be functionally homogeneous entities or potential transcriptional modules.