An original graph clustering approach to efficient localization of error covariances is proposed within an ensemble-variational data assimilation framework. Here the localization term is very generic and refers to the idea of breaking up a global assimilation into subproblems. This unsupervised localization technique based on a linearizedstate-observation measure is general and does not rely on any prior information such as relevant spatial scales, empirical cut-off radius or homogeneity assumptions. It automatically segregates the state and observation variables in an optimal number of clusters (otherwise named as subspaces or communities), more amenable to scalable data assimilation.The application of this method does not require underlying block-diagonal structures of prior covariance matrices. In order to deal with inter-cluster connectivity, two alternative data adaptations are proposed. Once the localization is completed, an adaptive covariance diagnosis and tuning is performed within each cluster. Numerical tests show that this approach is less costly and more flexible than a global covariance tuning, and most often results in more accurate background and observations error covariances.