An interesting approach to characterize graph topology, both locally and globally is to use a graphlet transform, there some interesting research happening around these types of topology signals, here's one that takes a very algebraic approach

https://github.com/fcdimitr/fglt