In one embodiment, a device in a network receives a first plurality of measurements for network metrics captured during a first time period. The device determines a first set of correlations between the network metrics using the first plurality of measurements captured during the first time period. The device receives a second plurality of measurements for the network metrics captured during a second time period. The device determines a second set of correlations between the network metrics using the second plurality of measurements captured during the second time period. The device identifies a difference between the first and second sets of correlations between the network metrics as a network anomaly.