3
$\begingroup$

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

$\endgroup$
5
  • 2
    $\begingroup$ There are myriad possible solutions. To choose among them, it would help to know what these graphs represent, how they are measured or observed, and what you hope to gain from the clustering. Since any graph on $n$ nodes can be represented by its $n\times n$ adjacency matrix, you automatically have a representation in a space of $n^2$ dimensions. Whether that is useful or not depends on those unnamed "properties" you wish to use in the clustering. For instance, this wouldn't work well if you wish to find clusters of isomorphic graphs (a difficult problem in any event). $\endgroup$
    – whuber
    Feb 2 at 20:39
  • 2
    $\begingroup$ @whuber is right. If you impose additional constraints on the graphs then the adjacency matrix may be an easily-calculated representation. The Frobenius norm would induce a metric on such matrices that could be used to construct a distance matrix. This would require that the graphs have the same number of vertices and that there is a chosen order on the vertices. The approaches I mention in my answer preserve the action of the permutation group on the (indexed) vertex set and allow the graphs to differ in size. $\endgroup$
    – Galen
    Feb 2 at 20:57
  • $\begingroup$ Thanks for the comments, it gives me an idea of what can be done, I found something that might suite my needs, the Graph2Vec algorithm, so the nodes and edges of a Graph can be represented as a vector, from there, I can use regular algorithms that work on structured data, or at least that is the idea $\endgroup$
    – Rodrigo A
    Feb 3 at 14:01
  • 2
    $\begingroup$ @RodrigoA Clearly from the name graph2vec, it is intended to convert graphs into vector representations. Be sure to read the paper to ensure that the representation is suitable for your current research question. $\endgroup$
    – Galen
    Feb 3 at 16:21
  • $\begingroup$ Thanks, I'll read it for sure $\endgroup$
    – Rodrigo A
    Feb 8 at 20:35

1 Answer 1

4
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ More generally, you can use graph kernels to compute the similarity between graphs (en.wikipedia.org/wiki/Graph_kernel). And there is a fourth method: whole graph embeddings allow you to project each graph in a vector space, and then apply a wider range of clustering methods (compared to the distance matrix). $\endgroup$ Feb 3 at 16:57
  • $\begingroup$ @VincentLabatut More general in what sense? How do graph kernels generalize enumeration of automorphism orbits, for instance? I do not see an inner product in such an enumeration, for example. $\endgroup$
    – Galen
    Feb 3 at 17:05
  • $\begingroup$ @VincentLabatut Yes, graph embeddings make sense prima facie. The OP appears to be interested in graph2vec. $\endgroup$
    – Galen
    Feb 3 at 17:07
  • $\begingroup$ @VincentLabatut Yes, there are other clustering methods that do not require distance matrices. Assumptions of a metric are sometimes relaxed to merely identity of indiscernibles and non-negativity. Perhaps further relaxations or restrictions are desirable in some instances. $\endgroup$
    – Galen
    Feb 3 at 17:12
  • 1
    $\begingroup$ you're right. I meant that there are other ways to compute a distance between graphs than the edit approach. I didn't mean graph kernels are a generalization of the methods you mentioned. Sorry for the imprecision! $\endgroup$ Feb 3 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.