AdsGNN: Behavior-Graph Augmented Relevance Modeling in Sponsored Search

Sponsored search ads appear next to search results when people look for products and services on search engines. In recent years, they have become one of the most lucrative channels for marketing. As the fundamental basis of search ads, relevance modeling has attracted increasing attention due to the significant research challenges and tremendous practical value. Most existing approaches solely rely on the semantic information in the input query-ad pair, while the pure semantic information in the short ads data is not sufficient to fully identify user's search intents. Our motivation lies in incorporating the tremendous amount of unsupervised user behavior data from the historical search logs as the complementary graph to facilitate relevance modeling. In this paper, we extensively investigate how to naturally fuse the semantic textual information with the user behavior graph, and further propose three novel AdsGNN models to aggregate topological neighborhood from the perspectives of nodes, edges and tokens. Furthermore, two critical but rarely investigated problems, domain-specific pre-training and long-tail ads matching, are studied thoroughly. Empirically, we evaluate the AdsGNN models over the large industry dataset, and the experimental results of online/offline tests consistently demonstrate the superiority of our proposal.

INTRODUCTION
Search engine advertising has become a significant element of the web browsing due to the outburst of search demands. Choosing the right ads for a query and the order in which they are displayed greatly affects the probability that a user will see and click on each ad [22]. As the fundamental component of sponsored search systems, the relevance model measures the semantic closeness between an input query and a candidate ad, which is capable of improving the user experience and driving revenue for the advertisers.
Existing relevance models usually capture the semantic correlations inside the query-ad pairs with powerful Natural Language Understanding (NLU) models, which has been a key research field with many breakthroughs over the last years. Deep Structured Semantic Model (DSSM) [21,28] is one of the first powerful solutions to encode text data into latent distributed vectors. With the development of NLU, transformers [32] and BERT [3,23] are both the emerging pre-trained language models with far superior performance, which surpass previous approaches and can even approach the human level. Pre-trained models can capture the contextual information in the sentences and generate high-quality language representations, leading to the promising performance.
However, directly applying such NLU approaches to the relevance modeling scenario may not be desirable as the pure semantic information in the ads data is not sufficient to fully identify the user search intents. The queries and ads are quite short (e.g., less than 4 words on average from Bing's log) compared with the long text (e.g., sentences and documents) used in the traditional NLU tasks, and thus the performance is hindered by the scarce semantic information in the input short texts. Manually labeled queryad pairs can provide more linguistic guidance for better understanding the latent search intents, but they are quite expensive and time-consuming. Besides, although existing models have demonstrated satisfying results in matching common queries with popular ads, they usually achieve undesirable performance on the longtail queries/ads [39], which is potentially caused by under-training due to naturally scarce data on these low-frequency examples.
Existing NLU-based relevance models mainly focus on implicit feature engineering solely from the input textual data. Structural complexities of new relevance models grow exponentially but the performance improvement is relatively marginal. Therefore, in order to significantly improve the relevance performance, employing new and accessible data with supplementary information is a more practical and favorable approach. A natural and easily accessible data source that provides information beyond semantic text in the search engine system is users' historical click behaviors. Our motivation lies in exploring this cheap and massive click data as complementary for relevance modeling. For example, given a short query " 1", it is intractable for NLU models to understand the actual meanings correctly. But in the user behavior data, its historical clicked ads include " 1" and " 1 ℎ ". With this complementary information, the input query can be easily comprehended as a sub-brand of Nike shoes, which will facilitate the downstream relevance modeling task.
A straightforward strategy is to employ click relations as a surrogate of relevance annotations. Namely, the clicked query-ad pair is viewed as positive, and negative pairs are synthesized by fixing a query while randomly sampling its un-clicked ads. This strategy confuses the relevance correlations with the click relations and thus may introduce ambiguities from two aspects. Firstly, the arbitrariness and subjectivity of user behavior lead to the misalignment between user clicks and true relevance annotations [20], which may introduce noises into the ground truth and further pollute the training set. Secondly, negative pairs sampled by data synthesizing usually share no common tokens for queries and ads, which may mislead the relevance model to view common terms as critical evidence of relevance. However, lexically similar query and ad may have totally different intents such as "iPad" and "iPad charger".
Here we extensively study how to naturally incorporate the user behaviors in the format of graphs without introducing the mentioned ambiguities. Queries and ads are connected by click relations, based on which a bipartite behavior graph can be built easily from the search logs. Over the recent years, Graph Neural Network (GNN) [10,33] and the variants are widely applied on graph structural data with promising performance on many downstream applications (e.g., node and graph classifications). Inspired by GNN, we attempt to properly integrate the abundant behavior graph data into the traditional semantic model. In most GNN models, the node textual features are pre-existed and fixed in the training phase. In contrast, we make the semantic and graph models work in conjunction with each other, which contributes to generating more comprehensive representations for deeper intent understanding.
In this paper, we propose the AdsGNN models that naturally extend the powerful text understanding model with the complementary graph information from user historical behaviors which serves as a powerful guide to help us better understanding the latent search intents. Firstly, three variations are proposed to effectively fuse the semantic textual information and user behavior graph from the perspectives of nodes, edges and tokens. Specifically, the node-level AdsGNN views the queries and ads as separated entities, then aggregates the neighborhood information from the click graph to facilitate the learning of entity representations. Edge-level AdsGNN treats the input query-ad pair as a unit and directly learns the edge representations by aggregating the local topological information. Token-level AdsGNN regards the input token as processing units and fuses the graph information to learn behavior-enhanced token representations, which is a deeper tightlycoupled integration approach compared with previous two variations. After that, in order to take full advantage of user behaviors, we propose to pre-train the AdsGNN model on the behavior graph with two graph-based pre-training objectives. Finally, as the long-tail queries/ads are usually associated with limited click signals, we propose to learn a knowledge distillation model to directly learn the mapping from the pure semantic space to the behaviorenhanced embedding space, which empowers our proposal with powerful topological predictive ability to handle the long-tail entities. Empirically, AdsGNNs are evaluated over the large industry dataset and yield gains over state-of-the-art baselines with regards to the different parameter settings, which demonstrates the superiority of our proposal.
We summarize our main contributions as follows.
• We incorporate the unsupervised user behavior graph as complementary to enrich the semantic information in the input query-ad pairs and propose three novel AdsGNN models to effectively fuse textual data and behavior graph from different perspectives. • A novel knowledge distillation based framework is proposed to alleviate the formidable but less explored challenge of long-tail ad matching. • Extensively, we evaluate our proposal on the large industry dataset. Experimental results demonstrate the superior performance of the proposed AdsGNN models.

PROBLEM DEFINITION
In this section, we will formally define the studied problem. Different from existing approaches solely based on the semantic data, here we further exploit the unsupervised user behavior data from the search log as complementary. The behavior graph is defined as a bipartite graph: G = {Q, A, E}, in which Q and A denote the set of queries and ads, respectively. E ∈ N |Q|× |A| is the adjacency matrix, which includes the click signals between queries and ads. The ground truth of relevance modeling task is defined as a set of triples: L = {< , , >}, where denotes the input query, denotes the ad and ∈ {0, 1} represents the relevance label between and . We aim to learn a classifier f : f ( , ) ∈ {0, 1} by fusing the ground truth L and the click graph G.

METHODOLOGY 3.1 AdsGNN for Node-level Aggregation
Denote and as the input query and ad, respectively. Figure  1(a) shows the motivation of the node-level aggregation model AdsGNN . Given the input (green pentagram), its neighbors in the behavior graph are the ads (orange circles) that users tend to q a (a) The illustration of AdsGNN in the behavior graph. q a q n 1 q n 2 a n 1 a n 2 a n 3  click. The dotted lines represent message-passing directions. Considering the scarce semantic information in the short input text, fusing the behavior neighborhood contributes to correctly understanding the user's search intents. The architecture of the AdsGNN model is illustrated in Figure  1(b). is the -th graph neighbor (ad) of the input query , and is the -th graph neighbor (query) of the input ad . The proposed model is a natural extension of the high performance two-tower models (e.g., C-DSSM [5] and TwinBERT [23]) with additional information from graph structural data. As there exist millions of candidate ads, it is infeasible to use a sophisticated text encoder to compute the similarity between a search query and each ad one-byone [23]. Hence, the twin-tower structure is a good choice for online serving as we could pre-compute the ad representations in advance. When a query comes, we can easily generate its embedding and calculate the similarities between the input query embedding and cached ad representations. From the bottom up, AdsGNN model includes the following three layers: Node Encoder. Node encoder embeds the textual information of input entities into the low-dimensional latent vectors, which can be implemented as any layer-wise text encoding models. For example, as shown in Figure 1(b), BERT is selected as the node encoder. The input text is first tokenized by the WordPiece [35] tokenizer. For each token within the input sequence, the initial embedding is acquired with the summation of its token embedding and positional embedding before it goes through three transformer encoder layers. After the node encoder layer, we can get a sequence of vectors corresponding to the tokens in the sentence. The vectors are then combined using a weighted-average pooling layer following TwinBERT model. Considering the topology context of queries and ads are quite different (e.g., the number of a query's neighbors is usually larger than the one of an ad), we design two node encoders with different parameter sets marked with different colors. Encoders with the same color are set to share the same parameters. Node Aggregator. The output vectors of the node encoders are fed into the node aggregator to perform neighborhood fusion. A desirable node aggregator should be able to collect valuable information from the behavior neighborhood, then fuse these messages with the center node to learn high-quality contextual representations. Considering the importance of different neighbors differ greatly in depicting the local context, we employ the self-attention strategy used in Graph Attention Network (GAT) [33] to learn the neighbor weights properly and then weighted combine the contextual semantic information. The attention score between the input query and its neighbor is calculated as follows: in which || is the concatenation operation, a is the local-level attention vector for the neighbors and is activation function to introduce nonlinear transformation. denotes the number of neighbors. h and h are the embeddings learned by node encoder of and , respectively. The learned attention score denotes how important neighbor will be for the center node . Then the contextual embedding z can be achieved by aggregating the neighbor's encoded features with the corresponding coefficients: This contextual embedding is then connected with the direct output of the query encoder through the concatenation, similar to the idea of Residual Connection Network [11]: Note that, query and ad aggregators are implemented with different parameter sets following the bipartite nature of the behavior graph.
Matching Layer. The topology-augmented query representation is interacted with ad-side output in the matching layer to get the final classification outputs. Here we implement the matching layer as a multi-layer perceptron (MLP) with one-hidden layer following previous works [19,23,39]. AdsGNN first learns the semantic embedding of each input text, and then combine them together following the guidance of user historical behaviors. The aggregation is processed in the nodelevel in the GNN style, which is expected to provide additional information beyond the traditional semantic texts.

AdsGNN for Edge-level Aggregation
The proposed AdsGNN model aggregates the neighborhood information on the node-level, in which input queries and ads are processed separately. However, the studied relevance matching problem focuses on the correlations inside the query-ad pair instead of a single query or ad. Handling the query-ad pair as a whole can capture and exploit the information from both sides, while the  First-order aggregator < q, a > < q, a n i > < a, q n i > < a, a n i > < q, q n i > Second-order aggregator  node-based model can only utilize the data from one side. Queryad pairs can be naturally viewed as the edges in the behavior graph, and thus we propose AdsGNN for the edge-level aggregation.
In order to embed the topological context into edges as much as possible, we design the following three types of edges as shown in Figure 2(a): • Input Edge denotes the relevance relation between the input query and ad , and most existing works are solely based on this connection. • First-order Edge captures the click relations between the center node and its neighbors in the behavior graph. The insight lies in the homophily [17,31] among the connected edges. Given the input query , its neighbor and the input ad can be viewed as the co-clicked items, and thus these two adjacent edges < , > and < , > tend to share similar search intents. Thus, the first-order edge can capture the local context of the input edge as the complementary. • Second-order Edge encodes the semantic relations between the input query (ad) and the neighbors of the input ad (query) (e.g., < , > and < , >). Our motivation is that if two ads are both clicked given the same query, they have a larger chance to be similar. Second-order edges are capable of capturing the semantic information from high-order neighbors to enrich the inputs.
Different meaningful and complex semantic information is involved in the various types of edges, and different edges may also extract diverse semantic information. It is nontrivial to select the most meaningful edges and fuse the semantic information suitably.
Hence, we propose a novel AdsGNN model based on the hierarchical attention, including first/second-order and edge-level attentions. Specifically, the first/second-order attentions aim to learn the importance of edges in the same category, while the edge-level attention is able to learn the informativeness of different types of edges and assign proper weights to them. Figure 2(b) demonstrates the details of AdsGNN model, which includes the following four layers: Edge Encoder. Edge encoder aims to capture the textual information of the input edge along with the correlations between the associated query and ad. The text of query and ad in the input edge are concatenated with the [SEP] token to define the sentence boundary as [ , , ]. After processing with the tokenizer, a threelayer BERT is employed to learn the representation of the input edge. In the transformer layer, each token on one side (e.g., query) is able to attend tokens on the other side (e.g., ad), which captures the correlations inside query-ad pair and is intrinsically different from the AdsGNN model. Note that, we design different encoders for different types of edges to emphasize the various roles. First/Second-order Aggregator. The output vectors of the edge encoders are fed into the first/second-order aggregators based on the edge categories. The first-order aggregator is selected as an example, which is designed to learn the importance of different first-order edges. Denote the embedding of the -th first-order edge as h . Different from the node-level aggregator, these edges are position-insensitive without the definitions of center or neighbor edges. Hence, we design another format of attention as follows: in which is the number of first-order edges, w and are the trainable parameters.
represents the normalized importance of the -th edge compared with other edges. Edges belonging to the same category are aggregated according to the attention scores. Edge Aggregator. Different types of edges may have different significance, and thus we design the edge aggregator to distinguish informative edge types from less informative ones. Here we also employ the self-attention method to learn the weights of three edge types, which is similar to the attention mechanism used in the node aggregator. The input edge is viewed as the center edge and others are regards as the neighbors.
Overall, AdsGNN model can be understood as the natural extension of the traditional one-tower models (e.g., BERT), which usually achieve higher performance by considering the rich information from both sides but cannot be easily applied on the lowlatency online matching scenario.

AdsGNN for Token-level Aggregation
The previous two models first learn the embeddings of input entities based on their own textual data and then aggregate the neighbor embeddings as the final representations. Graph aggregation q a q n 1 q n 2 a n  module is built on top of the textual encoder, which forms a cascade framework. In each layer of the encoder, a token can only attend to other tokens in the belonged node but cannot refer to the tokens in other nodes, leading to a loosely-coupled structure.
Here we aim to deeply fuse the textual and topological information with a tightly-coupled structure named AdsGNN , where multiple layers of graph transformers and text transformers are alternately deployed. As shown in Figure 3, messages are passed among contextual neighbors and the center node in each node encoder layer. Hence, tokens within the center node can attend to tokens in the neighborhood, which contributes to learning the topology-aware token representations. Each input text is tokenized into a sequence of tokens by WordPiece [35]. For each tokenized sequence, a [CLS] token is padded in the front. The embedding of [CLS] token is regarded as the representation of the input text. As shown in Figure  4, the -th layer of AdsGNN on the query side is selected as an example, which includes the following two components: Graph Transformer. Graph transformer aggregates the contextual topology information, and then dispatches it to the input texts. Firstly, we define the symbol h ( ) shown in Figure 4, which represents the embedding of -th token in the -th node in the layer . Index is set to 0 for the center node and = means this is the embedding of CLS token. The CLS embeddings h ( −1) from the ( -1)-th layer can be organized into a matrix H c in which is the number of neighbors and ℎ denotes the dimension of latent embedding. Then, the graph-transformer is introduced below to exchange information among different nodes: where Graph Transformer h (l−1) 0c Text Transformer Text Transformer Text Transformer In the text transformer phase, the CLS token collects the information from other textual tokens in the belonged sentence, and then exchange them with CLS tokens in other nodes by graph transformer. This indirect message passing structure is designed to ensure model efficiency. A straight-forward approach is to directly concatenate all the tokens from the neighborhood together and feed them into the BERT model. Denote as the average length of the input text and as the number of neighbors. Each token will attend to ( × ( + 1)) tokens, which significantly enlarges the parameter space and will be seriously memory-cost and timeconsuming. However, the attended field sizes of graph transformer and text transformer are and , respectively, which ensures our proposal is capable of both aggregating neighbor tokens and maintaining model efficiency.

Objective Function
The output vector from the matching layer is denoted as y ′ ∈ R 1×2 , which contains the predicted probabilities of the input pair is relevant or not. We select the cross-entropy as the objective function:

PRE-TRAINING ON BEHAVIOR GRAPH
The text encoders used in our proposal are set to the transformers, so we can conveniently load the weights from the first three layers of the pre-trained large BERT model to get a good starting point. However, the available BERT checkpoints are pre-trained on the general text dataset, which is intrinsically different from the sponsored search scenario. The ad text is much shorter than the normal sentences, and the relevance relation between the query and ad is also different from the adjacency relationship captured by the popular Next Sentence Prediction (NSP) task [3]. Hence, we propose the following two objective functions to adapt the general pre-trained checkpoints to the unsupervised user behavior graph as the domain-specific warm up. The first task is the neighbor-enhanced masked language modeling (NE-MLM), which aims to exploit the topological neighbors to predict the masked tokens. We first randomly select a set of entities from the click graph as the center node and then collect their neighbor texts. After that, a subset of the center node's textual tokens is replaced by the mask token. The BERT model is expected to predict the masked tokens according to the remaining ones and the data from neighborhood. NE-MLM empowers the text encoders with the ability to capture the token-level topological connections.
The second task is the neighbor prediction (NP), which is similar to the NSP task and only differs in the input data. Our motivation lies in predicting the neighbors given the center node, which captures the topological relations at the entity-level. We first randomly sample a set of edges from the behavior graph. Text in a node is viewed as the next sentence of the text in its connected node and vice visa. The constructed text pairs are then used to strengthen the model's ability to leverage the rich user behaviors. After pretraining the BERT checkpoint with these two tasks, we select the first three layers as the initialization of the text transformers used in the AdsGNN model.

KNOWLEDGE DISTILLATION FOR LONG-TAIL ADS MATCHING
The proposed AdsGNN models leverage the unsupervised user behavior graph to enhance the relevance matching performance. However, their practical value is potentially hindered by the low-frequency long-tail entities. Neighborhood information from the behavior graph is indispensable to our proposals in both the training and inference phases, while long-tail entities are usually associated with few or even no neighbors. This scarce topological information brings a formidable challenge to the graph-enhanced semantic models, which is rarely studied by previous works. Assume the AdsGNN model has been fully trained on the normal ads dataset. Next, we will study how to apply the learned model to generate quality embeddings for long-tail entities in the inference phase. One straight-forward approach is to set the missing neighbors as a special token (e.g., [PAD]) and feed them into the learned model to obtain the representations. Given an input query and its neighbors , AdsGNN essentially learns the mapping function M: z = M ( , ), in which z is the learned embedding and will be fed into the matching layer. If we input the query with meaningless tokens into the learned mapping function to get z ′ = M ( ), it is obvious that z and z ′ would be quite different, which may further lead to the diverse matching results. Thus, this padding strategy may not be a desirable solution. Another possible solution is to comprehend the long-tail entities with their semantical closeness neighbors. For example, we can use Approximate Nearest Neighbor (ANN) search [4] to select the top similar ads˜ from the whole candidate set and view them as the complemented neighbors of . Despite of the low-efficiency of ANN search on the dataset with millions of samples, the mapping function M is trained to capture the click relations between the queries and ads, which are intrinsically different from the semantic similarities. Thus, the set˜ and have a large chance to be different, leading to the undesirable matching performance.
Here we aim to alleviate the challenge of long-tail ads matching in the manner of knowledge distillation [12]. As shown in Figure  5(a), a pre-trained AdsGNN is viewed as the teacher model. The learned representation z encodes the input query and its neighbors, which will be used as the training target of the student model. The right sub-figure illustrates the student model, which is a vanilla BERT model with the output asẑ . Our motivation lies in that the output vectorẑ of the student model should be similar to z as much as possible. The objective function is defined as follows: The L2-loss L forces the outputs of the student model should be topological preserving, which strengthens the student model with the ability to latently predict the neighbor information. Thus, it can effectively handle the long-tail entities. In addition, according to the universal approximation theorem [13], a feed-forward neural network can approximate any nonlinear functions and BERT is a comparatively sophisticated model with a large number of parameters. Hence, the student model is expected to approximate the mapping function learned from the teacher model successfully.

EXPERIMENTS 6.1 Dataset
The proposed AdsGNN models are extensively evaluated on a large industry dataset and Table 1 shows its statistics. This dataset is imbalanced, which is consistent with the fact that most query-ad pairs are unrelated. User behavior graph is sampled from the search log of a commercial search engine with 300 million distinct segments and more than 1 billion clicked relations. There exist some publicly available datasets like MSLR 1 and ESR 2 . However, they only contain the relevance annotations but lack the historical user behaviors, which are not suitable for the studied graph-augmented task. Although only one dataset is adopted, it includes 847,058 different manually labeled samples, which is much larger than the publicly available datasets (e.g., 32,000 for ESR). Besides, it is an online serving relevance dataset used by a popular commercial search engine and achieves satisfying online performance, which proves the quality and comprehensiveness of this dataset.

Baseline Methods
We select several state-of-the-art supervised baselines, including the semantic-based, graph-based and hybrid models. The semanticbased baselines are shown as follows: • C-DSSM [26] is a latent semantic model that incorporates a convolutional-pooling structure over word sequences to learn representations for queries and documents.

• BERT [3] is a dominant method of pre-training language
representations. Here we concatenate the query and ad as the input of BERT model. • Twin-BERT [23] is two-tower BERT-based structure model, which serves for the efficient retrieval. Our proposal is also compared with the graph neural networks. Following the normal GNN pipeline, we first learn the semantic embeddings of entities with the pre-trained BERT checkpoint, which are viewed as static node features. Then, GNN models aggregate the contextual node features into the center one. The objective function is to maximize the similarities between query and ad in the positive pairs while minimizing the similarity scores in negative pairs. Two hybrid approaches are also introduced as follows: • MetaBERT concatenates the text of center node and contextual neighbors as the input of a BERT model. • TextGNN [39] incorporates the text and graph information with a node-level aggregator, which is similar to AdsGNN . The major difference is that query and ad encoders in TextGNN share the same parameters, while AdsGNN views them as independent modules. For the proposed AdsGNN model, "Bert-base-uncased" in the huggingface 3 is selected as pre-trained BERT model. The number of behavior neighbors is set to 3. For the pre-training tasks, 15% of the input tokens are masked (80% of them are replaced by the mask token, the rest are replaced randomly or kept as the original tokens with the same probabilities). The size of minimal training batch is 64, learning rate is set to 0.00001, number of training epochs is set to 3. The student model in the knowledge distillation part is implemented with a five-layer BERT model. Adam optimizer [16] is employed to minimize the training loss. Other parameters are tuned on the validation dataset and we save the checkpoint with the best validation performance as the final model. Parameters in baselines are carefully tuned on the validation set to select the most desirable parameter setting. Considering the high imbalance distribution of the annotations, following the previous work [20] we select ROC-AUC score as the measurement, which represents the area under the Receiver Operating Characteristic curve. We release our code to facilitate future research (https:// github.com/ qwe35/ AdsGNN ).

Experimental Results
portion of the training set is randomly selected to train the relevance models. We repeat this process three times and report the average ROC-AUC scores. Training ratio is increased from 0.1 to 1.0. Experimental results are reported in Table 2 with different settings of . From the results, one can see that GNN models obtain the worst performance, which may be due to the node textual features are pre-existed and fixed in the training phase, leading to the limited expression capacity. The one-tower textual model (BERT) outperforms the two-tower models (C-DSSM and Twin-BERT) as it can incorporate the information from both sides, while two-tower models can only exploit the data from a single side. However, one-tower structure has to compute the similarity between a search query and each ad one-by-one, which is not suitable for low-latency online scenario. By integrating the user behavior graph with semantic information under a unified co-training framework, the hybrid models beat the other baselines by nearly 1%. Our proposals consistently outperform all the baselines. Compared with TextGNN, the node-level aggregation model AdsGNN can capture the different roles of queries and ads, leading to around 1% performance gain. AdsGNN surpasses AdsGNN by nearly 0.7% because it is capable of capturing the correlations between queries and ads. AdsGNN achieves the best performance, demonstrating that the tightly-coupled structure is more powerful than the loosely-coupled framework in deeply fusing the graph and textual information. From the results, we can summarize the following two conclusions: (1) the unsupervised user behaviors indeed facilitate the relevance matching task; (2) it would be better to integrate the complementary information into the underlying semantic units (e.g., tokens) instead of the high-level ones (e.g., nodes and edges).

Ablation Study
Here we perform the ablation study on the proposed models from different perspectives. The training ratio is set to 0.1.

Pre-training Tasks
Here we aim to investigate the importance of two proposed pre-training tasks NE-MLM and NP. Text encoders are pre-trained with various combinations of pre-training tasks. Table 3 presents the experimental results. One can see that the model performance significantly drops without any pre-training tasks, which demonstrates the effectiveness of the domain-specific adaption. NE-MLM task outperforms the NP task, proving that the token-level correlations are more critical than the node-level correlations. This conclusion is consistent with the superior performance of token-level aggregation model AdsGNN . Mixing these two tasks can sufficiently incorporate the domain-specific data from different levels, thus achieving the best performance. Edge Category Here we perform ablation study on the proposed AdsGNN model from the perspective of edge category selection. As mentioned in section 3.2, three types of edges are proposed to capture the local topology structure: input edge , first-order edge 1 and second-order edge 2 . Here we investigate the performance of different combinations of three types of edges, in which is indispensable as it is the primary learning target. Hence, four ablation models can be obtained as shown in Table 4 along with the relevance matching performance. Without the neighborhood information, model performs the worst. Model + 1 significantly outperforms + 2 , which demonstrates that the directly connected neighbors are more important and informativeness than the long-distance neighbors. The proposed AdsGNN model achieves the best performance by enjoying the merits of three types of edges.  Figure 6: Results of different completion strategies.
Aggregation Mechanism In the AdsGNN and AdsGNN models, self-attention is selected as the node/edge aggregator. In order to demonstrate the effectiveness of attention-based aggregator, four popular aggregation strategies are selected as the baselines including mean-pooling, max-pooling, summation and LSTM [10]. Results are shown in Table 5. Max-pooling outperforms the meanpooling and summation operations as it can effectively extract the strongest features from the inputs but suffers from serious information missing. LSTM can preserve all the input text information and thus obtain higher performance. However, LSTM aggregates the neighbors in sequences, which cannot distinguish the informativeness nodes from the less important ones. Self-attention enables the AdsGNN models to learn the importance of the input nodes/edges and weighted combine them together as the high-quality representations, leading to more promising performance.

Experimental Results on the Long-Tail Set
Here we evaluate the performance of the proposed knowledge distillation based model on the long-tail dataset. Node degrees in the user behavior graph indicate the clicked frequencies, and thus we randomly select a subset of nodes with only one edge connected as the long-tail entities. Then, we combine the selected node with its neighbor as the long-tail query-ad pairs. The relevance models are still trained on the normal training set and then applied to the long-tail dataset. Here we design the following three neighborhood completion approaches for the long-tail entities: • Padding adds the special token [PAD] as the neighbors.
• ANN selects the most similar entities from the whole set based on the semantic closeness and then add them as the complemented neighbors.   • KD is the proposed knowledge distillation approach.
The strongest baseline method TextGNN is selected for comparison. Experimental results are shown in Figure 6. Given the same neighbor completion strategy, AdsGNN consistently outperforms other methods, demonstrating that the token-level aggregation is more robust to the scarce topology information. ANN method significantly beats the Padding strategy by around 3%, proving that the semantic-related neighbors can bring richer information than the meaningless special tokens. The proposed KD strategy consistently outperforms the other two approaches. By viewing the topology-augmented representation as the learning target, the learned KD model is able to fit the mapping function which directly projects the input text from the original textual space to the topology-aware space. The neighborhood of long-tail entities can be latently predicted and incorporated by the KD model.

Parameter Sensitivity Study
We study the performance sensitivity of AdsGNN models on two core parameters: the number of neighbors and the number of transformer layers used in encoders. Training ratio is set to 1. Both parameters vary from 1 to 4, and the ROC-AUC scores under different settings are recorded. Figure 7 presents the experimental results. From the results, one can see that with the increase of , the performance first increases and then keeps steady. It means that the incorporation of more contextual neighbors contributes to better matching performance at the beginning. When the available contextual semantic information is fully explored, larger neighbor number cannot further improve model performance, which in turn slows down the training speed. When the parameter increases from 1 to 2, the performance is significantly improved. After that, the trend rate of growth slows down.

Online A/B Testing
The distilled AdsGNN model has already been successfully deployed in a major sponsored search platform and demonstrated significant performance gains. Revenue Per Mile (RPM) and Defect Rate are selected as measurements to estimate the revenue gained for every thousand search requests and the ratio of irrelevant ad impressions, respectively. The defected impressions are labeled by human experts. C-DSSM model is the original online severing model. The online A/B testing results of the AdsGNN model are summarized in Table 6. Our proposal is employed on both recall and relevance stage of the ads search. As shown in the table, the AdsGNN model achieves very impressive results because it can significantly increase RPM and reduce advertising defect rates. Results demonstrate that our proposal is capable of improving the user experience and driving revenue for the advertisers simultaneously.

RELATED WORK
In this section, we will summarize the related works. Relevance modeling in sponsored search can be viewed as the sub-domain of information retrieval (IR). In terms of matching queries with documents, traditional approaches usually adopt the shallow language representation learning models such as LSA [25], LDA [2] and Bi-Lingual Topic Models [7]. In recent years, deep learning based approaches have dominated the search area. Specifically, the siamese structure is adopted in a range of works [6,14,18,27,29,30]. By modeling local contextual information at the word level, Shen et al. [29] present a series of latent semantic models based on CNN to learn semantic vectors for web searching. To map source-target document pairs into latent semantic space, Gao et al. [6] propose a deep semantic similarity model with special convolutional-pooling structure. Besides, several works adopt the interaction-based structure [34,36,38]. Yang et al. [36] propose an attention-based neural matching model that adopts a value-shared weighting scheme to combine matching signals. Auto-encoders are used in [25], in which documents are mapped to memory addresses so that semantically similar documents are located at nearby addresses. In addition, several works also utilize lexical and semantic matching networks [9,24]. By employing a jointly learning framework at the query term level, Guo et al. [9] propose a deep relevance matching model for ad-hoc retrieval. With two separated deep neural networks, Mitra et al. [24] propose a document ranking model utilizing local representation and learned distributed representations respectively to match the query and document. Bai et al. [1] propose an n-gram based embedding of queries and ads to perform the efficient sponsored search. Grbovic et al. [8] propose a realtime personalization solution where embeddings of items that user most recently interacted with are combined in an online manner to calculate similarities to items that need to be ranked. Huang et al. [15] design a unified embedding framework developed to model semantic embeddings for personalized search.
Apart from the textual information, some related works attempt to incorporate other types of data in sponsored search scenario. Yang et al. [37] propose to learn the compositional representations by fusing the textual, visual and relational data. Zhu et al. [39] extend the Twin-Bert model to TextGNN, which aims to incorporate the search log data as complementary. Different from existing works [39] only focusing on a single aspect of data fusion, we aim to extensively investigate how to naturally fuse the semantic textual information and the user behavior graph from different perspectives and address several critical challenges in industry scenario.

CONCLUSION
In this paper, we propose a set of AdsGNN models to effectively incorporate the click graph as complementary from three aspects to improve the relevance matching performance. Three variations are designed to aggregate the neighborhood information from node-, edge-and token-levels. After that, two domain-specific pre-training tasks are proposed to warm up model parameters. A knowledgedistillation model is further proposed to handle the challenge of long-tail entity inference. Empirically, we evaluate the proposed models over a real-life dataset, and the experimental results demonstrate the superiority of our proposal.


s2fieldsofstudy:
Computer Science
Business

text:
An Intelligent Path Evaluation Algorithm for Congestion Control in Wireless Sensor Networks

In Wireless Sensor Networks (WSNs), congestion occurs when the traffic load on the node reaches obvious network channel power and is considered as a prominent problem. So it is highly essential to identify, prevent and fix congestion when taking into account the network’s restricted resources. If congestion in the network is not managed correctly, it can lead to significant loss of QoS parameters, such as decreasing network throughput, increasing energy usage, and decreasing the distribution ratio of packets at the destination or sink node. In this article, we have formulated an algorithm to manage congestion using a modified ant colony algorithm that considers the residual energy, buffer occupancy and bandwidth of the neighbour node for selecting the best node to route the traffic that needs strict QoS requirements. For routing the traffic, there may be a variety of neighbour nodes exists in the network ,and if congestion occurs at any selected neighbour node the algorithm will rework to check the quality of rest of the neighbor nodes by calculating a path preference probability metric. The neighbour node with maximum path preference probability will be selected for routing the data packets belonging to realtime traffic that have stringent QoS. The proposed algorithm was simulated and tested using NS 2.33 and it was found that as opposed to the standard AntSense algorithm, the proposed algorithm is capable of achieving lower average energy consumption and packet loss ratio respectively with higher throughput.

Wireless Sensor Network
WSNs are simple computers with a variety of devices mounted on them that are used to configure environmental as well as physical data such as pressure, sound, orientation, vibration, and temperature, amongst many other factors. The input obtained from the sensors is redirected from one sensor to another via a multi-hop routing protocol to access the sink node. The base station is in possession of the results aggregation and analysis. Sensor nodes in WSNs have limited resources in terms of power consumption, resources, storage, bandwidth, processing capabilities, and so on. Initially, the researchers managed to come up with a routing scheme that would enable them to make efficient use of WSN resources. Nodes are mostly self-organized and connect with each other via wireless networks, which are implemented throughout the WSN on an ad hoc basis. The main obstacles amongst the other possible problems is that the routing mechanism of the WSN can be compromised, culminating in inevitable losses due to network congestion. In order to provide the congestion-free efficient routing, a number of techniques based on Ant colony optimization have been proposed . However, most of the techniques are either using residual energy or the gap between the node, and its destination is used to measure the likelihood of packet transmission using a neighbour node. So, in order to design an efficient congestion control algorithm, we have taken residual energy of the neighbour node, buffer occupancy and bandwidth allocated for calculating the probability of the next neighbor node for selection. The remaining section of this paper is as follows: Section 2 is a comprehensive review of related work, Section 3 is the basic Ant colony optimization work, Section 4 is the proposed Ant colony optimization algorithm, and Section 5 is the simulations and analysis of the results. Finally, the paper will be finalized in Section 6.2.

Congestion in Wireless Sensor Networks
Congestion is the most prominent issue in WSNs that adversely affect the network QoS parameters, must be handled properly. When the multiple sensor nodes start sending the data simultaneously the data generated at intermediate nodes increases. As a result, the number of data packets and generated data from the source nodes exceeds the underlying capacity of the network queue and at the same time makes the networks underperforming DOI: https://doi.org/10.17762/turcomat.v12i6.6953 An Intelligent Path Evaluation Algorithm for congestion Control in Wireless Sensor Networks ______________________________________________________________________________________________________________ __________________________________________________________________________________ 3107 due to congestion. In WSNs, we can have a variety of causes for congested networks, such as overloading of the queue, collision of packet with each other, parallel transfer of data packets sharing the bandwidth etc.There are 2 levels at which congestion can occur in the networks: node-level congestion and link-level congestion. Nodelevel congestion is very common in both conventional and wireless sensor networks. The key cause for nodelevel congestion is buffer overload at the sink or intermediate node in the network. Congestion at node-level contributes to packet loss and increased queuing delays. On the other hand, as more than one sensor node tries to transfer data within the same range, this leads to congestion at the link-level. In inclusion to growing network losses and wastage of network resources like energy, this type of congestion has an unfavorable impact on the throughput and connection capacity of the network (Wang et al.,2007;Patel et al.,2013). A sophisticated and accurate congestion management system is needed to make the network efficient. There are sections of congestion management: the detection of congestion, the confirmation of congestion and the control of congestion outlined below.

Congestion Detection
In the Wireless Sensor Networks, the role of sensing congestion and locating a scene of congestion is to predict congestion. Various metrics are used to track interference in wireless sensor networks: packet losses, Buffer occupancy and channel load.
• Packet loses: Packet losses can be estimated using ACKs on the sender side, the sequence number can be used on the receiver side; consistent packet loss can be used as an illustration of congestion.
• Buffer occupancy: This congestion detection parameter is also recognized as the length of the queue. Each WSN system retains a buffer for storing incoming packets if they cannot be transmitted immediately. Algorithms that use this parameter to detect congestion usually use a constant buffer threshold. As the length of the queue or the occupancy of the buffer raises the constant threshold value, congestion is identified, and some warning is raised.
• Load on a network channel load or busyness: can be another metric to detect congestion. Packet load is measured in the wireless medium of communication, and congestion is identified when the packet transmission time reaches the predefined threshold time. When the channel is occupied, the packet collision will increase. In the case of a spike in packet collision, several packets are eliminated from the buffer and thus the occupancy of the buffer decreases (Patel et

Congestion Notification
It is the obligation of the protocol operating in the network to transmit congestion-based information to expecting nodes so that effective ventures can be taken. These details may be a bit of congestion or a control message. Explicit congestion refers to data that is sent as a data traffic jam warning bit in the incoming packets, while implicit congestion refers to data that is sent as a separate surveillance code.
• Explicitly notification of congestion: In this strategy, the source node is intimated as to congestion by the use of control packets in the event of congestion detection. Sending the congestion condition in the form of control packets to the already congested network puts an extra burden on the network. This approach is therefore not commonly used and used by some of the congestion management protocols. This is the major drawback of being specifically told of congestion (Sergiou et al.,2014;Tao et al.,2010).
• Implicitly notification of congestion: Implicit congestion warning strategy does not use control packets to monitor congestion to the respective source nodes and load on the already congested nodes and the network. The packet payload header is piggybacked with congestion information and distributed to other nodes on the network

Related Work
In real-world scenarios, there is a number of optimization problems exists which are difficult to solve and categorized as NP-hard category problems. The two basic categories of techniques that can be used to solve such kind of problems are: Providing the actual algorithm and the approximate results algorithms which optimally generate the approximate results through a sequence of iterations. The main difference between the two techniques is that the former one will provide us with the optimal solutions with more computation time, but the later one will use less computation time for generating the optimal results for NP-hard problems.
The routing problem based on Ant Colony Optimization (ACO) is a category of NP-hard approach that is implemented in WSN in particular. ACO is an algorithm based on swarm intelligence, motivated by the discovery behaviour of ant colonies present in the natural environment, and is a powerful technique to fathom combinational optimization algorithms. A multi-pronged decomposition-based ant colony algorithm (Cheng et Research Article Vol.12 No.6 (2021), 3106-3114 al.,2012) was put forwarded , where the colony of the ant was split into several subspecies , and for each group, one pheromone pattern was kept. However the importance of separate objectives for all targets to stake the equivalent pheromone data could not be expressed in this approach, which meant that the objective functions were similarly relevant. In order to solve the problem of multiple targets of differing meaning (Hackel et al., 2008), a Pareto optimization approach hinged on dynamic programming with multilevel of pheromone and heuristic intelligence was proposed. With the help of two pheromone matrices and a probing matrix (Prasad et al. 2013), a routing scheme with Multi-objective and multi cast criteria based on the ant colony algorithm was used to route packets with contended QoS. However, none of the algorithms mentioned above has not considered the congestion while routing the data from one node to another node. In order to consider the factor of congestion in the routing algorithm we have designed a novel algorithm for routing the information from optimal path. The main contributions of the article are as follows.
• To evaluate the various paths available for routing the information from neighbour node to the next node. Path evaluation will be done by calculating the path preference probability of the neighbor nodes using Ant colony opti-mization probability function and selecting the neighbor node with maximum path preference probability.
• To consider the residual energy of neighbour node, bandwidth allocated and buffer occupancy for calculate the path preference probability.
• To simulate the proposed algorithm by using Ns-2.33 simulator and analyzing the results on network parameters throughput, average energy consumption and packet delivery fraction. Finally comparing the results of the proposed algorithm with the traditional Antsense algorithm.

Traditional Ant Colony Optimization
Met heuristic is a collection of dedicated rules that can be utilized to establish heuristic procedures that apply to a large variety of different optimization problems. (Sharma et al., 2016) has formalized ACO as a met heuristic for mixture optimization problems. ACO takes inventiveness from the provender practices of ant species who inject pheromones on the ground to signify any suitable routes that other members of the colony should follow. To solve problems of optimization, ACO uses a similar mechanism. An individual sensor is insect type species with minimal memory requirement and involved in executing simple ventures. The colony communicates a diverse collective activity that provides an intelligent process to the problems such as moving heavy items, building bridges and discovering the quickest pathways from the nest to the source of food, since a unique insect has no broad understanding of the function it plays and its activities are based on local settlements and are highly irregular. This intelligent behaviour of course occurs as a result of self-sustaining and incidental communication between ants, which can be referred to as (Sharma et al., 2014;Camilo et al.,2006) swarm intelligence.
In the basic part of ACO algorithm the process iterates through three steps after initialization: ConstructAntSolutions, ApplyLocalSearch algorithm, and UpdatePheromones process. A series of surrogates are established by ants that are optimally improved by a local search algorithm and the update pheromone process. In view of this formulation, by moving simultaneously and asynchronously to a sufficiently defined graphical representation that represents any given problem domain, ACO ants produce solutions to the problem. Ants select the next neighbour hop node j from a node i according to the probability formula defined given below (Sharma et al.,2016) where Pi,j is the probability of ant selecting the next node j from node i. Ti,j is the concentration of pheromone in the path i to j. Ni indicated the number of next neighbour nodes that an ant can select. α indicates the weight of the concentration of pheromone. Di,j is the distance of next neighbour node from i node and β indicates the weight of the distance.
Wireless sensor networks routing is a difficult problem since the features of the network, such as traffic loading and network topology, can differ stochastically and in a time of varying nature. The distributed design of network routing is well associated with the multi-agent nature of ACO algorithms. Traffic-adaptive and multipath routing is given by the collection of unique properties that characterises ACO objects for routing problems, based on both passive and active data tracking and collection, using hypothetical units, not allowing local processes to have a global effect, setting up routes in a less greedy way than in strictly shortest path techniques preferring balancing of network load (Sharma et al.,2016).

4.Proposed Work
In the suggested algorithm, Path evaluation will be done using the intelligent behaviour of ANT colony optimization algorithm and congestion will be controlled, if occurs, by routing the different type of traffic from different paths based upon the goodness of paths available. Congestion in the network will be detected at the node level by checking the buffer occupancy of the node. The proposed algorithm is based on devising the algorithm for evaluating the best path for real-time traffic like audio/video using an updated Ant colony optimization algorithm. For this purpose algorithm will identify if there is congestion in the network by checking the buffer occupancy of the neighbor node for transferring the packets. If buffer occupancy falls under the situation that can lead to congestion, we need to identify the packets belonging to different traffic types like audio, video or scalar traffic. The packets belonging to real-time traffic will be routed through the best node among the neighbors. In sensor networks, there can be variety of sensor nodes generating the data packets which may belong to scalar as well as real-time traffic. The main objective of the proposed algorithm is to route the real time packets through the nodes having maximum path preference probability.
In the event of congestion, the proposed algorithm will calculate the path preference probability of all the neighbour nodes from where data can be routed. The path preference probability will be calculated by considering the residual energy, bandwidth and buffer occupancy of the neighbour nodes and node with the maximum path preference probability will be selected for routing the information. In order to calculate the path preference probability, we will be using the mathematical model illustrated below. The path preference probability from node i to neighbour node j can be calculated using the following mathematical function.
where PpFi,j is the path preference probability of ant selecting the next node j from node i. Ni indicated the number of next neighbor nodes that an ant can select. Ei,j is the energy of next neighbor node from i node and α indicates the weight of energy. Bi,j is the bandwidth of next neighbor node from i node to node j and β indicates the weight of bandwidth. BOi,j is the buffer occupancy of the node j and γ indicates the weight of buffer occupancy. Ti,j is the accumulation of pheromone in the path i to j and θ indicates its weight.
The Algorithm flowchart of the proposed algorithm is shown in figure 1 Research Article Vol.12 No.6 (2021), 3106-3114 . Figure 1: Algorithm flowchart of proposed algorithm

Simulation and Result Analysis
Proposed algorithm using updated ant colony optimization algorithm and traditional algorithm Antsense under the situation of congestion have been simulated by using a well-known simulator NS-2.33 under the varying number of sensor nodes. A number of extensive simulations have been performed to check the efficacy of the developed algorithm. Nodes are put randomly in a 2000 m x 2000 m zone in all scenarios. Each mobile node's maximum transmitting range is 100 m. Static nodes are called the sensor nodes that have been simulated on the network. The channel bandwidth is 2 Mbps and the IEEE 802.11 DCF is used for the MAC layer. Each simulation runs for 100 seconds at a time. A variety of CBR sources with multiple sources for the development of multiple traffic types and with a single destination have generated data traffic. Various parameters taken for the network simulation is listed Table 1.

Average Energy Consumption Analysis
The figure 2 represents the average energy consumption at the end of simulation and it has been observed that the proposed algorithm shows less energy consumption as compared to traditional Antsense algorithm. This is due to the fact that the proposed algorithm uses bandwidth between the two nodes as well as buffer occupancy of the neighbor node to be selected for packet transmission in addition to residual energy of the node. As shown in the figure extensive simulations have been performed by varying the number of nodes in the network and in all the scenarios the proposed algorithm is showing the positive result. In the event of congestion in the network simulation, the proposed algorithm efficiently able to select the best node among the set of neighbor nodes with maximum path preference probability. Table 2 summarizes the throughput obtained for proposed and traditional Antsense algorithm by varying the number of nodes in the network.

Throughput Analysis
The figure 3 represents the throughput at the end of simulation and it has been observed that the proposed algorithm shows higher throughput as compared to traditional Antsense algorithm. This is due to the fact that the proposed algorithm uses bandwidth between the two nodes as well as buffer occupancy of the neighbor node for selecting the next for packet transmission in addition to residual energy of the node there by able to select the best node for transmission. When the best node is used for transmission among the various available neighbor nodes then the reliability of the network increases thereby increasing the throughput of the network. As shown in the figure 3 extensive simulations have been performed by varying the number of nodes in the network and in all the scenarios the proposed algorithm is showing the positive result. In the event of congestion during the network simulation, the proposed algorithm efficiently able to select the best node among the set of neighbor nodes with maximum path preference probability.  The Packet loss rate (PLR) is one of the important metric for measuring the performance of traffic related to realtime flows such as video and Voice over IP. The number of lost data packets must be low in order to prove the smooth and seamless data transmission. The number of lost data packets is increasing with the increase in number of nodes increasing in the simulated network. However, the proposed algorithm has lower packet loss rate increase than that of the AntSense algorithm. This is due to the fact that the proposed algorithm uses the best node among the available neighbor nodes available for data transmission in the event of congestion. When the traffic is diverted to the congestion free path from the congested path then packet loss tare decreases as show in the figure 4

Conclusion
In this paper we have proposed a path evaluation algorithm based on modified ant colony optimization technique for controlling the congestion in wireless sensor networks. The proposed algorithm improves the heuristic function for selection the next neighbor node to transmitting the packet. The improved heuristic function considers residual energy, buffer occupancy and bandwidth allocated to the neighbor node and calculates path preference probability of all the neighbor nodes. The algorithm selects the neighbor node with maximum path preference probability. The simulation result shows that the proposed algorithm shows the decrease in the average energy consumption and packet loss ratio and increase in the throughput of the network when compared with AntSense algorithm.


On the interpretation and significance of bias metrics in texts: a PMI-based approach

In recent years, the use of word embeddings has become popular to measure the presence of biases in texts. Despite the fact that these measures have been shown to be effective in detecting a wide variety of biases, metrics based on word embeddings lack transparency, explainability and interpretability. In this study, we propose a PMI-based metric to quantify biases in texts. We show that this metric can be approximated by an odds ratio, which allows estimating the confidence interval and statistical significance of textual bias. We also show that this PMI-based measure can be expressed as a function of conditional probabilities, providing a simple interpretation in terms of word co-occurrences. Our approach produces a performance comparable to GloVe-based and Skip-gram-based metrics in experiments of gender-occupation and gender-name associations. We discuss the advantages and disadvantages of using methods based on first-order vs second-order co-occurrences, from the point of view of the interpretability of the metric and the sparseness of the data.

In recent years, the use of word embeddings has become popular to measure the presence of biases in texts. Despite the fact that these measures have been shown to be effective in detecting a wide variety of biases, metrics based on word embeddings lack transparency, explainability and interpretability. In this study, we propose a PMI-based metric to quantify biases in texts. We show that this metric can be approximated by an odds ratio, which allows estimating the confidence interval and statistical significance of textual bias. We also show that this PMI-based measure can be expressed as a function of conditional probabilities, providing a simple interpretation in terms of word cooccurrences. Our approach produces a performance comparable to GloVe-based and Skipgram-based metrics in experiments of genderoccupation and gender-name associations. We discuss the advantages and disadvantages of using methods based on first-order vs secondorder co-occurrences, from the point of view of the interpretability of the metric and the sparseness of the data.

Introduction
Techniques for estimating the semantic closeness between words are a core component in a wide va-riety of NLP applications. One particularly prolific idea behind these methods is that the meaning of words is at least partially determined by the context in which they appear (Harris, 1954), of which word embeddings are their most popular instantiation (Mikolov et al., 2013;Pennington et al., 2014).
In particular, word embedding-based approaches have been used to detect and quantify the presence of gender, ethnic, racial and other stereotypes in texts (Lenton et al., 2009;Caliskan et al., 2017;Garg et al., 2018). As the size of corpora that are fed into AI applications keeps growing, the need for efficient and accurate techniques for the analysis of biases has become an urgent matter (Font and Costa-jussà, 2019).

Bias quantification in texts
Consider two sets of target words A and B, and a set of context words C. Generally speaking, bias measures seek to quantify how much more the words of C are associated with the words of A than with arXiv:2104.06474v1 [cs.CL] 13 Apr 2021 those of B (or vice versa). Consider for instance the case of gender biases in occupations: the fact that certain jobs (C) are more likely to be associated with one particular gender (A) than other(s) (B). Here target words are often taken to be pronouns and simple gendered nouns, e.g., A = {she, her, woman,..} and B = {he, him, man,...} (Garg et al., 2018;Caliskan et al., 2017;Gálvez et al., 2019;Lenton et al., 2009;Lewis and Lupyan, 2020).
A popular choice for C is to consider one word at a time, i.e. estimating how a specific job (such as nurse, doctor or engineer) is associated with the two previously defined sets. Once these sets have been defined, most metrics can be parametrized as a difference between the similarities between A and C, on the one hand, and B and C, on the other (Lenton et al., 2009;Garg et al., 2018;Lewis and Lupyan, 2020); in most cases subtracting the similarities A vs C and B vs C, One particularly influential case that belongs to this class of metrics is that of Caliskan et al. (2017), who define In the present paper we propose a metric to measure biases that follows eq. 1 based on Point-wise Mutual Information (PMI) (Church and Hanks, 1990;Jurafsky and Martin, 2000) as our plugin measure for similarity between words.
PMI is a non-parametric measure of statistical association derived from information theory (Fano, 1961). Given two words w x and w y , PMI is defined as Here, p(w x , w y ) is the probability of cooccurrence of words w x and w y in a given window of k words. The PMI (Equation 3) compares the probability of co-occurrence of the words w x and w y with that of the case in which w x and w y are independent. Moreover, the same expression (eq. 3) can be used to calculate associations between word-lists X and Y , Here p(X, Y ) is the probability of co-occurrence between any word in X with anyone in Y . Similarly, p(X) and p(Y ) are the probability of occurrence of any word in X and any word in Y , respectively. The usage of PMI in the study of textual biases is not new (Gálvez et al., 2019). However, in this article we will show a number of statistical and interpretability benefits associated with PMI-based measures that have been overlooked until now.
In particular, we make the following contributions: • In section 2 we show how the bias measurement using PMI can be approximated by an odds ratio. This comes with a number of statistical perks, including the possibility of performing computationally unexpensive null hypothesis statistical testing • In section 3 we demonstrate that methods based on Glove, Skip-gram and PMI produce comparable results in Caliskan et al. (2017) tasks, in which statistics of gender biases in occupations and names are compared with the biases measured in texts • In section 4 we contend that the use of PMI in bias metrics is substantially more transparent and interpretable than counterparts based on word embedding techniques 2 Approximation of the PMI-based bias metric to an odds ratio PMI can be expressed in terms of context words' conditional probability, Therefore, the PMI-based bias can be rewritten as follows, To compute the PMI-based bias, we can estimate probabilities via maximum likelihood, Here f A,C and f B,C represent the number of times words in C appear in the context of words in A and B, respectively, and f A,nC and f B,nC represent how many times words in C appear in the context of words that are not in A and B, respectively. See contingency table in Table 1 for reference.
In the case in which the following condition is fulfilled, equation 5 can be approximated by where OR is the odds ratio associated with Table  1. This quantity has a confidence interval given by This last approximation considers condition 6.

Experiments
To compare the measure of bias based on PMI with those based on embeddings, we follow the approach of Caliskan et al. (2017). They compare biases present in texts with those of two census datasets: (1) an U.S. occupation-gender dataset, which contains the percentage of participation of women in a list of occupations, and (2) an U.S. name-gender dataset, which shows, for a list of androgynous names, the percentage of people with that name who are women.
Experimental setup. We build a corpus with articles from an English Wikipedia dump from august 2014. We pre-process the dump by removing non alpha-numeric symbols, removing articles with less than 50 tokens and sentence splitting. We use a window size of 10 in all models and we ignore words with less than 100 occurrences, resulting in a vocabulary of 173,056 words. Word embeddings with 300 dimensions are trained with skip-gram with negative-sampling (SGNS) and GloVe. For SGNS we use the word2vec implementation of the Gensim library (Řehůřek and Sojka, 2010) with default hyperparameters. GloVe is trained with the original implementation (Pennington et al., 2014) with 100 iterations. This version uses by default additive word representations, in which each word embedding is the sum of its corresponding context and word vectors.
Using PMI, SGNS and GloVe, we replicate the gender bias experiments performed in the Word Embedding Factual Association Tests (WEFATs) in Caliskan et al. (2017). To represent female and male contexts we use the same sets of words as in Caliskan et al. (2017) 1 . The female proportions for names and occupations in the U.S. were extracted from the datasets provided by Will Lowe's cbn R library 2 , which contains tools for replicating Caliskan et al. (2017).
For both occupations and names association tests, we assess the correlation between the realworld female proportion and the female bias as measured by PMI, SGNS and GloVe. Female bias refers to the bias metrics where A and B represent the lists of female and male words, respectively. Therefore, positive values imply that the context word is more associated with female words than with male ones.
We emphasize that the objective of this experiment is not to find which method produces a greater correlation between the biases in the U.S. census data and the ones from Wikipedia -the aim is to show that the three bias metrics produce comparable correlations in these tasks.
Results. Figure 1 and Table 2 show the scatterplots and Pearson's r coefficients for each of the six experiments (two association tests with three bias measures each). Weighted Pearson's r coefficients are shown in Table 2 for the PMI-based metric for both association tests. Weighted Pearson's r takes into account the variance of each point, thus reducing the influence of relatively noisy estimates on the correlation. This type of adjustment is not feasible with embeddings-based methods, which lack a natural notion of statistical variability.
In the androgynous names setup, we find similar degrees of correlation for the three bias measurement methods, for both weighted and unweighted correlations. In the occupation experiment, we find similar values of Pearson's r for the three methods; and a slight increase in the correlation is observed when the variability of bias is considered in the estimation.
All in all, our results show that the embeddingbased methods and the PMI-based method produce comparable performances in the WEFAT tasks of Caliskan et al. (2017).

Significance testing
A permutations test that shuffles target words (A, B) is a way that has been used in similar metrics in order to calculate statistical significance. (Caliskan et al., 2017;Garg et al., 2018;Charlesworth et al., 2021). A limitation of this technique is that, for the test to have enough power, many words are required in the lists. To show this, we perform permutation tests in the occupations experiment using the SGNS-based method. We shuffle the words from lists A and B repeatedly and estimate the probability of obtaining an absolute value of bias that is equal to or greater than the one obtained in the original configuration (North et al., 2002). In Figure 2 we compare the p-values of the permutation test in the SGNS-based metric with the p-values of the odds ratio test of the PMI-based metric. A Benjamini-Hochberg correction was applied to the p-values obtained by both methods to account for multiple comparisons. The permutation test indicates that only the two words with the highest female SGNS-based bias are significantly different from zero. This supports our hypothesis that permutations tests don't have enough power whenever word-lists are small. In contrast, in the case of the PMI-based metric, the odds ratio test indicates that the majority of points are significantly different from zero, with the exception of some points with bias values close to zero.

Interpretability
Model interpretability has become a core topic of research in NLP. Loosely speaking, it refers to the degree to which a human can understand the cause of a decision -which has become progressively more complex as current models steer away from simpler setups.
In general terms, there seems to be an inverse relationship between complexity of a model and its interpretability. In simpler models it tends to be easier to understand which is the true process of the model. This aspect is called faithfulness (Tim, 2019) 3 .
Although there are many studies on how the vector space of word embeddings is formed (Levy and Goldberg, 2014;Levy et al., 2015;Ethayarajh et al., 2019), there is no transparent interpretation of bias measurements formed by cosine distances between word-vectors. This can be partially observed in the growing literature which tries to construct metrics in order to measure word embedding interpretability (Senel et al., 2018;Jang and Myaeng, 2017;Panigrahi et al., 2019). Most of those metrics can be considered post-hoc 4 .
In contrast, the PMI-based bias measure can be expressed intrinsically in terms of conditional prob-  Table 2: Pearson's r coefficients for each experiment shown in Figure 1. Because the PMI-based metric provides a measure of variance, weighted Pearson's r coefficients have been calculated to account for the variance of each data point. The bias is interpreted as the logarithm of how many more times it is likely to find words in C in the context of words in A than in the context of words in B. This can be interpreted as stating that it is 272.81% more likely to find the word nurse in the context of words associated with women (A) than in the context of words associated with men (B).

Discussion
As far as we know, our bias metric is the first that provides a simple and efficient way of evaluating the statistical significance of the obtained biases. We highlight the importance of knowing if the measured patterns are indeed significant. Imagine the case where we want to know if a collection of texts has a particular bias. To address this situation, it is not only necessary to estimate the magnitude of the bias, but also to have a decision rule that lets us know up to what degree this value might have been due to statistical fluctuation. A statistical test associated with the bias measure is essential in this use case.
Skip-gram and GloVe embeddings can capture word associations of second order or higher. (Levy et al., 2015;Altszyler et al., 2018;Schlechtweg et al., 2019). Therefore, when embeddings are used to measure word associations, it is not possible to know whether the emerging biases are due to ostensive co-occurrences within chunks of text or whether they are derived from higher-order cooccurrences. Rekabsaz et al. (2018) evidenced the presence of these spurious associations when quantifying semantic similarity with second-order contributions, and Brunet et al. (2019) showed in a sensitivity analysis that second-order effects provide an important contribution in the quantification of bias with the WEAT metric from Caliskan et al. (2017). Nevertheless, bias metrics based on second-order associations have the advantage of managing data sparsity. For example, they can capture relevant associations in synonyms occurrences of target and context words (A,B and C). In the case of our first-order metric, this problem must be addressed by increasing the length of word-lists with synonyms and different forms of the words of interest. Rekabsaz et al. (2018) propose a metric based on word embeddings that only captures first-order associations. Their results show that their metric correlates with biases in employment more than other measures based on second-order co-occurrences. This measure uses the product of word and context matrices of the Skip-gram model (W and C), so this measure can be interpreted as a shifted-PMI with smoothing. In future work we will compare Rekabsaz et al. (2018) metric with ours. However, we emphasize that the benefit of using the PMI-based metric lies in the interpretability and the estimation of confidence intervals and statistical significance.

Conclusions
In this article we present a PMI-based metric to capture biases in texts, which has the benefits of (a) providing simple and computationally unexpensive statistical significance tests, (b) having a simple interpretation in terms of word co-occurrences, and (c) being explicit and transparent in the associations that it is quantifying, since it captures first-order co-occurrences.
We show our PMI-based bias measurement can be approximated by an odds ratio. This allows for the calculation of confidence intervals and statistical significance for bias, using as the null hypoth-esis the absence of bias. We demonstrate that our measure can be expressed as the logarithm of the ratio of the probabilities of the context words conditional on the target words. This provides a simple interpretation of the metric's magnitudes in terms of word co-occurrences: how much more likely is it to find context words C in a window around target words A than in a window around target words B?
Finally, we prove that the use of our method produces a performance comparable to the one produced by GloVe-based and Skip-gram-based metrics in Caliskan et al. (2017) experiments of gender-occupation and gender-name associations.