Certified Reference Sets: Formal Explanations for Paper Classifiers on Citation Graphs

When a model assigns a paper to a research field, the natural bibliometric question is which of its references put it there. Today that question gets answered in one of two ways. Classical bibliometrics counts which fields the cited works belong to. Graph-explainer tools score edges by masking them. Neither answer is a guarantee. This proposal asks for a certificate instead. A minimal sufficient reference set is a smallest subset of a paper's reference list such that, if those citations are kept, no plausible change to the rest of the list can move the classifier's prediction to another field. It is the citation-graph version of an abductive explanation, meaning a set of inputs that provably forces the output.

The theory of formal explanations says such certificates are usually intractable. For ReLU networks and tree ensembles, even approximating the best one is provably impossible. The theory also says that requiring explanations to stay "realistic" can make matters worse. Nobody has worked out where citation-graph classifiers fall in this picture, or whether the bibliometrically meaningful restrictions ("you may only cite earlier papers", "a reference list must look like a real one") keep the problem tractable or break it. We propose to map this precisely, and then to build a classifier for ogbn-arxiv whose explanations are exact and cheap. We will measure how much accuracy that costs and what the certified reference sets reveal about interdisciplinary structure.

Core Claim

Our claim is that there is a sharp and useful tractability boundary for explaining paper-level field classifiers.

On the tractable side is a one-hop classifier that sums or averages frozen text embeddings of a paper's references and feeds them to a linear or monotone scorer. For this model, the minimal sufficient reference set is computable exactly in polynomial time when the only allowed modifications are to delete references or to add references from a per-candidate filter such as temporal order. The worst case over the free references then decomposes into a sorting problem. Mean aggregation needs a fractional-programming step on top of the sort.

On the intractable side, three things push the problem into hardness:

  • adding a second round of message passing with a nonlinearity,
  • letting the "freedom" of the free references range over any reference list,
  • constraining counterfactual reference lists with a learned plausibility model that couples edges.

We expect NP-hardness in all three cases and, for the two-layer case, inapproximability. The practical bet is that the tractable side gives up little accuracy on citation benchmarks. If so, it is the right tool for certified science mapping.

This builds on four results:

  • Perceptron vs. MLP split. Local vs. Global Interpretability: A Computational Complexity Perspective shows local sufficient reasons are polynomial for Perceptrons and $\Sigma_2^P$-complete for MLPs. That split is exactly the one we expect to reappear between one-hop linear aggregation and deeper message passing, and it supplies our reduction templates.
  • Inapproximability for ReLU networks. On the Hardness of Computing Counterfactual and Semi-factual Explanations in XAI proves that counterfactuals for ReLU networks, additive trees and nearest-neighbour models cannot be approximated within $2^{p(n)}$ unless P = NP. It works over vector inputs, not edge sets. We will adapt its reductions to edge deletion and addition.
  • Plausibility can dominate complexity. Hard to Explain: On the Computational Hardness of In-Distribution Model Interpretation shows that adding a distribution detector can raise the minimum-change problem from polynomial to NP-complete, even for a Perceptron. This is the result that constrains our design. It predicts that a learned "realistic reference list" detector will destroy tractability. It therefore motivates keeping plausibility as per-edge filters, and testing empirically what that simplification loses.
  • Tractability through monotone structure. On Efficiently Explaining Graph-Based Classifiers gets polynomial explanations from monotone decision-graph structure. We use the same monotonicity idea, applied to aggregation over the citation graph rather than to the model's internal DAG.

Research Program

Theory. The first part defines sufficient reference sets, and their counterfactual dual (the smallest set of references whose removal flips the field), under three freedom models: deletion only, deletion plus temporally admissible additions, and additions constrained by a learned plausibility scorer. We will state and prove complexity results for one-hop sum and mean aggregation and for two-layer message passing. The multiclass case is the delicate one, because the adversary may push toward any of 40 competing fields. We expect a polynomial algorithm for sum aggregation and do not presume one for mean aggregation; we will report whichever the proof gives. We also expect the hitting-set duality of On Relating Explanations and Adversarial Examples to carry over, which would let us enumerate all minimal reference sets via duality.

Model. The second part builds the certifiable classifier. It uses frozen language-model embeddings of titles and abstracts, a one-hop monotone aggregator over references, and a linear head. We will train it on ogbn-arxiv and compare it against deep text-and-graph models. The accuracy gap is the price of certification, and we will report it honestly.

Bibliometric analysis. The third part uses the certificates as a science-mapping instrument. We will compute, for every arXiv paper, its certified reference set, and measure two things:

  • Size. How small certified sets are. The analogue on tabular data is On Efficiently Explaining Graph-Based Classifiers, which found 2 to 5 essential features out of 12 on adult.
  • Field composition. How often a paper's certified set contains references from outside its assigned field. This is a certified interdisciplinarity index, which we contrast with raw cross-field citation shares.

We will then test whether certified references are cited differently in the text. Using the resolved citation contexts in Bibliometric-Enhanced arXiv: A Data Set for Paper-Based and Citation-Based Tasks (29.2 million contexts, about 96% resolution precision), we ask whether certified references are mentioned more often in a paper's body than the references the certificate leaves out. Finally, because What comes first the Co-authorship Network or the Citation? reports that citation impact tracks collaboration density (Spearman $R = 0.3863$), we check whether heavily cited references are over-represented in certified sets beyond what their text content justifies. That would be a prestige artefact inside the classifier itself.

Baselines

Naive reference point. The zero-model baseline is classical bibliographic coupling. We predict a paper's field by majority field of its references, and "explain" by listing the references in the winning field. It runs on the same ogbn-arxiv splits with no tuning. The certified model must beat it in accuracy to be worth using. Its explanations must also differ from this list often enough to show the classifier is not a relabelled vote count.

Strongest heuristic explainer. The strongest heuristic is edge-mask optimization of the GNNExplainer type, applied to both our certifiable model and a two-layer GNN. We give it the same per-paper time budget as the exact algorithm, and we run our exact verifier on its outputs. The only reported number for this family is 58% motif accuracy on synthetic CYCLIQ, against 88% for the distribution-compliant CoGE, both in Contrastive Graph Neural Network Explanation. CoGE itself is formulated for graph-level classification, so it is not directly runnable here. No reported result was found on Lacuna for any edge explainer on ogbn-arxiv. Beating this baseline means certified sets that are at least as small and are 100% sound under verification, while heuristic sets fail verification on a measurable fraction of papers.

Accuracy reference. The strongest predictive system is TAPE, from Explanations as Features: LLM-Based Features for Text-Attributed Graphs. It reports 77.50% accuracy on ogbn-arxiv. GLEM, from Learning on Large-scale Text-attributed Graphs via Variational Inference, reports gains up to 19% over raw OGB features. We will not claim to beat 77.50%. Success is a certifiable model within a few points of a two-layer GNN trained on the same frozen embeddings, which we train ourselves with a matched hyperparameter budget.

Ablations.

  • Freedom model. Deletion-only versus temporal-additions versus a learned plausibility scorer. This isolates whether the per-edge plausibility restriction is what preserves tractability, and what explanation size and realism it gives up.
  • Aggregation. Sum versus mean aggregation.

Why not just…?

Why not just run an exact MILP or SAT solver on an ordinary two-layer GNN? This is the most serious threat. ogbn-arxiv reference lists are short, so worst-case hardness may never bite in practice. We will measure solver time and timeout rate as a function of neighbourhood size. We use one-hop lists and two-hop neighbourhoods, where the latter can reach thousands of nodes. If the solver finishes on nearly all two-hop instances within budget, the restricted model is unnecessary for arXiv. The contribution then shrinks to the theory plus the bibliometric analysis, and we will say so.

Why not just count reference fields, as classical bibliometrics does? The naive baseline tests this directly. If certified sets usually coincide with same-field references, the certificate adds nothing. We will report the fraction of papers where they diverge, and whether divergence predicts cross-field citation contexts in the Bibliometric-Enhanced arXiv text.

Why not just ask an LLM to explain the field assignment, as TAPE does? TAPE's explanations are features that improve accuracy, not claims about which inputs force the output. We will check LLM-named references against our verifier on tape-arxiv23, the post-2023 split, to avoid memorization. The test is how often the named references are actually sufficient for the classifier's prediction.

Decisive Checks

The project succeeds if four things hold:

  • the tractability proofs go through for one-hop aggregation;
  • exact certified sets are computed for all roughly 170,000 ogbn-arxiv papers in minutes;
  • the certifiable model's accuracy on ogbn-arxiv, Cora and PubMed stays close to a matched two-layer GNN;
  • heuristic edge explainers fail exact verification on a nontrivial fraction of papers.

The project fails if any of three things happens:

  • two-hop exact solving is routinely fast, removing the need for the restricted model;
  • the accuracy gap is large;
  • certified sets reduce to same-field majority lists.