Organizations face a data discovery problem when their analysts spend more time looking for relevant data than analyzing it. This problem has become commonplace in modern organizations as: i) data is stored across multiple storage systems, from databases to data lakes, to the cloud; ii) data scientists do not operate within the limits of well-defined schemas or a small number of data sources—instead, to answer complex questions they must access data spread across thousands of data sources. To address this problem, we capture relationships between datasets in an enterprise knowledge graph (EKG), which helps users to navigate among disparate sources. The contribution of this paper is AURUM, a system to build, maintain and query the EKG. To build the EKG, we introduce a Two-step process which scales to large datasets and requires only one-pass over the data, avoiding overloading the source systems. To maintain the EKG without re-reading all data every time, we introduce a resource-efficient sampling signature (RESS) method which works by only using a small sample of the data. Finally, to query the EKG, we introduce a collection of composable primitives, thus allowing users to define many different types of discovery queries. We describe our experience using AURUM in three corporate scenarios and do a performance evaluation of each component.