In brain imaging and connectomics, the study of brain networks, estimating the mean of a population of graphs based on a sample is a core problem. Often, this problem is especially difficult because the sample or cohort size is relatively small, sometimes even a single subject, while the number of nodes can be very large with noisy estimates of connectivity. While the element-wise sample mean of the adjacency matrices is a common approach, this method does not exploit the underlying structural properties of the graphs. We propose using a low-rank method that incorporates dimension selection and diagonal augmentation to smooth the estimates and improve performance over the naïve methodology for small sample sizes. Theoretical results for the stochastic block model show that this method offers major improvements when there are many vertices. Similarly, we demonstrate that the low-rank methods outperform the standard sample mean for a variety of independent edge distributions as well as human connectome data derived from the magnetic resonance imaging, especially when the sample sizes are small. Moreover, the low-rank methods yield "eigen-connectomes," which correlate with the lobe-structure of the human brain and superstructures of the mouse brain. These results indicate that the low-rank methods are the important parts of the toolbox for researchers studying populations of graphs in general and statistical connectomics in particular.