Our solution builds on the GraphScan (1) and Linear Time Subset Scan (LTSS) (2) approaches, comparing the most anomalous subsets detected with and without the graph constraints. We consider a large set of potential graph structures and efficiently compute the highest-scoring connected subgraph for each graph structure and each training example using GraphScan. We normalize each score by dividing by the maximum unconstrained subset score for that training example (computed efficiently using LTSS). We then compute the mean normalized score averaged over all training examples. If a given graph is close to the true underlying structure, then its maximum constrained score will be close to the maximum unconstrained score for many training examples, while if the graph is missing essential connections, then the maximum constrained score given that structure will be much lower than the maximum unconstrained score. Any graph with a large number of edges will also score close to the maximum unconstrained score. Thus, we compare the mean normalized score of a given graph structure to the distribution of mean normalized scores for random graphs with the same number of edges and choose the graph structure with the most significant score given this distribution.