Proxy Attribute Discovery in Machine Learning Datasets via Inductive Logic Programming

Our first priority is to establish a systematic procedure for encoding a simple ML dataset as valid input for our target ILP system. As an example, we revisit the dataset from Table 1. Recall that this dataset has two non-protected attributes, \(\textbf{Marital}\) and \(\textbf{Country}\), a protected attribute \(\textbf{Sex}\), and that \(\textbf{Marital}\) is a proxy attribute of \(\textbf{Sex}\) when \(\textbf{Marital} = husband\) or \(\mathbf {Marital = wife }\). Informally, our goal is to encode each attribute as a logical relation, allowing the ILP system to derive rules that associate the protected attribute with the proxy attribute. Fig. 1 gives an abridged view of the encoding. Note that the background knowledge encodes the non-protected columns and the values appearing in the dataset (called decision points), while the examples encode the protected column.

Let us then formalize the encoding process. In a nutshell, we aim to define an encoding function \(\mathcal {E}(T)\) that takes as input a dataset \(T\) and encodes it as an ILP program. We can formally define a dataset \(T\) as:Here, a dataset is described as a sum of \(n\) rows \((\rho _i, t_i)\), where \(\rho _i\) is a tuple of non-protected attributes and \(t_i\) the protected attribute for some row \(i\). For example, the first row of Table 1 is defined as \((( husband, usa ), male)\). Note that the column \(\textbf{ID}\) is not encoded, as it is neither a protected nor a non-protected attribute. In general, a dataset may have any number of protected attributes; however, for modeling purposes, we assume that each dataset has only one. We can easily transform a dataset with \(k\) protected attributes into \(k\) datasets with a single protected attribute by simply isolating each protected attribute at a time.

Given a dataset \(T\), we define its encoding, \(\mathcal {E}(T)\), as:

where \(p_x\) is constructed by appending the value of \(x\) to the character \(p\) (e.g., if \(x = m\), then \(p_x = pm\)). The intuition behind this encoding is more involved. We explain each component of the sum individually:

In the current example, given the encoding shown in Fig. 1, an ILP system would learn the rules \(\text {sex}(X, Y) \ \text {:-} \ \text {pmarital}(X, Z), \ \text {ph}(Z), \ \text {pm}(Y)\), corresponding to the case \(\textbf{Marital} = husband\), and \(\text {sex}(X, Y) \ \text {:-} \ \text {pmarital}(X, Z), \ \text {pw}(Z), \ \text {pf}(Y)\), corresponding to the case \(\textbf{Marital} = wife\).

Although the basic encoding strategy described in §4.1 is effective for small synthetic datasets (e.g., Table 1), it often falls short when applied in the wild. To address this, we discuss the application of preprocessing techniques, focusing on two key issues: conflicts between rows, which we solve via majority voting, and size limitations, which we mitigate through sampling.

Removing Conflicts. A conflict between two or more rows occurs when all their non-protected attributes are identical but the protected attribute differs. Put formally, two rows \(i, j\) are conflicting if \(\rho _i = \rho _j\) but \(t_i \ne t_j\). This is a common issue in real-world datasets; an example of how it might happen is given in Table 4a. The dataset has two sets of conflicts: rows 1, 3 and 6, and rows 4 and 5. While a human can easily recognize that this example is not incorrect, many ILP systems interpret such conflicts as errors and struggle to produce meaningful output. Popper, for instance, often fails to discover relevant relations in datasets with conflicts, as it cannot find a set of rules that accurately predicts the protected attribute across all conflicting rows.

To remove conflicts, our tool implements a straightforward majority voting system. Given a set of conflicting rows, the system proceeds as follows: if any protected attribute holds a relative majority, it keeps a single row with that attribute; otherwise, it discards all rows. Applying these principles to Table 4a, the tool produces the dataset shown in Table 4b. In the example, the protected attribute \(\textbf{Race} = black\) holds a relative majority in rows 1, 3 and 6; hence, the preprocessed dataset keeps row 1. In contrast, no protected attribute holds a relative majority in rows 4 and 5, which are discarded. Since this approach may occasionally introduce false positives (e.g., \(\textbf{Marital}\) acting as a proxy of \(\textbf{Race}\) in Table 4b), rules inferred from the preprocessed dataset must be validated against the original dataset (cf. §4.4).

Sampling. Real-world datasets often have tens or even hundreds of thousands of rows. Applying our methodology directly to such datasets would result in extremely large ILP tasks. For instance, a dataset containing \(10\) non-protected attributes and \(20 \, 000\) rows would produce \(10 \times 20 \, 000 = 200 \, 000\) column relations. This poses a significant challenge to our approach, as even state-of-the-art ILP systems cannot efficiently handle inputs of that size.

To address this, our tool samples a random subset of rows from the dataset and applies the ILP procedure exclusively to this sample. The default sample size varies with the size of the dataset, and should balance performance and representativeness. Once the procedure terminates, the tool validates the rules inferred from the sampled rows against the entire dataset, accepting only those that perform well across all rows (cf. §4.4).

Consider the example shown in Table 5. The dataset has one non-protected attribute, \(\textbf{Score}\), and one protected attribute, \(\textbf{Race}\). Here, \(\textbf{Score}\) acts as a proxy attribute of \(\textbf{Race}\); specifically, when \(\textbf{Score} > 75\), \(\textbf{Race}\) has value \(white\). This relation cannot be discovered with our basic encoding methodology, which only supports equality-based reasoning for numeric attributes. However, as in this example, some datasets (e.g., the Ricci dataset [49]) contain proxy relations that can only be expressed through arithmetic relations beyond simple equalities.

In the context of ILP, one possible technique for reasoning about these relations is to explicitly encode them on the numeric values that appear in the sampled rows. For example, in Table 5, we can encode the underlying order relation using the less-than operator in tandem with the equality. Fig. 2 gives an abridged view of the application of this technique. The general structure is similar to that of Fig. 1, with the key difference being the inclusion of the less-than relations between integer values in the background knowledge. Note that the encoding of these relations is grounded, i.e., it is explicitly defined for all relevant integer pairs rather than being expressed as a mathematical rule. While this has an impact on the size of the background knowledge file, it improves the performance of the ILP procedure by pruning the search space [13].

As before, we can formalize the encoding process for some dataset \(T\). To account for arithmetic relations, our implementation is parametric on a set of relations to be grounded. For simplicity, however, we focus the formalism solely on the less-than operator. Hence, given a dataset \(T\), we define its parameterized encoding, \(\mathcal {E}_{lt}(T)\), as:

Here, the less-than operator is encoded as a set of pair relations \(lt(i, j)\) representing its grounding for all integers appearing in the sampled rows. Note that to parameterize \(\mathcal {E}(T)\) on other relations, one needs only modify the extended encoding. For instance, addition can be modeled by changing the inner union to \( \bigcup _{i, \, j \, \in \, \text {Ints}(c)} sum(i, j, i + j)\). By default, we encode only the less-than relation.

In the current example, given the encoding shown in Fig. 2, an ILP system would learn the rule \(\text {race}(X, Y) \ \text {:-} \ \text {pscore}(X, Z), \ \text {lt}(75, Z), \ \text {pw}(Y)\).

Identifying proxy attributes often requires a degree of flexibility in determining what qualifies as a proxy. For example, in Table 1, \(\textbf{Marital}\) acts as a proxy of \(\textbf{Sex}\) only when \(\textbf{Marital} = husband\) or \(\mathbf {Marital = wife }\), which will be reflected in the rules found by the ILP procedure. In general, it is acceptable for the inferred rules not to cover certain rows. Conversely, some rows may be misclassified due to noise or because the protected attribute is only strongly correlated with the proxy rather than directly implied by it. Therefore, rules must be evaluated against a set of criteria that allows for some leniency while still ensuring that overly specific or highly inaccurate rules are filtered out.

Metrics. For a given rule, we measure the number of rows where: (i) the proxy and protected attributes match the body and head of the rule, respectively (\(\textbf{TP}\)); (ii) neither the proxy nor the protected attributes match the body and head of the rule (\(\textbf{TN}\)); (iii) the proxy attributes match the body of the rule but the protected attribute does not match the head (\(\textbf{FP}\)); and (iv) the proxy attributes do not match the body of the rule but the protected attribute matches the head (\(\textbf{FN}\)). As an example, consider Table 6, which illustrates these concepts for the rule \(\text {sex}(\! X \! , male) \ \text {:-} \ \text {marital}(\! X \! , husband)\), written in simplified notation for clarity. We base our filtering criteria on three metrics: recall (\(R\)), precision (\(P\)) and coverage (\(C\)), defined in the standard way:Informally, recall ensures that rules are broad enough to filter out overly specific relations, precision that rules maintain a high level of accuracy, and coverage that rules apply to a statistically significant portion of the dataset. An attribute qualifies as a proxy only if there exists a rule pertaining to it that meets specific thresholds: by default, rules should be comprehensive (above 15% recall and 10% coverage) and highly accurate (above 85% precision). The choice of thresholds is critical in determining which proxies are found; we discuss them further in §5.3.

System Selection. To determine the most suitable ILP system for our tool’s backend, we define five criteria: (i) open-source availability; (ii) active maintenance; (iii) quality and comprehensiveness of documentation; (iv) support for noise; and (v) support for arithmetic relations. Despite the wide array of available ILP systems, we narrow our focus to four that best fit our task: Popper [14], which we discussed previously; Aleph [48], a longstanding and widely-used system; and two modern ILP tools, Metagol [43] and ILASP [38].

Table 7 gives an abridged comparison of the evaluated systems. With the exception of Metagol, all tools offer support for both noise and arithmetic relations, and are well-documented. However, both Aleph and Metagol are no longer maintained, while ILASP, despite being actively maintained, is not open-source. Popper, on the other hand, meets all our criteria and is easy to use, making it the ideal choice for our experiments.

Datasets. We evaluate our approach against 10 real-world datasets with well-known sources of indirect discrimination [39]:

A summary of the tested datasets and experimental results is given in [23, Appendices A and C]. For a more comprehensive discussion, see [39].

Establishing the Baseline. In the literature, there is no ground-truth list of proxy relations for the evaluated datasets. To establish our baseline of expected proxy relations, we began by analyzing the Bayesian networks given in [39], enumerating all non-protected attributes that were directly connected to protected attributes by an edge. This analysis signaled 41 attributes as proxy candidates, listed in [23, Appendix B].

Of the 41 candidates, five belonged to the Lawschool dataset, which was previously studied in [35]. We cross-checked these five candidates against the causal relations identified in [35], leaving us with two validated proxy relations in this dataset. For the remaining 36 candidates, we employed a random forest classifier [6, 34] to check whether the values of the corresponding protected attributes could be inferred with a Gini impurity level of 0.01. This process yielded another 12 expected proxy relations in the nine analyzed datasets.

The resulting list comprises the 14 expected proxy relations given above, and serves as a benchmark for comparison with our approach. While the list is not exhaustive, and, in fact, our methodology uncovered proxy relations beyond this baseline (cf. §5.2), it provides a point of reference for our experiments.

Experimental Setup. All tests were executed on a Ubuntu machine (22.04.4 LTS) with an Intel Core i5-8250U CPU and 8GB of RAM, using Popper 4.2.0¹ and SWI-Prolog 9.2.5. The datasets were preprocessed to remove the target labels and isolate each protected attribute individually. Each experiment was performed three times, with a maximum timeout of 20 minutes (1200 seconds) per run. The results were obtained by taking the union of all discovered rules from the three runs.

We tested each dataset for potential proxy attributes with varying thresholds for recall, precision, and coverage. Table 8 shows the number of detected proxy relations under different threshold settings, ranging from strict (20/90/15) to permissive (5/80/2.5). The number of expected proxy relations is indicated next to each dataset. Additionally, we provide the average recall, precision, and coverage values for the detected relations under each threshold setting, along with the total number of detected relations. For example, in the Adult dataset, we identified 3 rules that meet the default thresholds (15/85/10), with an average recall, precision, and coverage of 32/95/23.

We detected the expected proxy relations in nearly all cases, except for the Bank Marketing and COMPAS datasets. In both instances, the relevant proxy relations were identified, but did not meet our minimum thresholds and were therefore discarded. The remaining proxy relations were detected at varying threshold settings depending on the dataset. For example, in the Adult dataset, we detected the relationship proxy at the highest thresholds (20/90/15), while in the Credit Card dataset, we only detected the age proxy at the lowest (5/80/2.5).

We also identified several proxy relations that have not been previously discussed in the literature. For instance, in the Ricci dataset, we detected a relation between combine and race: \(\text {race}(X, white) \ \text {:-} \ \text {combine}(X, Y), \text {lt}(79, Y)\), written in simplified notation for clarity, with recall, precision, and coverage of 25/94/14. Informally, this rule states that an individual is white if their combine score is greater than \(79\). Notably, Le Quy et al. [39] overlook this relation because they categorize combine into two groups, \(\{< 70, \ge 70\}\), failing to identify the correct splitting point for this attribute.

In addition, we identified proxy relations involving multiple proxy attributes. In the Adult dataset, we found a relation between native-country/education and race: \(\text {race}(X, white) \ \text {:-} \ \text {native-country}(X, usa), \text {education}(X, bsc)\), with recall, precision, and coverage of 16/92/14. Informally, this rule states that an individual is white if they have a bachelor’s degree and are from the US. While prior work [39] found causal relations between native-country, education, and race, their combination in a single proxy relation was previously unknown. In contrast, our approach explicitly identifies the proxy relation.

Finally, Table 9 shows the maximum recall, precision, and coverage values found in the proxy relations detected for each dataset. The corresponding values for the other metrics are provided in parentheses. For example, in the Credit Card dataset, the maximum detected recall was \(7.65\%\), with the corresponding rule having \(83\%\) precision and \(4\%\) coverage. Note that these values may fall below the minimum thresholds, resulting in their exclusion from Table 8 (e.g., in the Bank Marketing and COMPAS datasets). Furthermore, notice that while the maximum precision is consistently high, it often comes from rules with low recall/coverage. On the other hand, the maximum recall and coverage vary across datasets, and in some cases even fail to meet the thresholds, despite being typically associated with high precision rules.

The results demonstrate that ILP is an effective technique for proxy attribute discovery, having successfully identified most of the proxy attributes discussed in the literature, as well as some that were previously unknown. This discussion highlights the strengths and limitations of our approach, and how it compares to more traditional causal methods.

Thresholds. The modeling choice that most affects our approach is threshold selection. Stricter thresholds lead to lower detection rates, but have a higher likelihood of detecting true proxy attributes. In turn, more permissive thresholds boost detection rates, but at the risk of introducing false positives. There are no universally optimal thresholds; the appropriate choice depends on the specific dataset under analysis. For instance, in the Credit Card dataset, we only identify the age proxy at the lowest threshold settings, while in the German Credit dataset, nearly every attribute is flagged as a proxy under similar conditions.

In general, we have found that the limiting factors in our approach are typically recall and coverage, rather than precision. This is in line with the results from Tables 8 and 9: while the average recall/coverage tends to drop significantly when we lower the thresholds, the average precision tends to remain constant. Our sensitivity to these metrics can be attributed to two main factors. First, as we have already discussed, the choice of thresholds impacts which rules are discarded and which are not. Second, ILP systems prioritize inferring general rules over highly specific ones. This means that if a proxy relation has a very low coverage (e.g., under 1%), the dataset sample fed into the ILP system may contain too few instances where the rule applies. In such cases, the system will discard the rule, as it is not general enough to induce [13].

Comparison with Causal Methods. The impact of the different metrics varies significantly depending on the discovery method used. Causal approaches tend to be more sensitive to lower precision. For example, Le Quy et al. [39] fail to discover the relation between marital-status and race in the Adult dataset, while we detect it with a precision of approximately 87%. In contrast, our approach is more sensitive to lower coverage, as evidenced by its failure to detect proxies in the Bank Marketing and COMPAS datasets.

Another difference between the two methods lies in the handling of numeric attributes. As mentioned earlier, Le Quy et al. [39] are able to detect proxy relations involving arithmetic operations (e.g., in the Ricci dataset). However, their approach relies on the categorization of numeric attributes, which requires domain knowledge and user effort. As a result, if the user fails to choose the appropriate categories, the system may miss relevant causal relations (e.g., the combine proxy in the Ricci dataset). In contrast, our approach supports arithmetic relations natively, and does not require any user-guided preprocessing.

Finally, the proxy relations we detect are directly interpretable and can be easily validated. This stands in contrast to causal approaches, as shown by the relation between native-country/education and race discussed earlier. While causal methods may detect such proxy attributes [39], their output provides limited insight into the underlying proxy relations. In contrast, our approach explicitly identifies these relations, making them straightforward to interpret and validate.