Service recommendation is key to improving users’ online experience. The development of the Internet has accelerated the creation of many services, and whether users can obtain good experiences among the massive number of services mainly depends on the quality of service recommendation. It is commonly believed that deep learning has excellent nonlinear fitting ability in capturing the complex interactions between users and items. The advantage in learning intricacy relationships enables deep learning to become an important technology for present service recommendation. Recently, it is noticed that linear models can perform almost as well as the state-of-the-art deep learning models, suggesting that capturing linear relationships between users and items is also very important for recommender systems. Therefore, numerous deep learning systems combined with linear models have been proposed. However, existing models are incapable of considering the size of the embedding. When the embedding dimension is too large, it leads to overfitting and thus influences the model’s ability to capture linear relationships. In this paper, a neural network based on two-layer matrix factorization and multi-layer perceptron—Two-layer Matrix factorization and Multi-layer perceptron Neural Network (TMMNN)—is proposed. To solve the problem of overfitting caused by an oversized embedding dimension, multi-size embedding technology has been integrated into the model. Matrix factorization and the multi-layer perceptron are placed in the upper and lower layers respectively, and they both receive embedding vectors dynamically adjusted for dimensions. In the upper layer, the matrix factorization is responsible for receiving the embedding of users and items, capturing linear relationships, and then yielding the generated new vectors as input to the multi-layer perceptron in the lower layer. Compared to other previously proposed models, the experimental results on the standard datasets MovieLens 20M and MovieLens Latest show that the TMMNN model is evidently better in terms of prediction accuracy.