High performance graph processing poses significant challenges for both algorithm and platform designers due to the large performance variability it exhibits: performance depends on the algorithm, the dataset, and the (hardware/software) platform. Traditionally, performance variability is tackled by extensive benchmarking, modeling, and, eventually, better or smarter algorithms. Our own research into the impact of datasets on the performance of graph algorithms has convinced us that such extensive benchmarking is very difficult for graph processing simply because we lack input data: the public datasets and graph generation tools currently available are insufficient for a systematic investigation of the impact of different graph properties. In this work we propose to alleviate this problem by using evolutionary computing as a method to generate graphs. Our goal is allow users to request graphs with a given set of properties (e.g., number of vertices, number of edges, degree distribution), and enable the generator to evolve graphs until they satisfy the request. Such a fine-grain, flexible exploration of graphs and their properties will finally enable a statistical take on performance analysis and modeling for graph processing. To this end, our work-in-progress paper presents the design of our generator, discusses the challenges and trade-offs to be encountered, and reveals our preliminary results.