OpenRaiser/Intern-Atlas huggingface dataset:
The Autonomy-Alignment Problem in Open-Ended Learning Robots: Formalising the Purpose Framework
Venue: arXiv cs.RO 2025
Year: 2025

The rapid advancement of artificial intelligence is enabling the development of increasingly autonomous robots capable of operating beyond engineered factory settings and into the unstructured environments of human life. This shift raises a critical autonomy-alignment problem: how to ensure that a robot's autonomous learning focuses on acquiring knowledge and behaviours that serve human practical objectives while remaining aligned with broader human values (e.g., safety and ethics). This problem remains largely underexplored and lacks a unifying conceptual and formal framework. Here, we address one of its most challenging instances of the problem: open-ended learning (OEL) robots, which autonomously acquire new knowledge and skills through interaction with the environment, guided by intrinsic motivations and self-generated goals. We propose a computational framework, introduced qualitatively and then formalised, to guide the design of OEL architectures that balance autonomy with human control. At its core is the novel concept of purpose, which specifies what humans (designers or users) want the robot to learn, do, or avoid, independently of specific task domains. The framework decomposes the autonomy-alignment problem into four tractable sub-problems: the alignment of robot purposes (hardwired or learnt) with human purposes; the arbitration between multiple purposes; the grounding of abstract purposes into domain-specific goals; and the acquisition of competence to achieve those goals. The framework supports formal definitions of alignment across multiple cases and proofs of necessary and sufficient conditions under which alignment holds. Illustrative hypothetical scenarios showcase the applicability of the framework for guiding the development of purpose-aligned autonomous robots.
Eight-Partitioning Points in 3D, and Efficiently Too
Venue: arXiv cs.CG 2025
Year: 2025

An {\em eight-partition} of a finite set of points (respectively, of a continuous mass distribution) in $\mathbb{R}^3$ consists of three planes that divide the space into $8$ octants, such that each open octant contains at most $1/8$ of the points (respectively, of the mass). In 1966, Hadwiger showed that any mass distribution in $\mathbb{R}^3$ admits an eight-partition; moreover, one can prescribe the normal direction of one of the three planes. The analogous result for finite point sets follows by a standard limit argument. We prove the following variant of this result: Any mass distribution (or point set) in $\mathbb{R}^3$ admits an eight-partition for which the intersection of two of the planes is a line with a prescribed direction. Moreover, we present an efficient algorithm for calculating an eight-partition of a set of $n$ points in~$\mathbb{R}^3$ (with prescribed normal direction of one of the planes) in time $O^{*}(n^{7/3})$.
Space Complexity of Euclidean Clustering
Venue: arXiv cs.CG 2025
Year: 2025

The $(k, z)$-Clustering problem in Euclidean space $\mathbb{R}^d$ has been extensively studied. Given the scale of data involved, compression methods for the Euclidean $(k, z)$-Clustering problem, such as data compression and dimension reduction, have received significant attention in the literature. However, the space complexity of the clustering problem, specifically, the number of bits required to compress the cost function within a multiplicative error $\varepsilon$, remains unclear in existing literature. This paper initiates the study of space complexity for Euclidean $(k, z)$-Clustering and offers both upper and lower bounds. Our space bounds are nearly tight when $k$ is constant, indicating that storing a coreset, a well-known data compression approach, serves as the optimal compression scheme. Furthermore, our lower bound result for $(k, z)$-Clustering establishes a tight space bound of $Θ( n d )$ for terminal embedding, where $n$ represents the dataset size. Our technical approach leverages new geometric insights for principal angles and discrepancy methods, which may hold independent interest.
Two-Phase Channel Estimation for RIS-Assisted THz Systems with Beam Split
Venue: arXiv cs.IT 2025
Year: 2025

Reconfigurable intelligent surface (RIS)-assisted terahertz (THz) communication is emerging as a key technology to support ultra-high data rates in future sixth-generation networks. However, the acquisition of accurate channel state information (CSI) in such systems is challenging due to the passive nature of RIS and the hybrid beamforming architecture typically employed in THz systems. To address these challenges, we propose a novel low-complexity two-phase channel estimation scheme for RIS-assisted THz systems with beam split effect. In the proposed scheme, we first estimate the full CSI over a small subset of subcarriers, then extract angular information at both the base station and RIS. Subsequently, we recover the full CSI across remaining subcarriers by determining the corresponding spatial directions and angle-excluded coefficients. Theoretical analysis and simulation results demonstrate that the proposed method achieves superior performance in terms of normalized mean-square error while significantly reducing computational complexity compared to existing algorithms.
Enhancing Vision-Language Pre-training with Rich Supervisions
Venue: arXiv cs.CV 2025
Year: 2025

We propose Strongly Supervised pre-training with ScreenShots (S4) - a novel pre-training paradigm for Vision-Language Models using data from large-scale web screenshot rendering. Using web screenshots unlocks a treasure trove of visual and textual cues that are not present in using image-text pairs. In S4, we leverage the inherent tree-structured hierarchy of HTML elements and the spatial localization to carefully design 10 pre-training tasks with large scale annotated data. These tasks resemble downstream tasks across different domains and the annotations are cheap to obtain. We demonstrate that, compared to current screenshot pre-training objectives, our innovative pre-training method significantly enhances performance of image-to-text model in nine varied and popular downstream tasks - up to 76.1% improvements on Table Detection, and at least 1% on Widget Captioning.
D4C: Improving Negative Example Quality to Enhance Machine Abstract Reasoning Ability
Venue: arXiv cs.CV 2025
Year: 2025

This paper is dedicated to addressing the challenge of enhancing the abstract reasoning capabilities of AI, particularly for tasks involving complex human concepts. We introduce Lico-Net, a novel reasoning engine grounded in deep learning theory, which encodes the logical structure of Raven's Progressive Matrices (RPM) problems into probabilistic representations. Lico-Net excels in solving RPM tasks. Furthermore, we propose Lico-Net-Bongard, a tailored version of Lico-Net for the Bongard-Logo problem, which also achieves high reasoning accuracy through probabilistic representations. However, we observe a mismatch between the way deep learning algorithms and humans induce reasoning concepts, primarily attributed to the inadequate quality of negative samples. Improper configuration of negative samples can convey erroneous conceptual information to deep learning algorithms, thereby distorting their learning objectives. To address this issue, we propose two novel approaches: first, treating different sample points within reasoning problems as mutual negative samples to alter the existing negative sample structure in the data; second, designing a negative sample generator based on a step-wise linear attention mechanism to produce high-quality negative samples. Experimental results demonstrate that these methods significantly improve the performance of Lico-Net (-Bongard) and other baseline models on the RPM and Bongard-Logo datasets, as well as in the domain of foundational vision model processing, particularly when addressing the NICO dataset's distribution shift problem. Our findings emphasize the importance of improving negative sample quality for enhancing the abstract reasoning capabilities of deep learning algorithms and suggest that systems represent a promising direction for future research in this field.
Marginalize, Rather than Impute: Probabilistic Wind Power Forecasting with Incomplete Data
Venue: arXiv cs.LG 2025
Year: 2025

Machine learning methods are widely and successfully used for probabilistic wind power forecasting, yet the pervasive issue of missing values (e.g., due to sensor faults or communication outages) has received limited attention. The prevailing practice is impute-then-predict, but conditioning on point imputations biases parameter estimates and fails to propagate uncertainty from missing features. Our approach treats missing features and forecast targets uniformly: we learn a joint generative model of features and targets from incomplete data and, at operational deployment, condition on the observed features and marginalize the unobserved ones to produce forecasts. This imputation-free procedure avoids error introduced by imputation and preserves uncertainty aroused from missing features. In experiments, it improves forecast quality in terms of continuous ranked probability score relative to impute-then-predict baselines while incurring substantially lower computational cost than common alternatives.
A Survey on Adversarial Contention Resolution
Venue: arXiv cs.DC 2025
Year: 2025

Contention resolution addresses the challenge of coordinating access by multiple processes to a shared resource such as memory, disk storage, or a communication channel. Originally spurred by challenges in database systems and bus networks, contention resolution has endured as an important abstraction for resource sharing, despite decades of technological change. Here, we survey the literature on resolving worst-case contention, where the number of processes and the time at which each process may start seeking access to the resource is dictated by an adversary. We also highlight the evolution of contention resolution, where new concerns -- such as security, quality of service, and energy efficiency -- are motivated by modern systems. These efforts have yielded insights into the limits of randomized and deterministic approaches, as well as the impact of different model assumptions such as global clock synchronization, knowledge of the number of processors, feedback from access attempts, and attacks on the availability of the shared resource.
Empirical Game-Theoretic Analysis: A Survey
Venue: arXiv cs.GT 2025
Year: 2025

In the empirical approach to game-theoretic analysis (EGTA), the model of the game comes not from declarative representation, but is derived by interrogation of a procedural description of the game environment. The motivation for developing this approach was to enable game-theoretic reasoning about strategic situations too complex for analytic specification and solution. Since its introduction over twenty years ago, EGTA has been applied to a wide range of multiagent domains, from auctions and markets to recreational games to cyber-security. We survey the extensive methodology developed for EGTA over the years, organized by the elemental subproblems comprising the EGTA process. We describe key EGTA concepts and techniques, and the questions at the frontier of EGTA research. Recent advances in machine learning have accelerated progress in EGTA, and promise to significantly expand our capacities for reasoning about complex game situations.
To Spend or to Gain: Online Learning in Repeated Karma Auctions
Venue: arXiv cs.GT 2025
Year: 2025

Recent years have seen a surge of artificial currency-based mechanisms in contexts where monetary instruments are deemed unfair or inappropriate, e.g., in allocating food donations to food banks, course seats to students, and, more recently, even for traffic congestion management. Yet the applicability of these mechanisms remains limited in repeated auction settings, as it is challenging for users to learn how to bid an artificial currency that has no value outside the auctions. Indeed, users must jointly learn the value of the currency in addition to how to spend it optimally. Moreover, in the prominent class of karma mechanisms, in which artificial karma payments are redistributed to users at each time step, users do not only spend karma to obtain public resources but also gain karma for yielding them. For this novel class of karma auctions, we propose an adaptive karma pacing strategy that learns to bid optimally, and show that this strategy a) is asymptotically optimal for a single user bidding against competing bids drawn from a stationary distribution; b) leads to convergent learning dynamics when all users adopt it; and c) constitutes an approximate Nash equilibrium as the number of users grows. Our results require a novel analysis in comparison to adaptive pacing strategies in monetary auctions, since we depart from the classical assumption that the currency has known value outside the auctions, and consider that the currency is both spent and gained through the redistribution of payments.
A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges
Venue: arXiv cs.LG 2025
Year: 2025

Graph-structured data exhibits universality and widespread applicability across diverse domains, such as social network analysis, biochemistry, financial fraud detection, and network security. Significant strides have been made in leveraging Graph Neural Networks (GNNs) to achieve remarkable success in these areas. However, in real-world scenarios, the training environment for models is often far from ideal, leading to substantial performance degradation of GNN models due to various unfavorable factors, including imbalance in data distribution, the presence of noise in erroneous data, privacy protection of sensitive information, and generalization capability for out-of-distribution (OOD) scenarios. To tackle these issues, substantial efforts have been devoted to improving the performance of GNN models in practical real-world scenarios, as well as enhancing their reliability and robustness. In this paper, we present a comprehensive survey that systematically reviews existing GNN models, focusing on solutions to the four mentioned real-world challenges including imbalance, noise, privacy, and OOD in practical scenarios that many existing reviews have not considered. Specifically, we first highlight the four key challenges faced by existing GNNs, paving the way for our exploration of real-world GNN models. Subsequently, we provide detailed discussions on these four aspects, dissecting how these solutions contribute to enhancing the reliability and robustness of GNN models. Last but not least, we outline promising directions and offer future perspectives in the field.
T-TAME: Trainable Attention Mechanism for Explaining Convolutional Networks and Vision Transformers
Venue: arXiv cs.CV 2025
Year: 2025

The development and adoption of Vision Transformers and other deep-learning architectures for image classification tasks has been rapid. However, the "black box" nature of neural networks is a barrier to adoption in applications where explainability is essential. While some techniques for generating explanations have been proposed, primarily for Convolutional Neural Networks, adapting such techniques to the new paradigm of Vision Transformers is non-trivial. This paper presents T-TAME, Transformer-compatible Trainable Attention Mechanism for Explanations, a general methodology for explaining deep neural networks used in image classification tasks. The proposed architecture and training technique can be easily applied to any convolutional or Vision Transformer-like neural network, using a streamlined training approach. After training, explanation maps can be computed in a single forward pass; these explanation maps are comparable to or outperform the outputs of computationally expensive perturbation-based explainability techniques, achieving SOTA performance. We apply T-TAME to three popular deep learning classifier architectures, VGG-16, ResNet-50, and ViT-B-16, trained on the ImageNet dataset, and we demonstrate improvements over existing state-of-the-art explainability methods. A detailed analysis of the results and an ablation study provide insights into how the T-TAME design choices affect the quality of the generated explanation maps.
Near-Optimal Algorithm for Directed Expander Decompositions
Venue: arXiv cs.DS 2025
Year: 2025

In this work, we present the first algorithm to compute expander decompositions in an m-edge directed graph with near-optimal time Õ(m). Further, our algorithm can maintain such a decomposition in a dynamic graph and again obtains near-optimal update times. Our result improves over previous algorithms of Bernstein-Probst Gutenberg-Saranurak (FOCS 2020), Hua-Kyng-Probst Gutenberg-Wu (SODA 2023) that only obtained algorithms optimal up to subpolynomial factors. In order to obtain our new algorithm, we present a new push-pull-relabel flow framework that generalizes the classic push-relabel flow algorithm Goldberg-Tarjan (JACM 1988) which was later dynamized for computing expander decompositions in undirected graphs Henzinger-Rao-Wang (SIAM J. Comput. 2020), Saranurak-Wang (SODA 2019). We then show that the flow problems formulated in recent work Hua-Kyng-Probst Gutenberg-Wu (SODA 2023) to decompose directed graphs can be solved much more efficiently in the push-pull-relabel flow framework. Recently, our algorithm has already been employed to obtain the currently fastest algorithm to compute min-cost flows Van den Brand-Chen-Kyng-Liu-Probst Gutenberg-Sachdeva (FOCS 2024). We further believe that our algorithm can be used to speed-up and simplify recent breakthroughs in combinatorial graph algorithms towards fast maximum flow algorithms Chuzhoy-Khanna (SODA 2024), Chuzhoy-Khanna (STOC 2024), Bernstein-Blikstad-Saranurak-Tu (FOCS 2024).
Time-Aware Projections: Truly Node-Private Graph Statistics under Continual Observation
Venue: arXiv cs.DS 2025
Year: 2025

We describe the first algorithms that satisfy the standard notion of node-differential privacy in the continual release setting (i.e., without an assumed promise on input streams). Previous work addresses node-private continual release by assuming an unenforced promise on the maximum degree in a graph, but leaves open whether such a bound can be verified or enforced privately. Our algorithms are accurate on sparse graphs, for several fundamental graph problems: counting edges, triangles, other subgraphs, and connected components; and releasing degree histograms. Our unconditionally private algorithms generally have optimal error, up to polylogarithmic factors and lower-order terms. We provide general transformations that take a base algorithm for the continual release setting, which need only be private for streams satisfying a promised degree bound, and produce an algorithm that is unconditionally private yet mimics the base algorithm when the stream meets the degree bound (and adds only linear overhead to the time and space complexity of the base algorithm). To do so, we design new projection algorithms for graph streams, based on the batch-model techniques of Day et al. 2016 and Blocki et al. 2013, which modify the stream to limit its degree. Our main technical innovation is to show that the projections are stable -- meaning that similar input graphs have similar projections -- when the input stream satisfies a privately testable safety condition. Our transformation then follows a novel online variant of the Propose-Test-Release framework (Dwork and Lei, 2009), privately testing the safety condition before releasing output at each step.
TS-RSR: A provably efficient approach for batch Bayesian Optimization
Venue: arXiv cs.LG 2025
Year: 2025

This paper presents a new approach for batch Bayesian Optimization (BO) called Thompson Sampling-Regret to Sigma Ratio directed sampling (TS-RSR), where we sample a new batch of actions by minimizing a Thompson Sampling approximation of a regret to uncertainty ratio. Our sampling objective is able to coordinate the actions chosen in each batch in a way that minimizes redundancy between points whilst focusing on points with high predictive means or high uncertainty. Theoretically, we provide rigorous convergence guarantees on our algorithm's regret, and numerically, we demonstrate that our method attains state-of-the-art performance on a range of challenging synthetic and realistic test functions, where it outperforms several competitive benchmark batch BO algorithms.
Secure Information Embedding in Forensic 3D Fingerprinting
Venue: arXiv cs.CR 2025
Year: 2025

Printer fingerprinting techniques have long played a critical role in forensic applications, including the tracking of counterfeiters and the safeguarding of confidential information. The rise of 3D printing technology introduces significant risks to public safety, enabling individuals with internet access and consumer-grade 3D printers to produce untraceable firearms, counterfeit products, and more. This growing threat calls for a better mechanism to track the production of 3D-printed parts. Inspired by the success of fingerprinting on traditional 2D printers, we introduce SIDE (\textbf{S}ecure \textbf{I}nformation Embe\textbf{D}ding and \textbf{E}xtraction), a novel fingerprinting framework tailored for 3D printing. SIDE addresses the adversarial challenges of 3D print forensics by offering both secure information embedding and extraction. First, through novel coding-theoretic techniques, SIDE is both~\emph{break-resilient} and~\emph{loss-tolerant}, enabling fingerprint recovery even if the adversary breaks the print into fragments and conceals a portion of them. Second, SIDE further leverages Trusted Execution Environments (TEE) to secure the fingerprint embedding process.
From Chain to Tree: Refining Chain-like Rules into Tree-like Rules on Knowledge Graphs
Venue: arXiv cs.AI 2025
Year: 2025

With good explanatory power and controllability, rule-based methods play an important role in many tasks such as knowledge reasoning and decision support. However, existing studies primarily focused on learning chain-like rules, which limit their semantic expressions and accurate prediction abilities. As a result, chain-like rules usually fire on the incorrect grounding values, producing inaccurate or even erroneous reasoning results. In this paper, we propose the concept of tree-like rules on knowledge graphs to expand the application scope and improve the reasoning ability of rule-based methods. Meanwhile, we propose an effective framework for refining chain-like rules into tree-like rules. Experimental comparisons on four public datasets show that the proposed framework can easily adapt to other chain-like rule induction methods and the refined tree-like rules consistently achieve better performances than chain-like rules on link prediction. The data and code of this paper can be available at https://anonymous.4open.science/r/tree-rule-E3CD/.