Due to the high production of complex data, the last decades have provided a huge advance in the development of similarity search methods. Recently graph-based methods have outperformed other ones in the literature of approximate similarity search. However, a graph employed on a dataset may present different behaviors depending on its parameters. Therefore, finding a suitable graph configuration is a time-consuming task, due to the necessity to build a structure for each parameterization. Our main contribution is to save time avoiding this exhaustive process. We propose in this work an intelligent approach based on meta-learning techniques to recommend a suitable graph along with its set of parameters for a given dataset. We also present and evaluate generic and tuned instantiations of the approach using Random Forests as the meta-model. The experiments reveal that our approach is able to perform high quality recommendations based on the user preferences.