Estimated time of arrival (ETA) is one of the critical services offered by navigation and hailing providers. The majority of existing solutions approach ETA as a regression problem and leverage GPS trajectories for estimation. However, the travel time fluctuates greatly between different trips, making simple regression methods skewed. Additionally, these methods are incapable of conducting estimation in practice because the trajectories of future trips are unknown. To jointly tackle these problems, we propose a novel Categorical approximate method to Estimate Time of Arrival (CatETA). Specifically, we formulate the ETA problem as a classification problem and label it with the average time of each category. To eliminate bias in categorical labeling, we approximate travel time using the weighted average of different classes in the testing stage. Then, we design a network structure that extracts the spatio-temporal features of link sequences and integrates a set of global information. Furthermore, we merge link sequences according to network topology and graph embedding to alleviate the computational burden associated with large-scale link networks. Comprehensive experiments on real-world datasets demonstrate that CatETA considerably improves the estimation performance and significantly reduces computational effort.