Internet Device Graphs are datasets that organize and associate the many identifiers produced by PCs, phones, smart TVs and tablets as they access media on internet. Digital cross-media, the delivery and measurement of advertisements across screens, has grown increasingly reliant on device graphs. In response to privacy and tracking concerns, some web browsers limit the persistence of the identifiers used in device graphing. Examples include Safari's implementation of Intelligent Tracking Prevention and user invoked incognito/private browsing capabilities. Non-persistent identifiers create both a scale and accuracy challenge for device graphing. Motivated by accurate audience measurement, this paper demonstrates how measurement and other entities in the digital advertising ecosystem can overcome lack of persistence in identifiers without the need for techniques such as browser fingerprinting. The approach is based on first constructing a device graph using persistent identifiers, and then appending the non-persistent identifiers to the original graph using a technique termed graph backfilling. The resulting device graphs are of immense scale, including more than 2.5 billion identifiers in the US alone.