Clustering Graphs using graph distance
What I'm currently doing is:

Train a GNN and see which graphs are labelled wrongly compared to the ground truth.
Use a GNN-explainer model to help explain which minimum sub-graph is responsible for the mislabeling by checking the wrongly label instances.
Use the graph_edit_distance from networkx to see how much these graphs differentiate from another.
See if I can find clusters that help explain why the GNN might label some graphs wrongly.

Does this seem reasonable?
How would I go around step 4? Would I use something like sklearn_extra.cluster.KMedoids?
All help is appreciated!


Use the graph_edit_distance from networkx to see how much these graphs
differentiate from another.

Guessing this gives you a single number for any pair of graphs.
The question is: on what direction is this number?  How many dimensions ( directions ) are there?  Suppose two graphs have the same distance from a third.  Does this mean that the two graphs are close together, forming a cluster at a distance from the third graph?
If you have answers to the questions in the previous paragraph, then the KMeans algorithm can find clusters for as many dimensions as you might have.  It is fast and easy to code, usually giving satisfactory results. https://en.wikipedia.org/wiki/K-means_clustering
