Robust Sequence Networked Submodular Maximization

We wish to design an algorithm that is robust against the removal of an arbitrary subset of $\tau$ selected elements. In this paper, we propose the RoseNets Algorithm, which can approximately solves the RoseNets problem and is shown in Algorithm 1. Note we consider the case that $k\geq 3$.

The limitation of the Sequence Greedy algorithm is that the selected sequence is vulnerable. The overall utility might be concentrated in the first few elements. Algorithm 1 is motivated by this key observation and works in two steps. In Step 1 (the first while loop), we select a sequence $\sigma_{1}$ of $\tau$ elements from $V$ in a greedy manner as in Sequence Greedy. In Step 2 (the second while loop), we select another sequence $\sigma_{2}$ of $k-\tau$ elements from $V\backslash\sigma_{1}$, again in a greedy manner as in Sequence Greedy. Note that when we select sequence $\sigma_{2}$, we perform the greedy selection as if sequence $\sigma_{1}$ does not exist at all. This ensures that the value of the final returned sequence $\sigma=\sigma_{1}\oplus\sigma_{2}$ is not concentrated in either $\sigma_{1}$ or $\sigma_{2}$. The complexity of Algorithm 1 is $O(k|E|)$, which is in terms of the number of function evaluations used in the algorithm.

To show the differences and benefits of the RoseNets algorithm, we go back to see the example in Figure 2. When $k=5$ and $\tau=2$, the RoseNets algorithm will select the sequence $\sigma_{1}=\langle A,B\rangle$ and sequence $\sigma_{2}=\langle C,D,G\rangle$. When selecting $\sigma_{2}$, the RoseNets algorithm would not consider element $B$ in $\sigma_{1}$. Thus element $E$ and $F$ are regarded as making not contribution to the utility function. The RoseNets algorithm will return the sequence $\sigma=\langle A,B,C,D,G\rangle$. The worst case of removing $\tau=2$ elements, is to remove $B$ and any one element in $\{C,D,G\}$. The residual utility is 0.5. Remember the case for Sequence Greedy algorithm, the residual utility of the worst case is 0. This example shows the benefits of the RoseNets algorithm.

Both the examples in Figure 1 and Figure 2 imply that a robust sequence should have complex network structure. The utility should not concentrate in a center element, but aggregated from all the edges among elements in the sequence. Such a robust sequence can only be selected by multiple trials of greedy selection, with the trials neglecting each other. Otherwise, the central element (if exists) with its high edge weight neighbors are probability selected, as node $B$ in Figure 2. If such a node is removed, the utility would slump. In this paper, we implement such intuitive strategy by using two trials of greedy selection. Intuitively, invoking more times of greedy selection trial may improve the approximation ratio. However, as we are to take a first step in the RoseNets problem while our theoretical analysis is already non-trivial, we leave the design of multi-part selection algorithm and the approximation ratio analysis for future works.

Let $\alpha=2d_{\text{in}}+1$, $\beta=1+d_{\text{in}}+d_{\text{out}}$, $\gamma=e^{\frac{k-3}{k-2}}$, $\eta=e^{\frac{k-2\tau-1}{k-\tau-1}}$. Note $d_{\text{in}}$ and $d_{\text{out}}$ are the maximum in and out degree of the network respectively. For convience, we denote $f(v|\sigma)$ and $f(\sigma^{\prime}|\sigma)$ as the marginal gain of attending $v$ and $\sigma^{\prime}$ to sequence $\sigma$ respectively. We denote $\sigma^{*}(V,k,\tau)$ as the optimal solution of the RoseNets problem with element set $V$, cardinality $k$ and robust parameter $\tau$, and $g_{\tau}(\sigma)$ be the minimum value of $f(\sigma)$ after $\tau$ elements are removed from $\sigma$.

In Theorem 1, it is hard to compare the two approximation ratios directly due to their complex mathematical expression. Thus we consider specific network setting to show the different advantages of the two terms.

First, it is easy to verify that both the two terms are monotonically increasing function of $k$. When $k=3$, we have $\frac{1-e^{-(1-1/k)}}{\alpha\beta}-\frac{\gamma^{\frac{1}{d_{\text{in}}}}-1}{\beta\gamma^{\frac{1}{d_{\text{in}}}}-1}=\frac{1-e^{-2/3}}{\alpha\beta}>0$. Thus we know that when $k$ is small, the first term is larger. When $k\to\infty$, the first term has a limit value of $(1-1/e)/\alpha\beta$, and the second term has a limit value of $\frac{e^{\frac{1}{d_{\text{in}}}}-1}{\beta e^{\frac{1}{d_{\text{in}}}}-1}$.When $d_{\text{in}}=1$, then $\alpha=3$ and $(1-1/e)/\alpha\beta-\frac{e^{\frac{1}{d_{\text{in}}}}-1}{\beta e^{\frac{1}{d_{\text{in}}}}-1}=(1-1/e)/3\beta-\frac{e-1}{\beta e-1}=\frac{-1-2\beta e+\frac{1}{e}+2\beta}{3\beta(\beta e-1)}<0$. In this case, the second term is larger than the first term in Theorem 1. Thus we can conclude that under specific network structure, the second term would be larger with large $k$.

Similarly, for Theorem 2, when $k=3$ and $\tau=1$, $\frac{1-e^{-(1-1/k)}}{\alpha\beta}-\frac{\tau\alpha\beta(\eta^{\frac{1}{d_{\text{in}}}}-1)}{\tau\alpha\eta^{\frac{1}{d_{\text{in}}}}-\beta(1-e^{-(1-1/k)})}=\frac{1-e^{-2/3}}{\alpha\beta}>0$. Thus we know when $k$ and $\tau$ is small, the first term is larger. When $k\to\infty$ while $\tau$ remains a constant, the first term has a limit value of $(1-1/e)/\alpha\beta$, the second term has a limit value of $\frac{\tau\alpha\beta(e^{\frac{1}{d_{\text{in}}}}-1)}{\tau\alpha e^{\frac{1}{d_{\text{in}}}}-\beta(1-e^{-1})}$. When $d_{\text{in}}=1$ and $d_{\text{out}}<\frac{3\tau e^{2}}{e-1}-2$, then $\alpha=3$, $\beta<\frac{3\tau e^{2}}{e-1}$ and $(1-1/e)/\alpha\beta-\frac{\tau\alpha\beta(e^{\frac{1}{d_{\text{in}}}}-1)}{\tau\alpha e^{\frac{1}{d_{\text{in}}}}-\beta(1-e^{-1})}=\frac{(1-\frac{1}{e})(3\tau e-\beta(1-\frac{1}{e}))-9\beta^{2}\tau(e-1)}{3\beta(3\tau e-\beta(1-\frac{1}{e}))}<0$. In this case, the second term is larger than the first term in Theorem 2. Thus we can conclude that under specific network structure, the second term would be larger with large $k$.

According to the above analysis, we know that the value of $k$ and $\tau$, together with the network topology, significantly affect the approximation ratio. It would be an interesting future direction to explore how the approximation ratio change when the parameters and network topology change.

To prove the above two theorems, we need the following three auxiliary lemmas. Due to space limitations, we here assume Lemma 1, 2 and 3 hold and show the proof of Theorem 1 below. We provide the proofs of Lemma 1, 2, 3 and Theorem 2 in the supplementary material.

Given $\tau=1$, the selected sequence $\sigma_{1}$ has one element. And we have $\sigma_{2}=k-1$. Let $\sigma_{1}=\{v_{1}\}$. Then the final sequence is $\sigma=\{v_{1}\}\oplus\sigma_{2}$. Suppose the the removed vertex from the sequence is $z$.

First, we show a lower bound on $f(\sigma_{2})$:

The first inequality is due to the approximation ratio of Sequence Greedy algorithm for net-submodular maximization (Mitrovic et al. 2018). The second inequality is due to Lemma 3.

Now, we can see the removed element $z$ can be either $v_{1}$ or an element in $\sigma_{2}$. In the following, we will consider these two cases:

Case 1. Let $z=v_{1}$. Then we have

Case 2. Let $z\in\sigma_{2}$. We then further consider two cases:

Case 2.1. Let $f(\sigma_{2})\leq f(\sigma_{2}-z)$.

In this case, the removal does not reduce the overall value of the remaining sequence $\sigma_{2}-\{z\}$. Then we have

Case 2.2. Let $f(\sigma_{2})>f(\sigma_{2}-z)$.

We define $q=\frac{f(\sigma_{2})-f(\sigma_{2}-z)}{(d_{\text{in}}+d_{\text{out}})f(\sigma_{2})}$, to represent the ratio of the loss of removing element $z$ from sequence $\sigma_{2}$ to the value of the sequence $\sigma_{2}$. Obviously, we have $q\in(0,\frac{1}{d_{\text{in}}+d_{\text{out}}}]$ since $f(\sigma_{2})>f(\sigma_{2}-z)$.

First, we have

where $h(e_{z}^{\text{in}})$/$h(e_{z}^{\text{out}})$ are the edge that has maximum utility over all the incoming/outgoing edges of $z$. The first inequality is due to the fact that the marginal gain of a vertex $z$ to the prefix and subsequent sequence is at most $d_{\text{in}}h(e_{z}^{\text{in}})$ and $d_{\text{out}}h(e_{z}^{\text{out}})$. Then the second inequality follows intuitively.

Given Equation (4), we need to prove four inequalities for finally proving the theorem.

First, suppose the first vertex of $\sigma_{2}$ is $v_{2}$. By the monotonicity of function $f(\cdot)$ and Equation (4), we have

Given Equation (5), we have Inequality 1 as below.

Inequality 1:

We know $\max\{x,1-bx\}\geq\frac{1}{1+b}$ for $x\in(0,\frac{1}{b}]$ and $b>0$.³³3As $x$ is monotone increasing and $1-bx$ is monotone decreasing, the function achieves the maximum value when $x=1-bx$ Thus we have Inequality 2 as below.

Inequality 2: $\max\{q,1-(d_{\text{in}}+d_{\text{out}})q\}\geq 1/\beta.$

Note that the first two elements $v_{2},v_{3}$ in $\sigma_{2}$ satisfy that

Thus by replacing the parameters in Lemma 2 and Lemma 3, we have the following result, which implies Inequality 3.

Now define $\ell_{1}(q)=q\frac{\gamma^{\frac{1}{d_{\text{in}}}}-1}{\gamma^{\frac{1}{d_{\text{in}}}}-q}$ and $\ell_{2}(q)=(1-(d_{\text{in}}+d_{\text{out}})q)\frac{\gamma^{\frac{1}{d_{\text{in}}}}-1}{\gamma^{\frac{1}{d_{\text{in}}}}-q}\}\geq\frac{\gamma^{\frac{1}{d_{\text{in}}}}-1}{\beta\gamma^{\frac{1}{d_{\text{in}}}}-1}$. It is easy to verify that for $k\geq 3$ and $q\in(0,\frac{1}{d_{\text{in}}+d_{\text{out}}}]$, $\ell_{1}(q)$/$\ell_{2}(q)$ is monotonically increasing/decreasing. Note when $q=\frac{1}{\beta}$, $\ell_{1}(q)=\ell_{2}(q)=\frac{\gamma^{\frac{1}{d_{\text{in}}}}-1}{\beta\gamma^{\frac{1}{d_{\text{in}}}}-1}$. We consider two cases for $q$: (1) when $q\in(0,\frac{1}{\beta}]$, we have $\max\{\ell_{1}(q),\ell_{2}(q)\}\geq\ell_{2}(\frac{1}{\beta})$ as $\ell_{2}(q)$ is monotonically decreasing; (2) when $q\in(\frac{1}{\beta},\frac{1}{d_{\text{in}}+\text{out}}]$, we have $\max\{\ell_{1}(q),\ell_{2}(q)\}\geq\ell_{1}(\frac{1}{\beta})$ as $\ell_{1}(q)$ is monotonically increasing. Thus we have the Inequality 4 as below.

Inequality 4:

Combining Inequality 1, Inequality 2 and Equation (1), we can have the first lower bound in Theorem 1:

Combining Inequality 1, Inequality 3 and Inequality 4, we can have the second lower bound in Theorem 1:

Now we are done.

Using the Amazon Video Games review dataset (Ni, Li, and McAuley 2019), we conduct experiments for the task of recommending products to users. In particular, given a specific user with the first 4 products she has purchased, we want to predict the next $k$ products she will buy. We first build a graph $G=(V,E)$, where $V$ is the set of all products and $E$ is the set of edges between these products. The weight of each edge, $w_{ij}$, is defined to be the conditional probability of purchasing product $j$ given that the user has previously purchased product $i$. We compute $w_{ij}$ by taking the fraction of users that purchased $j$ after having purchased $i$ among all the users that purchased $i$. There are also self-loops with weight $w_{ii}$ that represent the fraction of users that purchased product $i$ among all the users. We focused on the products that have been purchased at least 50 times each, leaving us with a total of 9383 unique products. Also we select the users that have purchased at least 29 products, leaving use 909 users. We conduct recommendation task on these 909 users and take the average value of each evaluation metric.

Figure 3 shows the performance of the comparison algorithms using the accuracy score, sequence score and utility function value respectively. In Figure 3(a), 3(b), 3(c) and 3(d), we find that after the removal of $\tau$ elements, the RoseNets outperforms all the comparisons. Such results demonstrate that the RoseNets algorithm is effective and robust in real applications since accuracy score and sequence score are common evaluation metrics in practical. In Figure 3(e) and 3(f), the only difference is that the OMegA algorithm is outperforming when $\tau$ is small or $k$ is large. The OMegA algorithm aims to find a global optimal solution. It topologically resorts all the candidates after each element selection. It can return a solution with better utility function value when $k$ is large and $\tau$ is small, but runs much slower than RoseNets or Sequence. Also, it shows poor performance in accuracy and sequence score. Thus the RoseNets algorithm is more effective and robust in real applications.

In addition, we also show the case of RoseNets and Sequence with $\tau=0$. We can see that in all the experimental results for the three metrics, the RoseNets outperforms Sequence, which is consistent to our expectation. On utility function value, the Sequence($\tau=0$) is better than the RoseNets($\tau=0$). However, on accuracy score and sequence score, the RoseNets($\tau=0$) is very close to the Sequence($\tau=0$), sometimes shows better performance. The former result is due to the effectiveness of greedy framework. The RoseNets algorithm indeed invokes Sequence for two trials independently, which intuitively cannot achieve comparable performance with one trial Sequence execution, due to the Net-submodularity. But the latter result shows that directly implementing greedy selection is not always outperforming. This is due to the intrinsic property of the greedy algorithm. Though $1-1/e$ is almost the best approximation ratio, some heuristic algorithms may achieve better performance in specific cases. However, if we invoke more trials of Sequence algorithm, better robust experimental results and approximation ratio might be achieved but the utility value would become lower. This is because more trials of independent greedy selection would give high probability of triggering the diminishing return phenomenon. In real applications, this is a trade-off for designing robust algorithms that requires a balance between high efficiency on robustness and maximization of utility value.

Using the Wikispeedia dataset (West, Pineau, and Precup 2009), we consider users who are surfing through Wikipedia towards some target article. Given a sequence of articles the user has previously visited, we want to guide her to the page she is trying to reach. Since different pages have different valid links, the order of pages we visit is critical to this task. Formally, given the first 4 pages each user visited, we want to predict which page she is trying to reach by making a series of suggestions for which link to follow. In this case, we build the graph $G=(V,E)$, where $V$ is the set of all pages and $E$ is the set of existing links between pages. Similarly to the recommendation case, the weight $w_{ij}$ of an edge $(i,j)\in E$ is the probability of moving to page $j$ given that the user is currently at page $i$, i.e., the fraction of moves from $i$ to $j$ among all the visit of $i$. In this case, we build no self-loops as we assume we can only move using links. Thus we cannot jump to random pages. We condense the dataset to include only articles and edges that appeared in a path, leaving us 4170 unique pages and 55147 edges. We run the algorithm on paths with length at least 29, which leaves us 271 paths. We conduct link prediction task on these 271 paths and take the average value of each evaluation metric.

Figure 4 shows the performance of the comparison algorithms using the accuracy score, sequence score and utility function value respectively. In Figure 4, we find that after the removal of $\tau$ elements, the RoseNets outperforms all the comparisons in all the cases. These results demonstrate that the RoseNets algorithm is effective and robust in real applications. The OMegA algorithm does not show comparable performance to RoseNets algorithm any more. This is because that (1) the path need to be predicted is very long, and (2) the intersection part of different paths is not as large as the case in Amazon recommendation experiments. Thus the global algorithm OMegA cannot exploit its advantages. We still can find in Figure 4(a), 4(c) and 4(e) that when $k$ becomes larger, the performance of OMegA algorithm increases faster. This in turn demonstrates that the RoseNets algorithm is more general, effective and robust, which does not assume specific real application scenario.

Another difference in the link prediction application is that, the RoseNets($\tau=0$) outperforms Sequence($\tau=0$) almost in all the cases on accuracy and sequence score. This again verifies that directly implementing greedy selection may sometimes far away from the optimal solution. As discussed in the end of the recommendation case, an interesting future direction is to explore the trade-off between high efficiency on robustness and the maximization of utility value by invoking more independent greedy selection trials.

Lemma 1. There exists a vertex $v$ for sequence $\sigma_{1}$ and $\sigma_{2}$ satisfies that $f(v|\sigma_{1})\geq\frac{1}{d_{\text{in}}|\sigma_{2}|}f(\sigma_{2}|\sigma_{1})$.

Lemma 2. Consider $c\in(0,1]$ and $1\leq k^{\prime}\leq k$. Suppose that the sequence selected by the Sequence Greedy Algorithm is $\sigma$ with $|\sigma|=k$ and that there exists a sequence $\sigma^{\prime}$ with $|\sigma^{\prime}|=k-k^{\prime}$ such that $\sigma^{\prime}\subseteq\sigma$ and $f(\sigma^{\prime})\geq cf(\sigma)$. Then we have $f(\sigma)\geq\frac{e^{\frac{k^{\prime}}{d_{\text{in}}k}}-1}{e^{\frac{k^{\prime}}{d_{\text{in}}k}}-c}f(\sigma^{*}(V,k,0))$.