Tag2Gauss: Learning Tag Representations via Gaussian Distribution in Tagged Networks

1 Introduction

Tagged networks, namely networks including not only relationships between nodes but also the subordinate relationship between nodes and tags, are ubiquitous. Keywordbased tags (referred to as tags) are used to represent additional attributes of nodes in addition to what is explicitly stated in their contents. Taking YouTube as an example, a million-video sample shows that 6 tags are applied to each video on average, the majority of which do not exist in the title [Geisler and Burns, 2007; Aggarwal, 2011; Huang et al., 2010; Godin et al., 2013].

∗This work was supported by the National Natural Science Foundation of China (Grant No. 61876006 and No. 61572041).

†These authors contributed equally to the work.

‡Corresponding Author

In addition to mere literal meanings expressed in the words of tags, tags also convey more complex semantics illustrated in the way they interact with tagged nodes, thereby providing nodes with information highly useful to users. Consequently, tags can be used for different tasks, such as information retrieval, item recommendation, and event analysis [Chang, 2010; Tsur and Rappoport, 2012].

However, it is challenging to learn satisfactory tag representations.

• Traditional representation methods generally fail when it comes to representing tags. On one hand, naive one-hot representations of tags ignore the semantic relationships between tags. On the other hand, representing tags with mere word embedding focus more on the literal meaning of keyword-based tags, which ignores their interaction with tagged nodes and is not suitable for tag representation. In addition, conventional representation learning models, which map objects to vectors also fail to generate satisfactory representations, since, a single point in the vector space is unable to represent complex relationships between tags, such as inclusion, entailment and hierarchy. Consequently, more flexible representation methods should be involved.
• Bidirectional interactions between nodes and tags should be modeled, which are generally not dealt within existing research works. For example, in Bilibili, the tag "MAD" is similar to the tag "ANIMATION" according to tagged videos, however it is difficult to find the correlation in general literal corpus. More extremely, some tags with mosaic keywords cannot convey any useful literal information. As discussed above, the meanings tags express are largely defined by the nodes adhered with them, and vise versa. However, explicit similarity measures, such as links between tag pairs, are not available in tagged networks, which underscores the need for us to design models capturing complex interactions between nodes and tags.

To cope with these problems, we study the tag embedding problem in node-tag hybrid networks derived from a tagged network (see Figure 1) and propose our model, named Tag2Gauss, which deals with the challenges correspondingly. On one hand, since tags represent node communities with intricate overlapping relationships, we propose that distributions, namely a region associated with different intensity, would be more appropriate in modeling tags containing nodes with scattering positions in vector space. On the other hand, considering the bidirectional interactions between nodes and tags, we propose a tag representation learning model mapping tags to distributions consisting of two embedding tasks, namely tag-view embedding and node-view embedding. Specifically, in tag-view embedding module, tags are represented as Gaussian distributions. To capture similarity between tags, a walking strategy, named Hybrid Walker, is proposed based on the node-tag hybrid network, followed by a max-margin ranking objective to optimize tag representations. In node-view embedding, we present a generative model for node representations inspired by the Gaussian Mixture Model. In this way, tag distributions are directly used for node embedding generation, enabling the joint learning of tag representations and node representations in the multi-task learning framework we propose.

To summarize, we make the following contributions:

• We represent tags as Gaussian distributions, which is able to characterize the complex semantic relationships between tags, such as inclusion, entailment and hierarchy.
• We design a multi-task learning framework, Tag2Gauss, involving both tag representation learning and node representation learning that can be optimized jointly.
• We conduct extensive experiments on three real-world tagged networks, and the results demonstrate that our model can capture the rich information carried in both nodes and tags and achieve superior performance from its counterparts.

2 RelatedWork

Network Embedding. Network embedding aims to map the vertices or edges of a network into low-dimensional vector space for the sake of better performance of learning tasks such as node classification and link prediction [Goyal and Ferrara, 2018]. Some methods proposed are based on context of the vertex to preserve its structural properties [Perozzi et al., 2014; Tang et al., 2015; Du et al., 2018a; Du et al., 2018b], others are based on graph factorization or deep learning [Goyal and Ferrara, 2018; Wang et al., 2016]. Embedding of attributed network whose nodes are each associated with their rich features [Huang et al., 2017], has received attention in recent years. TADW leverages rich text features in graph factorization [Yang et al., 2015], while GCN and GraphSAGE turn to scalable deep learning architecture with neighborhood aggregation [Kipf and Welling, 2017; Hamilton et al., 2017]. However, stable discrete node features as tags are often treated as one-hot vector in those works and interactions between them are overlooked.

Variational Representation with Gaussian Distribution.

Gaussian distribution is used to describe the variation bound for posterior probabilities in Variational Autoencoders (VAE) [Kingma and Welling, 2014]. Uncertainty of Gaussian distribution has also been utilized in word embedding models to make the parameters more expressive both in prior [Vilnis and McCallum, 2015] and posterior [Brazinskas et al., 2017] ways. When it comes to network/graph, KG2E train Gaussian embeddings for entities and relations in knowledge graph [He et al., 2015]; VGAE, based on VAE, embeds the network with Gaussian using GCN encoder and inner dot decoder [Kipf and Welling, 2016]. However, to the best of our knowledge, expressive Gaussian methods has not been generalized to tagged networks yet.

3 ProblemDefinition

Definition 1 (Tagged Network). A tagged network is defined as G = <V, E, T>, where V = {vi}, i = 1, 2, . . . , n represents the set of nodes, E = {eij}, i, j = 1, 2, . . . , n, i ̸= j represents the set of edges, and T = {tk}, k = 1, 2, . . . , |T | represents the set of tags that each node belongs to. Each node vi has k tags, i.e., Tvi ={ti1 , ti2 , . . . , tik }, tij ∈ T. If node vi is marked with tag t, node vi has a tag t, or tag t belongs to node vi.

Tags are literal symbols to label characteristics of a node. The semantics of tag is essentially determined by the characteristics of the set of nodes marked with it. In order to explore the tag representation based on the interaction of nodes, we introduce the definition of node-tag hybrid network as shown in Figure 1 as follows:

Definition 2 (Node-Tag Hybrid Network). A node-tag hybrid network H=<VH, EH> is derived from a tagged network G=<V, E, T>, where VH = V ∪ T , EH = E ∪ ET . For vH ∈ VH, vH is a plain node if vH ∈ V . Otherwise, it is a tag node if vH ∈ T. For eH ∈ EH, eH is an interaction edge if eH = <v1, v2> ∈ E. Otherwise, it is an affiliation edge eH = <v, t> and node v is marked with tag t.

Due to the bidirectional interactions between nodes and tags, tag representation learning task and node representation learning task can reinforce each other and be jointly optimized. Next, we introduce the definition of node-view embedding for node representation and tag-view embedding for tag representation, respectively.

Definition 3 (Node-view Embedding). Given a tagged network G = <V,E, T>, the problem of node-view embedding aims to represent each node v ∈ V attached with multiple tags Tv into a low-dimensional Euclidean space conditional on tags adhered with it, i.e., learning a mapping function Φ(V |T ) : V → Rd , where d ≪ |V |.

According to the above analysis, a single point in the vector space is unable to represent complex relationships between tags. Inspired by the Word2Gauss [Vilnis and McCallum, 2015], we represent each tag as a Gaussian distribution. Next, we introduce the definition of tag-view embedding for tag representation learning.

Definition 4 (Tag-view Embedding). Given a tagged network G = <V, E, T>, the problem of tag-view embedding aims to represent each tag t ∈ T and preserve tag proximity into a low-dimensional Euclidean space based on the interaction of nodes V . The tag tk ∈ T is mapped to a Gaussian distribution N(µk,Σk) in a d-dimensional space, where µk ∈ Rd is a mean vector and Σk ∈ Rd×d is a covariance matrix.

4 Tag2Gauss

In this section, we introduce the overview of our model Tag2Gauss and more specifically introduce two main modules, i.e., tag-view embedding module and node-view embedding module. Finally, we propose a multi-task learning framework to jointly learn tag representations as well as node representations.

4.1 Framework Overview

In the framework of Tag2Gauss (see Figure 2), the parameters set {N(µk,Σk))}, where k = 1, 2, . . . , |T| are the tag representations to be learned, and N(µk,Σk) is the tag tk corresponding Gaussian distribution. In tag-view embedding module, we design a hybrid walker to generate tag pair corpus and train them with the max-margin ranking objective. In node-view embedding module, we present a generative model based on Gaussian Mixture Model for the node representation generation [Rasmussen, 2000]. During the joint learning process, tag representation can be directly used to generate the node embedding. Meanwhile, the optimization process of the node embedding can also tune the tag representation by the back-propagation.

4.2 Tag-view Embedding

In this section, we design the tag-view embedding module to map each tag to a Gaussian distribution based on the interaction of nodes. Because there is no explicit link between tag pairs in the tagged network, we design a walking strategy based on the node-tag hybrid network, namely hybrid walker, to capture the tag proximity which is preserved by optimizing the max-margin ranking objective.

Hybrid Walker

We first define "tag relation sequence" as such a walking sequence which starts and ends with tag nodes, and the rest are plain nodes (see Figure 3).

The hybrid walker strategy is as follows: v refers to the current position, Γ is the type mapping function,

According to the definition of "tag relation sequence", Γ(v0 ) = 0, and the walking process ends up with vL, where Γ(vL) = 0. The transition probability p(vi+1 |vi ) at step i is defined as follows:

where,

where, wi,i+1 refers to the edge weight of plain nodes, ˆwi,i+1 refers to the edge weight between plain nodes and tag nodes, and c is a damping factor, which punishes the length of the walking sequence, such as c = 2. p(vi+1 |vi , t = 0) is the transition probability from a node vi to a tag node vi+1 . p(vi+1 |vi , t = 1) is the transition probability from a node vi to another plain node vi+1 . Such a walk strategy essentially learns the number of different-order co-neighbors of tags corresponding node groups. Therefore, the closer the semantic distance between the node groups, the higher the probability of the corresponding tags appearing in the same "tag relation sequence".

Max-margin Ranking Objective

From each tag relation sequence, we can get the tag and its context. Considering mapping tags to Gaussian distributions, we train them with max-margin ranking objective Otag view, which pushes scores of positive pairs above negatives by a margin [Vilnis and McCallum, 2015]:

where utag is drawn from some distribution Z, vtag is drawn from the similarity distribution of PsimG (utag, ·) in network G. In our model, PsimG (utag, ·) is determined by the frequency of tag occurrence in tag pair corpus from the hybrid walker. ˜ vtag is drawn from noise distribution Q. KL divergence is used to measure the similarity S(tagi, tagj) to help learn the complex semantic relationship between tags, such as inclusion, entailment and hierarchy.

4.3 Node-view Embedding

In this section, we design the node-view embedding module to generate node embeddings with the distribution of tags. This feedback from the node embeddings tunes the tag representations during training. When it comes to the node embedding, compared with neighbor-aware proximity ( e.g. firstorder and second-order proximity in [Tang et al., 2015]), tagaware proximity does not require two nodes to be directly linked or share many "contexts" for being close, even with high order. Therefore, not only neighbor-aware proximity,

Algorithm 1 Node Embedding Generation Algorithm

Input: Tagged Network G = <V,E, T>; input features {xv}; tag sets {Ti}; neighborhood function N : v → 2V

Output: Node representations U for all v ∈ V ; Tag representations Utag for all t ∈ T

• 1: Initialize the set of parametersN(µk,Σk) for all tag tk ∈ T
• 2: Initialize weight matrixW
• 3: for vi in V do
• 4: ⃗ni = GCN(vi)
• 5: α = softmax(W · ⃗ni)
• 6: sample ⃗ti from ∑tk∈|Ti| αkN(µk,Σk)
• 7: Φ(vi) =MLP([⃗ni,⃗ti])

tag-aware proximity is taken into consideration in the node embedding.

Because tags are represented as distributions, we elaborate a generative node embedding model, where the node representation Φ(vi) is drawn from Pr(vi|Nvi , Tvi ) which is the conditional distribution given the neighbor structure Nvi and the tag set Tvi of the node, i.e.,

where Tvi is the tag set of vi, and Nvi is the neighbor information of vi. Gaussian distribution N(µk,Σk), where k = 1, 2, . . . , |T| is the representation of k-th tag in Tvi . In order to model the node representation distribution Pr with the neighbor information, we design the α as the function of Nvi , i.e., αk(Nvi ).

Node Embedding Generation

According to Equation 10, we describe the node embedding generation (Algorithm 1). To capture the neighbor-aware proximity, Graph Convolutional Networks [Kipf and Welling, 2017] are introduced to aggregate information. The parameters to be tuned in the training process are the Gaussian distribution N(µk, Σk) for any tag tk ∈ T , and the weight matrix W for modelling mixing coefficients α. The tag-aware information ⃗ti is drawn from the mixture distribution and next bonded with the neighbor-aware information ⃗ni to generate the final node representation Φ(v).

NCE Objective Function

In order to learn useful and predictive representations in a fully unsupervised setting, we apply the following NCE loss function to distinguish between node samples u and v from the empirical similarity distribution PsimG and those negative samples {˜ v} generated by a noise distribution Q over the nodes, which encourages nearby nodes to have similar representations:

where σ(·) = 1/(1 + exp(-x)) is the sigmoid function, u is drawn from some distribution Z, v is drawn from the similarity distribution PsimG (u, ·) which is determined by the plain edge weights linked from u. ˜ v is drawn from noise distribution Q. EPr(Φ(u)) is the expectation of Φ(u), which can be calculated by drawing multiple times from the distribution Pr defined in Equation 10.

4.4 Multi-task Learning

Based on previous analysis, Otag view and Onode view can be jointly optimized for better learning tag representations, as well as node representations. In the multi-task learning framework, the whole objective is designed as follows:

Obviously, we can optimize Otag view with Stochastic Gradient Descendent (SGD). However, generating EPr(Φ(u)) with multiple times sampling is a non-continuous operation and has no gradient, which can not be back-propagated the error with SGD. Next, we introduce the solution for this problem, called "reparameterization trick" which extends from [Kingma and Welling, 2014]

Reparameterization Trick

For any Gaussian Mixture Model P(x), i.e.,

we can get the expectation EP(x) by first sampling from each Gaussian distribution Ni(x) to get the expectation ENi(x), then mixing these expectations with α to get EP(x), which is proved as follows:

Also, given µ and Σ of a Gaussian distribution, we can sample x from N(µ, Σ) by first sampling ε ∼ N(0, I), then computing x = µ+Σ 12 ∗ ε, i.e.,

Therefore, the sampling operation in our model can be moved to an input layer. With the help of reparameterization trick, none of the expectations are related to distributions that depend on our model parameters. Therefore we can optimize Onode view with SGD.

5 Experiments

5.1 Experiment Setup

Data Sets

Leetcode 1 is an online programming website. Nodes stand for open problems, edges mean direct hyperlink between problems, and tags are certain categories associated with the problem; we treat difficulty as the label (562 nodes, 1095 edges, 34 tags, 3 classes).

Bilibili 2 is a start-up Chinese video website. Nodes resemble videos, edges are the links of "related video", and tags are certain short words added by uploaders. We collect a sample of videos and their links using BFS and regard the genre (namely type name) of each video as the label (11727 nodes, 187149 edges, 151 tags, 10 classes).

1 https://leetcode.com/

2 https://www.bilibili.com/

Cora. We also convert the open data set Cora [Sen et al., 2008] to the tagged network where each of the 1433 words resembles a tag (2707 nodes, 5429 edges, 1433 tags, 7 classes).

Baselines

We choose the following methods as baselines for classification: DeepWalk [Perozzi et al., 2014], Node2Vec [Grover and Leskovec, 2016], LINE [Tang et al., 2015], and GraphSAGE [Hamilton et al., 2017].

Parameters Settings

In Tag2Gauss, diagonal covariance is set as the covariance of Gaussian distribution and λ in Equation 12 is selected according to the grid search. The learning rate is 0.001. The experimental results are reported in our experiment with the 10-fold cross-validation.

5.2 Node Classification

For classification, the embedding dimension across different models is 64. We classify the pre-trained embeddings using Logistic Regression over different training size. We take the mean Macro-F1 as the result. Table 1 shows the Macro-F1 on node classification. As Tag2Gauss takes the polysemy and complex semantic relations of tags, it outperforms all other methods. Especially, the necessity of discriminating the tag from node feature can be verified from the outperformance of Tag2Gauss to GraphSage.

5.3 Tag Representation Capacity

We prove it is more advantageous for network mining tasks when tags are mapped to distribution through node classification experiment. A more detailed analysis is as follows. Figure 5 shows the node classification accuracy on data set Leetcode on different models, i.e., DeepWalk, Hybrid DeepWalk, and Tag2Gauss. As a typical algorithm that preserves the structure, DeepWalk is introduced into our experiments to verify the validity of regarding tags as auxiliary information. Especially, Hybrid DeepWalk, applies DeepWalk algorithm to node-tag hybrid network and learn the representations of nodes and tags simultaneously and finally joint node embedding with corresponding tag embedding. Tag2Gauss takes the representations of nodes from node-view embedding module.

The figure shows that tags do play a role in network representation learning as DeepWalk is worse than Hybrid DeepWalk and Tag2Gauss; however, Hybrid DeepWalk is inadvisable as it is not significantly improved and lacks robustness. This naive method cannot exploit the implicit information between tags and nodes well. In such situations, Tag2Gauss shows its incomparable advantages on account of exploiting the implicit information of tags and keeping robust by mapping tags to distributions.

5.4 Tag Representation Visualization

In this section, we verify the advantages of mapping tags to Gaussian distributions. Different from a single point, the representation of each tag can learn the semantics and polysemy with the help of the mean vector and variance matrix in Gaussian distribution. We train 2-dimension embeddings with diagonal covariance to visualize the tags in a plane. Figure 4 depicts the visualization of a subset of tag representations in Leetcode. In Figure 4(a), we draw every tag representation as an ellipse with a mean vector and three times of standard derivation. For comparison, Figure 4(b) shows the tags drawn with the mean vector.

(b) Shown as scatters

Figure 4: A subset of tags visualization in Leetcode dataset.

Compared with point representations, ellipses are of great benefit because the overlaps illustrate the inclusion, entailment and hierarchy of tags, hence they reveal the correlation between tags more precisely. The ellipse region of tags in Leetcode shows the applicability of related algorithm among these programming problems, and the intersection of ellipses means that the corresponding tag has the same set of solvable problems. For example, tag DP has a larger set of solvable problems than tag DFS. As for the complicated interaction among tags, point representation can only show the relationship as distance, thus limited in the expression ability. For example, figure 4(b) shows that Heap is close to Queue, but Heap actually contains Queue which can be seen in figure 4(a).

5.5 Cold Start

In cold start, a model generates embedding for new nodes unseen during training. For Tag2Gauss, tag representations provide the auxiliary information for new nodes representing. To validate the effectiveness of Tag2Gauss in cold start, we divide the network into two parts, i.e., the initial network Ginit and the new node set Gnew. Ginit is used to train the embedding model, and then the learned node embedding is used to learn a logistic regression classifier(same as above). In the testing process, embedding of nodes in Gnew are inferred with the trained embedding model and classifier. Figure 6 shows the node classification accuracy on Gnew with 10-fold cross-validation. It can be seen from Figure 6 that Tag2Gauss prevail over GraphSage on Leetcode and Cora.

6 Conclusion

In this paper, we propose Tag2Gauss to learn tag representation via Gaussian distribution in the tagged network. Specifically, we represent the tag as a Gaussian distribution to characterize the complex semantic relationships between tags, such as inclusion, entailment and hierarchy. Moreover, we propose a tag representation learning model mapping tags to distributions consisting of two embedding tasks, namely tagview embedding and node-view embedding. Empirically, the extensive experimental results on node classification and network visualization, as well as cold start of new nodes, demonstrate the advantages of Tag2Gauss.