Few previous studies considered brain network architecture when establishing machine learning models to identify major depressive disorder (MDD). Based on a large, multi-site dataset including 1586 participants, this study aimed to use novel graph convolution network (GCN) to distinguish MDD patients from controls, identify MDD subtypes and characterize related network disruption. We found that GCN enabled excellent classification performance of over 80% accuracy. Besides, shared and distinct disrupted network patterns were identified in first-episode drug-naive and recurrent patients. These findings support the feasibility and effectiveness of network-based GCN classier, illustrating the utility of GCN for detecting disrupted network topology.