Patients with vascular cognitive impairment (VCI) commonly exhibit deficits in processing speed. This has been attributed to a disruption of frontal subcortical neuronal circuits by ischemic lesions, but the exact mechanisms and underlying anatomical structures are poorly understood. We set out to identify a strategic brain network for processing speed by applying graph-based data-mining techniques to MRI lesion maps from patients with small vessel disease. We studied 235 patients with CADASIL, a genetic small vessel disease causing pure VCI. Using a probabilistic atlas in standard space we first determined the regional volumes of white matter hyperintensities (WMH) and lacunar lesions (LL) within major white matter tracts. Conditional dependencies between the regional lesion volumes and processing speed were then examined using Bayesian network analysis. Exploratory analysis identified a network of five imaging variables as the best determinant of processing speed. The network included LL in the left anterior thalamic radiation and the left cingulum as well as WMH in the left forceps minor, the left parahippocampal white matter and the left corticospinal tract. Together these variables explained 34% of the total variance in the processing speed score. Structural equation modeling confirmed the findings obtained from the Bayesian models. In summary, using graph-based models we identified a strategic brain network having the highest predictive value for processing speed in our cohort of patients with pure small vessel disease. Our findings confirm and extend previous results showing a role of frontal-subcortical neuronal circuits, in particular dorsolateral prefrontal and cingulate circuits, in VCI.