The dynamics of the hydrogen bond network of isotopically substituted liquid water are investigated with a new ultrafast nonlinear vibrational spectroscopy, three-dimensional infrared spectroscopy (3D-IR). The 3D-IR spectroscopy is sensitive to three-point frequency fluctuation correlation functions, and the measurements reveal heterogeneous structural relaxation dynamics. We interpret these results as subensembles of water which do not interconvert on a half picosecond time scale. We connect the experimental results to molecular dynamics (MD) simulations, performing a line shape analysis as well as complex network analysis.