We investigated changes in functional network architecture in amnestic mild cognitive impairment using graph-based analysis of task-free functional magnetic resonance imaging and fine cortical parcellation. Widespread disconnection was observed primarily in cortical hubs known to manifest early Alzheimer's disease pathology, namely precuneus, parietal lobules, supramarginal and angular gyri, and cuneus, with additional involvement of subcortical regions, sensorimotor cortex and insula. The connectivity changes determined using graph-based analysis significantly exceed those detected using independent component analysis both in amplitude and topographical extent, and are largely decoupled from the presence of overt atrophy. This superior ability of graph-based analysis to detect disease-related disconnection highlights its potential use in the determination of biomarkers of early dementia. Graph-based analysis source code is provided as supplementary material.