This paper investigates the adoption of measures used to evaluate complex networks properties in the characterization of the complexity of data sets in machine learning applications. These measures are obtained from a graph based representation of a data set. A graph representation has several interesting properties as it can encode local neighborhood relations, as well as global characteristics of the data. These measures are evaluated in a meta-learning framework, where the objective is to predict which classifier will have better performance in a given task, in a pair wise basis comparison, based on the complexity measures. Results were compared to traditional data set complexity characterization metrics, and shown the competitiveness of the proposed measures derived from the graph representation when compared to traditional complexity characterization metrics.