In one embodiment, a device classification service receives telemetry data indicative of behavioral characteristics of a plurality of devices in a network. The service obtains side information for the telemetry data. The service applies metric learning to the telemetry data and side information, to construct a distance function. The service uses the distance function to cluster the telemetry data into device clusters. The service associates a device type label with a particular device cluster.