Recommending individuals through keywords is an essential and common search task in online social platforms such as Facebook and LinkedIn. However, it is often that one has only the impression about the desired targets, depicted by labels of social contexts (e.g. gender, interests, skills, visited locations, employment, etc). Assume each user is associated a set of labels, we propose a novel task, Search by Social Contexts (SSC), in online social networks. SSC is a kind of query-based people recommendation, recommending the desired target based on a set of user-specified query labels. We develop the method Social Query Embedding Learning (SQEL) to deal with SSC. SQEL aims to learn the feature representation (i.e., embedding vector) of the query, along with user feature vectors derived from graph embedding, and use the learned query vectors to find the targets via similarity. Experiments conducted on Facebook and Twitter datasets exhibit satisfying accuracy and encourage more advanced eforts on search by social contexts.
Users in online social services such as Facebook, Instagram, and LinkedIn, often perform search tasks to find the particular persons. Given the name of the target person specified, the goal of social search is usually to accurately recommend targets who are user desires. However, it is every now and then that users have no idea about the names of the targets, and have only very limited information about the targets (e.g. gender, interests, hometown, company, and graduated school). On the other hand, sometimes users want to find some persons (e.g. experts or celebrities) who meet some requirements (e.g. skills, awards, and visited locations). The common settings of both scenarios is that the target persons can be depicted by a set of labels. We think it is potential to develop a system allowing such kind of social search without specifying the names of targets. In this paper, we propose a novel search task, Search by Social Contexts (SSC), which is to find the desired targeted persons using the social network behind users and the Copyright © CIKM 2018 for the individual papers by the papers' authors. Copyright © CIKM 2018 for the volume as a collection by its editors. This volume and its papers are published under the Creative Commons License Attribution 4.0 International (CC labels associated on users. SSC can be also considered as a querybased people recommendation. By specifying a small set of labels depicting the target, rather than her name, SSC is designed to recommend a list of persons such that the true desired target is covered and ranked at the top position in the list.
The proposed Search by Social Contexts lies in that there should be latent correlation between the input query labels and the target through the interactions between users and labels and the connections between users in social networks. To perform search and recommendation by contexts, we leverage the technique of node feature representation learning in graphs to model the hidden correlation between query labels and potential target users in the latent space. A novel method, Social Query Embedding Learning (SQEL), is developed to learn the feature representation (i.e., embedding vector) of the query, and use the learned feature vector to find the users with highest vector similarity scores as the recommended targets. Here is our basic idea: the query embedding feature vector is a certain ensemble of an accurate query language model and the proximity distribution between the query and other labels. The former depicts the semantic similarity considering the interactions between users and labels in the latent feature space, while the latter quantifies the connectivity of query labels in the graph structure. We conduct the experiments using Facebook and Twitter datasets to validate whether SQEL can truly find the targets. The results exhibit that SQEL outperforms a number of competing methods in terms of accuracy.
Related Work. J. Kleinberg [
We first define a number of terms and notations, followed by the problem definition of Search by Social Contexts.
graph G = (V , E). Each node v has a set of labels. Each edge represents the interaction between two nodes. Edge weights refer to the interaction cost, where lower values indicate better interactions.
of labels q, in which ∀ci ∈ q : ci ∈ L, where L is the universe set of labels.
ri j = ui , cj is a connection that links user ui ∈ V with label cj ∈ L if ui possesses cj . We can have a set of user-label interaction R = {ri j } from all of the interactions between users and labels.
Definition 4: Hybrid Graph. A hybrid graph is a weighted graph H = (V, E), where the node set is the union of user set V and label set L, i.e., V = V ∪ L, and the edge set is the union of social tie set E and user-label interaction set R, i.e., E = E ∪ R. Note that we create a node for each label in the hybrid graph. The hybrid graph can be considered to jointly model the connections between users and the interactions between users and labels.
a social network G, the label set L, the user-label interaction R, the context query q, and the budget parameter k, the task of search by social contexts (SSC) is to recommend a ranking list of k users S (|S | = k) such that the ground-truth target u⋆ can be not only covered by list S (i.e., u⋆ ∈ S), but also accurately ranked at the highest position in list S. 3
To deal with the task of search by social contexts, we propose a novel
method, Social Query Embedding Learning (SQEL). The main idea of
SQEL is to learn the feature representation (i.e., embedding vector)
of the query, and use the learned feature vector to find the users
with highest vector similarity scores as the results. SQEL consists
of four main steps. First, based on the constructed hybrid graph,
we can learn the feature representation of each node using the
technique of node2vec [
We aim to leverage the technique of maximum likelihood estimation
(MLE) to learn the feature representation (i.e., embedding vector)
of the query. The central idea of our method is to maximize the
likelihood of an query embedding probabilistic distribution towards
a query language model and the proximity distribution from query
labels to other labels in the hybrid graph H . The underlying
assumption is that the query feature vector is a certain ensemble of
query language model and the graph proximity distribution. The
query feature vector is required to be reflected by not only the
co-occurrence between labels, but also how users adopt labels in
the graph. In other words, we seek to learn the query embedding
feature vector that is close to the fusion of the query language
model and the graph proximity distribution by MLE. Here we first
define the probability of each label c given a query vector q®, termed
query embedding distribution, as below:
p(c |q®) = Íc′ ∈L s(c®′, q®)
where s(·, ·) is a similarity function that calculates the similarity
between two feature vectors, c® is the embedding feature vector
of label c, and L is the set of all labels. Then for the query q, we
assume that there is a query language model θq , which quantifies
the importance of each query label ci ∈ q in the query. Let q®⋆ be
the optimal query feature vector, which is the query embedding
vector (Eq. 1 that is closest to the ensemble of the query language
model θq and the proximity distribution pH (q → c). Therefore,
we propose to find the query feature vector that maximizes the
following log-likelihood function:
(1)
(3)
q®⋆ = arg max Õ
q® c ∈L
α · p(c |θq ) + (1 − α ) · pH (q → c) ·
i=0 c®i q®i !
Íd
∥q®∥
(4)
q®⋆ = arg max Õ
q® c ∈L
α · p(c |θq ) + (1 − α ) · pH (q → c) log p(c |q®),
(2)
where the proximity distribution from query labels to other labels
pH (q → c) is derived using Random Walk with Restart [
We take advantage of softmax function to estimate the similarity between learned feature vectors of labels. We can define the similarity function s(·, ·) as below: s(c®, c®′) = exp
i=0 c®i c®i′ ! , Íd ∥c®∥ ∥c®′∥ where d is the dimension of learned feature vectors. We assume that each learned feature vector of label is a unit vector, i.e., the norm equals to 1, under the setting without loss of generality. Then we can rewrite the objective function from Eq. 2 to the following: By letting the query feature vector be a unit vector, i.e., ∥q ∥ = 1, we can have the objective function in the form of Lagrange function: abovementioned conditional independence between query labels, we can have the query language model as below: (8) (9) p(c |θq ) ≈ p(c1, c2, · · · , ck |c)p(c) = p(c) p(ci |c), where {ci |i = 1, 2, · · · , k } are the set of query labels, and k is the size of query label set. We compute p(ci |c) in Eq. 8 using the similarity formula Eq. 3 with the learned embedding feature vectors that depict the high-order relationships between labels and users in the hybrid graph, as follows. k Ö i=1 α · p(c |θq ) + (1 − α ) · pH (q → c) ( ∂∂qL®i = Íc ∈L c®i α · p(c |θq ) + (1 − α ) · pH (q → c) − 2λq®i ∂∂Lλ = 1 − Ídi=1 (q®i )2 , (6) where q®i is the i-th value of query feature vector q®. By setting the partial derivatives in Eq. 6 as zero, we can obtain the closed-form solution of our objective as follows: Íc ∈L c®i α · p(c |θq ) + (1 − α ) · p(q → c) Íc ∈L c®j α · p(c |θq ) + (1 − α ) · pH (q → c) 2 . (7) Eventually we can have the query feature vector q®i using the closedform formula in Eq. 7. 3.2
Since our goal is to recommend a ranking list of k targeted users S, we aim at estimating the social afinity between the query q and each user ui ∈ V based on the learned embedding vectors of users and query u®i and q®. Users with higher social afinity scores to the query are considered as more relevant to the query, and thus are ranked at higher positions in the final list S. We select the top k users with highest social afinity scores. We define the social afinity δ (ui , q) between user ui and query q using the similarity between two s(u®i,q®) . We can embedding vectors defined in Eq. 3: δ (ui , q) = Íj s(u®j,q®) simplify the computation of δ (ui , q) by discarding the denominator because it is the same for all users, i.e., δ (ui , q) ≈ s(u®i , q®). 3.3
The word embedding techniques have been validated to improve
the accuracy of document retrieval [
In order to estimate the query language model p(c |θq ), the Bayes rule is applied: p(c |θq ) = p(θqp|(cq))p(c) ≈ p(θq |c)p(c) (the term p(q) can be neglected as it is independent of label c). Based on the p(ci |c) = Í s(c®i , c®) cj ∈L s(c®j , c®) .
In addition, we can to compute p(c) based on the law of total probability: p(c) ≈ Ícj ∈L s(c®j , c®). A label with higher similarity with all the other labels will derive higher probability. 4
The experiments are conducted using Facebook and Twitter social network data provided by SNAP1. The data statistics are shown in Table 1, in which CC means clustering coeficient while APL refers to average path length in the social network G. Labels in both data used include the terms of school, hometown, employer, skill, gender, location, position, etc. In the social networks, we compute the edge weights using the Jaccard coeficient: wu,v = 1 − (|Lu ∩ Lv |/|Lu ∪ Lv |), where Lu is the set of labels of node u. Our general aims at examining whether or not the proposed SQEL can help accurately find the desired targets for the task of search by social contexts.
Table 1: Statistics of Facebook and Twitter data.
Twitter #nodes 4,039 81,306
CC 0.606 0.565
APL 4.7 4.5
We compare SQEL with four competing methods: (a) label
matching (LM): using the query label set Q to find a list of possible
target users u such that the labels of u have the highest
overlap with Q, LM(u, Q) = |Lu ∩Q | ; (b) Center-Piece Subgraph (CePS)
|Lu |
[
In the evaluation setting, we first choose users in a random
manner as the ground-truth targets. Then for each ground-truth
target user u¯, we randomly select k labels from the label set of
users {u¯} ∪ N (u¯), denoted by L {u¯ }∪N(u¯), to be the query label set
Qu¯ , where N (u¯) is the immediate neighbors of user u¯ in the social
network G, LX = ÐvinX Lv is the union of label sets of users X , and
1http://snap.stanford.edu/data/egonets-Facebook.html
http://snap.stanford.edu/data/egonets-Twitter.html
|Qu¯ | = k. Here we set k = 10 by default, and will vary k to simulate
diferent knowledge extent about the target. To control the hardness
of the search task, we introduce a hardness parameter τ ∈ [
The evaluation plan consists of two parts. The first is General Evaluation: varying the number of query labels k = |Q | to show the performance of SQEL. A larger Q set means that the query contains more information depicting the target. The second is sensitivity analysis: varying the hardness τ – higher τ will introduce more indirect labels that might be less relevant to the target, and thus make the task more dificult; and vary the parameter α in Eq. 2 – higher α will make the query embedding more significantly learned from the query language model.
Experimental results are shown in Figure 1. By varying the number of query labels k, we can find that the proposed SQEL outperforms the other competing methods, especially when the number of query labels increases. It is because more labels provide more evidences about the desired targets. Though the integration (CePS+LM) of structural connectivity in CePS and label matching in LM can boost the efectiveness, the accuracy values are still lower than SQEL. In addition, SQEL also clearly and consistently outperforms the recent work POI-Search. These results imply that learning the feature representation of query and users can efectively capture the search intent and accurately obtain the targets.
Figure 2 shows the results of sensitivity analysis for the parameters of (a) the hardness τ and (b) α that determines the importance between query language model and proximity distribution in Eq. 2. We can apparently find, in Figure 2(a) that higher values of τ lead to lower accuracy scores while lower τ produces better performance, since more labels describing the target make the task easier.
The results are consistent in both Facebook and Twitter datasets. On the other hand, in Figure 2(b), too high or too low values of α values lead to worse accuracy scores. The performance tends to be better when alpha is around 0.7, which is therefore used as the default value. Such results also inform us the influence of query language model is more significant than the proximity distribution in learning query representation. 5
This paper proposes the task of Search by Social Contexts (SSC) to recommend the target individuals desired by the user based on a set of query labels in social networks. The main technical contribution is the novel development of Social Query Embedding Learning (SQEL), which learns the feature representation of the query considering the query language model and the proximity distribution in a user-label interaction hybrid graph. Experimental results show promising accuracy. We will also evaluate SQEL using a user study by a developing Facebook application. The future work is to extend SSC by imposing spatio-temporal contexts – the targets are required to reflect the current time and location of the user.