CS Paper Radar

General Classification for Digital Knowledge: Algorithm, Identifiers and a First Benchmark

David Awad

cs.DL ·submitted 2026-10-14 04:04 UTC · v1
benchmark

Abstract

Digital libraries and knowledge graphs need a way to organize very large collections so that related works are close and any work is quick to reach. The classifications libraries inherited for this, such as LCC and DDC, are maintained by editorial staff, are partly closed, and were not built against a stated, measurable objective. We propose the opposite: a general classification that is fitted, under the constraints that make a classification usable on a shelf or in a browse list, to the same quantity that a companion survey and benchmark (Awad, 2026) ranks existing schemes by. The objective is J = D + 0.005 N, where D is the normalized Dasgupta cost of the class tree on a fixed similarity graph (Dasgupta, 2016) and N is an expected navigation cost in bits with a per-level charge. Two constraints are hard: every class is a contiguous run of one fixed shelf order (the optimal-alphabetic-tree constraint of Hu and Tucker, 1971), and new works are filed by splitting leaf classes only, so that every existing class keeps its code, label and parent. On a corpus of 10,000 arXiv papers the fitted prototype has 110 hand-labelled classes and reaches cost 0.1722 in sample (average linkage 0.1518; arXiv's own categories 0.3333; the best existing scheme reached through the same lexical classifier 0.6414, from the survey). Filing 500 library books as new works created 16 classes and changed no existing identifier. Fit, filing and scoring share one embedding: the held-out skill of 0.922 falls to 0.896 when the same fit is scored on the graphs of the two other models, and on books the average falls from 0.806 to 0.731. The scheme has also seen only arXiv, and labels for inserted classes are weak. We state those limits plainly, release the scheme as CC0 open data, and ask whether a learned, open, order-preserving classification can become a general one.

Comment
10 pages

Closest papers

Nearest neighbours by meaning across the whole index.

SAT-based Encodings for Optimal Decision Trees with Explicit Paths

cs.LO ·2026-08-20 ·Mikoláš Janota, António Morgado
top venuehighly cited similarity 0.58
Abstract

Decision trees play an important role both in Machine Learning and Knowledge Representation. They are attractive due to their immediate interpretability. In the spirit of Occam's razor, and interpretability, it is desirable to calculate the smallest tree. This, however, has proven to be a challenging task and greedy approaches are typically used to learn trees in practice. Nevertheless, recent work showed that by the use of SAT solvers one may calculate the optimal size tree for real-world benchmarks. This paper proposes a novel SAT-based encoding that explicitly models paths in the tree, which enables us to control the tree's depth as well as size. At the level of individual SAT calls, we investigate splitting the search space into tree topologies. Our tool outperforms the existing implementation. But also, the experimental results show that minimizing the depth first and then minimizing the number of nodes enables solving a larger set of instances.

0.68

SHELF: A Synthetic Harness for Multi-Task Bibliographic Benchmarking

cs.CL cs.AIcs.IR ·2026-09-02 ·Michael J. Bommarito
benchmarkcode/data similarity 0.55
Abstract · 17 pages, 15 tables. Code available at https://github.com/mjbommar/shelf-benchmark ; data available at https://huggingface.co/datasets/mjbom…

Libraries and archives manage large collections with limited staff and computing budgets, yet common benchmarks do not systematically test their bibliographic work. They need to know which methods work for their tasks and what those methods require to run. SHELF, the Synthetic Harness for Evaluating LLM Fitness, addresses this gap. It is a Python system that turns labelled taxonomies, writing specifications, and a generation budget into controlled benchmark data and evaluation tasks. This first release contains 62,899 model-written documents based on Library of Congress vocabularies, with tasks for classification, clustering, retrieval, pair classification, and instruction retrieval. We compare TF, TF-IDF, BM25, popular encoders, and, on subject classification only, zero-shot decoders; each method appears only on tasks that support it. Subject classification reaches 0.8887, while genre-form classification reaches only 0.2605, and several pair and clustering tasks remain near chance. Sparse methods remain competitive on classification, while TF-IDF is the fastest measured arm in the subject timing experiment. SHELF also varies bibliographic facets independently and can generate new, verifiably unseen documents after a model's training cutoff. Comparisons with LCSHBench and Project Gutenberg show that model rankings transfer more reliably than absolute scores, but SHELF scores do not estimate accuracy on production catalogue data. We release all source code and data under permissive licenses on GitHub and Hugging Face.

0.38

Reading the Neighborhood: Text-Attentive Graph Reranking for Automated Subject Indexing

cs.IR cs.DL ·2026-10-14 ·Lakshmi Rajendram Bashyam, Ralf Krestel
published similarity 0.55
Abstract · Presented at the ACM/IEEE-CS Joint Conference on Digital Libraries (JCDL) 2026

Subject indexing assigns descriptors from a controlled vocabulary to bibliographic records, a task characterized by thousands of labels, few positive examples per label, and a long tail of rarely used descriptors. Existing extreme multi-label classifiers treat the vocabulary as a flat list, ignoring the semantic relations that thesauri encode. We present TAGHN, a heterogeneous graph reranker over a per-document subgraph of retrieved candidates augmented with the thesaurus neighborhood. The relevance of a candidate descriptor is estimated jointly from its similarity with the document and also the degree to which the candidate's thesaurus neighborhood matches the document content. A decomposed scoring head combines interpretable graph-derived features with retrieval signals. On STW, an economic thesaurus of 6,198 descriptors, TAGHN reaches 0.380 macro F1 against 0.346 for a fine-tuned cross-encoder and 0.278 for a fixed-vocabulary XMLC classifier. In terms of micro F1, it outperforms reranking models and stays competitive (-3.0) with the best fixed-vocabulary XMLC model. Qualitative analysis shows the graph resolving errors that per-label scoring cannot, selecting a narrower gold descriptor where an unstructured reranker settles for its broader parent.

0.50

Sorting from Counterexamples

cs.LG cs.CCcs.CGcs.DS+1 ·2026-08-21 ·Noga Alon, Shay Moran, Shlomo Moran
publishedtheory similarity 0.55
Abstract

Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.

0.37

AutoGrable: What Is a Good Graph for a Table?

cs.LG ·2026-08-11 ·Tamara Cucumides, Floris Geerts
similarity 0.54
Abstract · 28 pages, 4 figures

Graph learning presupposes a graph, and tables and relational databases do not come with one. Applying a GNN to them requires deciding which entities become nodes, which of them to connect, and through which relations---a decision made by hand, by schema heuristics, or by training a model on every candidate graph and keeping the best. We give a criterion that requires no trained graph model. In the minimal table-to-graph abstraction each row is a node, so a message-passing GNN, bounded by 1-WL, sees a construction only as a partition of the rows into colour-refinement classes: a construction is good for a task when that partition separates rows with different labels and does not split rows that share one. AutoGrable turns this criterion into a construction procedure. For incidence constructions the partition is fixed by the selected columns, so building a graph reduces to choosing them, and we score a candidate subset by a label-alignment risk: the held-out risk of the best predictor constant on its blocks, penalised by an occupancy term measuring how thinly the blocks are populated. The score materialises no graph and trains no GNN, so AutoGrable can search the space of subsets greedily and cheaply, and returns the resulting grable for single tables and for foreign-key schemas alike. Our experiments show that over a space of candidate graphs the score discards a large fraction while retaining the best; that AutoGrable recovers the columns that generate the label on controlled tasks and outperforms fixed, random, and task-aware constructors on real tasks under a fixed predictor; and that it is the only method compared that can decline to build a graph when none helps.

0.46

Data Scout: Targeted Web Crawling for Domain-Specific Pretraining Corpora

cs.LG cs.AI ·2026-09-04 ·Chirag Garg, Eelaaf Zahid, Farhan Ahmed, Jay Pankaj Gala, Eric Butler +1 more
top venue similarity 0.54
Abstract

The dominant approach to building domain-specific pretraining corpora is to filter large web archives such as CommonCrawl. This works well for popular domains but breaks down for specialized ones, where relevant content is sparse and often beyond the reach of popularity-driven crawlers. We present Data Scout, which inverts this: instead of filtering an archive, it directs a targeted crawl. An LLM expands a root topic into a taxonomy and thousands of search queries; the returned URLs (seeds) are grouped by subdomain and screened with a user-supplied classifier (the probe), admitting each subdomain on the basis of a small sample. This works because relevance has a sharp boundary at the subdomain level: in mathematics, a page is 21x more likely to be relevant than one on a sibling subdomain. With the FineMath classifier as the probe, 21.9% of crawled pages are high-quality math content, 70x the 0.31% rate from filtering a comparable web sample, so the crawl wastes far less effort. But the payoff is not just efficiency: 63.2% of these pages are missing from CommonCrawl altogether, yet just as useful for training. Continued pretraining of Llama-3.2-3B on 1.9B Data Scout tokens matches FineMath corpus on GSM8k. Because the probe is the only domain-specific component, Data Scout can in principle apply to any domain with such a classifier.

0.47

Block Sparse Attention with Log-Linear Complexity

cs.LG ·2026-09-25 ·Bohao Tang, Zhen Qin, Yuqi Pan, Zheng Li, Pengfei Liu
highly cited similarity 0.54
Abstract

Scaling language models to long contexts is limited by the quadratic cost of self-attention. Block sparse attention offers an efficient alternative, but selecting the retained blocks remains a bottleneck. Conventional block selection requires scoring all query-block pairs and therefore remains quadratic in sequence length. To address this issue, we propose PISA, a block-sparse attention mechanism that employs a pyramid Top-$K$ selection strategy. The main idea is to gradually narrow down the candidates across different levels, making it more efficient to find the most relevant keys. Specifically, we construct a coarse-to-fine hierarchy of keys and perform selection from the coarsest level. At each level, LogSumExp scoring is applied to a bounded candidate set to select candidates for the next finer level, continuing until the finest level is reached. Through pooling, we construct $O(\log N)$ levels of keys, yielding an overall complexity of $O(N\log N)$, where $N$ denotes the sequence length. We develop hardware-aware Triton kernels for both training and inference, fusing hierarchical routing and LogSumExp scoring without materializing the query-key score matrix. We further evaluate our method on language modeling tasks. Compared with the baseline, our method achieves comparable performance on benchmarks such as commonsense reasoning while delivering better results on retrieval tasks.

0.42

Practical Threshold-based Tree Edit Distance Lower-Bounds

cs.DB ·2026-09-02 ·Lukáš Moravec, Radim Bača
similarity 0.54
Abstract · Full version with 15 pages

Threshold-based similarity search over tree-structured data using tree edit distance (TED) is computationally intensive. Given a query tree and a database of trees, the goal is to retrieve all trees within a predefined TED threshold $τ$. Because exact TED computation is expensive, practical methods employ lower-bounds to prune dissimilar candidates before verification. Existing lower-bounds exhibit a fundamental trade-off: inexpensive statistical and structural bounds provide limited pruning power, whereas the more precise traversal-based string edit distance (SED) bound is expensive to compute using standard quadratic dynamic programming. Moreover, previous comparative studies do not cover recent structural filters or threshold-aware SED implementations, leaving their practical trade-offs unclear. In this article, we first provide a comprehensive experimental comparison of state-of-the-art TED lower-bounds in terms of pruning precision and computational cost. We then accelerate the SED lower-bound using Ukkonen's bounded string edit distance algorithm, substantially reducing its runtime without affecting its pruning power. Finally, we introduce the SED-struct threshold filter, which strengthens SED with axes-aware constraints capturing structural relationships among tree nodes. Experiments on synthetic and real-world datasets show that SED-struct consistently achieves the highest filtering precision while retaining practical filtering costs. The results suggest that SED-struct is particularly beneficial for heterogeneous tree collections in which the standard SED lower-bound achieves relatively low precision.

0.24