Triangle Graph Interest Network for Click-through
Rate Prediction

Extracting triangles is a time-consuming process, especially for large-scale graph data. However, as a real-time task, CTR prediction has a high demand for efficiency. Empirically, for a specific item, the triangles near to it have a stronger influence. Hence, in our paper, triangles are extracted only from small-scale neighborhood of each item. Take the 0-order triangle as an example, for each node in the co-occurrence graph, we sample all its 1-order neighbors. Then we check if each pair of neighbor nodes can form a triangle with the specific item. That is, it is necessary to judge whether there is an edge between each pair. We solve it by constructing a Hashmap for edges, which can limit the time complexity to $\mathcal{O}$(1). But it requires high storage capacity and encounters an obstacle when handling billions of edges. Thus, we use Bloom Filters (Broder and Mitzenmacher, 2004) to alleviate this problem. We can produce all the 1-order triangles after deduplication. Based on this, triangles of any order can be obtained in a similar way.

Inspired by (Chen et al., 2018), we adopt Determinantal Point Processes (DPP) to model the selection probability of a relevant yet diverse set of triangles. Specifically, a DPP on the triangle set $\mathcal{T}$ is a probability distribution on the powerset of $\mathcal{T}$. If it assigns non-zero probability to the empty set $\emptyset$, there exists a positive semi-definite kernel matrix $\mathbf{L}\in\mathbb{R}^{N\times N}$, such that for each subset of $\mathcal{S}\subseteq\mathcal{T}$, the probability of $\mathcal{S}$ is defined as follows:

where $\mathbf{L}_{\mathcal{S}}$ is $\mathbf{L}$ restricted to those rows and columns which are indexed by $\mathcal{S}$, and $\mathbf{I}$ is the identity matrix.

As revealed in (Chen et al., 2018), the kernel matrix $\mathbf{L}$ can be written as a Gram matrix $\mathbf{L}=\mathbf{TT}^{\top}$. The rows of $\mathbf{T}$ are vectors representing the feature of triangles. Each row vector $\mathbf{T}_{i}$ are empirically constructed as the product of the triangle relevance score $r_{i}$ and the triangle feature vector $\mathbf{x}_{i}\in\mathbb{R}^{1\times d}$, i.e., $\mathbf{T}_{i}=$ $r_{i}\mathbf{x}_{i}$. Hence, an element of $\mathbf{L}$ is written as $\mathbf{L}_{ij}=\mathbf{T}_{i}\mathbf{T}_{j}^{\top}=r_{i}r_{j}\mathbf{x}_{i}\mathbf{x}_{j}^{\top}$. Moreover, if the feature vector $\mathbf{x}_{i}$ is normalized, the cosine similarity between two triangles can be calculated as $\mathbf{C}_{ij}=\mathbf{x}_{i}\mathbf{x}_{j}^{\top}$. Hence, $\mathbf{L}$ can be re-written as follows:

where $\mathbf{C}$ is the triangle similarity matrix, and $\operatorname{Diag}\{\mathbf{r}\}$ is a diagonal matrix with the $i^{th}$ element being $r_{i}$. Following (Chen et al., 2018), we modify the DPP kernel matrix as follows:

where $\alpha=\theta/(2(1-\theta))$ and $\theta\in(0,1)$. $\theta$ is a hyper-parameter used to trade-off between relevance and diversity.

In practice, we calculate the triangle feature vector by averaging the features of three nodes within it. As to the triangle relevance score, we introduce the inner weight and the outer weight of the triangle. The inner weight is the average weight of its three edges. For the outer weight, we set the denominator as the sum of the distances from three inner nodes to the central node, and set the numerator as the sum of the edge weights connecting three inner nodes and the central node. Based on this, the triangle relevance score is the arithmetic square root of the product of the inner and outer weights. After the DPP kernel $\mathbf{L}$ is determined, the inference algorithm (Chen et al., 2018) is applied to find the optimal diverse while relevant triangle set for the recommendation.

We adopt both public and industrial datasets. The statistics of all datasets are shown in Table 2:

• •

  Public dataset: Following the setting of (Zhou et al., 2019), we use two subsets of Amazon dataset (McAuley et al., 2015): Books and Electronics. For these two datasets, we regard the reviews as the user behaviors and sort the reviews from each user by the time order. Based on user historical behaviors, our purpose is to predict whether a user will write a review.

• •

  Industrial dataset: We collect the click logs for 30 days from Alibaba online display advertising system. A sample instance consists of the candidate item, user, context and its historical behaviors. The items that user clicked in the previous 29 days contribute to user sequential behaviors. Our goal is to predict whether the user clicks at the candidate item on the last day.

We compare TGIN with the following state-of-the-art approaches:

• •

  Wide&Deep (Cheng et al., 2016) consists of two parts: its deep model is the same as Base Model, and its wide model is a linear model.

• •

  PNN (Qu et al., 2016) uses a product layer to capture interactive patterns between interfield categories.

• •

  DIN (Zhou et al., 2018b) uses the embedding product attention mechanism to learn the adaptive representation of user behaviors w.r.t. the target item.

• •

  GIN (Li et al., 2019) is the first to mine and aggregate the user’s latent intention on the co-occurrence item graph with graph attention technique.

• •

  DIEN (Zhou et al., 2019) designs an auxiliary network to capture user’s temporal interests and proposes AUGRU to model the interest evolution.

• •

  MIMN (Pi et al., 2019) is a multi-channel memory network to capture user interests from long sequential behaviors.

• •

  DMIN (Xiao et al., 2020) models latent multiple user interests from user behavior sequences to improve the CTR task.

As introduced in Section 2, the item-item co-occurrence graph is constructed with a sliding window. To prevent information leakage, graph construction is only based on the train set for each dataset. The window size is set as 3 to avoid too extensive connections in the graphs. In our experiment, the dimension of the item and user embedding is set as 18, and the size of position embedding is set as 2. The learning rate is 0.001 and the batch size is 128. The maximum order of triangles is 2. The lengths of user behavior sequences vary in different datasets. Therefore, we set the maximum length to 10, 20, 15 for the Books dataset, the Electronics dataset, and the industrial dataset respectively. The evaluation metrics is Area Under the Curve (AUC). To ensure the fairness of comparison experiments, we reuse the metrics already reported in original papers or choose optimal hyper-parameters carefully after reproducing the code for different baselines.

The results on the public datasets are shown in Table 3. Compared with the benchmark algorithm, our proposed model achieves the highest AUC scores on both two datasets. Among all baselines, compared with traditional methods, Wide & Deep and PNN, DIN and other models can achieve higher AUC scores obviously by capturing user interests. GIN outperforms DIN, demonstrating that introducing the item-item co-occurrence graph can alleviate the behavior sparsity problem. Due to longer user behavior sequences in the Books dataset, MIMN performs better on this dataset than on the Electronic dataset. DIEN uses a specially designed AUGRU, thus, it is better at modeling the interest evolving process. As to DMIN, its advantages benefit from capturing multiple interests. Markedly, the auxiliary loss can bring a large improvement to all of DIEN, DMIN and our method. It is worth mentioning that our method can outperform all baselines even without the auxiliary loss. We own it to resolving the problems of elusive motivation and diversity restriction effectively.

We further conduct the experiments on the industrial dataset of display advertisement. The results are shown in Table 4. Different from only one category of goods in the public Amazon dataset, our industrial dataset contains various types of items. Thus, it is much more challenging and complex. DIN and DIEN use the attention mechanism to capture the relevance of items, significantly improving performance. Furthermore, when compared to GIN, DIEN, and MIMN, our proposed model outperformed them all. Even when compared to DMIN, which performs the best on this dataset, TGIN achieves a 0.004 absolute AUC gain. It is notable that in commercial advertising systems with hundreds of millions of traffics, 0.004 absolute AUC gain is significant and worthy of model deployment empirically. TGIN shows great superiority to better understand and make use of the characteristics of user behavior data.

We test several variations of our full model, including BaseModel (MeanAgg), BaseModel (WeightAgg), BaseModel (AttentionAgg), BaseModel + AuxLoss. BaseModel is the base model to uses a set of triangles in the item-item co-occurrence graph to model every user behavior. There are three strategies to aggregate triangle information and click behaviors for each user, including MeanAgg, WeightAgg and AttentionAgg. They represent the average pooling, the weighted pooling and the attention pooling, respectively. BaseModel + AuxLoss denotes the base model with the best pooling operation and the auxiliary loss. All of these variations adopt the weight-based strategy to sample triangles. And TGIN is our full model, which samples relevant and diverse triangles as introduced in Section 4.2.

Figure 4 shows the results of different variations of our full model on the public datasets. When compared to DIN in Table 3, all triangle-based models achieve a clear advantage on the Books and Electronics datasets. We own it to the effectiveness of modeling triangles as the basic units of user interests. It makes a great contribution to capturing implicit user interests. Considering different aggregation strategies, we find that the best choices for these two datasets are different: the attention pooling is better for Books while the weighted pooling is suitable for Electronics. We speculate that the reason is that the user behavior of the Electronic is sparser than that of Books, and complex aggregation mechanisms may cause overfitting. For all the experiments in this paper, we always choose the best aggregation strategies for each dataset. As to the auxiliary loss, it brings great improvements for both datasets. It reflects the importance of supervision information for the learning of sequential interests. However, the improvement on Electronics is not as obvious as that on Books. The difference may derive from the longer user behavior sequences in the Books dataset.

Now we examine the influence of two key parameters in our framework: the number of triangles $n$ and the parameter $\theta$ in triangle selection. The results on two public datasets are shown in Figure 5. We can find that when the number of triangles increases from 1 to 10, our model can achieve better results on two datasets simultaneously. Because more triangles can provide more clues about user interests. However, in practice, we set $n$ as 10 to balance efficiency and effectiveness. We set the parameter $\theta$ for a trade-off between relevance and diversity when choosing triangles. As shown in the right of Figure 5, it has a little effect on the Electronics dataset while the Books dataset benefits from a higher $\theta$. We assume that the item features in these two datasets are very sparse, which may have a negative impact on triangle selection.

To verify whether a variety of triangles can bring more novel items, we analyzed different item sampling methods, including weight-based node sampling in GIN, weight-based triangle sampling in TGIN, and diversity-based triangle sampling in TGIN (in Section 4.2). For the fairness of comparison, we use different methods to sample the same number of items on the industrial dataset, and then, count the number of keywords involved in these items. The more different keywords, the more diverse items. The experimental results are shown in Figure 6. We can find that the items sampled by GIN are relatively homologous. Because GIN is bias to popular or similar items. In contrast, by introducing triangle structures, weight-based sampling in GIN can improve diversity to a certain extent. In our full model, we try to select diverse and relevant triangles. In this way, higher diversity can be achieved with fewer items. Inspired by this, we improve the model efficiency by reducing the number of sampled triangles.

The calculation time of TGIN is compared with other popular sequential models, including DIN, GIN, MIMN, DIEN, DMIN. We recorded the training time of these models per epoch on the Books dataset with 1 NVIDIA Tesla P100 GPU. For TGIN, we extracted and selected triangles through preprocessing. The order of triangles is fixed to 2. The number of triangles is set as 5. For other methods, we directly run their released codes or reproduce their results. The experimental results show that the efficiency of TGIN is comparable to, if not better than, that of these baselines. Specifically, DIN costs 367 seconds, TGIN 430s, GIN 457s, DMIN 1,309s, DIEN 1,354s, and MIMN 7,954s per epoch. GIN and TGIN are slower than DIN because they introduce item-item co-occurrence graphs as an auxiliary for broader exploration. When compared with other baselines, TGIN shows a distinct advantage by modeling a few and diverse triangles. For online deployment, we optimized every component for our algorithm and finally obtain quick responses to user clicks for online advertising. More details are described in the next section.

From April 10 to April 17 in 2021, careful online A/B testing was conducted in the merchant advertising system of AliExpress (one of the biggest global e-commerce platform). During almost a week’s testing, TGIN has improved UV L-P by 3.62% and L-GMV by 3.16% compared to the base model. Besides, TGIN has improved commission earn per user (EPU) by 3.20%. This is a significant improvement and demonstrates the effectiveness of TGIN. Now, as showed in Figure 7, TGIN has been deployed online and serves the merchant traffic, which contributes a significant business revenue growth.

In practice, we employ the TPP platform to handle real-time user requests. ABFS (Ali Basic Feature Service) is used to obtain real-time behaviors and user portraits. Then we obtain the recall candidates via BE (Basic Engine). In the following step, item attribute information and the corresponding triangle index is requested via iGraph (GRAPH ENGINE). Finally, we calculate the CTR score through the TGIN model service deployed by RTP (REAL-TIME PREDICTION) and recommend items to users for online display. The average response time is about 30 milliseconds, which is sufficient to meet the timeliness requirement of the CTR prediction task. Meantime, the user behavior log is returned to ABFS through FLINK real-time data. In particular, all the triangle indexes are established offline. Firstly, a large-scale item-item co-occurrence graph is built for AliExpress. The triangle extraction and selection algorithm is implemented using Alibaba MaxCompute and MapReduce. To improve the efficiency, we restrict the number of triangles strictly.