Water distribution networks are critical infrastructures under threat from the accidental or intentional release of contaminants. Large-scale data collection is vital for digital twin modelling, but remains challenging in underground spaces over vast areas. Therefore, inferring the contaminant spread process with minimal sensor data is important. Existing sensor deployment optimisation approaches use scenario-based numerical optimisation, but suffer from scalability issues and lack performance guarantees. Analytical graph theoretic approaches link complex network topology (e.g. Laplacian spectra) to optimal sensing locations, but neglect the complex fluid dynamics. Alternative data-driven approaches such as compressed sensing offer limited sample node reduction. In this work, we introduce a novel data-driven Graph Fourier Transform that exploits the low-rank property of networked dynamics to optimally sample WDNs. The proposed GFT guarantees error free recovery of network dynamics and offers attractive compression and scaling improvements over existing numerical optimisation, compressed sensing, and graph theoretic approaches. By testing on 100 different contaminant propagation data sets, the proposed scheme shows that, on average, with nearly 30% of the junctions monitored, we are able to fully recover the networked dynamics. The framework is useful for other monitoring applications of WDNs and can be applied to a variety of infrastructure sensing for digital twin modelling.