# clustering data set based on the similarity of tree structure

I have a data set (>5000). each individual record of data is structured as a multilevel n-ary tree (>200 nodes). The tree node identifiers are unique within the tree. but the same identifiers are used to represent the same type of node across the data set. I would like to group the data set into multiple clusters based on the similarity between records. The records generally have a similar structure except some records have some branches pruned.

Here are some overly simplified examples.

basic type:
A - B - C
\- D - E - F
\- G - H - I
\- J

sample 1:
A
\- D - E - F
\- G - H - I
\- J

sample 2:
A - B - C
\- G - H - I
\- J

sample 3:
A - B - C
\- D - E - F
\- G - H - I


I have no idea how many different types of tree structures are there in the dataset. I guess it's about 10-30. This is why I want to have a better understanding of the dataset by clustering the dataset. I want 'clustering' because I want to allow small variations in a cluster so that I could have a controllable number of clusters for analysis purposes.

any thought? thanks

• so what is the actual question? How to cluster based on graph similarity? Jun 30, 2021 at 12:34
• how are you defining "similarity" here? Which pairs of those different samples would you want to be scored as having higher or lower similarity? My immediate thought is to calculate some graph features for each tree like average node degree, clustering coefficient, etc, and use a conventional similarity metric to compare trees in that feature space. But I don't know if that approach to "similarity" is useful for your problem. Jul 1, 2021 at 15:38
• In my case, I would like to see the 4 given graphs in different clusters. On one hand, I want to find out how many different graphs type. On the other hand, I want the flexibility to reduce the number of clusters when I need to. I guess the 'Similarity' is measured by the number of overlapping nodes. so, graphs will the least mismatch should be grouped into the same cluster. Jul 8, 2021 at 10:23

Since these trees are all subtrees (in the rooted sense) of some universal tree, you can go as simple as the size of the symmetric difference.

If your trees can have very different sizes, it might be beneficial to be more lax in measuring similarity of large trees compared to small trees; in that case, the Jaccard distance may work well.

Finally, you might want to care more about the actual tree structures. Consider:

basic type:
A - B - C
\- D - E - F
\- G - H - I
\- J

sample 2:
A - B - C
\- G - H - I
\- J

sample 4:
A - B
\- D - E
\- G - H
\- J


Samples 2 and 4 both have lost 3 nodes from the basic type, and so are the same distance from it according to either of my first two metrics. But for your use-case, maybe losing an entire branch is more or less different than losing three leaves. You can weight by distance from the root, or any number of other things, to accommodate these differences; just be careful if your clustering algorithm requires a strict metric that your weighting still satisfies the axioms.

You have to convert your data into graphs. There are tools like Networkx to create graphs that you can classify with functions from karateclub libraries, for example graph2vec.

To convert you data into graphs, you will want to parse your data structure to fit the networkx one.

import networkx as nx
G = nx.Graph()


Then make a loop taking the data following its hierarchical structure adding nodes or edges:

G.add_node(1)

Basically every network/tree can be seen as a NxN binary matrix where N is the number of nodes and where ever node i is connected to node j, x_ij would be 1. If you have directionality in your network you can also consider +1 versus -1. The third dimension would be your samples. Let's say you have M samples, you will end up with a 3d tensor NxNxM.