Gait recognition is an important topic in biometrics. Current works primarily focus on recognizing a single person's walking gait. However, a person's gait will change when they walk with other people. How to recognize the gait of multiple people walking is still a challenging problem. This paper proposes an attribute discovery model in a max-margin framework to recognize a person based on gait while walking with multiple people. First, human graphlets are integrated into a tracking-by-detection method to obtain a person's complete silhouette. Then, stable and discriminative attributes are developed using a latent conditional random field (L-CRF) model. The model is trained in the latent structural support vector machine (SVM) framework, in which a new constraint is added to improve the multi-gait recognition performance. In the recognition process, the attribute set of each person is detected by inferring on the trained L-CRF model. Finally, attributes based on dense trajectories are extracted as the final gait features to complete the recognition. The experimental results demonstrate that the proposed method achieves better recognition performance than traditional gait recognition methods under the condition of multiple people walking together.