Detecting User Community in Sparse Domain via Cross-Graph Pairwise Learning

As aforementioned, conventional methods suffer from graph sparseness problem. In this study, we propose a Pairwise Cross-graph Community Detection (PCCD) model that particularly aims at detecting user pairwise community closeness in sparse graphs by involving cross-graph techniques.

Particularly, a well connected graph is called ”main graph” in this paper, corresponding to the targeted sparse graph. In general, as users may visit multiple cyber domains within a short time period, these mutual users co-occurred in both the main and sparse graph are taken as the bridge to connect the two graphs. Therefore, the relevant information from the main graph can be propagated to the sparse graph to support its user community detection.

Specifically, our proposed model (showed in Figure 2) is trained on mutual user triplets to learn three types of pairwise community relationship including “similar”, “closer” and “farther”. The goal of this study can be reformulated as the following pairwise learning task: Given a sparse graph $S$ and a main graph $M$ where $N^{C}$ denotes their mutual user collection, for a mutual user triplet $\langle u_{i},u_{j},u_{k}\rangle\in N^{C}$ (Model Input), we aim to predict the relationship of its pairwise community closeness in graph $S$ (Model Output). In this paper, “similar” relationship means that $u_{j}$ and $u_{k}$ are either in the same community or different communities with $u_{i}$. “closer” relationship means that $u_{j}$ and $u_{i}$ are in the same community, while $u_{k}$ and $u_{i}$ are in different communities. “farther” relationship means that $u_{j}$ and $u_{i}$ are in different communities, while $u_{k}$ and $u_{i}$ are in the same community.

For a mutual user triplet, our proposed model detects communities firstly on separate graphs to obtain all user raw community representations (Section 2.2). Their propagative representations are learned through a community-level and a node-level filter (Section 2.3). Both representations are jointly utilized for predicting user community affiliation in each graph via a Community Recurrent Unit (Section 2.4). In the end, we integrate the community affiliation distributions to identify the pairwise community relationship of the triplet (Section 2.5). Particular training strategies are introduced in the end (Section 2.6).

Note that even though our model is only trained on mutual users, it is still functional to detect pairwise community closeness on those users solely appeared in either the main or sparse graph. Further experiments in Section 3.5 will verify its effectiveness on different types of users.

As the user behavior is enriched in the main graph $M$, detecting user communities in it would offer auxiliary community features to potentially enhance our model performance. Therefore, we decide to involve user communities in the main graph as a part of model input. The same information from the sparse graph is intentionally omitted because its sparse graph structure is not able to offer reliable community partition results.

Considering all possible community detection methods listed in Section 3.2, Infomap (Kheirkhahzadeh et al., 2016) is empirically selected to detect user communities in the main graph $M$. Infomap method simulates a random walker wandering on the graph for $m$ steps and indexes his random walk path via a two-level codebook. Its final goal aims to generate a community partition with the minimum random walk description length, which is calculated as follows:

where $L(\pi)$ is the description length for a random walker under current community partition $\pi$. $q_{\curvearrowright}^{i}$ and $p_{\circlearrowright}^{i}$ are the jumping rates between and within the $i_{th}$ community in each step. $H(\mathcal{Q})$ is the frequency-weighted average length of codewords in the global index codebook and $H(\mathcal{P}^{i})$ is frequency-weighted average length of codewords in the $i_{th}$ community codebook.

In the end, given a user $u_{i}$, we obtain its one-hot community representation $v_{c,i}^{M}$ in the main graph $M$, which is regarded as part of user representations for the model input.

To better convey the mutual user insights in both main and sparse graph, their representations are learned from both direct transformation and weighted information propagation. The optimization processes are similar in the main and sparse graph. In the beginning, a user $u_{i}$ can be represented as a multi-hot embedding $p_{i}^{M}$ in the main graph $M$ (left part in Figure 3) and $p_{i}^{S}$ in the sparse graph $S$. Each dimension in the embedding refers to a unique object with which the user connects in the related graph.

The direct transformation from user multi-hot embedding learns a dense vector via one hidden layer so as to retrieve the compressed information from user connected objects directly, which is calculated as follows:

where $G\in\{M,S\}$ denotes either the main or the sparse graph. $W_{e}^{G}$ and $b_{e}^{G}$ denote the weight matrix and bias respectively. $v_{e,i}^{G}$ is the learned direct transformation representation for user $u_{i}$.

On the other hand, from information propagation perspective, each object carries information, which can be propagated to its connected users as a type of representation. However, as such information are noisy, not all of them are equally important to users. Therefore, a filtering module is proposed to automatically select appropriate information to propagate from both community level and node level. The overall flow of the filtering module is illustrated in Figure 3.

Community-Level Filter: As the raw detected communities in the sparse graph is not reliable because of graph sparseness, we only apply the community-level filter in the main graph $M$. According to the raw community partition $\pi$ calculated in Section 2.2, each object node $n_{i}$ is assigned to a community $\pi(n_{i})$. The community-level filter propagate object information in a coarser manner by considering its community importance weight $w_{\pi(n_{i})}$. Throughout this filter, we aim to learn a weight vector $w$ where each dimension of $w$ denotes the importance score of a related community.

Node-Level Filter: Node-level filter assesses the propagated information with a fine resolution. In the main graph $M$ ( a user-object bipartite graph), we aim to learn object representations $H^{M}=\{h_{1}^{M},...,h_{n}^{M}\}$ where $h_{n}^{M}$ denotes the $n_{th}$ object representation. Similarly, $H^{S}$ denotes the object representations in the sparse graph $S$. The weight of the $j_{th}$ object node decides the amount of its information propagating to its connected user nodes, which is calculated in an attentive means:

where $G\in\{M,S\}$ denotes either the main or the sparse graph. $u^{G}_{p}$ denotes the project vector in the related graph to calculate object attentive weights. $W_{p}^{G}$ and $b_{p}^{G}$ denote the corresponding weights and bias, respectively.

We combine the community-level and node-level weights together to quantify the information propagation in the main graph $M$. While only the node-level weights is considered in the sparse graph $S$. Normalized by the ${\rm softmax}(\cdot)$ function, the related representation of user $u_{i}$ in both graphs are calculated as follows:

Both $v_{p,i}^{M}$ and $v_{p,i}^{S}$ are the weighted sum of the neighbour object representations. $\mathcal{N}^{S}(n_{i})$ and $\mathcal{N}^{M}(n_{i})$ denote user connected objects in both graphs.

Finally, given a user $u_{i}$, its raw community representation, direct transformation representation and two-level filtered representation construct its propagative representation in the main graph $M$. While its direct transformation representation and node-level filtered representation construct its propagative representation in the sparse graph $S$. To avoid gradient vanishing, a ${\rm batch\_norm(\cdot)}$ function is applied on top of the concatenated representations in both graph:

After previous steps, each user of the mutual user triplet $\langle u_{i},u_{j},u_{k}\rangle$ is associated with a propagative representation. In this section, its corresponding community affiliation scores $c_{i}^{G}$ are further calculated in related graphs $G\in\{M,S\}$ through a designed Community Recurrent Unit (CRU), which is showed in Figure 4. The CRU contains an affiliation gate to calculate the user affiliation score for each community and an update gate to update community self representations. Within this unit, a community memory $D^{G}=\{d_{1}^{G},...,d_{K}^{G}\}$ is designated to store $K$ community representations. Particularly, community representation is required to be with the same dimension as user propagative representation in both graphs.

Community Affiliation Gate: The affiliation gate helps to generate the affiliation score of a user $u_{i}$ towards each community in both graphs, which forms a $K$-dimensional vector $c_{i}^{G}=\{c_{i,1}^{G},...,c_{i,K}^{G}\}$ where $G\in\{M,S\}$ . The user $u_{i}$’s affiliation score $c_{i,j}^{G}$ towards the $j_{th}$ community in the graph $G$ is calculated as follows:

The dot product between transformed user propagative representation ${\rm tanh}(v_{i}^{G})$ and the $j_{th}$ community representation $d_{j}^{G}$ indicates their potential correlation, which further turns to a scalar affiliation score $c_{i,j}^{G}$ between 0 to 1 with the help of a projection vector $u_{c}^{G}$ and normalization function $\sigma(\cdot)$.

Community Update Gate: When calculating $u_{i}$’s community affiliation, its information can help to update community representations in return. The updated representation is relied on both previous step community representation and current user propagative representation. Therefore, to better embrace the two representations, we use a delicate RNN variant, where the update process is calculated as follows:

where $G\in\{M,S\}$. $s^{G}$ denotes the update rate and $z^{G}$ is transformed user information to be updated in current community. $d_{j}^{G*}$ denotes the updated representation of the $j_{th}$ community in graph $G$, which is the weighted sum on previous community and current user representations. $W_{s}^{G}$ and $W_{z}^{G},$ denote related weight matrices, while $b_{s}^{G}$ and $b_{z}^{G},$ denote related biases.

Community Constraint: To obtain the communities with less overlapping information in graph $G\in\{M,S\}$, the community representations ideally should be independent with each other. In our model, cosine similarity ${\rm cos}(\cdot)$ is taken as the criteria to measure the community similarity where higher score indicates stronger correlation. The averaged cosine similarities of all possible community representation pairs is calculated as a community loss to minimize:

where $K$ is the number of communities in each graph.

Similar to RankNet (Burges, 2010), given a mutual user triplet $\langle u_{i},u_{j},u_{k}\rangle$, as three types of pairwise label are considered including “closer”, “similar” and “farther”, label $y_{i,j,k}$ is calculated as follows:

In terms of the community closeness for $u_{i}$, if $u_{j}$ is closer than $u_{k}$, $S_{jk}=1$; if $u_{j}$ is farther than $u_{k}$, $S_{jk}=-1$; if $u_{j}$ and $u_{k}$ are similar, $S_{jk}=0$. In this way, we convert the pairwise ranking task to a regression task.

To optimize this task, first of all, we calculate the correlation representation $r^{G}_{ij}$ between $u_{j}$ and $u_{i}$ in single graph $G\in\{M,S\}$:

where $W^{G}_{r}$ and $b^{G}_{r}$ are related weight and bias, respectively.

To construct the information from both graphs, we concatenate the correlation representations from both graphs:

Similarly, the cross-graph correlation representation between $u_{i}$ and $u_{k}$ is calculated as $r_{ik}$.

After that, we predict the community relationship between $u_{j}$ and $u_{k}$ towards $u_{i}$ as follows:

where $W_{o}$ and $b_{o}$ are the related weight and bias. $\sigma(\cdot)$ denotes the sigmoid activation function. In the end, the final loss $\mathcal{L}_{total}$ is the weighted sum of the optimization loss calculated via cross entropy and the community constraint losses where $\mathcal{L}_{c}^{S}$ is for the sparse graph and $\mathcal{L}_{c}^{M}$ is for the main graph:

Although our model is trained solely on mutual user triplets, it is also able to detect pairwise community closeness among users only appeared in either sparse graph or main graph. Two training tricks are particularly employed in our model to improve model robustness, including shared weights and masked training.

First, as our model should be insensitive to the sequence of input user triplet, the weight matrices, biases and project vectors in both Section 2.3 and Section 2.4 should be shared among the three users. Moreover, in Section 2.4, the community memory $D^{G}$ where $G\in\{M,S\}$ is updated by taking the average of the three updated community representations (calculated in Eq. 7) from input triplets.

Second, to alleviate the negative effects of excessive connections in main graph $M$, we employ a masked training strategy by randomly remove a small ratio $\rho$ of connected objects from users in the main graph during each training batch. $\rho=0$ means users remain their original multi-hot embeddings while $\rho=1$ means users lose all their connections on objects.

As one of the largest e-commerce ecosystems, Alibaba owns multiple online businesses, where users could try different services via the same login ID. For this experiment, we employ three services from Alibaba including an online shopping website, a digital news portal and a cooking recipe website. The online shopping website is regarded as the main graph because it is Alibaba core service having the largest number of active users. By contrast, the other two services are regarded as sparse graphs. In the online shopping website, each object refers to a product for sale, and links are user purchase behaviors on products. In the digital news portal, each object refers to a news article, and links are user reads on news. In the cooking recipe website, each object refers to a cooking recipe, and links mean that users follow recipe instructions.

To prove our model robustness with respect to the graph size, two cross-graph datasets are constructed in different scales, which are showed in Table 1. The SH-NE dataset is the cross-graph dataset constructed by the shopping graph and news graph, which is ten times larger than the SH-CO dataset constructed by the shopping graph and recipe graph. Users are categorized into three different types including MU (mutual users appeared in both graphs), MO (users only appeared in the main graph), and SO (users only appeared in the sparse graph). Note that, only mutual user triplets are used for training.

Both datasets are built by taking a week of user behaviors from 09/20/2018 to 09/26/2018. In this paper, for two sparse graphs, we aim to predict user pairwise community labels (calculated from enriched seven-day user behaviors) using sparse user behaviors (the first four-day user behaviors, arbitrarily defined in this paper).

To construct our ground truth data, we run all baseline models (will be introduced in Section 3.2) on both seven-day sparse graphs which are assumed to contain sufficient user-product connections during this relatively long time period. Only mutual user communities agreed by all six baselines (except random model) are kept, from which mutual user triplets are subsequently selected as we assume the commonly-agreed communities are reliable. In this paper, we define three types to label pairwise community closeness for a mutual user triplet, including “closer”, “similar”, and “farther” (detailed definition is in Section 2.1). Equal number of triplets are randomly selected for each label type. In total, there are 207,291 triplets in SH-NE dataset and 20,313 triplets in SH-CO dataset for testing propose.

Training data generation is the same as ground truth data construction except using first four-day user behaviors. In total, there are 2,072,905 triplets in SH-NE dataset and 203,123 triplets in SH-CO dataset, from which 90% of the triplets are used for training and 10% for validation.

In both training and testing process, our model input is user triplets with first four-day behavior information. Their difference is that the pseudo labels for training are generated from four-day user behaviors, while the ground truth labels for testing are generated from whole seven-day user behaviors in sparse graphs.

As there is neither reliable nor open-sourced studies on pairwise cross-graph community detection, we have no direct comparative models. In this paper, we select one random model and six compromised but state-of-art baselines which are originally designed for whole graph community detection. In all seven baselines, after user communities are detected, we calculate user triplet labels via Eq. 9. As all baselines are trained on the sparse graph with first four-day user behavior and the main graph, they bring no information loss compared with our model. Here is the details of how these baselines calculate user communities:

• •

  random: users are randomly assigned to a given number of communities.

• •

  Infomap (Kheirkhahzadeh et al., 2016): A random walk based method to detect user communities by minimizing description length of walk paths¹¹1https://github.com/mapequation/infomap.

• •

  DNR (Yang et al., 2016): A novel nonlinear reconstruction method to detect communities by adopting deep neural networks on pairwise constraints among graph nodes²²2http://yangliang.github.io/code/.

• •

  LSH (Chamberlain et al., 2018): A random walk based method for community detection in large-scale graphs³³3https://github.com/melifluos/LSH-community-detection.

• •

  node2vec (Grover and Leskovec, 2016): A skip-gram model to generate node emebeddings based on guided random walks on graphs. And K-means method subsequently calculates communities from the generated embeddings⁴⁴4https://github.com/snap-stanford/snap/.

• •

  BigClam (Yang and Leskovec, 2013): A non-negative matrix factorization method to detect overlapping communities in large scale graphs4.

• •

  WMW (Castrillo et al., 2017): A fast heuristic method for hierarchical community detection inspired by agglomerative hierarchical clustering⁵⁵5https://github.com/eduarc/WMW.

The result is reported with best hyper-parameters from grid search. Empirically, a mini-batch (size = 200) Adam optimizer is chosen to train our model with learning rate as 0.01. Community number on both graphs is $K=50$ (Eq. 8). Community constraint weight is $\alpha=0.1$ (Eq. 13). Masked training rate in the main graph is $\rho=0.05$. The model is trained for 1000 epochs in order to get a converged result.

Model performance is evaluated from both classification and retrieval viewpoints. From classification aspect, Accuracy (ACC), F1-macro (F1) and Matthews Correlation Coefficient (MCC) are reported metrics. From retrieval aspect, Mean Reciprocal Rank (MRR), Normalized Discounted Cumulative Gain (NDCG) and Mean Average Precision (MAP) are reported metrics. All of them are fundamental metrics widely used for model evaluation.

All model performance are evaluated from both classification and retrieval viewpoints. Each baseline method is run on three graphs including the main graph, the sparse graph, and their combined graph. While our model can only be tested by utilizing both graphs given the proposed model structure. Table 2 shows the overall model performance under three graphs. Particularly, we run our model ten times and report the average performance result. To verify our model’s superiority, we calculate the performance differences between our model and the best baseline on each metric for all the runs, and apply a pairwise t-test to check whether the performance difference is significant.

Our model output is a predicted score in the range from 0 to 1. Its associated label is assigned to be one of “closer”, “similar” or “farther” based on which third the predicted score lies in (associated with label definition in Section 2.5). For example, a user triplet $\langle u_{i},u_{j},u_{k}\rangle$ with score 0.3 will be labelled as “farther”, which means compared with $u_{k}$, $u_{j}$ is has a farther community closeness to $u_{i}$. After that, from classification perspective, ACC, F1 and MCC scores are calculated by comparing predicted labels with the ground truth labels. While from retrieval perspective, MRR, NDCG and MAP are calculated for the pairwise ranking within user triplets.

Table 2 shows that almost all baseline performances in the combined graph achieve the best among three types of graphs. And performances in the main graph are always better than in the sparse graph. It demonstrates that main graph holds beneficial information to reveal user potential communities in sparse graphs. The random baseline is with similar performance among all three graphs, which makes sense because the random community partition is regardless of graph structures. It can be used as the default model to compare with in each graph. For the rest six baselines, random walk based baselines (Infomap and LSH) do not perform well in all three graphs. Their evaluation results are just a bit better than random model performance. Even though solely running Infomap does not perform well, it is the most supportive model for Section 2.2 Raw Community Detection (related empirical experiment comparisons are omitted as it is not the major model contribution). WMW model performs the best among all baselines. Actually, its results are always the best in three graphs of both datasets. However, by taking the pairwise t-test, it statistically proves that our model still significantly outperforms the WMW model in terms of all metrics.

It is also interesting to see that the model evaluation results are consistent in all datasets. For example, DNR model always performs better than LSH model. The only exception is that BigClam performs better than node2vec in SH-NE dataset, but worse in SH-CO dataset.

In this section, we aim to explore whether all components of our proposed model have positive effect on final model performance and which component has the largest impact. There are six components that can be disassembled from the main model, including Raw Community Representation in the main graph (RCR), Direct Transformation Representation (DTR), Node-level filter (NF), Community-level filter (CF), Community Constraint (CC) and Masked Training (MT). We iteratively remove each component while keep the rest firmed to demonstrate their performance difference compared to the original model. All comparison results are showed in Table 3.

Among the six components, if we remove node-level filter, the performance drop dramatically, even worse than some of baseline models. It indicates that node-level information are excessive and noisy. Without appropriate filtering on the propagated information, it would vitally pollute the quality of user representations. Similarly, community-level filter also has a huge impact on model performance, meaning filtering propagated information from a coarser view also has a positive effect on learning user representations. By contrast, the two extra representations (RCR and DTR) do not have strong influence in our model. Having these information can slightly improve model performance as they still involve extra information. However, as one-hot embeddings, the amount of new information that RCR can offer is very limited. Similarly, DTR is only one-layer transformation on multi-hot embeddings. The information it can offer is also limited. By adding extra constraint, CC also has a little positive effect to enhance model performance. But as we always set its weight with a small value in training process, its influence is also indifferent. MT has the least impact on model performance as randomly masking user behaviors in the main graph has an overlapped effect with attentive weights calculated from the node-level filter in Section 2.3.

As aforementioned in Section 3.1, there are three types of users in our cross-graph datasets including MU (mutual users appeared in both graphs), MO (users only appeared in the main graph), and SO (users only appeared in the sparse graph). Unlike our training data which is constructed only with mutual users, our testing data can be with all types of users. To examine our model performance on each type of users, each single-type user user triplets are screened with five thousand instances, i.e., an eligible user triplet only contains three MO type users. In fact, the performance on MO user triplets reflects the capability of our model to solve cold-start problem as these users have no behaviors in the sparse graphs. The result showed in Table 4 demonstrates that the label of MU triplets can be best identified, which makes sense as the information of mutual users come from both graphs. While performance results on MO are better than SO user triplets, which might because that users are likely to have more enriched behaviors in the main graph compared with the sparse graph. Even that, the performance of our model on SO user triplets is still better than most of baselines running on the combined graph.

To explore our model robustness for solving cold-start problem on sparse graphs, we randomly keep $\delta$ ratio of the total links in the sparse graph, where $\delta=\{0.1,0.3,0.5,0.7,0.9\}$. Our model is trained on the whole main graph and each truncated sparse graph. The reported evaluation metrics under all sparse graphs with varied scales are visualized in Figure 5. All metrics in both SH-NE and SH-CO datasets are in a rising trend with more links preserved in related sparse graphs. Compared with SH-NE dataset, SH-CO can benefit more from the sparse graph as it has a larger increase in all reported metrics.

With more links are preserved, all evaluation metrics first grows rapidly. While the increasing speed slows down when 70%-90% links are preserved. This phenomenon can be seen in almost all plots in Figure 5. It can be explained by the law of diminishing marginal utility, meaning that the marginal utility to bring new information derived from each additional link is declined.

Although classification related metrics significantly increase with more links preserved (i.e., F1 score in SH-CO dataset increases 10% when involving sparse graph), the retrieval related metrics (MRR, NDCG and MAP) do not change much in the mean time. One possible reason is that the information from the main shopping graph already contains enough information for the pairwise ranking in user triplets. For example, without considering sparse graph information, our model has already achieved high MRR score as 0.87 in SH-NE dataset and 0.89 in SH-CO dataset, which is already better than most baseline results running on the combined graph.

In order to testify whether our proposed Community Recurrent Unit is able to accurately calculate user affiliation scores in each community, we choose three users (labelled from user $u_{1}$ to user $u_{3}$) and calculate their affiliation scores of ten selected communities (labelled from community $c_{1}$ to community $c_{10}$) in the main shopping graph. The detailed result is visualized in Figure 6. In the left part of the figure, darker color indicates higher affiliation scores in the range from 0 to 1. Besides, in the shopping graph, we also extract all products purchased by each user, and manually select the most representative ones summarized as keywords in a table, which is demonstrated in the right part of Figure 6.

From the right-part table, $u_{1}$ and $u_{2}$ share similar shopping interests in clothing products. $u_{2}$ is more like a girl fond of sports. And $u_{1}$ more tends to be a fashion girl. While the shopping interests of $u_{3}$ is much far away from the other users. All purchased products by $u_{3}$ is furnishing stuffs. It seems s/he is decorating her/his living space. Referring to the left part of Figure 6, the affiliation distribution among ten communities between $u_{1}$ and $u_{2}$ are very similar. They both have a high weight in community $c_{1}$, $c_{7}$ and $c_{8}$. While the community distribution of $u_{3}$ is totally different. $u_{3}$ is heavily affiliated with community $c_{2}$. The results of our calculated community affiliation distribution is consistent with actual user behaviors, which indicates our Community Recurrent Unit (CRU) is functional well to reflect user community information.