Higher-order data with high dimensionality arise in a diverse set of application areas such as computer vision, video analytics and medical imaging. Tensors provide a natural tool for representing these types of data. Two major challenges that confound current tensor based supervised learning algorithms are storage complexity and computational efficiency. In this paper, we address these problems by introducing a multi-branch tensor network structure. The multi-branch structure is a general tensor decomposition that includes Tucker and tensor-train (TT) as special cases and takes advantage of the flexibility of the tensor network to provide a better balance between storage and computational complexity. We then introduce a supervised discriminative tensor-train subspace learning approach referred to as tensor-train discriminant analysis (TTDA), and its implementations using the multi-branch tensor network structure. Multi-branch implementations of TTDA are shown to achieve lower storage and computational complexity while providing improved classification performance with respect to both Tucker and TT based supervised learning methods.