1
$\begingroup$

I am working on an algorithm that ranks a set of nodes in a graph with respect to how relative this node is to other predefined nodes (I call them query nodes). The way how the algorithm works is similar to recommendation algorithms. For instance, if i want to buy an item from an online store, the algorithm will look at my preferences (and/or history of purchased items) and recommend new items for me. Applying this to graph theory, the set of nodes are items and my preferred items are the query nodes. The problem am facing right now is how to benchmark my results (i.e. I want to run recall and precision on my results) but I don't have a ground truth data. My question is: does anyone know a benchmark for this problem, if not, how do you think I can evaluate my results.

Note: My algorithm has nothing to do with recommendation algorithms (i.e. the application is different), but I gave this to deliver the general idea of the RELATIVE IMPORTANCE algorithms. I am looking for any dataset with benchmark that may help me in this context.

Edit: Based on some requests, I will explain my algorithm with more details. The algorithm takes as input: graph (can be directed or undirected, weighted or unweighted), and a set of query nodes (included in the graph). The algorithm will try to rank the nodes in the graph according to their importance with respect to the query nodes. The importance of a node increases as the relationship between it and the query nodes increases. Depending on the application, this relationship is quantified by a value (the weight of an edge) that reflects the level of association between two nodes. For instance, in the DBLP co-authership dataset, the relation between two nodes is the number of common papers between the two nodes (authors). Therefore, in this case, the algorithm will rank the authors in the DBLP graph according to how close they are to all query nodes (the predefined authors). I hope that this is clear.

Thank you

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ This seems far too vague for anyone to answer. Your question is, essentially, "I have some algorithm that processes data. How can I benchmark it?" Can you be more precise? $\endgroup$
    – David Richerby
    Commented Oct 22, 2014 at 19:37
  • $\begingroup$ There is no clear question here. So I wont be able to recommend any dataset, however, I feel preflib.org is somehow related. You need to describe your problem precisely; What do you have? a (directed) graph? how you define relative importance algorithms? what do you expect the output to be? $\endgroup$
    – seteropere
    Commented Oct 22, 2014 at 21:51

2 Answers 2

Reset to default
1
$\begingroup$

You can for instance take as ground truth data the movielens dataset, remove some rating links between users and movies. You can rank your algorithm by counting the number of link that you can guess right. Usually machine learning algorithm also guess the rating score.

Improve this answer
$\endgroup$
0
$\begingroup$

The answer is: you can't. You cannot evaluate your results or your algorithm without ground truth data. The quality of your predictions is "the accuracy of your algorithm, when run on real-world data". This means that the only way you can evaluate the quality of your predictions is by looking at how accurate they are on realistic, representative data sets. This requires ground truth. If you don't have ground truth data, your first step is to acquire ground truth data -- without it, you're stuck.

Evaluating on randomly generated graphs is not a substitute for ground truth data. If you evaluate on synthetic data, all you learn is how accurate your algorithm is on synthetic data, but you have no way of knowing whether the synthetic data is representative of real-world data, so this might not tell you anything about how accurate your algorithm will be on real data. There's no free lunch.

Improve this answer
$\endgroup$
2
  • $\begingroup$ or rely on randomly generating graphs if there is no real world data. $\endgroup$
    – seteropere
    Commented Oct 22, 2014 at 22:03
  • 1
    $\begingroup$ Actually, no. That's not a substitute for ground truth data. If you evaluate on synthetic data, all you learn is how accurate your algorithm is on synthetic data, but you have no way of knowing whether the synthetic data is representative of real-world data, so this might not tell you anything about how accurate your algorithm will be on real data. There's no free lunch. $\endgroup$
    – D.W. ♦
    Commented Oct 22, 2014 at 22:45

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