BACKGROUND : Recent functional connectivity (FC) studies have proved the potential value of resting-state functional magnetic resonance imaging (rs-fMRI) in the study of major depressive disorder (MDD); yet, the rs-fMRI-based individualized diagnosis of MDD is still challenging. METHODS : We enrolled 82 treatment-naïve first episode depression (FED) adults and 72 matched normal control (NC). A computer-aided diagnosis framework was utilized to classify the FEDs from the NCs based on the features extracted from not only traditional "low-order" FC networks (LON) based on temporal synchronization of original rs-fMRI signals, but also "high-order" FC networks (HON) that characterize more complex functional interactions via correlation of the dynamic (time-varying) FCs. We contrasted a classifier using HON feature (CHON) and compared its performance with using LON only (CLON). Finally, an integrated classification model with both features was proposed to further enhance FED classification. RESULTS : The CHON had significantly improved diagnostic accuracy compared to the CLON (82.47% vs. 67.53%). Joint classification further improved the performance (83.77%). The brain regions with potential diagnostic values mainly encompass the high-order cognitive function-related networks. Importantly, we found previously less-reported potential imaging biomarkers that involve the vermis and the crus II in the cerebellum. CONCLUSIONS : We only used one imaging modality and did not examine data from different subtypes of depression. CONCLUSIONS : Depression classification could be significantly improved by using HON features that better capture the higher-level brain functional interactions. The findings suggest the importance of higher-level cerebro-cerebellar interactions in the pathophysiology of MDD.