Malware remains an important security threat, as miscreants continue to deliver a variety of malicious programs to hosts around the world. At the heart of all the malware delivery techniques are executable files (known as downloader trojans or droppers) that download other malware. Because the act of downloading software components from the Internet is not inherently malicious, benign and malicious downloaders are difficult to distinguish based only on their content and behavior. In this paper, we introduce the downloader-graph abstraction, which captures the download activity on end hosts, and we explore the growth patterns of benign and malicious graphs. Downloader graphs have the potential of exposing large parts of the malware download activity, which may otherwise remain undetected. By combining telemetry from anti-virus and intrusion-prevention systems, we reconstruct and analyze 19 million downloader graphs from 5 million real hosts. We identify several strong indicators of malicious activity, such as the growth rate, the diameter, and the Internet access patterns of downloader graphs. Building on these insights, we implement and evaluate a machine learning system for malware detection. Our system achieves a 96.0% true-positive rate, with a 1.0% false-positive rate, and detects malware an average of 9.24 days earlier than existing antivirus products. We also perform an external validation by examining a sample of unlabeled files that our system detects as malicious, and we find that 41.41% are blocked by anti-virus products.