OpenRaiser/Intern-Atlas huggingface dataset:
Pointwise Distance Distributions for detecting near-duplicates in large materials databases
Venue: arXiv cs.CG 2025
Year: 2025

Many real objects are modeled as discrete sets of points, such as corners or other salient features. For our main applications in chemistry, points represent atomic centers in a molecule or a solid material. We study the problem of classifying discrete (finite and periodic) sets of unordered points under isometry, which is any transformation preserving distances in a metric space. Experimental noise motivates the new practical requirement to make such invariants Lipschitz continuous so that perturbing every point in its epsilon-neighborhood changes the invariant up to a constant multiple of epsilon in a suitable distance satisfying all metric axioms. Since the given points are unordered, the key challenge is to compute all invariants and metrics in a near-linear time of the input size. We define the Pointwise Distance Distribution (PDD) for any discrete set and prove, in addition to the properties above, the completeness of PDD for all periodic sets in general position. The PDD can compare nearly 2 million crystals from the world's five largest databases within 2 hours on a modest desktop computer. The impact is upholding data integrity in crystallography because the PDD will not allow anyone to claim a `new' material as a noisy disguise of a known crystal.
Agnostic Online Learning and Excellent Sets
Venue: arXiv cs.DM 2025
Year: 2025

We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $ε$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi's celebrated Regularity Lemma). We prove that $ε$-excellent sets exist for any $ε< \frac{1}{2}$ in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $ε< 1/{2^{2^k}}$ or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide.
The emojification of sentiment on social media: Collection and analysis of a longitudinal Twitter sentiment dataset
Venue: arXiv cs.SI 2025
Year: 2025

Social media, as a means for computer-mediated communication, has been extensively used to study the sentiment expressed by users around events or topics. There is however a gap in the longitudinal study of how sentiment evolved in social media over the years. To fill this gap, we develop TM-Senti, a new large-scale, distantly supervised Twitter sentiment dataset with over 184 million tweets and covering a time period of over seven years. We describe and assess our methodology to put together a large-scale, emoticon- and emoji-based labelled sentiment analysis dataset, along with an analysis of the resulting dataset. Our analysis highlights interesting temporal changes, among others in the increasing use of emojis over emoticons. We publicly release the dataset for further research in tasks including sentiment analysis and text classification of tweets. The dataset can be fully rehydrated including tweet metadata and without missing tweets thanks to the archive of tweets publicly available on the Internet Archive, which the dataset is based on.
Contest Design with Threshold Objectives
Venue: arXiv cs.GT 2025
Year: 2025

We study contests where the designer's objective is an extension of the widely studied objective of maximizing the total output: The designer gets zero marginal utility from a player's output if the output of the player is very low or very high. We consider two variants of this setting, which correspond to two objective functions: binary threshold, where the designer's utility is a non-decreasing function of the number of players with output above a certain threshold; and linear threshold, where a player's contribution to the designer's utility is linear in her output if the output is between a lower and an upper threshold, and becomes constant below the lower and above the upper threshold. For both of these objectives, we study rank-order allocation contests and general contests. We characterize the contests that maximize the designer's objective and indicate techniques to efficiently compute them.
Tracing Affordance and Item Adoption on Music Streaming Platforms
Venue: arXiv cs.IR 2025
Year: 2025

Popular music streaming platforms offer users a diverse network of content exploration through a triad of affordances: organic, algorithmic and editorial access modes. Whilst offering great potential for discovery, such platform developments also pose the modern user with daily adoption decisions on two fronts: platform affordance adoption and the adoption of recommendations therein. Following a carefully constrained set of Deezer users over a 2-year observation period, our work explores factors driving user behaviour in the broad sense, by differentiating users on the basis of their temporal daily usage, adoption of the main platform affordances, and the ways in which they react to them, especially in terms of recommendation adoption. Diverging from a perspective common in studies on the effects of recommendation, we assume and confirm that users exhibit very diverse behaviours in using and adopting the platform affordances. The resulting complex and quite heterogeneous picture demonstrates that there is no blanket answer for adoption practices of both recommendation features and recommendations.
The mathematics of adversarial attacks in AI -- Why deep learning is unstable despite the existence of stable neural networks
Venue: arXiv cs.LG 2025
Year: 2025

The unprecedented success of deep learning (DL) makes it unchallenged when it comes to classification problems. However, it is well established that the current DL methodology produces universally unstable neural networks (NNs). The instability problem has caused an enormous research effort -- with a vast literature on so-called adversarial attacks -- yet there has been no solution to the problem. Our paper addresses why there has been no solution to the problem, as we prove the following mathematical paradox: any training procedure based on training neural networks for classification problems with a fixed architecture will yield neural networks that are either inaccurate or unstable (if accurate) -- despite the provable existence of both accurate and stable neural networks for the same classification problems. The key is that the stable and accurate neural networks must have variable dimensions depending on the input, in particular, variable dimensions is a necessary condition for stability. Our result points towards the paradox that accurate and stable neural networks exist, however, modern algorithms do not compute them. This yields the question: if the existence of neural networks with desirable properties can be proven, can one also find algorithms that compute them? There are cases in mathematics where provable existence implies computability, but will this be the case for neural networks? The contrary is true, as we demonstrate how neural networks can provably exist as approximate minimisers to standard optimisation problems with standard cost functions, however, no randomised algorithm can compute them with probability better than 1/2.
Contextual Combinatorial Bandits with Changing Action Sets via Gaussian Processes
Venue: arXiv cs.LG 2025
Year: 2025

We consider a contextual bandit problem with a combinatorial action set and time-varying base arm availability. At the beginning of each round, the agent observes the set of available base arms and their contexts and then selects an action that is a feasible subset of the set of available base arms to maximize its cumulative reward in the long run. We assume that the mean outcomes of base arms are samples from a Gaussian Process (GP) indexed by the context set ${\cal X}$, and the expected reward is Lipschitz continuous in expected base arm outcomes. For this setup, we propose an algorithm called Optimistic Combinatorial Learning and Optimization with Kernel Upper Confidence Bounds (O'CLOK-UCB) and prove that it incurs $\tilde{O}(\sqrt{λ^*(K)KTγ_{KT}(\cup_{t\leq T}\mathcal{X}_t)} )$ regret with high probability, where $γ_{KT}(\cup_{t\leq T}\mathcal{X}_t)$ is the maximum information gain associated with the sets of base arm contexts $\mathcal{X}_t$ that appeared in the first $T$ rounds, $K$ is the maximum cardinality of any feasible action over all rounds, and $λ^*(K)$ is the maximum eigenvalue of all covariance matrices of selected actions up to time $T$, which is a function of $K$. To dramatically speed up the algorithm, we also propose a variant of O'CLOK-UCB that uses sparse GPs. Finally, we experimentally show that both algorithms exploit inter-base arm outcome correlation and vastly outperform the previous state-of-the-art UCB-based algorithms in realistic setups.
Nash Convergence of Mean-Based Learning Algorithms in First-Price Auctions
Venue: arXiv cs.GT 2025
Year: 2025

The convergence properties of learning dynamics in repeated auctions is a timely and important question, with numerous applications in, e.g., online advertising markets. This work focuses on repeated first-price auctions where bidders with fixed values learn to bid using mean-based algorithms -- a large class of online learning algorithms that include popular no-regret algorithms such as Multiplicative Weights Update and Follow the Perturbed Leader. We completely characterize the learning dynamics of mean-based algorithms, under two notions of convergence: (1) time-average: the fraction of rounds where bidders play a Nash equilibrium converges to 1; (2) last-iterate: the mixed strategy profile of bidders converges to a Nash equilibrium. Specifically, the results depend on the number of bidders with the highest value: - If the number is at least three, the dynamics almost surely converges to a Nash equilibrium of the auction, in both time-average and last-iterate. - If the number is two, the dynamics almost surely converges to a Nash equilibrium in time-average but not necessarily last-iterate. - If the number is one, the dynamics may not converge to a Nash equilibrium in time-average or last-iterate. Our discovery opens up new possibilities in the study of the convergence of learning dynamics.
Enhancing business process execution with a context engine
Venue: arXiv cs.SE 2025
Year: 2025

Changes in workflow relevant data of business processes at run-time can hinder their completion or impact their profitability as they have been instantiated under different circumstances. The purpose of this paper is to propose a context engine to enhance a business process management (BPM) system's context-awareness. The generic architecture provides the flexibility to configure processes during initialization as well as to adapt running instances at decision gates or during execution due to significant context change. The paper discusses context-awareness as the conceptual background. The technological capabilities of business rules and complex event processing (CEP) are outlined in an architecture design. A reference process is proposed and discussed in an exemplary application. The results provide an improvement over the current situation of static variable instantiation of business processes with local information. The proposed architecture extends the well-known combination of business rules and BPM systems with a context engine based on CEP. The resulting architecture for a BPM system using a context engine is generic in nature and, hence, requires to be contextualized for situated implementations. Implementation success is dependent on the availability of context information and process compensation options. Practitioners receive advice on a reference architecture and technology choices for implementing systems, which can provide and monitor context information for business processes as well as intervene and adapt the execution. Currently, there is no multi-purpose non-proprietary context engine based on CEP or any other technology available for BPM, which facilitates the adaptation of processes at run-time due to changes in context variables. This paper will stimulate a debate between research and practice on suitable design and technology.
State-Space Constraints Can Improve the Generalisation of the Differentiable Neural Computer to Input Sequences With Unseen Length
Venue: arXiv cs.LG 2025
Year: 2025

Memory-augmented neural networks (MANNs) can perform algorithmic tasks such as sorting. However, they often fail to generalise to input sequence lengths not encountered during training. We introduce two approaches that constrain the state space of the MANN's controller network: state compression and state regularisation. We empirically demonstrated that both approaches can improve generalisation to input sequences of out-of-distribution lengths for a specific type of MANN: the differentiable neural computer (DNC). The constrained DNC could process input sequences that were up to 2.3 times longer than those processed by an unconstrained baseline controller network. Notably, the applied constraints enabled the extension of the DNC's memory matrix without the need for retraining and thus allowed the processing of input sequences that were 10.4 times longer. However, the improvements were not consistent across all tested algorithmic tasks. Interestingly, solutions that performed better often had a highly structured state space, characterised by state trajectories exhibiting increased curvature and loop-like patterns. Our experimental work demonstrates that state-space constraints can enable the training of a DNC using shorter input sequences, thereby saving computational resources and facilitating training when acquiring long sequences is costly.
Boosting Resource-Constrained Federated Learning Systems with Guessed Updates
Venue: arXiv cs.LG 2025
Year: 2025

Federated learning (FL) enables a set of client devices to collaboratively train a model without sharing raw data. This process, though, operates under the constrained computation and communication resources of edge devices. These constraints combined with systems heterogeneity force some participating clients to perform fewer local updates than expected by the server, thus slowing down convergence. Exhaustive tuning of hyperparameters in FL, furthermore, can be resource-intensive, without which the convergence is adversely affected. In this work, we propose GEL, the guess and learn algorithm. GEL enables constrained edge devices to perform additional learning through guessed updates on top of gradient-based steps. These guesses are gradientless, i.e., participating clients leverage them for free. Our generic guessing algorithm (i) can be flexibly combined with several state-of-the-art algorithms including FEDPROX, FEDNOVA, FEDYOGI or SCALEFL; and (ii) achieves significantly improved performance when the learning rates are not best tuned. We conduct extensive experiments and show that GEL can boost empirical convergence by up to 40% in resource constrained networks while relieving the need for exhaustive learning rate tuning.
Can Character-based Language Models Improve Downstream Task Performance in Low-Resource and Noisy Language Scenarios?
Venue: arXiv cs.CL 2025
Year: 2025

Recent impressive improvements in NLP, largely based on the success of contextual neural language models, have been mostly demonstrated on at most a couple dozen high-resource languages. Building language models and, more generally, NLP systems for non-standardized and low-resource languages remains a challenging task. In this work, we focus on North-African colloquial dialectal Arabic written using an extension of the Latin script, called NArabizi, found mostly on social media and messaging communication. In this low-resource scenario with data displaying a high level of variability, we compare the downstream performance of a character-based language model on part-of-speech tagging and dependency parsing to that of monolingual and multilingual models. We show that a character-based model trained on only 99k sentences of NArabizi and fined-tuned on a small treebank of this language leads to performance close to those obtained with the same architecture pre-trained on large multilingual and monolingual models. Confirming these results a on much larger data set of noisy French user-generated content, we argue that such character-based language models can be an asset for NLP in low-resource and high language variability set-tings.
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
Venue: arXiv cs.IT 2025
Year: 2025

Locally Decodable Codes (LDCs) are error-correcting codes for which individual message symbols can be quickly recovered despite errors in the codeword. LDCs for Hamming errors have been studied extensively in the past few decades, where a major goal is to understand the amount of redundancy that is necessary and sufficient to decode from large amounts of error, with small query complexity. In this work, we study LDCs for insertion and deletion errors, called Insdel LDCs. Their study was initiated by Ostrovsky and Paskin-Cherniavsky (Information Theoretic Security, 2015), who gave a reduction from Hamming LDCs to Insdel LDCs with a small blowup in the code parameters. On the other hand, the only known lower bounds for Insdel LDCs come from those for Hamming LDCs, thus there is no separation between them. Here we prove new, strong lower bounds for the existence of Insdel LDCs. In particular, we show that $2$-query linear Insdel LDCs do not exist, and give an exponential lower bound for the length of all $q$-query Insdel LDCs with constant $q$. For $q \ge 3$ our bounds are exponential in the existing lower bounds for Hamming LDCs. Furthermore, our exponential lower bounds continue to hold for adaptive decoders, and even in private-key settings where the encoder and decoder share secret randomness. This exhibits a strict separation between Hamming LDCs and Insdel LDCs. Our strong lower bounds also hold for the related notion of Insdel LCCs (except in the private-key setting), due to an analogue to the Insdel notions of a reduction from Hamming LCCs to LDCs. Our techniques are based on a delicate design and analysis of hard distributions of insertion and deletion errors, which depart significantly from typical techniques used in analyzing Hamming LDCs.
Geodesic Length Distribution in Sparse Network Ensembles
Venue: arXiv cs.SI 2025
Year: 2025

A key task in the study of networked systems is to derive local and global properties that impact connectivity, synchronizability, and robustness; computing shortest paths or geodesics yields measures of network connectivity that can explain such phenomena. We derive an analytic distribution of geodesic lengths on the giant component in the supercritical regime -- when the giant component exists -- or on small components in the subcritical regime, of any sparse (and possibly directed) network with conditionally independent edges, in the infinite-size limit. We provide specific results for widely used network models like stochastic block models, dot product graphs, random geometric graphs, and sparse graphons. The survival function of the geodesic length distribution possesses a simple closed-form expression which is asymptotically tight for finite lengths, has a natural interpretation of traversing independent geodesics in the network, and delivers novel insight into the aforementioned network families.
Continuity, Uniqueness and Long-Term Behavior of Nash Flows Over Time
Venue: arXiv cs.GT 2025
Year: 2025

We consider a dynamic model of traffic that has received a lot of attention in the past few years. Users control infinitesimal flow particles aiming to travel from an origin to a destination as quickly as possible. Flow patterns vary over time, and congestion effects are modeled via queues, which form whenever the inflow into a link exceeds its capacity. Despite lots of interest, some very basic questions remain open in this model. We resolve a number of them in the single-commodity setting: - We show uniqueness of journey times in equilibria. - We show continuity of equilibria: small perturbations to the instance or to the traffic situation at some moment cannot lead to wildly different equilibrium evolutions. - We demonstrate that, assuming constant inflow into the network at the source, equilibria always settle down into a "steady state" in which the behavior extends forever in a linear fashion. One of our main conceptual contributions is to show that the answer to the first two questions, on uniqueness and continuity, are intimately connected to the third. To resolve the third question, we substantially extend the approach of Cominetti et al., who show a steady-state result in the regime where the input flow rate is smaller than the network capacity.
Answer Generation for Questions With Multiple Information Sources in E-Commerce
Venue: arXiv cs.CL 2025
Year: 2025

Automatic question answering is an important yet challenging task in E-commerce given the millions of questions posted by users about the product that they are interested in purchasing. Hence, there is a great demand for automatic answer generation systems that provide quick responses using related information about the product. There are three sources of knowledge available for answering a user posted query, they are reviews, duplicate or similar questions, and specifications. Effectively utilizing these information sources will greatly aid us in answering complex questions. However, there are two main challenges present in exploiting these sources: (i) The presence of irrelevant information and (ii) the presence of ambiguity of sentiment present in reviews and similar questions. Through this work we propose a novel pipeline (MSQAP) that utilizes the rich information present in the aforementioned sources by separately performing relevancy and ambiguity prediction before generating a response. Experimental results show that our relevancy prediction model (BERT-QA) outperforms all other variants and has an improvement of 12.36% in F1 score compared to the BERT-base baseline. Our generation model (T5-QA) outperforms the baselines in all content preservation metrics such as BLEU, ROUGE and has an average improvement of 35.02% in ROUGE and 198.75% in BLEU compared to the highest performing baseline (HSSC-q). Human evaluation of our pipeline shows us that our method has an overall improvement in accuracy of 30.7% over the generation model (T5-QA), resulting in our full pipeline-based approach (MSQAP) providing more accurate answers. To the best of our knowledge, this is the first work in the e-commerce domain that automatically generates natural language answers combining the information present in diverse sources such as specifications, similar questions, and reviews data.