It is widely considered that unlicensed taxis pose a risk to public safety and interfere with the effective management of traffic. Significant human and material resources are expended by traffic control departments to locate these vehicles with limited success. This study suggests a smart, trajectory big data-based approach entitled Trajectory Graph Embedding-based Unlicensed Taxi Detection (TGE-UTD) to identify suspected unlicensed taxis and address this issue. The model implementation comprises three stages: first, the Automatic Number Plate Recognition (ANPR) data are transformed into a trajectory graph; second, a biased random walk is deployed to embed the trajectory graph; and finally, the set of vehicles similar to the known licensed taxis is obtained as the set of suspected unlicensed taxis using the cosine similarity of the vehicle embedding vector. Through precision evaluation and dimension reduction experiments, the performance of the walk model TGE-UTD is compared to that of the no-walk models Word2Vec and Doc2Vec in detecting large vehicles and taxis. TGE-UTD is observed to exhibit the best performance among the three models. This study pioneers the application of machine learning for feature extraction in detecting unlicensed taxis. The model proposed in the study can be deployed to detect unlicensed taxis; moreover, its application can be extended to detect other types of vehicles, providing traffic management departments with supporting vehicle detection information.