Optimal Tagging with Markov Chain Optimization
Many information systems use tags and keywords to describe and annotate content. These allow for efficient organization and categorization of items, as well as facilitate relevant search queries. As such, the selected set of tags for an item can have a considerable effect on the volume of traffic that eventually reaches an item. In tagging systems where tags are exclusively chosen by an item's owner, who in turn is interested in maximizing traffic, a principled approach for assigning tags can prove valuable. In this paper we introduce the problem of optimal tagging, where the task is to choose a subset of tags for a new item such that the probability of browsing users reaching that item is maximized. We formulate the problem by modeling traffic using a Markov chain, and asking how transitions in this chain should be modified to maximize traffic into a certain state of interest. The resulting optimization problem involves maximizing a certain function over subsets, under a cardinality constraint. We show that the optimization problem is NP-hard, but has a (1− 1 e )-approximation via a simple greedy algorithm due to monotonicity and submodularity. Furthermore, the structure of the problem allows for an efficient computation of the greedy step. To demonstrate the effectiveness of our method, we perform experiments on three tagging datasets, and show that the greedy algorithm outperforms other baselines.
The current paper is devoted to the problem of maximizing the probability of reaching a given vertex under a Markov random walk on a graph by adding a set of new incoming links from a given set of feasible links under a budget constraint. Authors prove that the problem is NP-hard and propose a greedy algorithm, which is reasonable due to the submodularity of the reaching probability with respect to the chosen set of links. Though the paper is clear and results look correct, the paper does not seem novel enough in the theoretical part and does not seem to have a proved impact for practical tasks. At this stage, I recommend to reject it.
Optimization of the link structure for PR is not a new topic. Apart from papers mentioned in Related work, there are also those not reviewed, including “PageRank Optimization by Edge Selection” by Csaji et al., “Maximizing PageRank with New Backlinks” by Olsen, “PageRank Optimization in Polynomial Time by Stochastic Shortest Path Reformulation” by Csaji et al.  **The novelty** of the study is questionable.  The probability of reaching the target state $\sigma$ can be viewed as the state’s stationary probability for the graph, where the added edges are directed to the state $\sigma$ and the matrix of transition probabilities is raised to an appropriate power. This observation does not immediately reduce the problem of the paper to a known task, however, it may partially explain the similarity between the theoretical part and the works of Olsen, where the stationary probability is maximized.     In particular, Section 4 resembles the work “Maximizing PageRank with New Backlinks” (not cited in the paper), where M. Olsen considered a reduction of a Markov chain optimization problem to the independent set problem, which is equivalent to the vertex cover problem.  Theorems 5.1, 5.3 are reasonable, but very simple and resemble Lemmas 1,2 from [15].  **The practical example** with tags and objects looks a bit questionable, because of the two reasons:  1) To use the proposed solution in practice, one needs first to choose the set of feasible tags for the object. It should be conducted with some objective, and we can assume that it is performed by some ranking algorithm on the graph. Note that the development of such an algorithm is the task of the current paper. Therefore, we can assume in practice that the feasible set coincides with the whole set of tags. Furthermore, this means that objects do not differ in the sense that the properties of the object are not taken into account in the problem formulation.  2) I did not get why maximizing the probability of reaching an item is a well-suited objective for the application. Why is it better than the PageRank value?   **Experiments:**  I would be appreciated to see a stronger baseline like the following one. Compute, for each tag $\tau$, the probability $P(\tau)$ of reaching $\tau$ for the Markov chain for the initial graph. Choose $k$ tags $\tau$ with the maximal value of $q_{\tau \sigma}^+ P(\tau)$. This heuristic seems to be an equivalent of the one in [15] (“high PageRank values compared to the outdegree”, see Fig. 1). Note that the Low degree baseline outperforms the High Degree one for all datasets according to Figure 1. While the degree of a tag itself is an ambiguous factor, a more complicates heuristic would perform much better.  **Other comments:**  The presentation could be significantly optimized in terms of space occupied by different parts. In particular, Abstract and Introduction could be shortened significantly. For example, some sentences are redundant: compere “When an item is tagged, positive probabilities are assigned to transitioning from the tag to the item and vice versa” at line 51 and “Intuitively, tagging an item causes probability to flow from the tag to the item, on account of other items with this tag.” at line 54. It is said 3 times that “the optimization problem is NP-hard” and so on.  Equation in step 5 of Algorithm 1 is something not standard.  The equation for $B$ in line 255 looks wrong.  **Questions:**  Could you compare the proof in Section 4 with the technique of Olsen? Is the idea of the proof in Section 4 still novel after the work of Olsen?  50: “Our framework can incorporate many web search click models [9, 3].” Which click models from [9] are incorporated in particular? I believe, that paper do not study any Markov chain models.  64: “we argue that maximizing the probability of reaching an item, as opposed to maximizing the proportion of time an infinite random walk spends in the item’s state, is a better suited objective for the applications we consider.” Why? I don’t think so and argue the opposite.   **Misspellings:**  46: “a a set” 79: "One the main roles" -> "One of the main roles" 84: “[5].While” Space is missed 111: Eq. 1: $\max_{S\in [n]}$ should be $\max_{S\subset [n]}$     ----- **UPDATE on Author Feedback**  - A: Thank you for suggesting the additional baseline - however it actually does appear in our paper (“One Step” in Fig. 1).  It implies from the text (l. 284) that One Step baseline is much simpler and definitely different from that I proposed. In fact, you obtain One Step baseline, if you substitute the *initial distribution* $\pi$ instead of the *probabilities $P(\tau)$ of reaching $\tau$* used in the baseline I proposed. I believe, 1) The scoring in my baseline is a better approximation of the true gain, 2) It is still much more efficient than the Greedy algorithm, 3) It is analogous to a baseline from [15].  - A: We agree that it would be practically wise to first select a feasible set of tags. However, we do not see this as a caveat, since finding a set of K potential tags with k << K << n seems like a very reasonable user-initiated preliminary step.  It is still not clear, which objectives could prevent a user from choosing K=n while not preventing from choosing K=k.   - A: As our model supports arbitrary transition probabilities from tags to items, these can be set according to click models. For instance, in the cascade model, for item i with rank r in tag t we set Pr(t -> i) = (1-p_1)*(1-p_2)*...*(1-p_{r-1})*p_r. We will elaborate on this.  Now this is clear. Still, I read [9] and believe this paper is NOT about cascade click models (unlike [3]). Please, be more precise.