TransNet: Translation-Based Network Representation Learning for Social Relation Extraction

1 Introduction

How to represent networks is critical for network analysis, such as vertex classification [Lindamood et al., 2009], clustering [Shepitsen et al., 2008] and link prediction [LibenNowell and Kleinberg, 2007]. Typically, researchers employ one-hot representation and treat each vertex as a unique symbol. Such representation method is fairly simple. Nevertheless, it faces the sparsity issue, and deteriorates the performance of many machine learning algorithms when applied to network analysis tasks.

Inspired by recent trends of representation learning on image, speech and natural language, network representation learning (NRL) is proposed as an efficient technique to address the sparsity issue. NRL aims to encode the structure information of each vertex into a low-dimensional real-valued vector, which can be further utilized as features in various network analysis tasks.

There have been a large amount of NRL models proposed in recent years. These models tend to learn efficient vertex representations from local structure [Perozzi et al., 2014;

∗Corresponding Author: Zhiyuan Liu

Tang et al., 2015] or global patterns [Cao et al., 2015; Tu et al., 2016a]. Besides, there are also some works proposed to incorporate heterogeneous information into NRL, such as text [Yang et al., 2015] and labels [Tu et al., 2016b; Li et al., 2016].

What calls for special attention is that most existing NRL models neglect the semantic information of edges. As one of the essential network components, the edge is usually simplified as a binary or continuous value in conventional NRL models and most network analysis tasks. It is intuitive that such simplification can not model rich information of edges well. It is also well-acknowledged that the interactions between vertices in real-world networks exhibit rich and variant meanings. For example, the following behaviors to the same user in social media may be caused by different reasons; two authors have co-authored with another one in an academic network due to various common interests. Therefore, it is essential to integrate the detailed relation information of edges into NRL, which is expected to enable extracting latent relations between vertices in return.

In this work, we propose the task of Social Relation Extraction (SRE) to model and predict social relations for social networks. SRE is similar to the task of relation extraction in knowledge graphs (KG), for which the most widelyused methods are knowledge representation learning (KRL) such as TransE [Bordes et al., 2013]. The difference is that there are usually no well pre-defined relation categories in SRE, and relations between vertices are typically hidden in their interactive text (such as co-authored papers between two researchers). It is intuitive that social relations can be represented by key phrases extracted from the interactive text, and there are usually multiple relational labels to indicate the complex relation between two vertices.

SRE cannot be well addressed by existing NRL and KRL methods. Conventional NRL models ignore the rich semantic information on edges when learning vertex representations, while typical KRL models such as TransE only perform well when the relation between two entities is specifically annotated with a single label. According to our statistics, only 18% entity pairs in FB15k (a typical KG) possess multiple relation labels, while the percentages of multi-label edges in SRE datasets are severalfold. To address this issue, we present a novel translation-based NRL model TransNet to incorporate multiple relational labels on edges into NRL.

"Translation" here means the movement that changes the position of a vector in representation space. Inspired by the successful utilization of translation analogy in word representation [Mikolov et al., 2013] and KGs [Bordes et al., 2013], we embed vertices and edges into the same semantic space and employ a translation mechanism to deal with the interactions among them, i.e., the representation of tail vertex should be close to the representation of head vertex plus the representation of edge. To handle the multi-label scenario, in TransNet we design an auto-encoder to learn edge representations. Moreover, the decoder part can be utilized to predict labels of unlabeled edges.

We construct three network datasets for SRE, in which edges are annotated with a set of labels. Experimental results show that TransNet achieves significant and consistent improvements comparing with typical NRL models and TransE. It demonstrates that our proposed TransNet is efficient and powerful on modeling relationships between vertices and edges.

To summarize, we make the following contributions:

1. We are the first to formalize social relation extraction (SRE) for evaluating the effectiveness of NRL models.
2. We propose a novel translation-based NRL model, TransNet, to incorporate the semantic information of edges. As a simple and straightforward model, it models the relationships among vertices and edges with translation mechanism.
3. We collect three annotated datasets for SRE, and experimental results on these datasets demonstrate the outstanding capabilities of TransNet to model and predict the relations between vertices.

2 RelatedWork

Recently, network representation learning (NRL) becomes an active research field that learns vertex representations from network structure. Various NRL models have been presented, which can be broadly divided into three categories. DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], node2vec [Grover and Leskovec, 2016] and SDNE [Wang et al., 2016] tend to learn representations from local network structure. Besides, there are also some works that intend to capture the global structure and community patterns, such as GraRep [Cao et al., 2015], CNRL [Tu et al., 2016a] and MNMF [Wang et al., 2017b]. Moreover, how to incorporate heterogeneous information into NRL is also critical. TADW [Yang et al., 2015] introduces text information into NRL with matrix factorization. CANE [Tu et al., 2017] learns context-aware network representation with mutual-attention mechanism. MMDW [Tu et al., 2016b] and DDRW [Li et al., 2016] incorporate labelling information to learn discriminative network representations. Besides, SiNE [Wang et al., 2017a] learns vertex representations in signed networks, where each edge is either positive or negative. Nevertheless, such consideration of edges is over-simplified and not suitable to other types of networks.

To the best of our knowledge, less work has been done to consider the rich semantic of edges and make detailed predictions of relations on edges. It's worth noting that relation extraction has been an essential task in knowledge graphs [Mintz et al., 2009; Riedel et al., 2010; Hoffmann et al., 2011; Surdeanu et al., 2012; Lin et al., 2016], which aims to extract relational facts to enrich existing KGs. It usually performs as relation classification, as there exist various large-scale KGs such as Freebase [Bollacker et al., 2008] and DBpedia [Auer et al., 2007] , with labelled relations between entities. Nevertheless, there are usually no annotated explicit relations on edges in social networks, and it is also timeconsuming to annotate edges in large-scale networks with human efforts. To address this issue, we propose to obtain the relations from interactive text information through NLP techniques automatically.

How to model the relationships between vertices and edges is crucial for predicting the relations precisely. In word representation learning field, [Mikolov et al., 2013] found translation patterns such as "King"-"Man"="Queen"-"Woman". In knowledge graphs, [Bordes et al., 2013] interprets the relations as translating operations between head and tail entities in the representation space, i.e., "head"+"relation"="tail". Inspired by these analogies, we assume there also exists translation mechanism in social networks, and propose translationbased NRL model, TransNet.

3 Social Relation Extraction

SRE is similar to the task of relation extraction (RE) in KGs, which is an important technique that aims to extract relational facts to enrich existing KGs. Knowledge representation learning (KRL) methods such as TransE [Bordes et al., 2013], have been widely used for RE in KGs.

In this work, we present the task of Social Relation Extraction (SRE), which is designed to extract relations between social network vertices. Comparing with conventional RE in KGs, there are two obvious distinctions of SRE:

1. In KGs, relation categories are well pre-defined, and relational facts are annotated precisely with human efforts. Conversely, SRE is proposed to deal with a new scenario, in which relations between social network vertices are latent and typically hidden in their interactive text information.
2. In social networks, relations between vertices are extremely dynamic and complex, and cannot be portrayed well with a single label, because such practice cannot provide sufficient and accurate descriptions of these social relations. It is intuitive to represent the social relations by extracting key phrases from the interactive text information as a relation label set. These key phrases are flexible and capable of capturing the complex semantic information within social relations, as well as making these relations interpretable.

Formally, we define the problem of SRE as follows. Suppose there is a social network G = (V,E), where V is the set of vertices, and E ⊆ (V ×V ) are edges between vertices. Besides, the edges in E are partially labeled, denoted as EL. Without loss of generality, we define the relations between vertices as a set of labels, instead of a single label. Specifically, for each labelled edge e ∈ EL, the label set of edge e is denoted as l = {t1, t2, . . .}, where each label t ∈ l comes from a fixed label vocabulary T .

Finally, given the overall network and the labeled edges in EL, SRE aims to predict the labels over unlabeled edges in EU , where EU = E - EL represents the unlabeled edge set.

4 TransNet

In this work, we focus on the problem of incorporating rich relation information on edges into NRL.

As shown in Figure 1, TransNet consists of two critical components, i.e., translation part and edge representation construction part. In the following parts, we first give the detailed introduction of translation mechanism in TransNet. Afterwards, we introduce how to construct the edge representations. At last, we give the overall objective function of TransNet.

4.1 TranslationMechanism

Motivated by translation mechanisms in word representations [Mikolov et al., 2013] and knowledge representations [Bordes et al., 2013], we assume that the interactions between vertices in social networks can also be portrayed as translations in the representation space.

Specifically, for each edge e = (u, v) and its corresponding label set l, the representation of vertex v is expected to be close to the representation of vertex u plus the representation of edge e. As each vertex plays two roles in TransNet: head vertex and tail vertex, we introduce two vectors v and v′ for each vertex v, corresponding to its head representation and tail representation. After that, the translation mechanism among u, v and e can be formalized as

Note that, l is the edge representation obtained from l, which will be introduced in details in section 4.2.

We employ a distance function d(u + l, v′ ) to estimate the degree of (u, v, l) that matches the Eq. (1). In practice, we simply adopt L1-norm.

With the above definitions, for each (u, v, l) and its negative sample (ˆu, ˆ v, ˆl), the translation part of TransNet aims to minimize the hinge-loss as follows:

where γ > 0 is a margin hyper-parameter and (ˆu, ˆ v, ˆl) is a negative sample from the negative sampling set Ne as

In Eq. (3), the head vertex or tail vertex is randomly replaced by another disconnected vertex, and the label set is replaced by a non-overlapping label set.

The vertex representations in Eq. (2) are treated as parameters, and the edge representations are generated from the corresponding label set, which will be introduced in the following part.

4.2 Edge Representation Construction

As shown in Figure 1, we employ a deep autoencoder to construct the edge representations. The encoder part composes of several non-linear transformation layers to transform the label set into a low-dimensional representation space. Moreover, the reconstruction process of the decoder part makes the representation preserve all the label information. In the following sections, we introduce how to realize it in detail.

Input Mapping: We first map the label set to an input vector of autoencoder. Specifically, for a label set l = {t1, t2, . . .} of edge e, we obtain a binary vector s = {si}|T | i=1 , where si = 1 if ti ∈ l, and si = 0 otherwise.

Non-linear Transformation: Taking the obtained binary vector s as input, the encoder and decoder parts of the autoencoder consist of several non-linear transformation layers

Here, K represents the number of layers and f denotes the activation function. h(i) , W(1) and b(i) represent the hidden vector, transformation matrix and bias vector in the i-th layer respectively. Specifically, we employ tanh activation function to get the edge representation l = h(K/2) as the vertex representations are real-valued, and sigmoid activation function to get the reconstructed output ˆs as the input vector s is binary.

Reconstruction Loss: Autoencoder aims to minimize the distance between inputs and the reconstructed outputs. The reconstruction loss is shown as:

Here, we also adopt L1-norm to measure the reconstruction distance, the same as in Eq. (2).

However, due to the sparsity of the input vector, the number of zero elements in s is much larger than that of non-zero elements. That means the autoencoder will tend to reconstruct the zero elements rather than non-zero ones, which is incompatible with our purpose. Therefore, we set different weights to different elements, and re-defined the loss function in Eq. (5) as follows:

where x is a weight vector and ⊙ means the Hadamard product. For x = {xi}|T| i=1 , xi = 1 when si = 0 and xi = β > 1 otherwise.

With the utilization of deep autoencoder, the edge representation not only remains the critical information of corresponding labels, but also has the ability of predicting the relation (labels) between two vertices.

4.3 Overall Architecture

To preserve the translation mechanism among vertex and edge representations, as well as the reconstruction ability of edge representations, we combine the objectives in Eqs. (2) and (6), and propose a unified NRL model TransNet. For each (u, v, l) and its negative sample (ˆu, ˆ v, ˆl), TransNet jointly optimizes the objective as follows:

Here, we introduce two hyper-parameters α and η to balance the weights of different parts. Besides, Lreg is an L2-norm regularizer to prevent overfitting, which is defined as

In order to prevent overfitting, we also employ dropout [Srivastava et al., 2014] to generate the edge representations. At last, we adopt Adam algorithm [Kingma and Ba, 2015] to minimize the objective in Eq. (7).

4.4 Prediction

With the learnt vertex representations and the edge autoencoder, TransNet is capable of predicting the labels on the edges in EU .

To be specific, given an unlabeled edge (u, v) ∈ EU, TransNet assumes that the representations of u and v conform to the Eq. (1) with the potential edge representation. Thus, we can get the approximate edge representation through l = v′ - u. Naturally, we decode the edge representation l with the decoder part in Eq. (4) to obtain the predicted label vector ˆs. A larger weight ˆsi indicates ti is more possible in l.

5 Experiments

In order to investigate the effectiveness of TransNet on modeling relations between vertices, we compare the performance of our model to several baseline methods on social relation extraction (SRE) with three automatically constructed social network datasets.

5.1 Datasets

ArnetMiner 1 [Tang et al., 2008] is an online academic website that provides search and mining services for researcher social networks. It releases a large-scale co-author network 2 , which consists of 1, 712, 433 authors, 2, 092, 356 papers and 4, 258, 615 collaboration relations.

In this network, authors collaborate with different people on different topics, and the co-authored papers can reflect the detailed relations between them. Therefore, we construct the co-authored network with labeled edges in the following steps. Firstly, we collect all the research interest phrases from the author profiles and build the label vocabulary with these phrases. These phrases are mainly crawled from the authors' personal home pages and annotated by themselves. Hence, these phrases are rather credible, which is also confirmed by our manual check. Secondly, for each co-author relationship, we filter out the in-vocabulary labels in the abstracts of coauthored papers and regard them as the ground truth labels of this edge. Note that, as the edges in co-author networks are undirected, we replace each edge with two directed edges with opposite directions.

1 https://cn.aminer.org/

2 https://cn.aminer.org/aminernetwork

Specifically, to better investigate the characteristics of different models, we construct three datasets with different scales, denoted as Arnet-S(small), Arnet-M(medium) and Arnet-L(large). The details are shown in Table 1.

5.2 Baselines

We employ the following NRL models as baselines:

DeepWalk [Perozzi et al., 2014] performs random walks over networks to generate random walk sequences. With these sequences, it employs Skip-Gram [Mikolov et al., 2013], an efficient word representation model, to learn vertex representations.

LINE [Tang et al., 2015] defines the first-order and second-order proximities of networks and optimizes the joint and conditional probabilities of edges in large-scale networks.

node2vec [Grover and Leskovec, 2016] extends DeepWalk with a biased random walk strategy. It can explore the neighborhood architecture more efficiently.

For these NRL models, we treat SRE as a multi-label classification task. Therefore, we concatenate the head and tail vertex representations to form the feature vector and adopt one-vs-rest logistic regression implemented by [Pedregosa et al., 2011] to train a multi-label classifier.

Besides, we also compare our model with the typical knowledge embedding model, TransE [Bordes et al., 2013]. For each training instance (u, v, l), where l = {t1, t2, . . .}, it is intuitive to obtain several triples, i.e., (u, v, ti) for each ti ∈ l, which can be directly utilized to train TransE model. We adopt the similarity based predicting method as introduced in [Bordes et al., 2013].

5.3 EvaluationMetrics and Parameter Settings

For a fair comparison, we evaluate the performance for each triple (u, v, ti) as in TransE, where ti ∈ l. Besides, we also employ hits@k and MeanRank [Bordes et al., 2013] as evaluation metrics. Here, MeanRank is the mean of predicted ranks of all annotated labels, while hits@k means the proportion of correct labels ranked in the top k. Note that, the above metrics will under-estimate the models that rank other correct labels in the same label set high. Hence, we can filter out these labels before ranking. We denote the primal evaluation setting as "Raw" and the latter one as "Filtered".

We set the representation dimension to 100 for all models. In TransNet, we set the regularizer weight η to 0.001, the learning rate to 0.001 and the margin γ to 1. Besides, we employ a 2-layer autoencoder for all datasets and select bestperformed hyper-parameters α and β on validation sets.

5.4 Results and Analysis

Table 2, Table 3 and Table 4 show the SRE evaluation results with different evaluation metrics on different datasets. In these tables, the left four metrics are raw results, and the right are filtered ones. From these tables, we have the following observations:

(1) Our proposed TransNet achieves consistent and significant improvements than all the baselines on all different datasets. More specifically, TransNet outperforms the best baseline, i.e., TransE, by around 10% to 20% absolutely. It demonstrates the effectiveness and robustness of TransNet on modeling and predicting relations between vertices.

(2) All NRL models perform poorly on SRE task under various situations, due to the neglect of rich semantic information over edges when learning vertex representations. On the contrary, both TransE and TransNet incorporate this information into the learned representations, thus achieve promising results on SRE. It indicates the importance of considering the detailed edge information, as well as the rationality of translation mechanism on modeling relations between vertices.

(3) Comparing with TransNet, TransE also performs poorly as it can only consider a single label on an edge each time, which turns the representation of labels on the same edge to be identical. Such practice may accord with the scenario in KG, where only 18% entity pairs possess multiple relation labels, according to our statistics on FB15k [Bordes et al., 2013]. Conversely, the percentages of multi-label edges on SRE datasets are larger (42%, 64% and 62% on ArnetS, Arnet-M, and Arnet-L respectively). Therefore, TransNet models all the labels over an edge simultaneously and can handle these issues well according to the results.

(4) TransNet has stable performance under different scales of networks. Moreover, when the number of labels turns larger, the performance of TransNet only has a small drop (from 90% to 80% on filtered hits@10), while NRL models and TransNet decrease more than 20%. This indicates the flexibility and stability of TransNet.

5.5 Comparison on Labels

To investigate the strengths of TransNet on modeling relations between vertices, we compare TransNet with TransE under high-frequency labels and low-frequency ones. In Table 5, we show the filtered hits@k and MeanRank results on Arnet-S over top-5 labels and bottom-5 labels respectively.

From this table, we find that TransE performs much better on high-frequency labels than low-frequency labels since there is a liberal quantity of training instances for highfrequency labels. Compared with TransE, TransNet has stable and worthy performance on both types of labels. The reason is that TransNet employs an autoencoder to construct edge representations, which can take the correlations between labels into consideration. These correlations can provide additional information for low-frequency labels, which will benefit the modeling and predicting of them.

5.6 Parameter Sensitivity

There are two crucial hyper-parameters in TransNet, i.e., α and β. We investigate the parameter sensitivities on Arnet-S.

For β, it balances the weight of non-zero elements in autoencoder. We determine the value of β according to the reconstruction performance when we initialize the auto-encoder using Eq. (6). In the left part of Figure 2, we show the raw hits@1 trends on validation set under different values of β. From this figure, we find that the reconstruction performance becomes stable after several iterations. More specifically, when β is too small (e.g., 5), the autoencoder will tend to reconstruct zero element rather than non-zero ones, which will lead to the poor reconstruction performance.

The hyperparameter α controls the weight of auto-encoder loss comparing with the translation loss. When the optimal β is determined, we show the raw hits@10 results in the right part of Figure 2 when α takes values under different orders of magnitude. From this figure, we observe that the performance of TransNet rises rapidly at the beginning, and then becomes stable. When α varies broadly, all the implements of TransNet can exceed TransE within 20 iterations and achieves stable performance at last. Therefore, TransNet can be easily implemented and well trained in practice due to its insensitivity of hyper-parameters.

5.7 Case Study

To demonstrate the effectiveness of TransNet, we provide a case in the test set of Arnet-S. The selected researcher is "A. Swami", and the recommended labels for its co-authors are shown in Table 6. In this table, labels in bold are correct ones. We observe that, both TransE and TransNet can recommend reasonable labels to different neighbors, which can reflect their distinct co-author topics. However, for a specific neighbor, TransE only recommends similar labels due to its similarity-based recommendation method. Conversely, TransNet can recommend discriminative labels with the usage of decoder.

6 Conclusion

In this paper, we formalize the problem of social relation extraction (SRE) in social networks, which aims to extract detailed relations between vertices and can be used to evaluate the ability of NRL models on relation modeling. Moreover, we propose a novel translation-based NRL model, TransNet, to model interactions between vertices with translation mechanism. Experimental results on SRE show that TransNet can successfully integrate the rich semantic information preserved on edges into vertex representations and achieves significant improvements comparing with all baseline methods.

In future, we will explore the following directions:

1. The effectiveness of TransNet has been verified on extracting explicit relations in homogeneous networks. In future, we want to explore how to model the relations between various types of vertices in heterogeneous networks.
2. In SRE, the co-occurring vertex pairs and labels on edges can be regarded as a hyperedge in hypergraphs, where each edge contains three or more various vertices. Thus, we will explore network representation learning in hypergraphs, and the learned representations of vertices and labels are expected to benefit the SRE task.

Acknowledgements

This work is supported by the Major Project of the National Social Science Foundation of China (No.13&ZD190), the National Natural Science Foundation of China (NSFC No. 61572273, 61532010), and Tsinghua University Initiative Scientific Research Program (20151080406).