Abstract: Cooperative navigation of unmanned surface vehicle (USV) fleets in constrained coastal waters is challenged by uncertain environmental information, limited onboard perception, and the need to simultaneously maintain collision avoidance, formation stability, and adaptability to dynamic environments. To address these challenges, this study proposes a multi-agent deep reinforcement learning framework for unmanned aerial vehicle (UAV)-assisted cooperative navigation of USV fleets. The heterogeneous UAV-USV system is formulated as a dynamic interaction graph, in which a Graph Neural Network (GNN) aggregates multi-hop neighborhood information to integrate the UAV′s global environmental observations with the local states of individual USVs, thereby enhancing fleet-level situational awareness. An improved multi-agent proximal policy optimization (MAPPO) algorithm is further developed under a centralized-training-and-decentralized-execution architecture. Heterogeneous state encoders are introduced to accommodate differences in observation dimensions and action spaces between aerial and surface agents while maintaining efficient decentralized decision-making. In addition, a hierarchical reward mechanism and a dynamic formation-reconfiguration strategy are designed to enable stable formation keeping in open waters and adaptive formation adjustment in constrained waterways. Simulation results demonstrate the effectiveness of the proposed framework in coordinating heterogeneous UAV-USV agents under complex navigation conditions. The proposed approach provides a systematic solution for cross-domain cooperative navigation and offers potential for applications such as coastal hydrographic surveying and port-waterway inspection.