Mesh adaptation plays a central role in efficient numerical simulation of partial differential equations, particularly in regimes where resolving localized features is critical. Classical adjoint-based and optimization-driven refinement strategies, while accurate and principled, are often computationally expensive and difficult to scale in large or repeated simulation settings. This motivates solver-independent and computationally efficient alternatives for identifying refinement regions. In this work, we study two complementary paradigms for solver-independent mesh adaptation. The first is a sparse recovery-based formulation of discretization entity marking, where mesh refinement is posed as an inverse problem to recover a sparse entity-wise refinement indicator using operator-driven sensing and structured sparsity, resulting in an explicit and interpretable selection of mesh entities for refinement. To improve scalability, we incorporate operator-weighted scaling and sketching strategies while preserving reconstruction quality. The second is a machine learning-based formulation using graph neural networks trained with a physics-informed classification objective. The model takes flux gradient features defined on a mesh graph as input and is supervised using the Euler residual as a refinement signal. This approach learns refinement indicators directly from data without explicit operator structure, enabling fast inference at the cost of reduced interpretability and dependence on training data. All experiments are conducted on steady two-dimensional Euler equations with a fixed mesh density setup. Performance is evaluated across variations in sketching strategy and associated parameters. The sparse recovery approach shows stable convergence, robustness to perturbations in the right-hand side, and resilience under aggressive sketching. The learning-based models achieve competitive refinement performance and capture dominant flow features, though finer-scale structures are less consistently resolved compared to the sparse formulation. Overall, the results highlight a fundamental trade-off in solver-independent mesh adaptation: structured sparse recovery provides interpretability through explicit refinement indicators and controlled optimization behavior, whereas graph-based learning offers flexibility and fast evaluation. These approaches represent two ends of a spectrum, and the appropriate choice depends on whether robustness and interpretability or computational efficiency and data-driven adaptability are prioritized.