Hypothesis testing on time series of attributed graphs has applications in diverse areas, e.g., social network analysis (wherein vertices represent individual actors or organizations), connectome inference (wherein vertices are neurons or brain regions) and text processing (wherein vertices represent authors or documents). We consider the problem of anomaly/change point detection given the latent process model for time series of graphs with categorical attributes on the edges. Various attributed graph invariants are considered, and their power for detection as a function of a linear fusion parameter is presented. Our main result is that inferential performance in mathematically tractable first-order and second-order approximation models does provide guidance for methodological choices applicable to the exact (realistic but intractable) model. Furthermore, to the extent that the exact model is realistic, we may tentatively conclude that approximation model investigations have some bearing on real data applications.