Knowledge Graphs are a widely used method to represent relations between entities in various AI applications, and Graph Embedding has rapidly become a standard technique to represent Knowledge Graphs in such a way as to facilitate inferences and decisions. As this representation is obtained from behavioural data, and is not in a form readable by humans, there is a concern that it might incorporate unintended information that could lead to biases. We propose EXTRACT: a suite of Explainable and Transparent methods to ConTrol bias in knowledge graph embeddings, so as to assess and decrease the implicit presence of protected information. Our method uses Canonical Correlation Analysis (CCA) to investigate the presence, extent and origins of information leaks during training, then decomposes embeddings into a sum of their private attributes by solving a linear system. Our experiments, performed on the MovieLens-1M dataset, show that a range of personal attributes can be inferred from a user's viewing behaviour and preferences, including gender, age and occupation. Further experiments, performed on the KG20C citation dataset, show that the information about the conference in which a paper was published can be inferred from the citation network of that article. We propose four transparent methods to maintain the capability of the embedding to make the intended predictions without retaining unwanted information. A trade-of between these two goals is observed.
Knowledge graphs are structures that encode entities and the relationships between them, and
are useful representations of real world phenomena. Knowledge graphs can be employed in an
array of applications, including linguistic representation learning [
This study emphasizes link prediction , an inherent task in Knowledge Graph Embedding, that can simplify crucial issues like recommending user actions or answering entity-specific queries. Using user gender as an exemplar of private information, we scrutinize its influence on representations and its ethical implications within AI systems. nEvelop-O LGOBE
https://research-information.bris.ac.uk/en/persons/martha-lewis (M. Lewis);
Recent studies showed that personal information can be inferred from user behaviour. A
study of Facebook users showed that certain private traits (including gender and race) could
be reconstructed on the basis of their public “likes” [
We address issues, similar to prior word embedding research, concerning vector
representations derived from word co-occurrence [
Related Work The presence of gender information in word embeddings was already reported
in Bolukbasi et al. [
When it comes to bias removal, a range of strategies exists. Regularization methods focusing
on fairness have been explored [
Our Contributions We introduce EXTRACT: Explainable and Transparent ConTrol of bias in embeddings, a two-step process to detect and mitigate bias in Knowledge Graph Embeddings, implemented on the MovieLens 1M and KG20C citation datasets. Our detection methods include logistic classifiers (detect-LC), canonical correlation analysis (detect-CCA), and a linear decomposition (detect-LD). Bias removal leverages linear projection methods (remove-LP and remove-LP-multi) and two retraining methods, remove-FM and remove-FM-multi.
The proposed methods are efective and interpretable, with our novel application of detectCCA and detect-LD. Specifically, detect-CCA constitutes a novel use of CCA, marking its debut in bias detection. Additionally, detect-LD contributes a unique decomposition of node embedding space into interpretable dimensions, signifying attribute presence or absence - a method not previously implemented. Our methods, remove-LP and remove-LP-multi, can be directly applied to pre-existing embeddings, saving computational resources by eliminating the need for retraining from scratch. Despite slight performance decreases, our methods parallel state-of-the-art results, maintaining conciseness, interpretability, and explainability.
Knowledge Graph-Based Recommendation Algorithms In a knowledge graph = ( , ℱ , ) , vertices signify real-world entities, each endowed with a set of attributes. Relationships between these vertices are captured in a set ℱ consisting of facts. Each fact ∈ ℱ is articulated as a triple (ℎ, , ) , where belongs to a set of relations ℛ that serve as direct edges from head ℎ to tail . For instance, considering a set of users and movies as vertices, user ratings form the edges.
A knowledge graph embedding translates vertices into vectors maintaining graph topology,
represented as (h, R, t) ∈ ℝ . The score function ( h, R, t) governs the linking between nodes.
Rating Prediction In alignment with Berg et al. [
( ) ( ) + ∑ ′≠∈ R ( ′) In the above formula, = (ℎ, , ) denotes a true triple, and ′ = (ℎ, ′, ) denotes a corrupted triple, that is a randomly generated one. We use as a proxy for a negative example (a pair of nodes that are not connected).
Assigning numerical values to relations , the predicted relation is then just the expected value
prediction = ∑∈ R (h, R, t) In our application of viewers and movies, the set of relations
R could be the possible ratings that a user can give a movie. The predicted rating is then
the expected value of the ratings, given the probability distribution produced by the scoring
function. ( ) refers to the scoring function in Yang et al. [
To learn a graph embedding, we follow the setting of Bose and Hamilton [
( ) ( ) + ∑ ′∈F ′ ( ′) This loss function maximises the probabilities of true triples ( ) and minimises the probability of triples with corrupted triples ( ′).
Unlike predicting movie ratings which is the relation in MovieLens 1M,
we use a margin based loss [
∈ℱ ′∈ℱ ′ = ∑ ∑ [ + ( ′) − ( ) ] + Here, []+ means keeping the positive part of the loss function and we want ( ) > (
We use 4 metrics to evaluate our performance on the link prediction task. These are root mean square error (RMSE, relation and is the true relation), Hits@K - the probability that our target value is in the top predictions, mean rank (MR) - the average ranking of each prediction, and mean reciprocal rank (MRR) to evaluate our performance on the link prediction task. These are standard metrics √ 1 ∑ =1 ( ̂ − )2, where ̂ is our predicted in the knowledge graph embedding community. ′).
(3)
The general problem is as follows. Given a knowledge graph = ( , ℱ , ) , suppose that one attribute ∈
is private: we do not wish users of the embedded graph to be able to predict the value of for a given vertex ∈ . We show here that it is possible to predict the value of some private attributes even when that attribute is not used in the embedding algorithm.
We give three methods: a logistic classifier based method (detect-LC), Canonical Correlation Analysis (detect-CCA), and a linear decomposition method (detect-LD) to detect private information in the vertices . detect-LC: Logistic Classifier
Consider a knowledge graph denoted by = ( , ℱ , ) .
We’ve represented this graph in a -dimensional space, ℝ , based solely on the information
from and . Suppose a subset of vertices ⊆
is labelled with the presence or absence of
attributes . For example, in a database of users and movies, we might have a subset of users,
with each node labelled as over 18 or under 18. We train a logistic classifier to predict the value
of for each vertex ∈ . See Figure 1 for an illustration. In the case of our movie rating
example, private attributes could be gender, age, and occupation.
detect-CCA: Canonical Correlation Analysis Canonical Correlation Analysis (CCA) is
used to measure the correlation information between two multivariate random variables [
As above, we assume that a subset ⊆ of vertices is labelled with the presence or absence of attributes . Supposing we have attributes, we can then form a Boolean-valued matrix A of dimension | | × , where each row corresponds to a vertex in , and each column corresponds to an attribute. In this matrix, each ∈ is therefore represented by a vector of ones and zeros corresponding to presence or absence of each attribute. Suppose we have a | | × matrix of vertex embeddings U that we have learnt via our knowledge graph embedding. We compute the CCA between A and U. We learn vectors w and w , such that the correlation between the projected A and projected U are maximised, that is = max(w ,w ) corr (Aw , Uw ). Note there are correlations corresponding to components.
In the example of viewers and movies, we use this method to compare two descriptions of users, illustrated in Figure 2. One matrix is based on demographic information, represented by Boolean vectors. The other matrix is based on their behaviour, computed by their movie ratings only. detect-LD: Linear Decomposition Again assuming we have a matrix of entity embeddings U with Boolean matrix A encoding the attribute information, we investigate the possibility that the entity embeddings can be decomposed into a linear combination of embeddings corresponding to attributes. Specifically, we investigate whether we can learn a matrix X by solving AX = U.
We investigate here the possibility that entity embeddings in knowledge graphs can be
decomposed into linear combinations of embeddings corresponding to attributes. We use
methods from Xu et al. [
In our example of viewers and movies, we define a set of users as and the Boolean encoding matrix of the attributes as A. We aim to solve a linear system AX = U, so that the user embedding can be decomposed into three components (gender, age, occupation) as follows, u = ∑ x , where u is a user embedding, ranges over all possible values of each private attribute, x is an embedding corresponding to the th attribute value, and ∈ {0, 1} indicates the presence or absence of that attribute value. Figure 3 shows a running example of decomposing user into gender and age (18-30 and 31-60). Figure 3 shows the schematic of detect-LD.
to detect private information by comparing with randomly shufled data. Our null hypothesis is
that the embedding of a vertex and its attributes are independent. To test whether this is the
case, we employ a non-parametric statistical test, whereby we directly estimate the -value as
the probability that we could obtain a “good”1 value of the test statistic under the null hypothesis.
If the probability of obtaining the observed value of the test statistic is less that 1%, we reject
the null hypothesis. Specifically, we will randomly shufle the pairing of vertices and attributes
100 times, and compute the same test statistic. If the test statistic of the paired data is better
than that of the randomly shufled data across all 100 random permutations, we conclude that
the correctly paired data performs better to a 1% significance level. The test statistic for the
logistic classifier is the accuracy of predicted labels, for CCA is the correlation , and for the
linear System AX = U we look at the L2 norm loss of the linear system, cosine similarity and
retrieval accuracy, a metric defined in [
As well as detecting bias in a knowledge graph, we also wish to remove it. In the following, we
give two methods for removing bias based on a linear transformation method (remove-LP) as
well as an extension of this (remove-LP-multi), and two (remove-FM and remove-FM-multi)
based on penalising diferences between the distribution of items with diferent protected
characteristics. The diference in distribution is approximated by comparing only the first
moments, though the method can be extended to further moments.
(remove-LP): Linear Transformation We refer to previous work on word embedding debias
[
∈ by − , so that now, all the sets have the same centroid. (remove-FM): First-Moment Loss Ideally, two sets of items that difer only along protected dimensions should have the same distribution in the embedding space. Therefore we aim to reduce the diference between distributions of items which difer in that way by penalising the distance between first-moments of their empirical distribution (i.e. between their empirical means) during the training process.
Again suppose we have a graph = ( , ℱ , )
, a subset of vertices of interest , an embedding
of this graph, and that we are able to detect information about an attribute that we wish
to keep private. Consider two subsets of vertex embeddings = {u } and = {u } with
private attribute taking values and . For the first-moment loss we consider each of and
as multivariate distributions of the two classes and . We aim to remove the diference in
the first moments of the two classes by centering the mean coordinates of the two classes. An
illustration of this can be shown in Figure 4. We follow Zemel et al. [
L = ∗ Loss + ∑ 1 (‖u − ‖2 − 1) 2 + ∑
1 , ( − ) 2 where , ∈ {Class 1, Class2, Class3 ... }, is the count of vertices of class , , is the count of combinations of diferent classes. is the center point of class , is the weight parameter that gives more weight to the Loss (the original loss in Equation 2, 3) for predicting relations/entities.
This experiment was conducted on the MovieLens 1M dataset [
Users and movies each have attributes. For example, users have demographic information
such as gender, age, or occupation. Whilst this information is typically used to improve the
accuracy of recommendations, we use it to test whether the embedding of a user correlates
to private attributes, such as gender or age. Crucially, we compute our graph embedding
based only on ratings, leaving out user attributes. Experiments for training knowledge
graph embeddings are implemented with the OpenKE [
We use a 90:10 train:test split to train user and movie embeddings with triples ( , , ) . Initial embeddings are randomly assigned and optimized to minimize loss as per equation (2). We sample 10 corrupted entities and 4 corrupted relations for each true relation. The learning rate is 0.01 and epochs are set at 300. Link prediction on the 10% test set yields an RMSE score of 0.88 (table 2).
Citation Network The KG20C knowledge graph is constructed from 20 top AI conferences
[
We view the venue, i.e. conference, as information that we wish to detect and potentially remove. As an application, suppose we are building a search engine and wish to avoid the “echo chamber” of groups of authors citing each other’s work. Detecting conference information could help to return a more diverse set of search results.
Embeddings for entities and relation types were randomly initialized and trained to minimize the loss as per equation 3, using a 0.05 learning rate over 300 epochs and a margin, , set to 6. Link prediction task metrics (Hits@10: 0.29, Hits@1: 0.075, MRR: 0.15, and MR: 1369.93) attest to our embeddings’ quality. The bias-removal strength, , incrementally set to 50, 100, and 150, increased the loss function’s bias-removal component. With 1/3 of triples sharing the same head and relation but diferent tails, individual triples were tested to maintain accuracy. To ensure the reproducibility of our results, we have made the code available at https://github. com/ZhijinGuo/EXTRACT.
We now apply our three methods for bias detection to investigate the extent to which private information can be detected in user embeddings trained without that information. detect-LC on MovieLens We use a logistic classifier to predict gender, age, and occupation from the embeddings. We sub-sample the data to have balanced datasets with respect to gender, age, and occupation.
Using an 80:20 training-to-test split across all datasets, we trained logistic classifiers for each
attribute, implemented via the scikit-learn toolkit [
We apply CCA to calculate the correlation between users and their attributes. We apply the non-parametric statistical test described in section 3. Specifically, our null hypothesis is that users’ movie preferences are not correlated with their attributes. We calculate Pearson’s correlation coeficient (PCC) between projected Aw and projected Uw . We go on to calculate the PCC between 100 randomly generated pairings of user and attribute embeddings, and find that the PCC between true pairs of attribute and user embeddings is higher each time. We therefore reject the null hypothesis at a 1% significance level. The correlation coeficients between real pairs and random pairs is reported in figure 5a.
(a) Pearson’s correlation coeficient (PCC) for true user-attribute pairings and 100 permuted pairings.
PCC is calculated between projected A and
projected U. axes stands for the th components,
axes gives the value. The PCC value for real
pairings is larger than for any permuted pairings.
(b) (t-SNE) visualisation [
As with the CCA setting, we permuted the pairing of users 100 times. Table 1 shows the observed p-value for three diferent statistics, which is the probability of seeing that value of statistic under the null hypothesis. We first decompose the user embedding into gender and age. Our results show the linear system is able to decompose the user embedding with a loss of 0.47, which is lower than every loss for a random permutation (1.11-2.11). The cosine similarity is 99.8%, higher than any permuted pairs. The identity retrieval accuracy is 0.79 which is higher than any random permuted pairs (0.0-0.14). Therefore, the null hypothesis is rejected. This shows that a user embedding can be reconstructed as a linear combination of gender and age.
When decomposing the embedding into gender, age and occupation, the L2 norm is 17.87 which is lower than every loss for a random permutation (18.90-19.56). The cosine similarity is 97.1%, higher than any permuted pairs. As for identity retrieval accuracy, although the value is only 0.23 which is not a good result, it is still higher than any random permuted pairs (0.00-0.08). Therefore, the null hypothesis is rejected.
We consider a dataset of scientific papers, whose entities are the papers, their authors, the conference in which those papers were presented, and the scientific domain they belong to. For the sake of example, we will treat as sensitive the information about the specific conferences in which a given paper was presented (we could pretend that this information should not be used as part of career assessment, and therefore should be hidden for this reason).
We embed scientific papers using their relations with the sets of authors and domains, and then we will test if that embedding could contain enough information for a logistic classifier to learn how to predict the specific conference. Note that this is a very strict requirement - that in no way can any information relevant to this task be contained in the embedding of the paper. Similar to the movie recommender system, we treat the conference information in this citation network as a sensitive attribute.
Utilizing 5407 papers with respective author, citation, domain, and author afiliation relations, we generate embeddings for each and label them with one of the 20 conferences, which are then split into training and test sets. Our logistic classifier (detect-LC) yields a 55% accuracy in conference venue prediction, surpassing the 13% baseline (5b). Despite not being trained on conference data, the embeddings can still distinguish diferent conferences.
We apply the techniques introduced in section 4 to remove information about age and gender from MovieLens-1M, and information about conference from the KG20C citation network. (a) Gender - rating trade-of (b) Age - rating trade-of remove-LP for MovieLens We investigate the ability to remove the gender and age bias detected in the knowledge graph user embedding whilst maintaining the ability of the embedding to predict behaviour. We apply remove-LP (section 4) to remove gender and age information from the data splits described in section 5.2. We run the bias removal process for 10 iterations. Results are reported in table 2.
As depicted in figures 6a and 6b, there is a trade-of between predictive power and bias. An increase in iterations leads to a drop in gender classification accuracy from 73% to 54%, nearing baseline accuracy, with a slight increase in RMSE from 0.88 to 0.93. A similar pattern is observed in age bias removal, with accuracy for under/over 50s decreasing from 0.72 to 0.62, and RMSE rising from 0.88 to 1.01. remove-FM for MovieLens We use remove-FM (section 4) to remove bias during the training of the embeddings. We again use embeddings and splits described in section 5.2, and investigate how well predictive power is retained as bias information is removed. Figures are reported in table 2. We see that as we increase the parameter , the accuracy of the gender classifier decreases, although not monotonically. The RMSE increases slightly from 0.88 to 0.96. remove-LP-multi for KG20C Regarding the KG20C dataset, we employ linear shifting for classes greater than or equal to two to eliminate bias post-training, adjusting the paper embedding to ensure that paper sets labelled with diferent conferences converge at a common center. Results, detailed in Table 3, indicate that the model, while becoming conference neutral, experiences a minor decrease in predictive power (Hits@10 reduces from 0.29 to 0.21). remove-FM for KG20C We apply the methods described in the multi-class version of removeFM (section 4). The embeddings are debiased during training. A parameter weights the strength of the prediction power. We set to 1 and 20, to increase the influence of the prediction part of the loss function. As shown in Table 3, a larger slightly improves Hits@10 but decreases Hits@1 and MR. Additionally, the retained conference information increases accuracy from 0.14 to 0.26, though Hits@10 drops 0.14, signifying a trade-of between prediction power and unwanted information removal.
In this work, we introduced EXTRACT, a comprehensive framework that combined three methods for detecting and four methods for removing biases in knowledge graph embeddings. Using datasets like MovieLens 1M and KG20C, EXTRACT eficiently identified leaks of sensitive attributes and unintended conference afiliations. This two-step process ensured that specific dimensions of user embeddings, correlating to private or sensitive attributes, were identified and appropriately treated. Our findings showed that the correlations between the private attributes and the user representations were significantly higher than random, validating the eficacy of EXTRACT in capturing statistical patterns that reflect private attribute information.
Furthermore, our linear decomposition system, an integral part of the EXTRACT framework, revealed that user-behaviour-embedding can be approximated by a sum of user-demographic vectors. This validated the framework’s ability to decompose user embeddings into a weighted sum of attribute embeddings, thereby allowing for the targeted removal or control of bias.
Our four approaches to debiasing were more transparent and explainable than more complex methods. Remove-LP method was most successful at debiasing, whilst retaining relatively good performance than the link prediction task. Overall, EXTRACT served as a unified, two-step approach that advanced the field towards ethical and transparent knowledge graph embeddings.