Security of Spectrum Learning in Cognitive Radios

Due to delay and energy constraints, a cognitive radio may not be able to perform spectrum sensing in all available channels. Therefore, a sensing policy is needed to decide which channels to sense. The channel selection problem is the problem of designing such a sensing policy to maximize throughput while avoiding interference to primary users. The channel selection problem can be formulated as a reinforcement learning problem. Channel selection schemes that employ reinforcement machine learning algorithms are vulnerable to belief manipulation attacks that contaminate the knowledge base of the learning algorithms. In this paper, we analyze the security of channel selection algorithms that are based on reinforcement learning and propose mitigation techniques that make these algorithms more robust against belief manipulation attacks.

I. INTRODUCTION
It is widely believed that cognitive radios (CRs) are one of the key technologies that can address the spectrum scarcity problem. It is expected that they will play an important role in maximizing spectrum utilization and help satisfy the QoS requirements of a number of important communications applications-from emergency first responders' public safety networks to military tactical networks. CRs often employ software-defined radio platforms that are capable of executing complex computational tasks to communicate efficiently without causing interference to licensed (a.k.a. primary) users. A specialized software module within a CR called the cognitive engine performs the aforementioned tasks, such as the optimization of the transmission/reception DRAFT arXiv:1304.0606v1 [cs.CR] 2 Apr 2013 (TX/RX) parameters and execution of spectrum sensing and spectrum access strategies. Most of the tasks performed by a cognitive engine require the use of machine learning algorithms, especially if those tasks need to be carried out in a distributed manner.
Considering the computing limitations and energy constraints of a battery-powered CR, a CR may not be able to perform full-spectrum sensing (i.e., sense all available spectrum bands) because of its prohibitive cost. Therefore, a spectrum sensing policy at the medium access control (MAC) layer is needed to decide which set of channels to sense. The channel selection problem is the problem of designing such a sensing policy. The optimal channel selection strategy for an unlicensed user (i.e., secondary user) is based on the availability statistics of the channels.
The availability of the channels is determined by the presence/absence of primary user signals in those channels. The channels' availability statistics are initially unknown to a secondary user and need to be estimated using sensing samples. The critical tradeoff that the cognitive engine faces in each timeslot is between transmission ("exploitation") on the channel that has the highest expected reward (e.g., throughput) and channel sensing ("exploration") to get more information about the expected rewards of the other channels. The exploitation vs. exploration tradeoff problem, such as the one just described, is central to an area of machine learning known as reinforcement learning.
Spectrum learning is the process of learning the spectrum statistics (i.e., primary user occupancy information), which is crucial to enable CRs to sense/interpret their spectrum environment and make intelligent decisions to achieve efficient communication. Although spectrum learning is beneficial for CRs, it can pose a serious security vulnerability. A radio that can learn has the potential to be taught by malicious entities in an adversarial environment. This kind of threat may have a long-lasting impact on the cognitive radio network.
As mentioned above, the design of the optimal sensing policy can be formulated as a reinforcement learning (RL) problem. When the channels are assumed to be independent, it can be formulated as a special class of RL problems known as a restless multi-armed bandit process.
Recent results (i.e., [1] - [4]) show that a surprisingly simple myopic policy that ignores the impact of the current action on the future reward is optimal when channels are identical. In this paper, we show that in adversarial environments, where an active attacker performs belief manipulation attacks against the machine learning algorithms executed on a cognitive engine, the myopic policy is no longer optimal and a softmax policy that exploits some level of randomness DRAFT outperforms the myopic policy.
Our contributions can be summarized as follows: 1) We derive closed-form expressions for the throughput of cognitive radios in an adversarial environment for the two-channel case in two channel selection policies, viz myopic policy and softmax policy.
2) We derive the attacker's optimal attack strategy and the cognitive engine's optimal defense strategy by solving respective optimization problems for more than two non-identical channels.
3) We identify and discuss two fundamental trade-offs in the security of spectrum learning: (1) the attackers tradeoff between the attack probability and the number of required observations for attack detection (i.e., the time that the attack detection system needs to detect an attack); and (2) the channel selection systems tradeoff between attack resilience and performance of a given channel selection policy. 4) We prove that for sufficiently large attack probabilities, a softmax policy with a proper choice of parameters outperforms the myopic policy for all possible attacker's strategies.
The rest of this paper is organized as follows. In Section II, the work related to this paper are discussed. Section III provides the channel selection system model and the attack model.
In Section IV, we analyze sensing policies in an adversarial environment for a cognitive radio system with two channels and Section V extends the result to a cognitive radio system with more than two channels. Finally Section VI concludes the paper.

II. RELATED WORK
The formulation of spectrum learning problem as a restless multi-armed bandit process is investigated in [1]- [6]. It is proved that when channels are identical and independent the myopic policy is the optimal policy [2]- [4], and that this policy is a special case of Whittle's index policy for the restless bandit problem which can be computed for non-identical channels as well [5]. An asymptotically optimal policy is proposed in [6] for a more realistic case where the policy does not require any prior statistical knowledge about the traffic pattern and the channels are different.
Despite all these work that assume a non-adversarial environment, this paper investigates the spectrum learning problem in an adversarial environment where active attackers aim to reduce the throughput of the cognitive radio network. DRAFT The security of machine learning algorithms that have been applied to applications such as intrusion detection systems (IDS) and spam filters is investigated thoroughly in [7]- [11]. In these papers, the authors discuss how an adversary can maliciously mistrain a learning system in an IDS and how an attacker may contaminate the knowledge base of a spam email filtering system to bypass the filtering. In [8] and [10] different kinds of attacks against machine learning algorithms are introduced and a variety of potential defenses against those attacks are proposed.
In the context of cognitive radios, security of machine learning algorithms that are used for signal classification are addressed in [18] and [19], but the types of learning algorithms that are analyzed is different from the algorithms in this paper. To the best of our knowledge, this paper describes the first analysis of a reinforcement learning algorithm's vulnerability against belief manipulation attacks to cognitive radios.

III. THE CHANNEL SELECTION SYSTEM AND THE ATTACK MODEL
In this section, we introduce the channel selection system and establish the attack model.

A. Channel Selection System Model
We consider a general dynamic spectrum access system where a user has access to N independent and stochastically non-identical parallel Gillbert-Elliot channels [12], and chooses one channel to sense and access in each time slot, aiming to maximize its expected long-term reward (i.e., throughput).
As illustrated in Figure 1, the state of the k-th channel-either idle (1) or busy (0)-indicates that the channel is unused by primary users or it is occupied. The transitions between these two states follow a Markov chain with transition probabilities {p k ij } i,j=0,1 . We assume that these transition probabilities for all channels are learnt in a non-adversarial environment before the system starts operating and thus the transition probabilities are known to the system. We also assume that p k 11 > p k 01 or equivalently the channel states in two consecutive time slots are positively correlated. Note that this assumption is only used for derivation of closed-form expressions and can easily be relaxed by separately considering the case where this assumption does not hold. Due to its limited sensing and access capability, a secondary user chooses one of the N channels to sense and access in each slot. Designing an optimal sensing policy that governs the channel selection at each time slot can be formulated as a restless multi-armed bandit process for independent channels. We denote S k (t) as the state of channel k in slot t that is given by the two-state Markov chain in Figure 1. Let S(t) = [S 1 (t), · · · , S N (t)] ∈ {0, 1} N denote the full system state. The channel selection system is reward-based. At each time slot the secondary user selects one of the N channels to sense. If the sensed channel is occupied by primary user signals, the user collects no reward; otherwise it accesses the channel and collects one unit of reward. The system keeps periodical sensing and transmitting on that channel until a primary user appears on the channel or a jamming attack prevents the user from transmission on the channel. The secondary user's aim is to maximize the throughput (reward) over a horizon of T slots by choosing an optimal sensing policy.
Due to limited sensing (i.e., sensing only one channel out of N channels), the full system state (S(t)) in slot t is not observable. However, it has been shown that a sufficient statistic for optimal decision making is given by the conditional probability that each channel is in state 1, given all past observations and decisions [13]. Referred to as the belief vector, we denote this sufficient statistic by Ω(t) = [ω 1 , · · · , ω N ], where ω k (t) is called the belief value of channel k which is equivalent to the conditional probability that S k (t) = 1 given all past observations and decisions for that channel. Given the sensing action a(t) = k (the channel that is selected to be sensed in slot t) and the observation S k (t) in slot t, the belief vector for slot t + 1 can be updated via Bayes rule through the following equation: DRAFT where Γ(x) = xp k 11 + (1 − x)p k 01 . A sensing policy π specifies a sequence of functions π = [π 1 , · · · , π t ], where π t maps the belief vector Ω(t) to a sensing action a(t). Multi-channel opportunistic access can thus be formulated as the following stochastic optimization problem: where π t (Ω(t)) is the channel selected for sensing and R πt(Ω(t)) (t) is the reward when the belief vector is Ω(t) and the action π t (Ω(t)) is taken, and Ω(1) is the initial belief vector. If no information about the initial system state is available, each entry of Ω(1) can be set to the stationary distribution ω k 0 of the underlying Markov chain: Let V t (Ω(t)) be the value function which represents the maximum expected total reward that can be obtained starting from slot t given the current belief vector Ω(t). Given that the user selects channel k and observes S k (t) in slot t, the maximum expected reward consists of the following two parts: 1) The expected immediate reward: 2) The maximum expected future reward: where τ (Ω(t)|k, S k (t)) denotes the updated belief vector for slot t + 1 as given in (1). If we maximize over all channel selections, we obtain the following optimization equation: Because the value function is limited to horizon T , we have: and V t (Ω(t)) = 0 for t > T . Theoretically, the optimal policy π * and its performance V 1 (Ω(1)) can be obtained by solving the above dynamic programming problem. However, because of the DRAFT impact of the current action on the future reward and the uncountable space of the belief vector, obtaining the optimal solution via the above recursive equations is computationally prohibitive.

B. Attack Model
We assume that there exists a single attacker in the environment who tries to decrease the throughput of secondary users by preventing them from transmission in some time slots, by employing adaptive interference techniques (or cognitive jamming attacks). Although many defenses against these attacks have been proposed, but none of these defenses is perfect or can address all classes of attackers. While such defenses can restrict the instantaneous effect of these attacks, they can not reduce the long-term effect of such attacks on cognitive radio network, when the network is using a learning system as part of its cognitive engine. These attacks gradually contaminate the knowledge base of a cognitive radio and lead the learning system to make wrong decisions which results in degrading the performance of the radio.
The attacker uses the same equipment as secondary users, i.e., it is equipped with a CR that is comparable to a typical secondary user's CR in terms of battery capacity, transmission power, computing power, memory capacity, etc. Therefore the attacker is power-limited and wish to avoid jamming continuously, which quickly drains power and causes fast detection by the attack detection module of cognitive engine. We also assume that the attacker can attack only one channel at each time slot. Suppose that the attacker perform attacks in t a slots out of T consecutive time slots on average. We denote α = ta T as the attack probability in the environment. The attacker controls the attack probability in order to cause maximal damage to the network in terms of throughput reduction. It can easily be seen that a higher attack probability will result in a lower throughput for the cognitive radio system.
We assume that the adversary possesses full knowledge about the network and its parameters.
We introduce the notion of the attacker's optimal strategy using the following definition: Definition 1: The attacker's α-optimal strategy is a strategy that minimizes the throughput of the target cognitive radio while keeping the attack probability fixed to value α.

C. Attack Detection Model
The cognitive radio network employs a mechanism for monitoring network status and detecting potential malicious activity. This monitoring mechanism is proposed in [20] to protect the network DRAFT against jamming attacks. The monitoring can be done by specific monitor nodes in a distributed network and a detection algorithm is employed by the detection module at a monitor node; it takes as input observation samples obtained by the monitor node (i.e., failed transmission/successful transmission) and decides whether there is an attack or not. On one hand the observation window should be small enough, such that the attack is detected in a timely manner and appropriate countermeasures are initiated. On the other hand, this window should be sufficiently large such that the chance of a false alarm or a mis-detection is reduced.
The sequential nature of observations at consecutive time slots motivates the use of sequential H 1 that denotes the hypothesis that assumes the existence of an attack has a Bernoulli p.m.f f 1 The logarithm of likelihood ratio at stage k with observations x 1 , · · · , x k is: where x i = 1, if the system observes a failed transmission at time slot i, and x i = 0 otherwise. DRAFT The decision variable is defined as follows: The analysis in [20] shows that using this SPRT, the average number of samples needed for detecting an attack is: where C is a fixed positive number. Using this equation for E[N |H 1 ] we have: Increasing the attack probability, α, increases the impact of the attack on the target (i.e., lower its throughput), but it also enables a detection module to detect the attack sooner. We define the attacker's cost as the inverse of E[N |H 1 ]: Also in order to normalize the attacker's cost, we assume that the constant C is equal to the maximum value of the statement θ 1 ln( θ 1 θ 0 ) + (1 − θ 1 ) ln( 1−θ 1 1−θ 0 ) that happens at α = 1, i.e. C = ln( 1 p 10 ), therefore: This definition for the attacker's cost shows that by risking detection of the attack by a detection module, the attacker's cost increases. The equation 4 would be used as a measure for the DRAFT attacker's cost in the rest of this paper.

CHANNELS
In this section, we analyze and compare the myopic policy [2] and the softmax policy [14] in a hostile environment for N = 2 identical channels, i.e. p 1 ij = p 2 ij = p ij .

A. Analysis of the Myopic Policy
The myopic policy explained in this section is identical to the one presented in [2], but in this section, we analyze the performance of this policy in an adversarial environment. A myopic policy ignores the impact of the current action on the future reward and only focuses on maximizing the immediate reward. At any given time slot t, the myopic policy for selecting a channel for sensing can be expressed as follows: In [3], the authors proved that for the channel selection system that was introduced in Section 2.1, the myopic policy is the optimal policy for all N . They also showed that the myopic policy has a simple structure that does not require the knowledge of the transition probabilities p ij or updates to the belief vector.
We define the steady-state throughput of the myopic policy as: where V m 1:T (Ω(1)) is the expected total reward obtained in T slots under the myopic policy when the initial belief vector is Ω(1). The key to computing the throughput U is to first find how long a user stays in the same channel. Let us introduce the concept of a transmission period (TP), which represents the time that a user stays in the same channel. Let L k denote the k-th TP. In [3], Zhao et al. showed that under the condition p 11 > p 01 , the steady-state throughput is: where L = lim K→∞ K k=1 L k K denotes the average length of a TP.
DRAFT Throughput analysis is thus reduced to analyzing the average TP length L. For N = 2, we can derive a closed-form expression of L as a function of the attack probability α, which leads to a closed-form expression of the myopic policy throughput U m (α).
Combining (9), (10) and (11) results in Substituting (12) into (11) and solving for λ 2 , we get λ 2 = ω(1 − p 11 (1 − α)), where ω is given in (7). From (12), we can find the stationary distribution as Using (13) to compute L m (α) = ∞ k=1 kλ k results in (6). Using the results of Theorem 1, we can show that U m (α) is a decreasing function of α, and thus an attacker can lower the target radio's throughput (which is employing myopic sensing) by increasing the attack probability α. However, as we discussed in Section 2.2, increasing α increases the probability that the attack is detected.

B. Analysis of the Softmax Policy
The softmax action selection policies are randomized policies where, at time t, the action a t is chosen at random by the user according to some probability distribution giving more weight to actions which have performed well in the past. The greedy action is given the highest selection probability, but all the others are ranked and weighted according to their accumulated rewards [14]. The most common softmax action selection method uses a Gibbs or Boltzman distribution for the action selection probabilities. It chooses action a at time slot t, with probability where τ is a positive parameter called the temperature and controls the greediness of the policy.
High temperatures cause all the actions to be all equiprobable while low temperatures cause a high probability for greedy action, and in the limit as τ → 0, the softmax policy becomes equivalent to the myopic policy. DRAFT In this section, for simplicity and ease of computation, we use a Bernoulli distribution instead of a Boltzmann distribution, i.e., we choose action a at time slot t with probability We define the main probability q as the probability of taking greedy action (i.e. selecting the channel that has the highest ω i ). According to the definition of q and the softmax policy, we have 0.5 ≤ q ≤ 1 when N = 2. Also note that for q = 1, the softmax policy reduces to myopic policy, i.e., myopic policy is a special case of softmax policy.
The attacker's optimal strategy for attacking a channel selection system employing the myopic policy is simple: only attack the channel that has the biggest belief value, since the user does not transmit on other channels. The attackers optimal strategy against the softmax policy is not so straightforward. As mentioned in Section 2.2, the α-optimal strategy for an attacker is a strategy that minimizes the throughput of a cognitive radio while keeping the attack probability α fixed. Knowing that the softmax policy uses a fixed main probability q for channel selection (i.e., it uses (14) for channel selection), the attacker divides its attacks between the two channels. We define d as the conditional probability of channel 1 (the greedy option for the policy) being attacked at a given timeslot, assuming that the timeslot is attacked and call it the division probability. Figure 2 illustrates the concept of the division probability (the slots colored in gray are the time slots in which an attacker jams a channel). The attacker chooses d such that a cognitive radios throughput is minimized. On the other hand the channel selection system exploits its knowledge about the DRAFT optimal strategy of the attacker to select the main probability q such that the throughput is maximized. Assume that U s (q, d) define the throughput of the radio when the softmax policy uses a main probability of q and the attacker exploits the division probability d, constructing optimal attack strategy and its corresponding optimal channel selection probability distribution can be formulated as the following optimization problems: Optimization Problem 1: Optimization Problem 2: The steady-state throughput of the softmax policy is given by: where V s 1:T (Ω(1)) is the expected total reward obtained in T slots under the softmax policy when the initial belief vector is Ω(1). As shown in Section 3.1, we only need the average TP length to compute the throughput for the softmax policy. Suppose that the attacker uses its optimal strategy. An analysis similar to what we did in section 2, results in the following theorem.
Theorem 2: For N = 2, the average TP average length for a softmax policy with main probability q is given by: where L m (·) is the function defined in (6) and L n (x) = 1 + p 01 (1−x) 1−p 11 (1−x) . Proof: Using a procedure similar to the one used in the proof of Theorem 1, we can readily show that if the channel selection algorithm always selects the channel with the smaller belief DRAFT value (which is the opposite of a greedy action), then the stationary distribution of {L k } ∞ k=1 is Using (15) to compute L n (α) = ∞ k=1 kλ k results in .
By using the Bayes rule and the statement of Theorem 1, we can obtain the statement of Theorem 2.
To quantify how much randomness is added to the channel selection system by the softmax policy, we use the entropy of the channel selection probability distribution, H. For the N = 2 case, because we use Bernoulli distribution, H = −(q ln(q) + (1 − q) ln(1 − q)). By changing q from 1 to 0.5, the entropy increases from 0 to its maximum value ln (2).
We denote U π (α) as the throughput of the cognitive radio, when it uses policy π for channel selection and the attacker uses its α-optimal strategy. We use the following definitions to quantify the robustness and the performance of policy π: Definition 2: The robustness of a policy π for a channel selection system under an α-optimal attack is: .

Definition 3:
The performance of a policy π for a channel selection system under an αoptimal attack is: P π = U π (0).

C. Numerical Results for two Channels
Using the results of Theorem 2, it can easily be shown that for α = 0, q * = 1, i.e., a non-adversarial environment the optimal softmax policy is equivalent to the myopic policy.
Solving the optimization problems 1 and 2 for other values of α is straightforward due to the problem's small solution space. Figure 3 shows the solutions to this problem for a range of attack probabilities. Because myopic sensing is a special case of softmax sensing, it is obvious that U s ≥ U m . Numerical results illustrated in Figure 3 shows that except for small values of α (α < 0.1), U s is strictly greater than U m , i.e., softmax sensing outperforms myopic sensing. Figure 4 shows the trade-off between the robustness and the performance of the system for fixed attack probability α = 0.5. As it can be seen, increasing the randomness that is used in ENVIRONMENT As mentioned in [2], because L k is a random process with higher-order memory, obtaining a closed-form expression of throughput for N > 2 channels with different statistics is very difficult. Nevertheless we can show that a softmax policy that uses a Boltzmann distribution with an intelligent choice for the temperature, τ , can outperform myopic policy for all possible strategies of the attacker, including its optimal strategy.
Assume that the channel selection system selects one of the N channels at each time slot.
When a channel is selected, the system keeps using that channel until a primary user begins to transmit on the channel. Suppose Ω(t) = (ω 1 (t), ω 2 (t), · · · , ω N (t)) is the belief vector of the system at time t and Q(t) = (q 1 (t), q 2 (t), · · · , q N (t)) is the corresponding probability vector, i.e. q i (t) = f i (Ω(t)) is the probability of selecting channel i at time t where f (·) is a function that maps the belief vector into a probability value. For the sake of notation simplicity, we omit t in the belief and and probability vectors henceforth. Without loss of generality, assume that ω N ≥ ω N −1 ≥ · · · ≥ ω 1 and consequently q N ≥ q N −1 ≥ · · · ≥ q 1 . As we mentioned in Section 2, the α-optimal strategy for the attacker is a strategy that minimizes the throughput while keeping the attack probability α fixed. In order to do so, the attacker needs to attack channel i with probability αd i , where d i is the division probability for channel i (i.e., the conditional probability of channel i being attacked at a given timeslot, assuming that the timeslot is attacked) which is a function of Q and Ω. Also to keep α fixed, we need to have N i=1 d i = 1. The following theorem states the optimization problem that the attacker needs to solve to find its optimal strategy. Theorem 3: In order to find its α-optimal strategy, the attacker needs to solve the following equality-constrained convex optimization problem: DRAFT Proof: In order to minimize the throughput, attacker needs to minimize the expected value for L k (ω). We know that the attacker attacks this channel with probability αd i , so we have: It can easily be shown that .
So we have: ).
To prove that the E[L k (ω)] is a convex function of d i 's, we compute the Hessian matrix of this function: We can see that the Hessian of this function is a diagonal matrix where: It is obvious that we have ∀i : h ii ≥ 0, thus the matrix H is positive semidefinite and as a result is a convex function.
The above equality-constrained convex optimization problem can be solved by using elimination and Newton's method in (N +1) 3 3 steps [16]. However, solving this optimization problem requires attacker's exact knowledge about the channel selection strategy of the system and the statistics of all channels during a long period of time. Obviously, acquiring such knowledge is not feasible under most circumstances. Therefore instead of using the α-optimal strategy, the attacker can use alternative, simpler strategies. Each of these strategies differ in terms of the amount of knowledge on the channel selection system that is required. These strategies are: • Greedy Strategy: The attacker only knows the best channel for transmission at each time slot and attacks this channel, i.e., d N = 1 and d i = 0 for 1 ≤ i ≤ N − 1. This strategy is the optimal attack strategy when the channel selection system uses a myopic policy.
• Uniform Strategy: The adversary attacks all channels equiprobably, i.e., d i = 1 N : This strategy can be used when the attacker does not have any knowledge about the channel selection system.
• Ω Strategy: The attacker only knows the channel statistics Ω = (ω 1 , · · · , ω N ) and has no knowledge about the channel selection policy of the system. It has a Boltzmann distribution with an arbitrary temperature τ a , i.e., d i = e ω i /τa N j=1 e ω j /τa : 1 ≤ i ≤ N . Simulation results show that when the attack probability, α, is large, this strategy inflicts approximately the same effect as the α-optimal strategy.
In order to find the best channel selection strategy, the system assumes the worst-case attack scenario when the attacker uses its α-optimal strategy, which is the solution to the Optimiza- . The channel selection system needs to solve the following optimization problem in order to maximize the cognitive radio's throughput.
Finding the global optimal solution of the non-linear optimization problem 4, gives us the amount of randomness that we need to add to the system in order to minimize the attack's effect and maximize the throughput.
We can also show that for all possible attack strategies, including the α-optimal strategy, a softmax policy that uses a Boltzmann distribution with a well-chosen temperature outperforms myopic policy.
Theorem 4: When the channel selection system is consisted of more than two identical channels, for all attack strategies that the adversary may employ, with a fixed attack probability α > (ω 0 −p 01 )N (ω 0 N −p 01 ) , a softmax policy that uses a Boltzmann distribution with temperature achieves a greater throughput than a myopic policy.
Proof: Let ω N ≥ ω N −1 ≥ · · · ≥ ω 1 denote the belief values of all channels in the first slot DRAFT of the k-th TP. For the myopic policy, the length L k of this TP has the following distribution.
And for the softmax policy, the length L k of this TP has the following distribution.
N j=1 e (ω j −ω i )/τ are the action selection probabilities that follow a Boltzmann distribution. It is readily observable that if ω ≥ ω N (1 − α), then L k (ω) stochastically dominates L k (ω N ) and consequently the throughput of the softmax policy would be greater than the throughput of the myopic policy. We use the fact that ∀i, p 01 ≤ ω i ≤ ω 0 which results in and also the fact that q N > 1 N and d N > 1 N . Now we show that ω ≥ ω N (1 − α). Using (18) and (17), we have:

A. Numerical Results for More than Two Channels
We simulated the channel selection system to evaluate the performance of myopic sensing and softmax sensing for more than two channels. Figures 5 and 6 show the throughput of the channel DRAFT   As it can be seen, the throughput drop caused by the increase in the attack probability is more severe for the myopic policy. Comparing the slope of lines in Figures 5 and 6, we can see that increasing the number of channels from 4 to 10 makes the softmax policy more robust against the belief manipulation attacks. In Figure 6, the softmax policy's drop in throughput is barely noticeable even as the attack probability is increased to 0.5. Figures 5 and 6 also show that in a non-adversarial environment (i.e. when α = 0), the performance of myopic policy is better than the performance of a softmax policy. These figures confirm the findings of [2] in which the authors showed that the optimal policy in non-adversarial environments is the myopic policy.
To compare different attack strategies and to investigate the amount of required randomness in the channel selection system, we used the more realistic model of non-identical channels with different transition probabilities. Figure 7 shows the effectiveness of the different attack strategies for different attack probabilities in a system of 4 non-identical channels with transition probabilities shown in Table 1.
As can be seen in Figure 7, the Ω strategys performance is close to that of the α-optimal strategy for large values of α. We can also see from the figure that the greedy strategy is the worst strategy among these four different strategies.
It is well known that the temperature of a Boltzmann distribution, τ , is a measure of the amount of randomness in the distribution, which can be inferred from the fact that the entropy  we can observe that the channel selection system needs to increase the randomness (i.e., τ ) in its learning process as the attack probability (i.e., α) is increased to minimize the effect of the attack.
We observed the effect of increasing attack probability on performance of the channel selection system. Figure 9 plots the attacker's cost using the equation 4 versus the attack probability. This figure shows that though increasing the attack probability reduces the performance of the channel selection system significantly, it also increases the attacker's cost with a high rate.

VI. CONCLUSION
In this paper, we analyzed the security of a reinforcement learning algorithm that is used for solving the channel selection problem. We proposed a sensing policy that uses some level of randomness in the decision function to hide information about the learning algorithm. The obtained theoretical and simulation results show that the proposed mitigation technique can cause a dramatic improvement in the robustness of the channel selection process to adaptive jamming attacks. This countermeasure is applicable to other cognitive radio applications that use the same type of machine learning algorithm.


Access Patterns for Robots and Humans in Web Archives

Although user access patterns on the live web are well-understood, there has been no corresponding study of how users, both humans and robots, access web archives. Based on samples from the Internet Archive's public Wayback Machine, we propose a set of basic usage patterns: Dip (a single access), Slide (the same page at different archive times), Dive (different pages at approximately the same archive time), and Skim (lists of what pages are archived, i.e., TimeMaps). Robots are limited almost exclusively to Dips and Skims, but human accesses are more varied between all four types. Robots outnumber humans 10:1 in terms of sessions, 5:4 in terms of raw HTTP accesses, and 4:1 in terms of megabytes transferred. Robots almost always access TimeMaps (95% of accesses), but humans predominately access the archived web pages themselves (82% of accesses). In terms of unique archived web pages, there is no overall preference for a particular time, but the recent past (within the last year) shows significant repeat accesses.

INTRODUCTION
The web has become an integral part of our lives, shaping how we get news, shop, and communicate. In turn, web archives have become a significant repository of our recent history and cultural heritage. The Internet Archive [19] is the largest and oldest of the various web archives, holding over 240 billion web pages with archives as far back as 1996 [13]. Access to this vast archive is available through the Wayback Machine [30], which sees about 82 million requests per day, based on our dataset.
Previous work has studied how users access the live web [31] and search engines [12], but few studies have investigated how users access web archives. Understanding the current demand for access to web archives can provide insights into how to make the best use of limited archiving and access resources.
In this paper, we provide an analysis of user accesses to a large web archive. We examine a set of anonymized Wayback Machine server access logs from February 2012. We investigate the differences between human and robot accesses of the Wayback Machine, identify four major web archive access patterns, and uncover the temporal preference for web archive access. In particular, we find that robots (such as crawlers and spiders) account for 91% of all sessions and 93% of all page requests. Yet, robots only outnumber humans 5:4 in terms of raw, unfiltered requests and 4:1 in terms of megabytes transferred. Humans download more information per session, as they typically download embedded resources (e.g., images and stylesheets), which robots ignore.
We introduce four basic user access patterns of web archives: Dip, Slide, Dive, and Skim. Dip is requesting for a single URI. Slide is browsing different archived copies of the same URI. Dive is following the hyperlinks of a page, but staying near the same datetime. Skim is requesting only the TimeMaps (list of all archived copies for a specific original resource). Robots exhibit the Dip and Skim patterns equally, both about 49% of their sessions, and almost exclusively request TimeMaps. Humans exhibit the Dip (39%) and Dive (30%) patterns the most and access archived pages significantly more than TimeMaps. This paper is organized as follows. Definitions of important terms and a review of related work on web usage mining and web archive studies are presented in Section 2. Section 3 contains the patterns for accessing web archives along with an explanation and example for each pattern. A description of the Wayback Machine's web server logs, the dataset we used in the analysis, and the methodology of this study are presented in Section 4. Section 5 contains the results from analyzing the Wayback Machine access logs. Future work and conclusions are presented in Section 6.

RELATED WORK
Despite the significance of web archives in preserving web heritage, the aspect of web archive usage has been overlooked. The only previous related work is a study of the search behavior characterization for web archives [7]. We highlight this work, but first we define the terms for our discussion.

Memento Terminology
Memento [33] is an HTTP protocol extension which enables time travel on the web by interlinking the current resources with their prior state. Memento introduces content negotiation in the datetime dimension using a special HTTP header, Accept-Datetime [32]. Memento defines the following terms: • URI-R denotes the original resource. It is the resource as it used to appear on the live web; it may have 0 or more mementos (URI-Ms).
• URI-M is an archived snapshot for the URI-R at a specific datetime, which is called Memento-Datetime. e.g., URI-Mi= URI-R@ti.
• URI-T denotes a TimeMap, a resource that provides a list of mementos (URI-Ms) for a URI-R with their Memento-Datetimes, e.g.,

Web Usage Mining
The breadth and depth of research in the area of web usage mining is massive and increasing [3,14,23,5]. Web usage mining involves discovering usage patterns from web data using data mining [25]. The results obtained from web usage mining can be used in different applications, such as web traffic analysis, site modification, system improvement, personalization, business intelligence, and usage characterization. Our study provides traffic analysis and usage characterization by providing abstract models for accessing web archives.
Adams et al. explored the usage patterns of scientific and historical data repositories [1]. However, their study focused on a variety of archive types (e.g., public vs. private, digital but non-web resources) and does not directly address the issue of archiving the web. The only web usage mining research that has been conducted on the usage of web archives is the study of search behavior characterization of web archives based on a quantitative analysis of the Portuguese Web Archive (PWA) search logs [7]. The authors introduced a comparison between search patterns of web archives and web search engines. Despite the different information needs for web archives and web search engine users, the search patterns for web archives had shown adoption of web search engine technologies. They found that most web archive users conducted short sessions. In our study, the sessions that are composed of one request contribute the most to the number of sessions. One important finding from analyzing the search interactions of the PWA logs is that the users prefer older documents. This is in contrast to what we found, that web archive users have significant repetitions for requests in 2011 (the year prior to our sample).
The challenge that faces web usage mining is detecting the robots who camouflage their identity and pretend to be humans. The robot detection problem has been examined in several studies [27,9,15,11]. Doran et al. characterized robot detection techniques into four categories: syntactical log analysis, traffic pattern analysis, analytical learning techniques, and Turing test systems [10]. We used syntactical log analysis (simple processing by finding the self-identified robots) and traffic pattern analysis (specifying features for contrasting robots with humans).

ABSTRACT MODELS FOR ACCESSING WEB ARCHIVES
Through our analysis, we discovered four major patterns for web archive access. We present the model for each pattern along with an example from the logs in Figures 1-4. Each example consists of three columns: the client IP, the access time, and the requested URI. The times annotating the transition arrows in Figure 2-4 represent the interrequest time in the given examples. Note that we use TM URI-R to denote a TimeMap in the figures. We use Memento terminology (URI-T, URI-M, and URI-R) in the definitions. We refer to the original resource for URI-T and URI-M with URI-R(URI-T) and URI-R(URI-M), respectively.

Pattern 1: Dip
Dip is the pattern where a user accesses only one URI. The request can be for a URI-T (Figure 1

Pattern 2: Slide
Slide is the pattern in which a user accesses the same URI-R at different Memento-Datetimes. In this pattern, the user requests a URI-R and walks through time browsing its different copies ( Figure 2).
Navigation between different URI-Ms can be done in many ways, e.g., directly from URI-M1 to URI-M2 (URI-R@t1 ⇒ URI-R@t2) or from URI-M1 to URI-M2, but in the middle the user returns to the TM URI-R to choose between the available datetimes (URI-R@t1 ⇒ URI-T ⇒ URI-R@t2).

Pattern 3: Dive
Dive is when a user accesses different URI-Rs at nearly the same datetime. In this pattern, the user accesses one URI-R at a specific time, URI-R1@t0, then navigates to different hyperlink(s) of URI-R1's page (e.g., URI-R2@t0) and so on (

METHODOLOGY
In this study, we introduce an analysis of the user access patterns of web archives. The analysis was conducted on the Internet Archive's Wayback Machine access logs. The first step in preparing the Wayback access logs for usage mining was transforming the raw log file into server sessions through web-log preprocessing, which included data cleaning, user identification, and session identification [6]. Then, we performed feature extraction, robot detection, and user access pattern detection.

Wayback Machine Access Logs
A Web server log file is a plain text file that records the activity information of the submitted requests from the users on the web server. The Wayback Machine access logs contain the following fields: client IP, access time, HTTP request method (GET or HEAD), URI, protocol (HTTP), HTTP status code (200, 404, etc.), bytes sent, referring URI, and User-Agent. For privacy purposes, the Internet Archive anonymized the client IP address. A segment from the Wayback Machine server logs, which we will call Wayback access logs, is shown in Figure 5. The first line shows a request for a URI-T. The second line shows a request for a URI-M.

Dataset
The Wayback Machine allows users to browse archived copies of web pages across time. The Wayback access logs were sampled using two probability techniques [29]: cluster sampling, which is choosing a cluster of data randomly, and random sampling, where each sampling unit has an equal chance of being included. We performed cluster sampling by choosing a week (Feb. [2][3][4][5][6][7][8]2012) and random sampling by taking a random slice from each day of the week. Each sample comprised a slice of 2M requests to the Wayback Machine web server. Table 1 shows the characteristics of each dataset. It contains the following features for each sample: • Duration: the difference between the last request time and the first request time of each sample in HH:MM:SS format.
• GET: the percentage of requests that used the GET method.
• Embedded: the percentage of requests that were for embedded resources of web pages (such as images and CSS files, etc.).
• SI Robots: the percentage of requests by self-identified robots based on the User-Agent field.
• NullRef: the percentage of requests that had an empty referral field.
• Cleaned: the percentage of requests remaining after removing requests for embedded resources, HEAD requests, and requests that resulted in status codes other than 200, 404, or 503.
• Sessions: the number of sessions.
The last three columns of the table show the mean, standard deviation, and corresponding standard error between the samples. We use the Feb. 2, 2012 sample in our analysis because as we see from Table 1, it is a representative sample.
In the Feb. 2 sample, we note that HTTP 3xx accounts for 52% of the total number of requests. This is related to the default Wayback Machine behavior. First, the Wayback Machine rewrites all of the hyperlinks of a memento's embedded resources with the mementos's timestamp. Second, in the resolution of these URIs, the Wayback Machine will redirect the request of the embedded resources and hyperlinks to the nearest (timestamp) available memento. Furthermore, the Wayback Machine responds with a 302 status first when the requested URI-R is not available on the Wayback Machine, and then responds with a 404 status.

Data Cleaning
The first step in preprocessing our dataset was data cleaning, i.e., removing log entries that were not needed for the mining process [17,28]. In similar studies for log analysis, robots that identify themselves in the User-Agent field were removed. Because robots crawl web archives intentionally, we did not exclude their requests in the cleaning step. We eliminated the following items which were irrelevant in terms of user behavior: • Requests that were generated automatically by the web browser for embedded resources of the requested web page (such as graphic files, page style files, etc.). • Entries with an HTTP status code other than HTTP 200, 404, or 503. We kept only these because we considered them to be requests executed by the user. • Requests using the HEAD request method (as suggested by [16]). • Static resources of the Internet Archive web site and the URIs of the liveweb service, which the Internet Archive introduces to redirect the user to the live web when the copy is not found on the Wayback Machine. • Invalid requests from web sites which included a link for malformed URI-Rs (for example, about:blank) among their embedded resources, so that each request on their web sites caused automatic requests to the Wayback Machine server. Similar behavior had been detected by Omodei [21].

User Identification
To identify the users, the log files were first sorted by the IP, then by the request time. At first, we identified users by the 2-tuple (IP, User-Agent), but we found instances of malicious robots who not only did not self-identify, but who also changed their User-Agent with every request. There are some legitimate cases for humans to have different User-Agents and the same IP, for instance, two simultaneous users coming from behind a firewall. So, we needed to determine a reasonable threshold for the number of User-Agents per IP to detect malicious robots. Figure 6 shows the relationship between the number of User-Agents per IP and the number of requests per IP (for those IPs with more than one User-Agent). We excluded self-identified robots from the graph to avoid biasing the results. We found only 24 users who had changed their User-Agent field more than 20 times. The median value for the number of User-Agents per IP for the dataset is 3 (excluding users who had one User-Agent only). We concluded that 20 different User-Agents per IP is a good threshold for this dataset. For IPs with at most 20 different User-Agents, we used the 2-tuple (IP, User-Agent) to identify individual users. The 24 IPs with more than 20 different User-Agents were classified as 24 separate robots.

Session Identification
A session is the set of web pages that are requested by particular user [17]. Session identification is performed by dividing a web server log file into web server sessions. First, we group all the requests based on the IP and User-Agent (as described in Section 4.4). Second, we apply a threshold timeout, so that if the time elapsed between two consecutive requests is longer than this threshold, the second request is considered to be the first request of the new session. There have been several suggested timeout thresholds including 25.5 minutes [5], 30 minutes [27,14], and 60 minutes [2]. Others proposed 10 minutes as a conservative threshold to capture the time for staying on one page [16,24]. In our study, we divided the requests of each user into individual sessions based on a 10 minute timeout threshold. Future research is required to verify that searching and browsing models for the current web are valid for browsing the past web (i.e., web archives).
After identifying the sessions, we extracted features for each session to be used further in the analysis. A session, S, is 7-tuple.

Robot Detection
Because of the increasing numbers of web crawlers that are engaged in web harvesting, many studies have been conducted for investigating the robot detection problem [   15]. In this study, we used different types of robot detection techniques [10]. First, we applied syntactical log analysis by checking the User-Agent field to identify the self-identified robots. Second, we applied traffic pattern analysis techniques to distinguish humans from robots based on their navigational behavior. In this section, we describe heuristics we used for distinguishing robots from humans.

User-Agent Check
The User-Agent check is applied for requests from crawlers and robots which declared their identity to the web server through the User-Agent field (SI robots). We excluded these robots by applying this heuristic before the calculations of the session features to avoid biasing the results.

Number of User-Agent per IP
As explained earlier (Section 4.4), we used 20 as a threshold for the maximum number of different User-Agents for each IP. Users with more than 20 different User-Agents were classified as robots.

Robots.txt file
Web site administrators put a list of access restrictions to specify which parts of their web site are not allowed to be visited by robots. We labeled the sessions in which users downloaded the robots.txt file for the Wayback Machine (http://web.archive.org/robots.txt) as robots.

Browsing Speed (BS)
The importance and the effect of BS has been discussed and used for detecting robots many times [20,28,22]. We use BS ≤ 0.5 (i.e., no faster than one request every two seconds) as a threshold for human browsing speed [4]. We observed that this threshold is appropriate for our dataset, so we classify the sessions with BS > 0.5 as robots.

Image-to-HTML Ratio (IH)
Human sessions should have more images than robot sessions because of the embedded images present in most HTML pages. Robots tend to retrieve only HTML pages, while ignoring image formats. We used the IH metric calculated previously for each session to detect robots. In [26], 1:10 IH had been suggested as a good threshold for distinguishing robots from humans. We label a session with less than one image file for every 10 HTML files as a robot. IH is the only heuristic that does not require a session have at least two requests. This heuristic is the best predictor for robots [27,26], and it has a strong effect on our dataset.

RESULTS AND ANALYSIS
In this section, we explain the results of preprocessing the dataset (described in Sections 4.3-4.5) and of applying the heuristics for robot detection (described in Section 4.6). We analyze the resulting data and contrast the behavior and access patterns of humans and robots. We conclude with an analysis of the temporal preference of human users.

Traffic Analysis
To extract the user access patterns for web archives from the Wayback access logs, we first applied data preprocessing techniques (data cleaning, user identification, session identification) to convert the log file into web server sessions. The raw log file contains 2M requests from which we determined 21,932 unique IPs. Because of the stateless nature of the log files, we identified the users based on the IP and User-Agent to identify 33,841 users who created 37,634 different sessions.
The characteristics of each filter (3xx status code, embedded resources, static resources and liveweb, invalid requests, HEAD) and the total number of excluded requests after applying all the filters together are shown in Table 3. The number of records in the Feb. 2 sample was decreased from 2M to 426,317 (21.3% of the requests in the raw file). Table 2 contains the results of applying the heuristics for detecting robots. The rules are not mutually exclusive, but we calculated the number of requests which had been labeled as robots from each filter separately. IH had the largest effect on detecting robots. We used a 1:10 IH as a threshold for distinguishing robots from humans. We found that 99.93% of the sessions which were detected by this heuristic had 0 images. BS is also important, because it classified a significant number of robots who had a BS (more than 0.5 requests/second) impossible for humans.   the percentage of raw requests from humans and robots did not equal 2M requests. The reason is that there are many accesses that were created by invalid requests to the web server. Furthermore, there are many requests to embedded resources only, which were filtered. The percentage of human requests after cleaning and separating robot requests is only 1.5% of the 2M requests. The significant discovery here is the 10:1 ratio of robot sessions to human sessions. This ratio is a strong motivation for building an API interface that serves robot accesses in order to decrease the load of robots on the Wayback Machine. A typical human session costs more than a robot session as humans average 1.30 MB/session and robots average 0.58 MB/session. Human requests include automatic downloads of the embedded resources of the web pages they access, and robots usually ignore downloading these embedded resources.

Robots vs Humans
We discovered that most of the robots had a breadth search strategy in downloading the web pages from the Wayback Machine; more than 95% of the robots downloaded TimeMaps only, as shown in Table 4. On the other hand, of all human requests, only 18.5% were for TimeMaps.

Session Length (S l )
After detecting the robots, we separated them from humans and analyzed their behaviors individually. Figure 7 shows the session length frequency for robots in red and for humans in blue. We notice from the figure that many more robots have longer sessions than humans. TheS l for robots is 10 requests/session, while humans have anS l of 9 requests/session.

Session Duration (S d )
We computed session duration by subtracting the time of the first request from the time of the last request for each session. Session duration requires at least two requests. Figure 8 shows the percentage of sessions with different session durations for robots and humans. We can see that the majority of the sessions were short, taking into consideration that we did not count the time spent on the last requested web page. TheS d is 10 minutes for robots and 5 minutes for humans.

Inter-Request Time
We also calculatedSrt and stdev(Srt) for each session. We found that the median values ofSrt for human and robot sessions are 19 seconds and 40 seconds, respectively. The median of stdev(Srt) values is 37 seconds for robots and 11 seconds for humans. This indicates that robots tend to have more irregular periods between HTML requests than humans, and this matches the finding by Tan et al. [27].

Web Archive User Access Patterns
How do users go through web archives? Do they go in deeply from URI-R1 to URI-R2, do they browse broadly from URI-M1 to URI-M2 for the same URI-R, or do they use a combination of these two patterns? Are robot accesses similar to human accesses?
In this section, we answer the previous questions by extracting the user access patterns for web archives from our filtered dataset. The requested URIs for each session were extracted and then identified based on their type, URI-M or URI-T. We also extracted the URI-R of each requested URI to compare it with the other URI-Rs from the same session. Because of the existence of different forms of URIs which refer to the same website [18], we applied URI canonicalization for the URI-Rs to normalize them under one host [8].
We discovered four basic building blocks (Dip, Slide, Dive, Skim) of the user access patterns for web archives.

Dip
Dip is the pattern where the user requests a single URI. This URI can be a URI-M or a URI-T. It represents the most repeated pattern for humans (33% of all sessions) and robots (49% of all sessions). URI-Ms contribute to 83% of human sessions that exhibit the Dip pattern, although 94% of the robot Dips are requests for URI-Ts.

Slide
The user who is interested in travelling through time, browsing different copies of the same URI-R, creates the Slide pattern. There are only a few humans who access the web archives broadly then navigate away (4.2% of all sessions). Robot sessions do not have this pattern with a noticeable percentage (0.1% of all sessions).

Dive
Dive represents the second highest percentage of human sessions, 29.7%. In this pattern, the user goes deeply for browsing hyperlinks of URI-Ms. The robot sessions which were composed of this pattern crawl the web sites deeply, but they are not a significant number of sessions.

Skim
Skim is the pattern for which the users access different numbers of TimeMaps. Robot sessions exhibit this pattern 48.7% of the time. Investigating the relationship between the topics of the URI-Rs of the requested TimeMaps during a single session is one of our goals for upcoming research.

User
Pattern

Pattern Length
Each pattern is made up of a number of requests, which we call the pattern length. We calculated the pattern length for all sessions. The median, mean, and standard deviation of the lengths of each pattern for robots and humans are summarized in Table 5. For humans, the longest mean pattern length is an 8-request Dive, while for robots the longest mean pattern length is 21 requests in a Skim. Figure 10 shows both the unique and total number of mementos referenced grouped by the year of their Memento-Datetime. Although there is no clear temporal preference for any one year of the unique mementos, there were a significant number of repeated requests for mementos from 2011. This locality of reference suggests that there is an important benefit to be gained by caching the mementos from the recent past. Figure 11 shows that the total number of mementos available for 2011 was similar to previous years. In both Figures 11 and 10, pre-2001 data is included although in those years the archives are too sparse for meaningful comparison with later years.

CONCLUSIONS AND FUTURE WORK
We introduced the basic building blocks (Dip, Slide, Dive, and Skim) for user access patterns for web archives through an analysis of the Internet Archive's Wayback Machine access logs. We applied heuristics for detecting robots and found that robot sessions outnumber human sessions 10:1. This suggests that there is utility in building an API interface that serves robot accesses. Robots account for 91% of sessions and 93% of requests to the Wayback Machine, yet robots outnumber humans 5:4 only in terms of raw, unfiltered requests and 4:1 in terms of megabytes transferred. We found that humans download more information per session due to embedded resources, which robots ignore. We also analyzed human and robot access patterns to emphasize the similarities and the differences between them. We found that robots mainly exhibit the Dip and Skim patterns, with about 49% of their sessions for each pattern, and that they access TimeMaps almost exclusively. Humans exhibit the Dip and Dive patterns the most with 39% and 30% of their sessions, respectively. Unlike robots, humans mainly access archived pages rather than TimeMaps. Finally, we provide an analysis for the temporal preferences of humans based on the Memento-Datetime (by year) of their requests and discovered significant repetitions for requests in 2011. This suggests that there is a benefit to be gained by caching mementos from the recent past.
Web server logs are a rich source for information about web archives. We are planning to extend our analysis to serve other applications of web usage mining, such as personalization for making dynamic recommendations to web archive users based on their navigational behavior patterns by using data mining techniques. Further, we will study the validity of applying searching and browsing models for the current web to web archives. We also expect that Slides and Dives that users create on web archives may create stories around a particular event. We plan to extend our study on a large data set to detect stories that humans might create from their access patterns, which will be integrated into the live web to produce automatic stories about specific event for the users.

ACKNOWLEDGMENTS
This work was supported in part by the NSF (IIS 1009392) and the Library of Congress. We thank Kris Carpenter Negulescu (Internet Archive) for access to the anonymized Wayback Machine logs.


extfieldsofstudy:
Computer Science
Mathematics

text:
Learning Hidden Structures with Relational Models by Adequately Involving Rich Information in A Network

Effectively modelling hidden structures in a network is very practical but theoretically challenging. Existing relational models only involve very limited information, namely the binary directional link data, embedded in a network to learn hidden networking structures. There is other rich and meaningful information (e.g., various attributes of entities and more granular information than binary elements such as"like"or"dislike") missed, which play a critical role in forming and understanding relations in a network. In this work, we propose an informative relational model (InfRM) framework to adequately involve rich information and its granularity in a network, including metadata information about each entity and various forms of link data. Firstly, an effective metadata information incorporation method is employed on the prior information from relational models MMSB and LFRM. This is to encourage the entities with similar metadata information to have similar hidden structures. Secondly, we propose various solutions to cater for alternative forms of link data. Substantial efforts have been made towards modelling appropriateness and efficiency, for example, using conjugate priors. We evaluate our framework and its inference algorithms in different datasets, which shows the generality and effectiveness of our models in capturing implicit structures in networks.

Introduction
Learning hidden structures within a network is an emergent topic in various areas including social-media recommendation (Tang & Liu, 2010), customer partitioning, social network analysis, and partitioning protein interaction networks (Girvan & Newman, 2002; Preliminary work. Under review by the International Conference on Machine Learning (ICML). Do not distribute. Fortunato, 2010). Many models have been proposed in recent years to address this problem by using linkage information such as a person's view towards others. Examples include stochastic blockmodel (Nowicki & Snijders, 2001) and its infinite communities case infinite relational model (IRM) (Kemp et al., 2006), both aiming at partitioning a network of entities into different groups based on their pairwise, directional binary observations. The "inter-nodes" link data used in existing approaches contributes to the explicit insight on social structures.
On the other hand, the "intra-nodes" metadata information could complement the disclosure of hidden implicit relations structures. Let us take the Lazega lawfirm network (detailed in Section 6) as an example, which contains both link and metadata information: The metadata information include attributes such as offices (Boston, Hartford or Providence), law schools (harvard, yale, ucon or other) and age associated with each of the entities (attorneys). Naturally, people with similar attributes tend to have relationship with each other. The directional link data including elements such as basic advice frequency, co-work time and friendship. These elements however, may take different forms. Here the first two elements can be represented by integer values (i.e. count link data), while friendship may better be represented by a real value on the unit interval (i.e. unit link data). If they have to be "binarized" as in the case of the existing models, then the lost of granularity could lead to poorer utilization of information.
We propose a new informative relational model (In-fRM) framework, which incorporates both the rich metadata information and granular link data in a sensible and efficient way. To integrate the metadata information, a new transform is proposed, and the corresponding result is placed as the prior for the communities of each entity. This enables the similarity of metadata information between entities to be reflected in their corresponding hidden structures. Inspired by the existing benchmark relational models of MMSB (Airoldi et al., 2008) and LFRM (Miller et al., 2009), we individually model the hidden structure as mixed memberships and latent features respectively. This lead to informative mixed membership model (InfMM) and informative latent feature model (InfLF) which is the centerpiece of this paper. The stick breaking process (Sethuraman, 1994) (Teh et al., 2007) alike methods were proposed to model the unknown number of communities. In particular, our InfMM model successfully gains the conjugate property. As discussed in Section 3.1, through these efforts, the existing models can be seen as the special cases of our proposed models.
In addition, we designed a set of solutions to model the various forms of link data, including the count and unit link data. We have chosen the likelihood and prior model carefully for both of their practical appropriateness and computation efficiencies. Their effects have been demonstrated in our experiments.
As a result, our models capture much richer information embedded in a network, thus leading to better performance as illustrated in Section 6 in modelling hidden structures. The rest of the paper is organized as follows. Section 2 introduces the relational models and necessary notations for our work. In Section 3, we describe the InfRM framework for integrating metadata information into each entity's hidden structure, including InfMM and InfLF. The generation distributions proposed for different forms of link data are provided in Section 4. Section 5 discusses the sampling methods and computational complexity analysis. Experiments in Section 6 compare our methods with the previous work and validate our model performance. Conclusions and future works are in Section 7.

Relational Models
The stochastic blockmodel (Nowicki & Snijders, 2001) assumes that each entity has a latent variable that directly represents its community membership. Each of the fixed number of communities associates with a weight, and the whole weight vector can be seen as a draw from a K-dimensional Dirichlet distribution. Naturally, the community memberships are realized from the multinomial distribution parameterized by the weight vector. The binary link data between two entities is determined by their belongingness communities. This model has been extended to an infinite K community, i.e., infinite relational model (IRM) (Kemp et al., 2006) where the Dirichlet distribution has been replaced by a Dirichlet process.
Various recent work has been proposed to capture the complex interactions amongst entities based on stochastic blockmodel, which can be categorized into two notable branches, both are a generalisation of stochastic blockmodel. The first branch features the latent feature relational model (LFRM) (Miller et al., 2009): instead of associating an entity with only a single feature, i.e., its membership indicator, it allows a variable number of binary features to be associated with each entity. The second branch follows the mixedmembership stochastic blockmodel (MMSB) model, in which each entity has its own community distribution, hence having a "mixed" class of interactions with other entities.
The LFRM-like work was originated from (Hoff et al., 2002;Hoff, 2005), while it assumes a latent realvalued feature vector for each entity. The LFRM in (Miller et al., 2009) uses a binary vector to represent latent features of each entity, and the number of features of all entities can potentially be infinite using an Indian Buffet Process prior (Griffiths & Ghahramani, 2006;2011). The work in (Palla et al., 2012) further uncovers the substructure within each feature and uses the "co-active" features from two entities during generating their link data. On the MMSB-typed work, a few variants have been subsequently proposed, including (Koutsourelakis & Eliassi-Rad, 2008) which extends the MMSB into the infinite community case and (Ho et al., 2012) which uses the nested Chinese Restaurant Process (Blei et al., 2010) to build the hierarchical structure of communities.

Notations
All notations in this paper are given in Table 1 directional, binary interactions s ij , r ij membership indicators of e ij in MMSB z i latent feature vector of entity i in LFRM π i membership distribution for entity i, π ik is the significance of community k for entity i B asymmetric, role-compatibility matrix, B kl indicates compatibility of communities k, l Figure 1 depicts the generative models of all the variables used in our work. In this paper, metadata information is incorporated into both branches of the stochastic blockmodel described earlier, i.e. MMSB and LFRM. Further, it can be applied to their base mode IRM (Kemp et al., 2006) with the similar approach, which we will not elaborate here.
Here C1 and C2 are the stick breaking representation for our mixed membership distribution π i . C3 and C4 correspond to the membership indicator and link data's generation, respectively. Detailed elaboration is in (Airoldi et al., 2008;Koutsourelakis & Eliassi-Rad, 2008). We leave equation C4 in its general form, i.e., g(B sij rij ), which may take on a variety of forms, such as those described in Section 4.
We use the attribute age in Lazega lawfirm to further explain the importance indicator η f k used in C1. W.l.o.g., we let f th 0 column of φ matrix denote the age attribute of all the entities, φ if0 = 1 implies that entity i has age > 40 (in our experimental setting), and C4 Figure 1. The generative model for several implementations. Observations are denoted in grey. The part above the dashed line corresponds to involving metadata information in Section 3; the below part corresponds to modeling link information discussed in Section 4. C1 to C4 represent four conditional distributions in two different forms as shown in Sections 3.1 and 3.2, respectively. 0 otherwise. From equation C1, one can easily see that when η f0k ≪ 1, age would largely increase the impact of the k th community. Likewise, η f0k ≫ 1 reduces the significance of the age attribute on the k th community. η f0k = 1 means that age does not have influence on the k th community at all. When φ if0 = 0, it makes age of the entity i neutral towards all other communities.
Instead of C1, the NMDR model (Kim et al., 2012;Kim & Sudderth, 2011) uses the logistic normal distribution (with the mean value being the linear sum (i.e., f φ if η f k )) to construct a stick-breaking weight ψ ik . While the method can successfully integrate the metadata information into the entity's membership distribution, it suffers from the lack of conjugacy, which makes inference inefficient. In our approach InfMM, we replaced the logistic normal distribution with a beta distribution, parameterised by f η φ if f k , where the positive, importance indicator η f k is given a vague gamma prior η f k ∼ Gamma(α η , β η ).
Despite the model relaxation, empirical results show that NMDR has a slow convergence. It is therefore imperative for us to search for a more efficient way to incorporate the metadata information. Compared to iMMM, our InfMM model replaces unified f k for the generation of ψ ik . Its conjugate property makes our model appealing in terms of mixing efficiency, which is confirmed in the results shown in Section 6.3. What is more is that our model can be seen as a natural extension of the popular iMMM model. By letting η f k = α 1/F and φ if = 1 , we obtain the classical iMMM. This makes sense, as without the presence of metadata, each feature is assumed to be counted equally, which implies that the model becomes the classical iMMM.

Informative Latent Feature Model
The generative process for informative latent feature (InfLF) model is defined as follows: Here C1 and C2 refer to the detailed construction of our specialized stick breaking representation π i . Similar to the traditional stick-breaking process (Sethuraman, 1994) (Teh et al., 2007), they are used to generate the latent feature matrix z in C3. C4 corresponds to the link data's generation in our model. Our work can be seen as an extension to the traditional LFRM, which can be seen at (Miller et al., 2009).
However, our InfLF's hidden structure differs from the one of LFRM. More specifically, the original LFRM uses one specialized beta process as the underlying representation for all the n entities' latent feature z. This process can be easily marginalized out in convenient of the Beta-Bernoulli conjugacy (Thibaux & Jordan, 2007). In our InfLF, each i th entity's latent feature is motivated by their own stick breaking representation π i , i.e., there are n representations in total. Thus, the individual metadata information is contained in each corresponding representation, which will be reflected in the latent feature.
We use the new transform, i.e., f η φ if f k , as the mass parameter (Thibaux & Jordan, 2007) in the construction of the stick breaking representation, as stated in C1. The importance indicator η here plays an opposite role when comparing to the InfMM model, i.e., larger value of η f k would make the present of attribute f promote the k th community.
An interesting notation is that the stick breaking representations in both of our InfMM and InfLF are no longer Dirichlet Process and Beta Process individually, as the single valued α parameter is replaced by a set

Count Link Data
In iMMM, we propose to model the count link data with the following likelihood and prior distributions: The parameter B kl in the Poisson distribution reflects the compatibility between the two communities k and l. The lager B kl encourages larger e ij . Further, we put a vague gamma prior on it as B kl ∈ R + . The resultant predictive distribution is the Negative Binomial distribution (Hilbe, 2011)

when marginalizing out B kl
For the discovered communities k, l in iMMM, we sample B kl as: Here On calculating an undiscovered community K + 1 in iMMM, we can marginalize the corresponding B value out:

Unit Link Data
In modelling the unit Link Data, we use the Beta Distribution instead as the corresponding generation distribution. For the iMMM case, we have: Thus, the posterior distribution of B kl between the discovered communities k, l is: While involving an undiscovered community K + 1, we have Due to the space limit, the detailed sampling procedures of both InfMM and InfLF models are summarised in the Supplementary Material. In here, we explicitly sample {π i } n i=1 . In fact, most of the conditional distributions used in Gibbs have been stated in the preceding sections.

Computational Complexity
We estimate the computational complexities for each model and present the results in Table 2. Our InfMM and InfLF are O(Kn 2 + Kn + F Kn) and O(K 2 n 2 + Kn + F Kn) respectively, with O(Kn) for the sampling of {π i } n i=1 and O(F Kn) for the metadata information's incorporation.
We have independently implemented the above benchmark algorithms to the best of our understanding. There have been a slight variation to NMDR, in which we have employed Gibbs sampling to sample the unknown cluster number, instead of Retrospective MCMC (Papaspiliopoulos & Roberts, 2008) used in the original paper. This is because we have set the conjugate priors to their corresponding generation distributions.
To validate the model's prediction accuracy, we use a ten-fold cross-validation, where we randomly select one out of ten for each entity's link data as testing data and the rest as training data. The criteria for evaluating the prediction capability are the training error (0−1 loss), the testing error (0−1 loss), the testing log likelihood and the AUC (Area Under the roc Curve) score, where these detailed derivations can be found in the Supplementary Material. Also, an extra study is performed on learning the importance indicator of metadata information in the lazega-lawfirm dataset as we have successfully inferred the corresponding η values.
At the beginning of the learning process, we set the vague Gamma prior Γ(1, 1) for all the hyperparameters, including α η , β η , α B , β B .
The initial states are of random guesses on the hidden labels (membership indicators in MMSB and latent feature in LFRM). For all the experiments, we run chains of 10, 000 MCMC samples for 30 times, assuming 5000 samples are used for burn-in. The average of the remaining 5000 samples are reported.

Lazega-lawfirm Dataset
The lazega-lawfirm dataset is about a social networking corporate located in the northeastern part of the U.S. in 1988 -1991. The dataset contains three different types of relations: co-work network, basic advice network, and friendship network for 71 attorneys, in which each link data is labelled as 1 (exist) or 0 (absent). Apart from these three 71 binary asymmetric matrices, the datasets also provide some metadata information on each of the attorneys, including the status (partner or associate), gender, office (Boston, Hartford or Providence), years with the firm, age, practice (litigation or corporate), law school (harvard, yale, ucon or other). After binarizing these attributes, a 71 × 11 binary metadata information matrix is obtained.
We conduct the link prediction on the co-work network and show the result in Table 3. Notably, the performance of our implementation of NMDR model is inferior compared to its original (Kim et al., 2012). The reason may be as a result of a sub-optimal metadata binarization process. However, we have shown that with the same attributes, our InfMM performs better than the NMDR in terms of training error, test capability and convergence behaviour (including the burn in samples needed and mixing rate).
Another interesting topic here is the learning of the importance indicator η for the attributes in the metadata information. We take a geometric mean value of participating the communities for each attribute and show the detail result in Table 4. As stated in Section 3.1, smaller value indicates larger influence. Table 4. The recovered Importance indicator η in Lazegalawfirm dataset. As we can see, the value of attribute office is the smallest amongst all these values, which indicates it has a largest influence. This phenomenon is consistent with common sense as people in the same place would be more likely to have a relation. Also, the attribute practice is more important than the others in forming this co-work link data.  towards the others, i.e., e i,j represents the proximity from i to j based on participant i's opinion. The detailed link values indicate the average proximity from one subject to another, which is categorised into 5 values correspondingly. While using previous models (Koutsourelakis & Eliassi-Rad, 2008), we manually set the proximity value larger than 10 minutes per day as 1, and 0 otherwise. We hence obtain a 73 × 73 asymmetric matrix. According to the generation distribution used, we can choose either the integer matrix or its binary version.
Alongside this directional link data, we also have a survey data on the entities involving metadata, including the traffic choice to work, personal habitat, social activity, the communication method, and satisfaction of university life.
As we can see in Table 3, we find our InfMM's performance is similar to the ones in iMMM. The reason may be that the metadata information does not correlate with the link data. Our pInfMM and piMMM's performance is the best among all these models. This validates the necessity of using Poisson distribution while encountering the count link data.

Convergence Behaviour
Trace plot for AUC A trace plot for the AUC value versus iteration time could help us choose an appropriate burn-in length. An earlier reach to the stable status of MCMC is desirable as it indicates fast convergence. Figure 2 shows the detailed results.
Mixing rate for a stable MCMC. Besides the MCMC trace plot, another interesting observation is the mixing rate of the stable MCMC chains. We use the number of active communities K as a function of the updated variable to monitor the mixing rate of the MCMC samples, whereas the efficiency of the algorithms can be measured by estimating the integrated autocorrelation time τ and Effective Sample Size (ESS) for K. τ is a good performance indicator as it measures the statistical error of Monte Carlo approximation on a target function f . The smaller τ , the more efficient of the algorithm. Also, the ESS of the stable MCMC chains informs the quality of the Markov chains, i.e., a larger ESS value indicates more independent useful samples, which is our desired property.

NIPS Coauthor Dataset
We use the co-authorship as a relation gained from the proceedings of the Neural Information Processing Systems (NIPS) conference for years 2000-2012. Due to the sparsity of the co-authorship, we observe the author activities in all 13 years (i.e. regardless of the time factor) and set the link data being 1 if two corresponding authors have co-authored on no less than 2 papers, which is to remove the co-authoring randomness. Further, the authors with less than 4 relationships with others are manually eliminated. Thus, a 92 × 92 symmetric, binary matrix is obtained.
We focus on the count link data's modelling in this dataset, where the actual link data among these 92 entities are used. As the detail result shown in Table 3, our piMMM performs better than the classical iMMM.

Conclusions & Future work
Increasing applications with natural and social networking behaviors request the effective modelling of hidden relations and structures. This is beyond the currently available models, which only involves limited link information in binary settings. In this paper, we have proposed a unified approach to incorporate various kinds of information into the relational models, including the metadata information and different formats of link data. The proposed informative mixed membership (InfMM) model and informative latent feature (InfLF) model have been demonstrated effective in learning the structure and show advanced performance on learning implicit relations and structures. Also, our adaptive link data modelling method further boosts the capability of utilizing rich link data in the real-work scenario.
We are extending our work to: 1), how to integrate the multi-relational networks and unify them into the InfMM framework to deeply understand network structure; 2), when the link data is categorical, what