We present two model-based methods for learning Granger causality networks for multivariate categorical time series. Our first proposal is based on the mixture transition distribution (MTD) model. Traditionally, MTD is plagued by a nonconvex objective, non-identifiability, and presence of many local optima. To circumvent these problems, we recast inference in the MTD as a convex problem. The new formulation facilitates the application of MTD to high-dimensional multivariate time series. Our second proposal is based on a multi-output logistic autoregressive model, which while a straightforward extension, has not been previously applied to the analysis of multivariate categorial time series. We investigate identifiability conditions of both methods, devise novel optimization algorithms for the MTD, and compare the MTD and mLTD in simulated experiments. Our approach simultaneously provides a comparison of methods for network inference in categorical time series and opens the door to modern, regularized inference in MTD model.