Extreme operating condition search (EOCS) is one of the core issues in relay protection setting calculation, used to ensure that protection settings can adapt to variations in system operating conditions over a certain period after being deployed. In new energy power systems, operating conditions are more flexible and dynamic, necessitating online setting calculation methods. However, existing EOCS methods fail to meet the efficiency requirements of online applications. To reduce computation time, this paper applies deep learning to the EOCS problem for the first time and proposes an efficient method based on a parallel graph neural network. First, the power system structure is modeled using four matrices, and feature extraction is performed by a graph neural network. Subsequently, the high-dimensional features are concatenated and flattened before being fed into a decision network to predict extreme operating conditions. Finally, the proposed method is validated on the IEEE39-bus and 118-bus systems. Results demonstrate that the proposed method achieves higher accuracy while significantly improving computational efficiency.