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.

Does the resulting graph have to be a DAG? If so, the problem (if you want to accept the maximum number of edge insertions) generalizes the NP-hard Feedback Arc Set problem, and will probably be hard to solve optimally. But this depends on what the actual objective is. — Falk Hüffner
@FalkHüffner yes, it has to be a DAG. I have heard about the solution you are proposing, however I am not able to apply it since I am not familiar with it. Nevertheless, I will update the question text. — Eleanore

Esoteric Screen Name Esoteric Screen Name · Accepted Answer · 2013-04-26T15:17:07

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.

Consensus on multiple graphs

2 Answers