Deploying deep learning in clinical settings requires balancing accuracy with limited computational resources. This is especially challenging in multitask medical imaging, where shared encoders reduce redundancy but task-specific heads remain memory-intensive. We propose Efficient Graph Neural Architecture Search (EGNAS), a gradient-based method that explores a graph-structured space to find compact, task-specific predictors. EGNAS jointly optimizes accuracy and model size using a Pareto-efficient strategy. Evaluated on six MedNIST tasks, it reduces head size by 2.1x on average without performance loss. We further validate EGNAS in a real-world deployment on a low-resource clinical laptop in Algeria, demonstrating its practical utility for resource-constrained healthcare.