Algorithm to infer tag hierarchy

Question

I'm looking for an algorithm to infer a hierarchy from a set of tagged items.

E.g. if the following items have the tags:

1 a
2 a,b
3 a,c
4 a,c,e
5 a,b
6 a,c
7 d
8 d,f

Then I can construct an undirected graph (or graphs) by tallying the node weights and edge weights:

 node weights  edge weights

 a 6           a-b 2
 b 2           a-c 3
 c 3           c-e 1
 d 2           a-e 1  <-- this edge is parallel to a-c and c-e and not wanted
 e 1           d-f 1
 f 1

The first problem is how to drop any redundant edges to get to the simplified graph? Note that it's only appropriate to remove that redundant a-e edge in this case because something is tagged as a-c-e, if that wasn't the case and the tag was a-e, that edge would have to remain. I suspect that means the removal of edges can only happen during the construction of the graph, not after everything has been tallied up.

What I'd then like to do is identify the direction of the edges to create a directed graph (or graphs) and pick out root nodes to hopefully create a tree (or trees):

 trees         

    a        d 
  // \\      | 
 b     c     f 
        \      
         e     

It seems like it could be a string algorithm - longest common subsequences/prefixes - or a tree/graph algorithm, but I am a little stuck since I don't know the correct terminology to search for it.

Answer 1

This is what I've come up with. For my data, it's fast enough and the results are what I was after.

1. First, construct a tree where nodes are not necessarily unique, all nodes must share a "root" tag (in this case 'a') so partition returns just one tree, in pseudo-python:

   nodes = [[a,b], [a,c], [a,b,d], [a,b,d,e], [a,c,e], [a,c,d,e]]
   
   tree = partition(nodes)[0]
   
   def partition(self, nodes, parent=None):
       children = []
       while nodes:
           pivot, count = most_frequent_tag(nodes)
           if not pivot:
               break
   
           left = [node for node in nodes if pivot in node]
           right = [node for node in nodes if pivot not in node]
           child = Node(pivot, count, parent=parent)
           child.children = partition([[tag for tag in node if tag != pivot]
                                       for node in left],
                                      parent=child)
           children.append(child)
           nodes = right
       return children
   
   def most_frequent_tag(nodes):
       ...
       return tag, count
   
   class Node(object):
       def __init__(self, tag, count, parent=None):
           self.tag = tag
           self.count = count
           self.parent = parent
           self.children = []
   

   This results in the tree:

      a (6)
     /    \
   b (3)  c (3)
    |      |
   d (2)  e (2)
    |      |
   e (1)  d (1)
   

2. The nodes in this tree have to be reordered for it to turn into an acyclic graph, so swap any parent-child relationships where the child occurs more frequently than the parent (any metric will do though). When they have the same frequency, ensure the parent has the lower tag (alphabetically).
   This is a little tricky as the parent node may have to be split if it's count > than the child count.

   tree.check_order()
   
   def Node.check_order(self):
       new_children = []
       for child in self.children:
           swaps.extend(child.check_order())
           if not self.in_order(child):
               # add child to parent, self to child
               new_child = Node(child.tag, child.count, self.parent)
               new_self = Node(self.tag, child.count, new_child)
               self.count -= child.count
               new_self.children = child.children
               new_child.children.append(new_self)
               self.parent.children.append(new_child)
           else:
               new_children.append(child)
       self.children = new_children
   

   The new tree now looks like:

         a (6)
        /    \
      b (3)   c (3)
     /    \     \
   d (2)  e (1)  e (2)
           |      |
          d (1)  d (1)
   

Once that's complete, the tree can be traversed to create a list of graph edges (there may be some duplicates) or a co-occurrence matrix.

Answer 2

To solve this problem it is important to consider how you want to represent the Graph. In your sketch you have assigned a weight both to nodes and to edges, but it seems that the edge weight is irrelevant. A good representation might be a pair of the weight and an array of neighbours:

Node(weight: Int, name: String, neighbours: Set of Node)

During the building of the initial undirected graph, you maintain a dictionary of nodes by their name.

For each path in the input, you look up or create all nodes in the dictionary. You then increment the weight of all nodes, and connect the nodes on each pair of the graph to each other:

var nodes = path.split("-").map(s => dict.lookupOrCreate(s));
// increment the weight
for var node <- nodes { node.weight++ }
// add the connections
for var i <- (1 upto nodes.length) {
  nodes[i  ].neighbours.add(nodes[i-1]);
  nodes[i-1].neighbours.add(nodes[i  ]):
}

We now have an undirected, unconnected graph with weighted nodes:

2   6   3   1   2   1
b ↔ a ↔ c ↔ e   d ↔ f
     ↖_____↗

It is now that you will want to remove cycles. Your example contains the subgraph

  e 1        I.  a6 → e1 → c3     ↗ e1
 / \    ==>                     a6     III.
a 6 |        II. a6 → c3 → e1     ↘ c3
 `- c 3

As you can see, there are three possibilites to eliminate this cycle while starting from a. The 3rd possibility is the easiest to implement.

If you want one of the other orders, you'll have to do more expensive reachability tests: For each two child nodes, skip (but not mark as seen) one of those child nodes if it is reachable by the other without using a path that uses the current node.

Next, we want to get the node with the highest weight. This is a simple sort.

var [..., highest] = dict.values.sortBy(n => n.weight);

Now, we traverse the whole graph starting from that node and build the DAG. We can either build a completely new graph (preferable) or remove the current node from the neighbour set. If this set then contains any nodes that were already visited during DAG buidling, a cycle was detected (which we break by skipping that node). Subgraphs that are not reachable will be forgotten, this would eliminate the d-e part. We can work around of this by deleting any nodes from the dictionary, and creating DAGs until the dict is empty. This would create a forest.

var forest = collect until dict.isEmpty {
  var [..., highest] = dict.values.sortBy(n => n.weight);

  def recurse(node: Node): DagNode {
    // remove current node from dict
    dict.delete(node.name);

    // remove seen childs – eliminates cycles
    var childs = node.neighbours.filter(c => dict.contains(c.name));
    // mark all new childs as seen
    for var child <- childs { dict.delete(child.name) }

    // return the DAG subgraph (here: tree) and recurse into each child
    return DagNode(weight: node.weight,
                   name:   node.name,
                   childs: childs.map(c => recurse(c)));
  }

  yield recurse(highest);
}

This should create the forest

  _a_    d
 / | \   |
b  c  e  f

Answer 3

There's a family of data mining algorithms called decision tree analysis or decision tree learning. The Wikipedia page explains how it is used to create a graph that represents a given data set. Once the algorithm creates the model, it can be used to predict missing characteristics of new data points.