A multivariate analytical strategy may pinpoint the structural connectivity patterns associated with Alzheimer’s disease (AD) pathology in connectome-wide association studies. Diffusion magnetic resonance imaging data from 161 participants including subjects with healthy controls, AD, stable and converting mild cognitive impairment, were selected for group-wise comparisons. A multivariate distance matrix regression (MDMR) analysis was performed to detect abnormality in brain structural network along with disease progression. Based on the seed regions returned by the MDMR analysis, supervised learning was applied to evaluate the disease predictive performance. Nine brain regions, including the left orbital part of superior and middle frontal gyrus, the bilateral supplementary motor area, the bilateral insula, the left hippocampus, the left putamen, and the left thalamus demonstrated extremely significant structural pattern changes along with the progression of AD. The disease classification was more efficient when based on the key connectivity related to these seed regions than when based on whole-brain structural connectivity. MDMR analysis reveals brain network reorganization caused by AD pathology. The key structural connectivity detected in this study exhibits promising distinguishing capability to predict prodromal AD patients.