Urban traffic congestion remains one of the most pressing challenges confronting smart city development worldwide, imposing substantial economic costs, environmental degradation, and diminished quality of life for urban residents. Existing traffic signal control paradigms including fixed-time plans, actuated controllers, and adaptive systems such as Split Cycle Offset Optimisation Technique (SCOOT) and Sydney Coordinated Adaptive Traffic System (SCATS) exhibit significant limitations in network-wide coordination under dynamically varying demand conditions. More recently, Reinforcement Learning (RL)-based approaches have demonstrated promise at isolated intersections but face persistent challenges in scalability, sample efficiency, transferability, and real-time multi-intersection coordination. This paper presents Graph-Based Metaheuristic For Traffic Signal Coordination (GRAPH-TSC), a novel algorithm that models the urban traffic network as a directed graph and employs a graph-aware Ant Colony Optimization (ACO) variant hybridized with local search to jointly optimize cycle lengths, green splits, and offsets across all intersections in real time. GRAPH-TSC introduces four key innovations: 1) a Graph Attention Network (GAT)-based surrogate model that replaces computationally expensive microsimulation for rapid fitness evaluation during optimization, 2) a pheromone diffusion mechanism that propagates pheromone updates along the traffic graph in proportion to inter-intersection traffic flow dependencies, naturally encoding green wave coordination, 3) a hierarchical network decomposition strategy that partitions large networks into overlapping subnetworks for scalable optimization with boundary coordination via shared pheromone, and 4) an adaptive re-optimization trigger based on Cumulative Sum (CUSUM) change detection that initiates re-optimization only upon detected traffic pattern shifts. GRAPH-TSC was evaluated on SUMO-simulated networks modeled after real urban areas in Algiers, Algeria (42 intersections) and Hanoi, Vietnam (67 intersections), as well as synthetic grid networks of up to 100 intersections. Experimental results demonstrate that GRAPH-TSC achieves an 18–27% reduction in average vehicle delay, a 14–22% improvement in network throughput, and an 11–19% reduction in CO2 emissions compared to Webster’s fixed-time, SCATS-like adaptive, standard ACO, Genetic Algorithm (GA), and Deep Q-Network (DQN)-based methods. Re-optimization is completed within 3 seconds for the 67-intersection Hanoi network, confirming the algorithm’s real-time applicability for operational deployment in smart city traffic management systems.