Existing graph analysis techniques generally focus on decreasing the dimensionality of graph data (i.e., removing nodes, edges, or both) in diverse predictive learning tasks in pattern recognition, computer vision, and medical data analysis such as dimensionality reduction, filtering and embedding techniques. However, graph super-resolution is strikingly lacking, i.e., the concept of super-resolving low-resolution (LR) graphs with n r nodes into high-resolution graphs (HR) with n(r') > n(r) nodes. Particularly, learning how to automatically generate HR brain connectomes, without resorting to the computationally expensive MRI processing steps such as image registration and parcellation, remains unexplored. To fill this gap, we propose the first technique to super-resolve undirected fully connected graphs with application to brain connectomes. First, we root our brain graph super-resolution (BGSR) framework in learning how to estimate a centered LR population-based brain graph representation, coined as connectional brain template (CBT), acting as a proxy in the target BGSR task. Specifically, we hypothesize that the estimation of a wellrepresentative and centered CBT would help better capture the individuality of each LR brain graph via its residual distance from the population-based CBT. This will eventually allow an accurate identification of the most similar individual graphs to a new testing graph in the LR domain for the target prediction task. Second, we leverage the estimated LR CBT (i.e., population mean) to derive residual LR brain graphs, capturing the deviation of all subjects from the estimated CBT. Third, we learn multi-topology LR graph manifolds using different graph topological measurements (e.g., degree, closeness, betweenness) by estimating residual LR similarity matrices modeling the relationship between pairs of residual LR graphs. These are then fused so we can effectively identify for each testing LR subject its most K similar training LR graphs. Last, the missing testing HR graph is predicted by averaging the HR graphs of the K selected training subjects. Predicted HR from LR functional brain graphs boosted classification results for autistic subjects by 16.48% compared with LR functional graphs. (C) 2020 Elsevier B.V. All rights reserved.