In this report we talk about outbreak detection sort of a reverse to influence maximisation. In influence maximisation we are trying to create a cascade and here we are studying detection of these cascades as quickly as possible. We also discuss how Develop an approximation algorithm for it, which is also a submodular optimisation problem. We also discuss a new data dependent bound on the solution quality that is valid for optimizing any submodular function. The guarantee that greedy hill climbing provides, that at least 63% of nodes from Optimal solution is data independent.

Real world use cases for outbreak detection include figuring out where to put sensors in a real city water distribution network, so that we can detect contamination as quickly as possible given the data on how contamination spreads in the network.

In information networks, which users/news sites should one follow to detect cascades as effectively possible.

Given a dynamic process spreading over a network we want to select a set of nodes to detect the process effectively and as quickly as possible.

We have two notions to consider one is utility of placing sensors and another is the cost of placing the sensors.

Some nodes can cause high impact outbreaks that might affect the most nodes, we try to measure this impact of contamination in terms of utility.

For each subset $S\subseteq V$ compute utility $f(S)$, S is set of nodes where we have the sensors.

We are given the graph G(V, E) and data about how outbreaks spread over the G, i.e for each outbreak i we know the time T(u, i) when the outbreak i contaminates node u.

In case of water contamination, we get T(u, i) from mechanical simulation flow and consumption. And in case of News, we get it from traces of the information flow, we collect lots of articles and trace them to obtain data about information flow form a given news site.

Our goal is to select a subset of nodes S such that it maximizes the expected reward given below

$\underset{S\subseteq V}{\max }=\sum _{i}P(i)f_i(S)$ subject to $cost(S)<B$

where $P(i)$ probability of outbreak i occuring and $f_i$ reward for detecting outbreak i using sensors S. Basically expected reward for detecting an outbreak over all possible outbreaks subject to our budget constraints B.

Reward can be one of the following

• Minimize time of detection
• Maximize number of detected propagations
• Minimize number of infected people

Cost can be thought as reading big blogs is more time consuming in case of information networks or the cost of placing a sensor in a remote location.

Objectives for outbreak detection

We consider penalty ${\pi }_i(t)$ for detecting outbreak i at time t.

For the rewards we specified above penalty can be given accordingly.

• While maximizing Time to detection DT, we consider the penalty for detecting at time t ${\pi }_i(t)=t$
• While maximizing number of detected propagations we consider penalty in terms of detection likelihood DL, how many contaminations did we detect. This is a binary outcome, whether we detect it or not. ${\pi }_i(t)=0\text{ and }{\pi }_i(\infty )=1$
• In case of minimizing number of infected people, we just consider the population affected as the penalty. ${\pi }_i(t)=$ number of infected nodes in outbreak i by time t.

In all these cases detecting sooner does not hurt, hence all these penalty functions are monotone.

From here we define $f_i(S)$ as penalty reduction

$f_i(S)={\pi }_i(\infty )-{\pi }_i(T(S,i))$

We formulated objective this way because f is a submodular function. maximizing $\pi$ would not be submodular but maximizing $f$ is a submodular function.

Adding a new node will lead to diminishing returns, hence making it submodular. In terms of f adding a new sensor helps less than it would help if we added the same sensor to a subset of the original S.

For all $A\subseteq B\subseteq V$ and a sensor $x\in V\backslash B$

$f(A\cup \{x\})-f(A)\ge f(B\cup \{x\})-f(B)$

For us to prove this we need to consider 3 cases, based on when A, B and x detected the outbreak.

Case 1

x is the last to detect, hence both A and B will not benefit, when $T(B,i)\le T(A,i)\le T(x,i)$

so $f_i(A\cup \{x\})=f_i(A)$ and $f_i(B\cup \{x\})=f_i(B)$, this implies $f_i$ is submodular $f(A\cup \{x\})-f(A)=f(B\cup \{x\})-f(B)=0$

Case 2

x detects after B but before A, when $T(B,i)\le T(x,i)\le T(A,i)$. x detects sooner than any node in A but after any node in B. So x only helps improve the solution in A but not in B.

$f_i(A\cup \{x\})-f_i(A)\ge 0=f_i(B\cup \{x\})-f_i(B)$

Case 3

x detects earlier than both A and B, where $T(x,i)<T(B,i)\le T(A,i)$. The inequality $f_i(A)\le f_i(B)$ is due to the fact that $f_i$ is a non decreasing function and A is a subset of B. So

$f_i(A\cup \{x\})-f_i(A)=[{\pi }_i(\infty )-{\pi }_i(T(x,i))]-f_i(A)\ge [{\pi }_i(\infty )-{\pi }_i(T(x,i))]-f_i(B)=f_i(B\cup \{x\})-f_i(B)$

From all the above cases we conclude that $f_i(.)$ is submodular which makes $f(.)$ also submodular cause $f(S)={\sum }_{i}P(i)f_i(S)$

Greedy Hill climbing for optimising submodular functions is near optimal with factor $(1-1/e)$, but this only works for unit cost case, where each sensor costs the same. But for us each sensor has a cost $c(s)$. And also hill climbing algorithm is slow, at each iteration we need to re-evaluate marginal gains of all the nodes whose runtime is $O(|V|.K)$ for placing K sensors.

CELF

CELF is an algorithm for optimizing submodular functions under cost constraints.

Naive way of doing Hill climbing in this case can be ignoring the sensor cost, repeatedly select sensor with highest marginal gain until we exhaust the budget. This results in a solution where the hill-climbing will result in is arbitrarily far from OPT, optimal solution.

You can see this by considering a node with reward r that costs the whole budget B, and rest of the nodes where reward is $r-ϵ$ and cost 1. The greedy algorithm will pick the first node to put a sensor for only minor increase in reward by exhausting the whole budget B. We ended up with a solution S with only one node, which is so far away from the Optimal solution.

Even greedily picking a new sensor location based on the benefit to cost ratio $s_i={\mathrm{argmax}}_{s\in (V\backslash A)}\frac{f(A_{i-1}\cup \{s\})-f(A_{i-1})}{c(s)}$ will result a obviously bad solution. You can see this by considering two sensors $s_1$ and $s_2$ where costs are $c(s_1)=ϵ,c(s_2)=B$ and benefits $f(s_1)=2ϵ,f(s_2)=B$. Accordingly the benefit cost ratios are $f(s_1)/c(s_1)=2,f(s_2)/c(s_2)=1$. If we select $s_1$ greedily based on this benefit to cost ratio we will end up with reward $2ϵ$ instead of B. This will be an arbitrarily bad solution when $ϵ\to 0$. In this case greedy algorithm incentivizes choosing nodes with very low cost, even when slightly more expensive ones can lead to much better global results.

Basically with cost in the picture we don't an optimisation metric that is a monotone.

CELF(Cost-Effective Lazy Forward-selection) is a two pass greedy algorithm. Where we compute solution $S^{\prime }$ that is benefit-cost greedy and solution $S^{\prime \prime }$ that is unit-cost greedy leading to our actual solution $S=\mathrm{argmax}(f(S^{\prime }),f(S^{\prime \prime }))$

CELF is near optimal with a factor of $1/2(1-1/e)$ [Krause&Guestrin, '05]. Using two clearly suboptimal solutions, but taking the best of the two is guaranteed to give a near-optimal solution.

Speeding up Hill-Climbing

Consider so far we picked the sensors till step i $S_i=\{s_1,\cdots ,s_i\}$, we now have to pick $s_{i+1}={\mathrm{argmax}}_{u}f(S_i\cup \{u\})-f(S_i)$. We are trying to maximise the marginal gain of adding u to $S_i$ lets call this ${\delta }_i(u)=f(S_i\cup \{u\})-f(S_i)$.

Using the submodularity property we can conclude that ${\delta }_i(u)\ge {\delta }_j(u)\text{ for }i<j\text{ since }{S}_i\subset S_j$

Marginal benefits ${\delta }_i(u)$ only shrink as i grows.

Lazy Hill Climbing

From above we can use ${\delta }_i$ as an upper bound on ${\delta }_j$ for all $j>i$

Everytime we keep the marginal benefits ${\delta }_i$ for all the nodes from the previous iterations. And reevaluate ${\delta }_i$ for only the top nodes. Re-order and prune.

We start by computing all the marginal benefits of adding each node to S. Say we added the node a, that gives us the best benefit into S. We sort the rest of the marginal gains, and compute marginal gains in the second step in that order. While computing if the marginal benefit of the first placed node in the second step is smaller than the marginal benefits of the rest, we reorder our sort list, and compute the marginal benefit of the second placed node and etc. And when we found the node with the best marginal benefit out of all the sorted nodes, we put it in S, and move to the next iteration. In the worst case, its as good as the naive greedy hill climbing algorithm.

It's called lazy algorithm, because we only evaluate the marginal benefit, when we have to.

In practice CELF using lazy evaluation runs 700 times faster than greedy hill-climbing algorithm in the below example.

Data Dependent Bound

We know that we have a $(1-1/e)$ bound for submodular functions. And it's the worst case bound which is data independent. In some cases we might get solutions that are much better than 63%. We want to be able to have a better bound based on the input data.

Suppose S is some solution to $f(S)$ such that $|S|\le k$, and $OPT=\{t_1,\cdots ,t_k\}$ be the optimal solution. and for each node u $\delta (u)=f(S\cup \{u\})-f(S)$ be the marginal gain in f, by adding u to S.

If we order the marginal gains such that $\delta (1)\ge \delta (2)\ge \cdots$, then $f(OPT)\le f(S)+{\sum }_{i=1}^k\delta (i)$

we can prove the above statement as follows

$$\begin{gathered} f(OPT)\le f(OPT\cup S) \\ =f(S)+f(OPT\cup S)-f(S) \\ \le f(S)+{\sum }_{i=1}^k[f(S\cup \{t_i\})-f(S)] \\ =f(S)+{\sum }_{i=1}^k\delta (t_i) \\ \le f(S)+{\sum }_{i=1}^k\delta (i)\Rightarrow f(OPT)\le f(S)+{\sum }_{i=1}^k\delta (i) \end{gathered}$$

This is a data dependent bound because $f(S)$ and $\delta$ are based on the input, but it doesn't make any assumptions about how we got S. For some inputs this bound can be worse than 63%.

Using this inequality, we can have a data bound based on our data and how far away we are from the Optimal solution.

From the below image we can see how the greedy algorithm is performing based on both our original bound and the data dependent bound. As we can see our hill climbing approach was much more closer to the optimal solution after looking at the data-dependent bound. This is modeled on a real metropolitan area water network with 20k nodes and 25k edges. Using a cluster of 50 machines for a month, they simulated 3.6 million epidemic scenarios, by randomising locations, days and time of the day.

We can also see that placement heuristics perform much worse than CELF. Heuristics based on population, degree of nodes, flow, diameter and etc.

Chapters

1. Introduction, Structure of Graphs
2. Properties of Networks and Random Graph Models
3. Motifs and Structural Roles in Networks
4. Community Structure in Networks
5. Spectral Clustering
6. Message Passing and Node Classification
7. Graph Representation Learning
8. Graph Neural Networks
9. Graph Neural Networks - Pytorch Geometric
10. Deep Generative Models for Graphs
11. Link Analysis: PageRank
12. Network Effects and Cascading Behaviour
13. Probabilistic Contagion and Models of Influence
14. Influence Maximization in Networks
15. Outbreak Detection in Networks
16. Network Evolution
17. Reasoning over Knowledge Graphs
18. Limitations of Graph Neural Networks
19. Applications of Graph Neural Networks