betaFeedback

WorksComputer Science

TopoSHAP: Shapley for Explainable and Efficient Topological Deep Learning

Abstract

Topological deep learning (TDL) extends learning on graphs, such as molecules or social networks, to higher-order structures, such as rings in a molecule or groups in a social network. Explaining which of these structures drive a model's predictions, and which architectural components matter most for its performance, remains challenging. We introduce TopoSHAP, an efficient and general explanation framework that addresses both questions across topological domains and model architectures. TopoSHAP-cell assigns Shapley values to topological data cells and extracts compact explanations. These explanations match or outperform graph-based counterparts on GraphXAI benchmark data while running up to 112×\times faster. They also reveal advantageous topological feature design, leading to measured improvements in explanation recovery and predictive accuracy. On the architecture side, TopoSHAP-neighbor explains how neighborhoods contribute to model performance, and turns these evaluations into a backward-elimination search that identifies smaller, competitive architectures early in training. This is up to 11.3×11.3\times cheaper than traditional TDL training sweeps.

Introduction

Graph neural networks (GNNs) learn from relational data, such as molecules and social networks [21]. They achieve this by explicitly modeling pairwise interactions between the nodes (atoms, people) of the data. However, real-world systems often exhibit interactions that are inherently multiway. For instance, atoms can form rings which have critical functional roles; people can form groups whose nature goes beyond pairwise relationships. These higher-order interactions are not explicitly represented in standard GNNs. Topological neural networks (TNNs) address this limitation by explicitly modeling higher-order structure [19, 30]. In particular, topological deep learning (TDL) uses combinatorial complexes to organize interactions into cells of different ranks: atoms are rank-0 cells, bonds are rank-1 cells, and rings are rank-2 cells. At each layer, TNNs update each cell feature based on the features of its neighboring cells. On standardized topological benchmarks, TNNs often match or exceed GNN accuracy [39].

As TDL moves towards domain-specific applications like chemistry and materials science [29], practitioners face two black box challenges. First, they need to understand which structures drive these predictions. For a molecular model, for example, one may be compelled to reveal the chemical features and molecular structures the model deems relevant to the target property. Second, TDL practitioners do not know a priori what topological relations, or neighborhoods, matter for their task. Current TDL pipelines rely on an expensive hyperparameter search to identify the best architecture [31, 4]. This is not only expensive but also fails to provide practical insight as to why a specific architecture worked better.

Machine learning explainers are a promising avenue to opening these black boxes. They investigate model behavior by attributing predictions to parts of the input [8, 33, 23]. However, existing post-hoc explainers are limited to graph [36, 43, 24, 45, 28] and hypergraph ([25, 38]) neural networks. We propose the first explainer for general topological domains, encompassing both prediction and performance explanation.

Contributions. We introduce TopoSHAP, a unified game-theoretic framework for explaining TDL models, which attributes both predictions and performance to the cells and neighborhoods of a combinatorial complex. TopoSHAP is available at github.com/mathildepapillon/toposhap.

  • We explain predictions across ranks. We formulate a cooperative game in which cells of every rank are players, producing per-cell Shapley attributions and compact explanations. Across both outputs, we match or outperform graph explanation methods on GraphXAI benchmarks. We also propose the first explanations of topological benchmark datasets going beyond hypergraphs. We call this component TopoSHAP-cell.

  • We use cell attributions to improve topological features. Rank-specific attributions show that topological features, typically built by aggregating node features, retain information about lower-rank cells. Using this finding, we design new topological features and match or improve explanation recovery on GraphXAI benchmarks.

  • We explain performance and use it to select architectures. We formulate a second game in which a model’s neighborhood-specific modules are players and test performance is the payoff. We propose an inexpensive backward-elimination procedure that selects neighborhood-specific modules for full training. This reduces training compute by up to an order of magnitude relative to standard TDL training sweeps. We call this component TopoSHAP-neighbor.

Related Work

TopoSHAP builds on three lines of work: (i) topological deep learning, the subfield proposing the TNNs we explain; (ii) Shapley-value attribution in machine learning, the game-theoretic background we rely on; and (iii) GNN explainers, the methods we generalize. We review each below.

Topological deep learning (TDL). TDL proposes neural networks that learn from higher-order topological domains generalizing graphs, such as: simplicial complexes ([11]), cellular complexes ([5]), hypergraphs ([12]) and combinatorial complexes ((Hajji et al., 2023)). TopoTune ([31]) defines the architectural design space we study. Specifically, we consider Generalized Combinatorial Complex Neural Networks (GCCN) as they are general TNNs that are conveniently specified by the set of neighborhoods they each admit. We also consider the non-message passing version of GCCNs, introduced in HOPSE ((Bernárdez et al., 2025), which leverage graph embeddings. Our framework treats HOPSE and message-passing TNNs identically because it only requires forward evaluations. Regarding implementation, TopoBench [39] standardizes liftings, models, and training across topological domains. We host our contribution and experiments there.

Shapley-value attribution in machine learning. The Shapley value credits each player in a cooperative game with its average marginal contribution across coalitions, and is the unique such credit assignment satisfying a standard set of fairness axioms [35]. SHAP brought this machinery to machine learning with input features as players [23], and interaction indices extend credit to coalitions [17]. In TopoSHAP-cell, our players are the cells (node, edge, hyperedge, face, and so on) that make up the topological domain. Because exact values cost exponential time in the number of players, larger complexes use unbiased permutation sampling [6, 37]. Shapley values are unsound for selecting players when two players can do the same job [14]. Our framework therefore uses the game only to order candidates, and compares the shortlisted candidates by validation of fully trained models (§ 4.2).

Explaining GNNs and Hypergraph Neural Networks. Existing GNN explainers broadly fall into two families. The first family of explainers learns continuous masks over the graph’s nodes and edges. GNNExplainer learns a new mask for each instance, requiring a new optimization run per prediction [43]. PGExplainer trains a single mask-generating model once over the dataset, which then generalizes to new instances without further optimization [24]. Second, search-based explainers return discrete subgraphs scored by prediction preservation: SubgraphX explores connected subgraphs by Monte-Carlo tree search, scoring each with a sampled Shapley reward [45], and Zorro greedily selects sparse masks with stability guarantees [15]. GraphSVX [9] and GraphSHAP-IQ [28] bring Shapley values and exact any-order Shapley interactions to GNNs, with nodes and features as players, and Covert et al. (2021) unify such methods by their choice of removal operator, model behavior, and summary. TopoSHAP instantiates that framework with cells as players and detachment on the complex as the removal operator. Shapley values over internal model components also precede us in neuron attribution [16] and structured pruning [2]. TopoSHAP-neighbor differs by scoring architectural neighborhoods with masked validation accuracy and by never selecting on the Shapley ranking itself (§ 4.2). All of the above operate on nodes, edges, features, or network units.

Beyond graphs, HyperEX explains hypergraph predictions through node–hyperedge associations [25], and SHypX returns explanatory subhypergraphs [38]. Because hypergraphs are simply rank-≤1\le1 combinatorial complexes, these approaches also do not handle cells across ranks. Counterfactual hypergraph explanations [40] pursue prediction-changing edits, complementary to our prediction-preserving objective. FORGE [36] lifts graphs to cell complexes before explaining, yet still outputs node-level attribution. TopoSHAP instead defines games over cells across ranks of a combinatorial complex (of which graphs and hypergraphs are special cases) and over architectural neighborhoods. It is also the first to propose prediction attribution alongside validation-based architecture selection.

Preliminaries

TopoSHAP relies on three components: (i) the data, combinatorial complexes (§ 3.1), whose cells are the players of the cell game, (ii) the models, topological neural networks (TNNs) specified by a set of neighborhoods (§ 3.2), whose neighborhoods are the players of the neighbor game, and (iii) the game-theoretic machinery, Shapley values (§ 3.3).

Combinatorial Complexes and Their Cells

Combinatorial complexes are discrete topological domains that generalize graphs, as follows.

Definition 1 (Combinatorial complex and cells [19]). A combinatorial complex is a triple C=(V,K,k)\mathcal{C}=(V,\mathcal{K},k) where VV is a finite set of nodes, K⊆2V∖{∅}\mathcal{K}\subseteq2^V\setminus\{\varnothing\} is a set of cells, and k:K→Z≥0k:\mathcal{K}\to\mathbb{Z}_{\geq0} is a rank function monotone with respect to inclusion: x⊆y⇒k(x)≤k(y)x\subseteq y\Rightarrow k(x)\leq k(y).

Cells are the building blocks of the combinatorial complex (depicted in Figure 1, top left). Cells of rank 0, 1 and 2 are called nodes (depicted in blue), edges (depicted in pink) and faces (depicted in burgundy), respectively. Cells of higher ranks represent higher multi-way interactions between nodes. Graphs and hypergraphs are special cases of combinatorial complexes, where all cells have rank ≤1\le1. Other higher order domains used in TDL are also special cases, such as simplicial complexes, whose rank-2 cells are triangles and whose cells are closed under taking subsets, and cellular complexes, whose faces may be arbitrary polygons. Combinatorial complexes generalize them all ([19]), which is why we define TopoSHAP on them.

Figure 1. TopoSHAP explains a Topological Neural Network’s predictions and performance. A. TopoSHAP-cell considers the cells of the input combinatorial complex as players (1). Given certain coalitions SiS_i of those players (2), it evaluates the model’s predictions (3). Averaging marginal contributions over coalitions outputs one Shapley value per cell and a sub-complex best preserving the prediction (4). B. TopoSHAP-neighbor manipulates the neighborhoods that contribute to feature updates in the TNN (1). It briefly trains a model with all neighborhoods, then masks coalitions of them (2) to measure neighborhood impact on test performance (3). Averaging marginal contributions over coalitions outputs one attribution value per neighborhood and a subset of that preserves model performance (4).

Raw data is often provided in graph format. A topological lifting converts a graph into a higher order domain by promoting substructures of nodes to higher-order cells. For example a cycle of nodes in a graph can be defined as a face in a cellular complex ([5]). Of the datasets we use, only MANTRA ([3]) is natively defined on a higher order domain, namely the simplicial complex. We lift the other (graph) datasets we use to the cellular complex domain using liftings available in TopoBench ([39]). We will see that the choice of lifting impacts both accuracy and explanation quality (§ 5).

Topological Neural Networks and Their Neighborhoods

TNNs generalize GNNs to consider higher order domains. Here, we specifically consider the combinatorial complex for its generality, encompassing graph, hypergraphs, simplicial/cell complexes, and more. A TNN architecture is specified by a set of neighborhoods, the relationships through which cells interact on the combinatorial complex. We first define neighborhoods formally, then provide preliminaries for the two model families we use in experiments: GCCNs, which pass messages along the chosen neighborhoods, and HOPSE, which encodes them without message passing.

Definition 2 (Neighborhood ([19, 4]). A neighborhood on a combinatorial complex C=(V,X,k)\mathcal{C} = (V, \mathcal{X}, k) is a function N:X→2X\mathcal{N} : \mathcal{X} \to2^{\mathcal{X}} assigning to each cell xx a set N(x)\mathcal{N}(x) of cells, its neighbors. The standard neighborhoods are indexed by ranks. For a cell xx of rank tt and a rank s≠ts \ne t, the incidence

Is→t(x)={y∈X∣k(y)=s, x⊊y or y⊊x}I_{s \to t}(x) = \{ y \in\mathcal{X} \mid k(y) = s,\ x \subsetneq y\ \text{or}\ y \subsetneq x \}

collects the rank-ss cells that contain xx (when s>ts > t) or are contained in xx (when s<ts < t), and the adjacency

At,s(x)={y∈X∖{x}∣k(y)=t, Is→t(x)∩Is→t(y)≠∅}A_{t,s}(x) = \{ y \in\mathcal{X} \setminus\{x\} \mid k(y) = t,\ I_{s \to t}(x) \cap I_{s \to t}(y) \ne\varnothing\}

collects the rank-tt cells that share a rank-ss incident cell with xx.

Intuitively, neighborhoods are the routes along which cells exchange information. Incidences connect cells of different ranks, e.g., I1→0I_{1 \to0} links each node to the edges containing it; adjacencies connect cells of the same rank through a shared cell, e.g., A0,1A_{0,1} links nodes joined by an edge. In practice each neighborhood is stored as a sparse matrix over cells.

Given a set N={N1,…,Nm}\mathcal{N} = \{\mathcal{N}_1,\ldots,\mathcal{N}_m\} of neighborhoods, each N∈N\mathcal{N} \in\mathcal{N} decomposes C\mathcal{C} into an ordinary graph on cells, the strictly augmented Hasse graph GN\mathcal{G}_{\mathcal{N}}, where cells participating in the neighborhood are nodes and the relationships of the neighborhood are edges ([31]). With this formulation, the combinatorial complex C\mathcal{C} can be represented as a collection of smaller graphs, one per neighborhood. Both TNN families we use are built directly on this collection. Because both models represent each neighborhood as an architectural component, removing a neighborhood from N\mathcal{N} is a well defined operation on the model.

Definition 3 (Generalized combinatorial complex network (GCCN)) ([31]). A GCCN stacks LL message-passing layers over the strictly augmented Hasse graphs {GN}N∈N\{\mathcal{G}_{\mathcal{N}}\}_{\mathcal{N}\in\mathcal{N}}. At layer ℓ\ell, every cell xx exchanges a message with its neighbors along each graph GN\mathcal{G}_{\mathcal{N}}, using a GNN layer ψN\psi_{\mathcal{N}} dedicated to that neighborhood; the messages arriving from a single neighborhood are pooled together, and the results are then pooled once more across neighborhoods to update xx’s feature:

hx(ℓ+1)=ϕ(hx(ℓ), ⨂N∈N ⨁y∈N(x)ψN(hx(ℓ),hy(ℓ))).(1)\mathbf{h}_{x}^{(\ell+1)} = \phi\left(\mathbf{h}_{x}^{(\ell)},\ \bigotimes_{\mathcal{N}\in\mathcal{N}}\ \bigoplus_{y\in\mathcal{N}(x)} \psi_{\mathcal{N}}\left(\mathbf{h}_{x}^{(\ell)},\mathbf{h}_{y}^{(\ell)}\right)\right). \tag*{(1)}

Definition 4 (Higher-Order Positional and Structural Encoder (HOPSE)) ([4]). HOPSE replaces every GNN layer ψN\psi_{\mathcal{N}} with a fixed positional or structural encoder, such as Laplacian

eigenvectors, computed once on the strictly augmented Hasse graph GN\mathcal{G}_N rather than learned during training. For every cell xx, HOPSE collects the encodings xx receives this way from each of its Hasse graphs, concatenates them with xx's own input feature, and passes the result through a small learnable network, shared across cells of the same rank, to produce xx's final feature.

Measuring a Contribution to a Game: Shapley Values and Interactions

A cooperative game (P,v)(P,v) consists of players PP, ∣P∣=n|P|=n, and a value function v:2P→Rv:2^P \to\mathbb{R} with v(∅)=0v(\varnothing)=0, where v(S)v(S) is the gain that the coalition S⊆PS \subseteq P secures on its own. The question is how to divide the total gain v(P)v(P) among the nn players.

The Shapley value [35] of player ii averages its marginal contribution over all coalitions:

ϕi(v)=∑S⊆P∖{i}∣S∣!(n−∣S∣−1)!n![v(S∪{i})−v(S)].(2)\phi_i(v)=\sum_{S\subseteq P\setminus\{i\}}\frac{|S|!(n-|S|-1)!}{n!}\left[v(S\cup\{i\})-v(S)\right]. \tag*{(2)}

It is the unique attribution satisfying four desirable axioms: (i) efficiency, i.e., attributions credit the total gain exactly, ∑iϕi=v(P)\sum_i\phi_i=v(P), (ii) symmetry where ϕi=ϕj\phi_i=\phi_j whenever v(S∪{i})=v(S∪{j})v(S\cup\{i\})=v(S\cup\{j\}) for all SS, (iii) null player where ϕi=0\phi_i=0 whenever v(S∪{i})=v(S)v(S\cup\{i\})=v(S) for all SS, and (iv) linearity which makes credit additive across games, ϕi(v+w)=ϕi(v)+ϕi(w)\phi_i(v+w)=\phi_i(v)+\phi_i(w). These axioms explain the adoption of Shapley values in explainable machine learning. For this reason, this is the attribution that we will use in TopoSHAP.

Method: TopoSHAP

TopoSHAP asks two questions about a trained TNN. Which cells of an input drove its prediction? Which neighborhoods of the architecture drove its performance? Each question can be answered with a cooperative game (§ 3.3), which we call TopoSHAP-cell and TopoSHAP-neighbor, respectively. Figure 1 compares the two games.

TopoSHAP-cell: Explaining Predictions.

The cell game. The players PP are the cells of the input complex, at every rank; n=∣P∣n=|P|. A coalition S⊆PS\subseteq P specifies a perturbed input C[S]C[S] in which every cell outside SS is detached. Specifically, its feature row is zeroed, neighborhoods are rebuilt without it, and it is excluded from readout pooling. Retained cells keep the input features they were supplied with; cells are independent players, so a face remains when one of its vertices is detached, losing only its incidence to that node. For HOPSE, whose inputs include precomputed encodings of the complex, the encodings are recomputed on C[S]C[S].

The value of a coalition is v(S)=f(C[S])−f(C[∅])v(S)=f(C[S])-f(C[\varnothing]), where f(C[S])f(C[S]) is the model's prediction given the coalition, and f(C[∅])f(C[\varnothing]) is the model's prediction given an empty complex, leaving the encoder and readout biases. As PP the rebuilt input reproduces the model's stored forward pass. Appendix § 11 gives the full algorithm.

Output 1: cell attributions. The Shapley value ϕi(v)\phi_i(v) of Equation (2) credits each player with its average marginal contribution to the coalition value v(S)v(S). The Shapley axioms ensure efficiency, meaning the Shapley values sum to v(P)v(P), as well as null-player behavior, meaning a player jj the model never uses gets ϕj(v)=0\phi_j(v)=0. To compute exact Shapley values, Equation (2) requires every possible coalition. While this is feasible for small numbers of players (such as in TopoSHAP-neighbor where n=11n=11 so 2n=20482^n=2048 coalitions), it is prohibitively expensive for many players (such as in TopoSHAP-cell for large complexes). In that case, we follow Castro et al. [6] and draw TT random orderings of the players, add them one at a time to a coalition, and average the marginal changes. This unbiased estimate costs O(Tn)O(Tn) model evaluations.

Output 2: explanation via greedy pruning. An explanation is a small set of players that together preserve the model's prediction; we approximate it with one greedy candidate per size. Starting from all players PP, we repeatedly eliminate the player whose removal lowers vv the least. Because the steps are nested, one pass returns a candidate coalition S^b\widehat{S}_b for every size bb, at most (n2+n)/2(n^2+n)/2 evaluations in total. Each S^b\hat{S}_b is a compact, high-scoring coalition on the greedy path. Greedy elimination carries no optimality guarantee, so S^b\hat{S}_b need not be the best size-bb coalition.

Axioms as unit tests. For an exact game the Shapley axioms hold with equality; our implementation matches brute force to 2.254×10−142.254 \times10^{-14}, and separate consistency checks test the masking itself (Section A.1).

TopoSHAP-neighbor: Explaining Performance

TopoSHAP-neighbor evaluates how neighborhoods contribute to a trained model’s validation accuracy. These evaluations support both neighborhood attribution and architecture selection. The players are the candidate neighborhoods N\mathcal{N}, with n=∣N∣n = |\mathcal{N}|. Our main rank-2 architecture-selection experiments consider eleven neighborhoods. Here, a coalition S⊆NS \subseteq\mathcal{N} specifies a model where the neighborhood-specific modules (message-passing modules in GCCN or encoding MLP blocks in HOPSE) are constrained to neighborhoods in SS. The encoder and readout backbones are left untouched.

Evaluating coalitions. In practice, training a separate model for every coalition requires 2n2^n training runs. With the goal of TopoSHAP-neighbor being practical in applied TDL settings, we propose a cheaper alternative. Specifically, we briefly train a full version of the model containing all neighborhoods, and then evaluate coalitions on a frozen version of it. For each SS, we mask any neighborhood-specific modules outside SS and measure the resulting validation accuracy, a(S)a(S). We define the value function v(S)=a(S)−a(∅)v(S) = a(S) - a(\emptyset) where a(∅)a(\emptyset) is the accuracy of the same model with all neighborhood components masked, leaving its encoder and readout active. Each coalition therefore requires one validation pass. This brief initial training follows prior work on identifying ideal architectures from early epochs ([44, 13]) and low-fidelity candidate ranking in architecture and hyperparameter search ([22, 26]).

Output 1: neighborhood attributions. The Shapley value of a neighborhood measures its average marginal contribution to v(N)v(\mathcal{N}). We compute these values exactly by evaluating all 2n2^n coalitions S⊆NS \subseteq\mathcal{N}. We note that these attributions describe neighborhood contributions in one frozen model, meaning they do not establish which neighborhoods a separately trained model would need. For example, a model may learn to rely on one of two neighborhoods carrying equally useful information.

Output 2: architecture selection. We use the coalition evaluations to select architectures through backward elimination, following backward stepwise selection and recursive feature elimination ([18, 20]). Starting from S=NS = \mathcal{N}, we evaluate every possible single-neighborhood removal and retain the coalition with the highest validation accuracy. We repeat this process down to one neighborhood, obtaining one candidate per size. Each step reassesses removal effects given the neighborhoods that remain (Algorithm 2).

From these nn candidates, we choose BB to train further, where 1≤B≤n1 \le B \le n. We first select the stop candidate: the architecture immediately before the first removal whose accuracy loss exceeds

τ=p(1−p)m,p=a(N),\tau= \sqrt{\frac{p(1-p)}{m}}, \qquad p = a(\mathcal{N}),

where mm is the number of validation examples and pp is the briefly trained full model’s validation accuracy. This estimated binomial standard error provides a data-dependent pruning threshold. If no removal exceeds it, the stop candidate is the last remaining neighborhood. The threshold marks a candidate without halting elimination, and does not bound the cumulative accuracy loss relative to the full model.

We select the remaining B−1B - 1 architectures by selecting the remaining candidates with the highest validation accuracy. Each of the BB selected architectures is initialized using the full frozen model and then trained to completion. Of the BB trained models, we select the one with the highest final validation accuracy. This pipeline provides an inexpensive alternative to proposing architectures based on early neighborhood contributions. Algorithm 2 gives the complete procedure.

Results I: Explaining Predictions with TopoSHAP-cell

This section asks which cells a trained TNN relies on, considering benchmark explanation graph datasets, lifted topological versions of those datasets, as well as unlabeled standard topological datasets.

Setup. We use four GraphXAI molecular benchmark data with ground truth explanations from Agarwal et al. [1], four lifted topological benchmark data from TopoBench (Telyatnikov et al. [39]), and the MANTRA dataset (Ballester et al. [3]), a native simplicial complex dataset. All comparisons use identical splits and three seeds (mean ± sd). Explanation accuracy is Graph Explanation Accuracy (GEA), the Jaccard overlap between a size-bb explanation and a same-size ground-truth motif (Agarwal et al. [1]). In cases where no ground truth is available, we measure explanation faithfulness using deletion-Area-Under-the-Curve (deletion-AUC; Petsiuk et al. [32]). To compute it, cells are detached cumulatively from most to least important and the predicted-class probability is integrated over the removal process. A faithful ranking collapses the prediction quickly, so lower is better (formula in Section A.1). Lastly, the alignment gap Δ=v(S^b)−v(Sgt)\Delta= v(\hat{S}_b) - v(S_{\mathrm{gt}}) compares the greedy candidate S^b\hat{S}_b to the annotated ground truth motif SgtS_{\mathrm{gt}}. A positive Δ\Delta occurs when a same-size coalition scored above the annotated motif, indicating that the annotation is in fact not the game’s optimum on that instance. Datasets and training details are in Section B; evaluation settings in Section C.

TopoSHAP-cell on Graphs Matches GNN Explainers for Cheap

TopoSHAP-cell matches within 1σ or outperforms every baseline. In Table 1, all methods explain the same parameter-matched models of two types: GCN (Kipf and Welling, [21]) and GIN (Xu et al., [41]). The table shows each method’s better model-type per-dataset results are in Table 4. We evaluate both outputs by their overlap with the annotated motif (the ground truth): attribution selects the bb highest-scoring nodes, while greedy pruning retains a size-bb set through successive removals. Greedy pruning achieves higher motif overlap on Benzene with GIN; attribution-based selection performs better on Mutagenicity and Alkane-Carbonyl for both model types.

BenzeneFluorideCarbonylMutagenicityAlkaneCarbonyls / inst.
TopoSHAP (attribution)0.859 ± 0.0090.507 ± 0.0470.798 ± 0.1240.500 ± 0.0813.3–4.0
TopoSHAP (explanation)0.969 ± 0.0090.340 ± 0.0100.480 ± 0.1350.354 ± 0.1250.33–0.67
SubgraphX0.796 ± 0.0290.439 ± 0.1070.344 ± 0.0360.296 ± 0.01021–52
PGExplainer0.642 ± 0.0440.555 ± 0.0670.290 ± 0.1020.205 ± 0.160<0.01†
GNNExplainer0.443 ± 0.0540.210 ± 0.0140.158 ± 0.0230.162 ± 0.0490.80–0.82
Random0.250 ± 0.0000.219 ± 0.0000.132 ± 0.0000.173 ± 0.000<0.01

Table 1. Explanation accuracy on graphs. GEA on parameter-matched GNN models; per method the better of GCN/GIN is shown (both in Section C.1). Last column: measured seconds per instance; †plus one-time training (142–1501 s per dataset). Bold is best and gray is within ≤ 1σ.

BenzeneFluorideMutagenicityAlkane
GCN models
TopoSHAP (attribution)0.467±0.0780.467 \pm0.0780.398±0.0400.398 \pm0.0400.723±0.0740.723 \pm0.0740.411±0.0580.411 \pm0.058
TopoSHAP (explanation)0.377±0.0120.377 \pm0.0120.289±0.0940.289 \pm0.0940.317±0.0620.317 \pm0.0620.318±0.0740.318 \pm0.074
TopoSHAP (explanation, zero-fill)0.648±0.0550.648 \pm0.0550.244±0.0340.244 \pm0.0340.561±0.0620.561 \pm0.0620.378±0.0750.378 \pm0.075
SubgraphX0.664±0.0270.664 \pm0.0270.226±0.0240.226 \pm0.0240.344±0.0360.344 \pm0.0360.276±0.0130.276 \pm0.013
PGExplainer0.642±0.0440.642 \pm0.0440.429±0.0920.429 \pm0.0920.290±0.1020.290 \pm0.1020.203±0.1370.203 \pm0.137
GNNExplainer0.443±0.0540.443 \pm0.0540.210±0.0140.210 \pm0.0140.152±0.0330.152 \pm0.0330.066±0.0500.066 \pm0.050
Random0.250±0.0000.250 \pm0.0000.219±0.0000.219 \pm0.0000.132±0.0000.132 \pm0.0000.173±0.0000.173 \pm0.000
GIN models
TopoSHAP (attribution)0.859±0.0090.859 \pm0.0090.507±0.0470.507 \pm0.0470.798±0.1240.798 \pm0.1240.500±0.0810.500 \pm0.081
TopoSHAP (explanation)0.969±0.0090.969 \pm0.0090.340±0.0100.340 \pm0.0100.480±0.1350.480 \pm0.1350.354±0.1250.354 \pm0.125
TopoSHAP (explanation, zero-fill)0.569±0.0640.569 \pm0.0640.313±0.0380.313 \pm0.0380.273±0.1640.273 \pm0.1640.391±0.0280.391 \pm0.028
SubgraphX0.796±0.0290.796 \pm0.0290.439±0.1070.439 \pm0.1070.274±0.0550.274 \pm0.0550.296±0.0100.296 \pm0.010
PGExplainer0.453±0.2390.453 \pm0.2390.555±0.0670.555 \pm0.0670.175±0.2000.175 \pm0.2000.205±0.1600.205 \pm0.160
GNNExplainer0.256±0.0810.256 \pm0.0810.166±0.0350.166 \pm0.0350.158±0.0230.158 \pm0.0230.162±0.0490.162 \pm0.049
Random0.250±0.0000.250 \pm0.0000.219±0.0000.219 \pm0.0000.132±0.0000.132 \pm0.0000.173±0.0000.173 \pm0.000

Table 4. Explanation accuracy by model type. Node-level GEA (mean ±\pm sd, 3 seeds) for each parameter-matched model type, one panel per type. The zero-fill row runs our explanation search with feature zero-filling in place of detachment. Bold: column best; gray: within one sd.

TopoSHAP’s explanation output is 64–112× cheaper per instance than search-based explanation. The explanation output takes 0.33–0.67 s per instance and the attribution output 3.3–4.0 s, against 21–52 s for its graph counterpart SubgraphX (Table 1). PGExplainer has a costly training setup: for computing explanations it exceeds TopoSHAP’s cost on every dataset (Table 5).

MethodBenzeneFluorideMutagenicityAlkane
TopoSHAP (attribution)3.3±0.93.3 \pm0.93.3±0.83.3 \pm0.84.0±3.14.0 \pm3.13.3±0.83.3 \pm0.8
TopoSHAP (explanation)0.33±0.110.33 \pm0.110.35±0.110.35 \pm0.110.67±1.050.67 \pm1.050.36±0.110.36 \pm0.11
SubgraphX21.1±16.121.1 \pm16.134.3±28.934.3 \pm28.951.6±79.451.6 \pm79.440.4±28.840.4 \pm28.8
PGExplainer{sup}†`0.002±0.0000.002 \pm0.0000.002±0.0000.002 \pm0.0000.002±0.0000.002 \pm0.0000.002±0.0000.002 \pm0.000
GNNExplainer0.81±0.080.81 \pm0.080.80±0.080.80 \pm0.080.80±0.070.80 \pm0.070.82±0.080.82 \pm0.08
Random0.001±0.0010.001 \pm0.0010.003±0.0100.003 \pm0.0100.001±0.0010.001 \pm0.0010.002±0.0030.002 \pm0.003
PGExplainer training (one-time){sup}†`1500.8±159.51500.8 \pm159.51081.3±115.91081.3 \pm115.9221.3±21.7221.3 \pm21.7142.5±15.5142.5 \pm15.5

Table 5. Per-instance explanation cost. Measured wall-clock seconds per explained instance (mean ±\pm sd over both model types and 3 seeds), on one NVIDIA H200 per run. †PGExplainer’s per-instance entry is inference only; the last row is its one-time training.

TopoSHAP-cell on Higher-Order Data Recovers Explanations

We consider the rank-2 GCN containing all eleven possible neighborhoods. We lift the GraphXAI datasets conventionally by converting chordless cycles of up to 10 nodes to a face (Section B.1).

Standard lifting preserves aggregated node information. The standard lifting assigns face features using the sum of their incident nodes’ features. In TopoSHAP-cell, because retained cells keep their original features during masking, this summary information remains available regardless of node or edge masking. We find that selected coalitions sometimes retain faces while discarding edges (Benzene, Section C.2), suggesting some models use these summaries. The selected coalitions also outscore the annotated motifs on most evaluated instances (Δ>0\Delta> 0; Table 2), showing that motif recovery and the model’s preferences under masking can diverge.

BenzeneFluorideCarbonylMutagenicityAlkaneCarbonyl
attribution, structural lifting0.471±0.0180.471 \pm0.0180.491±0.0350.491 \pm0.0350.326±0.0650.326 \pm0.0650.333±0.0970.333 \pm0.097
attribution, standard lifting0.459±0.1920.459 \pm0.1920.516±0.0890.516 \pm0.0890.257±0.0770.257 \pm0.0770.348±0.0430.348 \pm0.043
explanation, structural lifting0.725±0.1050.725 \pm0.1050.426±0.0270.426 \pm0.0270.436±0.0810.436 \pm0.0810.362±0.1300.362 \pm0.130
explanation, standard lifting0.509±0.1880.509 \pm0.1880.372±0.0040.372 \pm0.0040.289±0.1170.289 \pm0.1170.364±0.0530.364 \pm0.053
model accuracy, structural lifting0.942±0.0050.942 \pm0.0050.947±0.0030.947 \pm0.0030.976±0.0020.976 \pm0.0020.967±0.0060.967 \pm0.006
model accuracy, standard lifting0.928±0.0030.928 \pm0.0030.936±0.0030.936 \pm0.0030.969±0.0090.969 \pm0.0090.971±0.0050.971 \pm0.005
share with Δ>0\Delta> 0, structural lifting0.740.740.930.930.970.970.990.99
share with Δ>0\Delta> 0, standard lifting0.970.970.940.941.001.000.990.99

Table 2. Explanation accuracy on lifted complexes. Node-projected GEA for both TopoSHAP outputs of the GCCN with all eleven neighborhoods under the two liftings; the lower block gives each model’s test accuracy and its share of candidates with Δ>0\Delta> 0. Bold is best and gray is within ≤1σ\le1\sigma.

Constant higher-rank features improve motif recovery on three of four datasets. Building on our finding of summary information caching structural information, we devise a new lifting where every higher-rank feature is instead the same constant all-ones vector. Under this “structure-only” lifting, greedy explanations achieve higher mean GEA on three datasets and attribution results are mixed (Table 2). Mean predictive accuracy also increases on three datasets. We consider models trained on Benzene as a specific example. Moving from standard to structure-only lifting increases face retention from 0.84±0.140.84 \pm0.14 to 0.95±0.050.95 \pm0.05 and boundary-edge recovery from 0.40±0.140.40 \pm0.14 to 0.86±0.060.86 \pm0.06 (Section C.2). Thus, explanations more often retain both the face and its boundary. More broadly, these findings support the importance of feature lifting for explanation recovery.

TopoSHAP-cell Is the Most Faithful Explainer Without Annotations

TopoSHAP-cell beats occlusion, gradient-times-input, and random on every unannotated dataset. Here we apply TopoSHAP-cell to benchmark topological datasets hosted in TopoBench ([39]). Because there is no ground truth annotation, we score explanations against the model’s own prediction by deletion-AUC (Table 7; protocol in Section C.3). We hypothesize that TopoSHAP outperforms other baselines by attributing cells across coalitions rather than in isolation.

NCI1NCI109MUTAGPROTEINS
TopoSHAP0.218 ± 0.0050.203 ± 0.0440.175 ± 0.0430.338 ± 0.067
Occlusion0.254 ± 0.0210.240 ± 0.0380.231 ± 0.0060.431 ± 0.065
Gradient×Input0.552 ± 0.0160.507 ± 0.0490.499 ± 0.0730.638 ± 0.047
Random0.545 ± 0.0040.491 ± 0.0350.481 ± 0.0140.666 ± 0.058

Table 7. Faithfulness without ground truth. Deletion-AUC (lower is better; a fixed draw of 50 test complexes per dataset, except MUTAG, which uses its whole 47-complex test split). Subjects are GCCNs with all eleven neighborhoods under the structure-only lifting; explanations target the model’s own prediction.

Rank-specific attributions help explain models’ prediction strategies. Here, we consider MANTRA ([3]), the natively topological dataset, and its orientability classification task. HOPSE performs best overall (AUROC 0.93), followed by GCCN (0.79) and the published TopoBench baseline (0.52). However, when we restrict evaluation to surfaces with matched cell counts, GCCN falls to near chance (0.51), while HOPSE retains 0.79. Thus, HOPSE can distinguish orientability using information beyond the numbers of nodes, edges, and triangles (protocol in Section C.4). Cell attributions help interpret this difference. Consider an orientable torus and a non-orientable Klein bottle with identical cell counts (Figure 3). Attributions show GCCN leverages triangles, but fails to distinguish triangles of orientable and the non-orientable surfaces. HOPSE instead concentrates its credit on nodes and edges, but successfully assigns attributions of opposite sign. We hypothesize that HOPSE succeeds because its spectral encodings provide global information about the complex’s topology. Giving GCCN access to these encodings supports the hypothesis: with Hodge Laplacian eigenvectors concatenated to its input features, GCCN reaches a balanced accuracy of 0.88, exceeding HOPSE’s 0.79 (Table 8). This is an example of how TopoSHAP-cell can shed light on models’ inner workings and help design better TNNs for specific tasks.

Figure 3. MANTRA attributions on a count-matched pair. One orientable torus and one non-orientable Klein-bottle-family surface with identical cell counts (9 nodes, 27 edges, 18 triangles), drawn from the smallest count group containing both classes: per-cell contribution to the orientable-class logit margin for the three models of § 5.3 (published-architecture baseline; the GCCN selected by TopoSHAP-neighbor at B=2B=2; the sweep-best HOPSE). Panel headers give each model’s overall and count-conditional test AUROC. HOPSE is drawn on its own yy-scale, stated on the axis. Per-cell values are single sampled-game estimates at T=512T=512 orderings (Section A.1); no aggregation, hence no error bars.

Model / input featuresBalanced test acc.Runs
Logistic regression on cell counts0.5051 fit
Structural features only0.5413 seeds (means only)
GCCN, selected (B=2B=2, plain-accuracy selection)0.641 ± 0.1235 seeds
GCCN + Hodge Laplacian eigenvectors0.8763 seeds (means only)
HOPSE, selected (B=2B=2)0.771 ± 0.0173 seeds
HOPSE, sweep best0.792 ± 0.0093 seeds

Table 8. MANTRA orientability: feature and model comparison. Balanced test accuracy. The count-only row is a single logistic regression fit; the structural-features and eigenvector rows are means over three training seeds whose per-seed values were not exported, so no sd is shown. The feature study trains its own GCCN configuration, distinct from the selected models, so rows compare feature sets across configurations. Selection rows report mean ± sd over seeds.

Results II: Explaining Performance with TopoSHAP-neighbor

Architecture Selection in Practice

TopoSHAP-neighbor reduces total training compute by a factor of 4.5–11.3 relative to the evaluated architecture sweeps. The resulting accuracy–compute trade-off varies by dataset, as shown in Figure 2 and Table 9. We evaluate GCCN and HOPSE across 11 datasets against their respective reported architecture search grids [31, 4]. Our pipeline uses a five-epoch full model to select B=2B = 2 smaller architectures, completes the training of these smaller architectures, and selects one by validation accuracy. Reported costs include search, candidate training, and preprocessing (Section D.1). Controls using the same initialization and continuation settings compare elimination with a random two-candidate shortlist and the full-model default (Table 10). We find that elimination generally improves mean accuracy.

Figure 2. Architecture selection: accuracy versus total compute. Dark markers denote TopoSHAP-neighbor; pale markers denote each family’s validation-selected sweep winner, charged for the full sweep. Error bars show standard deviation over five seeds for GCCN B=2B = 2 and three otherwise. Due to its practical costs, HOPSE sweeps are limited to complex-level datasets and we avoid training any HOPSE models on Pubmed. MANTRA uses balanced test accuracy.

Table 9. Architecture selection: full results by model family. Test accuracy (mean ±\pm sd; GCCN B=2B=2 uses five seeds 42–46, all other columns the shared seeds 42–44; {sup}bbalanced test accuracy on MANTRA) and, in parentheses, total training FLOPs as a multiple of that dataset’s $B=1$ run ({xref}Section D.1); sweeps are charged their full grid. Gap = selection $B=2$ minus that family’s sweep; sweeps use per-seed validation-best configurations. —: not run. Pubmed carries no HOPSE runs ({xref}Section B.1`).

GCCN family
DatasetB=1B=1B=2B=2sweepgap
Benzene0.925 ±\pm 0.007 (×\times1.0)0.926 ±\pm 0.004 (×\times2.0)0.926 ±\pm 0.002 (×\times22.7)+0.000
Fluoride-Carb.0.901 ±\pm 0.057 (×\times1.0)0.939 ±\pm 0.006 (×\times1.9)0.938 ±\pm 0.004 (×\times20.6)+0.001
Mutagenicity0.967 ±\pm 0.011 (×\times1.0)0.975 ±\pm 0.010 (×\times2.0)0.964 ±\pm 0.014 (×\times15.4)+0.012
Alkane-Carb.0.965 ±\pm 0.006 (×\times1.0)0.962 ±\pm 0.005 (×\times2.4)0.975 ±\pm 0.003 (×\times16.2)-0.012
NCI10.764 ±\pm 0.011 (×\times1.0)0.758 ±\pm 0.010 (×\times2.8)0.759 ±\pm 0.022 (×\times15.0)-0.000
MUTAG0.879 ±\pm 0.025 (×\times1.0)0.906 ±\pm 0.024 (×\times2.1)0.901 ±\pm 0.025 (×\times13.1)+0.006
NCI1090.758 ±\pm 0.011 (×\times1.0)0.756 ±\pm 0.009 (×\times1.8)0.747 ±\pm 0.015 (×\times11.3)+0.009
Cora0.838 ±\pm 0.008 (×\times1.0)0.835 ±\pm 0.005 (×\times2.3)0.856 ±\pm 0.006 (×\times14.9)-0.021
Citeseer0.673 ±\pm 0.014 (×\times1.0)0.670 ±\pm 0.007 (×\times1.8)0.683 ±\pm 0.002 (×\times15.1)-0.013
Pubmed0.860 ±\pm 0.004 (×\times1.0)0.863 ±\pm 0.004 (×\times2.3)0.865 ±\pm 0.001 (×\times14.4)-0.002
MANTRA{sup}b`0.532 ±\pm 0.028 (×\times1.0)0.641 ±\pm 0.123 (×\times1.8)0.548 ±\pm 0.000 (×\times11.0)+0.093
HOPSE family
DatasetB=2B=2sweepgap
Benzene0.934 ±\pm 0.001 (×\times5.4)0.936 ±\pm 0.003 (×\times36.4)-0.002
Fluoride-Carb.0.918 ±\pm 0.004 (×\times8.5)0.934 ±\pm 0.009 (×\times41.6)-0.015
Mutagenicity0.961 ±\pm 0.008 (×\times5.9)0.976 ±\pm 0.009 (×\times36.3)-0.015
Alkane-Carb.0.969 ±\pm 0.009 (×\times10.5)0.963 ±\pm 0.007 (×\times47.8)+0.006
NCI10.759 ±\pm 0.024 (×\times5.6)0.745 ±\pm 0.011 (×\times34.5)+0.013
MUTAG0.844 ±\pm 0.012 (×\times10.9)0.844 ±\pm 0.054 (×\times53.3)+0.000
NCI1090.720 ±\pm 0.005 (×\times5.2)0.737 ±\pm 0.011 (×\times27.1)-0.017
Cora0.851 ±\pm 0.005 (×\times10.2)——
Citeseer0.712 ±\pm 0.007 (×\times6.8)——
MANTRA{sup}b`0.771 ±\pm 0.017 (×\times9.6)0.792 ±\pm 0.009 (×\times68.7)-0.021

caption:

Table 10. Shortlist baselines with shared initialization and training settings. Test accuracy (mean ±\pm sd, shared seeds 42–44; {sup}b`balanced on MANTRA). All three columns share the five-epoch initial model and standard continuation; random B=2B=2 replaces backward elimination with two uniformly random architectures, and the full-model default trains all 11 neighborhoods with no search.

DatasetTopoSHAP-neighbor B=2B=2Random B=2B=2Full default
Benzene0.927 ±\pm 0.0000.925 ±\pm 0.0130.927 ±\pm 0.003
Fluoride-Carbonyl0.939 ±\pm 0.0070.929 ±\pm 0.0020.938 ±\pm 0.003
Mutagenicity0.976 ±\pm 0.0120.932 ±\pm 0.0610.972 ±\pm 0.015
Alkane-Carbonyl0.965 ±\pm 0.0060.973 ±\pm 0.0030.955 ±\pm 0.007
NCI10.757 ±\pm 0.0130.755 ±\pm 0.0260.766 ±\pm 0.005
MUTAG0.915 ±\pm 0.0210.879 ±\pm 0.0250.879 ±\pm 0.012
NCI1090.755 ±\pm 0.0110.755 ±\pm 0.0110.749 ±\pm 0.001
Cora0.839 ±\pm 0.0020.831 ±\pm 0.0210.836 ±\pm 0.003
Citeseer0.669 ±\pm 0.0010.660 ±\pm 0.0130.666 ±\pm 0.010
Pubmed0.862 ±\pm 0.0040.853 ±\pm 0.0060.861 ±\pm 0.002
MANTRA{sup}b`0.615 ±\pm 0.1030.687 ±\pm 0.1140.777 ±\pm 0.035

caption:

Controlled Evaluation with Exhaustive Training

We separately train all 26=642^{6} = 64 subsets of six neighborhoods across twelve GCCN dataset/hyperparameter settings and three seeds (Section D.3). This exhaustive retraining allows us to compute the neighborhoods’ Shapley values from separately trained coalitions and compare them with attributions from the masked five-epoch model; the selection pipeline of § 6.1 itself never consumes attributions, scoring candidate removals directly by masked coalition accuracy.

Masked attributions describe reliance in the trained model. Masked-model and retrained-model Shapley values show weak pooled agreement (ρ=0.23\rho= 0.23), rising to 0.32 when masking is scored by accuracy rather than logits (Table 12). Masking uses validation data, whereas retraining is scored by test accuracy or negative MAE, so this comparison also reflects differences in data and scoring (Section D.3). The results caution against interpreting fixed-model attributions as necessity after retraining.

DatasetAgreement ρ\rho (logit)(accuracy)Per-seed ρ\rho (stability)
MUTAG-0.37+0.89-0.16 ±\pm 0.74
NCI1-0.31+0.14-0.12 ±\pm 0.95
NCI109+0.09+0.09+0.20 ±\pm 0.70
ZINC-subset (fixed recipe)-0.09-0.09+0.14 ±\pm 0.29
ZINC-subset (strong)-0.31-0.31-0.45 ±\pm 0.14
Alkane-Carbonyl+0.49+0.49+0.50 ±\pm 0.36
Benzene+0.83+0.31+0.43 ±\pm 0.37
Citeseer+0.66+0.66+0.56 ±\pm 0.12
Cora+0.94+0.94+0.94 ±\pm 0.00
PubMed+0.54+0.37+0.39 ±\pm 0.22
Fluoride-Carbonyl-0.09+0.77+0.26 ±\pm 0.45
Mutagenicity+0.94+0.77+0.71 ±\pm 0.20
Pooled (72 points)+0.23 [-0.05, +0.52]+0.32 [+0.06, +0.60]

Table 12. Attribution agreement with retraining. Spearman correlation between masked-game and retraining-game Shapley profiles over the six neighborhoods (masked: logit-scored, validation split; retraining: test metric). Agreement: correlation between seed-averaged attribution profiles. Stability: per-seed correlation, mean ±\pm sd (seeds 42–44). Pooled row: 95% CI in brackets.

Backward elimination generates competitive candidates in an oracle analysis. We score removals using the separately trained coalitions’ seed-averaged test performance. On five held-out settings across four datasets, the cheap greedy architecture selection (outlined in § 4.2) contains the exhaustive benchmark’s best architecture in four settings (Table 13). This is encouraging evidence that our pipeline can construct competitive candidate sequences (Section D.4).

SettingStatusEmptyFullBest (kk)Path best (kk)Regret
Benzenedevelopment0.7390.9210.925 (3)0.925 (3)+0.0000
Mutagenicitydevelopment0.8210.9560.957 (5)0.957 (5)+0.0000
Alkane-Carbonylheld-out0.9670.9670.984 (4)0.984 (4)+0.0000
Fluoride-Carbonyldevelopment0.8220.9350.943 (4)0.943 (4)+0.0000
MUTAGheld-out0.7230.9010.922 (5)0.922 (5)+0.0000
NCI1development0.6670.7590.768 (3)0.768 (5)+0.0000
NCI109held-out0.6800.7560.762 (3)0.762 (3)+0.0000
ZINC-subset (fixed recipe)mheld-out-0.699-0.548-0.534 (5)-0.534 (5)+0.0000
ZINC-subset (strong)mheld-out-0.723-0.225-0.177 (4)-0.184 (5)+0.0068
Coradevelopment0.6320.8480.861 (3)0.861 (3)+0.0000
Citeseerdevelopment0.6440.6810.688 (3)0.685 (3)+0.0024
PubMeddevelopment0.8540.8610.867 (3)0.863 (5)+0.0042

Table 13. Oracle evaluation of candidate generation on the exhaustive benchmark. Backward elimination is rerun with each removal scored by the separately trained coalitions’ seed-averaged test values (three seeds); ties break toward the first neighborhood in the order of Section A.2. Because it consults test scores, this is a diagnostic of the candidate generator, not a deployable selection. Empty = trained model with node features only; Full = all six neighborhoods; Best = best of all 64 subsets, with its size; Path best = best subset on the greedy elimination path; Regret = Best − Path best. ZINC values are negative test MAE (higher is better).

Limitations and Conclusion

TopoSHAP brings prediction and architecture explanations into a unified explainability framework for Topological Deep Learning, providing insight into model predictions and performance. We conclude by describing two limitations which are also promising avenues for future work. First, scaling to larger complexes requires more efficient coalition evaluation. Although greedy pruning is substantially cheaper than SubgraphX on our benchmarks (Table 1), it requires O(n2)O(n^2) model evaluations for nn cells, while attribution requires O(Tn)O(T^n) evaluations for TT sampling passes. Truncated or sampled search offers a path toward complexes with thousands of cells. Second, our evaluation against ground truth explanations remains graph-based in this work. Developing explanation-annotated benchmarks on general combinatorial complexes, building on graph benchmarks and emerging synthetic hypergraph benchmarks [38], will be paramount for developing better explanations for, and thus more trustworthy, Topological Deep Learning.

Acknowledgments

M. P. and N. M. acknowledge partial support from NSF grant 2602079 and the Noyce foundation. M. P. and N. M. also thank Goodfire AI for providing access to Silico through its academic research grant program. M. P. also acknowledges support from NSF Career grant 2240158 and the National Science and Engineering Research Council of Canada.

AI Use Statement

In this work, we used generative AI tools to assist with implementing and debugging the proposed methods, running experiments, and drafting initial versions of portions of the manuscript. We also used generative AI tools to assist with summarizing existing literature; all cited literature and associated claims were independently reviewed by the authors. AI tools were not used to conceptualize the project, develop its core research ideas or methodology or interpret the experimental results. All datasets used in this work were publicly available prior to this study and were not generated using AI. AI-assisted code was reviewed, modified, and tested by the authors, and all experimental results and analyses were independently verified by the authors. The authors wrote a substantial portion of the main text and heavily revised and edited all AI-assisted text. Appendix text is a more equal combination of author and AI written text. We take full responsibility for the final content of the paper, including all claims, analyses, code, and artifacts.

Reproducibility Statement

Datasets, splits, and all model, training, and explainer settings are specified in Section B; evaluation protocols and full results in Sections C and D; the software environment in Section E. The implementation is made available at github.com/mathildepapillon/toposhap.

Additional Method Details

Cell Masking and Explanation Algorithms

Masked input. Given a complex C\mathcal{C} with cells PP and a coalition S⊆PS \subseteq P, the masked input C[S]\mathcal{C}[S] is built by detaching every cell outside SS: its feature row is zeroed, its entries are removed from every neighborhood matrix in which it appears (as source, target, or intermediate cell, with composed neighborhoods rebuilt from the incidences of the remaining cells, using the same constructors that built the original input), and it is excluded from readout pooling. Retained cells keep the input features they were supplied with; because cells are independent players, a face can remain after one of its nodes is detached, so C[S]\mathcal{C}[S] is a masked complex and not in general a node-induced subcomplex. For HOPSE, whose inputs include precomputed positional and structural encodings, the encodings are recomputed on each C[S]\mathcal{C}[S]. On plain graphs we take the nodes as players and let incident edges follow their endpoints, in which case C[S]\mathcal{C}[S] is the node-induced subgraph.

Target score. ff reads one fixed class logit, held fixed across all coalitions of an instance: the annotated class on labeled benchmarks, the predicted class on datasets without annotations (no labels consulted), and the orientable-class logit margin on MANTRA. Coalition values are v(S)=f(C[S])−f(C[∅])v(S)=f(\mathcal{C}[S])-f(\mathcal{C}[\varnothing]), where C[∅]\mathcal{C}[\varnothing] detaches every cell, leaving the encoder and readout biases.

Attribution (Output 1). Exact Shapley values enumerate all 2n2^n coalitions when nn is small. Otherwise we sample player orderings, add players in the sampled order, and average the marginal changes [6]. The budget TT counts every evaluated ordering: orderings are drawn uniformly at random and each drawn ordering is followed by its reverse, so TT orderings comprise T/2T/2 random draws and their reversals. A reversed ordering visits its own coalitions; all coalition values are cached by bitmask, so the total cost is at most Tn+1Tn+1 model evaluations and fewer in practice. Explanation experiments use T=128T=128 with estimator seed 0, distinct from the training seeds; the per-cell estimates of Figure 3 use T=512T=512.

Explanation (Output 2). Greedy backward pruning (Algorithm 1) starts from PP and repeatedly removes the cell whose removal lowers vv the least, producing one nested candidate S^b\hat{S}_b per size bb in at most (n2+n)/2(n^2+n)/2 evaluations. The candidates are compact, high-scoring coalitions on the greedy path and carry no optimality guarantee.

Algorithm 1 TopoSHAP-cell on one instance

Require: complex C\mathcal{C} with cells PP, n=∣P∣n=|P|; model logit ff; sampling budget TT

  1. define v(S)=f(C[S])−f(C[∅])v(S)=f(\mathcal{C}[S])-f(\mathcal{C}[\varnothing]), cached by coalition

  2. Output 1: ϕ←\phi\leftarrow exact Shapley values if 2n2^n is affordable, else the TT-ordering estimate (each drawn ordering followed by its reverse)

  3. Output 2: S←PS\leftarrow P; S^n←P\hat{S}_n\leftarrow P

  4. for b=n−1,…,1b=n-1,\ldots,1 do

  5. i∗←arg⁡max⁡i∈Sv(S∖{i})i^*\leftarrow\arg\max_{i\in S}v(S\setminus\{i\}), ties toward the lower cell index

  6. S←S∖{i∗}S\leftarrow S\setminus\{i^*\}; S^b←S\hat{S}_b\leftarrow S

  7. end for

  8. return ϕ\phi and {S^b}b=1n\{\hat{S}_b\}_{b=1}^{n}

Implementation checks. At S=PS=P the rebuilt input must reproduce the model’s stored forward pass exactly; this check runs at construction, and the HOPSE variant additionally checks that recomputed full-coalition encodings reproduce the stored prediction within tolerance. The Shapley computation is verified against brute-force enumeration to 2.254×10−142.254\times10^{-14} on small games. These checks verify the implementation of the specified game; separate consistency checks (attribution invariance under batch permutation, equality on provably symmetric cells) test the masking itself.

Neighborhood Masking and Architecture Selection

The eleven neighborhoods. Every subset mask indexes neighborhoods in the order listed below, with the code label followed by the notation of Definition 2 (Is→tI_{s\to t}: messages from rank-ss cells to their incident rank-tt cells): up_adjacency-0 =A0,1=A_{0,1}, up_incidence-0 =I0→1=I_{0\to1}, down_incidence-1 =I1→0=I_{1\to0},

Algorithm 2 TopoSHAP-neighbor: architecture selection

Require: Full model with neighborhoods N\mathcal{N}; training and validation sets Dtrain,DvalD_{\mathrm{train}},D_{\mathrm{val}}; candidate budget 1≤B≤∣N∣1 \le B \le|\mathcal{N}|

Ensure: Selected trained model

  1. Train the full model for five epochs, obtaining weights θ0\theta_0

  2. Define a(S)a(S) as its validation accuracy with neighborhoods outside SS masked and weights fixed at θ0\theta_0

  3. Cache all evaluations of a(S)a(S)

  4. m←∣Dval∣m \leftarrow|D_{\mathrm{val}}|, p←a(N)p \leftarrow a(\mathcal{N}), τ←p(1−p)/m\tau\leftarrow\sqrt{p(1-p)/m}

  5. S←NS \leftarrow\mathcal{N}, K←{N}\mathcal{K} \leftarrow\{\mathcal{N}\}, Sstop←∅S_{\mathrm{stop}} \leftarrow\varnothing

  6. for k=∣N∣,…,2k = |\mathcal{N}|,\ldots,2 do

  7. i∗←arg⁡max⁡i∈Sa(S∖{i})i^* \leftarrow\arg\max_{i\in S} a(S\setminus\{i\})

  8. S′←S∖{i∗}S' \leftarrow S\setminus\{i^*\}

  9. if Sstop=∅S_{\mathrm{stop}} = \varnothing and a(S)−a(S′)>τa(S)-a(S')>\tau then

  10. Sstop←SS_{\mathrm{stop}} \leftarrow S ▷ Mark the candidate before this removal

  11. end if

  12. K←K∪{S′}\mathcal{K} \leftarrow\mathcal{K}\cup\{S'\}; S←S′S\leftarrow S' ▷ Continue even after marking a candidate

  13. end for

  14. if Sstop=∅S_{\mathrm{stop}}=\varnothing then

  15. Sstop←SS_{\mathrm{stop}}\leftarrow S ▷ Use the singleton if no loss exceeded τ\tau

  16. end if

  17. T←{Sstop}∪{B−1 candidates in K∖{Sstop} with highest a(S)}\mathcal{T}\leftarrow\{S_{\mathrm{stop}}\}\cup\{B-1\text{ candidates in }\mathcal{K}\setminus\{S_{\mathrm{stop}}\}\text{ with highest }a(S)\}

  18. for each T′∈TT'\in\mathcal{T} do

  19. Initialize fT′f_{T'} from a separate copy of θ0\theta_0, removing components outside T′T'

  20. Continue training fT′f_{T'} to completion under standard settings

  21. q(T′)←Accuracy⁡(fT′,Dval)q(T')\leftarrow\operatorname{Accuracy}(f_{T'},D_{\mathrm{val}})

  22. end for

  23. return fT∗,T∗=arg⁡max⁡T′∈Tq(T′)f_{T^*},T^*=\arg\max_{T'\in\mathcal{T}}q(T') (ties toward SstopS_{\mathrm{stop}})

up_adjacency-1 = A1,2A_{1,2}, down_incidence-2 = I2→1I_{2\to1}, 2-up_adjacency-0 = A0,2A_{0,2}, down_adjacency-1 = A1,0A_{1,0}, up_incidence-1 = I1→2I_{1\to2}, down_adjacency-2 = A2,1A_{2,1}, 2-up_incidence-0 = I0→2I_{0\to2}, 2-down_incidence-2 = I2→0I_{2\to0}. The exhaustive benchmark of Section D.3 uses the first six.

Masking a neighborhood. In a GCCN, each neighborhood owns one message-passing module per layer; in HOPSE, one encoding block (the fixed encoder on that neighborhood’s graph plus its learned MLP). Masking a neighborhood silences its modules; removing it deletes them, and for HOPSE also removes that block’s preprocessing, which is charged accordingly (Section D.1).

Selection. Algorithm 2 restates the procedure of § 4.2. The five-epoch initial model defines a(S)a(S), the masked validation accuracy; backward elimination removes, at each step, the neighborhood whose removal keeps aa highest (ties toward the first neighborhood in the order listed above), continuing down to one neighborhood and yielding one candidate per size. The stop candidate is the architecture immediately before the first removal whose measured loss exceeds τ=p(1−p)/m\tau=\sqrt{p(1-p)/m}; τ\tau is a heuristic based on the estimated standard error of a single accuracy, and it does not bound the cumulative loss relative to the full model. The remaining B−1B-1 shortlist places go to the candidates with the highest masked accuracies at sizes not yet taken. Each shortlisted candidate starts from a separate copy of the initial model with excluded components removed and continues training under the dataset’s standard settings, with epochs and early stopping counted from the continuation start; the five initial epochs are charged additionally in every reported cost. The full architecture is a candidate whenever the elimination path marks it; the empty architecture is never a candidate and serves as the baseline a(∅)a(\varnothing). The final choice is the trained candidate with the highest validation accuracy, ties toward the stop candidate. Only this final comparison uses fully trained models; all intermediate removals use the masked game.

Datasets and Training Settings

Datasets, Splits, and Liftings

Our experiments use three groups of datasets (Table 3). Benzene, Fluoride-Carbonyl, Alkane-Carbonyl, and Mutagenicity are binary graph-classification tasks from the GraphXAI suite [1], built on the attribution benchmarks of Sanchez-Lengeling et al. [34]; each molecule’s label is determined by a known functional group, so every graph carries a ground-truth explanation. MUTAG, NCI1, NCI109, and PROTEINS are graph-classification benchmarks from the TUDataset collection [27]; Cora, Citeseer, and Pubmed [42] are citation networks with node-level classification (one complex each; transductive, random 50/25/25 node split, split seed 0). MANTRA [3] is a collection of triangulated 2-manifolds, natively simplicial; we use the orientability task. The ZINC subset [10] (regression, scored by mean absolute error) appears only in the exhaustive six-neighborhood benchmark of Section D.3, under two training configurations described in Section B.2; both use ZINC’s predefined subset splits of 10,000/1,000/1,000 graphs (train/validation/test, about 23 nodes and 50 edges per graph). It is not part of the selection or explanation experiments.

DatasetTrainValTestCellsr0r1r2Classes
GraphXAI benchmarks (lifted to cellular complexes)
Benzene840018001800212222
Fluoride-Carbonyl606913001302212322
Alkane-Carbonyl787168170212322
Mutagenicity1237265266293022
Graph benchmarks (lifted to cellular complexes)
MUTAG944747182032
NCI1205510271028303242
NCI109206310311033303242
PROTEINS5562782793973332
Cora13546776772,7085,2781,6487
Citeseer16638318333,3274,5521,2596
Pubmed98584929493019,71744,3249,3253
Natively higher-order (simplicial)
MANTRA (orientability)2156810785107851034232

Table 3. Dataset statistics after preprocessing. Cells per rank are means over complexes (rank 0 nodes, rank 1 edges, rank 2 2-cells; MANTRA is natively simplicial). Node-level datasets are one complex whose splits partition the nodes (transductive, random 50/25/25 split, split seed 0); their split columns count nodes.

Liftings. Graph datasets are lifted to cellular complexes with TopoBench’s cycle lifting [39]: chordless cycles of up to ten nodes become rank-2 cells. Two feature liftings appear. The standard lifting (ProjectionSum) gives each higher-rank cell the sum of its constituent nodes’ features. The structure-only lifting gives every cell above rank 0 a constant all-ones feature vector, identical across cells, at the width of the rank below (MANTRA’s native convention); rank-1 and rank-2 cells are treated the same way, node features are kept, and the complex itself is unchanged. MANTRA needs no lifting.

Participation. The prediction-explanation experiments of § 5 use the four GraphXAI datasets (GNN models on graphs; GCCN models on their lifted complexes), the four unannotated TU datasets for faithfulness, and MANTRA for the model diagnostics. The architecture-selection experiments of § 6 use eleven datasets (all of Table 3 except PROTEINS, which appears in the faithfulness study only). On Pubmed, HOPSE preprocessing does not complete at practical cost (its eigensolvers exceed eight GPU-hours on the lifted complex), so Pubmed carries no HOPSE runs; the HOPSE sweep covers the complex-level datasets.

Models, Training, and Explainer Settings

TNN models (architecture selection). All GCCN selection experiments use the topotune_nonlinear_exact configuration: a TopoTune GCCN backbone with two layers, hidden width 32, one two-layer GCN sub-network per neighborhood (BatchNorm, ReLU), and a linear sum-pool readout. HOPSE models replace each neighborhood’s message-passing module with fixed encodings of that neighborhood’s graph plus a learned MLP block (Definition 4): four encodings per neighborhood (Laplacian-eigenvector positional, random-walk structural, electrostatic positional, and heat-kernel-diagonal structural), each targeting 20 dimensions per cell and concatenated with the cell’s input feature; the encoder width is 64, with two backbone layers and a sum-pool readout. Both families train with Adam (learning rate 10−310^{-3}, no weight decay), the learning rate halved every 50 epochs, up to 300 epochs with early stopping (patience 25) on the dataset’s monitored validation metric, and batch size 64 for graph datasets, 256 for MANTRA, and full-batch for the citation complexes. Checkpoint selection is validation-best. Continuations in the selection pipeline restart these settings from the five-epoch initial model.

ZINC benchmark configurations. The exhaustive benchmark’s two ZINC settings share ZINC’s predefined subset splits and are scored by negative test MAE. The fixed-recipe setting uses the shared GCCN configuration above (26,112 backbone parameters at the full six-neighborhood model); the strong setting replaces the GCN sub-networks with GIN sub-networks (104,448 backbone parameters).

GNN models (graph explanation). Parameter-matched GCN ([21]) and GIN ([41]) models: three layers, input width 14, hidden width 32, two classes; Adam with learning rate 10−310^{-3} and weight decay 5×10−45 \times10^{-4}; class-weighted cross-entropy; batch size 64; up to 300 epochs with early stopping on validation balanced accuracy (patience 30); checkpoint = best validation balanced accuracy; stratified shuffle splits with seed 42; three training seeds per model.

Baseline explainers (settings from the saved suite): SubgraphX with 10 Monte-Carlo tree-search rollouts, minimum subgraph size 3, cpuct=10c_{\mathrm{puct}} = 10, 14 expansion atoms, local radius 4, and 100 reward samples per evaluation; GNNExplainer with learning rate 0.05 for 1000 epochs (selected on training data; the GraphXAI defaults of 0.01/200 were also run); PGExplainer trained once per dataset-model pair on up to 1000 training graphs (30 epochs, learning rate 0.003 selected on training data; defaults 10 epochs/0.1 also run). Every method receives the annotated motif’s size and is evaluated on the same instances. Occlusion scores each cell by the leave-one-out drop v(P)−v(P∖{i})v(P) - v(P \setminus\{i\}) under the same masked game; gradient-times-input scores each cell by the gradient of the target margin with respect to its raw input features, dotted with those features and summed over the feature dimension (signed); the random baseline draws one seeded uniform score per cell. All methods are ranked by signed score, descending.

Seeds, hardware, software. Comparisons share seeds 42–44; the GCCN B=2B=2 selection additionally carries seeds 45–46 (Table 9). All local runs use one NVIDIA H200 GPU per job; PyTorch 2.3.0 (CUDA 12.1) and a pinned TopoBench commit, listed in Section E.

Additional Results for TopoSHAP-cell

Graph Explanation Accuracy and Runtime

From scores to node sets. On graphs, every method is scored as a node set of the annotated motif’s size bb: the attribution output takes the bb highest-scoring nodes, the explanation output takes the greedy candidate S^b\hat{S}_b, and baselines are converted with the same top-bb rule (GNNExplainer and PGExplainer score a node by the sum of its incident edges’ mask weights; SubgraphX scores a node by its best explored-coalition reward, plus one for membership in the returned subgraph; ties break toward the lower node index). On lifted complexes, sizes are matched at the cell level instead: the size-bb cell set is projected to the union of its constituent nodes without re-truncation, so the projected node set can exceed bb nodes and the Jaccard score penalizes the excess. GEA is the best Jaccard over the instance’s admissible annotated candidates. The evaluated population is every ground-truth-positive complex in the test split, shared by every method: 917 (Benzene), 231 (Fluoride-Carbonyl), 96 (Mutagenicity), and 58 (Alkane-Carbonyl) instances.

Runtime protocol. Table 5 reports measured wall-clock seconds per explained instance, averaged over both model types and three seeds, on one NVIDIA H200 GPU per run, with each method timed end to end on the same instances; PGExplainer’s one-time per-dataset training is reported as its own row.

Feature Lifting and Motif Recovery

Table 6 reports the lifting diagnostics behind § 5.2, on the explanation output S^b\hat{S}_b of the GCCN with all eleven neighborhoods. Face retention is the fraction of instances whose selected coalition contains at least one rank-2 cell; boundary recall is the mean recall of the annotated motif’s rank-1 cells. The two statistics are computed separately, and both use the full ground-truth-positive test populations and three training seeds. The final column re-scores the standard lifting with its summed higher-rank features recomputed on every masked complex, so a retained face carries only the features of its retained nodes; everything else (weights, players, target) is unchanged. The difference in motif recovery between the two liftings persists when the summed features are recomputed after masking.

DatasetFace retentionBoundary recallGEA, recomputed feat.
standardstructure-onlystandardstructure-only(standard lifting)
Benzene0.84 ± 0.140.95 ± 0.050.40 ± 0.140.86 ± 0.060.56 ± 0.09
Fluoride-Carbonyl0.00 ± 0.000.00 ± 0.000.16 ± 0.060.53 ± 0.040.28 ± 0.02
Mutagenicity0.05 ± 0.040.13 ± 0.150.08 ± 0.040.30 ± 0.040.18 ± 0.02
Alkane-Carbonyl0.02 ± 0.030.03 ± 0.050.07 ± 0.130.50 ± 0.240.25 ± 0.17

Table 6. Lifting diagnostics for the explanation output. Face retention: fraction of instances whose selected coalition contains at least one rank-2 cell. Boundary recall: mean recall of the annotated motif’s rank-1 cells. Both are computed on the full ground-truth-positive test populations (mean ± sd over three training seeds). The last column rescores the standard lifting with its summed features recomputed on every masked complex instead of held fixed (node-projected GEA); its structural-lifting counterpart is in Table 2.

Faithfulness Without Annotations

Deletion-AUC detaches cells cumulatively, most important first. With mkm_k the target margin after detaching the kk highest-ranked of nn cells and s=sign⁡(m0)s = \operatorname{sign}(m_0) orienting the margin toward the predicted class,

AUC⁡=∑k=1nσ(smk−1)+σ(smk)2⋅1n,\operatorname{AUC} = \sum_{k=1}^{n} \frac{\sigma(s m_{k-1}) + \sigma(s m_k)}{2} \cdot\frac{1}{n},

the trapezoid rule applied to the predicted-class probability (σ\sigma: logistic function) over the removed fraction, from the full complex to full removal. Lower is better. The explained models are GCCNs with all eleven neighborhoods under the structure-only lifting; explanations target the model’s own prediction. The evaluated population is a fixed seed-0 draw of 50 test complexes per dataset, except MUTAG, which uses its entire 47-complex test split.

MANTRA: Attribution Patterns and Feature Ablations

Metrics. The overall AUROC in § 5.3 is computed on MANTRA’s full test split from each model’s orientable-class score. The count-conditional AUROC restricts comparisons to pairs of test complexes with identical (V,E,F)(V, E, F) cell counts: over all count groups containing both classes (four groups), it is the pooled probability that an orientable complex outscores a non-orientable one within the same group; between-group pairs are excluded, so a model that predicts every class cannot exceed 0.5. These AUROCs are model diagnostics and are distinct from the balanced test accuracy used for selection results.

Feature ablations. Table 8 collects the comparison behind § 5.3: models restricted to cell counts or purely structural features, the GCCN and HOPSE selections of § 6.1, and a GCCN trained with Hodge Laplacian eigenvectors concatenated to its input features. The rows differ in model-selection procedure and seed count (stated per row in the table), so the table compares feature sets across configurations rather than isolating one controlled feature change.

Additional Results for TopoSHAP-neighbor

Architecture Selection, Baselines, and Compute

Sweeps. The GCCN sweep is a TopoTune-style neighborhood grid of 22–25 configurations per dataset: the saved record’s per-dataset draws on the eight datasets it covered, and one fixed 23configuration draw reused verbatim on the three datasets swept for this paper (per-dataset counts in Figure 2’s legend; the configuration lists ship with the released pipeline). The HOPSE sweep is its published 12-configuration grid. Sweep winners are selected per seed by validation accuracy and charged the full grid.

Shortlist controls. Each control starts from the same five-epoch initial model and continues training under the standard settings of the selection pipeline. The random B=2B=2 control draws two architectures uniformly at random from the 2047 non-empty neighborhood subsets (draw seeded by dataset and seed, redrawing duplicates), continues both, and selects between them by validation accuracy: two continuations, like the selection pipeline, but without backward elimination’s 66 validation passes. The full-model default continues one model, the all-neighborhood architecture, with no search and no selection step.

Compute accounting. All FLOPs are counted under one convention: PyTorch’s FlopCounterMode with dense pricing, explicit formulas for operations the counter does not price (eigendecomposition, SVD, sparse products), and every stage charged, including HOPSE’s encoding preprocessing. Runs that predate the profiler are priced by rebuilding the recorded architecture, profiling one training epoch and the evaluation passes under the same convention, and combining these per-epoch counts with the recorded epoch and evaluation tallies; we describe such costs as profiler-based reconstructions. Exact neighborhood attribution requires all 211=20482^{11}=2048 masked validation passes; backward elimination requires (n2+n)/2=66(n^2+n)/2=66; sampled cell attribution requires at most T+1T+1 forward passes per instance, with TT counting every evaluated ordering (Section A.1 and Table 5). Wall-clock comparisons run on one NVIDIA H200 GPU per run.

Figure 4. Wall-clock variant of Figure 2. The same four marker groups as Figure 2 (selected GCCN, selected HOPSE, and each family’s sweep), with the horizontal axis showing measured wall-clock seconds (one NVIDIA H200 GPU per run) instead of FLOPs. Wall-clock time includes HOPSE’s preprocessing.

Sensitivity Analyses

Initial-training length. Table 11 repeats the B=2B=2 selection with the initial model trained for 3, 5 (default), or 10 epochs. Mean selected test accuracy moves by at most 0.012 on Benzene and NCI1 and by 0.036 on MUTAG; the selected neighborhood sets themselves differ across settings.

Brief-run epochsBenzeneNCI1MUTAG
30.926 ± 0.0080.763 ± 0.0060.879 ± 0.033
5 (protocol)0.927 ± 0.0000.757 ± 0.0130.915 ± 0.021
100.925 ± 0.0060.769 ± 0.0080.887 ± 0.033

Table 11. Sensitivity to the brief-run epoch count. Test accuracy of the B=2B=2 selection (mean ± sd, 3 seeds) with the initial model trained for 3, 5 (default), or 10 epochs.

Selection metric on MANTRA. A separately run three-seed variant replaces ordinary validation accuracy with balanced validation accuracy in the masked game, the threshold’s pp, and the final comparison (τ\tau’s binomial form is then an approximation, since balanced accuracy is not a binomial proportion). It selects 11, 11, and 9 neighborhoods across seeds 42–44 and reaches 0.804 ± 0.011 balanced test accuracy, against 0.615 ± 0.103 for the original plain-accuracy run on the same seeds, consistent with ordinary validation accuracy rewarding majority-class predictions on this imbalanced dataset. Figure 2 and Table 9 report the original plain-accuracy selection.

Exhaustive Benchmark and Attribution Agreement

The controlled evaluation of § 6.2 uses all 26=642^{6}=64 subsets of the first six neighborhoods of Section A.2, each trained separately from scratch to the standard budget, under twelve dataset/hyperparameter settings and seeds 42–44; the empty subset is a trained model with node features only. The twelve settings are the four GraphXAI molecule datasets, MUTAG, NCI1, NCI109, the two ZINC configurations of Section B.2, and the three citation graphs. Seven settings were available while the selection procedure was developed; five (MUTAG, NCI109, Alkane-Carbonyl, and the two ZINC configurations) were held out and first evaluated after the procedure was fixed.

Table 12 compares exact Shapley attributions over the six neighborhoods computed two ways: from masked evaluations of the five-epoch model (the logit column scores validation logits, the primary comparison; the accuracy column re-scores the masked side by validation accuracy) and from the separately trained subsets’ test values. Agreement is the Spearman correlation between seed-averaged

Figure 5. Backward-elimination traces on all eleven datasets. Masked validation accuracy along the GCCN elimination path, from eleven neighborhoods to one, for training seeds 42–46. Markers identify the stop candidate selected before the first removal whose accuracy loss exceeds τ\tau; elimination continues after this candidate is marked. All panels share one yy-axis span, positioned per panel. MANTRA uses ordinary validation accuracy in this experiment.

attribution profiles; stability is the mean ±\pm sd of the per-seed correlations, which mixes seed-to-seed variation of the masked profile into the same statistic and is reported separately for that reason. The pooled row correlates 12×6=7212 \times6 = 72 points (one per setting and neighborhood, each a three-seed mean); intervals are 95% bootstrap over the twelve setting blocks (10,000 resamples), and the primary statistic’s permutation pp is 0.048 (20,000 permutations). The two games differ in split and score (validation logits or accuracy versus test accuracy or negative MAE), a mismatch the saved record does not allow us to remove.

Oracle Evaluation of Candidate Generation

Table 13 reruns backward elimination with each removal scored by the benchmark’s seed-averaged test values, per setting. Because it consults test scores, this analysis is an oracle diagnostic of the candidate generator; it is not a validation-only application of the practical method, and it does not validate the masked scores the practical pipeline uses. On the five held-out settings the greedy path contains the benchmark’s best architecture in four, with worst regret +0.0068 (the GIN-backbone ZINC recipe); on the seven development settings it matches the best architecture’s test value in five (on NCI1 with a size-5 subset rather than the size-3 optimum) and trails by at most +0.0042.

Reproduction Instructions

Environment. Python 3.11; PyTorch 2.3.0 (CUDA 12.1); torch-geometric with matching scatter/sparse wheels; TopoBench pinned at the commit recorded in the repository. The repository’s README gives the exact installation commands.

Released code. The release contains the explainer library with its test suite, including the exactness check of the Shapley implementation against brute-force enumeration, a tutorial, and the experiment runners and configuration files used in this paper.

Rerunning experiments. Each experiment has one runner under experiments/ (for example, architecture selection, the sweeps, the shortlist controls, the balanced-selected MANTRA variant, and the faithfulness study), with seeds and output locations set by command-line arguments. The exhaustive six-neighborhood benchmark and the GraphXAI explainer suite were produced on a separate cluster; their configurations and saved numerical results are included with the release.

References

  1. [1]Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(144), 2023.DOI
  2. [2]Marco Ancona, Cengiz Öztireli, and Markus Gross. Shapley value as principled metric for structured network pruning. arXiv preprint arXiv:2006.01795, 2020.arxiv.org/abs/2006.01795
  3. [3]Rubén Ballester, Ernst Röell, Daniel Bin Schmid, Mathieu Alain, Sergio Escalera, Carles Casacuberta, and Bastian Rieck. MANTRA: The manifold triangulations assemblage. In International Conference on Learning Representations (ICLR), 2025.arxiv.org/abs/2410.02392
  4. [4]Guillermo Bernárdez, Marco Montagna, Louis Van Langendonck, Martin Carrasco, Amirreza Akbari, Louisa Cornelis, Mathilde Papillon, Pere Barlet-Ros, Nina Miolane, and Lev Telyatnikov. HOPSE: Scalable higher-order positional and structural encoder for combinatorial representations. arXiv preprint arXiv:2505.15405, 2025.arxiv.org/abs/2505.15405
  5. [5]Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yuguang Wang, Pietro Liò, Guido Montúfar, and Michael Bronstein. Weisfeiler and Lehman go cellular: CW networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 2625–2640. Curran Associates, Inc., 2021. URL https://proceedings.neurips.cc/paper_files/paper/2021/file/157792e4abb490f99dbd738483e0dd24-paper.pdf.
  6. [6]Javier Castro, Daniel Gómez, and Juan Tejada. Polynomial calculation of the Shapley value based on sampling. Computers & Operations Research, 36(5):1726–1730, 2009. ISSN 0305-0548. doi: https://doi.org/10.1016/j.cor.2008.04.004. URL https://www.sciencedirect.com/science/article/pii/S0305054808000804.
  7. [8]Finale Doshi-Velez and Been Kim. Towards a rigorous science of interpretable machine learning. arXiv preprint arXiv:1702.08608, 2017.
  8. [9]Alexandre Duval and Fragkiskos D Malliaros. GraphSVX: Shapley value explanations for graph neural networks. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases (ECML PKDD), pages 302–318. Springer, 2021.arxiv.org/abs/2104.10482
  9. [10]Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1–48, 2023.
  10. [11]Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. In Topological Data Analysis and Beyond workshop at NeurIPS, 2020. URL https://arxiv.org/abs/2010.03633.
  11. [12]Yifan Feng, Haoxuan You, Zizhao Zhang, Rongrong Ji, and Yue Gao. Hypergraph neural networks. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence, pages 3558–3565. AAAI Press, 2019. doi: 10.1609/aaai.v33i01.33013558. URL https://ojs.aaai.org/index.php/AAAI/article/view/4235.DOI
  12. [13]Jonathan Frankle, David J. Schwab, and Ari S. Morcos. The early phase of neural network training. In International Conference on Learning Representations (ICLR), 2020.arxiv.org/abs/2002.10365
  13. [14]Daniel Fryer, Inga Strumke, and Hien Nguyen. Shapley values for feature selection: The good, the bad, and the axioms. IEEE Access, 9:144352–144360, 01 2021. doi: 10.1109/ACCESS.2021.3119110.DOI
  14. [15]Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Zorro: Valid, sparse, and stable explanations in graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 35(8):8687–8698, 2023.arxiv.org/abs/2105.08621
  15. [16]Amirata Ghorbani and James Zou. Neuron Shapley: Discovering the responsible neurons. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 5922–5932. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper_files/paper/2020/file/41c542dfe6e4fc3deb251d64cf6ed2e4-Paper.pdf.arxiv.org/abs/2002.09815
  16. [17]Michel Grabisch and Marc Roubens. An axiomatic approach to the concept of interaction among players in cooperative games. International Journal of Game Theory, 28(4):547–565, 1999.
  17. [18]Isabelle Guyon, Jason Weston, Stephen Barnhill, and Vladimir Vapnik. Gene selection for cancer classification using support vector machines. Machine Learning, 46:389–422, 2002.DOI
  18. [19]Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáenz, Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K. Dey, Soham Mukherjee, Shreya S. Samaga, Neal Livesay, Robin Walters, Paul Rosen, and Michael T. Schaub. Topological deep learning: Going beyond graph data. arXiv preprint arXiv:2206.00606, 2023.arxiv.org/abs/2206.00606
  19. [20]Trevor Hastie, Robert Tibshirani, and Jerome Friedman. The Elements of Statistical Learning: Data Mining, Inference, and Prediction. Springer, 2nd edition, 2009.
  20. [21]Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openreview.net/forum?id=SJU4ayYgl.arxiv.org/abs/1609.02907
  21. [22]Lisha Li, Kevin Jamieson, Giulia DeSalvo, Afshin Rostamizadeh, and Ameet Talwalkar. Hyperband: A novel bandit-based approach to hyperparameter optimization. Journal of Machine Learning Research, 18(185):1–52, 2018.
  22. [23]Scott M. Lundberg and Su-In Lee. A unified approach to interpreting model predictions. In Advances in Neural Information Processing Systems (NeurIPS), 2017.arxiv.org/abs/1705.07874
  23. [24]Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Advances in Neural Information Processing Systems (NeurIPS), volume 33, 2020.arxiv.org/abs/2011.04573
  24. [25]Sepideh Maleki, Ehsan Hajiramezanali, Gabriele Scalia, Tommaso Biancalani, and Kangway V. Chuang. Learning to explain hypergraph neural networks. In 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-ML), 2023. URL https://openreview.net/forum?id=B6YeDatCfW.
  25. [26]Joe Mellor, Jack Turner, Amos Storkey, and Elliot J. Crowley. Neural architecture search without training. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.arxiv.org/abs/2006.04647
  26. [27]Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataset: A collection of benchmark datasets for learning with graphs. In ICML 2020 Workshop on Graph Representation Learning and Beyond, 2020. arXiv:2007.08663.arxiv.org/abs/2007.08663
  27. [28]Maximilian Muschalik, Fabian Fumagalli, Paolo Frazzetto, Janine Strotherm, Luca Hermes, Alessandro Sperduti, Eyke Hüllermeier, and Barbara Hammer. Exact computation of any-order Shapley interactions for graph neural networks. In International Conference on Learning Representations (ICLR), 2025.
  28. [29]Theodore Papamarkou, Tolga Birdal, Michael M. Bronstein, Gunnar Carlsson, Justin Curry, Yue Gao, Mustafa Hajij, Roland Kwitt, Pietro Liò, Paolo Di Lorenzo, Vasileios Maroulas, Nina Miolane, Farzana Nasrin, Karthikeyan Natesan Ramamurthy, Bastian Rieck, Simone Scardapane, Michael T. Schaub, Petar Veličković, Bei Wang, Yusu Wang, Guo-Wei Wei, and Ghada Zamzmi. Position: Topological deep learning is the new frontier for relational learning. In Proceedings of the 41st International Conference on Machine Learning (ICML), 2024.
  29. [30]Mathilde Papillon, Sophia Sanborn, Mustafa Hajij, and Nina Miolane. Architectures of topological deep learning: A survey of message-passing topological neural networks. arXiv preprint arXiv:2304.10031, 2023.arxiv.org/abs/2304.10031
  30. [31]Mathilde Papillon, Guillermo Bernárdez, Claudio Battiloro, and Nina Miolane. TopoTune: A framework for generalized combinatorial complex neural networks. In Proceedings of the 42nd International Conference on Machine Learning (ICML), 2025.
  31. [32]Vitali Petsiuk, Abir Das, and Kate Saenko. RISE: Randomized input sampling for explanation of black-box models. In British Machine Vision Conference (BMVC), 2018.
  32. [33]Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. “why should I trust you?”: Explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 1135–1144, 2016.DOI
  33. [34]Benjamin Sanchez-Lengeling, Jennifer Wei, Brian Lee, Emily Reif, Peter Wang, Wesley Wei Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko. Evaluating attribution for graph neural networks. In Advances in Neural Information Processing Systems, volume 33, pages 5898–5910, 2020.
  34. [35]Lloyd S. Shapley. A value for n-person games. In Harold W. Kuhn and Albert W. Tucker, editors, Contributions to the Theory of Games, Volume II, volume 28 of Annals of Mathematics Studies, pages 307–317. Princeton University Press, Princeton, NJ, 1953.
  35. [36]Akshit Sinha, Sreeram Vennam, Charu Sharma, and Ponnurangam Kumaraguru. Higher order structures for graph explanations. In Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence and Thirty-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence, AAAI’25/IAAI’25/EAAI’25. AAAI Press, 2025. ISBN 978-1-57735-897-8. doi: 10.1609/aaai.v39i19.34260. URL https://doi.org/10.1609/aaai.v39i19.34260.
  36. [37]Erik Strumbelj and Igor Kononenko. An efficient explanation of individual classifications using game theory. Journal of Machine Learning Research, 11:1–18, 2010.
  37. [38]Shive Su, Julia Duta, Lucie Charlotte Magister, and Pietro Liò. Explaining hypergraph neural networks: From local explanations to global concepts. arXiv preprint arXiv:2410.07764, 2024.arxiv.org/abs/2410.07764
  38. [39]Lev Telyatnikov, Guillermo Bernárdez, Marco Montagna, Mustafa Hajji, Martin Carrasco, Pavlo Vasylenko, Mathilde Papillon, Ghada Zamzmi, Michael T. Schaub, Jonas Verhellen, Pavel Snopov, Bertran Miquel-Oliver, Manel Gil-Sorribes, Alexis Molina, Victor Guallar, Theodore Long, Julian Suk, Patryk Rygiel, Alexander V. Nikitin, Giordan Escalona, Michael Banf, Dominik Filipiak, Liliya Imasheva, Max Schattauer, Alvaro L. Martinez, Halley Fritze, Marissa Masden, Valentina Sánchez, Manuel Lecha, Andrea Cavallo, Claudio Battiloro, Matthew Piekenbrock, Mauricio Tec, George Dasoulas, Nina Miolane, Simone Scardapane, and Theodore Papamarkou. TopoBench: A framework for benchmarking topological deep learning. Journal of Data-centric Machine Learning Research, 2025. URL https://openreview.net/forum?id=07sTzyEVtY.arxiv.org/abs/2406.06642
  39. [40]Fabiano Veglianti, Lorenzo Antonelli, and Gabriele Tolomei. Counterfactual explanations for hypergraph neural networks. arXiv preprint arXiv:2602.04360, 2026.arxiv.org/abs/2602.04360
  40. [41]Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https://openreview.net/forum?id=ryGs6iA5Km.arxiv.org/abs/1810.00826
  41. [42]Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In Proceedings of the 33rd International Conference on Machine Learning, pages 40–48, 2016.arxiv.org/abs/1603.08861
  42. [43]Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating explanations for graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, 2019.
  43. [44]Haoran You, Chaojian Li, Pengfei Xu, Yonggan Fu, Yue Wang, Xiaohan Chen, Yingyan Lin, Zhangyang Wang, and Richard G. Baraniuk. Drawing early-bird tickets: Towards more efficient training of deep networks. In International Conference on Learning Representations (ICLR), 2020.arxiv.org/abs/1909.11957
  44. [45]Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In Proceedings of the 38th International Conference on Machine Learning (ICML), pages 12241–12252, 2021.arxiv.org/abs/2102.05152

Paper details

vlnc:W_hwn44rs6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY-SA 4.0
Usage

views · 9

downloads · 1

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents