Deterministic network is a key focus and hotspot in the current development of the Internet. How to evaluate the performance of non-deterministic traffic in deterministic network systems remains a challenge both in theory and engineering. Although traditional methods， such as modeling network traffic arrival distribution using queuing theory， employing network calculus analysis to establish upper and lower bounds of network behavior， and applying machine learning and deep learning algorithms to predict network performance trends from large-scale historical data statistically， can address this issue partially， they still suffer from poor accuracy and performance facing complex deterministic network systems. Therefore， a Complex-Enhanced Attention Graph Neural Network （CEA-GNN）-based method was proposed for deterministic network performance evaluation. In the method， the gating property of deterministic network systems was utilized fully， and an attention mechanism was employed to deliver critical information to the Graph Neural Network （GNN）， thereby improving the evaluation accuracy. At the same time， the relevant information was extracted from both the graph spatial domain and the complex frequency domain to update the GNN， thereby enhancing performance of the evaluation model. Experimental results from experiments conducted on the National Science Foundation Network （NSFNet） topology indicate that compared to the RouteNet-Fermi evaluation method， the proposed method reduces the Mean Absolute Error （MAE） of non-deterministic traffic latency prediction in deterministic networks by 87.4%， decreases the MAE of packet loss rate prediction by 12.7%， and reduces the average processing time per flow by 64.4%.