OpenRaiser/Intern-Atlas huggingface dataset:
On Continuity of Robust and Accurate Classifiers
Venue: arXiv cs.LG 2025
Year: 2025

The reliability of a learning model is key to the successful deployment of machine learning in various applications. However, it is difficult to describe the phenomenon due to the complicated nature of the problems in machine learning. It has been shown that adversarial training can improve the robustness of the hypothesis. However, this improvement usually comes at the cost of decreased performance on natural samples. Hence, it has been suggested that robustness and accuracy of a hypothesis are at odds with each other. In this paper, we put forth the alternative proposal that it is the continuity of a hypothesis that is incompatible with its robustness and accuracy in many of these scenarios. In other words, a continuous function cannot effectively learn the optimal robust hypothesis. We introduce a framework for a rigorous study of harmonic and holomorphic hypothesis in learning theory terms and provide empirical evidence that continuous hypotheses do not perform as well as discontinuous hypotheses in some common machine learning tasks. From a practical point of view, our results suggests that a robust and accurate learning rule would train different continuous hypotheses for different regions of the domain. From a theoretical perspective, our analysis explains the adversarial examples phenomenon in these situations as a conflict between the continuity of a sequence of functions and its uniform convergence to a discontinuous function. Given that many of the contemporary machine learning models are continuous functions, it is important to theoretically study the continuity of robust and accurate classifiers as it is consequential in their construction, analysis and evaluation.
Bandwidth Parameterized by Cluster Vertex Deletion Number
Venue: arXiv cs.DS 2025
Year: 2025

Given a graph $G$ and an integer $b$, Bandwidth asks whether there exists a bijection $π$ from $V(G)$ to $\{1, \ldots, |V(G)|\}$ such that $\max_{\{u, v \} \in E(G)} | π(u) - π(v) | \leq b$. This is a classical NP-complete problem, known to remain NP-complete even on very restricted classes of graphs, such as trees of maximum degree 3 and caterpillars of hair length 3. In the realm of parameterized complexity, these results imply that the problem remains NP-hard on graphs of bounded pathwidth, while it is additionally known to be W[1]-hard when parameterized by the tree-depth of the input graph. In contrast, the problem does become FPT when parameterized by the vertex cover number. In this paper we make progress in understanding the parameterized (in)tractability of Bandwidth. We first show that it is FPT when parameterized by the cluster vertex deletion number cvd plus the clique number $ω$, thus significantly strengthening the previously mentioned result for vertex cover number. On the other hand, we show that Bandwidth is W[1]-hard when parameterized only by cvd. Our results develop and generalize some of the methods of argumentation of the previous results and narrow some of the complexity gaps.
Automatic Data Repair: Are We Ready to Deploy?
Venue: arXiv cs.DB 2025
Year: 2025

Data quality is paramount in today's data-driven world, especially in the era of generative AI. Dirty data with errors and inconsistencies usually leads to flawed insights, unreliable decision-making, and biased or low-quality outputs from generative models. The study of repairing erroneous data has gained significant importance. Existing data repair algorithms differ in information utilization, problem settings, and are tested in limited scenarios. In this paper, we initially compare and summarize these algorithms using a new guided information-based taxonomy. We then systematically conduct a comprehensive evaluation of 12 mainstream data repair algorithms under the settings of various data error rates, error types, and downstream analysis tasks, assessing their error reduction performance with a novel metric. Also, we develop an effective and unified repair optimization strategy that substantially benefits the state of the arts, as empirically confirmed. We demonstrate that, the pure clean data may not necessarily yield the best performance in data analysis tasks and data is always worth repairing regardless of error rate. Based on the found observations and insights, we provide some practical guidelines for 5 scenarios and 2 main data analysis tasks. We anticipate this paper enabling researchers and users to well understand and deploy data repair algorithms in practice. Finally, we outline research challenges and promising future directions in the data repair field.
JugglePAC: A Pipelined Accumulation Circuit
Venue: arXiv cs.AR 2025
Year: 2025

Reducing a set of numbers to a single value is a fundamental operation in applications such as signal processing, data compression, scientific computing, and neural networks. Accumulation, which involves summing a dataset to obtain a single result, is crucial for these tasks. Due to hardware constraints, large vectors or matrices often cannot be fully stored in memory and must be read sequentially, one item per clock cycle. For high-speed inputs, such as rapidly arriving floating-point numbers, pipelined adders are necessary to maintain performance. However, pipelining introduces multiple intermediate sums and requires delays between back-to-back datasets unless their processing is overlapped. In this paper, we present JugglePAC, a novel accumulation circuit designed to address these challenges. JugglePAC operates quickly, is area-efficient, and features a fully pipelined design. It effectively manages back-to-back variable-length datasets while consistently producing results in the correct input order. Compared to the state-of-the-art, JugglePAC achieves higher throughput and reduces area complexity, offering significant improvements in performance and efficiency.
Online POMDP Planning with Anytime Deterministic Optimality Guarantees
Venue: arXiv cs.AI 2025
Year: 2025

Decision-making under uncertainty is a critical aspect of many practical autonomous systems due to incomplete information. Partially Observable Markov Decision Processes (POMDPs) offer a mathematically principled framework for formulating decision-making problems under such conditions. However, finding an optimal solution for a POMDP is generally intractable. In recent years, there has been a significant progress of scaling approximate solvers from small to moderately sized problems, using online tree search solvers. Often, such approximate solvers are limited to probabilistic or asymptotic guarantees towards the optimal solution. In this paper, we derive a deterministic relationship for discrete POMDPs between an approximated and the optimal solution. We show that at any time, we can derive bounds that relate between the existing solution and the optimal one. We show that our derivations provide an avenue for a new set of algorithms and can be attached to existing algorithms that have a certain structure to provide them with deterministic guarantees with marginal computational overhead. In return, not only do we certify the solution quality, but we demonstrate that making a decision based on the deterministic guarantee may result in superior performance compared to the original algorithm without the deterministic certification.
Parameterized Model-checking of Discrete-Timed Networks and Symmetric-Broadcast Systems
Venue: arXiv cs.LO 2025
Year: 2025

We study the complexity of the model-checking problem for parameterized discrete-timed systems with arbitrarily many anonymous and identical processes, with and without a distinguished "controller", and communicating via synchronous rendezvous. Our framework extends the seminal work from German and Sistla on untimed systems by adding discrete-time clocks to processes. For the case without a controller, we show that the systems can be efficiently simulated -- and vice versa -- by systems of untimed processes that communicate via rendezvous and symmetric broadcast, which we call "RB-systems". Symmetric broadcast is a novel communication primitive that allows all processes to synchronize at once; however, it does not distinguish between sending and receiving processes. We show that the parameterized model-checking problem for safety specifications is pspace-complete, and for liveness specifications it is decidable in exptime. The latter result is proved using automata theory, rational linear programming, and geometric reasoning for solving certain reachability questions in a new variant of vector addition systems called "vector rendezvous systems". We believe these proof techniques are of independent interest and will be useful in solving related problems. For the case with a controller, we show that the parameterized model-checking problems for RB-systems and systems with asymmetric broadcast as a primitive are inter-reducible. This allows us to prove that for discrete timed-networks with a controller the parameterized model-checking problem is undecidable for liveness specifications. Our work exploits the intimate connection between parameterized discrete-timed systems and systems of processes communicating via broadcast, providing a rare and surprising decidability result for liveness properties of parameterized timed-systems, as well as extend work from untimed systems to timed systems.
zkFL: Zero-Knowledge Proof-based Gradient Aggregation for Federated Learning
Venue: arXiv cs.AI 2025
Year: 2025

Federated learning (FL) is a machine learning paradigm, which enables multiple and decentralized clients to collaboratively train a model under the orchestration of a central aggregator. FL can be a scalable machine learning solution in big data scenarios. Traditional FL relies on the trust assumption of the central aggregator, which forms cohorts of clients honestly. However, a malicious aggregator, in reality, could abandon and replace the client's training models, or insert fake clients, to manipulate the final training results. In this work, we introduce zkFL, which leverages zero-knowledge proofs to tackle the issue of a malicious aggregator during the training model aggregation process. To guarantee the correct aggregation results, the aggregator provides a proof per round, demonstrating to the clients that the aggregator executes the intended behavior faithfully. To further reduce the verification cost of clients, we use blockchain to handle the proof in a zero-knowledge way, where miners (i.e., the participants validating and maintaining the blockchain data) can verify the proof without knowing the clients' local and aggregated models. The theoretical analysis and empirical results show that zkFL achieves better security and privacy than traditional FL, without modifying the underlying FL network structure or heavily compromising the training speed.
Understanding Pan-Sharpening via Generalized Inverse
Venue: arXiv cs.LG 2025
Year: 2025

Pan-sharpening algorithms utilize a panchromatic image and a multispectral image to generate a high spatial and high spectral image. However, the optimizations of the algorithms are designed with different standards. We employ a simple matrix equation to describe the Pan-sharpening problem. The conditions for the existence of a solution and the acquisition of spectral and spatial resolution are discussed. A down-sampling enhancement method is introduced to improve the estimation of spatial and spectral down-sample matrices. Using generalized inverse theory, we discovered two kinds of solution spaces of generalized inverse matrix formulations, which correspond to the two prominent classes of Pan-sharpening methods: component substitution and multi-resolution analysis. Specifically, the Gram-Schmidt adaptive method is demonstrated to align with the generalized inverse matrix formulation of component substitution. A model prior of the generalized inverse matrix of the spectral function is rendered. Theoretical errors are analyzed. The diffusion prior is naturally embedded with the help of general solution spaces of the generalized inverse form, enabling the acquisition of refined Pan-sharpening results. Extensive experiments, including comparative, synthetic, real-data ablation and diffusion-related tests are conducted. The proposed methods produce qualitatively sharper and superior results in both synthetic and real experiments. The down-sampling enhancement method demonstrates quantitatively and qualitatively better outcomes in real-data experiments. The diffusion prior can significantly improve the performance of our methods across almost all evaluation measures. The generalized inverse matrix theory helps deepen the understanding of Pan-sharpening mechanisms.
Finding coherent node groups in directed graphs
Venue: arXiv cs.SI 2025
Year: 2025

Grouping the nodes of a graph into clusters is a standard technique for studying networks. We study a problem where we are given a directed network and are asked to partition the graph into a sequence of coherent groups. We assume that nodes in the network have features, and we measure the group coherence by comparing these features. Furthermore, we incorporate the cross edges by penalizing the forward cross edges and backward cross edges with different weights. If the weights are set to 0, then the problem is equivalent to clustering. However, if we penalize the backward edges, the order of discovered groups matters, and we can view our problem as a generalization of a classic segmentation problem. We consider a common iterative approach where we solve the groups given the centroids, and then find the centroids given the groups. We show that, unlike in clustering, the first subproblem is NP-hard. However, we show that we can solve the subproblem exactly if the underlying graph is a tree or if the number of groups is 2. For a general case, we propose an approximation algorithm based on linear programming. We propose 3 additional heuristics: (1) optimizing each pair of groups separately while keeping the remaining groups intact, (2) computing a spanning tree and then optimizing using only the edges in that, and (3) a greedy search moving nodes between the groups while optimizing the overall loss. We demonstrate with our experiments that the algorithms are practical and yield interpretable results.
GRAPES: Learning to Sample Graphs for Scalable Graph Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

Graph neural networks (GNNs) learn to represent nodes by aggregating information from their neighbors. As GNNs increase in depth, their receptive field grows exponentially, leading to high memory costs. Several existing methods address this by sampling a small subset of nodes, scaling GNNs to much larger graphs. These methods are primarily evaluated on homophilous graphs, where neighboring nodes often share the same label. However, most of these methods rely on static heuristics that may not generalize across different graphs or tasks. We argue that the sampling method should be adaptive, adjusting to the complex structural properties of each graph. To this end, we introduce GRAPES, an adaptive sampling method that learns to identify the set of nodes crucial for training a GNN. GRAPES trains a second GNN to predict node sampling probabilities by optimizing the downstream task objective. We evaluate GRAPES on various node classification benchmarks, involving homophilous as well as heterophilous graphs. We demonstrate GRAPES' effectiveness in accuracy and scalability, particularly in multi-label heterophilous graphs. Unlike other sampling methods, GRAPES maintains high accuracy even with smaller sample sizes and, therefore, can scale to massive graphs. Our code is publicly available at https://github.com/dfdazac/grapes.
Divide, Conquer and Verify: Improving Symbolic Execution Performance
Venue: arXiv cs.CR 2025
Year: 2025

Symbolic Execution is a formal method that can be used to verify the behavior of computer programs and detect software vulnerabilities. Compared to other testing methods such as fuzzing, Symbolic Execution has the advantage of providing formal guarantees about the program. However, despite advances in performance in recent years, Symbolic Execution is too slow to be applied to real-world software. This is primarily caused by the \emph{path explosion problem} as well as by the computational complexity of SMT solving. In this paper, we present a divide-and-conquer approach for symbolic execution by executing individual slices and later combining the side effects. This way, the overall problem size is kept small, reducing the impact of computational complexity on large problems.
CLEVRER-Humans: Describing Physical and Causal Events the Human Way
Venue: arXiv cs.AI 2025
Year: 2025

Building machines that can reason about physical events and their causal relationships is crucial for flexible interaction with the physical world. However, most existing physical and causal reasoning benchmarks are exclusively based on synthetically generated events and synthetic natural language descriptions of causal relationships. This design brings up two issues. First, there is a lack of diversity in both event types and natural language descriptions; second, causal relationships based on manually-defined heuristics are different from human judgments. To address both shortcomings, we present the CLEVRER-Humans benchmark, a video reasoning dataset for causal judgment of physical events with human labels. We employ two techniques to improve data collection efficiency: first, a novel iterative event cloze task to elicit a new representation of events in videos, which we term Causal Event Graphs (CEGs); second, a data augmentation technique based on neural language generative models. We convert the collected CEGs into questions and answers to be consistent with prior work. Finally, we study a collection of baseline approaches for CLEVRER-Humans question-answering, highlighting the great challenges set forth by our benchmark.
3D POLYLLA: Polyhedral meshing algorithm based on terminal-edge regions and terminal-face regions
Venue: arXiv cs.CG 2025
Year: 2025

Polylla is a polygonal mesh algorithm that generates meshes with arbitrarily shaped polygons using the concept of terminal-edge regions. Until now, Polylla has been limited to 2D meshes, but in this work, we extend Polylla to 3D volumetric meshes. We present two versions of Polylla 3D. The first version generates terminal-edge regions, converts them into polyhedra, and repairs polyhedra that are joined by only an edge. This version differs from the original Polylla algorithm in that it does not have the same phases as the 2D version. In the second version, we define two new concepts: longest-face propagation path and terminal-face regions. We use these concepts to create an almost direct extension of the 2D Polylla mesh with the same three phases: label phase, traversal phase, and repair phase.
LumiNet: Perception-Driven Knowledge Distillation via Statistical Logit Calibration
Venue: arXiv cs.CV 2025
Year: 2025

In the knowledge distillation literature, feature-based methods have dominated due to their ability to effectively tap into extensive teacher models. In contrast, logit-based approaches, which aim to distill "dark knowledge" from teachers, typically exhibit inferior performance compared to feature-based methods. To bridge this gap, we present LumiNet, a novel knowledge distillation algorithm designed to enhance logit-based distillation. We introduce the concept of "perception", aiming to calibrate logits based on the model's representation capability. This concept addresses overconfidence issues in the logit-based distillation method while also introducing a novel method to distill knowledge from the teacher. It reconstructs the logits of a sample/instances by considering relationships with other samples in the batch. LumiNet excels on benchmarks like CIFAR-100, ImageNet, and MSCOCO, outperforming the leading feature-based methods, e.g., compared to KD with ResNet18 and MobileNetV2 on ImageNet, it shows improvements of 1.5% and 2.05%, respectively. Codes are available at https://github.com/ismail31416/LumiNet.
Break-Resilient Codes
Venue: arXiv cs.IT 2025
Year: 2025

We investigate the problem of encoding data into an $(n, t)$-break-resilient code ($(n, t)$-BRC), i.e., a collections of sequences of length~$n$ from which the original data can be reconstructed even if they are adversarially broken at up to~$t$ arbitrary positions. We establish lower bounds on the redundancy of any $(n, t)$-BRC and present code constructions that meet these bounds up to asymptotically negligible terms. Interestingly, this problem shares similarities with the recently studied torn paper channel, which has emerged in the context of DNA data storage.
On a Hierarchy of Spectral Invariants for Graphs
Venue: arXiv cs.CC 2025
Year: 2025

We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto eigenspaces of the adjacency matrix. We provide a purely combinatorial characterization of this hierarchy in terms of the walk counts. This allows us to give a complete answer to Fürer's question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison to the 2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan and Seppelt (SODA 2023). As another application of the characterization, we prove that almost all graphs are determined up to isomorphism in terms of the spectrum and the angles, which is of interest in view of the long-standing open problem whether almost all graphs are determined by their eigenvalues alone. Finally, we describe the exact relationship between the hierarchy and the Weisfeiler-Leman algorithms for small dimensions, as also some other important spectral characteristics of a graph such as the generalized and the main spectra.
ReactionTeam: Teaming Experts for Divergent Thinking Beyond Typical Reaction Patterns
Venue: arXiv cs.LG 2025
Year: 2025

Reaction prediction, a critical task in synthetic chemistry, is to predict the outcome of a reaction based on given reactants. Generative models like Transformer have typically been employed to predict the reaction product. However, these likelihood-maximization models overlooked the inherent stochastic nature of chemical reactions, such as the multiple ways electrons can be redistributed among atoms during the reaction process. In scenarios where similar reactants could follow different electron redistribution patterns, these models typically predict the most common outcomes, neglecting less frequent but potentially crucial reaction patterns. These overlooked patterns, though rare, can lead to innovative methods for designing synthetic routes and significantly advance synthesis techniques. To address these limitations, we build a team of expert models to capture diverse plausible reaction outcomes for the same reactants, mimicking the divergent thinking of chemists. The proposed framework, ReactionTeam, is composed of specialized expert models, each trained to capture a distinct type of electron redistribution pattern in reaction, and a ranking expert that evaluates and orders the generated predictions. Experimental results across two widely used datasets and different data settings demonstrate that our proposed method achieves significantly better performance compared to existing state-of-the-art approaches.