The agile earth observation satellite scheduling problem (AEOSSP) is a combinatorial optimization problem with time-dependent constraints. Recently, many construction heuristics and meta-heuristics have been proposed; however, existing methods cannot balance the requirements of efficiency and timeliness. In this paper, we propose a graph attention network-based decision neural network (GDNN) to solve the AEOSSP. Specifically, we first represent the task and time-dependent attitude transition constraints by a graph. We then describe the problem as a Markov decision process and perform feature engineering. On this basis, we design a GDNN to guide the construction of the solution sequence and train it with proximal policy optimization (PPO). Experimental results show that the proposed method outperforms construction heuristics at scheduling profit by at least 45%. The proposed method can also calculate the approximate profits of the state-of-the-art method with an error of less than 7% and reduce scheduling time markedly. Finally, we demonstrate the scalability of the proposed method.