\subsubsection*{Data profile as root cause.} Towards solving the first
challenge, our observation is that data-driven systems often function properly
for certain datasets, but malfunction for others. Such malfunction is often
rooted in certain \emph{properties} of the data, which we call \emph{data
profiles}, that distinguish passing and failing datasets. Examples include size
of a dataset, domains and ranges of attribute values, correlations between
attribute pairs, conditional independence~\cite{DBLP:conf/sigmod/YanSZWC20},
functional dependencies and their variants~\cite{papenbrock2015functional,
koudas2009metric, DBLP:conf/icde/FanGLX09, ilyas2004cords,
caruccio2016discovery}, and other more complex data
profiles~\cite{song2011differential, DBLP:journals/vldb/LangerN16,
papenbrock2015divide, DBLP:journals/pvldb/ChuIP13}.

\subsubsection*{Oracle-guided root cause identification.} Our second
observation is that if we have access to an \emph{oracle} that can indicate
whether the system functions desirably or not, we can verify our hypotheses.
Access to an oracle allows us to precisely isolate the correct root causes of
the undesirable malfunction from a set of candidate causes. Here, an oracle is
a mechanism that can characterize whether the system functions properly over
the input data. The definition of proper functioning is application-specific;
for example, achieving a certain accuracy may indicate proper functioning for
an ML pipeline. Such oracles are often available in many practical settings,
and have been considered in prior work~\cite{bugdoc, aid}.

\smallskip

\paragraph{Solution sketch.} In this paper, we propose \textsc{DataExposer}\xspace, a framework
that identifies and exposes data profiles that cause a data-driven system to
malfunction. Our framework involves two main components: (1)~an
intervention-based mechanism that alters the profiles of a dataset, and (2)~a
mechanism that speeds up analysis by carefully selecting appropriate
interventions. Given a scenario where a system malfunctions (fails) over a
dataset but functions properly (passes) over another, \textsc{DataExposer}\xspace focuses on the
\emph{discriminative} profiles, i.e., data profiles that significantly differ
between the two datasets. \textsc{DataExposer}\xspace's intervention mechanism modifies the
``failing'' dataset to alter one of the discriminative profiles; it then
observes whether this intervention causes the system to perform desirably, or
the malfunction persists. \textsc{DataExposer}\xspace speeds up this analysis by favoring
interventions on profiles that are deemed more likely causes of the
malfunction. To estimate this likelihood, we leverage three properties of a
profile:
(1)~\emph{coverage}: the more tuples an intervention affects, the more likely
it is to fix the system behavior,
(2)~\emph{discriminating power}: the bigger the difference between the failing
and the passing datasets over a profile, the more likely that the profile is a
cause of the malfunction, and
(3)~\emph{attribute association}: if a profile involves an attribute that is
also involved with a large number of other discriminative profiles, then that
profile has high likelihood to be a root cause. This is because altering such a
profile is likely to passively repair other discriminative profiles as a
side-effect (through the associated attribute).
We also provide a group-testing-based technique that allows \emph{group
intervention}, which helps expedite the root-cause analysis further.

\smallskip

\paragraph{Scope.} In this work, we assume knowledge of the classes of
(domain-specific) data profiles that encompass the potential root causes. E.g.,
in Example~\ref{ex:one}, we assume the knowledge that correlation between
attribute pairs and disparity between the conditional probability distributions
(the probability of belonging to a certain gender, given price of items bought)
are potential causes of malfunction. This assumption is realistic because:
(1)~For a number of tasks there exists a well-known set of relevant profiles:
e.g., class imbalance and correlation between sensitive and non-sensitive
attributes are common causes of unfairness in
classification~\cite{bellamy2018ai}; and violation of conformance
constraints~\cite{fariha2021conformance}, missing values, and
out-of-distribution tuples are well-known causes of ML model's performance
degradation. (2)~Domain experts are typically aware of the likely class of data
profiles for the specific task at hand and can easily provide this additional
knowledge as a \emph{conservative} approximation, i.e., they can include extra
profiles just to err on the side of caution. Notably, this assumption is also
extremely common in software debugging techniques~\cite{aid,
liblit2005scalable, Zheng2006}, which rely on the assumption that the
``predicates'' (traps to extract certain runtime conditions) are expressive
enough to encode the root causes, and software
testing~\cite{mesbah2011invariant}, validation~\cite{kumar2013verification},
and verification~\cite{henzinger2003software} approaches, which rely on the
assumption that the test cases, specifications, and invariants reasonably cover
the codebase and correctness constraints.

\looseness-1 To support a data profile, \textsc{DataExposer}\xspace further needs the corresponding
mechanisms for discovery and intervention. In this work, we assume knowledge of
the profile discovery and intervention techniques, as they are orthogonal to
our work. Nevertheless, we discuss some common classes of data profiles
supported in \textsc{DataExposer}\xspace and the corresponding discovery and intervention
techniques. For data profile discovery, we rely on prior work on pattern
discovery~\cite{pattern}, statistical-constraint
discovery~\cite{DBLP:conf/sigmod/YanSZWC20}, data-distribution
learning~\cite{hellerstein2008quantitative}, knowledge-graph-based concept
identification~\cite{galhotra2019automated}, etc. While our evaluation covers
specific classes of data profiles (for which there exist efficient discovery
techniques), our approach is generic and works for any class of data profiles,
as long as the corresponding discovery and intervention techniques are
available.

\smallskip

\paragraph{Limitations of prior work.} \looseness-1 To find potential issues in
data, Dagger~\cite{DBLP:conf/cidr/RezigCSSMTOS20,
DBLP:journals/pvldb/RezigBTO0MMS20} provides data debugging primitives for
human-in-the-loop interactions with data-driven computational pipelines. Other
explanation-centric efforts~\cite{DBLP:conf/sigmod/WangDM15,
Bailis:2017:MPA:3035918.3035928, Chirigati:2016:DPM:2882903.2915245,
GebalyFGKS14} report salient properties of historical data based only on
observations. In contrast with observational techniques, the presence of an
oracle allows for interventional techniques~\cite{bugdoc} that can query the
oracle with additional, system-generated test cases to identify root causes of
system malfunction more accurately. One such approach is
CheckCell~\cite{DBLP:conf/oopsla/BarowyGB14}, which presents a ranked list of
cells of data rows that unusually affect output of a given target function.
CheckCell uses a fine-grained approach: it removes one cell of the data at a
time, and observes changes in the output distribution. While it is suitable for
small datasets, where it is reasonable to expect a human-in-the-loop paradigm
to fix cells one by one, it is not suitable for large datasets, where no
individual cell is significantly responsible, rather, a holistic property of
the entire dataset (profile) causes the problem.

Interpretable machine learning is related to our problem, where the goal is to
explain behavior of machine-learned models. However, prior work on
interpretable machine learning~\cite{lime, anchors} typically provide
\emph{local} (tuple-level) explanations, as opposed to \emph{global}
(dataset-level) explanations. While some approaches provide feature importance
as a global explanation for model behavior~\cite{casalicchio2018visualizing},
they do not model feature interactions as possible explanations.

\looseness-1 Software testing and debugging techniques~\cite{Gulzar2018,
Attariyan2011, Attariyan2012, chen2002pinpoint, fraser@tse2013,
godefroid@ndss2008, holler@uss2012, DBLP:conf/icse/JohnsonB20, Zheng2006,
liblit2005scalable} are either application-specific, require user-defined test
suites, or rely only on observational data. The key contrast between software
debugging and our setting is that the former focuses on white-box programs:
interventions, runtime conditions, program invariants, control-flow graphs,
etc., all revolve around program source code and execution traces. Unlike
programs, where lines have logical and semantic connections, tuples in data do
not have similar associations. Data profiles significantly differ in their
semantics, and discovery and intervention techniques from program profiles,
and, thus, techniques for program profiling do not trivially apply here. We
treat data as a first-class citizen in computational pipelines, while
considering the program as a black box.

\smallskip

\paragraph{Contributions.} In this paper, we make the following contributions:

\begin{itemize}

	\item We formalize the novel problem of identifying root causes (and fixes)
of the disconnect between data and data-driven systems in terms of data
profiles (and interventions). (Sec~\ref{sec:problem})

	\item We design a set of data profiles that are common root causes of
data-driven system malfunctions, and discuss their discovery and intervention
techniques based on available technology. (Sec~\ref{sec:profile})

	\item We design and develop a novel interventional approach to pinpoint
causally verified root causes. The approach leverages a few properties of the
data profiles to efficiently explore the space of candidate root causes with a
small number of interventions. Additionally, we develop an efficient
group-testing-based algorithm that further reduces the number of required
interventions. (Sec~\ref{sec:algorithm})

	\item We evaluate \textsc{DataExposer}\xspace on three real-world applications, where
data profiles are responsible for causing system malfunction, and demonstrate
that \textsc{DataExposer}\xspace successfully explains the root causes with a very small number
of interventions (< $5$). Furthermore, \textsc{DataExposer}\xspace requires $10$--$1000\times$ fewer
interventions when compared against two state-of-the-art techniques for
root-cause analysis: BugDoc~\cite{bugdoc} and Anchors~\cite{anchors}. Through
an experiment over synthetic pipelines, we further show that the number of
required interventions by \textsc{DataExposer}\xspace increases sub-linearly with the number of
discriminative profiles, thanks to our group-testing-based approach.
(Sec~\ref{sec:experiment})

\end{itemize}
\subsection{Quantifying System Malfunction}
To measure how much the system malfunctions over a dataset, we use the
\emph{malfunction score}.

\begin{definition}[Malfunction score]
	%
	 Let $D \subseteq \mathbf{Dom}^m$ be a dataset, and $S$ be a system operating on
	 $D$. The malfunction score $m_S(D) \in [0, 1]$ is a real value that
	 quantifies how much $S$ \emph{malfunctions} when operating on $D$.
	 %
\end{definition}

The malfunction score $m_S(D)=0$ indicates that $S$ functions properly over $D$
and a higher value indicates a higher degree of malfunction, with $1$
indicating extreme malfunction.
A threshold parameter $\tau$ defines the acceptable degree of malfunction and
translates the continuous notion of malfunction to a Boolean value. If $m_S(D)
\le \tau$, then $D$ is considered to pass with respect to $S$; otherwise, there
exists a mismatch between $D$ and $S$, whose cause (and fix) we aim to expose.

\begin{example}
	%
	For a binary classifier, its misclassification rate (additive inverse of
accuracy) over a dataset can be used as a malfunction score. Given a dataset
$D$, if a classifier $S$ makes correct predictions for tuples in $D' \subseteq
D$ , and incorrect predictions for the remaining tuples, then $S$ achieves
accuracy $\frac{\lvert D' \rvert}{\lvert D \rvert}$, and, thus, $m_S(D) =
1-\frac{\lvert D' \rvert}{\lvert D \rvert}$.
\end{example}

\begin{example}
	%
	In fair classification, we can use disparate impact~\cite{ibmaif360}, which
is defined by the ratio between the number of tuples with favorable outcomes
within the unprivileged and the privileged groups, to measure malfunction.
	%
\end{example}

\subsection{Profile-Violation-Transformation (PVT\xspace)}
Once we detect existence of a mismatch, the next step is to investigate its
cause. We characterize the issues in a dataset that are responsible for the
mismatch between the dataset and the system using \emph{data profiles}.
Structure or schema of data profiles is given by profile \emph{templates},
which contains holes for parameters. Parameterizing a profile template gives us
a \emph{concretization} of the corresponding profile ($P$). Given a dataset
$D$, we use existing data-profiling techniques to find out parameter values to
obtain concretized data profiles, such that $D$ satisfies the concretized
profiles. To evaluate how much a dataset $D$ satisfies or violates a data
profile, we need a corresponding violation function ($V$). Violation functions
provide \emph{semantics} of the data profiles. Finally, to alter a dataset $D$,
with respect to a data profile and the corresponding violation function, we
need a transformation function ($T$). Transformation functions provide the
intervention mechanism to alter data profiles of a dataset and suggest fix to
remove the cause of malfunction. \textsc{DataExposer}\xspace requires the following three
components over the schema $\langle$\textbf{P}rofile, \textbf{V}iolation
function, \textbf{T}ransformation function$\rangle$, PVT\xspace in short:

\begin{enumerate}

	\item $P$: a (concretized) profile along with its parameters, which follows
the schema $\langle$profile type, parameters$\rangle$.

	\item$V(D, P)$: a violation function that computes how much the dataset $D$
violates the profile $P$ and returns a violation score.

	\item $T (D, P, V)$: a transformation function that transforms the dataset
$D$ to another dataset $D'$ such that $D'$ no longer violates the profile $P$
with respect to the violation function $V$. (When clear from the context, we
omit the parameters $P$ and $V$ when using the notation for transformation
functions.)

\end{enumerate}

\smallskip

For a PVT\xspace triplet $X$, we define $X_P$ as its profile, $X_V$ as the violation
function and $X_T$ as the transformation function. We provide examples and
additional discussions on data profiles, violation functions, and
transformation functions in Section~\ref{sec:profile}.

\subsubsection{Data Profile}

Intuitively, data profiles encode dataset characteristics. They can refer to a
single attribute (e.g., mean of an attribute) or multiple attributes (e.g.,
correlation between a pair of attributes, functional dependencies, etc.).

\begin{definition}[Data Profile]

	Given a dataset $D$, a data profile $P$ denotes properties or constraints
that tuples in $D$ (collectively) satisfy.

\end{definition}

\subsubsection{Profile Violation Function}
To quantify the degree of violation a dataset incurs with respect to a data
profile, we use a \emph{profile violation function} that returns a numerical
violation score.

\begin{definition}[Profile violation function]
	%
	Given a dataset $D$ and a data profile $P$, a \emph{profile violation
function} $V(D, P) \mapsto [0, 1]$ returns a real value that quantifies how much
$D$ violates $P$.
	%
\end{definition}

$V(D, P) = 0$ implies that $D$ fully complies with $P$ (does not violate it at
all). In contrast, $V(D, P) > 0$ implies that $D$ violates $P$. The higher the
value of $V(D, P)$, the higher the profile violation.

\begin{figure*}
	\centering
	\renewcommand{\arraystretch}{1.2}
	\resizebox{\textwidth}{!}{
	\begin{tabular}{
		l
		>{\columncolor{vlightgray}}l
		>{\columncolor{vlightgray}}l
		>{\columncolor{vlightgray}}p{1.5cm}
		>{\columncolor{vlightgray}}p{3.3cm}
		>{\columncolor{vlightgray}}p{3.3cm}
		>{\columncolor{vlightgray}}p{4.3cm}
		>{\columncolor{vlightgray}}l
	}

		\toprule
		& \multicolumn{1}{l}{}
		& \multicolumn{1}{l}{\textbf{Profile}}
		& \multicolumn{1}{l}{\textbf{Data type}}
		& \multicolumn{1}{l}{\textbf{Discovery over $D$}}
		& \multicolumn{1}{l}{\textbf{Interpretation}}
		& \multicolumn{1}{l}{\textbf{Violation by $D$}}
		& \multicolumn{1}{l}{\textbf{Transformation function}}
		\\

 		\midrule

		\rowcolor{white}
		& $\mathbf{1}$
		& \begin{tabular}{@{}l} $\langle$\pl{$\textsc{Domain}\xspace$}, $A_j$, $\mathbb{S} \rangle$\end{tabular}
		& \begin{tabular}{@{}l}Categorical\end{tabular}
		&
				\begin{tabular}{@{}l}
					$\mathbb{S} = \displaystyle\bigcup_{t \in D} \{ t.A_j \}$
				\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}Values are drawn from a specific domain.\end{tabular}
		& \begin{tabular}{@{}l}$\frac{\sum_{t\in D} \llbracket t.A_j \;  \not\in \; \mathbb{S}\rrbracket}{\lvert D \rvert}$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Map  values outside $\mathbb{S}$ to values in $\mathbb{S}$ using domain knowledge.\end{tabular}
		\\

		& $\mathbf{2}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Domain}\xspace$}, $A_j$, $\mathbb{S}\rangle$\end{tabular}
		& \begin{tabular}{@{}l}Numerical\end{tabular}
		&
			\begin{tabular}{@{}l@{$\;\;$}ll}
			$\mathbb{S}$ & = & $[\mathtt{lb}, \mathtt{ub}]$,	where\\
			$\mathtt{lb}$ & = & $\displaystyle\min_{t \in D} t.A_j$\\
			$\mathtt{ub}$ & = & $\displaystyle\max_{t \in D} t.A_j$
		  \end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}Values lie within a bound.\end{tabular}
		& \begin{tabular}{@{}l}$\frac{\sum_{t\in D} \llbracket t.A_j \;  \not\in \; \mathbb{S}\rrbracket}{\lvert D \rvert}$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}
			(1)~Use monotonic linear transformation and transform all values.\\
			(2)~Use winsorization techniques to replace the violating values only.
		\end{tabular}
		\\

		\rowcolor{white}
		\multirow{-7}{*}{\footnotesize\rotatebox{90}{\makecell[l]{\textbf{strict}}}}
		& $\mathbf{3}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Domain}\xspace$}, $A_j$, $\mathbb{S} \rangle$\end{tabular}
		& \begin{tabular}{@{}l}Text\end{tabular}
		&
		\begin{tabular}{@{}l}
			$\mathbb{S} = [t \in \texttt{Dom}_j \mid t \models \mathbb{P}]$,\\
			where $\mathbb{P}$ is a regex\\
			over $D.A_j$ learned via\\
			pattern discovery~\cite{pattern}
		\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}Values satisfy a regular expression or length of values lie within a bound.\end{tabular}
		& \begin{tabular}{@{}l}$\frac{\sum_{t\in D} \llbracket t.A_j \;  \not\in \; \mathbb{S}\rrbracket}{\lvert D \rvert}$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Minimally alter data to satisfy regular expression. For example, insert (remove) characters to increase (reduce) text length.\end{tabular}
		\\

		\toprule
		\toprule

		& $\mathbf{4}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Outlier}\xspace$}, $A_j$, {$O$}, $\theta \rangle$\end{tabular}
		& \begin{tabular}{@{}l}All\end{tabular}
		&
				\begin{tabular}{@{}l}
					$\theta = \frac{\sum_{t\in D} \llbracket O(D.A_j, t.A_j) \rrbracket}{\lvert D \rvert}$,\\
					where $O$ is learned from\\
					$D.A_j$'s distribution~\cite{hellerstein2008quantitative}
				\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}Fraction of outliers within an attribute does not exceed a threshold.\end{tabular}
		& \begin{tabular}{@{}l}$\max\Big(0, \frac{\sum_{t\in D} \llbracket O(D.A_j, t.A_j) \rrbracket - \theta \cdot \lvert D \rvert }{\lvert D \rvert \cdot (1 - \theta)} \Big)$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}
		(1)~Replace outliers with the expected value (mean, median, mode) of the attribute.\\
		(2)~Map all values above (below) the maximum (minimum) limit with highest (lowest) valid value.
		\end{tabular}
		\\

		\rowcolor{white}
		& $\mathbf{5}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Missing}\xspace$}, $A_j$, $\theta \rangle$\end{tabular}
		& \begin{tabular}{@{}l}All\end{tabular}
		& \begin{tabular}{@{}l}$\theta = \frac{\sum_{t\in D} \llbracket t.A_j = \mathtt{NULL} \rrbracket}{\lvert D \rvert}$\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}Fraction of missing values within an attribute does not exceed a threshold.\end{tabular}
		& \begin{tabular}{@{}l}$\max\Big(0, \frac{\sum_{t\in D} \llbracket t.A_j = \mathtt{NULL}  \rrbracket - \theta \cdot \lvert D \rvert }{\lvert D \rvert \cdot (1 - \theta)} \Big)$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Use missing value imputation techniques.\end{tabular}

		\\

		\multirow{-8}{*}{\footnotesize\rotatebox{90}{\makecell[l]{\textbf{thresholded by data coverage}}}}
		& $\mathbf{6}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Selectivity}\xspace$}, $\mathbb{{P}}, \theta \rangle$\end{tabular}
		& \begin{tabular}{@{}l}All\end{tabular}
		& \begin{tabular}{@{}l}$\theta = \frac{\lvert \sigma_\mathbb{P}(D) \rvert}{\lvert D \rvert}$\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}Fraction of tuples satisfying a given constraint (selection predicate) does not exceed a threshold.\end{tabular}
		& \begin{tabular}{@{}l}$\max\Big(0, \frac{\lvert \sigma_\mathbb{P}(D) \rvert - \theta \cdot \lvert D \rvert }{\lvert D \rvert \cdot (1 - \theta)} \Big)$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Undersample tuples that satisfy the predicate $\mathbb{P}$.\end{tabular}

		\\

		\toprule
		\toprule

		\rowcolor{white}
		& $\mathbf{7}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Indep}\xspace$}, $A_j$, $A_k$, $\alpha \rangle$\end{tabular}
		& \begin{tabular}{@{}l}Categorical\end{tabular}
		&
			\begin{tabular}{@{}l}
				$\alpha$ denotes Chi-squared\\
				statistic between $D.A_j$\\
				and $D.A_k$
			\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}} $\chi^2$ statistic between a pair of attributes is below a threshold	with a p-value $\le$ 0.05.\end{tabular}
		&
			\begin{tabular}{@{}l}
				$1 - e^{-\max(0, \chi^2(D.A_j, D.A_k) - \alpha)}$\\
			\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Modify attribute values to remove/reduce dependence.\end{tabular}
		\\

		& $\mathbf{8}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Indep}\xspace$}, $A_j$, $A_k$, $\alpha \rangle$\end{tabular}
		& \begin{tabular}{@{}l}Numerical\end{tabular}
		&
			\begin{tabular}{@{}l}
				$\alpha$ denotes Pearson\\
				correlation coefficient\\
				between $D.A_j$ and $D.A_k$
			\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}} PCC between a pair attributes is below a threshold with a p-value $\le$ 0.05.\end{tabular}
		&
			\begin{tabular}{@{}l}
				$\max\big(0, \frac{\lvert \mathtt{PCC}(D.A_j, D.A_k) \rvert - \lvert \alpha \rvert}{1 - \lvert \alpha \rvert}\big)$
			\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Add noise to remove/reduce\\dependence between attributes.\end{tabular}
		\\

		\rowcolor{white}
		\multirow{-8}{*}{\footnotesize\rotatebox{90}{\makecell[l]{\textbf{thresholded by parameter}}}}
		& $\mathbf{9}$
		& \begin{tabular}{@{}l}$\langle$\pl{$\textsc{Indep}\xspace$}, $A_j$, $A_k, \alpha \rangle$\end{tabular}
		& \begin{tabular}{@{}l}Categorical,\\ numerical\end{tabular}
		& \begin{tabular}{@{}l}Learn causal graph and  \\causal coefficients ($\alpha$)\\using TETRAD~\cite{scheines1998tetrad}\end{tabular}
		& \begin{tabular}{@{}p{3.3cm}}A causal relationship between a pair of attributes is unlikely (with causal coefficient less than $\alpha$).\end{tabular}
		& \begin{tabular}{@{}l}$\max\big(0, \frac{|\mathtt{coeff}( A_j, A_k)| - \alpha}{1 - \alpha}\big)$\end{tabular}
		& \begin{tabular}{@{}p{4.3cm}}Change data distribution to modify the causal relationship.\end{tabular}
		\\

			%

		\bottomrule

	\end{tabular}
	}
	%
	\vspace{-3mm}
\caption{A list of PVT\xspace triplets that we consider in this paper, their syntax, and semantics.}
	\vspace{-2mm}
\label{fig:pvt}
\end{figure*}

\subsubsection{Transformation Function} In our work, we assume knowledge of a
passing dataset for which the system functions properly, and a failing dataset
for which the system malfunctions. Our goal is to identify which profiles of
the failing dataset caused the malfunction. We seek answer to the question: how
to ``fix'' the issues within the failing dataset such that the system no longer
malfunctions on it (mismatch is resolved)? To this end, we apply
\emph{interventional causal reasoning}: we intervene on the failing
dataset by altering its attributes such that the profile of the altered dataset
matches the corresponding correct profile of the passing dataset.
To perform intervention, we need \emph{transformation functions} with the
property that it should push the failing dataset ``closer'' to the passing
dataset in terms of the profile that we are  interested to alter. More
formally, after the transformation, the profile violation score should
decrease.

\begin{definition}[Transformation function]
	%
Given a dataset $D$, a data profile $P$, and a violation function $V$, a
transformation function $T (D, P, V) \mapsto 2^{\mathbf{Dom}^m}$ alters $D$ to
produce $D'$ such that $V(D', P) = 0$.
	%
\end{definition}
A dataset can be transformed by applying a series of transformation functions,
for which we use the composition operator ($\circ$).

\begin{definition}[Composition of transformations]
	%
	\begin{sloppypar} Given a dataset $D$, and two PVT\xspace triplets $X$ and $Y$,
$(X_T \circ Y_T)(D) = X_T(Y_T(D))$. Further, if $D'' = (X_T \circ
Y_T)(D)$, then $ X_V(D'', X_P) = Y_V(D'', Y_P) = 0$. \end{sloppypar}
\end{definition}

\subsection{Problem Definition} We expose a set of PVT\xspace triplets for explaining
the system malfunction. The explanation contains both the \emph{cause} and the
corresponding \emph{fix}: profile within a PVT\xspace triplet indicates the cause of
system malfunction with respect to the corresponding transformation function,
which suggests the fix.

\begin{definition}[Explanation of system malfunction]
	%
	Given
	\begin{enumerate}
		\item a system $S$ with a mechanism to compute $m_S(D)$ $\forall D \subseteq \mathbf{Dom}^m$,
		\item an allowable malfunction threshold $\tau$,
		\item a passing dataset $D_{\mathit{pass}}$ for which $m_S(D_{\mathit{pass}}) \le \tau$,
		\item a failing dataset $D_{\mathit{fail}}$ for which $m_S(D_{\mathit{fail}}) > \tau$, and

		\item \begin{sloppypar} a set of candidate PVT\xspace triplets $\mathcal{X}$ such that $\forall X \in \mathcal{X} \;\;$  $X_V(D_{\mathit{pass}}, X_P) = 0 \wedge X_V(D_{\mathit{fail}}, X_P) > 0$,\end{sloppypar}
	\end{enumerate}
 	%
	the explanation of the malfunction of $S$ for $D_{\mathit{fail}}$, but not
for $D_{\mathit{pass}}$, is a set of PVT\xspace triplets ${\mathcal{X}^{*}} \subseteq {\mathcal{X}}$
such that $m_S((\circ_{X \in {\mathcal{X}^{*}}}X_T)(D_{\mathit{fail}})) \le \tau$.
\end{definition}

\looseness-1 Informally, ${\mathcal{X}^{*}}$ explains the cause: why $S$ malfunctions for
$D_{\mathit{fail}}$, but not for $D_{\mathit{pass}}$. More specifically,
\emph{failing to satisfy} the profiles of the PVT\xspace triplets in ${\mathcal{X}^{*}}$ are the
causes of malfunction.
Furthermore, the transformation functions of the PVT\xspace triplets in ${\mathcal{X}^{*}}$ suggest
the fix: how can we repair $D_{\mathit{fail}}$ to eliminate system malfunction.
However, there could be many possible such ${\mathcal{X}^{*}}$ and we seek a \emph{minimal}
set ${\mathcal{X}^{*}}$ such that transformation for every $X \in {\mathcal{X}^{*}}$ is necessary to bring
down the malfunction score below the threshold $\tau$.

\begin{definition}[Minimal explanation of system malfunction]
	%
	Given a system $S$ that malfunctions for $D_{\mathit{fail}}$ and an allowable
malfunction threshold $\tau$, an explanation ${\mathcal{X}^{*}}$ of $S$'s malfunction for $D_{\mathit{fail}}$ is
minimal if $ \; \forall\mathcal{X}' \subset {\mathcal{X}^{*}} \; m_S((\circ_{X \in \mathcal{X}'}X_T)(D_{\mathit{fail}})) >
\tau$.
   %
\end{definition}

\looseness-1 Note that there could be multiple such minimal explanations and we
seek any one of them, as any minimal explanation exposes the causes of mismatch
and suggests minimal fixes.

\begin{problem}[Discovering explanation of mismatch between data and system]
	%
	 Given a system $S$ that malfunctions for $D_{\mathit{fail}}$ but functions
	 properly for $D_{\mathit{pass}}$, the problem of discovering the explanation
	 of mismatch between $D_{\mathit{fail}}$ and $S$ is to find a minimal
	 explanation that captures (1)~the cause why $S$ malfunctions for
	 $D_{\mathit{fail}}$ but not for $D_{\mathit{pass}}$ and (2)~how to repair
	 $D_{\mathit{fail}}$ to remove the malfunction.
	%
\end{problem}

\subsection{Example Scenario}%
Consider the task of predicting the attribute \texttt{high\_expenditure} to
determine if a customer should get a discount (Example~\ref{ex:one}). The
system calculates bias of the trained classifier against the unprivileged
groups (measured using disparate impact~\cite{ibmaif360}) as its malfunction
score. We seek the causes of mismatch between this prediction pipeline and
$\mathit{People_{fail}}$\xspace (Figure~\ref{fig:faildb}), for which the pipeline fails with a
malfunction score of $0.75$. We assume the knowledge of $\mathit{People_\mathit{pass}}$\xspace
(Figure~\ref{fig:passdb}), for which the malfunction score is $0.15$. The goal
is to identify a minimal set of PVT\xspace{}s whose transformation functions bring
down the malfunction score of $\mathit{People_{fail}}$\xspace below $0.20$.

\smallskip

(Step 1) The first goal is to identify the profiles whose parameters differ
between $\mathit{People_{fail}}$\xspace and $\mathit{People_\mathit{pass}}$\xspace. To do so, \textsc{DataExposer}\textsubscript{GRD}\xspace identifies the exhaustive
set of PVT\xspace{}s over $\mathit{People_\mathit{pass}}$\xspace and $\mathit{People_{fail}}$\xspace and discards the identical ones
(PVT\xspace{}s with identical profile-parameter values). We call the PVT\xspace{}s of the
passing dataset whose profile-parameter values differ over the failing dataset
\emph{discriminative} PVT\xspace{}s. Figure~\ref{fig:discpvt} lists a few profiles of
the discriminative PVT\xspace{}s w.r.t. $\mathit{People_\mathit{pass}}$\xspace and $\mathit{People_{fail}}$\xspace.

(Step 2) Next, \textsc{DataExposer}\textsubscript{GRD}\xspace ranks the set of discriminative PVT\xspace{}s based on their
likelihood of offering an explanation of the malfunction. Our intuition
here is that if an attribute $A$ is related to the malfunction, then many
PVT\xspace{}s containing $A$ in their profiles would differ between $\mathit{People_{fail}}$\xspace and
$\mathit{People_\mathit{pass}}$\xspace. Additionally, altering $A$ with respect to one PVT\xspace is likely to
automatically ``fix'' other PVT\xspace{}s associated with $A$.\footnote{Altering
values of $A$ w.r.t. a PVT\xspace may also increase violation w.r.t. some other
PVT\xspace{}s. However, for ease of exposition, we omit such issues in this example
and provide a detailed discussion on such issues in the appendix.} Based on this intuition, \textsc{DataExposer}\textsubscript{GRD}\xspace constructs a
\emph{bipartite graph}, called PVT\xspace-attribute graph, with discriminative PVT\xspace{}s on one side and data
attributes on
the other side (Figure~\ref{fig:dependency}).
In this graph, a PVT\xspace $X$ is connected to an attribute $A$ if $X_P$ is defined
over $A$.
In the bipartite graph, the degree of an attribute $A$ captures the number of
discriminative PVT\xspace{}s associated with $A$. During intervention, \textsc{DataExposer}\textsubscript{GRD}\xspace
prioritizes PVT\xspace{}s associated with a high-degree attributes. For instance,
since $\mathtt{high\_expenditure}$ has the highest degree in
Figure~\ref{fig:dependency}, PVT\xspace{}s associated with
it are considered for intervention before others.

\looseness-1 (Step 3) \textsc{DataExposer}\textsubscript{GRD}\xspace further ranks the subset of the discriminative
PVT\xspace{}s that are connected to the highest-degree attributes in the PVT\xspace-attribute
graph based on their \emph{benefit score}. Benefit score of a PVT\xspace $X$ encodes
the likelihood of reducing system malfunction when the failing dataset is
altered using $X_T$. The benefit score of $X$ is estimated from (1)~the
violation score that the failing dataset incurs w.r.t. $X_V$, and (2)~the
number of tuples in the failing dataset that are altered by $X_T$. For example,
to break the dependence between \texttt{high\_expenduture} and \texttt{race},
the transformation corresponding to $\textsc{Indep}\xspace$ modifies five tuples in
$\mathit{People_{fail}}$\xspace by perturbing (adding noise to) \texttt{high\_expenditure}. In
contrast, the transformation for $\textsc{Missing}\xspace$ needs to change only one value
($t_6$ or $t_{10}$). Since more tuples are affected by the former, it has
higher likelihood of reducing the malfunction score. The intuition behind this
is that if a transformation alters more tuples in the failing dataset, the more
likely it is
to reduce the malfunction score.
This holds particularly in
applications where the system optimizes aggregated
statistics such as accuracy, recall, F-score, etc.

\begin{figure}[t]
	\centering
	\includegraphics[width=1\columnwidth]{Figures/drawing_bipartite.pdf}
	\vspace{-5mm}
	\caption{PVT\xspace-attribute graph. The attribute
	\texttt{high\_expenditure} is associated
	with two discriminative PVT\xspace{}s. For ease of exposition, we only show profile within a PVT\xspace to denote the entire PVT\xspace.
	}
	\vspace{-5mm}
	\label{fig:dependency}
\end{figure}

\begin{figure}
	\centering
	\resizebox{1\columnwidth}{!}{
	\setlength{\tabcolsep}{1mm}
	\begin{tabular}{llc|c||}
		\toprule
$\mathit{People_\mathit{pass}}$\xspace	& $\mathit{People_{fail}}$\xspace\\
		\midrule
\hl{$\langle \textsc{Domain}\xspace, \mathtt{age}, [22, 51] \rangle$}&	\hl{$\langle \textsc{Domain}\xspace, \mathtt{age}, [20, 60] \rangle$}\\
\hline
\hl{$\langle \textsc{Missing}\xspace, \mathtt{zip\_code}, 0.11 \rangle$}& \hl{$\langle \textsc{Missing}\xspace, \mathtt{zip\_code}, 0.2 \rangle$}\\\hline
 \hl{$\langle \textsc{Indep}\xspace,\mathtt{race}, \mathtt{high\_expenditure}, 0.04 \rangle$}& \hl{$\langle \textsc{Indep}\xspace,\mathtt{race}, \mathtt{high\_expenditure},0.67 \rangle$}\\\hline
 \hl{$\langle \textsc{Selectivity}\xspace, \mathtt{gender} = \text{F}$} &\hl{$\langle \textsc{Selectivity}\xspace, \mathtt{gender} = \text{F}$} \\
\hl{$ \wedge \mathtt{high\_expenditure} = \text{yes}, 0.44 \rangle$}&\hl{$\wedge \mathtt{high\_expenditure} = \text{yes} , 0.1 \rangle$}\\
		\bottomrule
	\end{tabular}
	}
	%
	\vspace{-3mm}
	\caption{A list of PVT\xspace{}s that discriminate $\mathit{People_\mathit{pass}}$\xspace
(Figure~\ref{fig:passdb}) and $\mathit{People_{fail}}$\xspace (Figure~\ref{fig:faildb}) based on the
scenario of Example~\ref{ex:one} . We omit the violation and transformation
functions for ease of exposition.}
	\vspace{-5mm}
	%
	\label{fig:discpvt}
\end{figure}

(Step 4) \textsc{DataExposer}\textsubscript{GRD}\xspace starts intervening on $\mathit{People_{fail}}$\xspace using the transformation of
the PVT\xspace corresponding to the profile \hl{$\langle \textsc{Indep}\xspace,\mathtt{race},
\mathtt{high\_expenditure}, 0.04 \rangle$} as its transformation offers the
most likely fix. Then, it evaluates the malfunction of the system over the
altered version of $\mathit{People_{fail}}$\xspace. Breaking the dependence between
\texttt{high\_expenditure} and \texttt{race} helps reduce bias in the trained
classifier, and, thus, we observe a malfunction score of $0.35$ w.r.t. the
altered dataset. This exposes the first explanation of malfunction.

(Step 5) \textsc{DataExposer}\textsubscript{GRD}\xspace then removes the processed PVT\xspace (\textsc{Indep}\xspace) from the
PVT\xspace-attribute graph, updates the graph according to the altered dataset, and
re-iterates steps 2--4. Now the PVT\xspace corresponding to the profile
$\textsc{Selectivity}\xspace$ is considered for intervention as it has the highest benefit
score. To do so, \textsc{DataExposer}\textsubscript{GRD}\xspace over-samples tuples corresponding to female customers
with $\mathtt{high\_expenditure} = yes$. This time, \textsc{DataExposer}\textsubscript{GRD}\xspace intervenes on the
transformed dataset obtained from the previous step. After this transformation,
bias of the learned classifier further reduces and the malfunction score falls
below the required threshold. Therefore, with these two interventions,
\textsc{DataExposer}\textsubscript{GRD}\xspace is able to expose two issues that caused undesirable behavior of the
prediction model trained on $\mathit{People_{fail}}$\xspace.

\looseness-1 (Step 6) \textsc{DataExposer}\textsubscript{GRD}\xspace identifies an initial explanation over two
PVT\xspace{}s: \textsc{Indep}\xspace and \textsc{Selectivity}\xspace. However, to verify whether it is a
minimal, \textsc{DataExposer}\textsubscript{GRD}\xspace tries to drop from it one PVT\xspace at a time to obtain a proper
subset of the initial explanation that is also an explanation. This procedure
guarantees that the explanation only consists of PVT\xspace{}s that are
\emph{necessary}, and, thus, is minimal. In this case, both $\textsc{Indep}\xspace$ and
$\textsc{Selectivity}\xspace$ are necessary, and, thus, are part of the minimal explanation.
\textsc{DataExposer}\textsubscript{GRD}\xspace finally reports the following as a minimal explanation of the
malfunction, where failure to satisfy the profiles is the cause and the
transformations indicate fix (violation and transformation functions are
omitted).
\begin{align*}
	\{ &\langle \textsc{Indep}\xspace,\mathtt{race}, \mathtt{high\_expenditure}, 0.04
\rangle, \\
&\langle \textsc{Selectivity}\xspace, \mathtt{gen\-der} = \text{F} \wedge
\mathtt{high\_expenditure} = \text{yes}, 0.44 \rangle\}
\end{align*}

\subsection{Assumptions and Observations\label{sec:observations}} We now
proceed to describe our intervention algorithms more formally. We first state
our assumptions and then proceed to present our observations that lead to the
development of our algorithms.

\subsubsection*{Assumptions} \textsc{DataExposer}\xspace makes the following assumptions:

(A1) The ground-truth explanation of malfunction is captured by at least one of
the discriminative PVT\xspace{}s. This assumption is prevalent in software-debugging
literature where program predicates are assumed to be expressive enough to
capture the root causes~\cite{aid, liblit2005scalable}.

(A2) If the fix corresponds to a composition of transformations, then the
malfunction score achieved after applying the composition of transformations is
less than the malfunction score achieved after applying any of the
constituents, and all these scores are less than the malfunction score of the
original dataset. For example, consider two discriminative PVT\xspace{}s $X$ and $Y$
and a failing dataset $D_{\mathit{fail}}$. Our assumption is that if $\{X, Y\}$
corresponds to a minimal explanation, then $m_S((Y_T \circ
X_T)(D_{\mathit{fail}})) < m_S(X_T(D_{\mathit{fail}})) <
m_S(D_{\mathit{fail}})$ and $m_S((Y_T \circ X_T)(D_{\mathit{fail}})) <
m_S(Y_T(D_{\mathit{fail}})) < m_S(D_{\mathit{fail}})$.

Intuitively, this assumption states that $X$ and $Y$ have consistent
(independent) effect on reducing the malfunction score, regardless of whether
they are intervened together or individually. If this assumption does not hold,
\textsc{DataExposer}\xspace can still work with additional knowledge about multiple failing and
passing datasets. More details are in the appendix.

\subsubsection*{Observations} We make the following
observations:

(O1) If the ground-truth explanation of malfunction corresponds to an
attribute, then multiple PVT\xspace{}s that involve the same attribute are likely to
differ across the passing and failing datasets. This observation motivates us
to prioritize interventions based on PVT\xspace{}s that are associated with
high-degree attributes in the PVT\xspace-attribute graph. Additionally, intervening
on the data based on one such PVT\xspace is likely to result in an automatic ``fix''
of other PVT\xspace{}s connecting via the high-degree attribute. For example, adding
noise to \texttt{high\_expenditure} in Example~\ref{ex:one} breaks its
dependence with not only \texttt{race} but also with other attributes.

(O2) The PVT\xspace for which the failing dataset incurs higher violation score is
more likely to be a potential explanation of malfunction.

(O3) A transformation function that affects a large number of data tuples is
 likely to result in a higher reduction in the malfunction score, after the
transformation is applied.

\smallskip

\noindent \textbf{PVT\xspace-attribute graph.} \textsc{DataExposer}\xspace leverages observation O1 by
constructing a bipartite graph ($G_{PA}$), \emph{called PVT\xspace-attribute graph,} with
all attributes $A \in \mathcal{R}(D)$ as nodes on one side and all
discriminative PVT\xspace{}s $X\in \mathcal{X}$ on the other side. An attribute $A$ is
connected to a PVT\xspace $X$ if and only if $X_P$ has $A$ as one of its parameters.
E.g., Figure~\ref{fig:dependency} shows the PVT\xspace-attribute graph w.r.t.
$\mathit{People_{fail}}$\xspace and $\mathit{People_\mathit{pass}}$\xspace (Example~\ref{ex:one}). In this graph, the PVT\xspace
corresponding to \pl{$\langle \textsc{Indep}\xspace, \mathtt{race},
\mathtt{high\_expenditure}\rangle$} is connected to two attributes,
\texttt{race} and \texttt{high\_expenditure}. Intuitively, this graph captures
the dependence relationship between PVT\xspace{}s and attributes, where an
intervention with respect to a PVT\xspace $X$ modifies an attribute $A$ connected to
it. If this intervention reduces the malfunction score then it could possibly
fix other PVT\xspace{}s that are connected to $A$.

\setlength{\textfloatsep}{5pt}
\setlength{\floatsep}{2pt}

\begin{algorithm}[t]
\KwIn{Failing dataset $D_{\mathit{fail}}$, passing dataset $D_{\mathit{pass}}$, malfunction score threshold $\tau$}
\KwOut{A minimal explanation set of PVT\xspace{}s ${\mathcal{X}^{*}}$}

$\mathcal{X}_f \leftarrow \textsc{Discover-PVT}(D_{\mathit{fail}})$ \label{lineone}\\
$\mathcal{X}_p \leftarrow \textsc{Discover-PVT}(D_{\mathit{pass}})$ \label{linetwo}\\
$\mathcal{X}_\cap \leftarrow \mathcal{X}_f\cap \mathcal{X}_p$ \label{linethree} \tcc*[f]{Common PVT\xspace{}s}\\
$\mathcal{X} \leftarrow \mathcal{X}_p \setminus \mathcal{X}_\cap$ \label{linefour} \tcc*[f]{Discriminative PVT\xspace{}s}\\
$G_{PA} (V_G, E_G) \leftarrow \textsc{Construct-PVT\xspace-Attr-Graph}(\mathcal{X}, D_{\mathit{fail}})$ \label{linefive}\\
$B \leftarrow \textsc{Calculate-Benefit-Score}(\mathcal{X}, G_{PA}, D_{\mathit{fail}})$\label{linesix} \\
${\mathcal{X}^{*}} \leftarrow \emptyset$ \tcc*[f]{Initialize minimal explanation set to be empty}\label{lineseven}\\
$D \leftarrow D_{\mathit{fail}}$ \tcc*[f]{Initialize dataset to the failing dataset}\label{lineeight}\\
\While{$m_S(D) > \tau$\label{linenine}}
{
	$\mathcal{X}_{\mathtt{hda}} = \{ X {\in} \mathcal{X} | (X, A) {\in} E_G {\wedge} A {=} \argmax_{A \in \mathcal{R}(D)} deg_{G}(A)\}\!\!$ \label{lineten}
	\tcc*[f]{PVT\xspace{}s adjacent to high-degree attributes in $G_{PA}$}\\
	$X = \argmax_{X \in \mathcal{X}_{\mathtt{hda}}} B(X)$ \label{line11} \tcc*[f]{Highest-benefit PVT\xspace}\\
	$\Delta \leftarrow m_S(D)- m_S(X_T(D))$ \label{line12} \tcc*[f]{Malfunction reduction}\\
	$G_{PA}\leftarrow G_{PA}.\textsc{Remove}(X)\label{line13}$ \tcc*[f]{Update $G_{PA}$} \\
	\If(\tcc*[f]{Reduces malfunction}){$\Delta > 0$\label{line14}}
	{

		 $D \leftarrow X_T(D)$ \tcc*[f]{Apply transformation}\\
		  $G_{PA}.\textsc{Update}(D)$ \tcc*[f]{Update the PVT\xspace-attribute graph }\\
		 $B.\textsc{Update}(D)$ \tcc*[f]{Update benefit scores}\\
		 ${\mathcal{X}^{*}} \leftarrow {\mathcal{X}^{*}} \cup \{ X\}$ \tcc*[f]{Add $P$ to explanation set}\\
		 $\mathcal{X} \leftarrow \mathcal{X} \setminus \{ X\}$\label{line18} \tcc*[f]{Remove $P$ from the candidates}\\
	}
}
${\mathcal{X}^{*}}$ = \textsc{Make-Minimal}(${\mathcal{X}^{*}}$)\label{line19} \tcc*[f]{Obtain minimality of ${\mathcal{X}^{*}}$}\\
\Return ${\mathcal{X}^{*}}$ \tcc*[f]{${\mathcal{X}^{*}}$ is a minimal explanation}

\caption{\textsc{DataExposer}\textsubscript{GRD}\xspace (greedy)}
\label{alg:datadebuggreedy}
\end{algorithm}

\smallskip \noindent \textbf{Benefit score calculation.} \textsc{DataExposer}\xspace uses the
aforementioned observations to compute a benefit score for each PVT\xspace to model
their likelihood of reducing system malfunction if the corresponding
transformation is used to modify the failing dataset $D_{\mathit{fail}}$.
Intuitively, it assigns a high score to a PVT\xspace with a high violation score (O2)
and if the corresponding transformation function modifies a large number of
tuples in the dataset (O3). Formally, the benefit score of a PVT\xspace $X$ is
defined as the product of violation score of $D_{\mathit{fail}}$ w.r.t. $X_V$
and the ``coverage'' of $X_T$. The coverage of $X_T$ is defined as the
fraction of tuples that it modifies. Note that the benefit calculation
procedure acts as a proxy of the likelihood of a PVT\xspace to offer an explanation,
without actually applying any intervention.

\subsection{Greedy Approach} Algorithm~\ref{alg:datadebuggreedy} presents the
pseudocode of our greedy technique \textsc{DataExposer}\textsubscript{GRD}\xspace, which takes a passing dataset
$D_{\mathit{pass}}$ and a failing dataset $D_{\mathit{fail}}$ as input and
returns the set of PVT\xspace{}s that corresponds to a minimal explanation of system
malfunction.

\begin{description}
	%
\item[\algoexp{Lines~\ref{lineone}-\ref{linetwo}}] Identify two sets of PVT\xspace{}s
$\mathcal{X}_f$ and $\mathcal{X}_p$ satisfied by $D_{\mathit{fail}}$ and $D_{\mathit{pass}}$, respectively.

\item[\algoexp{Lines~\ref{linethree}-\ref{linefour}}] Discard the PVT\xspace{}s
$\mathcal{X}_f \cap \mathcal{X}_p$ from $\mathcal{X}_p$ and consider the remaining discriminative ones
$\mathcal{X}\equiv \mathcal{X}_p\setminus \mathcal{X}_f$ as candidates for potential explanation of system malfunction.

\item[\algoexp{Line~\ref{linefive}}] Compute the PVT\xspace-attribute graph $G_{PA}$,
where the candidate PVT\xspace{}s $\mathcal{X}$ correspond to nodes on one side and the data
attributes correspond to nodes on the other side.

\item[\algoexp{Line~\ref{linesix}}] Calculate the benefit score of each
discriminative PVT\xspace $X \in \mathcal{X}$ w.r.t. $D_{\mathit{fail}}$. This procedure
relies on the violation score using the violation function of the PVT\xspace and the
coverage of the corresponding transformation function over $D_{\mathit{fail}}$.

\item[\algoexp{Line~\ref{lineseven}-\ref{lineeight}}] Initialize the solution set
$\mathcal{X}^*$ to $\emptyset$ and the dataset to perform intervention on $D$
to the failing dataset $\mathcal{D}_{\mathit{fail}}$. In subsequent steps, $\mathcal{X}^*$ will
converge to a minimal explanation set and $D$ will be transformed to a dataset for
which the system passes.

\item[\algoexp{Line~\ref{linenine}}] Iterate over the candidate PVT\xspace{}s $\mathcal{X}$
until the dataset $D$ (which is being transformed iteratively) incurs an
acceptable violation score (less than the allowable
threshold $\tau$).

\item[\algoexp{Line~\ref{lineten}}] Identify the subset of PVT\xspace{}s
$\mathcal{X}_{\mathtt{hda}}\subseteq \mathcal{X}$ such that all $X\in \mathcal{X}_{\mathtt{hda}}$ are
adjacent to at least one of the highest degree attributes in the current
PVT\xspace-attribute graph (Observation O1).

\item[\algoexp{Line~\ref{line11}}] Choose the PVT\xspace $X\in \mathcal{X}_{\mathtt{hda}}$
that has the maximum benefit.

\item[\algoexp{Line~\ref{line12}}] Calculate the reduction in malfunction score
if the dataset $D$ is transformed according to the transformation $X_T$.

\item[\algoexp{Line~\ref{line13}}] Remove $X$ from $G_{PA}$ as it has been
explored. \item[\algoexp{Lines~\ref{line14}-\ref{line18}}] If the malfunction
score reduces over $X_T(D)$, then $X$ is added to the solution set ${\mathcal{X}^{*}}$, and
$D$ is updated to $X_T(D)$, which is then used to update the PVT\xspace-attribute
graph and benefit of each PVT\xspace. The update procedure recalculates the benefit
scores of all PVT\xspace{}s that are connected to the attributes adjacent to $X$ in
$G_{PA}$.

\item[\algoexp{Line~\ref{line19}}] Post-process the set ${\mathcal{X}^{*}}$ to identify a
minimal subset that ensure that malfunction score remains less than the
threshold $\tau$. This procedure iteratively removes one PVT\xspace at a time (say
$X$) from ${\mathcal{X}^{*}}$ and recalculates the malfunction score over the failing dataset
$D_{\mathit{fail}}$ transformed according to the transformation functions of
the PVT\xspace{}s in the set $\mathcal{X}'= {\mathcal{X}^{*}}\setminus \{X\}$. If the transformed dataset
incurs a violation score less than $\tau$ then ${\mathcal{X}^{*}}$ is replaced with $\mathcal{X}'$.
\end{description}

\subsection{Group-testing-based Approach\label{sec:grouptest}} We now present
our second algorithm \textsc{DataExposer}\textsubscript{GT}\xspace, which performs group interventions to identify
the minimal explanation that exposes the mismatch between a dataset and a
system. The group intervention methodology is applicable under the following
assumption along with assumptions $A_1$ and $A_2$
(Section~\ref{sec:observations}).

(A3) The
malfunction score incurred after applying a composition of transformations is less than the
malfunction score incurred by the the original dataset if and only if at least one of the
constituent transformations reduces the malfunction
score.
For two PVT\xspace{}s $X$ and $Y$, $m_S((X_T \circ Y_T)(D_{\mathit{fail}})) <
m_S(D_{\mathit{fail}})$, iff $m_S(X_T (D_{\mathit{fail}})) <
m_S(D_{\mathit{fail}})$ or $m_S(Y_T (D_{\mathit{fail}})) <
m_S(D_{\mathit{fail}})$. Note that this assumption is crucial to consider group
interventions and is prevalent in the group-testing
literature~\cite{du2000combinatorial}.

\looseness-1 \textsc{DataExposer}\textsubscript{GT}\xspace follows the classical adaptive group testing (GT)
paradigm~\cite{du2000combinatorial} for interventions. To this end, it
iteratively partitions the set of discriminative PVT\xspace{}s into two ``almost''
equal subsets (when the number of discriminative PVT\xspace{}s is odd, then the size
of the two partitions will differ by one). During each iteration, all PVT\xspace{}s
in a partition are considered for intervention \textit{together} (group
intervention) to evaluate the change in malfunction score. If a partition does
not help reduce the malfunction score, all PVT\xspace{}s within that partition are
discarded. While traditional GT techniques~\cite{du2000combinatorial} would use
a random partitioning of the PVT\xspace{}s, \textsc{DataExposer}\textsubscript{GT}\xspace can leverage the dependencies
among PVT\xspace{}s (inferred from the PVT\xspace-attribute graph) to achieve more
effective partitioning. Intuitively, it is beneficial to assign all PVT\xspace{}s
whose transformations operate on the same attribute to the same partition,
which is likely to enable aggressive pruning of spurious PVT\xspace{}s that do not
reduce malfunction.

\looseness-1 \textsc{DataExposer}\textsubscript{GRD}\xspace captures the dependencies among PVT\xspace{}s by constructing
a PVT\xspace-dependency graph $G_{PD}$. Two PVT\xspace{}s $U$ and $V$ are connected by an
edge in $G_{PD}$ if they are connected via some attribute in $G_{PA}$. $G_{PD}$
is equivalent to $G_{PA}^2$ (transitive closure of $G_{PA}$), restricted to
PVT\xspace nodes (excluding the attribute nodes). This ensures that PVT\xspace{}s that are
associated via some attribute in $G_{PA}$ are connected in $G_{PD}$. \textsc{DataExposer}\textsubscript{GRD}\xspace
partitions $G_{PD}$ such that the number of connections (edges) between PVT\xspace{}s
that fall in different partitions are minimized.
More formally, we aim to construct two ``almost'' equal-sized partitions of
$\mathcal{X}$ such that the number of edges between PVT\xspace{}s from different partitions
are minimized, which maps to the problem of finding the \textit{minimum
bisection} of a graph~\cite{garey1974some}. The minimum bisection problem is
NP-hard~\cite{garey1974some} and approximate algorithms
exist~\cite{fernandes2018minimum,fellows2012local}. In this work, we use the
\textit{local search algorithm}~\cite{fellows2012local} (details are in the
appendix).

We proceed to demonstrate the benefit of using \textsc{DataExposer}\textsubscript{GT}\xspace as opposed to traditional GT with the following
example.

\begin{algorithm}[t]
\KwIn{Failing dataset $D_{\mathit{fail}}$, passing dataset $D_{\mathit{pass}}$, malfunction score threshold $\tau$}
\KwOut{A minimal explanation set of PVT\xspace{}s ${\mathcal{X}^{*}}$}

$\mathcal{X}_f \leftarrow \textsc{Discover-PVT}(D_{\mathit{fail}})$\\
$\mathcal{X}_p \leftarrow \textsc{Discover-PVT}(D_{\mathit{pass}})$ \\
$\mathcal{X}_\cap \leftarrow \mathcal{X}_f\cap \mathcal{X}_p$ \tcc*[f]{Common PVT\xspace{}s}\\
$\mathcal{X} \leftarrow \mathcal{X}_p \setminus \mathcal{X}_\cap$ \tcc*[f]{Discriminative PVT\xspace{}s}\\
$G_{PA} (V_G, E_G) \leftarrow \textsc{Construct-PVT\xspace-attr-Graph}(\mathcal{X}, D_{\mathit{fail}})$ \\
$D, {\mathcal{X}^{*}} \leftarrow  \textsc{Group-Test}(\mathcal{X},D_{\mathit{fail}}, G_{PA}^2, \tau)$ \tcc*[f]{Obtain an exp.}\\
${\mathcal{X}^{*}}$ = \textsc{Make-Minimal}(${\mathcal{X}^{*}}$) \tcc*[f]{Obtain minimality of ${\mathcal{X}^{*}}$}\\
\Return ${\mathcal{X}^{*}}$ \tcc*[f]{${\mathcal{X}^{*}}$ is a minimal cause}

\caption{\textsc{DataExposer}\textsubscript{GT}\xspace (group-testing-based)}
\label{alg:datadebuggrptest}
\end{algorithm}

\begin{algorithm}[t]
 \KwIn{Candidate PVT\xspace $\mathcal{X}$, dataset $D$, PVT\xspace-dependency graph~$G_{PD}$, malfunction score threshold $\tau$}
 \KwOut{A transformed dataset $D'$ and an explanation set of PVT\xspace{s} ${\mathcal{X}^{*}}$
 }

 ${\mathcal{X}^{*}} \leftarrow \emptyset$ \label{gp:lineone}\tcc*[f]{Initialize explanation set to be empty}\\

 \If(\label{gp:linetwo}\tcc*[f]{Only a single PVT\xspace is candidate}){$|\mathcal{X}| = 1$}
 {

 	\Return $T_{\mathcal{X}}(D), \mathcal{X}$\label{gp:linethree}

 }
 $\mathcal{X}^1,\mathcal{X}^2 \leftarrow  \textsc{Get-Min-Bisection} (G_{PD},\mathcal{X})$\label{gp:linefour} \tcc*[f]{Partition $\mathcal{X}$ }\\
 $\mathcal{M} \leftarrow m_S(D)$\label{gp:linefive}\tcc*[f]{Initial malfunction score}\\
 $\Delta_1 \leftarrow \mathcal{M} - m_S(\mathcal{X}^1_T(D))$\label{gp:linesix} \tcc*[f]{Malfunction reduction by $\mathcal{X}^1_T$}\\

 \If(\tcc*[f]{${\mathcal{X}^1}$ alone is insufficient}){$\mathcal{M} - \Delta_1 > \tau$\label{gp:lineseven}}
 {
 	$\Delta_2 \leftarrow \mathcal{M} {-} m_S(\mathcal{X}^2_T(D))$ \label{gp:lineeight}\tcc*[f]{Malfunction reduction by $\mathcal{X}^2_T$}\\
 }

 \If{$(\mathcal{M} - \Delta_1 \le \tau)$ OR $(\Delta_1 > 0$ AND $\mathcal{M} - \Delta_2 > \tau)$\label{gp:linenine}}
 {
 	\tcc*[f]{\mbox{${\mathcal{X}_1}$ is sufficient OR ${\mathcal{X}_1}$ helps AND ${\mathcal{X}_2}$ is insufficient}}\\
 	$D, \mathcal{X}' \leftarrow  \textsc{Group-Test}(\mathcal{X}_1,D, G_{PD})$\\
 	${\mathcal{X}^{*}} = {\mathcal{X}^{*}} \cup  \mathcal{X}'$ \tcc*[f]{Augment explanation set}

 	\If(\tcc*[f]{Malfunction is acceptable}){$\mathcal{M} - \Delta_1 \le \tau$}
 	{
 		\Return $D, {\mathcal{X}^{*}}$ \tcc*[f]{No need to check $\mathcal{X}_2$\label{gp:line13}}
 	}
 }

 \If(\tcc*[f]{$T_{\mathcal{X}_2}$ reduces malfunction}){$\Delta_2 > 0$\label{gp:line14}}
 {
 	$D, \mathcal{X}' \leftarrow  \textsc{Group-Test}(\mathcal{X}_2,D, G_{PD})$\\
 	${\mathcal{X}^{*}} = {\mathcal{X}^{*}} \cup  \mathcal{X}'$ \label{gp:line16}\tcc*[f]{Augment explanation set}
 }
 \Return $D, {\mathcal{X}^{*}}$

 \caption{\textsc{Group-Test}}
 \label{alg:grptest}
 \end{algorithm}

\setlength{\textfloatsep}{10pt}

\begin{example}

\looseness-1 Consider a set of $\;8$ PVT\xspace{}s $\mathcal{X}=\{X_1,\ldots,X_{8}\}$ where the ground-truth (minimal) explanation is either $\{X_1,X_6\}$ or
$\{X_4,X_8\}$ (disjunction). An example of steps for a  traditional adaptive GT approach is shown in
Figure~\ref{fig:grprandom}. In this case, it requires a total of $14$
interventions. Note that adaptive GT is a randomized algorithm and this example
demonstrates one such execution. However, we observed similar results for other
instances. In contrast to adaptive GT, \textsc{DataExposer}\textsubscript{GT}\xspace constructs a min-bisection of
the graph during each iteration: it does not partition $\{X_2,X_3\}$ and
$\{X_5,X_7\}$ as none of these PVT\xspace{}s help reduce the malfunction. Therefore,
it requires only $10$ interventions.
\end{example}

 Algorithm~\ref{alg:datadebuggrptest} presents the \textsc{DataExposer}\textsubscript{GT}\xspace algorithm. It
starts with a set of discriminative PVT\xspace{}s $\mathcal{X}$ and the PVT\xspace-attribute graph
$G_{PA}$. All candidate PVT\xspace{}s are then considered by \textsc{Group-Test}
subroutine to identify the explanation ${\mathcal{X}^{*}}$.

\smallskip

\paragraph{\textsc{Group-Test}.} Algorithm~\ref{alg:grptest} presents the procedure
 that takes the set of discriminative PVT\xspace{}s $\mathcal{X}$,  a failing dataset $D$, PVT\xspace-dependency graph $G_{PD}$,
 and the malfunction score threshold $\tau$ as input. It returns a transformed (fixed) dataset and an explanation.
\begin{description}
	%
\item[\algoexp{Lines~\ref{gp:lineone}}]  Initialize the solution set ${\mathcal{X}^{*}}$ to $\emptyset$.
\item[\algoexp{Lines~\ref{gp:linetwo}-\ref{gp:linethree}}] Return the candidate PVT\xspace set $\mathcal{X}$
if its cardinality is 1.
\item[\algoexp{Lines~\ref{gp:linefour}}]  Partition $\mathcal{X}$ into $\mathcal{X}_1$ and $\mathcal{X}_2$ using min-bisection of the PVT\xspace-dependency graph $G_{PD}$.
\item[\algoexp{Lines~\ref{gp:linefive}}] Calculate the malfunction score of the input dataset.
\item[\algoexp{Lines~\ref{gp:linesix}}] Calculate the reduction in malfunction score $\Delta_1$ if $D$ is intervened w.r.t. all PVT\xspace{}s $\mathcal{X}_1$.
\item[\algoexp{Lines~\ref{gp:lineseven}-\ref{gp:lineeight}}] If the malfunction exceeds $\tau$
even after intervening on $D$ w.r.t. all PVT\xspace{}s
in $\mathcal{X}_1$ then try out $\mathcal{X}_2$: calculate the reduction in malfunction score $\Delta_2$ if $D$ is intervened w.r.t. all PVT\xspace{}s
in $\mathcal{X}_2$.
\item[\algoexp{Lines~\ref{gp:linenine}-\ref{gp:line13}}] Recursively call
\textsc{Group-Test} on the partition $\mathcal{X}_1$ if one of the
following conditions hold:
(1) Intervening on $D$ w.r.t. all PVT\xspace{}s in $\mathcal{X}_1$ reduces the  malfunction to be lower than $\tau$:
the explanation over $\mathcal{X}_1$ is returned as the final explanation.
(2) Intervening on $D$ w.r.t. all PVT\xspace{}s in $\mathcal{X}_1$ reduces the malfunction, but still remains above $\tau$, but intervening on $D$ w.r.t. all PVT\xspace{}s in $\mathcal{X}_2$ brings the malfunction below $\tau$: the explanation returned by the recursive call on $\mathcal{X}_1$ is added to the set ${\mathcal{X}^{*}}$ and $\mathcal{X}_2$ is processed next.
 \item[\algoexp{Lines~\ref{gp:line14}-\ref{gp:line16}}] Recursively call
 \textsc{Group-Test} on $\mathcal{X}_2$ if
 intervening on all PVT\xspace{}s in $\mathcal{X}_2$ reduces malfunction.
 The set of PVT\xspace{}s returned by this recursive call of the
 algorithm are added to the solution set ${\mathcal{X}^{*}}$.

\end{description}

\begin{figure}
    \centering
    \begin{subfigure}[t]{0.24\columnwidth}
		\includegraphics[width=\columnwidth]{Figures/grptestgraph.pdf}
		\caption{Dependency graph $G_{PD}$}
	\end{subfigure}
	\hspace{2mm}
    \begin{subfigure}[t]{0.69\columnwidth}
		\includegraphics[width=\columnwidth]{Figures/grptestbisection.pdf}
		\caption{Execution of \textsc{DataExposer}\textsubscript{GT}\xspace}
    \end{subfigure}
    \vspace{-2.5mm}
    \begin{subfigure}[t]{0.67\columnwidth}
		\includegraphics[width=\columnwidth]{Figures/grptestrandom.pdf}
		\caption{Execution of traditional group testing algorithm}
		\label{fig:grprandom}
    \end{subfigure}
	\vspace{-2mm}
    \caption{Comparison between \textsc{DataExposer}\textsubscript{GT}\xspace and adaptive group testing on a toy example.}
	\vspace{-3.5mm}
    \label{fig:grptestcomparison}
\end{figure}

\iffalse
\paragraph{\textsc{Get-Min-Bisection}.} This subroutine takes a PVT\xspace-dependency graph $G_{PD}$ as input
along with a set of PVT\xspace{}s $\mathcal{X}$ and returns
a partition of $\mathcal{X}=\mathcal{X}_1\cup\mathcal{X}_2$ such that
both partitions contain almost equal number of PVT\xspace{}s
and the edges that connect two PVT\xspace{}s from different partitions are minimized.
This is
referred to as the min-bisection of the graph $G_{PD}$ which is a subgraph of $G_{PA}$ over the nodes
$\mathcal{X}$\af{This is a wrong definition of min-bisection, it is just not a subgraph, it is a subgraph that ensures certain properties. But this whole thing has been told before. So remove}. \af{Start from here. Remove things before it. Also I think this enture thing can go to appendix. This is not our contirbution. Why do we discuss how min-bisection works in this paper?} Calculating the minimum bisection of an
input graph is known to be NP-hard~\cite{garey1974some}. The best-known
approximation result for general graphs gives $O(\log n)$-approximation for a
graph of $n$ vertices~\cite{racke2008optimal}. Many recent techniques have
proposed algorithms for special cases like planar graphs and tree-like
graphs~\cite{fernandes2018minimum}. In this work, we consider the local search
algorithm~\cite{fellows2012local} to identify the min-bisection of the graph
$G_{PD}$. It is an anytime algorithm~\cite{zilberstein1996using} and is known to be very efficient in most
practical settings~\cite{fellows2012local}. This algorithm initializes a random
bisection of $G_{PD}$ and iteratively moves PVT\xspace{}s from one partition to the
other if it reduces the number of edges going across the cut. \af{I'd get rid of this and perhaps add one/two lines}
\fi
\smallskip
\paragraph{Discussion on \textsc{DataExposer}\textsubscript{GRD}\xspace vs. \textsc{DataExposer}\textsubscript{GT}\xspace.} \looseness-1
\textsc{DataExposer}\textsubscript{GRD}\xspace intervenes by considering a single discriminative PVT\xspace at a
time. Hence, in the worst case, it requires $O(|\mathcal{X}|)$ interventions where $\mathcal{X}$
denotes the set of discriminative PVT\xspace{}s. Note that \textsc{DataExposer}\textsubscript{GRD}\xspace requires
much fewer interventions in practice and would require $O(|\mathcal{X}|)$ only when any of the
mentioned observations (O1--O3) do not hold.
In contrast, \textsc{DataExposer}\textsubscript{GT}\xspace performs
group intervention by recursively partitioning the set of discriminative PVT\xspace{}s. Thus, the maximum number of interventions required by \textsc{DataExposer}\textsubscript{GT}\xspace is
$O(t\log |\mathcal{X}|)$ where $t$ denotes the number of PVT\xspace{}s that help
reduce malfunction if the corresponding profile is altered. Note that, in expectation,
\textsc{DataExposer}\textsubscript{GT}\xspace
requires fewer interventions than \textsc{DataExposer}\textsubscript{GRD}\xspace whenever
$t=o(|\mathcal{X}|/\log |\mathcal{X}|)$. \textsc{DataExposer}\textsubscript{GT}\xspace is particularly helpful when multiple PVT\xspace{}s \textit{disjunctively} explain the malfunction.
However,
\textsc{DataExposer}\textsubscript{GT}\xspace requires an additional assumption assumption A3 (Section~\ref{sec:grouptest}).
We discuss the empirical impact of this assumption in Section~\ref{realworld}
(Cardiovascular disease prediction).
Overall, we conclude that \textsc{DataExposer}\textsubscript{GT}\xspace is beneficial for applications whenever
$t=O(|\mathcal{X}|/\log |\mathcal{X}|)$ and observations O1-O3 hold (more details are in the appendix).

\subsection{Real-world Case Studies}\label{realworld}

We design three case studies focusing on three different applications, where we
use well-known ML models~\cite{akbik2018coling, adaboost, randomforest} as
black-box systems. For all of the three case studies, we use real-world
datasets. Figure~\ref{tab:comparison} presents a summary of our evaluation
results.

\smallskip

\paragraph{Sentiment Prediction.}
The system in this study predicts sentiment of input text (reviews/tweets) and computes misclassification
rate as the malfunction score. It uses flair~\cite{akbik2018coling}, a
pre-trained classifier to predict sentiment of the input records and assumes a \texttt{target} attribute in the
input data, indicating the ground truth sentiment: A value of $1$ for the
attribute \texttt{target} indicates positive sentiment and a value of $-1$
indicates negative sentiment. We test the system over \texttt{IMDb}
dataset~\cite{imdb} ($50K$ tuples) and a \texttt{twitter}
dataset~\cite{sentiment140} (around $1.6$M tuples). The malfunction score of
the system on the \texttt{IMDb} dataset is only $0.09$ while on the
\texttt{twitter} dataset it is $1.0$.
We considered \texttt{IMDb} as the passing dataset and \texttt{twitter} as the
failing dataset and used
both \textsc{DataExposer}\textsubscript{GRD}\xspace and \textsc{DataExposer}\textsubscript{GT}\xspace to explain the mismatch between the \texttt{twitter}
dataset and the system. The ground-truth cause of the malfunction is that the
\texttt{target} attribute in the \texttt{twitter} dataset uses ``4'' to denote
positive and ``0'' to denote negative sentiment~\cite{sentiment140}.
\textsc{DataExposer}\textsubscript{GRD}\xspace identifies a total of $3$ discriminative PVT\xspace{}s between the two
datasets. One such PVT\xspace includes the profile $\textsc{Domain}\xspace$ of the \texttt{target} attribute that has corresponding parameter $\mathbb{S}=\{-1,1\}$ for \texttt{IMDb} and $\mathbb{S}=\{0,4\}$
for the \texttt{twitter} dataset. \textsc{DataExposer}\textsubscript{GRD}\xspace performs two
interventions and identifies that the malfunction score reduces to $0.36$ by
mapping $0\rightarrow -1$ and $4\rightarrow 1$ by intervening w.r.t.  the PVT\xspace corresponding $\textsc{Domain}\xspace$, which is returned as an explanation of the malfunction.

\iffalse
captures the regular expression representation of the attribute along its length.
This PVT\xspace implies that the length
of text in the \texttt{twitter} dataset is less than 280 characters but in the
\texttt{IMDb} dataset it is between 32 and 13K characters.
\af{Also, was it a spurious PVT\xspace?
If so, tell that and explain why two interventions were required.} The ground
truth cause \af{Is it also a discriminating PVT\xspace? Overall, this section needs a
lot of polishing w.r.t. the formalization we did in the prior section. It feels
very disconnected with the rest of the paper.} of the malfunction is that the
\texttt{target} attribute in the \texttt{twitter} dataset uses ``4'' to denote
positive and ``0'' to denote negative sentiment~\cite{sentiment140} \af{Which
profile captures it? Give details.}. The mismatch with the prediction
algorithm's expectation of \texttt{target} values in $\{+1,-1\}$ leads to low
accuracy, which results in a high malfunction score.
\fi

\textsc{DataExposer}\textsubscript{GT}\xspace and \texttt{GrpTest} both require
$3$ group interventions to explain the cause
of system malfunction. \texttt{BugDoc} and \texttt{Anchor}
require $10$ and $303$ interventions, respectively. \texttt{Anchor} calculates
system malfunction on datasets transformed according to various local
perturbations of the PVT\xspace{}s in the failing dataset.

\smallskip

\paragraph{Income Prediction.}
The system in this study trains a Random Forest classifier~\cite{randomforest}
to predict the income of individuals while ensuring fairness towards
marginalized groups. The pipeline returns the normalized disparate
impact~\cite{ibmaif360} of the trained classifier w.r.t.\ the protected
attribute (\texttt{sex}), as the malfunction score. Our input data includes
census records~\cite{Dua:2019} containing demographic attributes of individuals
along with information about income, education, etc. We create two datasets
through a random selection of records, and manually add noise to one of them to
break the dependence between \texttt{target} and \texttt{sex}.
 The system has  malfunction score of $0.195$ for the passing dataset and $0.58$ for the failing dataset due to the dependence
between \texttt{target} and \texttt{sex}.
\textsc{DataExposer}\textsubscript{GRD}\xspace identifies a total of $43$ discriminative PVT\xspace{}s and constructs a PVT\xspace-attribute graph. In this graph, the
\texttt{target} attribute has degree $15$ while all other attributes have degree $2$.
The PVT\xspace{}s that include \texttt{target} are then intervened in
non-increasing order of benefit. The
transformation w.r.t. $\textsc{Indep}\xspace$ PVT\xspace on the \texttt{target} attribute breaks the dependence
between \texttt{target} and all other attributes, thereby reducing the
malfunction score to $0.32$. Therefore, \textsc{DataExposer}\textsubscript{GRD}\xspace requires one intervention to explain the cause of the malfunction.
Our group testing algorithm \textsc{DataExposer}\textsubscript{GT}\xspace and \texttt{GrpTest} require $8$ and $10$ interventions, respectively.
Note that group testing is not very useful because the datasets contain few discriminative PVT\xspace{}s.

\texttt{BugDoc} and \texttt{Anchor} do not identify discriminative PVT\xspace{}s explicitly and consider
all PVT\xspace{}s ($136$ for this dataset) as candidates for intervention. \texttt{Anchor} performs $800$ local interventions to explain the malfunction.
\texttt{BugDoc} identifies the ground truth
malfunction in $50\%$ of the runs when allowed to run fewer than $10$ interventions. It  identifies the mismatch with intervention budget of $20$ but the returned
solution of PVT\xspace{}s is not minimal. For instance, \texttt{BugDoc} returns
two PVT\xspace{}s: $\{\langle$\pl{$\textsc{Indep}\xspace$}, $\texttt{target}$, $\texttt{education}$$\rangle$
\texttt{and}    $\langle$\pl{$\textsc{Indep}\xspace$}, $\texttt{target}$, $\texttt{sex}$$\rangle\}$
as the explanation of malfunction.

\smallskip

\paragraph{Cardiovascular Disease Prediction.}
\looseness-1
This system
trains an AdaBoost classifier~\cite{adaboost} on patients' medical
records~\cite{cardio} containing age, height (in centimeters) and weight along with
other attributes. It predicts if the patient
has a disease and does not optimize for false positives. Therefore, the system calculates recall over the patients having cardiovascular
disease, and the goal is to achieve more than $0.70$ recall. The pipeline returns
the additive inverse of recall as the malfunction score.
We tested the pipeline with two datasets generated through a random selection of records: (1)~the passing dataset
satisfies the format assumptions of the
pipeline;  (2)~for the failing dataset we manually converted \texttt{height} to inches.
\textsc{DataExposer}\textsubscript{GRD}\xspace identifies $86$ discriminative PVT\xspace{}s with \texttt{height},
\texttt{weight} and \texttt{age} having the highest degree of $15$ in the PVT\xspace-attribute
graph. Among the PVT\xspace{}s involving these attributes, the \textsc{Domain}\xspace of \texttt{height}
has the maximum benefit, which is the ground-truth PVT\xspace too. \textsc{DataExposer}\textsubscript{GRD}\xspace alters the failing dataset by applying a linear transformation
 and it reduces the malfunction from $0.71$ to $0.30$. This explanation matches
the ground truth difference in the passing and the failing dataset.
Among baselines, \texttt{BugDoc} and \texttt{Anchor} performed $100$ and $5900$
interventions, respectively. Group testing techniques are not applicable
because assumption A3 (Section~\ref{sec:grouptest}) does not hold. We observe
that the malfunction score with a composition of transformation functions is higher than
the one in the original dataset if the composition involves $\textsc{Indep}\xspace$ PVT\xspace. This behavior is observed
because adding noise to intervene with respect to $\textsc{Indep}\xspace$ PVT worsens the classifier performance.
If we remove PVT\xspace{}s that violate this assumption, then \textsc{DataExposer}\textsubscript{GT}\xspace and \texttt{GrpTest} require $6$ and $9$
interventions, respectively.

\smallskip

\paragraph{Efficiency.} Figure~\ref{tab:comparison} presents
the execution time
of considered techniques
for real-world applications presented above.
\textsc{DataExposer}\textsubscript{GRD}\xspace, \textsc{DataExposer}\textsubscript{GT}\xspace and \texttt{GrpTest} are highly efficient and
require less than $30$ seconds to explain the ground-truth cause of
malfunction. In contrast, \texttt{Anchor} is extremely inefficient as it
requires more than 143 minutes for \texttt{cardiovascular}, while \textsc{DataExposer}\textsubscript{GRD}\xspace and
\texttt{BugDoc} explain the malfunction within 63 seconds.

\smallskip

\paragraph{Key takeaways.} Among all real-world case studies, the greedy
approach \textsc{DataExposer}\textsubscript{GRD}\xspace requires the fewest interventions to explain the cause of
malfunction. Group testing techniques, \textsc{DataExposer}\textsubscript{GT}\xspace and \texttt{GrpTest}, require
fewer interventions than \texttt{BugDoc} and \texttt{Anchor} whenever
assumption A3 (Section~\ref{sec:grouptest}) holds. \texttt{Anchor} requires the
highest number of interventions as it performs many local transformations to
explain the cause of failure. \texttt{BugDoc} optimizes interventions by
leveraging combinatorial design algorithms: it requires more interventions than
\textsc{DataExposer}\xspace but fewer than \texttt{Anchor}.

\subsection{Synthetic Pipelines} We evaluate the effectiveness and scalability
of \textsc{DataExposer}\textsubscript{GRD}\xspace and \textsc{DataExposer}\textsubscript{GT}\xspace for a diverse set of synthetic scenarios.

\smallskip
\paragraph{\textsc{DataExposer}\textsubscript{GRD}\xspace vs. \textsc{DataExposer}\textsubscript{GT}\xspace.} In this experiment, we consider a pipeline
where the ground-truth explanation of malfunction violates the observations
discussed in Section~\ref{sec:observations}. Specifically, the
explanation requires modifying one particular value in the dataset and its
likelihood (as estimated by \textsc{DataExposer}\textsubscript{GRD}\xspace) is ranked $54$ among the set of
discriminative PVT\xspace{}s. Therefore, it requires $54$
interventions to explain the cause of
malfunction. On the other hand, \textsc{DataExposer}\textsubscript{GT}\xspace performs group interventions and
requires only $9$ interventions. This experiment demonstrates that \textsc{DataExposer}\textsubscript{GT}\xspace
requires fewer interventions than \textsc{DataExposer}\textsubscript{GRD}\xspace when the failing dataset and the
corresponding PVT\xspace{}s do not satisfy the observations \textsc{DataExposer}\textsubscript{GRD}\xspace relies on.
We present additional experiments with complex conjunctive and disjunctive explanations of
malfunction in the appendix.

\iffalse
\smallskip

\paragraph{Effect of number of attributes and PVT\xspace{}s.}
Figure~\ref{fig:interventions}(a)~presents \af{Again, a figure never compares,
it presents results of two things for comparison purpose. Use ``depicts''} the
effect of changing the number of attributes in the datasets on the number of
required interventions. \textsc{DataExposer}\textsubscript{GRD}\xspace requires less than $5$ interventions on
average. On the other hand, \af{Use ``In contrast'', less verbose than ``on the
other hand''. And also, ``on the other hand'' usually accompanies with on one
hand, we do foo, on the other hand, we doo bar.} \texttt{BugDoc} and
\texttt{Anchor} require orders of magnitude higher number of \af{more}
interventions. The number of interventions required by \texttt{GrpTest} is
higher \af{more} than that of \textsc{DataExposer}\textsubscript{GRD}\xspace and grows logarithmically with the
number of data PVT\xspace{}s. \af{Doesn't \textsc{DataExposer}\textsubscript{GRD}\xspace also grow logarithmically? what's
your point here?}

Figure~\ref{fig:interventions}(b)~compares \af{depicts} the effect of number of
discriminative PVT\xspace{}s on the number of required interventions. \textsc{DataExposer}\textsubscript{GRD}\xspace shows
superior performance and \af{as it} requires less than $10$ interventions even
when the number of discriminative PVT\xspace{}s go beyond $150$ \af{Did you mean
150K?}. We observe similar trends in Figure~\ref{fig:interventions}(a) for
other baselines. \af{Not clear what you mean by ``similar trends''}\fi

\smallskip

\paragraph{Scalability.} To test the scalability of our techniques, we compare
their running time with increasing number of attributes and discriminative
PVT\xspace{}s. Figure~\ref{fig:scalability} shows that the time required by \textsc{DataExposer}\textsubscript{GRD}\xspace
and \textsc{DataExposer}\textsubscript{GT}\xspace to explain the malfunction grows sub-linearly in the number of
attributes and discriminative PVT\xspace{}s. We observe similar trend of the number
of required interventions on varying these parameters. This experiment
demonstrates that \textsc{DataExposer}\textsubscript{GRD}\xspace requires fewer than $O(|\mathcal{X}|)$ interventions in
practice (where $\mathcal{X}$ denotes the set of discriminative profiles) and validates
the logarithmic dependence of \textsc{DataExposer}\textsubscript{GT}\xspace on $|\mathcal{X}|$.

\iffalse
\begin{figure*}[t]
    \centering
    \hspace{7mm}\includegraphics[width=0.9\columnwidth]{Figures/legend.png}
    \includegraphics[width=\textwidth]{Figures/interventions.pdf}
	\caption{Average number of interventions required by \textsc{DataExposer}\xspace and three other techniques for varying number of attributes, dicriminative PVT\xspace{}s, size of root cause conjunctions, and size of disjunctions.}
    \label{fig:interventions}
\end{figure*}
\fi

\section{Minimum Bisection} Algorithm~\ref{alg:minbisection} presents the
\textit{local search algorithm}~\cite{fellows2012local} that \textsc{DataExposer}\textsubscript{GT}\xspace uses to
partition the set of discriminative PVT\xspace{}s. It is an anytime
algorithm~\cite{zilberstein1996using} and is known to be very efficient in most
practical settings~\cite{fellows2012local}.

\begin{description}
	%

\item[\algoexp{Line~\ref{bs:line1}}] Initialize the solution $\mathcal{X}_1,\mathcal{X}_2$ to a
randomized partition of $\mathcal{X}$ where $|\mathcal{X}_1| - |\mathcal{X}_2| \leq 1$.

\item[\algoexp{Lines~2-\ref{bs:line13}}] Iteratively try to improve the
solution by performing local search.

\item[\algoexp{Line~\ref{bs:line3}}] Count the number of cut edges, i.e.,
edges that connect two nodes from different partitions.

\item[\algoexp{Line~\ref{bs:line3p}}] Initialize the number of cut edges in an
improved partitioning to be equal to the current number of cut edges.

\item[\algoexp{Lines~\ref{bs:line4}-\ref{bs:line7}}] Swap a pair of PVT\xspace{}s
between the partitions to create two temporary partitions.

\item[\algoexp{Lines~\ref{bs:line8}}] Count the number of cut edges between
the temporary partitions.

\item[\algoexp{Lines~\ref{bs:line9}-\ref{bs:line12}}] If swapping the PVT\xspace
pairs reduces the number of cut edges, then update the partitions and terminate
the current iteration.

\item[\algoexp{Line~\ref{bs:line13}}] Stop searching for an improved
partitioning reduction in the number of cut edges is no longer possible.

\item[\algoexp{Line~\ref{bs:line14}}] Return the updated partitions $\mathcal{X}_1,\mathcal{X}_2$
as the solution.

\end{description}

\section{Modeling Interaction among PVT\xspace Interventions}\label{multiple}

We now extend our techniques for the setting when intervening on one PVT\xspace may
affect the impact of intervention on another PVT\xspace. For example, when altering
the failing dataset with respect to PVT\xspace $P_1$ does not help reduce malfunction
when considered in isolation, but, malfunction reduces when the failing dataset
is intervened with respect to PVT\xspace $P_1$ along with another PVT\xspace $P_2$. In such
a setting, assumption A2 does not hold and \textsc{DataExposer}\xspace may fail to identify the
ground-truth cause of malfunction.

To address this issue, we propose to leverage multiple passing and failing
datasets. Using this additional knowledge, we generate a decision tree to guide
\textsc{DataExposer}\xspace. The key idea is to fit a decision tree based on the PVT\xspace{}s and the
relative decrease of the malfunction score ($m_S{D}$) with respect to the
maximum allowable malfunction score threshold ($\tau$). Each training data
point for learning the decision tree consists of the set of PVT\xspace{}s $\mathcal{X}_i$,
extracted from dataset $D_i$, and the outcome is the Boolean assessment of
whether $m_S(D_i) \le \tau$. Each path of the tree can be seen as a conjunction
of PVT\xspace{}s. If a conjunction leads to a consistent outcome (a ``pure'' leaf),
then that combination becomes an explanation ``candidate''. The candidates are
then verified by Algorithm~\ref{alg:datadebugthree}, where we perform
interventions on an arbitrary failing dataset.

\begin{description}
\item[\algoexp{Line~\ref{dt:init}}] Traverse the decision tree at least once.

\item[\algoexp{Line~\ref{dt:while}-\ref{dt:line11}}] Follow the decision-tree
paths until we find a conjunction of PVT\xspace{}s $\mathcal{X}$ that reduces the malfunction
score of $D_{\mathit{fail}}$ so that $m_S(D_{\mathit{fail}}) \le \tau$. If no
candidate conjunction of PVT\xspace{}s can convert $D_{\mathit{fail}}$ to a passing
dataset, then rebuild the decision tree.

\begin{algorithm}[t]
		\LinesNumbered
		\DontPrintSemicolon
\KwIn{Dependency Graph $G_{PD}$, discriminative PVT\xspace{}s $\mathcal{X}$}
\KwOut{Partitions $\mathcal{X}_1$, $\mathcal{X}_2$}
$\mathcal{X}_1,\mathcal{X}_2\leftarrow \textsc{Random-Bisection}(\mathcal{X})$\label{bs:line1} \tcc*[f]{Initialization}\\
\Do{$C' < C$;\tcc*[f]{As long as cut size reduces}\label{bs:line13}}
	{
		$C \leftarrow  \sum\limits_{X_1\in \mathcal{X}_1, X_2\in \mathcal{X}_2} \mathbbm{1}_{G _{PD}}(X_1,X_2 )$\label{bs:line3}\tcc*[f]{\#Cut edges}\\
		$C' \leftarrow C$\label{bs:line3p}\tcc*[f]{Initialize}\\
		\ForEach{$X_1 \in \mathcal{X}_1$\label{bs:line4}}{
		 \ForEach{$X_2 \in \mathcal{X}_2$\label{bs:line5}}{
			$\mathcal{X}_1'\leftarrow \mathcal{X}_1\cup\{X_2\}\setminus \{X_1\}$\label{bs:line6}\tcc*[f]{Swap PVT\xspace{}s }\\
			$\mathcal{X}_2'\leftarrow \mathcal{X}_2\cup\{X_1\}\setminus \{X_2\}$\label{bs:line7}\tcc*[f]{Swap PVT\xspace{}s }\\
			$ C' \leftarrow  \sum\limits_{X_1\in \mathcal{X}_1', X_2\in \mathcal{X}_2'} \mathbbm{1}_{G _{PD}}(X_1,X_2 )$\label{bs:line8}\tcc*[f]{\#Cut edges}\\
			\If(\tcc*[f]{Cut size is reduced}){$C' < C$\label{bs:line9}}
			{
				$\mathcal{X}_1 \leftarrow \mathcal{X}_1'$ \label{bs:line10}\tcc*[f]{Update partition}\\
				$\mathcal{X}_2 \leftarrow \mathcal{X}_2'$ \label{bs:line11}\tcc*[f]{Update partition}\\
				\textbf{break}\label{bs:line12}
			}
		 }
	  }
   }
\Return $\mathcal{X}_1,\mathcal{X}_2$ \label{bs:line14}\tcc*[f]{$\mathcal{X}_1,\mathcal{X}_2$ are returned as the solution}
\caption{\textsc{Get-Min-Bisection}}
\label{alg:minbisection}
\end{algorithm}

\item[\algoexp{Line~\ref{dt:lineone}}] Find the paths $\Pi$ of the decision
tree that lead to pure leaves (malfunction score is less than $\tau$ whenever
all PVT\xspace{}s in the paths, in conjunction, are observed) and sort them by their
PVT\xspace{}s' benefit scores, as defined in Algorithm~\ref{alg:datadebuggreedy}.

\item[\algoexp{Line~\ref{dt:unmark}}] Record that some candidate PVT\xspace{}s were
computed.

\item[\algoexp{Lines~\ref{dt:linetwo}-\ref{dt:line11}}] Iteratively test each
conjunction of PVT\xspace{}s $\mathcal{X}$.

\item[\algoexp{Line~\ref{dt:linethree}}] Transform the failing dataset
$D_{\mathit{fail}}$ w.r.t $\mathcal{X}$ to obtain $D_t$.

\item[\algoexp{Lines~\ref{dt:lineeleven}-\ref{dt:line11}}] If the transformed
dataset $D_t$ reduces the malfunction score, then return $\mathcal{X}$ as a cause of
malfunction. Otherwise, add a new instance (data point) to re-train the
decision tree and recompute $\Pi$.

\end{description}

In future work, we plan to extend this approach to leverage
combinatorial-design-based techniques to efficiently intervene PVT\xspace{}s to
initialize the decision tree algorithm~\cite{JCD:JCD20065}.

\section{Discussion on \textsc{DataExposer}\textsubscript{GRD}\xspace vs. \textsc{DataExposer}\textsubscript{GT}\xspace} As discussed in
Section~\ref{sec:grouptest}, \textsc{DataExposer}\textsubscript{GRD}\xspace always identifies the ground-truth cause
of malfunction, but, the number of interventions required may increase if
observations O1-O3 do not hold. If O1 does not hold, then the initial ordering
of attributes, which is computed based on their degree in PVT\xspace{}-Attribute
graph $G_{PA}$, may not be accurate. In this case, \textsc{DataExposer}\textsubscript{GRD}\xspace may require
$O(\mathcal{X})$ interventions to explain the cause of system malfunction. Similarly,
whenever O2 or O3 fail, the benefit-based ordering of the PVT\xspace{}s is likely to
be incorrect. In applications where O1 holds but O2 and O3 do not hold,
$G_{PA}$ is expected to be accurate and the number of required interventions is
$O(r)$, where $r$ is the degree of the attribute that has the highest degree in
$G_{PA}$. In contrast, \textsc{DataExposer}\textsubscript{GT}\xspace requires $O(t\log |\mathcal{X}|)$ interventions even
when these observations are violated. Therefore, \textsc{DataExposer}\textsubscript{GRD}\xspace is beneficial
whenever all of these observations hold, or $t=\Omega(|\mathcal{X}|/\log |\mathcal{X}|)$.

\begin{algorithm}[t]
	\LinesNumbered
\KwIn{Failing dataset $D_{\mathit{fail}}$, decision tree $DT$, malfunction score threshold $\tau$}
$\textsc{Update-Paths} \leftarrow \texttt{true}$\label{dt:init}\tcc*[f]{Indicates whether to explore decision tree paths}\\
\While{$\textsc{Update-Paths}$\label{dt:while}}{
    Let $\Pi$ be the set of  paths in $DT$ that are observed for instances where system malfunction score is less than $\tau$. All PVT\xspace{}s along a path are considered in conjunction and sorted  by decreasing order of their benefit score.\label{dt:lineone} \\

    $\textsc{Update-Paths} \leftarrow \texttt{false}$\label{dt:unmark}\tcc*[f]{$\Pi$ is up-to-date}\\

    \For{$\mathcal{X}\in \Pi$\label{dt:linetwo}}
    {
    	$D_t \leftarrow \mathcal{X}_T(D_{\mathit{fail}})$\label{dt:linethree}
    	\tcc*[f]{Transform $D_{\mathit{fail}}$ wrt $\mathcal{X}$}\\

    	\If(\tcc*[f]{Cause has been identified}){$m_S(D_t) \le \tau$\label{dt:lineeleven}}
    	{
    		\Return $\mathcal{X}$\label{dt:linetwelve}
    	}
    	\Else{
    	$DT.\textsc{Update}(D_t, \texttt{Fail})$\label{dt:linefive}
    	\tcc*[f]{Add instance to tree}\\

    	    $\textsc{Update-Paths} \leftarrow \texttt{true}$\label{dt:line11}\tcc*[f]{Recompute $\Pi$}\\
    	}
    }
}
\Return $\emptyset$
\caption{Greedy + Decision Tree Approach}
\label{alg:datadebugthree}
\end{algorithm}

\section{Effect of Various Parameters}

In this experiment, we test the effect of the number of dataset attributes and
the number of discriminative PVT\xspace{}s on the efficacy of \textsc{DataExposer}\xspace algorithms, and
contrast those with other state-of-the-art baselines. We also investigate the
influence of the number of PVT\xspace{}s involved in the root causes and their
interactions on the number of interventions each method requires.

\begin{figure*}[t]
    \centering
    \includegraphics[width=\textwidth]{Figures/interventions.pdf}

	 \caption{Average number of interventions required by two versions of
	 \textsc{DataExposer}\xspace and three other techniques for varying number of attributes,
	 discriminative PVT\xspace{}s, size of single conjunctive root causes, and size of
	 disjunctive root causes.}

	\label{fig:interventions}
\end{figure*}

\subsection{Effect of Number of Attributes and PVT\xspace{}s}
Figure~\ref{fig:interventions}(a)~presents the effect of changing the number of
attributes in the datasets on the number of required interventions.
\textsc{DataExposer}\textsubscript{GRD}\xspace requires fewer than $5$ interventions on average. In contrast,
\texttt{BugDoc} and \texttt{Anchor} require orders of magnitude more
interventions. The number of interventions required by \texttt{BugDoc} grows
linearly with the number of attributes. At the same time, \texttt{Anchor}
perturbs all PVT\xspace{}s to solve a multi-armed bandit problem: the more PVT\xspace{}s
affect the pipeline errors, the more interventions are needed.
Group-testing-based approaches also require more intervention than that of
\textsc{DataExposer}\textsubscript{GRD}\xspace, and grow logarithmically with the number of data attributes.

Figure~\ref{fig:interventions}(b)~depicts the effect of the number of
discriminative PVT\xspace{}s on the number of required interventions. \textsc{DataExposer}\textsubscript{GRD}\xspace shows
superior performance as it requires fewer than $10$ interventions even when the
number of discriminative PVT\xspace{}s go beyond $100$. Here, we observe trends
similar the one in Figure~\ref{fig:interventions}(a) for other baselines as the
number of PVT\xspace{}s are strongly and positively correlated to the number
attributes.

\balance

\subsection{Effect of Number of Root Causes and their Interactions} The
pipelines presented in Figures~\ref{fig:interventions}(a)
and~\ref{fig:interventions}(b) have a single PVT\xspace as the root cause of the
malfunction. In Figure~\ref{fig:interventions}(c), we fix the number of
attributes to $15$ and the number of discriminative PVT\xspace{}s between the passing
and the failing datasets to $136$. We also define the root cause to be a
conjunction over a set of PVT\xspace{}s of varying cardinalities. We find that the
cardinality of the root-cause set (length of the conjunctive cause) does not
impact the number of interventions as much as the number of attributes and the
number of discriminative PVT\xspace{}s do. However, having more than one cause for
malfunction (i.e., a disjunctive cause) requires more interventions for
\texttt{Anchor} and the Group-Test techniques, as shown in
Figure~\ref{fig:interventions}(d). \textsc{DataExposer}\textsubscript{GRD}\xspace still needs orders of magnitude
fewer interventions than these other approaches, although the probability of
failing to find any feasible transformation, which decreases malfunctions
scores, increases with the number of possible root causes within the
disjunction.

\section{Introduction}\label{sec:introduction}
\input{1_introduction}

\section{Preliminaries \& Problem Definition}\label{sec:problem}
\input{2_problem}

\section{Data Profiles, Violation Functions, \& Transformation Functions}\label{sec:profile}
\input{3_profile}

\section{Intervention Algorithms}\label{sec:algorithm}
\input{4_algorithm}

\section{Experimental Evaluation}\label{sec:experiment}
\input{5_experiment}

\section{Related Work}\label{sec:related}
\input{6_related}

\section{Summary and Future Directions}\label{sec:summary}
\input{7_summary}

\bibliographystyle{ACM-Reference-Format}