We study the detection of anomalous activity over graphs, where the patterns in question are weak and localized over the graph. We describe and compare three detectors for weak graph-structured patterns that are developed using tools from graph theory, optimization and machine learning. These detectors are computationally efficient, applicable to graphs and patterns with general structures and come with precise theoretical guarantees, often achieving near-optimal statistical performance.