Row Hammer is a serious security threat to modern computing systems using DRAM as main memory. It causes charge loss in DRAM cells adjacent to a frequently activated aggressor row and eventually leads to data bit flips in those cells. Even with countermeasures from hardware vendors for years, many latest DDR4 DRAM-based systems are still vulnerable to Row Hammer. Furthermore, technology scaling continues to reduce the Row Hammer threshold, hence posing even greater challenges than before. Although many architectural solutions for Row Hammer have been proposed in both industry and academia, they still incur substantial overhead in terms of chip area, energy, and performance, fail to provide a sufficient level of protection, or both. Thus, we propose Graphene, a low-cost Row Hammer prevention technique based on a space-efficient algorithm that identifies frequent elements from an incoming data stream. Graphene is provably secure without false negatives and with tightly bounded false positives. Furthermore, Graphene has an order of magnitude smaller area overhead compared to a state-of-the-art counter-based scheme. This makes Graphene a scalable solution to Row Hammer attacks for the memory systems of today and the future. Our evaluation shows that Graphene features nearly zero performance and energy overhead when running realistic workloads. Even for the most adversarial memory access patterns, Graphene increases refresh energy only by 0.34%.