Risk Assessment for Networked-guarantee Loans Using High-order Graph Attention Representation

1 Introduction

The bank loans are critical for the development of the small and medium enterprise [Biggs, 2002]. As the traditional rules are usually designed for the majority independent market players, the existing loan assessment criteria is inadequate for real demand. Companies are allowed to guarantee each other to enhance loan security. When more and more companies are involved, they form complex guarantee networks. Such complex structures are a double-edged sword for the national economy. On one hand, such easy-loans can help companies raise funds quickly, on the other hand, highly coupled relationships could magnify default risk along the guarantee chain even lead to massive defaults systematic risk. Whether a loan will be delinquent depends not only on its own financial status, but also on other companies in the network, which brings new challenges in loan risk assessment for banks.

∗Corresponding Author

Traditional approaches to predicting bank loan delinquency mainly use financial probabilistic models [Siddiqi, 2012; Bravo et al., 2015], for example the credit scorecards, which utilize a shallow linear regression or classification model with the borrower's financial information. With recent advances in machine learning techniques, different algorithms have emerged to improve prediction accuracy by increasing model capacity and adding behavior information [Fitzpatrick and Mues, 2016; Cheng et al., 2018].

However, these techniques (credit scorecards and machine learning methods) have two significant disadvantages: 1) they rely mainly on historical information of individual enterprises and are therefore unable to discover the delinquency probability caused by networked loans; 2) the classification model gives equal weights to each sample (i.e., each SME), but different nodes contribute differently in networked-guarantee loans. That means we should focus on dominant companies to curb systemic risk so as to discover the risk patterns.

To this end, we propose a high-order graph attention representation method (HGAR) for the default risk assessment of the networked-guarantee loans. The intuition behind the technique is that, based on our observations, the default probability of a borrower involved in a guarantee network is also influenced by connected nodes. This is because, in guarantee loans, if the borrower fails to repay to the bank, its guarantors have the debt obligation. This means defaults may spread rapidly across the network like the infectious disease transmission, especially during the period of economic downturn where many companies will fail to repay loans. This would have a domino effect and cause numerous enterprises to fall into an unfavorable situation.

Therefore, by integrating guarantee network representations to loan risk assessment systems, we are able to infer the delinquent probability comprehensively. We first set each vertex in the guarantee network to a binary role, guarantor or guarantee, and then present a graph attention layer that captures nodes' dominant importance in a network. Afterwards, we propose objective functions to preserve the binary role of nodes and high-order adjacency, and apply a productive strategy to optimize it. Through theoretical analysis, we demonstrate that the complexity of the proposed method is linear to the number of edges, which could scale to real-world large networks.

In a nutshell, the main contributions of this paper are:

1. We provide the first attempt in loan risk assessment by adding high-order graph attention representations (HGAR) in order to predict loan delinquency and warn of a domino effect loan crisis.
2. We propose a new high-order and graph attention based network representation method and demonstrate that the learned representation can improve the performance of loan delinquency prediction.
3. We conduct extensive experiments on real-world datasets over six months' empirical study. The result demonstrates that our methods can effectively predict defaults and provide early warning of loan risks.

2 RelatedWorks

We summarize the related works in two main areas: 1) graph representation; 2) networked financial risk.

Graph Representation

Graph representation is also known as network embedding, which is a learning approach designed to map each node of a network to a low-dimensional space by machine learning techniques [Perozzi et al., 2014; Cheng et al., 2019]. It learns latent representations using local information obtained from various types of walks, which are treated as the equivalent of sentences [Velickovic et al., 2018]; alternatively, it represents the connections between network vertices in the form of a matrix and uses different matrix factorization methods to obtain the representations [Liao et al., 2018; Li et al., 2018]. However, most of these studies are targeted on social, semantic, or citation networks, dismissing domain characteristics. Few of them tackle the loan defaults problem in financial networks.

Networked Financial Risk

Financial crises and systemic risk have always been a major concern for financial companies and governments, with extensive work on this having been undertaken [Fischer and Molenaar, 2012]. Networks represented by interconnected nodes and links between them are a good representation of modern financial systems as they also have complex interdependence and connections internally [Allen and Babus, 2008]. Researchers started to pay more attention on network theory after the 2008 global financial crisis, because the crisis brought on by the collapse of Lehman Brothers spread throughout connected corporations is similar to the epidemic of Severe Acute Respiratory Syndrome (SARS) in 2002. Both of them hit a networked system and caused cascaded consequences [Bougheas and Kirman, 2015]. Although initial efforts have been made using network theory to understand fundamental problems [Van Vlasselaer et al., 2013], there is little work on risk assessment in guarantee loan networks except for the preliminary work [Meng et al., 2017; Niu et al., 2018].

3 Loan Risk Assessment Methods

3.1 ProblemDefinition

We first present the preliminary concepts and definitions and then introduce the main problem in this paper.

Definition 3.1: Guarantee Network. A guarantee network (GN) is a directed graph G = (V,E), where V = {v1, v2, · · · , vm} is a set of vertices and each vertex denotes an SME, and E = {e1, e2, · · · , en} is a set of guarantee relationships (edges).

Definition 3.2: Loan Default(Delinquency) Event. A loan default event in this paper refers to an SME's delinquency of overdue repayments.

We now formalize our risk prediction problem using highorder graph attention representations as follows:

Given a set of loan and repayment records, guarantee networks G = (V,E), for each SME, this paper aims to present them in a low-dimensional space Rd . We want to infer the possibility of loan default events based on learned low-dimensional representations and loan features. The objective is to achieve a high accuracy of default prediction as well as to explore the risk patterns of guaranteed loans.

3.2 Graph Attentional Layer

Following Velickovic's work [Velickovic et al., 2018], we introduce graph attention layer in HGAR - an attention layer in neural networks that learns higher-level representations. Specifically, for a given network, we denote the latent embedding of node vi as ⃗ui and the attentional embeddings as ⃗ u′ i .

The input of the graph attention layer is the latent embeddings of nodes, u = {⃗u1, ⃗u2, · · · , ⃗uN}, ⃗ui ∈ RF , where N is the number of nodes and F is the dimension of latent embeddings. The layer outputs attentional features, u′ = {⃗ u′ 1, ⃗ u′ 2, · · · , ⃗ u′N}, ⃗ u′ i ∈ RF ′ .

Particularly, we apply a shared linear transformation in an initial step in order to transform the input features into highlevel representation. Each node is multiplied by a weighted matrix, W ∈ RF ′×F , and then a shared attentional mechanism φ : (RF ′ ,RF ′ ) → R is applied on top of it. The attention coefficients indicate the importance of node vj's feature to node vi, denoted as:

Normally, the model involves all vertices in the graph, which implies for each node, we need to update its attention weights on every other node. In this paper, we inject the graph structure by only computing ei,j for nodes vj ∈ Ni, where Ni are the n-th order neighborhoods. We then normalize ei,j across all choices of vj by using the softmax function:

By obtaining the normalized attention coefficients, which are parameters of a single-layer feed-forward neural network, we utilize them to compute the linear combination of the latent embeddings. Therefore, we reach the output feature as:

In order to stabilize the learning process of self-attention, we employ multi-head attention to the final layer of the network. K independent attention mechanisms execute as Equation 3. Their features are then aggregated, resulting in the following output feature representation:

3.3 High-order EmbeddingMethods

For given nodes vi and vj, if vi provides a guarantee to node vj, we perform an edge from vi to vj, indicating first-order neighborhoods, and we denote its adjacency as Ai,j. Consequently, we define the distance between vertex vi and vertex vj as ri,j = ∑l Ali,j , where l is the adjacent order index.

For each pair of vertices vi and vj, which connects in the first-order, we define its joint probability distribution as:

where ⃗ u′ i ∈ Rd is the attentional vector representation of vertex vi in low-dimensional space, and ̂ p1(·, ·) is a distribution on space V × V . Then, we define the empirical distribution of ̂ p1 as:

The low-dimensional vector representation of vertices is optimized by minimizing the distance between the above two distributions: O1 = d(̂ p1(·, ·), p1(·, ·)), where d(·, ·) denotes the distance between p1 and ̂ p1.

We apply the widely used KL-divergence as the measure of distance between two distributions[Kompass, 2007]. Then, we get the distance as below:

After omitting some constants, we reach the object function as:

In high-order estimation, we assume that vertices which have the same connections or similar structure are closer in learned feature space. This means each vertex is considered as both a vertex and a "context" of other vertices in the network. Specifically, we denote ̂ u′ i as the attentional representation of a vertex and introduce ̂ u′′ i as the learned features when vertex i is considered as the "context" of the other vertex. Thus, for each pair of vertices (vi, vj), given vi, the conditional probability is expressed as:

where |V | is the number of vertices which share neighbors with vi.

Also, we preserved network structure features between vertex vi and vj in the objective function. particularly, 1) the numbers of its guarantors; 2) the number of shared neighborhoods. Then, the probability between vi and vj is denoted as:

where ∑k∈cus ri,k is the collection of nodes that share the same neighborhoods with vertex vi.

In order to preserve network structure information in a learned representation, we bring ρ(i, j) in Eq. 10, which is designed to describe the similarity of neighborhood information between vertex vi and vj. It is defined as follows:

where λ is the penalty parameter to adjust the importance of the network structure in the empirical probability distribution.

We then learn the low-dimensional representation of each vertex vi by minimizing the distance between the empirical conditional probability ̂ p(·|vi) and estimated conditional probability p(·|vi):

where ωi denotes the number of the vertex vi's neighbors in networks. Same as the first-order estimation, we employ the KL-divergence as distance measures in Eq. 12. After simplifying the formation, we reach the object function as:

During training process, we include both of the first-order and high-order attentional representation. Afterwards, we concatenate the two estimated vectors as the final network low-dimensional representation in the downstream default prediction task.

3.4 Loan Default Prediction Layer

This paper aims to predict loan default events. After obtaining the representation of guarantee networks, we apply this to the prediction layer and the loss function is defined as:

where u′i denotes the representation of the ith node (SME), which is the output of the attention layer, si denotes the loan features, and yi denotes the label of the ith node, which is set to 1 if the loan defaults and 0 otherwise. predict(u′i , si) is a prediction function that maps u′i and si to a real valued score, indicating the probability of whether the company will default in the current time window. We implement predict(, : θ) with another shallow neural network (two-layer Relu and one-layer sigmoid).

We extract loan features si from the user's loan dynamic behavior. This includes: 1) active loan behavior, e.g., default status, loan type, loan amount, historical loan times, historical loan amounts, etc. They are calculated in the current time window; 2) historical behavior describes the accumulated features of a user's loan behavior, such as total loan amount, loan times and default times; 3) the user profile contains company type, registered capital, number of employees, enterprise scale, etc. Most banks require a company to supply this basic information when the enterprise makes a loan application, and we use the latest version of the user profile.

3.5 Complexity Analysis

The calculation of objective function in Eq. 13 involves all vertices in the network, which requires the summation over all vertices when calculating the conditional probability p(vj|vi). This is computationally inefficient, especially for large-scale networks. To address this problem, we employ the negative sampling approach, which samples multiple negative edges according to some noisy distribution for each edge ei,j .

Specifically, sampling on a sequence of edges requires O(|E|) time, where |E| denotes the number of edges. During implementation, we draw a sample of edges by using the alias table method[Li et al., 2014], which takes only O(1) time. Afterwards, the negative sampling approach in the optimization process takes O(d(T+1)) time, where T is the number of negative samples. Therefore, it takes O(dT) time in each step in total. As the number of steps is proportional to the number of edges and feature dimensions, we reach the overall time complexity of HGAR as O(dTF|E|). This demonstrates the complexity of our proposed method is linear to the number of edges, which does not depend on the number of vertices.

Meanwhile, the edge sampling method also speeds up the computation of the stochastic gradient descent process. In our implementation, we apply the Adam optimizer to update parameters. The initial learning rate is set to 0.0001, and the batch size is set to 128 by default.

4 Experiments

In this section, we conduct extensive experiments to evaluate the effectiveness and efficiency of our proposed methods. We first describe the experimental settings. Then, we give the experiment results of delinquent prediction compared with other baselines. After that, the effects of the attentional layer and high-order embeddings are tested respectively. Finally, we provide the parameter sensitivity and scalability evaluation of the methods.

4.1 Experimental Settings

We evaluate our method on the data from a major commercial bank in Asia, between 01/01/2013 and 31/12/2016. This includes 112872 nodes (companies), with 124957 edges (guarantee relationships). We found that most of the loans are repaid monthly. Hence, we aggregate the behavior feature with a one-month time window and mark the delinquency loans as the target label in the month.

Compared Methods

We use eight state-of-the-art methods to highlight the effectiveness of HGAR. These are: Graph Factorization (GF) [Ahmed et al., 2013], DeepWalk [Perozzi et al., 2014], LINE [Tang et al., 2015], node2vec [Grover and Leskovec, 2016], MNDF [Wang et al., 2017], AANE [Huang et al., 2017], SNE [Liao et al., 2018] and GATs [Velickovic et al., 2018]. We also construct sub-modules of our proposed model in comparison: HGAR-noatt/noho/nolf, in which attention layer/highorder/loan features are not used. For LoanFeature, we only utilize loan features in the prediction task.

We set the network embedding dimensions to 64, combining loan features (64) with 128 dimensional vectors in the experiments. The parameters of the methods compared are set to their default values. For our method, we set λ = 1 and l = 3 since we often reach stable results with these. We apply the prediction layer for all methods and evaluate the performance by AUC (Area Under the Curve) and Precision@k. Precision@k means the prediction precision of the top k nodes, formulated as:

where Vp is the set of predicted top k defaulted nodes, Vo is the set of observed default nodes and | · | represents the size of the set.

4.2 Loan Default Prediction

We evaluate the performance of different models for the default prediction task. Records from the year 2012 are used as training data, and then we predict defaults of the next three years in months. We report the average AUC in Table 1.

The first 9 rows of Table 1 report the results only of loan features and some state-of-the-art baselines. As we can see, eight baselines, which add network embeddings, outperform LoanFeature, showing improvements of at least 15%, demonstrating the effectiveness of adding guarantee network topology information in loan delinquency prediction. Of all the baselines, GATs and SNE are shown to be the most competitive. Rows 10-12 show the results of HGAR and some of its sub-models. The performance of HGAR-noho is similar to SNE. HGAR-noho and HGAR-noatt perform better than the baselines and LoanFeature, and the binary role properties prove to be effective when the guarantor and guarantee are treated differently in the embedding methods. The results of HGAR-all are significantly better than the sub-model methods, proving that high-order and attention layers could improve the model's performance. Moreover, compared with other baselines, the improvement in results using HGAR-all is especially noticeable.

4.3 Effects of Attentional High-order Models

In this experiment, we report the precision of the top k nodes in delinquent prediction. In order to prove the effects of each module on the proposed methods, we experimented on the benchmark dataset with LoanFeature, HGAR-nolf, HGARnoho, HGAR-noatt, and HGAR-all. Figure 1 shows the precision@k of default prediction with different k. The performance of HGAR-noho is similar to HGAR-noatt, and both are much better than HGAR-nolf and LoanFeature, showing the necessity of integrating topological and loan behavior features. HGAR-all performs much better than the four other baselines. The experimental results demonstrate the effectiveness of our proposed methods in loan risk assessment and default prediction.

4.4 Deployment and Case Studies

In HGAR, the attention layer is used to determine the importance of nodes during embedding within a certain time window. Figure 2 visualizes the attention weights of nodes in sampled time windows. We observe that a node with around 4 adjacent nodes is generally the most important since the colors of its heat distribution are brighter overall.

In order to validate the above observation, we employ an empirical study on a typical graph that is coded as GN75, which includes 112 nodes and 126 edges. We apply the KMeans algorithm on the learned embeddings of HGAR, as presented in Figure 3 (b). For comparison, we utilize random walk [Pons and Latapy, 2005] as the baseline for community detection, as presented in Figure 3 (a). It is clear that the results of random walk could only separate community equivalence. Our proposed method preserves better structure information in the learned embeddings, and the nodes with high attentions are clustered together, colored as blue and lilac. These companies show medium scale input, no output, star structures. This is because companies facing default need guarantors, but cannot gain many of them so as to form a normal star structure and do not have the ability to guarantee other companies. This phenomenon is also reported in [Meng et al., 2017], which proves the observation from the attention layer visualization.

We further investigate the attention selected high default patterns during the deployment period. Specifically, we apply motif detection from high attention nodes for risk pattern discovery: (1) we employ the gtrieScanner approach [Ribeiro and Silva, 2012] on around 4 nodes motif detection, as nodes with around 4 neighbors are highlighted in Figure 2. (2) We match the motifs with the entire network and calculate the ratio for default firms as shown in Figure 4. (3) We rank detected patterns in descending default order, and mark the top n of them as high default pattern candidates. It is computationally expensive to detect all those motifs in the whole network, so we start from motifs of 4 vertices.

We select a typical graph coded as GN32, which consists of 103 enterprises; 36% of them default on 85% loans from the bank. Figure 5 shows the risky pattern candidates detected from GN32. As can be seen, although there are nearly 199 kinds of 4-vertex motif shapes theoretically, only 12 of them are discovered as high default pattern candidates. The structures of them are normally complex. It should be noted that some of these motifs are well known by domain experts. Taking motif 16 for example, it is a joint liability loan and motif 5 is a combination of a joint liability guarantee loan with a single guarantee. The top five risk motifs show single input, single output, feed forward structures.

Our method is deployed in the loan management system.

Figure 4 presents the system interface and main components. During the observation time window, it successfully warns 76% of true positive ratio of all risky loans with an acceptable 26% false positive rate, involving 2538 SMEs and 7006 guarantors. It is worth noting that these risky loans failed to be discovered by conventional scorecard based risk control system.

5 Conclusions

In the loan risk assessment systems, an company's basic profile may not be completely accurate (it may be out of date or even include fake data), but the guarantee network provides a new dimension for loan risk assessment, which is more trustworthy. Thus, in this paper, we present a novel loan risk prediction system using high-order graph attention representations. In particular, it contains three characteristics: 1) binary roles of nodes; 2) high-order adjacent approximation; 3) attentional layer selection. Extensive experiments demonstrate that our proposed methods are better than eight other stateof-the-art baseline methods. By observing gradual changes of attention weights after deployment, we discover risk guarantee patterns, which have been employed by bank's internal risk managers to monitor possible delinquent companies and to curb systemic loan crises.

Acknowledgments

The work was supported by the National Basic Research Program of China (2015CB856004), the Key Basic Research Program of Shanghai Science and Technology Commission, China (15JC1400103, 16JC1402800), and China Postdoctoral Science Foundation.