In the real world, the duality of high-dimensional data is widespread. The coclustering method has been widely used because they can exploit the co-occurring structure between samples and features. In fact, most of the existing coclustering methods cluster the graphs in the original data matrix. However, these methods fail to output an affinity graph with an explicit cluster structure and still call for the postprocessing step to obtain the final clustering results. In addition, these methods are difficult to find a good projection direction to complete the clustering task on high-dimensional data. In this article, we modify the flexible manifold embedding theory and embed it into the bipartite spectral graph partition. Then, we propose a new method called structured optimal graph-based clustering with flexible embedding (SOGFE). The SOGFE method can learn an affinity graph with an optimal and explicit clustering structure and does not require any postprocessing step. Additionally, the SOGFE method can learn a suitable projection direction to map high-dimensional data to a low-dimensional subspace. We perform extensive experiments on two synthetic data sets and seven benchmark data sets. The experimental results verify the superiority, robustness, and good projection direction selection ability of our proposed method.