Collaboration Based Multi-Label Propagation for Fraud Detection

1 Introduction

The rapid growth of information technologies enables billions of people to shop online. E-commerce platforms connect customers with factories, stores, and third-party merchants, providing them a convenient, reliable and fast manner of shopping. Meanwhile, e-commerce has brought huge economic benefits to society. For instance, in the fiscal year of 2018, eBay GMV (gross merchandise volume) is reported to reach US $95 billion 1 and Alibaba GMV is reported to reach US $673 billion 2 .

Most e-commerce platforms calculate a ranking index and a reputation factor for sellers using the number of actions, e.g. clicks, purchases, and reviews. In general, items with a better ranking index will be listed in the front of the search results, and buyers prefer those items with a good reputation. Regular ways to boost these measurements include providing highquality items, good services, and advertising, which usually take much effort. It motivates some malicious merchants to promote their items by spam actions. Such dishonest behaviors lead to serious consequences: 1) for the customers, they are misled to purchase items seemingly only good on numbers over quality; 2) for regular sellers, their incomes are directly affected, which causes unfair competition; 3) for the e-commerce platforms, it increases the difficulty of recognizing good sellers and decreases the advertising revenues. As demonstrated in [Tian et al., 2015], the malicious promotion has caused hundreds of millions of dollars loss worldwide.

∗Zhao Li and Weiwei Liu are corresponding authors.

1 https://investors.ebayinc.com/overview/default.aspx

2 https://www.alibabagroup.com/cn/ir/earnings 2018.php

To deal with this problem, e-commerce platforms usually treat the fraud detection task as a binary classification problem, i.e., detecting fraud ones from an extremely huge number of users. For example, some algorithms [Li et al., 2014; Tian et al., 2015; Vlasselaer et al., 2017] propagate the label information on the user adjacency graph to discover the abnormalities. However, in reality, a fraud user may perform multiple species of fraud operations simultaneously, such as spam transactions, clicks, reviews and so on. As illustrated in Figure 1, the third-party fraud platforms will provide some combinational fraudulent strategies. Hence, a simple binary classification model is less powerful to deal with such rich labeling information.

To bridge this gap, we propose to assign each user multiple fraud labels. Moreover, since there are hundreds of millions of users, fully-annotation is impossible and only a few labeled data is available. Hence, it is formalized to a semisupervised multi-label learning (SSML) problem. A straightforward solution is binary relevance [Zhang and Zhou, 2014], that decomposes the original problem to a series of semisupervised binary classification tasks. Despite its simplicity and computational efficiency, it ignores the correlations among the labels and the predictive performance is limited. Utilizing off-the-shelf SSML methods [Kong et al., 2013; Wang and Tsotsos, 2016; Tan et al., 2017] seems to be an appealing strategy. However, most of them are either incompatible for e-commerce tasks or incapable of handling instancelevel large-scale datasets.

Consequently, this paper proposes a novel collaboration based multi-label propagation method (CMLP) for largescale SSML fraud detection task. First of all, we present a generic version that only propagates the independent label information and recovers the original labels by collaboration. To accommodate the large-scale e-commerce data, we employ the user-item interaction matrix as a bipartite graph to detect the communities and propose a scalable heterogeneous graph propagation variant of CMLP (H-CMLP). Furthermore, we rigorously prove that the resultant algorithm actually propagates information using Adamic-Adar weight. Extensive experiments demonstrate that the proposed method not only outperforms on ordinary multi-label datasets, but is effective and scalable on large-scale e-commerce dataset.

The main contributions of this work include: 1) A generic semi-supervised multi-label learning method CMLP is proposed. It integrates the collaboration and label propagation techniques to fully utilize the label dependencies and latent data distribution. 2) To handle e-commerce data, we accelerate CMLP by propagating information on the user-item graph directly. 3) Both theoretical analysis and empirical results verify the efficiency and effectiveness of our method.

2 RelatedWork

2.1 Fraud Detection

Malicious promotion is one of the major threats faced by ecommerce platforms. Dishonest merchants usually employ many fraud users to create unreal transactions, clicks, reviews and so on. To find out these fraud users, various detection algorithms have been proposed. One of the most popular approaches [Li et al., 2014; Tian et al., 2015; Tseng et al., 2015; Hu et al., 2017; Vlasselaer et al., 2017] focuses on graphbased fraud detection. Other detecting techniques include mixture model based methods [Bahrololum and Khaleghi, 2008], deep neural network models [Guo et al., 2019] and so on. However, they cannot be directly applied to our problem for two reasons. First, many of them are either dedicated to one specific platform or designed for other application domains, e.g. click fraud [Li et al., 2014], phone call fraud [Tseng et al., 2015] and so on. Second, existing fraud detection methods can handle single-label classification problems only.

2.2 Semi-SupervisedMulti-Label Learning

Multi-label learning (MLL) [Chen and Lin, 2012; Zhang and Zhou, 2014; Liu and Tsang, 2017; Liu et al., 2019] assumes that each data example is associated with multiple labels simultaneously. Most existing MLL methods focus on a fullsupervised setting. However, in real-world applications, it is expensive and difficult to obtain precisely annotated data. Therefore, semi-supervised multi-label learning (SSML) has significantly attracted the attention of researchers. To learn from both unlabeled and multi-labeled data, some algorithms [Zhan and Zhang, 2017] involve co-training technique in SSML, but they work well only when the conditional independence assumption holds. Another practical solution relies on utilizing the graph structure of data. For instance, manifold regularization based approaches [Jing et al., 2015; Tan et al., 2017] explore the topological structure of data; label propagation based methods [Kang et al., 2006; Kong et al., 2013] aggregate the neighbor information iteratively. Although these graph-based methods are promising on ordinary multi-label data, they are time-consuming and impractical in e-commerce fraud detection task. Specifically, manifold regularization algorithms usually require complex optimization techniques, and thus are demanding in large-scale datasets. Moreover, all of them are designed to run on the user-user adjacency graph, which is usually dense and large.

Note that that there are also some works study large-scale MLL problems [Bhatia et al., 2015]. However, they focus on the eXtreme Multi-Label learning (XML) setting, i.e. there are extremely many labels. We concentrate on the instancelevel large-scale problem, because a malicious service platform usually provides only dozens of kinds of services.

3 ProposedMethod

In this section, we first introduce a generic solution to SSML, i.e. collaboration based multi-label propagation algorithm (CMLP). Then, to make it feasible in large-scale e-commerce data, we accelerate it by propagating label information on a heterogeneous graph directly.

3.1 Collaboration BasedMulti-Label Propagation

We denote the instance matrix by X ∈ Rn×p . The target matrix of labeled data is denoted by Y ∈ {-1,+1}l×q (q ≪ n). Given an undirected graph G = 〈E, V,W〉, vanilla label propagation method iteratively updates the labels of one certain node by aggregating its neighbor's label information. Here E, V are edge, vertex sets, respectively. W = [wij]n×n is a non-negative weight matrix. Let P = D-1/2WD-1/2 be the propagation matrix by normalizing the columns of W, where D = diag[d1, d2, ..., dn] is a diagonal matrix with di = ∑nj=1 wij . Denote the model output by F = [ F l F u ] ∈ Rn×q , where F l ∈ Rl×q . According to

[Zhou et al., 2003], on t-th round, the updating procedure of vanilla label propagation algorithm is as follows,

where ˜ Y = [ Y0 ] and F0 = ˜ Y . Here β is the learning rate and µ is a regularization parameter.

In multi-label setting, such a simple strategy fails to utilize the label correlations and achieves degenerated performance. To cope with this limitation, CMLP makes a collaborative assumption [Feng et al., 2019] that the prediction for an individual label consists of two parts: its own prediction and the prediction of others. We involve a correlation matrix R = [rij]q×q where rij reflects the contribution of i-th label to j-th label and rii = 0, i.e. there is no collaboration from the label itself. Suppose the desired method gives an ordinary prediction f(X), the final prediction is made by,

That is, the final output absorbs the prediction of other labels in a collaborative fashion. By regarding the ground-truth of labeled data as final prediction, CMLP estimates R by,

where yj, rj denote the j-th columns of Y , R. Here α is the collaboration degree, a tradeoff parameter between the original prediction and the collaborative prediction. γ is the regularization parameter. By simple reformulation, it can be transformed to a standard ridge regression problem and therefore can be efficiently solved.

Recall the main drawbacks of existing multi-label propagation algorithms that they are either time-consuming or incapable of exploiting label dependencies. To tackle these problems, we propose an effective method that propagates only the independent part of labels instead of original label information. By assigning an intermediate variable Z ∈ Rl×q to the labeled instances, CMLP aims to optimize the following objective,

where Q = (1 - α)I + αR, µ and λ are trade-off parameters. f i is the i-th row vector of F. || · ||F is the Frobenius norm. To be more specific, CMLP simultaneously solves two subproblems: 1) propagating independent label information Z on the graph; 2) fitting the final predictions using correlation matrix R. Such an objective not only encourages the mutuality of these two subproblems, but enables our method to be highly scalable.

In this work, we initialize the variables by F0 = [ Y0 ] and Z0 = Y . Since Eq. (4) is a biconvex problem, it can be solved in an alternating way.

Updating F With Fixed Z

When Z is fixed, the remaining items constitute an objective of soft label propagation algorithmwith independent label Z. We first derive the gradient by,

where ˜Zt = [ Zt 0 ]. Then we perform a gradient descent step with learning rate β for F such that,

Updating Z With Fixed F

With F being fixed, the optimization problem reduces to,

A closed-form solution can be obtained by setting the gradient to zero,

When the iterations end, we have to transform the output to final prediction ˆ Y u = Ψ(F uQ). Here Ψ is a post-process operator, consisting of normalization and binarizing.

Time Complexity

The main computation of our method lies in the iteratively propagating labels on the graph. In Eq. (6), the matrix product of P and Ft dominates and takes O(qn2 ), which is the same as vanilla LP method. As for Eq. (8), ηYQ⊤ and (I +ηQQ⊤)-1 can be pre-computed with only few computation. Thus, updating Z requires O(lq2 ) and is much cheaper than updating F. In this paper, we do not consider extreme classification setting, and thus q ≪ n. We conclude that our algorithm is as fast as the original LP method with time complexity O(qn2 ) in each iteration.

Compared to other state-of-the-art multi-label propagation algorithms, our method is more scalable. For instance, CLP [Kang et al., 2006] solves a constrained optimization problem in each iteration, which is infeasible in large-scale semisupervised MLL problems. Our updating procedure only requires simple matrix operations and can be highly parallelized to achieve good scalability.

3.2 Heterogeneous Graph Propagation

Yet, we proposed a generic correlation-aware propagation algorithm for ordinary SSML tasks. In effect, the graph can be collected in a variety of ways, e.g. k-nearest neighbor adjacency graph [Wang and Tsotsos, 2016], webpage links [Wu et al., 2014; Wu et al., 2015] and so on. In the e-commerce fraud detection scenario, our goal is to determine whether a user has some fraud behaviors. In general, malicious merchants will hire many fraud users to buy the same items. Therefore, a natural choice is to synthesize a user-user mapping (U-U graph) from the user-item bipartite graph (U-I graph), i.e. two users are connected to each other if they are interested in the same item. Though this strategy avoids building a graph explicitly, which is usually time-consuming, we observe that it gives a really dense graph in practice (Figure 2). In many e-commerce platforms, a popular item can be connected to millions of users. Thus, U-U graph may contain many complete subgraphs and the number of edges grows dramatically. As we discussed above, the main computation cost of CMLP lies in the propagation procedure, i.e. aggregating label information from adjacent nodes. Thus, it will be demanding in large-scale datasets.

To alleviate this problem, we present a heterogeneous graph propagation (H-CMLP) approach, which detects communities on U-I graph directly. For simplicity, we concentrate on the propagation part in Eq. (6), i.e. At+1 = PFt. The calculation of At+1 can be divided into two steps. In the first step, for each item, we aggregate information from its neighbor users. Denote the temporary label vector for an item ek by sk . On t-th round, it is updated by,

where N(ek) is the index set of users that connect to ek, and f j t is the j-th row vector in Ft. In the second step, H-CMLP propagates the labels back to the users. Formally, for i-th user ui, its propagation part ait+1 is calculated by,

Here | · | denotes the capacity of a set and log(·) is natural logarithm.

Lemma 1. The updating rule defined by Eq. (9) and Eq. (10) is equivalent to propagating information on U-U graph using Adamic-Adar weight.

Proof. Consider a U-U graph based LP method that adopts Adamic-Adar [Adamic and Adar, 2003; Benson and Kleinberg, 2019], a common measure in graph mining problems, Define Hg,h(i, j, k) = ∑j∈Φ(i) ∑k∈N(ui)∩N(uj) h(k)g(j) with given function h and g. Namely, once there is an item ek shared by ui and uj, it contributes h(k)g(j) to Hg,h(i, j, k). Actually, we can reformulate it to Hg,h(i, j, k) = ∑k∈N(ui) h(k) ∑j∈N(ek),j̸=i g(j). Note that in Eq. (12), the numerator is a typical H function with h(k) = (log(|N(ek)|)-1 and g(j) = f j t . The denominator is also an H function with a same h and g(j) = 1. We conclude that Eq. (12) can be rewritten to,

We observe that ∑j∈N(ek),j̸=i f j t = skt - f i t . Hence, Eq. (12) is equivalent to Eq. (10) and the lemma is proved.

Time Complexity

According to Eq. (12), original CMLP takes O(2q|E|) time, i.e. summing up the degree number of all the nodes, to update the labels of each node. When the U-U graph is dense, e.g. many users are interested in some popular items, |E| can be extremely large. However, in heterogeneous graph setting, each propagation step travels all the edges on U-I graph. Thus, the time complexity is O(2q| ˆE|), where ˆE is the edge set of U-I graph. As illustrated in Figure 2, | ˆE| is much smaller because user-item interactions are usually sparse.

4 Experiments

4.1 OrdinaryMulti-Label Data

To show the effectiveness of our collaboration technique, we test CMLP on some ordinary multi-label datasets.

Datasets

We choose four real-world multi-label datasets from different task domains: 1) Medical [Pestian et al., 2007]: a text dataset contains clinical free texts, each of which is with 45 ICD9-CM labels, from CCHMC Department of Radiology. 2) Image [Wang et al., 2019]: a collection of 2, 000 images that are annotated by 5 labels. 3) Slashdot [Read et al., 2009]: a web text dataset collects 3, 782 technology-related news from 22 categories. 4) Eurlex-sm [Loza Menc'ia and F¨urnkranz, 2008]: a large text dataset contains 19, 348 legal documents about European Union law, having 201 subject matters tags.

All the datasets are randomly partitioned to 5% labeled data and 95% unlabeled data. In this paper, we focus on the transductive setting. We conduct these experiments for 5 times and the mean metric values with standard deviations are provided. In this work, we use four popular multi-label evaluation metrics [Zhang and Zhou, 2014], i.e. Ranking Loss, Example-F1, Macro-F1, and Micro-F1.

Benchmarks

The baselines include three state-of-the-art SSML methods and two supervised MLL algorithms: 1) Vanilla-LP [Zhou et al., 2003]: Vanilla label propagation algorithm utilizes the smooth property between labeled and unlabeled data to design a classifying function. It can also be regarded as a binary relevance model with LP model as the base classifier. 2) SMILE [Tan et al., 2017]: SMILE explores second-order label correlations by estimating a label correlation matrix from labeled data. Then it trains a linear multi-label classifier with manifold regularizer. 3) TRAM [Kong et al., 2013]: TRAM is a popular SSML algorithm that uses a hard label strategy to find out communities on the graph. 4) CPLST [Chen and Lin, 2012]: CPLST is a supervised MLL method that combines the concepts of principal component analysis and canonical correlation analysis. 5) DeepFraud [Guo et al., 2019]: DeepFraud is a deep neural network based fraud detection algorithm, which can deal with single-label problems only. Hence, we decompose the SSML problem into a set of single-label classification tasks to run this method.

Inspired by [Wang et al., 2019], we build a k-NN adjacency graph and the weight matrix is learned by reconstructing each instance using its neighbors. When building graphs, k is set as 20. For our methods, γ is selected from {0.1, 1, 10, 100}. α is chosen from {0.01, 0.05, 0.1, 0.2, 0.5}. β, λ and µ are empirically fixed to 0.1. For Vanilla-LP, β and µ are the same as CMLP. The parameter α and s in SMILE are both set as 0.5. For DeepFraud, we apply a three layer neural network with ReLU activation. The hidden size is set as 128. The learning rate and regularization parameter are set as 0.001 and 0.5. Other parameters of the baselines are set to their recommended values in their papers.

Results

Table 1 lists the transductive results on all the datasets. Figure 3 reports the parameter sensitivity of α and λ. From the empirical results, we conclude that: 1) CMLP generally achieves the best performance. For instance, on Image dataset, in terms of Example-F1, Macro-F1 and Micro-F1, CMLP improves the best results of the baselines by 3.1%, 3.5% and 3.3%. 2) Vanilla-LP and TRAM underperform our method, because they neglect the correlations among labels. 3) The effectiveness of SMILE is limited since it exploits the secondorder correlations only. 4) CPLST and DeepFraud are inferior to other methods because they ignore the distribution information of unlabeled data. 5) α has a significant influence on the final performance. Empirically, relatively small α leads to good performance. Moreover, CMLP is relatively stable with varying values of λ.

Table 3: The characteristics of Taobao-FUD dataset.

4.2 E-commerce Fraud Data

Experimental Setting

The other experiment is conducted on a large-scale ecommerce dataset Taobao-FUD. Taobao-FUD collects an interaction matrix from more than 72 million users and 80 million items. Each user is equipped with four binary labels {Transaction, Cart, Click, Review}, indicating whether the users have corresponding fraud behaviors on some items. If we construct a U-U graph from Taobao-FUD, the number of edges can be larger than 100 billion. Obviously, mining on such an extremely large graph is impossible. To verify the time efficiency of H-CMLP, we sample some user subsets with capacities of {1 K, 5 K, 10 K} (1 K = 1000) to construct three subgraphs and report the running time of H-CMLP and Vanilla-LP. Then, to compare the predictive performance, we implemented heterogeneous versions of Vanilla-LP (HV-LP) and TRAM (H-TRAM). We randomly select 5% examples as labeled data and the rest are used to evaluate the transductive performance. The statistical information of TaobaoFUD can be found in Table 3.

Note that SMILE and CPLST are incapable of dealing with instance-level large-scale data. Thus, we choose Vanilla-LP, TRAM, and DeepFraud as the benchmarks. Nevertheless, there are only graph-structured data in Taobao-FUD dataset, and DeepFraud cannot be applied directly. Therefore, we firstly extracts user embeddings using GraphSAGE on the U-I Graph and then feed them into DeepFraud model. The parameter setup and evaluation metrics are the same as last subsection. The computations are performed on MaxCompute platform, a fast, distributed and fully hosted GB/TB/PB level data warehouse solution. We use three computation instances for time comparison and 3000 instances for performance comparison.

Results

Table 2 reports the transductive performance of all the methods on Taobao-FUD. From the results, we observe that HCMLP is the most successful method. In terms of Micro-F1, Macro-F1, and Example-F1, H-CMLP improves the best results of the baselines by 1.6%, 4.6%, 2.2% respectively. The results demonstrate that the proposed method can effectively address the fraud detection task because our collaboration technique can sufficiently exploit the label correlations.

Table 4 shows the average running time on each iteration of H-CMLP and Vanilla-LP on three subgraphs. For H-CMLP, the running time has no obvious fluctuation. The reason is the size of U-I graph is really small, and the main computation is the scheduling procedure of MaxCompute. For Vanilla-LP, the U-U graph is much larger, and thus its running time grows quickly. By these observations, we conclude that our method can efficiently address the multi-label fraud detection task.

5 Conclusion

The huge success of online shopping motivates dishonest sellers to illegally promote their reputations. In general, these malicious merchants will hire many fraud users to create different kinds of spam actions concurrently. To tackle this problem, we treat the fraud user detection task as semi-supervised multi-label learning (SSML) problem and propose a scalable graph-based SSML algorithm. We first introduce a generic version that decomposes the final prediction to an independent part and a collaborative part. Then, to accommodate large-scale e-commerce data, we accelerate it by detecting communities on the user-item interaction graph directly. Extensive experiments demonstrate that our method can effectively and efficiently handle both ordinary SSML problems and fraud detection task.

Acknowledgments

This work is supported by the National Natural Science Foundation of China (Grant No. 61976161) and Key R&D Program of Zhejiang Province (Grant No. 2020C01024).