I’m trying to cluster some unlabeleded unweighted undirected graphs. I’d like to calculate some scalar features for each of them to build an embedding vector and then use a clustering algorithm to see if they can be distinguished in an unsupervised way. However, most of the features i was planning to use (closeness/betweenness centrality, clustering coefficient) are quite hard to compute and i don’t have access to any significant hardware.

What are some representative features of the graphs that have a lower computational complexity to be extracted? Say, around O(n) or O(m)

For this task i’m using the python library networkx