# Sign Inference for Dynamic Signed Networks via Dictionary Learning

Authors: Yi Cen; Rentao Gu; Yuefeng Ji
Journal: Journal of Applied Mathematics
 (2013)

---

## Abstract

Mobile online social network (mOSN) is a burgeoning research area. However, most existing works referring to mOSNs deal with static network structures and simply encode whether relationships among entities exist or not. In contrast, relationships in signed mOSNs can be positive or negative and may be changed with time and locations. Applying certain global characteristics of social balance, in this paper, we aim to infer the unknown relationships in dynamic signed mOSNs and formulate this sign inference problem as a low-rank matrix estimation problem. Specifically, motivated by the Singular Value Thresholding (SVT) algorithm, a compact dictionary is selected from the observed dataset. Based on this compact dictionary, the relationships in the dynamic signed mOSNs are estimated via solving the formulated problem. Furthermore, the estimation accuracy is improved by employing a dictionary self-updating mechanism.


---

## Body

## 1. Introduction

Over the past few years, a number of mobile applications that allow users to enjoy networking have emerged. Correspondingly, there has been a proliferation in mobile online social networks (mOSNs). With the ubiquitous use of mobile devices and a rapid shift of technology, it is worthy to investigate the mOSNs from a privacy or security standpoint [1, 2]. The related applications are also extensive such as authentication and recommendation online. In this context, researches about mobile online networks where two opposite kinds of relationships can occur have become common; people not only form links to indicate friendship, support, or approval but signify disapproval or distrust of the opinions of others. It is natural to model such networks as signed networks, where the sign of a link weight can be either positive or negative, representing the status of a relationship. Analogous to traditional social networks analysis, the relationships in signed mOSNs can be represented as a graph, where nodes denote the objects (e.g., people or mobile terminals) and signed edges denote the relationships or links (e.g., a communication made between two people). The link structure of the resulting graph can be exploited to detect underlying groups of objects, predict missing links, and handle many other tasks [3–17].One of the most fundamental theories that are applicable to signed social networks is social structural balance [5, 6, 16]. Structural balance corresponds to the possibility of exactly dividing the signed graph into two adversary subcommunities such that all edges within each subcommunity have positive weights while all edges joining agents of different communities have negative weights. Obviously, graphs of nonnegative weights are a special case of structural balance, in which one of the two subcommunities is empty. Since the assumption that structural balance exists in a real signed network might be too extreme, a concept called weak structural balance further generalizes structural balance by discussing the multiadversary-subcommunities partition of the signed graph [7].Structural balance and weak structural balance have been shown to be valid to analyze signed networks. For instance, the sign inference problem, which aims to infer the unknown relationship between two objects, can be solved by mining balance information of signed networks from local and global perspectives [8–10, 12–17]. With the help of the result inferred, it is possible to predict the relationships so that legitimate participants can eliminate networking security vulnerabilities. Nevertheless, most of these state-of-the-art methods for sign inference problem are mainly considered from a static point of view, and dynamic scenarios are rarely taken into account. Therefore, it is necessary to establish a rational dynamic network model to infer the sign of relationships.Actually, there exist several inherent qualities of mOSNs that are challenging to reliably sense the global states of relationships for the large networks in practice [2]. First, in contrast to traditional social networks, the observations of relationships in mOSNs are closely associated with the geographical environment, as well as the relative locations and signal coverage of mobile terminals/network access points. Due to these spatial constraints, such observations, which seem linearly related to the global data of relationships (i.e., linearly sampled from the global data), are bound to miss a significant number of values. Consequently, they are not sufficient to unambiguously infer the true status by the traditional solutions of linear-inverse problem in general. Second, in mOSNs different relations between entities may appear at different times. Accordingly, observations of the networks vary during a time period long enough. These dynamic interactions over time essentially introduce time dimension to the problem of mining, the potential relationship structures. Third, despite maintaining the dynamic performance, the underlying relationships in reality always display some “redundancy” attributed to the gradual/periodic variation [3], the relative stability, and so forth. Owing to the aforementioned characteristics of mOSNs, the mass redundant data generated in variant scenarios will result in resource challenge. Hence, although many observers collect features for at least part of the networks, there are still serious impediments to reliable large-scale or network-wide data processing. After these aspects of mOSNs are learned, it is reasonable to organize the entire relationship dataset in the form of tensor coincident with its spatiotemporal structure. Meanwhile, efficient relationship inference approaches associated with the tensor model are required to overcome the obstacles of this data processing.The aim of this paper is to develop algorithms for the sign inference in signed mOSNs in global and spatiotemporal evolvement perspectives. In particular, we assume that the signed mOSN possesses an underlying dynamic weakly balanced complete network structure. Suppose that we are given an incomplete networking observation tensor (or 3-dimensional array), which consists of the adjacency matrices corresponding to the snapshots of the underlying dynamic weakly balanced complete network at timesT0,T0+1,…,T0+T-1,T0+T. Then the sign inference task is to estimate the sign patterns of all possible links in the dynamic complete network at time T0+T. Utilizing the low-rank property of the weak structural balance and the features extracted from the observation tensor, we consider the inference via the incomplete relationship data as an underdetermined linear-inverse problem and develop an approach via a low-rank matrix reconstruction to solve this problem. Moreover, we regard the observation tensor as the training data set and choose a dictionary from it to improve the validity and efficiency of our inference approach. The dictionary selection method is designed by reducing the size of an overcomplete feature set extracted from the training dataset. Also, a dictionary self-updating mechanism is introduced to improve accuracy of the inference.Here are the key contributions we make in this paper.(i)
A dictionary selection approach based on group sparsity has been designed to generate a set containing minimal sizes of features to increase computational efficiency. Specifically, the observation tensor is considered to be the raw materials for feature extraction.(ii)
The sign inference problem referring to the weakly balanced mOSNs is formulated as a low-rank matrix reconstruction from the selected dictionary. Under certain mild conditions, a low-rank matrix reconstruction algorithm is applied to solve the sign inference problem, and it turns out to be much more accurate and efficient than other inference methods in the literature. A dictionary self-updating mechanism is also introduced to adjust the dynamic characteristics of the network and improve the sensing accuracy.The rest of this paper is organized as follows. In Section2, we build the model of the dynamic signed network. Some basics of balance theory are also reviewed for the sake of integrality. In Section 3, we first extract the initial candidate feature pool from the observation tensor and propose a dictionary selection approach. Then we propose our low-rank matrix reconstruction method to solve the sign inference problem. The implementation details of the dictionary self-updating procedure are also proposed. In Section 4, we conduct numerical experiments which demonstrate the validity of our network model for sign inference and justify the performance of our methods as well. Finally, we present our conclusions in Section 5.


## 2. Background and Preliminaries

### 2.1. Dynamic Signed Network Structure

Formally, a dynamic undirected signed network is represented as a dynamic graph𝒢=(𝒱,ℰ), where 𝒱 is the vertex set of size n and ℰ is the edge set varying over time. A network snapshot denoted by 𝒮t=(𝒱,ℰt,A(t)) presents the connections of 𝒢 observed at time t. Here, ℰt is the subset of ℰ and A(t)∈{-1,0,1}n×n is the adjacency matrix of 𝒮t with the signed weights
(1)aij(t)={1ifiandjhavepositiverelationship,-1ifiandjhavenegattiverelationship,0ifrelationshipbetweeniandjisunknown.Particularly, for each timet, a zero entry in A(t) is treated as an unknown relationship based on the acknowledgement that some potential attitudes exist between any two entities, even if the relationship itself is not observed. From this viewpoint, we can assume that there exists an underlying dynamics complete signed network 𝒢-, in which only some partial relationships are observed at times T0,T0+1,…,T0+T-1, respectively. Correspondingly, we let 𝒜-∈{-1,1}n×n×Tdenote the three-dimensional tensor that contains relationship information between all pairs of entities in 𝒢-. Thus, the observation tensor 𝒜 consisting of a series of network snapshots can be represented as
(2)𝒜i,j,t=aij(t)={𝒜-i,j,t,(i,j,t)∈Ω,0,otherwise,
where Ω is the index set of the observed entries. Let 𝒫Ω be the orthogonal projection operator onto the span of tensors vanishing outside Ω so that the (i,j,t)th component of 𝒫Ω(𝒳) is equal to 𝒳i,j,t when (i,j,t)∈Ω and zero otherwise. Then we have 𝒫Ω(𝒜-)=𝒜 (shown in Figure 1) and 𝒫Ωt(A-(t))=A(t) for each time slice t, where ⋂tΩt=∅ and ⋃tΩt=Ω.Illustration of the adjacency tensor, the cube units symbolize the data of relationships: (a) the adjacency tensor of the observed network and (b) the adjacency tensor of the underlying complete network.
(a)
(b)While the above kind of signed networks is called homogeneous, that is, relationships of the networks are between the same kinds of entities, a signed network can also be heterogeneous. In a heterogeneous signed network, there can be more than one kind of entities, and relationships between same or different entities can be positive and negative, such as YouTube with two kinds of entities—users and videos. Moreover, this three-dimensional network adjacency tensor can increase dimensions (e.g., spatial dimension, etc.) to adapt to a wider range of scenarios. In this paper, we mainly focus our attention on three-dimensional homogeneous signed networks.


### 2.2. Weak Structural Balance

Structural balance theory was first formulated by Heider [18] in order to understand the structure in a network of individuals whose mutual relationships are characterized in terms of friendship and hostility. Formally, a triad is considered balanced if the product of the signs in the triad is positive; that is, it contains an even number of negative edges. This is in agreement with principles such as “a friend of my friend is more likely to be my friend” and “an enemy of my friend is more likely to be my enemy” [6]. The configurations of balanced and unbalanced triads are shown in Figure 2. One possible weakness of this theory is that the defined balance relationships might be too strict. In this perspective, by extending the fundamental beliefs in real networks, weak structural balance is proposed as a way of eliminating the assumption that “the enemy of my enemy is my friend” [7]. Equivalently, the case that “the enemy of my enemy is my enemy” is permitted. Therefore, the local structure of weak balance posits that only triads with exactly two positive edges are implausible and that all other kinds of triads should be permissible (also illustrated in Figure 2).Signed undirected connectivity configurations mentioned in Section2.2: (i) (a) and (b) are balanced triads, (c) and (d) are unbalanced triads, and (ii) (a), (b), and (d) are weakly balanced triads.
(a)
(b)
(c)
(d)The formal definition of weakly balanced networks is as follows.Definition 1 (weakly balanced networks [7]).
A (possibly incomplete) network is weakly balanced if and only if it is possible to obtain a weakly balanced complete network by filling the missing edges in its adjacency matrix. Furthermore, in terms of patterns of global structure, a complete network is weakly balanced if and only if the vertex set can be divided intor clusters, r≥1, such that all the edges within clusters are positive and all the edges between clusters are negative.
There exists the literature discussing the approaches of clustering and sign prediction with respect to signed networks. Ideas derived from local balance of signed networks can be successfully used to yield algorithms for sign inference [9, 10]. Meanwhile, several works analyze the social interrelations from global perspective of structural balance [8, 13–15, 17]. In particular, it is shown in [8] that the adjacency matrix of weakly balanced networks has a “low-rank” structure, and the sign prediction methods based on low-rank modeling were proposed as well.Theorem 2 (low-rank structure of signed networks [8]).
The adjacency matrixA-∈{1,-1}n×n of a complete r-weakly balanced network has rank 1, if r≤2, and has rank r for all r>2.Actually, since the global viewpoint of weak balance stated in Definition1 obeys clustering characteristics presented in Theorem 2, for A-, there exists an invertible matrix P such that
(3)PA-PT=(1n11n2-11n3-1⋱1nr),
where 1ni on the primary diagonal is an ni-order square matrix whose entries are all 1 (∑i=1rni=n) and the other entries of PA-PT are all -1. The ni-order square matrix indicates the ith cluster.Notation. For X∈Rm×n, let the mixed norm ∥X∥2,1=∑i=1m∥Xi·∥2; the soft-thresholding operator 𝒟τ(·):X∈Rm×n↦Y∈Rm×n is also defined obeying
(4)Yi·={0if∥Xi·∥2≤τ,(1-τ∥Xi·∥2)Xi·otherwise,
where Xi· and Yi· denote the ith row of X and Y, respectively [15]. The invertible vectorization is denoted by vec(·):Rm×n↦Rmn.Let𝒮μ,L1,1(Rm×n) be the class of convex functions with Lipschitz gradient [19]. A continuous differentiable function f(Y) belongs to 𝒮μ,L1,1(Rm×n) for some 0≤μ≤L if for any X,Y∈Rm×n we have both of the following:
(5)∥∇f(X)-∇f(Y)∥F≤L∥X-Y∥F,〈∇f(X)-∇f(Y),X-Y〉≥μ∥X-Y∥F2.


## 2.1. Dynamic Signed Network Structure

Formally, a dynamic undirected signed network is represented as a dynamic graph𝒢=(𝒱,ℰ), where 𝒱 is the vertex set of size n and ℰ is the edge set varying over time. A network snapshot denoted by 𝒮t=(𝒱,ℰt,A(t)) presents the connections of 𝒢 observed at time t. Here, ℰt is the subset of ℰ and A(t)∈{-1,0,1}n×n is the adjacency matrix of 𝒮t with the signed weights
(1)aij(t)={1ifiandjhavepositiverelationship,-1ifiandjhavenegattiverelationship,0ifrelationshipbetweeniandjisunknown.Particularly, for each timet, a zero entry in A(t) is treated as an unknown relationship based on the acknowledgement that some potential attitudes exist between any two entities, even if the relationship itself is not observed. From this viewpoint, we can assume that there exists an underlying dynamics complete signed network 𝒢-, in which only some partial relationships are observed at times T0,T0+1,…,T0+T-1, respectively. Correspondingly, we let 𝒜-∈{-1,1}n×n×Tdenote the three-dimensional tensor that contains relationship information between all pairs of entities in 𝒢-. Thus, the observation tensor 𝒜 consisting of a series of network snapshots can be represented as
(2)𝒜i,j,t=aij(t)={𝒜-i,j,t,(i,j,t)∈Ω,0,otherwise,
where Ω is the index set of the observed entries. Let 𝒫Ω be the orthogonal projection operator onto the span of tensors vanishing outside Ω so that the (i,j,t)th component of 𝒫Ω(𝒳) is equal to 𝒳i,j,t when (i,j,t)∈Ω and zero otherwise. Then we have 𝒫Ω(𝒜-)=𝒜 (shown in Figure 1) and 𝒫Ωt(A-(t))=A(t) for each time slice t, where ⋂tΩt=∅ and ⋃tΩt=Ω.Illustration of the adjacency tensor, the cube units symbolize the data of relationships: (a) the adjacency tensor of the observed network and (b) the adjacency tensor of the underlying complete network.
(a)
(b)While the above kind of signed networks is called homogeneous, that is, relationships of the networks are between the same kinds of entities, a signed network can also be heterogeneous. In a heterogeneous signed network, there can be more than one kind of entities, and relationships between same or different entities can be positive and negative, such as YouTube with two kinds of entities—users and videos. Moreover, this three-dimensional network adjacency tensor can increase dimensions (e.g., spatial dimension, etc.) to adapt to a wider range of scenarios. In this paper, we mainly focus our attention on three-dimensional homogeneous signed networks.


## 2.2. Weak Structural Balance

Structural balance theory was first formulated by Heider [18] in order to understand the structure in a network of individuals whose mutual relationships are characterized in terms of friendship and hostility. Formally, a triad is considered balanced if the product of the signs in the triad is positive; that is, it contains an even number of negative edges. This is in agreement with principles such as “a friend of my friend is more likely to be my friend” and “an enemy of my friend is more likely to be my enemy” [6]. The configurations of balanced and unbalanced triads are shown in Figure 2. One possible weakness of this theory is that the defined balance relationships might be too strict. In this perspective, by extending the fundamental beliefs in real networks, weak structural balance is proposed as a way of eliminating the assumption that “the enemy of my enemy is my friend” [7]. Equivalently, the case that “the enemy of my enemy is my enemy” is permitted. Therefore, the local structure of weak balance posits that only triads with exactly two positive edges are implausible and that all other kinds of triads should be permissible (also illustrated in Figure 2).Signed undirected connectivity configurations mentioned in Section2.2: (i) (a) and (b) are balanced triads, (c) and (d) are unbalanced triads, and (ii) (a), (b), and (d) are weakly balanced triads.
(a)
(b)
(c)
(d)The formal definition of weakly balanced networks is as follows.Definition 1 (weakly balanced networks [7]).
A (possibly incomplete) network is weakly balanced if and only if it is possible to obtain a weakly balanced complete network by filling the missing edges in its adjacency matrix. Furthermore, in terms of patterns of global structure, a complete network is weakly balanced if and only if the vertex set can be divided intor clusters, r≥1, such that all the edges within clusters are positive and all the edges between clusters are negative.
There exists the literature discussing the approaches of clustering and sign prediction with respect to signed networks. Ideas derived from local balance of signed networks can be successfully used to yield algorithms for sign inference [9, 10]. Meanwhile, several works analyze the social interrelations from global perspective of structural balance [8, 13–15, 17]. In particular, it is shown in [8] that the adjacency matrix of weakly balanced networks has a “low-rank” structure, and the sign prediction methods based on low-rank modeling were proposed as well.Theorem 2 (low-rank structure of signed networks [8]).
The adjacency matrixA-∈{1,-1}n×n of a complete r-weakly balanced network has rank 1, if r≤2, and has rank r for all r>2.Actually, since the global viewpoint of weak balance stated in Definition1 obeys clustering characteristics presented in Theorem 2, for A-, there exists an invertible matrix P such that
(3)PA-PT=(1n11n2-11n3-1⋱1nr),
where 1ni on the primary diagonal is an ni-order square matrix whose entries are all 1 (∑i=1rni=n) and the other entries of PA-PT are all -1. The ni-order square matrix indicates the ith cluster.Notation. For X∈Rm×n, let the mixed norm ∥X∥2,1=∑i=1m∥Xi·∥2; the soft-thresholding operator 𝒟τ(·):X∈Rm×n↦Y∈Rm×n is also defined obeying
(4)Yi·={0if∥Xi·∥2≤τ,(1-τ∥Xi·∥2)Xi·otherwise,
where Xi· and Yi· denote the ith row of X and Y, respectively [15]. The invertible vectorization is denoted by vec(·):Rm×n↦Rmn.Let𝒮μ,L1,1(Rm×n) be the class of convex functions with Lipschitz gradient [19]. A continuous differentiable function f(Y) belongs to 𝒮μ,L1,1(Rm×n) for some 0≤μ≤L if for any X,Y∈Rm×n we have both of the following:
(5)∥∇f(X)-∇f(Y)∥F≤L∥X-Y∥F,〈∇f(X)-∇f(Y),X-Y〉≥μ∥X-Y∥F2.


## 3. Sign Inference via Dictionary Learning

In this section, we focus on a solution of the sign inference to estimate connection statuses via dictionary learning. As the preparation, we propose a large-scale dictionary selection method to generate the dictionary for inferring. Assume that we are given a (usually incomplete) network observation tensor𝒜 sampled from an underlying dynamic weakly balanced complete network 𝒢- with the adjacency tensor 𝒜-. As the description in Section 1, it is reasonable to suppose that most relationships between entities have their own stability in a long period of time in practice and subsequently the change in the scale of each subcommunity is limited. Apparently, this implies the strong dependence retained among the observed data. Combining these assumptions with the low-rank characteristic of weakly balanced complete networks, we extract an initial feature pool from the observation tensor 𝒜 and propose a dictionary selection method to compress the scale of the feature pool in Section 3.1. The corresponding algorithm is presented, respectively, in Section 3.2. With the trained dictionary, we propose our sign inference approach and dictionary updating mechanism in Section 3.3, which are also inspired by the low-rank characteristic of weakly balanced complete networks.The method we propose to handle the dictionary selection is motivated by the Singular Value Thresholding (SVT) algorithm, which is a simple and efficient algorithm for nuclear norm minimization problems proposed by Cai et al. [20]. Our basic idea is to obtain the optimal solution of the trace norm minimization problem by solving its dual problem whose objective function can be shown to be continuously differentiable with Lipschitz continuous gradient. Specifically, we prove that the optimal solution of the primary problem can be readily obtained from the optimal solution of the dual problem. We first provide a brief review of the standard SVT algorithm.Considering the problem(6)minXτ∥X∥*+12∥X∥F2subjectto𝒫Ω(X)=𝒫Ω(M),
Cai et al. [20] give a theoretical analysis that, when τ→∞, the optimal solution of problem (6) converges to that of the standard problem:
(7)minX∥X∥*subjectto𝒫Ω(X)=𝒫Ω(M).
Given that τ>0, the SVT algorithm operates as a linear Bregman iteration scheme. Furthermore, by defining the Lagrangian function of problem (6) as
(8)ℒ(X,Y)=τ∥X∥*+12∥X∥F2+〈Y,𝒫Ω(M-X)〉,
where Y is the Lagrangian dual variable, we can derive its dual function as
(9)f(Y)=infXℒ(X,Y).
Cai et al. show that SVT indeed optimizes the dual function f(Y) via the gradient ascent method.


### 3.1. Large-Scale Dictionary Selection

We address how to select the dictionary given an initial candidate feature pool in this subsection. To this end, we first extract an initial candidate feature pool from𝒜, which is sampled from 𝒜-. Since 𝒜- consists of the adjacency matrices A-(t)  (t=T0,T0+1,…,T0+T-1), the matrix A(t) in 𝒜 can retain the information of A-(t) more or less. Thus, we reserve the group of A(t) with relatively higher sample rate to extract features. We use singular value decomposition (SVD) to express each A(t) as a series of orthogonal bases in Hilbert space; that is,
(10)A(t)=∑r=1rtσr(t)ur(t)(vr(t))T=∑r=1rtσr(t)Ur(t),
where ur(t) and vr(t) are singular vectors of A(t) with eigenvalue σr(t), 1≤r≤rt. Without loss of generality, we sort σ1(t)≥σ2(t)≥⋯≥σrt(t) the singular values of A(t) in descending order, and set
(11)Lt=rt-argmaxr=1,…,rt-1(σr(t)≥σr+1(t)).
Then, due to the low-rank property of the weakly balanced complete adjacency matrix, we keep the group of Ur(t) corresponding to the Lt largest σr(t) as the features. By this procedure, we extract an initial candidate feature pool as {Ur(t):T0≤t≤T0+T-1,1≤r≤Lt}, where each matrix Ur(t)∈Rn×n denotes a feature. Equivalently, we can discuss 𝒬={vec(Ur(t)):T0≤t≤T0+T-1,1≤r≤Lt} and form the matrix Φ=[vec(U1),vec(U2),…,vec(US)] for convenience, where vec(Us)=vec(Ur(t)), 1≤r≤Lt, 1≤s≤S=∑tLt, and T0≤t≤T0+T-1.Due to massive data of the initial feature poolΦ, we hope to find an optimal subset to form the dictionary Ψ=[vec(U1),vec(U2),…,vec(UK)] such that the set Φ can be well reconstructed by Ψ and the size of Ψ is as small as possible. To achieve this goal, we select Ψ such that the rest of the features in Φ can be well reconstructed using it. Analogous to the optimization problem in [21], the basic problem is formulated as follows:
(12)minX∥X∥2,1subjecttoΦX=Φ,
where Φ∈RN×S  (N=n2), X∈RS×S, and ∥X∥2,1=∑i=1S∥Xi·∥2. Apparently, ∥X∥2,1 enforces the group sparsity on the variable X and the optimal solution usually contains zero rows. This means that not all features in Φ are necessary to be selected to reconstruct any data sample.Motivated by SVT, we have the equivalent problem of (12) as follows:
(13)minX∥X∥2,1+12∥X∥F2subjecttoΦX=Φ.
The Lagrangian function of problem (13) is defined as
(14)ℒ(X,Y)=τ∥X∥2,1+12∥X∥F2+〈Y,Φ-ΦX〉,
and its dual function is
(15)f(Y)=infXℒ(X,Y).
We first examine the properties of the dual function f(Y) and then show how to achieve the optimal solution of the problem (13) from its dual optimum directly. As the mixed norm ∥X∥2,1 is not differentiable, it is difficult to optimize the dual function f(Y) directly. However, we can obtain a useful property of the dual functionf(Y) as follows.Theorem 3.
For allτ≥0, the dual function f(Y) is continuously differentiable with Lipschitz continuous gradient at most M. Furthermore, the primal optimal X^ of the problem (13) is given by
(16)X^=𝒟τ(ΦY^),
when the dual optimal Y^ of the problem (13) is obtained.The proof of Theorem3 is based on the following results.Lemma 4.
For eachτ≥0 and Y∈Rm×n, one has
(17)𝒟τ(Y)=argminXτ∥X∥2,1+12∥X-Y∥F2.As a matter of fact, considering the following optimization problem:(18)minx∈Rτ|x|+12(x-y)2,
it is easy to show that the unique solution admits a closed form called the soft-thresholding operator, following a terminology introduced by Donoho and Johnstone [22]; it can be written that
(19)y^={0if|x|≤τ,(1-τ|x|)xotherwise.
Thus, from a generalized view, one has Lemma 4.Also, the following result can be deduced based on the properties of Moreau-Yosida regularization [23].Lemma 5.
For anyX,Y∈Rm×n, one has
(20)∥𝒟τ(X)-𝒟τ(Y)∥F2≤〈𝒟τ(X)-𝒟τ(Y),X-Y〉.
It follows that 𝒟τ(Y) is globally Lipschitz continuous with modulus 1.Proof of Theorem3.
Since(21)f(Y)=infXℒ(X,Y)=infX(τ∥X∥2,1+12∥X∥F2+〈Y,Φ-ΦX〉)=infX(τ∥X∥2,1+12∥X∥F2+〈Y,Φ〉-〈ΦTY,X〉)=infX(τ∥X∥2,1+12∥X-ΦTY∥F2)+〈Y,Φ〉-12∥ΦTY∥F2=g(Y)+〈Y,Φ〉-12∥ΦTY∥F2
and g(Y) is the Moreau-Yosida regularization of the mixed norm ∥·∥2,1, using the well-known properties of Moreau-Yosida regularization [23], we get the results that g(Y) is a globally continuously differentiable convex function. Moreover, ∇g(Y)=Φ(ΦTY-𝒟τ(ΦTY)) and ∇g(Y) is continuously differentiable with Lipschitz continuous gradient ρ; that is, for any Y1,Y2∈RN×S,
(22)∥∇g(Y1)-∇g(Y2)∥F≤∥ΦT(Y1-Y2)∥F≤ρ∥(Y1-Y2)∥F,
where ρ=sup∥Z∥F=1,Z∈RN×S∥ΦTZ∥F. Then the gradient of f(Y) can be obtained as follows:
(23)∇f(Y)=∇g(Y)+Φ-ΦΦTY=Φ(ΦTY-𝒟τ(ΦTY))+Φ-ΦΦTY=Φ-Φ𝒟τ(ΦTY).
It follows that, for any Y1,Y2∈RN×S,
(24)∥∇f2(Y1)-∇f2(Y2)∥F=∥Φ-Φ𝒟τ(ΦTY1)-Φ+Φ𝒟τ(ΦTY2)∥F=∥Φ(𝒟τ(ΦTY1)-𝒟τ(ΦTY2))∥F≤∥ΦΦT(Y1-Y2)∥F≤M∥Y1-Y2∥F,
where the first inequality follows from (20) and M=sup∥Z∥F=1,Z∈RN×S∥ΦΦTZ∥F. When the dual optimal Y^ is obtained, by using the result of (21), we can get
(25)X^=argminXℒ(X,Y)=argminX(τ∥X∥2,1+12∥X-ΦTY∥F2)=𝒟τ(ΦY^).
This concludes the proof.Sincef(Y) is the dual function of the objective function (13), f(Y) is concave. Let
(26)q(Y)=-f(Y)=-(12∥𝒟τ(ΦY)∥F2τ∥𝒟τ(ΦY)∥2,1=-(+12∥𝒟τ(ΦY)∥F2+〈Y,Φ-Φ𝒟τ(ΦY)〉),
which is convex. Thus, the following holds for any Y1,Y2∈RN×S:
(27)〈q(Y1)-q(Y2),Y1-Y2〉≥0.
It is also easy to show that q(Y) belongs to the class 𝒮0,M1,1(RN×S) and
(28)∇q(Y)=-Φ(I-𝒟τ(ΦTY^)),
where I∈RS×S is the identity matrix. Therefore, we can solve problem (13) by minimizing the objective function q(Y); that is,
(29)minYq(Y).
Therefore, the dictionary Ψ is selected by the optimal solution Y^; that is, the ith column of Φ is chosen to be the atom of Ψ if ∥Y^i·∥2≠0. The optimization algorithm is presented in the next subsection.


### 3.2. Optimization Methods

In this subsection, we develop an efficient optimization algorithm to solve the dual problem (29). Because the objective function q(Y) is continuously differentiable with Lipschitz continuous gradient, it is feasible to utilize gradient-based optimization methods to achieve the optimal solution for their simplicity and low complexity within each iteration. However, classical gradient-based methods for functions with Lipschitz continuous gradient converge at a rate of O(1/N), where N is the number of iterations during optimization [19]. In fact, this is too slow especially when dealing with large-scale datasets. Note that Nesterov showed in his work [24] that an accelerated gradient algorithm can be constructed such that O(1/N2), the lower bound on the convergence rate for gradient-based methods [25], is achieved when minimizing unconstrained smooth functions. With this consideration, in the following we propose an accelerated thresholding algorithm to solve these smooth convex optimization problems using Nesterov’s method with an adaptive line search scheme [19, 26].We recall Nesterov’s method with an adaptive line search scheme as follows. Take the unconstrained smooth convex minimization problemminy∈Rnq(y), for instance, where q(y) belongs to 𝒮μ,L1,1(Rn), μ≥0, and L<+∞. Nesterov’s method for this problem utilizes two sequences: {yl} and {sl}, yl,sl∈Rn. The searching point sl satisfies
(30)sl=yl+βl(yl-yl-1),
where βl is a tuning parameter. The approximate solution yl+1 can be computed as a gradient step of sl as
(31)yl+1=sl-1Ll∇q(sl),
where 1/Ll is the step size. Starting from an initial point y0, sl and yl+1 can be computed recursively according to (30) and (31) and can arrive at the optimal solution y^. Although it has been shown that Nesterov’s method is a very powerful optimization technique for class 𝒮μ,L1,1(Rn) [19], how to choose βl and 1/Ll in each iteration is a critical issue in Nesterov’s method. When they are set properly, the sequence {yl} can converge to the optimal y^ at a certain convergence rate. As a well-known scheme for setting βl and Ll, Nesterov’s constant scheme assumes βl and Ll to be constant [19], while Nemirovski’s line search scheme requires Ll to monotonically increase, and βl is independent of Ll [27]. Both of the settings result in slow convergence.To overcome this drawback, an adaptive line search scheme for Nesterov’s method is proposed in [26]. Under the assumption that μ~, the low bound of μ, is known in advance, this scheme is built upon the estimate sequence [19] defined as follows.Definition 6 (estimate sequence [19]).
A pair of sequences{ϕl(y)} and {λl≥0} is called an estimate sequence of function q(y) if limk→∞λk=0 and ϕl(y)≤(1-λl)q(y)+λlϕo(y), for all y∈Rn.The estimate sequence defined in Definition6 has the following important property.Theorem 7 (see [19]).
Let{ϕl(y)} and {λk≥0} be an estimate sequence. For any sequence {yl},   q(yl)-q^≤λk(ϕ0(y^)-q^)→0 if q(yl)≤ϕ^k≡miny∈Rnϕk(y), where q^ is the optimal objective function value.We further specify the estimation sequence in [19]:
(32)ϕl(y)=ϕ^l+γl2∥y-vl∥2,
where the sequences {γl}, {vl}, and {ϕ^l} satisfy
(33)vl+1=1γl+1((1-αl)γlvl+μ~αlsl-αl∇q(sl)),γl+1=(1-αl)γl+μ~αl,ϕ^l+1=(1-αl)ϕ^l+αlq(sl)-αl22γl+1∥∇q(sl)∥2+αl(1-αl)γlγl+1×(μ~2∥vl-sl∥2+〈∇q(sl),vl-sl〉).Then Algorithm  2 in [26] is proposed by modifying Nemirovski’s line search scheme with the adaptive parameters of this sequence, which satisfy Theorem 7.Note that Theorem3 indicates that the objective function q(Y) satisfies the conditions of using Nesterov’s method with an adaptive line search scheme. Therefore we directly extend Algorithm  2 in [26] to the high-dimensional scenarios to solve (29). The complete procedures are summarized in Algorithm 1.Algorithm 1:Adaptive line search scheme for dictionary selection.
(1)Input: μ~,α-1=0.5, Y-1=Y0, L-1=L0, γ0≥μ~,λ0=1
(2)Output: YN
(3)for  l=1,2,…,N  do
(4)while true do
(5)  computeαk∈(0,1) as the root of Llαl2=(1-αl)γl+αlμ~,
γl+1=(1-αl)γl+αlμ~,  βl=(1-αl-1)γl(γl+Llαl)αl-1;
(6)  computeSl=Yl+βl(Yl-Yl-1)
(7)  computeYl+1=Sl-(1/Ll)∇q(Sl)
(8)if  q(Yl+1)≤q(Sl)-(1/2Ll)∥∇q(Sl)∥F2  then
(9)   goto Step14
(10)else
(11)Ll=2Ll
(12)end if
(13)end while
(14)   setθ=2Llq(Sl)-q(Yl+1)∥∇q(Sl)∥F2,  Ll+1=h(θ)Ll
(15)   setλl+1=(1-αl)λl
(16)end forIn Algorithm1, the while loop from Step 4 to Step 13 is designed to choose a proper step size to satisfy Step 8. As the Lipschitz gradient of q(Y) is M, Ll is upper bounded by 2M since Step 8 always holds when Ll≥M [27]. In Step 14, we initialize Ll+1=h(θ)Ll, where
(34)h(θ)={1,1≤θ≤5,0.8,θ>5,
and θ>1 due to the condition in Step 8 [26]. Apparently, when θ is large, Ll+1 can be adjusted to avoid the step size 1/Ll becoming too small, which may slow down the convergence rate.


### 3.3. Sign Inference and Dictionary Update Mechanism

This subsection details how to use the dictionary to solve the sign inference problem. Actually, this problem bears similarity to the sign prediction problem in the static signed networks or the unsigned networks varying periodically [3, 8, 11, 12]. In this paper, we intend to infer the unknown relationship between a pair of entities i and j based on partial relationship observations of the entire dynamic network at time T0+T. We expect to accomplish this task with the help of the dictionary constructed by the relationship data for times T0 through T0+T-1. As aforementioned, there exists strong dependence between the connection status at time T0+T and the history relationship dataset in the dynamic network. We formulate the sign inference problem as follows:
(35)x^=argminx12∥y-Ψx∥22+∥x∥1,
where Ψ is the dictionary and y is the invertible vectorization of the matrix A(T0+T) observed at time T0+T; that is, y=vec(A(T0+T)). Because A-(T0+T)=∑rσr(T0+T)Ur(T0+T) by using SVD and subsequently vec(A-(T0+T))=∑rσr(T0+T)vec(Ur(T0+T)), we will estimate A-(T0+T) in the form of vector and transform the low-rank matrix reconstruction problem into a traditional l1-norm minimization problem in compressive sensing. We solve (35) by applying backtracking-based adaptive orthogonal matching pursuit (BAOMP) method, which incorporates a simple backtracking technique to detect the previously chosen atoms’ reliability and then deletes the unreliable atoms at each iteration [28]. Then we force that aij(T0+T), the element of the resulting matrix, is equal to 1 if aij(T0+T)>1 or equal to −1 if aij(T0+T)≤0, to ensure the elements coinciding with the value setting of relationships.Furthermore, assume that we are given a sequence input samplesY=[y(T0+T),y(T0+T+1),…,y(T~)], where y(t)=vec(A(t)), T0+T≤t≤T~, the task of the sign inference becomes to reconstruct the complete adjacency matrices A-(t) one by one. Since the A-(t) may contain some features which are not included in dictionary, it is necessary to add these features into the dictionary to increase the accuracy of the inference. However, the inferred matrix is not the original matrix exactly and consequently the unobserved relationships are not really known. In contrast, the observed adjacency matrix A(t) retains all existing relationships. For this reason, we only use A(t) to extract the features rather than the optimal solution of (35). We apply the extracting approach in Section 3.2 and add the complementary features into the dictionary. Note that this operation will continuously increase the scale of the dictionary while the samples keep inputting for inference; the dictionary selection approach proposed in Section 3.2 will be applied to compact the dictionary once the size of the dictionary exceeds a predetermined bound.


## 3.1. Large-Scale Dictionary Selection

We address how to select the dictionary given an initial candidate feature pool in this subsection. To this end, we first extract an initial candidate feature pool from𝒜, which is sampled from 𝒜-. Since 𝒜- consists of the adjacency matrices A-(t)  (t=T0,T0+1,…,T0+T-1), the matrix A(t) in 𝒜 can retain the information of A-(t) more or less. Thus, we reserve the group of A(t) with relatively higher sample rate to extract features. We use singular value decomposition (SVD) to express each A(t) as a series of orthogonal bases in Hilbert space; that is,
(10)A(t)=∑r=1rtσr(t)ur(t)(vr(t))T=∑r=1rtσr(t)Ur(t),
where ur(t) and vr(t) are singular vectors of A(t) with eigenvalue σr(t), 1≤r≤rt. Without loss of generality, we sort σ1(t)≥σ2(t)≥⋯≥σrt(t) the singular values of A(t) in descending order, and set
(11)Lt=rt-argmaxr=1,…,rt-1(σr(t)≥σr+1(t)).
Then, due to the low-rank property of the weakly balanced complete adjacency matrix, we keep the group of Ur(t) corresponding to the Lt largest σr(t) as the features. By this procedure, we extract an initial candidate feature pool as {Ur(t):T0≤t≤T0+T-1,1≤r≤Lt}, where each matrix Ur(t)∈Rn×n denotes a feature. Equivalently, we can discuss 𝒬={vec(Ur(t)):T0≤t≤T0+T-1,1≤r≤Lt} and form the matrix Φ=[vec(U1),vec(U2),…,vec(US)] for convenience, where vec(Us)=vec(Ur(t)), 1≤r≤Lt, 1≤s≤S=∑tLt, and T0≤t≤T0+T-1.Due to massive data of the initial feature poolΦ, we hope to find an optimal subset to form the dictionary Ψ=[vec(U1),vec(U2),…,vec(UK)] such that the set Φ can be well reconstructed by Ψ and the size of Ψ is as small as possible. To achieve this goal, we select Ψ such that the rest of the features in Φ can be well reconstructed using it. Analogous to the optimization problem in [21], the basic problem is formulated as follows:
(12)minX∥X∥2,1subjecttoΦX=Φ,
where Φ∈RN×S  (N=n2), X∈RS×S, and ∥X∥2,1=∑i=1S∥Xi·∥2. Apparently, ∥X∥2,1 enforces the group sparsity on the variable X and the optimal solution usually contains zero rows. This means that not all features in Φ are necessary to be selected to reconstruct any data sample.Motivated by SVT, we have the equivalent problem of (12) as follows:
(13)minX∥X∥2,1+12∥X∥F2subjecttoΦX=Φ.
The Lagrangian function of problem (13) is defined as
(14)ℒ(X,Y)=τ∥X∥2,1+12∥X∥F2+〈Y,Φ-ΦX〉,
and its dual function is
(15)f(Y)=infXℒ(X,Y).
We first examine the properties of the dual function f(Y) and then show how to achieve the optimal solution of the problem (13) from its dual optimum directly. As the mixed norm ∥X∥2,1 is not differentiable, it is difficult to optimize the dual function f(Y) directly. However, we can obtain a useful property of the dual functionf(Y) as follows.Theorem 3.
For allτ≥0, the dual function f(Y) is continuously differentiable with Lipschitz continuous gradient at most M. Furthermore, the primal optimal X^ of the problem (13) is given by
(16)X^=𝒟τ(ΦY^),
when the dual optimal Y^ of the problem (13) is obtained.The proof of Theorem3 is based on the following results.Lemma 4.
For eachτ≥0 and Y∈Rm×n, one has
(17)𝒟τ(Y)=argminXτ∥X∥2,1+12∥X-Y∥F2.As a matter of fact, considering the following optimization problem:(18)minx∈Rτ|x|+12(x-y)2,
it is easy to show that the unique solution admits a closed form called the soft-thresholding operator, following a terminology introduced by Donoho and Johnstone [22]; it can be written that
(19)y^={0if|x|≤τ,(1-τ|x|)xotherwise.
Thus, from a generalized view, one has Lemma 4.Also, the following result can be deduced based on the properties of Moreau-Yosida regularization [23].Lemma 5.
For anyX,Y∈Rm×n, one has
(20)∥𝒟τ(X)-𝒟τ(Y)∥F2≤〈𝒟τ(X)-𝒟τ(Y),X-Y〉.
It follows that 𝒟τ(Y) is globally Lipschitz continuous with modulus 1.Proof of Theorem3.
Since(21)f(Y)=infXℒ(X,Y)=infX(τ∥X∥2,1+12∥X∥F2+〈Y,Φ-ΦX〉)=infX(τ∥X∥2,1+12∥X∥F2+〈Y,Φ〉-〈ΦTY,X〉)=infX(τ∥X∥2,1+12∥X-ΦTY∥F2)+〈Y,Φ〉-12∥ΦTY∥F2=g(Y)+〈Y,Φ〉-12∥ΦTY∥F2
and g(Y) is the Moreau-Yosida regularization of the mixed norm ∥·∥2,1, using the well-known properties of Moreau-Yosida regularization [23], we get the results that g(Y) is a globally continuously differentiable convex function. Moreover, ∇g(Y)=Φ(ΦTY-𝒟τ(ΦTY)) and ∇g(Y) is continuously differentiable with Lipschitz continuous gradient ρ; that is, for any Y1,Y2∈RN×S,
(22)∥∇g(Y1)-∇g(Y2)∥F≤∥ΦT(Y1-Y2)∥F≤ρ∥(Y1-Y2)∥F,
where ρ=sup∥Z∥F=1,Z∈RN×S∥ΦTZ∥F. Then the gradient of f(Y) can be obtained as follows:
(23)∇f(Y)=∇g(Y)+Φ-ΦΦTY=Φ(ΦTY-𝒟τ(ΦTY))+Φ-ΦΦTY=Φ-Φ𝒟τ(ΦTY).
It follows that, for any Y1,Y2∈RN×S,
(24)∥∇f2(Y1)-∇f2(Y2)∥F=∥Φ-Φ𝒟τ(ΦTY1)-Φ+Φ𝒟τ(ΦTY2)∥F=∥Φ(𝒟τ(ΦTY1)-𝒟τ(ΦTY2))∥F≤∥ΦΦT(Y1-Y2)∥F≤M∥Y1-Y2∥F,
where the first inequality follows from (20) and M=sup∥Z∥F=1,Z∈RN×S∥ΦΦTZ∥F. When the dual optimal Y^ is obtained, by using the result of (21), we can get
(25)X^=argminXℒ(X,Y)=argminX(τ∥X∥2,1+12∥X-ΦTY∥F2)=𝒟τ(ΦY^).
This concludes the proof.Sincef(Y) is the dual function of the objective function (13), f(Y) is concave. Let
(26)q(Y)=-f(Y)=-(12∥𝒟τ(ΦY)∥F2τ∥𝒟τ(ΦY)∥2,1=-(+12∥𝒟τ(ΦY)∥F2+〈Y,Φ-Φ𝒟τ(ΦY)〉),
which is convex. Thus, the following holds for any Y1,Y2∈RN×S:
(27)〈q(Y1)-q(Y2),Y1-Y2〉≥0.
It is also easy to show that q(Y) belongs to the class 𝒮0,M1,1(RN×S) and
(28)∇q(Y)=-Φ(I-𝒟τ(ΦTY^)),
where I∈RS×S is the identity matrix. Therefore, we can solve problem (13) by minimizing the objective function q(Y); that is,
(29)minYq(Y).
Therefore, the dictionary Ψ is selected by the optimal solution Y^; that is, the ith column of Φ is chosen to be the atom of Ψ if ∥Y^i·∥2≠0. The optimization algorithm is presented in the next subsection.


## 3.2. Optimization Methods

In this subsection, we develop an efficient optimization algorithm to solve the dual problem (29). Because the objective function q(Y) is continuously differentiable with Lipschitz continuous gradient, it is feasible to utilize gradient-based optimization methods to achieve the optimal solution for their simplicity and low complexity within each iteration. However, classical gradient-based methods for functions with Lipschitz continuous gradient converge at a rate of O(1/N), where N is the number of iterations during optimization [19]. In fact, this is too slow especially when dealing with large-scale datasets. Note that Nesterov showed in his work [24] that an accelerated gradient algorithm can be constructed such that O(1/N2), the lower bound on the convergence rate for gradient-based methods [25], is achieved when minimizing unconstrained smooth functions. With this consideration, in the following we propose an accelerated thresholding algorithm to solve these smooth convex optimization problems using Nesterov’s method with an adaptive line search scheme [19, 26].We recall Nesterov’s method with an adaptive line search scheme as follows. Take the unconstrained smooth convex minimization problemminy∈Rnq(y), for instance, where q(y) belongs to 𝒮μ,L1,1(Rn), μ≥0, and L<+∞. Nesterov’s method for this problem utilizes two sequences: {yl} and {sl}, yl,sl∈Rn. The searching point sl satisfies
(30)sl=yl+βl(yl-yl-1),
where βl is a tuning parameter. The approximate solution yl+1 can be computed as a gradient step of sl as
(31)yl+1=sl-1Ll∇q(sl),
where 1/Ll is the step size. Starting from an initial point y0, sl and yl+1 can be computed recursively according to (30) and (31) and can arrive at the optimal solution y^. Although it has been shown that Nesterov’s method is a very powerful optimization technique for class 𝒮μ,L1,1(Rn) [19], how to choose βl and 1/Ll in each iteration is a critical issue in Nesterov’s method. When they are set properly, the sequence {yl} can converge to the optimal y^ at a certain convergence rate. As a well-known scheme for setting βl and Ll, Nesterov’s constant scheme assumes βl and Ll to be constant [19], while Nemirovski’s line search scheme requires Ll to monotonically increase, and βl is independent of Ll [27]. Both of the settings result in slow convergence.To overcome this drawback, an adaptive line search scheme for Nesterov’s method is proposed in [26]. Under the assumption that μ~, the low bound of μ, is known in advance, this scheme is built upon the estimate sequence [19] defined as follows.Definition 6 (estimate sequence [19]).
A pair of sequences{ϕl(y)} and {λl≥0} is called an estimate sequence of function q(y) if limk→∞λk=0 and ϕl(y)≤(1-λl)q(y)+λlϕo(y), for all y∈Rn.The estimate sequence defined in Definition6 has the following important property.Theorem 7 (see [19]).
Let{ϕl(y)} and {λk≥0} be an estimate sequence. For any sequence {yl},   q(yl)-q^≤λk(ϕ0(y^)-q^)→0 if q(yl)≤ϕ^k≡miny∈Rnϕk(y), where q^ is the optimal objective function value.We further specify the estimation sequence in [19]:
(32)ϕl(y)=ϕ^l+γl2∥y-vl∥2,
where the sequences {γl}, {vl}, and {ϕ^l} satisfy
(33)vl+1=1γl+1((1-αl)γlvl+μ~αlsl-αl∇q(sl)),γl+1=(1-αl)γl+μ~αl,ϕ^l+1=(1-αl)ϕ^l+αlq(sl)-αl22γl+1∥∇q(sl)∥2+αl(1-αl)γlγl+1×(μ~2∥vl-sl∥2+〈∇q(sl),vl-sl〉).Then Algorithm  2 in [26] is proposed by modifying Nemirovski’s line search scheme with the adaptive parameters of this sequence, which satisfy Theorem 7.Note that Theorem3 indicates that the objective function q(Y) satisfies the conditions of using Nesterov’s method with an adaptive line search scheme. Therefore we directly extend Algorithm  2 in [26] to the high-dimensional scenarios to solve (29). The complete procedures are summarized in Algorithm 1.Algorithm 1:Adaptive line search scheme for dictionary selection.
(1)Input: μ~,α-1=0.5, Y-1=Y0, L-1=L0, γ0≥μ~,λ0=1
(2)Output: YN
(3)for  l=1,2,…,N  do
(4)while true do
(5)  computeαk∈(0,1) as the root of Llαl2=(1-αl)γl+αlμ~,
γl+1=(1-αl)γl+αlμ~,  βl=(1-αl-1)γl(γl+Llαl)αl-1;
(6)  computeSl=Yl+βl(Yl-Yl-1)
(7)  computeYl+1=Sl-(1/Ll)∇q(Sl)
(8)if  q(Yl+1)≤q(Sl)-(1/2Ll)∥∇q(Sl)∥F2  then
(9)   goto Step14
(10)else
(11)Ll=2Ll
(12)end if
(13)end while
(14)   setθ=2Llq(Sl)-q(Yl+1)∥∇q(Sl)∥F2,  Ll+1=h(θ)Ll
(15)   setλl+1=(1-αl)λl
(16)end forIn Algorithm1, the while loop from Step 4 to Step 13 is designed to choose a proper step size to satisfy Step 8. As the Lipschitz gradient of q(Y) is M, Ll is upper bounded by 2M since Step 8 always holds when Ll≥M [27]. In Step 14, we initialize Ll+1=h(θ)Ll, where
(34)h(θ)={1,1≤θ≤5,0.8,θ>5,
and θ>1 due to the condition in Step 8 [26]. Apparently, when θ is large, Ll+1 can be adjusted to avoid the step size 1/Ll becoming too small, which may slow down the convergence rate.


## 3.3. Sign Inference and Dictionary Update Mechanism

This subsection details how to use the dictionary to solve the sign inference problem. Actually, this problem bears similarity to the sign prediction problem in the static signed networks or the unsigned networks varying periodically [3, 8, 11, 12]. In this paper, we intend to infer the unknown relationship between a pair of entities i and j based on partial relationship observations of the entire dynamic network at time T0+T. We expect to accomplish this task with the help of the dictionary constructed by the relationship data for times T0 through T0+T-1. As aforementioned, there exists strong dependence between the connection status at time T0+T and the history relationship dataset in the dynamic network. We formulate the sign inference problem as follows:
(35)x^=argminx12∥y-Ψx∥22+∥x∥1,
where Ψ is the dictionary and y is the invertible vectorization of the matrix A(T0+T) observed at time T0+T; that is, y=vec(A(T0+T)). Because A-(T0+T)=∑rσr(T0+T)Ur(T0+T) by using SVD and subsequently vec(A-(T0+T))=∑rσr(T0+T)vec(Ur(T0+T)), we will estimate A-(T0+T) in the form of vector and transform the low-rank matrix reconstruction problem into a traditional l1-norm minimization problem in compressive sensing. We solve (35) by applying backtracking-based adaptive orthogonal matching pursuit (BAOMP) method, which incorporates a simple backtracking technique to detect the previously chosen atoms’ reliability and then deletes the unreliable atoms at each iteration [28]. Then we force that aij(T0+T), the element of the resulting matrix, is equal to 1 if aij(T0+T)>1 or equal to −1 if aij(T0+T)≤0, to ensure the elements coinciding with the value setting of relationships.Furthermore, assume that we are given a sequence input samplesY=[y(T0+T),y(T0+T+1),…,y(T~)], where y(t)=vec(A(t)), T0+T≤t≤T~, the task of the sign inference becomes to reconstruct the complete adjacency matrices A-(t) one by one. Since the A-(t) may contain some features which are not included in dictionary, it is necessary to add these features into the dictionary to increase the accuracy of the inference. However, the inferred matrix is not the original matrix exactly and consequently the unobserved relationships are not really known. In contrast, the observed adjacency matrix A(t) retains all existing relationships. For this reason, we only use A(t) to extract the features rather than the optimal solution of (35). We apply the extracting approach in Section 3.2 and add the complementary features into the dictionary. Note that this operation will continuously increase the scale of the dictionary while the samples keep inputting for inference; the dictionary selection approach proposed in Section 3.2 will be applied to compact the dictionary once the size of the dictionary exceeds a predetermined bound.


## 4. Numerical Experiment

In this section, we perform experiments on synthetic networks and show that our low-rank model and dictionary learning method outperform other methods on the task of the sign inference for dynamic signed networks. To ensure that our results are reliable, we conduct all experiments 20 times and average out the results from all of the trials.To construct synthetic networks, we first consider a weakly balanced complete network𝒢- whose adjacency tensor is 𝒜-. The slide of 𝒜- at time t is an adjacency matrix A-(t) in the form of (3). In addition, only a few patterns of A-(t) exist in 𝒜-. The observation tensor 𝒜 is formed by sampling some entries from 𝒜-. Concretely, we let the adjacency tensor 𝒜- of 𝒢- consist of 50 250×250 matrices of complete 4-weakly balanced structure. For the network 𝒢-, four clusters are generated randomly. The size of each cluster is larger than 20 and the sum of the sizes is 250. We further assume that only a part of network relationships is observed by uniform sampling with probability p∈(0,1). It results in n2p entries being randomly sampled from A-(t), where p is the fraction of observed entries. We choose a set of matrices whose lost rates are from 0.05 to 0.55 and apply the approach proposed in Section 3.2 to select the dictionary Ψ.With the dictionaryΨ and the given observed matrix A(t) at time t≥T0+T, the task of the sign inference is achieved by solving (35). We use BAOMP to estimate the complete matrix A-(t) and compare the performance of our approach to two state-of-the-art methods, alternating least square (ALS) [29] and singular value projection (SVP) [30], for the sign inference problem. Different from accuracy defined by the relative error on the observed set in [8], we utilize the similarity between the inferred matrix and the original one to indicate the accuracy of estimation. The definition of the similarity is |〈A-(t),A^(t)〉|/∥A-(t)∥F∥A^(t)∥F. We vary the lost-rate of the original matrix A-(t) from 0.5 to 0.999 and plot the inference accuracy in Figure 3 (lost-rate: 0.5, 0.6, 0.7, 0.8, 0.9, 0.95, 0.96, 0.97, 0.98, 0.99, 0.995, and 0.999). Apparently, dictionary learning outperforms ALS and SVP. To present our result more clearly, we also use a visual expression in which the white pixels represent 1 and the black pixels represent −1. Figure 4 shows one example of the sign inference and we find that relationships and the clusters can almost be accurately estimated by our inference approach.Figure 3
Accuracy of sign inference algorithms on synthetic datasets. In general, we can see that dictionary learning outperforms ALS and SVP.An example of the sign inference. (a) illustrates the original matrix. Given the matrix with 98% lost-rate, (b) is the result inferred by dictionary learning method. The similarity of inferred matrix is 0.9347.
(a)
(b)


## 5. Conclusion

In this paper, we establish a low-rank tensor model for the dynamic weakly balanced signed networks. With this model, we first extract the feature pool and propose an approach to extract the compact dictionary from pool. To improve the performance of the selection approach, we derive the corresponding dual problem and introduce an accelerated thresholding algorithm to solve the dual problem. Consequently, the optimal solution of the primary problem can be readily obtained from optimizing the dual problem. In addition, combined with the compact dictionary generation method, the sign inference approach is provided for estimating missing relationships of the dynamic weakly balanced signed networks at a certain time slice. Also, the approach is endowed with the function of the dictionary updating if relationship statuses change.



---

*Source: 708581-2013-12-03.xml*