Surrogate-assisted multi-objective optimization has emerged as a practical strategy for engineering design problems in which finite element evaluations are computationally prohibitive. However, most existing surrogate models treat structural designs as flat parameter vectors, discarding the relational information that governs mechanical behavior: which components are connected, how loads are transferred, and where material interfaces arise. This representational mismatch limits surrogate accuracy and generalizability across structurally distinct topologies. This work introduces Graph-Assisted Design (GAD), a unified framework that encodes every candidate design as an attributed graph — nodes carry geometric and material state, edges encode mechanical interactions — and couples this representation with a Graph Attention Network (GAT) ensemble as a differentiable surrogate of finite element analysis. GAD drives the Non-dominated Sorting Genetic Algorithm III (NSGA-III) over this surrogate landscape across up to ten simultaneous structural objectives. A key contribution is the Surrogate Refresh strategy: high-fidelity 3D FEM evaluations are periodically performed on Pareto-front candidates, and correction factors are fed back via exponential moving average updates, bounding prediction drift throughout the optimization. The framework is demonstrated on compliant multi-material airless wheels for planetary rovers, parametrized through an 18-variable genome covering geometry, pantographic spoke configuration, and an eight-sector material distribution across FFF-printable polymers. Multi-scale analysis combines rapid 2D FEA (Neo-Hookean large-deformation and Goodman–Basquin fatigue models) with 3D FEM quadratic tetrahedral solutions as a high-fidelity oracle. Over 500 generations with a population of 1,000, a 103-solution Pareto front is obtained; the peak-stiffness candidate achieves 793 kN/m vertical stiffness with a von Mises safety factor of 20.1 confirmed by a 1.3-million-DOF FEM solution, and surrogate predictions agree with FEM to within 1%. The encoding, surrogate, and optimizer are fully decoupled from the application domain, as validated by a preliminary case study on compliant robotic-arm topology, establishing GAD as a generalizable methodology for machine-learning-assisted structural design.