CS Paper Radar

LandscapeSHAP: Which Persistent Homology Class Gets the Credit?

Nikola Milićević

cs.LG math.AT ·submitted 2026-09-25 16:17 UTC · v2

Abstract

Shapley values, a solution concept from cooperative game theory, have recently become a standard tool for feature credit allocation in machine learning. They provide an axiomatically justified method to fairly distribute a model's prediction among the data features. Shapley values have not yet been applied to explain machine learning models trained on features from topological data analysis. We develop what we believe is the first such approach, focusing on the persistence landscape featurization of persistence diagrams. Because each landscape coordinate is a rank statistic, crediting a model's prediction back to individual persistent homology classes (persistence diagram points) is nontrivial. We introduce LandscapeSHAP, a method for fair credit allocation to persistence diagram points based on a model's prediction. For linear models on persistence landscapes, LandscapeSHAP has a closed form expression that gives the exact Shapley value of every persistence diagram point. In particular, there is no coalition sampling required. We further prove that the four Shapley "fairness" axioms uniquely characterize this credit allocation for any model, not only linear ones. For a general nonlinear model, this unique value can only be calculated exactly from its defining coalition averaging formula, which requires considering all $2^N$ many coalitions, where $N$ is the number of points in the persistence diagram. This is computationally intractable for persistence diagrams of realistic size. We complement the exact linear model result with an efficient Monte Carlo sampling of persistence diagram coalitions. We give convergence rates in terms of number of samples needed to approximate to a desired degree of accuracy. We also prove stability results for the LandscapeSHAP credit allocation, for any model.

Comment
42 pages, 11 figures, 1 table, fixed typos, fixed errors in Example 3.6, improved stability results, expanded bibliography

Closest papers

Nearest neighbours by meaning across the whole index.

Stability Bands for Feature Attribution: The Core, the Nucleolus and the Bargaining Set of Explained-Variance Games

cs.GT cs.LGecon.EM ·2026-11-18 ·Fernando Delbianco, Fernando Tohmé
published similarity 0.58
Abstract · Presented at the XXV Jornadas Latinoamericanas de Teoría Económica (JOLATE 2026), San Luis, Argentina, October 29, 2026. 24 pages, 5 figures

Shapley-value attributions are the default way of explaining machine-learning predictions in economics, but they report a single number per feature and say nothing about whether a coalition of features that jointly accounts for more than it receives could contest that allocation. We study feature attribution through the core, the nucleolus and the bargaining set of an explained-variance game, in which the worth of a set of features is the variance of the model's predictions that those features generate. For every feature we report a stability band (its range of shares over the core, or over the least core when the core is empty), with the nucleolus as distinguished point and a certificate that the allocation admits no justified objection. Three results organise the approach. First, for linear models the game is exactly 2-additive, with pairwise Harsanyi dividends $2β_iβ_jσ_{ij}$, so multicollinearity is what creates coalitional structure. Second, in every 2-additive game the prenucleolus coincides with the Shapley value, the (least) core is point-symmetric around it, and the core is non-empty if and only if every cut of the interaction graph has non-negative weight. The Shapley value thus always lies in the prebargaining set, and stability adds information only through band widths and interactions of order three or more. Third, for convex games the bands have a closed form and any allocation can be certified with one minimum cut. In a hedonic price model, the usual mean-SHAP explanation admits a justified objection by the coalition {Ratings, ROM, Battery}. In a gradient-boosting forecaster of retail orders the exact game has an empty core and strong higher-order interactions; the nucleolus departs from the Shapley value by up to 0.19 variance shares, and sparse third-order surrogates recover it where pairwise ones cannot.

0.46

RelShap: Relationally Consistent Shapley Explanations

cs.LG ·2026-08-11 ·Seungeun Lee, Joao Fonseca, Julia Stoyanovich
code/data similarity 0.57
Abstract

Machine learning pipelines commonly flatten relational data into single-table representations, discarding structural constraints. Widely used Shapley value-based feature attributions then rely on feature independence, evaluating the model on combinations that could never arise in the underlying data, producing misleading explanations. We propose RelShap, a framework that incorporates relational constraints and data provenance into Shapley value computation, restricting both background data and coalition evaluation to relationally valid configurations. The framework is estimator-agnostic and composes with Kernel SHAP, Monte Carlo, and Leverage SHAP without altering their sampling or weighting properties. Functional dependencies further induce equivalence classes over feature coalitions, which RelShap exploits to reduce runtime without changing Shapley values; we provide a combinatorial characterization of the expected speedup. Experiments across multiple datasets, models, and estimators show that RelShap produces explanations that are more faithful to the data-generating process, correctly identifying the dominant feature in controlled settings where existing methods, including Conditional SHAP and ManifoldShap, do not. Our code is available at: https://github.com/duneag2/relshap.

0.24

Exact Topological Compliance: Generating Persistence-Equivalent Graphs

cs.LG math.AT ·2026-10-13 ·Mattie Ji, Indradyumna Roy, Vikas Garg
top venuetheorycode/dataunusual similarity 0.55
Abstract · Accepted by NeurIPS 2026

Persistent homology summarizes the topological evolution of a graph as persistence diagrams (PDs). Generating graphs whose topology matches a target descriptor is increasingly important, yet existing topology-aware generative models rely on soft regularization, producing graphs whose PDs may only be approximately similar. We initiate a principled investigation of the generation problem: produce graphs that realize a target PD exactly. We propose two approaches guided by the implicit local and global constraints a target PD imposes. The local approach builds degree-based PD-equivalent graphs iteratively, and we prove that every output realizes the target PD and that every degree-based PD-equivalent graph is reachable. However, as shown thereafter, local generation necessarily trades off between sample diversity and reaching infeasible states. We therefore recast generation as a global constraint satisfaction problem with a complete encoding solvable by modern constraint programming solvers. This is applicable to any vertex-based permutation equivariant filtration scheme and is minimal under the degree filtration. Experiments on four standard graph generation benchmarks confirm that both methods realize the target PD exactly. Together, our methods provide a principled treatment of strict topology-compliant graph generation. Code is available at https://github.com/Aalto-QuML/ExactCompliance.

0.48

$Ψ$-Resilience: Model-Free Feature Importance from 1D Topological Signals

cs.LG cs.AI ·2026-10-01 ·Fabian Galis, Darian Onchis, Pedro Real Jurado
similarity 0.54
Abstract

We introduce $Ψ$-Resilience, a model-free feature importance method that derives explanations directly from the data itself via 1D topological signals. Our method constructs a class-disagreement landscape by estimating class-conditional densities and taking their pointwise absolute difference along the feature axis. Then, the 0-dimensional persistence of this 1D signal defines a resilience functional that aggregates only those topological features that survive perturbations up to a robustness scale which is set by the user. This gives us a context-robust importance score that is inherently auditable via the underlying 1D landscapes and their persistence. We evaluate our method on both synthetic and real datasets. On synthetic generators with specified ground-truth importance, $Ψ$-Resilience recovers the ranking of features with high fidelity, achieving Spearman rank correlations up to 0.8 and performing competitively with multiple feature importance methods, including SHAP and mutual information. On real datasets with no known ground truth, our technique agrees with these methods, with correlations up to 0.9. These results show that $Ψ$-Resilience is a stable explanation method that enables rigorous, distribution-level auditing of feature importance without relying on a predictive model.

0.31

Nested Ensemble Learning with Topological Data Analysis for Graph Classification and Regression

cs.LG stat.MLstat.AP ·2026-11-11 ·Innocent Abaa, Umar Islambekov
published similarity 0.54
Abstract · This is the published version of the article. Published in International Journal of Topology, MDPI, DOI: 10.3390/ijt2040017. Link to the off…

We propose a nested ensemble learning framework that utilizes Topological Data Analysis (TDA) to extract and integrate topological features from graph data, with the goal of improving performance on classification and regression tasks. Our approach computes persistence diagrams (PDs) using lower-star filtrations induced by three filter functions: closeness, betweenness, and degree2 centrality. To overcome the limitation of relying on a single filter, these PDs are integrated through a data-driven, three-level architecture. At Level-0, diverse base models are independently trained on the topological features extracted for each filter function. At Level-1, a meta-learner combines the predictions of these base models for each filter to form filter-specific ensembles. Finally, at Level-2, a meta-learner integrates the outputs of these filter-specific ensembles to produce the final prediction. We evaluate our method on both simulated and real-world graph datasets. Experimental results demonstrate that our framework consistently outperforms base models and standard stacking methods, achieving higher classification accuracy and lower regression error. It also surpasses existing state-of-the-art approaches, ranking among the top three models across all benchmarks.

0.55

Proportionality in Ranking Compression

cs.GT cs.LGecon.TH ·2026-10-16 ·Daniel Halpern, Xinyu Liu, Evi Micha, Yu Peng Ng, Warut Suksompong
top venuetheory similarity 0.53
Abstract · Appears in the 40th Annual Conference on Neural Information Processing Systems (NeurIPS), 2026

Motivated by applications in reinforcement learning from human feedback, we consider a setting where a given collection of rankings needs to be compressed into a smaller collection of rankings. This can also be seen as a combination of two fundamental social choice frameworks: ranking aggregation and multiwinner voting. We propose three proportionality notions that capture different types of representation in this setting: positional proportionality, pairwise proportionality, and proportionality for solid coalitions (PSC). On the one hand, we show that positional proportionality and PSC are always satisfiable for any input rankings and target compression size, and a desired output can be found in polynomial time. On the other hand, we prove that pairwise proportionality cannot be satisfied in general, but can nevertheless be attained when the input rankings are single-peaked or single-crossing.

0.33

Optimally Selecting Representative Agents from a Metric Space

cs.GT cs.LG ·2026-08-29 ·Benjamin Cookson, Eva Deltl, Yeeseok Oh
theory similarity 0.51
Abstract

This paper studies the problem of proportionally fair clustering, where the goal is to select $k$ ``centers'' from a metric space that fairly represent a set of agents who also lie in the metric space. Specifically, we focus on finding a clustering satisfying a fairness property known as the Droop core. In the practical special case in which the set of feasible center locations contains every agent location, the previous best-known result guaranteed a $(1 + \sqrt{2})$-approximation of the Droop core, while the best-known lower bound was $2$. In this paper, we show that this lower bound is tight and that a clustering in the $2$-Droop core always exists. Further, we show that such a clustering can be achieved by only selecting centers from locations in the metric space where an agent resides. We establish this using Scarf's theorem guaranteeing a nonempty core for balanced non-transferable utility games. This result has several interesting corollaries. Most notably, it resolves the $β$-plurality problem of Aronov et al. [2021] for general metric spaces. The main result of this paper was generated by $\mathtt{ChatGPT}$-$\mathtt{5.6}$-$\mathtt{Sol}$ through a series of interactions with the authors. The authors of this paper verified the generated proof and rewrote it for clarity.

0.27

Geometric Kernel Diversity: An Axiomatic Diversity Measure in Euclidean Space

cs.CG cs.CCcs.LG ·2026-10-14 ·Ditbul Ban, Younghun Roh, Julian Shun, Vihan Lakshman
similarity 0.51
Abstract · 55 pages

Quantifying the diversity of a set of objects is a fundamental problem in machine learning and statistics. Mironov and Prokhorenkova (2025) recently showed that three axioms-monotonicity, uniqueness, and continuity-are crucial for a reliable diversity measure and that none of the standard metrics in the literature satisfy all three. They also constructed two measures that do satisfy the axioms, but both are NP-hard to compute, leaving open the question of whether efficient axiomatic diversity measures can exist. We study a Euclidean-restricted version of this question. We introduce Geometric Kernel Diversity (GKD), which associates a radial kernel solid with each point and measures the volume of their union. We show that canonical GKD satisfies all three Mironov-Prokhorenkova axioms on Euclidean-realizable inputs. For canonical GKD, we give exact polynomial-time algorithms in dimensions $d \le 3$. In arbitrary dimensions, we give a randomized algorithm that returns a $(1 \pm \varepsilon)$-approximation with probability at least $1-δ$ in time $O \left(\frac{nd}{\varepsilon^2}\log\frac{2}δ\right)$ for $n$ points. The axiomatic guarantee applies to exact canonical GKD; the randomized algorithm approximates this deterministic quantity. We further show that the two diversity measures of Mironov and Prokhorenkova (2025) remain NP-hard on Euclidean-realizable inputs and, unless $\mathrm{NP} = \mathrm{RP}$, admit no FPRAS even on this restricted domain.

0.24