A Note on Valid Inequalities for PageRank Optimization with Edge Selection Constraints

Consider a feasible point $(\hat{\mathbb{y}},\hat{\theta})$ to the RMP (2). We show that $(\hat{\mathbb{y}},\hat{\theta})$ satisfies the inequality (2.1) for any $\bar{\mathbb{y}}\in\mathcal{Y}\cap\mathbb{B}^{|Z|}$ with the associated $\hat{Y}\neq\bar{Y}$. Because of $\hat{Y}\neq\bar{Y}$, there exists two cases: at least one edge of $\bar{Y}$ that is not in $\hat{Y}$, or at least one edge of $\hat{Y}$ that is not in $\bar{Y}$ for the inequality (2.1).

• Case 1:

  For the case where at least one edge of $\bar{Y}$ is not in $\hat{Y}$, there are two possible results in the term $(\gamma(\emptyset,\{(i,j)\})-\mathcal{FR}(\bar{\mathbb{y}}))(1-\hat{y}_{(i,j)})$ when $\hat{y}_{(i,j)}=0$ for an edge $(i,j)\in\bar{Y}\setminus\hat{Y}$. We let $(i,j)_{0}^{\prime}$ and $(i,j)_{0}^{\prime\prime}$ denote two edges in $\bar{Y}\setminus\hat{Y}$ for the two results, where the associated variables $\hat{y}_{(i,j)_{0}^{\prime}}=\hat{y}_{(i,j)_{0}^{\prime\prime}}=0$ in $\hat{\mathbb{y}}$ with the conditions $(\gamma(\emptyset,\{(i,j)_{0}^{\prime}\})-\mathcal{FR}(\bar{\mathbb{y}}))(1-\hat{y}_{(i,j)_{0}^{\prime}})<0$ and $(\gamma(\emptyset,\{(i,j)_{0}^{\prime\prime}\})-\mathcal{FR}(\bar{\mathbb{y}}))(1-\hat{y}_{(i,j)_{0}^{\prime\prime}})\geq 0$. Here, since $\hat{\mathbb{y}}$ must includes at least one $\hat{y}_{(i,j)_{0}^{\prime}}=0$ or $\hat{y}_{(i,j)_{0}^{\prime\prime}}=0$, we have $\gamma(\emptyset,\{(i,j)_{0}^{\prime\prime}\})=\min\{\mathcal{FR}(\mathbb{y}):y_{(i,j)_{0}^{\prime\prime}}=0,\mathbb{y}\in\mathbb{B}^{|Z|}\}\leq\mathcal{FR}(\hat{\mathbb{y}})$ and $\gamma(\emptyset,\{(i,j)_{0}^{\prime}\})=\min\{\mathcal{FR}(\mathbb{y}):y_{(i,j)_{0}^{\prime}}=0,\mathbb{y}\in\mathbb{B}^{|Z|}\}\leq\mathcal{FR}(\hat{\mathbb{y}})$. In other words, both $\gamma(\emptyset,\{(i,j)_{0}^{\prime\prime}\})$ and $\gamma(\emptyset,\{(i,j)_{0}^{\prime}\})$ represent the relaxation of $\mathcal{FR}(\hat{\mathbb{y}})$.

• Case 2:

  Similar to the discussion in the previous case, we have another situation that at least one edge of $\hat{Y}$ is not in $\bar{Y}$. To put it briefly, let $(i,j)_{1}^{\prime}$ and $(i,j)_{1}^{\prime\prime}$ be possible edges in $\hat{Y}\setminus\bar{Y}$, where the associated variables $\hat{y}_{(i,j)_{1}^{\prime}}=\hat{y}_{(i,j)_{1}^{\prime\prime}}=1$ of $\hat{\mathbb{y}}$ with $(\gamma(\{(i,j)_{1}^{\prime}\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))\hat{y}_{(i,j)_{1}^{\prime}}<0$ and $(\gamma(\{(i,j)_{1}^{\prime\prime}\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))\hat{y}_{(i,j)_{1}^{\prime\prime}}\geq 0$. Both $\gamma(\{(i,j)_{1}^{\prime\prime}\},\emptyset)=\min\{\mathcal{FR}(\mathbb{y}):y_{(i,j)_{1}^{\prime\prime}}=1,\mathbb{y}\in\mathbb{B}^{|Z|}\}\leq\mathcal{FR}(\hat{\mathbb{y}})$ and $\gamma(\{(i,j)_{1}^{\prime}\},\emptyset)=\min\{\mathcal{FR}(\mathbb{y}):y_{(i,j)_{1}^{\prime}}=1,\mathbb{y}\in\mathbb{B}^{|Z|}\}\leq\mathcal{FR}(\hat{\mathbb{y}})$ are the relaxation of $\mathcal{FR}(\hat{\mathbb{y}})$.

We demonstrate the validity of the following inequalities for a point $(\hat{\mathbb{y}},\hat{\theta})$ based on the discussion in Cases 1 and 2.

Based on the relations $(\gamma(\emptyset,\{(i,j)_{0}^{\prime\prime}\})-\mathcal{FR}(\bar{\mathbb{y}}))\geq 0$ with $\mathcal{FR}(\hat{\mathbb{y}})\geq\gamma(\emptyset,\{(i,j)_{0}^{\prime\prime}\})$ and $(\gamma(\{(i,j)_{1}^{\prime\prime}\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))\geq 0$ with $\mathcal{FR}(\hat{\mathbb{y}})\geq\gamma(\{(i,j)_{1}^{\prime\prime}\},\emptyset)$, we conclude $\mathcal{FR}(\hat{\mathbb{y}})\geq\gamma(\emptyset,\{(i,j)_{0}^{\prime\prime}\})\geq\mathcal{FR}(\bar{\mathbb{y}})$ and $\mathcal{FR}(\hat{\mathbb{y}})\geq\gamma(\{(i,j)_{1}^{\prime\prime}\},\emptyset)\geq\mathcal{FR}(\bar{\mathbb{y}})$ for the validity of the inequality (6), where the inequality (6) can also be regarded as $\hat{\theta}\geq\mathcal{FR}(\hat{\mathbb{y}})\geq\mathcal{FR}(\bar{\mathbb{y}})+0\times(1-\hat{y}_{(i,j)_{0}^{\prime\prime}})+0\times y_{(i,j)_{1}^{\prime\prime}}$. The inequality (7) follows from the relations $\mathcal{FR}(\hat{\mathbb{y}})\geq\gamma(\emptyset,\{(i,j)_{0}^{\prime}\})=\mathcal{FR}(\bar{\mathbb{y}})+(\gamma(\emptyset,\{(i,j)_{0}^{\prime}\})-\mathcal{FR}(\bar{\mathbb{y}}))(1-y_{(i,j)_{0}^{\prime}})$ with $(\gamma(\{(i,j)_{1}^{\prime}\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))<0$ and $\mathcal{FR}(\hat{\mathbb{y}})\geq\gamma(\{(i,j)_{1}^{\prime}\},\emptyset)=\mathcal{FR}(\bar{\mathbb{y}})+(\gamma(\{(i,j)_{1}^{\prime}\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))y_{(i,j)_{1}^{\prime}}$ with $(\gamma(\{(i,j)_{1}^{\prime}\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))<0$. The inequality (8) follows from $\min\{0,(\gamma(\emptyset,\{(i,j)\})-\mathcal{FR}(\bar{\mathbb{y}}))\}\leq 0$ for all $(i,j)\in\bar{Y}\setminus\{(i,j)_{0}^{\prime}\}$ and $\min\{0,(\gamma(\{(i,j)\},\emptyset)-\mathcal{FR}(\bar{\mathbb{y}}))\}\leq 0$ for all $(i,j)\in Z\setminus(\bar{Y}\cup\{(i,j)_{1}^{\prime}\})$. This completes the proof. ∎

Since $\min_{\mathbb{y}\in\mathbb{B}^{|Z|}}\mathcal{FR}(\mathbb{y})$ is a relaxation of both $\min\{\mathcal{FR}(\mathbb{y}):y_{(i,j)}=1,\mathbb{y}\in\mathbb{B}^{|Z|}\}=\gamma(\{(i,j)\},\emptyset)$ and $\min\{\mathcal{FR}(\mathbb{y}):y_{(i,j)}=0,\mathbb{y}\in\mathbb{B}^{|Z|}\}=\gamma(\emptyset,\{(i,j)\})$, we have $\gamma(\{(i,j)\},\emptyset)\geq\min_{\mathbb{y}\in\mathbb{B}^{|Z|}}\mathcal{FR}(\mathbb{y})$ and $\gamma(\emptyset,\{(i,j)\})\geq\min_{\mathbb{y}\in\mathbb{B}^{|Z|}}\mathcal{FR}(\mathbb{y})$ for all $(i,j)\in Z$. Because of $\min_{\mathbb{y}\in\mathbb{B}^{|Z|}}\mathcal{FR}(\mathbb{y})\leq\mathcal{FR}(\bar{\mathbb{y}})$, we have

and

hold for any $\bar{\mathbb{y}}\in\mathcal{Y}\cap\mathbb{B}^{|Z|}$. This completes the proof. ∎

Given $\bar{\mathbb{y}}\in\mathcal{Y}\cap\mathbb{B}^{|Z|}$, let $\alpha_{(i,j)}$ be a positive constant that $\alpha_{(i,j)}=-\min\{0,(\gamma(\emptyset,\{(i,j)\})-\mathcal{FR}(\bar{\mathbb{y}}))\}\geq 0$ for all $(i,j)\in\bar{Y}$. We aim to find an inequality

where $\beta_{(i,j)^{k}}\in\mathbb{R}$ is a valid coefficient for a variable $y_{(i,j)^{k}}$ for all $k=1$ to $|Z\setminus\bar{Y}|$. We first slightly modify the original lifting problem (9) into another lifting problem referred to as

We prove the validity of (13) for determing the inequality (12) using the fundamental concepts of lifting and mathematical induction. For the edge $(i,j)^{1}$ of an arbitrary ordering, the exact lift problem for the valid coefficient of $y_{(i,j)^{1}}$ in the inequality (12) is

which provides a valid $\beta_{(i,j)^{1}}=\tilde{\pi}_{(i,j)^{1}}(\bar{\mathbb{y}})$ for the inequality (12). Suppose that we have the valid $\tilde{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})=\beta_{(i,j)^{k}}$ for $k=1$ to $r-1$. Given that the coefficients $\beta_{(i,j)^{1}}=\tilde{\pi}_{(i,j)^{1}}(\bar{\mathbb{y}})$ to $\beta_{(i,j)^{r-1}}=\tilde{\pi}_{(i,j)^{r-1}}(\bar{\mathbb{y}})$ in the inequality (12)​ are valid, the exact lifting problem for determining the valid coefficient of $y_{(i,j)^{r}}$ in the inequality (12) is

which provides a valid $\beta_{(i,j)^{r}}=\tilde{\pi}_{(i,j)^{r}}(\bar{\mathbb{y}})$ for the inequality (12). Since the value $r\in\{1,\dots,|Z\setminus\bar{Y}|\}$ and the ordering $(i,j)^{1},(i,j)^{2},\dots,(i,j)^{|Z\setminus\bar{Y}|}$ are arbitrary, this confirms the validity of (13) for determing the inequality (12). Compared to (13), the modified lifting problem (11) removes the $\mathcal{Y}$ of $\eqref{lift_c3}$ and the terms $\sum_{(i,j)\in\bar{Y}}\alpha_{(i,j)}(1-y_{(i,j)})-\sum_{k=1}^{r-1}\tilde{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})y_{(i,j)^{k}}$ of the objective function. Since $\mathbb{y}\in\mathbb{B}^{|Z|}$ is the relaxation of $\mathbb{y}\in\mathcal{Y}\cap\mathbb{B}^{|Z|}$ shown in (9c), the term $\alpha_{(i,j)}\geq 0$ for all $(i,j)\in\bar{Y}$, and the term $\tilde{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})\leq 0$ for all $k=1$ to $|Z\setminus\bar{Y}|$, we conclude that $\hat{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})$ is the relaxation of $\tilde{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})$ and $\hat{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})\leq\tilde{\pi}_{(i,j)^{k}}(\bar{\mathbb{y}})$ for all $k=1$ to $|Z\setminus\bar{Y}|$. That is, for a feasible point $(\hat{\mathbb{y}},\hat{\theta})$, we have

This completes the proof. ∎

From Observation (1.1), the function $\gamma(\bar{S},\bar{N})$ in (3) can be solved in polynomial time for two exclusive subsets $\bar{S}\subseteq Z$ and $\bar{N}\subseteq Z$. Algorithm 1 solves the $\gamma$ function at most $|Z|$ times within the loops. This completes the proof. ∎

Given $\bar{\mathbb{y}}\in\mathcal{Y}\cap\mathbb{B}^{|Z|}$, we set up an arbitrary ordering $(i,j)^{1},(i,j)^{2},\dots,(i,j)^{|Z\setminus\bar{Y}|}$ for all elements in $Z\setminus\bar{Y}$. Note that given an arbitrary $(i,j)^{r}\in Z\setminus\bar{Y}$, we have $\min\{\mathcal{FR}({\mathbb{y}}):\eqref{lift_c1},\eqref{lift_c2},\mathbb{y}\in\mathbb{B}^{|Z|}\}=\gamma(\{(i,j)^{r}\},\{(i,j)^{r+1},\dots,(i,j)^{|Z\setminus\bar{Y}|}\})\geq\gamma(\{(i,j)^{r}\},\emptyset)$. Therefore, from the equation (11b), the relation