How to Cluster Several Graphs? I'm relatively new to Graph Theory, but I'm wondering if I have a set of Graphs {G1, G2, ..., Gn}, are there any algorithms that allow for clustering these graphs? taking into account the nodes and edges present in each graph and their properties.
For example, having seven graphs, the output would be something like:
Cluster 0: G1, G5, G6
Cluster 1: G2, G4
Cluster 2: G3, G7
In this case, the set of Graphs is the same kind (Undirected, Directed, etc.), and is there any open-source implementation with these algorithms?
Or equivalent, are there any graph embeddings algorithms representing a whole graph like a k-dimensional vector? (fixed k for all graphs), so this embedding can be fed into classical algorithms like k-means, hdbscan, etc
 A: I do not believe there is a unique way to try to do this, nor do I think I could reasonably enumerate the possibilities. But I will mention some here to get you started.
Define a metric on graphs
One approach that should allow you to use a variety of clustering algorithms is to provide a distance matrix. This can be achieved with the graph edit distance. Wikipedia mentions that the time complexity for this will be cubic if you use modern shortest path algorithms such as A*.
Define a metric on a feature extracted from graphs
Another approach is to convert your graphs into some other representation. The first two methods are highly similar, while the third is works on a somewhat different principle.
The first method is to identify a collection of vertex-induced subgraphs of your graphs of interest that are mutually non-isomorphic. These are called "graphlets" in the literature. For each graph you can construct a vector of the counts of how many times each graphlet occurred in a graph. With vectors representing lossy representations of your original graphs, there are lots of algorithms and metrics for clustering collections of vectors.
The second method builds on the first. For a given graphlet, one may notice the existence of automorphism orbits from that graphlet to itself. One can count how many times each automorphism orbit from each graphlet can be found in each of your graphs. Again, one can choose an ordering on these quantities to put into a vector. With such a vector describing some of the structural details of each graph, one can again turn to conventional clustering methods.
For both the above representations, often only graphlets of 2-5 vertices are chosen because the computationally complexity increases with the size of the graphlets you consider. You'll find that just as people have distinguished graphs as simpled, signed, or directed, one can also find notions of simple, signed, or directed graphlets in which automorphisms must preserve those properties. And people also distinguish graphs, multigraphs, and hypergraphs, and you'll likewise find in the literature that there are similar methods for all of these.
The third method is to compute the degree distribution of the vertices of each graph. This approach loses a lot of information about the original graphs compared to the previous two methods. From there you could define vectors representing the counts of each degree from which you could use one of many metrics, or you could compute one of a variety of divergences (preferably a symmetric one to make it more metric-like) that can also be used for clustering.
Beyond this, there are a variety of functions defined on graphs (e.g. centrality) that can also induce distributions for which this third approach would also work. Instead, some functions assign a score to the entire graph, such as arboricity score, that could be clustered. Each such choice depends on whether you're interested in interpreting groupings of graphs based on a particular score. If you are going to consider whether graphs group together by some notion of similarity or disimilarity, this requires defining in what sense you mean that.
References
"Efficient Graphlet Counting for Large Networks", https://ieeexplore.ieee.org/document/7373304
"A combinatorial approach to graphlet counting", https://academic.oup.com/bioinformatics/article/30/4/559/205331
"Enumeration of Automorphism Orbits of Graphlets | HackSeq | Talk", https://www.youtube.com/watch?v=vY1UkCPSKH8&ab_channel=GalenSeilis
"Efficient enumeration of small graphlets and orbits.", https://www.bac-lac.gc.ca/eng/services/theses/Pages/item.aspx?idNumber=1287015316
"Algorithm and application for signed graphlets", https://dl.acm.org/doi/10.1145/3341161.3343692
"Classification in biological networks with hypergraphlet kernels", https://arxiv.org/abs/1703.04823
