To whom correspondence should be addressed. Abstract As proteins with similar structures often have similar funct ions, analysis of protein structures can help predict protein functions and is thus imp ortant. We consider the problem of protein structure classification, which computati onally classifies the structures of proteins into predefined groups. We develop a weighted network that depicts the protein structures, and more importantly, we propose the firs t graphlet-based measure that applies to weighted networks. Further, we develop a de ep neural network (DNN) composed of both convolutional and recurrent layers to use this measure for classification. Put together, our approach shows dramatic improvements in performance over existing graphlet-based approaches on 36 real datasets. E ven comparing with the state-of-the-art approach, it almost halves the classification error. In addition to protein structure networks, our weighted-graphlet measure and DNN cla ssifier can potentially be applied to classification of other weighted networks in computational biology as well as in other domains. Proteins are the building molecules of life, and their diver se functions define the mechanisms of sophisticated organisms [1].