Anomaly detection without any knowledge about structure
Graph Embeddings

You try to use graph embeddings. These would offer the ability to map your graph-based data into a single latent space, at based on the vertices, the edges or the graph schema as a whole. This has become somewhat of an exciting research topic within research over the last few years; combining graph analysis with modern embedding techniques.

Here is one survey paper that list approaches to these embeddings, along with the authors' own libraries for both static graphs and dynamic graphs. Looking through the results of that survey paper (they perform some becnhmarks towards the end), it would seem that the most promising model would be:


node2vec - if you want to classify the nodes as cleanly as possible (reference implementation)
Structural Deep Network Embedding - if you want to re-construct the graph (reference implementation)




Anomaly Detection

As to the end goal of anomaly detection, I am not sure which of the embedding methods would be best suited. It might be a case as to whether you want to preserve more local or global structure (as with the trade-off between methods such as t-SNE and PCA).

I think you can imagine what to try out with the embeddings in order to detect anaomalies. There might be more clues in the papers linked above as to which way researchers tend to go for certain problems.

Given the hierarchical nature of your graph data, I would be tempted to start by looking into using Hierarchical Density Based Spatial Clustering with Applications of Noise (i.e. HDBSCAN) - the main library specifically includes a few few methods of outlier detection! Here a citation from the linked paper:


  Based on these definitions, we can devise an algorithm DBSCAN* (similar to DBSCAN) that conceptually finds clusters as the connected components of a graph in
  which the objects of X are vertices and every pair of vertices is adjacent if and only
  if the corresponding objects are ε-reachable w.r.t. user-defined parameters ε and mpts.
  Noncore objects are labeled as noise.