In one embodiment, a network assurance service receives one or more sets of network characteristics of a network, each network characteristic forming a different feature dimension in a multi-dimensional feature space. The network assurance service applies machine learning-based anomaly detection to the one or more sets of network characteristics, to label each set of network characteristics as anomalous or non-anomalous. The network assurance service identifies, based on the labeled one or more sets of network characteristics, an anomaly pattern as a collection of unidimensional cutoffs in the feature space. The network assurance service initiates a change to the network based on the identified anomaly pattern.