## 3 Sentiment Classification
### Probability Model
This need can be circumvented by using other methods that calculate the labels for all unknown elements, such as loopy belief propagation. Alternatively, some works exploit the fact that SampleRank can also output the set of labels in addition to the value for \(\phi\)[2]. When used in this manner, training can be interpreted as a search in the space of possible labels, and the log-likelihood function is a heuristic that restricts the search. This method has been used successfully for user classification [2], and its main advantage is that it is simpler than using an additional layer of label propagation. Our proposed classification algorithm (Algorithm 1) is a modified version of SampleRank, which returns the labels for both users and content. ```
1:\(B_{u}:\{(u,p)\mid u\in U,p\in Polarities\}\)\(\triangleright\) Known user labels \(B_{c}:\{(c,p)\mid c\in C,p\in Polarities\}\)\(\triangleright\) Known content labels \(L_{u}:\{(i,j)\mid i,j\in U\}\)\(\triangleright\) Edges connecting users \(E_{uc}:\{(u,c)\mid u\in U,c\in C\}\)\(\triangleright\) Edges between users and content \(P:L^{N}\rightarrow\mathbb{R}\)\(\triangleright\) Performance (accuracy) \(\psi:L^{N}\times P^{N}\rightarrow\mathbb{R}\)\(\triangleright\) Objective function Output\(L_{u}\)\(\triangleright\) Estimated user labels \(L_{c}\)\(\triangleright\) Estimated content labels \(\phi\)\(\triangleright\) Learned weights
1:\(E_{u}\gets CD(E_{u})\)\(\triangleright\) Community detection. This is skipped in CrankNoComm
2:\(L_{u},L_{c}\gets Random(L_{u},L_{c})\)
3:\(Stale\gets 0\)
4:for\(step\gets 1\) to MaxStepsdo
5:\(L_{unnew},L_{cnew}\gets Sample(L_{u},L_{c})\)\(\triangleright\) Randomly modify only one label
6:\(\
abla\leftarrow\psi(L_{unnew},L_{cnew}B_{u},B_{c},E_{u},E_{uc})-\psi(L_{u},L_{c},B_{u},B_{c},E_{u},E_{uc})\)
7:\(\Delta P\gets P(L_{unnew},L_{cnew})-P(L_{u},L_{c})\)
8:if\(\phi\cdot\
abla>0\wedge\Delta P<0\)\(\triangleright\) Performance is worse, objective is better
9:\(\phi\leftarrow\phi-\eta\
abla\)\(\triangleright\) Performance is better, objective is worse
10:elseif\(\phi\cdot\
abla<0\wedge\Delta P>0\)then
11:\(\phi\leftarrow\phi+\eta\
abla\)\(\triangleright\) Converge if there are no changes in a given number of steps
12:if\(\
abla\leq 0\wedge P(L_{cnew},L_{u})\leq 0\)then
13:\(Stale\gets Stale+1\)
14:if\(Stale>=\)Convergencethenreturn
15:else
16:\(Stale\gets 0\)
17:if\(\Delta P>0\vee(\Delta P=0\wedge\phi\cdot\
abla>0)\)then\(\triangleright\) Performance is better, and objective function is at least the same
18:\(L_{u}\gets L_{unnew}\)
19:\(L_{c}\gets L_{cnew}\)
20:
```  
**Algorithm 1** Sentiment detection. In this algorithm, the \(Random(L_{u},L_{c})\) function returns a random set of user and content labels (within the range of \( Polarities\), which in a simple case would just be negative and positive). \(E_{u}\) represents edges between users, i.e., either relations or interactions. The \(CD(E_{u})\) function performs community detection given a set of edges and returns the set of edges between all users within the same community. In particular, we are using the Louvain method [36]. The \(Sample(L_{u},L_{c})\) function changes one of the labels from either \(L_{u}\) or \(L_{c}\), at random. Since the SampleRank algorithm is inherently stochastic, the model should be run several times, and the results of each run should be aggregated. In our case, we used a number of 21 iterations, based on earlier works [32], and simple majority over all iterations.