Electrical power grids are vulnerable to cyber attacks, as seen in Ukraine in 2015, 2016, and 2022. These cyber attacks are classified as Advanced Persistent Threats (APTs) with potential disastrous consequences such as a total blackout. However, state-of-the-art intrusion detection systems are inadequate for APT detection owing to their stealthy nature and long-lasting persistence. Furthermore, they are ineffective as they focus on individual anomaly instances and overlook the correlation between attack instances. Therefore, this research proposes a novel method for spatio-temporal APT detection and correlation for cyber-physical power systems. It provides online situational awareness for power system operators to pinpoint system-wide anomaly locations in near real-time and preemptively mitigate APTs at an early stage before causing adverse impacts. We propose an Enhanced Graph Convolutional Long Short-Term Memory (EGC-LSTM) by using sequential and neural network filters to improve APT detection, correlation, and prediction. Control center and substation communication traffic is used to determine cyber anomalies using semi-supervised deep packet inspection and software-defined networking. Power grid circuit breaker status is used to determine physical anomalies. Cyber-physical anomalies are correlated in cyber-physical system integration matrix and EGC-LSTM. The EGC-LSTM outperforms existing state-of-the-art spatio-temporal deep learning models, achieving the lowest mean square error.