Causal Banzhaf Value for Aggregate Query Explanations

Causal Banzhaf Value for aggregate query explanations⋆ Pouya Khani1,∗,Ira Assent1 1Department of Computer Science, Aarhus University, Aarhus, Denmark Abstract Aggregate queries, particularly those using averages, are essential for summarizing data and obtaining condensed information. Explaining such queries - by identifying how specific tuples, predicates, or combinations of predicates influence the result -provides deeper insights into the factors shaping query outcomes. However, existing statistical, interventional, and game theoretic explanation methods lack causal grounding, while causal methods require complete causal graphs, which are rarely available in large databases. To address this, we propose Causal Banzhaf Value (CBV): introducing causal awareness into Banzhaf values, our CBV method delivers explanations even in the absence of full causal graphs. Experiments on real world data demonstrate that CBV is computationally efficient, aligns with human intuition, and is consistent with causal explanations. Keywords Explainability, Query Answering, Data Analytics, Explainable Data Management 1. Introduction The increasing reliance on data-driven decision-making in fields such as business, healthcare, and scientific research has amplified the importance of query explanations in understanding patterns, trends, and anomalies [ 1 , 2 , 3 ]. Aggregate queries, such as averages, sums, or counts, play a pivotal role in summarizing high-dimensional data but pose unique challenges for understandability. Analysts often need explanations to to understand query results, such as the contributions of individual data segments or predicates, especially in high-dimensional datasets where interactions and dependencies are complex [4,5]. Example Consider the Stack Overflow Developer Survey [ 6 ], a dataset which includes features such as age, developer role, years of coding experience, education level, and salary. An analyst might pose the aggregate query SELECT AVG(Salary) FROM StackOverflow; to retrieve the average salary. However, understanding why the average takes its specific value requires additional explanation; e.g., the predicate Role = C-level Executive might increase the result, while Age = 25 might decrease it: Predicate Contribution to Avg. Salary Education = Bachelor's -15,000 Education = Master's +15,000 Education = ... ... ... ... Role = C-level +22,500 ... ... Age < 18 -8,000 ... ... This explanation breaks down query results into additive or subtractive contributions of individual predicates to salary, enabling analysts to identify key factors and make informed decisions or policy recommendations. However, DOLAP’25: International Workshop on Design, Optimization, Languages and Analytical Processing of Big Data, March 03–25, 2025, Barcelona, Spain ⋆ You can use this document as the template for preparing your publication. We recommend using the latest version of the ceurart style. ∗Corresponding author. Envelope-Open[email protected] (P. Khani); [email protected] (I. Assent) Orcid0000-0002-0877-7063 (P. Khani); 0000-0002-0877-7063 (I. Assent) © 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). accurately attributing the importance of individual predicates is challenging due to feature interdependencies and causal relationships. Existing techniques, such as DIFF [ 2 ] or MacroBase [ 4 ], fail to capture these dependencies, while game-theoretic methods like Shapley [ 7 ] and Banzhaf values [ 8 ] lack causal awareness [ 9 ]. Causal approaches, including XInsight [1] and CauSumX [10], rely on fully specified causal models, which are often computationally expensive and impractical to construct [3]. To address these limitations, we introduce Causal Banzhaf Values (CBV), a novel approach for causally informed query explanations. CBV integrates causal knowledge to respect feature dependencies and employs conditional sampling [ 11 ] to estimate contributions accurately. For instance, it accounts for interdependence between Age and Education , ensuring causal information is reflected in the explanation. Unlike methods focusing on entire features, CBV evaluates the importance of specific predicates, offering more granular insights. For example, identifying that Role = C-level drives salary outcomes is more informative than attributing importance to the general feature Role . Moreover, CBV does not require a fully specified causal graph, making it suitable for scenarios where defining complete causal models is infeasible. Finally, CBV achieves computational efficiency, balancing accuracy with practicality for real-world applications. 2. Related Work Approaches to explaining query results span statistical, relational, intervention-based, game-theoretic, and causal methods. Statistical techniques, such as DIFF [ 2 ] and MacroBase [ 4 ], find associations without causal insights. Relational methods, such as [ 12 ], trace data transformations through relational operations like joins, but lack the ability to provide causal explanations. Intervention-based approaches, such as Scorpion [ 13 ], detect outliers in aggregate queries but also lack consideration of causal relationships. Game-theoretic methods like Shapley values [ 14 ] and Banzhaf values [ 15 ], fairly attribute feature contributions by averaging marginal effects across subsets. While these approaches effectively capture interactions between features, they assume feature independence and disregard causal relationships [ 9 ]. Causal approaches, such as XInsight [ 1 ] and CauSumX [ 10 ], assume full causal models between all features. However, constructing complete causal models is challenging and often infeasible in practice [3]. Our proposed CBV approach addresses these limitations by integrating partial causal knowledge into a gametheoretic contribution model. While full causal models are often elusive, some knowledge about causal feature interactions is usually available and provides valuable information. 3. Feature attribution In explaining query outcomes, it is essential to determine how individual features influence a given result. The Banzhaf Value, rooted in cooperative game theory, provides a systematic way to quantify the influence of each feature as its marginal contribution. The change in value function 𝑣 ∶ 2𝑁→ ℝ across feature subsets, when including a particular feature 𝑖∈𝑁 from the set of features 𝑁 = {1,2,…,𝑛}, yields its Banzhaf Value 𝛽𝑖: 𝛽𝑖=1 2𝑛−1 ∑ 𝑆⊆𝑁 ∖{𝑖} [𝑣(𝑆 ∪ {𝑖}) − 𝑣(𝑆)], where 𝑣(𝑆∪{𝑖})−𝑣(𝑆) represents the marginal contribution of feature 𝑖 to the subset 𝑆 , and the sum iterates over all subsets 𝑆of 𝑁excluding 𝑖. Please note that the related Shapley Value [ 14 ] weighs contributions based on subset sizes, which may overshadow the raw impact of features. The Banzhaf Value offers a more direct measure of their impact, relevant in a variety of application domains (see e.g. discussion in [15]). Banzhaf Value (BV) offers a systematic framework for attributing contributions by evaluating all possible subsets of predicates. However, its limitations become evident when applied to aggregate query explanations. BV assumes independence among predicates, overlooking real-world dependencies, such as the relationship between Age = 10 and Education level = Doctoral Degree . This lack of causal awareness leads to misrepresentation of contributions. Additionally, BV distributes contributions symmetrically, failing to account for the hierarchical and asymmetric nature of causal chains (e.g., Education affects Role, which influences Salary). As a result, foundational predicates are undervalued. BV also incurs high computational overhead by evaluating all subsets exhaustively, which becomes impractical for high-dimensional datasets. CBV addresses these issues by integrating causal knowledge via partial DAGs to respect predicate dependencies, enabling accurate attribution. Unlike BV, CBV attributes contributions to specific predicate-value pairs, capturing their individual impacts while reflecting causal asymmetry. By focusing on causally valid subsets and using sampling techniques, CBV achieves efficiency without sacrificing accuracy. For predicates without causal ancestors, CBV defaults to BV, ensuring consistency. 4. Causal Banzhaf Value Traditional Banzhaf value fairly attributes contributions by averaging marginal effects but assumes feature independence. For instance, in a causal chain where Education Level influences Job Role , which then affects Salary , it treats Education Level and Job Role as independent contributors, potentially misestimating their true impact. To address this, we propose the Causal Banzhaf Value (CBV), which incorporates causal knowledge into the attribution process. Existing causal methods, such as XInsight [ 1 ] and CauSumX [ 10 ], account for dependencies among features but face challenges in practice because they inherently rely on fully specified causal DAGs, which are often difficult or infeasible to construct, especially for complex datasets, or even completely unavailable, depending on the domain. Errors or omissions in the DAG structure can lead to incorrect attributions, reducing their reliability. Additionally, the computational demands of simulating interventional scenarios grow exponentially with data dimensionality, limiting scalability. CBV addresses these challenges by working with partial causal graphs, leveraging available knowledge without requiring complete DAGs. CBV focuses on causally valid subsets to maintain consistency and employs conditional sampling to estimate contributions efficiently. This combination of partial causal integration, flexibility, and computational efficiency makes CBV a robust and practical alternative to causal methods. Unlike the application of Banzhaf value in Explainable AI [ 16 ], which focus on features, CBV evaluates the contributions of feature values (predicates). This aligns with query explanation needs, where specific feature values, such as Role = C-level , drive outcomes. CBV incorporates causal dependencies by considering causally valid coalitions (subsets) of features, defined based on a partial directed acyclic graph (DAG) 𝐺 : for each feature 𝑖 , we identify its ancestors 𝐴𝑖= {𝑗 ∈ 𝑁 ∣ 𝑗 ≺𝐺𝑖} , where ≺𝐺 represents the causal ordering in 𝐺 (see Figure 1for an example). Then, we identify the set of all causally valid subsets for feature 𝑖, denoted as 𝒮𝑖: 𝒮𝑖← {𝑆 ∣ 𝐴𝑖⊆ 𝑆,𝑆 ⊆ 𝑁 ∖ {𝑖,𝑌}}, Thus, a subset 𝑆 is valid if it contains all causal ancestors of 𝑖 𝐴𝑖 , and contains neither feature 𝑖 itself nor the target variable 𝑌 . This ensures that attributions respect the known causal structure, while otherwise adopting the assumption of order independence as in the Banzhaf value for feature combinations where order is not known to impact outcomes. For example, 𝑣( Gender = Male ∣ Education = Bachelor's , Age = 25) is identical to 𝑣( Gender = Male ∣ Age = 25, Education = Bachelor's ). The Causal Banzhaf Value (CBV) 𝛽C for a predicate 𝑝(𝑖 op 𝑢) of feature 𝑖 , a comparison operator 𝑜𝑝 such as equality =, and value 𝑢is defined as: 𝛽C 𝑝(𝑖 op 𝑢) =1 2𝑛−1 ∑ 𝑆∈𝒮𝑖 ∑ r∈ℛ(𝑆) [𝑣(𝑆r∪ {𝑝(𝑖 op 𝑢)}) − 𝑣(𝑆r)], where ℛ(𝑆) is the set of all possible realizations (value assignments) of features in subset 𝑆 , and 𝑣(𝑆r) is the expected value of the target variable 𝑌 conditioned on subset 𝑆 with realization r. For simplicity, we adopt the equality operator, i.e. predicate 𝑝(𝑖 = 𝑢), in the following presentation. To estimate 𝑣(𝑆r) and 𝑣(𝑆r∪{𝑝(𝑖 = 𝑢)}) , we employ conditional sampling [ 11 ], which maintains feature dependencies and provides high estimation accuracy. For each subset 𝑆 , realizations r (𝑛) are sampled from the empirical distribution  𝑃(𝑆) , while features not in 𝑆 ∪ {𝑖} are sampled conditionally as x (𝑛) ∼ 𝑃(𝑋∖(𝑆 ∪ {𝑖}) ∣ 𝑆 = r (𝑛)) . These samples allow the estimation of the expected value 𝑣(𝑆r): 𝑣(𝑆r) ← 1 𝑀 𝑀 ∑ 𝑛=1 𝑌(r(𝑛),x(𝑛)), and similarly for 𝑣(𝑆r∪ {𝑝(𝑖 = 𝑢)}) , where 𝑝(𝑖 = 𝑢) is fixed during sampling: 𝑣(𝑆r∪ {𝑝(𝑖 = 𝑢)}) ← 1 𝑀 𝑀 ∑ 𝑛=1 𝑌(r(𝑛),𝑖 = 𝑢,x(𝑛) 𝑖=𝑢). Age Student Education Major Years Coding Developer Role Race/ ethnicity Salary Figure 1: Partial causal DAG, adapted from the full causal model in [10] by removing one feature and several edges. Here, 𝑌( r (𝑛), x (𝑛)) is the estimated value of target variable 𝑌 given a sampled realization r (𝑛) of the subset 𝑆 , and x (𝑛) , which includes the sampled values for all features not in 𝑆 ∪ {𝑖} . This term reflects the target outcome based on the sampled configuration of the subset 𝑆 and the conditionally sampled remaining features. Similarly, 𝑌( r (𝑛),𝑖 = 𝑢, x (𝑛) 𝑖=𝑢) captures target variable 𝑌 under the same realization of 𝑆 , but with feature 𝑖 explicitly set to value 𝑢 . The term x (𝑛) 𝑖=𝑢 corresponds to the sampled values of the remaining features conditioned on 𝑆 = r (𝑛) and 𝑖 = 𝑢 . By setting 𝑖 = 𝑢 , this estimate reflects the impact of the specific value 𝑢 for feature 𝑖 on the target variable 𝑌 , considering the dependencies defined in the data distribution. Example Reconsider our average salary query. CBV attributes contributions to predicates while respecting causal dependencies (Fig. 1). For Education = Master's , we find causally valid subsets 𝒮Education , and for each 𝑆 ∈ 𝒮Education , the marginal contribution is computed as 𝑣(𝑆r∪ {𝑝( Education = Master's )}) − 𝑣(𝑆r) , where 𝑣(𝑆r) is the average salary conditioned on r, the realization of predicates in 𝑆 . CBV aggregates these contributions across all subsets and realizations to quantify the importance of 𝑝( Education = Master's ) , providing a causally consistent breakdown of how individual predicates contribute to the average salary. Enumerating all subsets and performing conditional sampling can be computationally intensive, especially for highdimensional datasets. To address this, We propose to approximate CBV by employing Monte Carlo sampling [ 17 ], which involves randomly selecting a suitable number of subsets 𝑀 from 𝒮𝑖 and estimating the corresponding expected values. This approach balances efficiency and accuracy (Alg. 1). 5. Experimental evaluation We implement Banzhaf Value (BV) [ 14 ] and Causal Banzhaf Value (CBV) using PyTorch with GPU acceleration on an NVIDIA T4 GPU, with 500 Monte Carlo samples for marginal contribution estimates via conditional sampling. Experiments are conducted on the Stack Overflow Developer Survey [ 6 ], a dataset offering insights into developer demographics, education, roles, and salaries, making it ideal for income analysis. Feature subsets were derived from a partial causal DAG, adapted from the complete version in [ 10 ], by excluding one feature and several edges to construct a partial causal model, as shown in Figure 1. Figure 2illustrates the BV and CBV contributions for the different features (plots (a)-(g)), detailed for different equality and range predicates. For features without ancestors in Algorithm 1 CBV Require: Dataset 𝐷 , features 𝑁 = {1,2,…,𝑛} , target variable 𝑌; partial causal DAG 𝐺; number of samples 𝑀 Ensure: Contributions 𝛽CBV 𝑝(𝑖=𝑢) for all features 𝑖 ∈ 𝑁 and unique values for that feature 𝑢 ∈ 𝑈𝑖 1: for 𝑖 ∈ 𝑁 do 2: 𝐴𝑖← {𝑗 ∈ 𝑁 ∣ 𝑗 ≺𝐺𝑖} 3: 𝒮𝑖← {𝑆 ∣ 𝐴𝑖⊆ 𝑆,𝑆 ⊆ 𝑁 ∖ {𝑖,𝑌}} 4: for 𝑢 ∈ 𝑈𝑖do 5: for 𝑆 ∈ 𝒮𝑖do 6: for 𝑚 = 1 to 𝑀do 7: r(𝑛) ∼ 𝑃(𝑆) 8: x(𝑛) ∼ 𝑃(𝑋∖(𝑆∪{𝑖}) ∣ 𝑆 = r(𝑛)) 9: 𝑌(𝑛) = 𝑌(r(𝑛),x(𝑛)) 10: x(𝑛) 𝑖=𝑢 ∼ 𝑃(𝑋∖(𝑆∪{𝑖}) ∣ 𝑆 = r(𝑛), 𝑝(𝑖 = 𝑢)) 11: 𝑌(𝑛) 𝑝(𝑖=𝑢) = 𝑌(r(𝑛),𝑝(𝑖 = 𝑢),x(𝑛) 𝑖=𝑢) 12: end for 13: 𝑣(𝑆r) ← 1 𝑀 𝑀 ∑ 𝑛=1 𝑌(𝑛) 14: 𝑣(𝑆r∪ {𝑝(𝑖 = 𝑢)}) ← 1 𝑀 𝑀 ∑ 𝑛=1 𝑌(𝑛) 𝑝(𝑖=𝑢) 15: 𝛽CBV 𝑝(𝑖=𝑢) ←1 2𝑛−1 [𝑣(𝑆r∪ {𝑝(𝑖 = 𝑢)}) − 𝑣(𝑆r)] 16: end for 17: end for 18: end for the DAG (race/ethnicity and age in Fig. 2g and Fig. 2f), BV and CBV produce identical results, as causal dependencies are absent. Using feature contributions, we analyze cases where CBV and BV differ. For FormalEducation (Fig. 2a), BV underestimates contributions of advanced degrees (Doctoral,Master’s,Professional), and overestimates those of elementary and secondary school, by treating all effects as direct, ignoring downstream roles like developer role, and upstream roles like Age, which significantly drive salaries. CBV accounts for these causal links, producing causally consistent explanations. For UndergradMajor (Fig. 2b), BV overestimates contributions for fields like Mathematics and Social Science, which often affect salaries indirectly through roles or skills. CBV reduces these contributions while increasing contributions for fields like Computer Science, which have direct links to high-paying roles, aligning better with domain knowledge in the causal model. For DevType (Fig. 2c), BV misses the importance of roles like Marketing and C-level. CBV redistributes contributions, assigning higher values to roles like C-level, influenced by education and age (experience), and lower values to roles like Marketing. For YearsCoding (Fig. 2d), BV attributes all contributions directly to coding experience, inflating the importance of mid-level ranges (12–14 years, 15–17 years). CBV incorporates the causal dependency of YearsCoding on Age, recognizing that older individuals naturally accumulate more experience, which indirectly influences salary. This adjustment results in more accurate contributions, reducing the inflation seen in BV. For Student status (Fig. 2e), BV suggests similar contributions for full-time and part-time students, which contradicts domain knowledge, as full-time students typically have less time for work and lower salaries. This issue arises because BV ignores Age as an ancestor of student status in the DAG, which appears to be the main cause for salary levels, whereas CBV contributions are in line with domain knowledge. For (a) Predicates in Formal Education (b) Predicates in Undergraduate Major (c) Predicates in Developer Type (d) Predicates in Years Coding (e) Predicates in Student (f) Predicates in Race / Ethnicity (g) Predicates in Age Figure 2: CBV and BV Stack Overflow predicate importance for salary. CBV obtains predicate importance in line with the partial causal model in Figure 1. Plots (a)-(e) show CBV finds notably different importance attributions where BV may result in misleading conclusions. For features in plots (f) and (g) without any ancestors in the causal model, BV and CBV results are identical (thus single bar only). Figure 3: Runtime of predicate explanations aggregated per feature. CBV consistently outperforms BV. race/ethnicity (RaceEthnicity, Fig. 2f) and Age (Age, Fig. 2g), BV and CBV results coincide exactly, as the DAG has no causal incoming edges for these features. Both methods highlight disparities in salary outcomes for e.g. Native Americans and higher age. CBV offers significant computational efficiency over BV, as shown in Figure 3. By focusing only on causally valid subsets, CBV avoids unnecessary computations on infeasible configurations, resulting in a substantially reduced runtime. This improvement is especially notable for features with many causal dependencies, such as developer role. Even with Monte Carlo sampling applied to both methods, CBV is faster as it limits sampling and evaluation to valid combinations, reducing overhead and effort. For features like age and race/ethnicity, which lack causal parents, BV and CBV produce identical results and a single bar represents the values for both in these two plots. 6. Conclusion and Future Work CBV presents a novel efficient causally consistent method for predicate attribution for aggregate query explanations, addressing the limitations of traditional game-theoretic or causal methods. CBV integrates partial causal knowledge without requiring complete causal graphs, making it a valuable contribution in practice. In the following, we outline some limitations of interest for future work. While conditional sampling preserves feature dependencies and enhances accuracy, it introduces computational overhead, particularly in high-dimensional settings. CBV could also be extended to handle continuous domains directly, without the need to define predicate ranges (as e.g. for age). Another direction is enhancing CBV to provide explanations based on combinations of predicates to uncover feature interactions with high joint influence, offering richer insights into how multiple factors work together. References [1] P. Ma, R. Ding, S. Wang, S. Han, D. Zhang, Xinsight: explainable data analysis through the lens of causality, Proceedings of the ACM on Management of Data 1 (2023) 1–27. [2] F. Abuzaid, P. Kraft, S. Suri, E. Gan, E. Xu, A. Shenoy, A. Ananthanarayan, J. Sheu, E. Meijer, X. Wu, et al., Diff: a relational interface for large-scale data explanation, The VLDB Journal 30 (2021) 45–70. [3] A. Meliou, W. Gatterbauer, K. F. Moore, D. Suciu, The complexity of causality and responsibility for query answers and non-answers, arXiv preprint arXiv:1009.2021 (2010). [4] P. Bailis, E. Gan, S. Madden, D. Narayanan, K. Rong, S. Suri, Macrobase: Prioritizing attention in fast data, in: Proceedings of the 2017 ACM International Conference on Management of Data, 2017, pp. 541–556. [5] Z. Miao, Q. Zeng, B. Glavic, S. Roy, Going beyond provenance: Explaining query answers with patternbased counterbalances, in: Proceedings of the 2019 International Conference on Management of Data, 2019, pp. 485–502. [6] Stack Overflow, Developer Survey, 2021. URL: https: //survey.stackoverflow.co/2021. [7] L. S. Shapley, A value for n-person games, Contributions to the Theory of Games 2 (1953) 307–317. [8] J. F. Banzhaf III, Weighted voting doesn’t work: A mathematical analysis, Rutgers Law Review 19 (1965) 317–343. [9] T. Heskes, E. Sijben, I. G. Bucur, T. Claassen, Causal shapley values: Exploiting causal knowledge to explain individual predictions of complex models, Advances in neural information processing systems 33 (2020) 4778–4789. [10] B. Youngmann, M. Cafarella, A. Gilad, S. Roy, Summarized causal explanations for aggregate views, Proceedings of the ACM on Management of Data 2 (2024) 1–27. [11] S. Chakraborty, E. Fischer, Y. Goldhirsh, A. Matsliah, On the power of conditional samples in distribution testing, in: Proceedings of the 4th conference on Innovations in Theoretical Computer Science, 2013, pp. 561–580. [12] C. Li, Z. Miao, Q. Zeng, B. Glavic, S. Roy, Putting things into context: Rich explanations for query answers using join graphs, in: Proceedings of the 2021 International Conference on Management of Data, 2021, pp. 1051–1063. [13] E. Wu, S. Madden, Scorpion: explaining away outliers in aggregate queries, Proc. VLDB Endow. 6 (2013) 553–564. URL: https://doi.org/10.14778/2536354. 2536356. doi: 10.14778/2536354.2536356 . [14] D. Deutch, N. Frost, B. Kimelfeld, M. Monet, Computing the shapley value of facts in query answering, in: Proceedings of the 2022 International Conference on Management of Data, 2022, pp. 1570–1583. [15] O. Abramovich, D. Deutch, N. Frost, A. Kara, D. Olteanu, Banzhaf values for facts in query answering, Proceedings of the ACM SIGMOD International Conference on Management of Data 2 (2024) 1–26. [16] A. Karczmarz, T. Michalak, A. Mukherjee, P. Sankowski, P. Wygocki, Improved feature importance computation for tree models based on the banzhaf value, in: Uncertainty in Artificial Intelligence, PMLR, 2022, pp. 969–979. [17] A. Shapiro, Monte carlo sampling methods, Handbooks in operations research and management science 10 (2003) 353–425.