Consensus on multiple graphs

Question

Let G = (V,E) be a Directed Acyclic Graph (DAG). V is the set of vertexes, while E is the set of edges.

Now, suppose that G is corrupted by some annotators in a crowd, according to the crowdsourcing paradigm:

• Some of them may decide to remove some edge e belonging to E
• Some of them may decide to add an edge e which was not existing

The result of the work of an annotator i is a graph whose set of vertexes V is the same as the original one and whose set of edges Ei may differ from the original one. If n is the number of annotators, we come up with n different graphs, having the same set of vertexes V, but a different set of edges E. Let G1 = (V,E1), ..., Gn = (V,En) be the set of graphs.

I would like to know whether there is a way of merging these graphs, so as to find a consensus on the presence/absence of each possible edge e between two vertexes v1,v2 in V. The purpose of this operation is the one of fusing the opinion of each annotator about the construction of the set of edges E in the graph G. The final graph has to be a DAG.

Answer 1

For each edge count the number of graphs that contains it. If it is greater than some threshold, assume it was an original edge.

You may face some problems if some of the actions are biased. That is, each user does not randomly choose a particular edge to act upon.

Answer 2

Let...

• U be the distinct union of all Ei sets plus the original set E
• T be some arbitrary threshold value
• H(x) be some heuristic function
• F be the final consensus set of edges

Pseudocode:

for each Edge e in U
   if H(e) >= T then F.Add(e)

The question is then of course how to define your heuristic function. A naive approach would be set based voting. Count the number of E sets containing the edge, and if enough people agree that it's in the graph, include it. This is a simple and efficient function to implement. Some weaknesses of this heuristic are its inability to detect and compensate for bad annotators or small crowd sizes.