Graph neural networks (GNNs) have made significant progress in various machine learning tasks. Despite their success, many existing GNN models are shown to be vulnerable to adversarial attacks, creating a stringent need to build robust GNN architectures. In this work, we introduce a novel interpretable message passing scheme over adaptive graph structures (ASMP) to enhance the resilience of GNNs against graph structural attacks. The ASMP layers are constructed through optimization steps that concurrently optimize node features and graph structures, allowing the message passing process to be conducted across dynamically adjusted graphs at different layers. This adaptability enables ASMP to handle noisy or perturbed graph structures more effectively, enhancing robustness. We also establish the theoretical convergence properties for the ASMP scheme. By integrating ASMP with neural networks, we introduce a new class of GNNs with adaptive structures (ASGNNs). Extensive experiments on semi-supervised node classification tasks demonstrate that ASGNN outperforms the state-of-the-art GNN architectures regarding classification accuracy when subjected to various adversarial attack scenarios.