OpenRaiser/Intern-Atlas huggingface dataset:
Homomorphisms of (n,m)-graphs with respect to generalised switch
Venue: arXiv cs.DM 2025
Year: 2025

The study of homomorphisms of $(n,m)$-graphs, that is, adjacency preserving vertex mappings of graphs with $n$ types of arcs and $m$ types of edges was initiated by Nešetřil and Raspaud in 2000. Later, some attempts were made to generalize the switch operation that is popularly used in the study of signed graphs, and study its effect on the above mentioned homomorphism. In this article, we too provide a generalization of the switch operation on $(n,m)$-graphs, which to the best of our knowledge, encapsulates all the previously known generalizations as special cases. We approach the study of homomorphisms with respect to the switch operation axiomatically. We prove some fundamental results that are essential tools in the further study of this topic. In the process of proving the fundamental results, we have provided yet another solution to an open problem posed by Klostermeyer and MacGillivray in 2004. We also prove the existence of a categorical product for $(n,m)$-graphs with respect to a particular class of generalized switch which implicitly uses category theory. This is a counter intuitive solution as the number of vertices in the Categorical product of two $(n,m)$-graphs on $p$ and $q$ vertices has a multiple of $pq$ many vertices, where the multiple depends on the switch. This solves an open question asked by Brewster in the PEPS 2012 workshop as a corollary. We also provide a way to calculate the product explicitly, and prove general properties of the product. We define the analog of chromatic number for $(n,m)$-graphs with respect to generalized switch and explore the interrelations between chromatic numbers with respect to different switch operations. We find the value of this chromatic number for the family of forests using group theoretic notions.
LatentGAN Autoencoder: Learning Disentangled Latent Distribution
Venue: arXiv cs.CV 2025
Year: 2025

In autoencoder, the encoder generally approximates the latent distribution over the dataset, and the decoder generates samples using this learned latent distribution. There is very little control over the latent vector as using the random latent vector for generation will lead to trivial outputs. This work tries to address this issue by using the LatentGAN generator to directly learn to approximate the latent distribution of the autoencoder and show meaningful results on MNIST, 3D Chair, and CelebA datasets, an additional information-theoretic constrain is used which successfully learns to control autoencoder latent distribution. With this, our model also achieves an error rate of 2.38 on MNIST unsupervised image classification, which is better as compared to InfoGAN and AAE.
DRAGON (Differentiable Graph Execution) : A suite of Hardware Simulation and Optimization tools for Modern AI/Non-AI Workloads
Venue: arXiv cs.AR 2025
Year: 2025

We introduce DRAGON, a fast and explainable hardware simulation and optimization toolchain that enables hardware architects to simulate hardware designs, and to optimize hardware designs to efficiently execute workloads. The DRAGON toolchain provides the following tools: Hardware Model Generator (DGen), Hardware Simulator (DSim) and Hardware Optimizer (DOpt). DSim provides the simulation of running algorithms (represented as data-flow graphs) on hardware described. DGen describes the hardware in detail, with user input architectures/technology (represented in a custom description language). A novel methodology of gradient descent from the simulation allows us optimize the hardware model (giving the directions for improvements in technology parameters and design parameters), provided by Dopt. DRAGON framework (DSim) is much faster than previously avaible works for simulation, which is possible through performance-first code writing practices, mathematical formulas for common computing operations to avoid cycle-accurate simulation steps, efficient algorithms for mapping, and data-structure representations for hardware state. DRAGON framework (Dopt) generates performance optimized architectures for both AI and Non-AI Workloads, and provides technology improvement directions for 100x-1000x better future computing systems.
Finding Pareto Trade-offs in Fair and Accurate Detection of Toxic Speech
Venue: arXiv cs.CL 2025
Year: 2025

Optimizing NLP models for fairness poses many challenges. Lack of differentiable fairness measures prevents gradient-based loss training or requires surrogate losses that diverge from the true metric of interest. In addition, competing objectives (e.g., accuracy vs. fairness) often require making trade-offs based on stakeholder preferences, but stakeholders may not know their preferences before seeing system performance under different trade-off settings. To address these challenges, we begin by formulating a differentiable version of a popular fairness measure, Accuracy Parity, to provide balanced accuracy across demographic groups. Next, we show how model-agnostic, HyperNetwork optimization can efficiently train arbitrary NLP model architectures to learn Pareto-optimal trade-offs between competing metrics. Focusing on the task of toxic language detection, we show the generality and efficacy of our methods across two datasets, three neural architectures, and three fairness losses.
Hierarchical Locality Sensitive Hashing for Structured Data: A Survey
Venue: arXiv cs.DS 2025
Year: 2025

Data similarity (or distance) computation is a fundamental research topic which fosters a variety of similarity-based machine learning and data mining applications. In big data analytics, it is impractical to compute the exact similarity of data instances due to high computational cost. To this end, the Locality Sensitive Hashing (LSH) technique has been proposed to provide accurate estimators for various similarity measures between sets or vectors in an efficient manner without the learning process. Structured data (e.g., sequences, trees and graphs), which are composed of elements and relations between the elements, are commonly seen in the real world, but the traditional LSH algorithms cannot preserve the structure information represented as relations between elements. In order to conquer the issue, researchers have been devoted to the family of the hierarchical LSH algorithms. In this paper, we explore the present progress of the research into hierarchical LSH from the following perspectives: 1) Data structures, where we review various hierarchical LSH algorithms for three typical data structures and uncover their inherent connections; 2) Applications, where we review the hierarchical LSH algorithms in multiple application scenarios; 3) Challenges, where we discuss some potential challenges as future directions.
Tightness without Counterexamples: A New Approach and New Results for Prophet Inequalities
Venue: arXiv cs.GT 2025
Year: 2025

Prophet inequalities consist of many beautiful statements that establish tight performance ratios between online and offline allocation algorithms. Typically, tightness is established by constructing an algorithmic guarantee and a worst-case instance separately, whose bounds match as a result of some "ingenuity". In this paper, we instead formulate the construction of the worst-case instance as an optimization problem, which directly finds the tight ratio without needing to construct two bounds separately. Our analysis of this complex optimization problem involves identifying structure in a new "Type Coverage" dual problem. It can be seen as akin to the celebrated Magician and OCRS (Online Contention Resolution Scheme) problems, except more general in that it can also provide tight ratios relative to the optimal offline allocation, whereas the earlier problems only establish tight ratios relative to the ex-ante relaxation of the offline problem. Through this analysis, our paper provides a unified framework that derives new prophet inequalities and recovers existing ones, with our principal results being two-fold. First, we show that the "oblivious" method of setting a static threshold due to Chawla et al. (2020), surprisingly, is best-possible among all static threshold algorithms, under any number $k$ of starting units. We emphasize that this result is derived without needing to explicitly find any counterexample instances. This implies the tightness of the asymptotic convergence rate of $1-O(\sqrt{\log k/k})$ for static threshold algorithms, which dates back to from Hajiaghayi et al. (2007). Turning to the IID setting, our second principal result is to use our framework to characterize the tight guarantee (of adaptive algorithms) under any number $k$ of selection slots and any fixed number of agents $n$.
Statistical Guarantees for Approximate Stationary Points of Shallow Neural Networks
Venue: arXiv cs.LG 2025
Year: 2025

Since statistical guarantees for neural networks are usually restricted to global optima of intricate objective functions, it is unclear whether these theories explain the performances of actual outputs of neural network pipelines. The goal of this paper is, therefore, to bring statistical theory closer to practice. We develop statistical guarantees for shallow linear neural networks that coincide up to logarithmic factors with the global optima but apply to stationary points and the points nearby. These results support the common notion that neural networks do not necessarily need to be optimized globally from a mathematical perspective. We then extend our statistical guarantees to shallow ReLU neural networks, assuming the first layer weight matrices are nearly identical for the stationary network and the target. More generally, despite being limited to shallow neural networks for now, our theories make an important step forward in describing the practical properties of neural networks in mathematical terms.
Fundamental Limits of Multiple-Access Integrated Sensing and Communication Systems
Venue: arXiv cs.IT 2025
Year: 2025

A state-dependent discrete memoryless multiple access channel is considered to model an integrated sensing and communication system, where two transmitters wish to convey messages to a receiver while simultaneously estimating the state parameter sequences through echo signals. In particular, the sensing state parameters are assumed to be correlated with the channel state. In this setup, improved inner and outer bounds for capacity-distortion region are derived. The inner bound is based on an achievable scheme that combines message cooperation and joint compression of past transmitted codewords and echo signals at each transmitter, resulting in unified cooperative communication and sensing. The outer bound is based on the ideas of dependence balance for communication rate, genie-aided state estimator and rate-limited constraints on sensing distortion. The proposed inner and outer bounds are proved to improve the state-of-the-art bounds. Finally, numerical examples are provided to demonstrate that our new inner and outer bounds strictly improve the existing results.
Are Metrics Enough? Guidelines for Communicating and Visualizing Predictive Models to Subject Matter Experts
Venue: arXiv cs.HC 2025
Year: 2025

Presenting a predictive model's performance is a communication bottleneck that threatens collaborations between data scientists and subject matter experts. Accuracy and error metrics alone fail to tell the whole story of a model - its risks, strengths, and limitations - making it difficult for subject matter experts to feel confident in their decision to use a model. As a result, models may fail in unexpected ways or go entirely unused, as subject matter experts disregard poorly presented models in favor of familiar, yet arguably substandard methods. In this paper, we describe an iterative study conducted with both subject matter experts and data scientists to understand the gaps in communication between these two groups. We find that, while the two groups share common goals of understanding the data and predictions of the model, friction can stem from unfamiliar terms, metrics, and visualizations - limiting the transfer of knowledge to SMEs and discouraging clarifying questions being asked during presentations. Based on our findings, we derive a set of communication guidelines that use visualization as a common medium for communicating the strengths and weaknesses of a model. We provide a demonstration of our guidelines in a regression modeling scenario and elicit feedback on their use from subject matter experts. From our demonstration, subject matter experts were more comfortable discussing a model's performance, more aware of the trade-offs for the presented model, and better equipped to assess the model's risks - ultimately informing and contextualizing the model's use beyond text and numbers.
Decomposition Strategies and Multi-shot ASP Solving for Job-shop Scheduling
Venue: arXiv cs.AI 2025
Year: 2025

The Job-shop Scheduling Problem (JSP) is a well-known and challenging combinatorial optimization problem in which tasks sharing a machine are to be arranged in a sequence such that encompassing jobs can be completed as early as possible. In this paper, we investigate problem decomposition into time windows whose operations can be successively scheduled and optimized by means of multi-shot Answer Set Programming (ASP) solving. From a computational perspective, decomposition aims to split highly complex scheduling tasks into better manageable subproblems with a balanced number of operations such that good-quality or even optimal partial solutions can be reliably found in a small fraction of runtime. We devise and investigate a variety of decomposition strategies in terms of the number and size of time windows as well as heuristics for choosing their operations. Moreover, we incorporate time window overlapping and compression techniques into the iterative scheduling process to counteract optimization limitations due to the restriction to window-wise partial schedules. Our experiments on different JSP benchmark sets show that successive optimization by multi-shot ASP solving leads to substantially better schedules within tight runtime limits than single-shot optimization on the full problem. In particular, we find that decomposing initial solutions obtained with proficient heuristic methods into time windows leads to improved solution quality.
A $(3+\varepsilon)$-Approximate Correlation Clustering Algorithm in Dynamic Streams
Venue: arXiv cs.DS 2025
Year: 2025

Grouping together similar elements in datasets is a common task in data mining and machine learning. In this paper, we study streaming algorithms for correlation clustering, where each pair of elements is labeled either similar or dissimilar. The task is to partition the elements and the objective is to minimize disagreements, that is, the number of dissimilar elements grouped together and similar elements that get separated. Our main contribution is a semi-streaming algorithm that achieves a $(3 + \varepsilon)$-approximation to the minimum number of disagreements using a single pass over the stream. In addition, the algorithm also works for dynamic streams. Our approach builds on the analysis of the PIVOT algorithm by Ailon, Charikar, and Newman [JACM'08] that obtains a $3$-approximation in the centralized setting. Our design allows us to sparsify the input graph by ignoring a large portion of the nodes and edges without a large extra cost as compared to the analysis of PIVOT. This sparsification makes our technique applicable in models such as semi-streaming, where sparse graphs can typically be handled much more efficiently. Our work improves on the approximation ratio of the recent single-pass $5$-approximation algorithm and on the number of passes of the recent $O(1/\varepsilon)$-pass $(3 + \varepsilon)$-approximation algorithm [Behnezhad, Charikar, Ma, Tan FOCS'22, SODA'23]. Our algorithm is also more robust and can be applied in dynamic streams. Furthermore, it is the first single pass $(3 + \varepsilon)$-approximation algorithm that uses polynomial post-processing time.
Persian Abstract Meaning Representation: Annotation Guidelines and Gold Standard Dataset
Venue: arXiv cs.CL 2025
Year: 2025

This paper introduces the Persian Abstract Meaning Representation (AMR) guidelines, a detailed guide for annotating Persian sentences with AMR, focusing on the necessary adaptations to fit Persian's unique syntactic structures. We discuss the development process of a Persian AMR gold standard dataset consisting of 1,562 sentences created following the guidelines. By examining the language specifications and nuances that distinguish AMR annotations of a low-resource language like Persian, we shed light on the challenges and limitations of developing a universal meaning representation framework. The guidelines and the dataset introduced in this study highlight such challenges, aiming to advance the field.
InDistill: Information flow-preserving knowledge distillation for model compression
Venue: arXiv cs.CV 2025
Year: 2025

In this paper, we introduce InDistill, a method that serves as a warmup stage for enhancing Knowledge Distillation (KD) effectiveness. InDistill focuses on transferring critical information flow paths from a heavyweight teacher to a lightweight student. This is achieved via a training scheme based on curriculum learning that considers the distillation difficulty of each layer and the critical learning periods when the information flow paths are established. This procedure can lead to a student model that is better prepared to learn from the teacher. To ensure the applicability of InDistill across a wide range of teacher-student pairs, we also incorporate a pruning operation when there is a discrepancy in the width of the teacher and student layers. This pruning operation reduces the width of the teacher's intermediate layers to match those of the student, allowing direct distillation without the need for an encoding stage. The proposed method is extensively evaluated using various pairs of teacher-student architectures on CIFAR-10, CIFAR-100, and ImageNet datasets demonstrating that preserving the information flow paths consistently increases the performance of the baseline KD approaches on both classification and retrieval settings. The code is available at https://github.com/gsarridis/InDistill.
Smart Grid: Cyber Attacks, Critical Defense Approaches, and Digital Twin
Venue: arXiv cs.CR 2025
Year: 2025

As a national critical infrastructure, the smart grid has attracted widespread attention for its cybersecurity issues. The development towards an intelligent, digital, and Internet-connected smart grid has attracted external adversaries for malicious activities. It is necessary to enhance its cybersecurity by both improving the existing defense approaches and introducing novel developed technologies to the smart grid context. As an emerging technology, digital twin (DT) is considered as an enabler for enhanced security. However, the practical implementation is quite challenging. This is due to the knowledge barriers among smart grid designers, security experts, and DT developers. Each single domain is a complicated system covering various components and technologies. As a result, works are needed to sort out relevant contents so that DT can be better embedded in the security architecture design of smart grid. In order to meet this demand, our paper covers the above three domains, i.e., smart grid, cybersecurity, and DT. Specifically, the paper i) introduces the background of the smart grid; ii) reviews external cyber attacks from attack incidents and attack methods; iii) introduces critical defense approaches in industrial cyber systems, which include device identification, vulnerability discovery, intrusion detection systems (IDSs), honeypots, attribution, and threat intelligence (TI); iv) reviews the relevant content of DT, including its basic concepts, applications in the smart grid, and how DT enhances the security. In the end, the paper puts forward our security considerations on the future development of DT-based smart grid. The survey is expected to help developers break knowledge barriers among smart grid, cybersecurity, and DT, and provide guidelines for future security design of DT-based smart grid.
Maximum Mean Discrepancy on Exponential Windows for Online Change Detection
Venue: arXiv cs.LG 2025
Year: 2025

Detecting changes is of fundamental importance when analyzing data streams and has many applications, e.g., in predictive maintenance, fraud detection, or medicine. A principled approach to detect changes is to compare the distributions of observations within the stream to each other via hypothesis testing. Maximum mean discrepancy (MMD), a (semi-)metric on the space of probability distributions, provides powerful non-parametric two-sample tests on kernel-enriched domains. In particular, MMD is able to detect any disparity between distributions under mild conditions. However, classical MMD estimators suffer from a quadratic runtime complexity, which renders their direct use for change detection in data streams impractical. In this article, we propose a new change detection algorithm, called Maximum Mean Discrepancy on Exponential Windows (MMDEW), that combines the benefits of MMD with an efficient computation based on exponential windows. We prove that MMDEW enjoys polylogarithmic runtime and logarithmic memory complexity and show empirically that it outperforms the state of the art on benchmark data streams.
Does DQN Learn?
Venue: arXiv cs.LG 2025
Year: 2025

A primary requirement for any reinforcement learning method is that it should produce policies that improve upon the initial guess. In this work, we show that the widely used Deep Q-Network (DQN) fails to satisfy this minimal criterion -- even when it gets to see all possible states and actions infinitely often (a condition under which tabular Q-learning is guaranteed to converge to the optimal Q-value function). Our specific contributions are twofold. First, we numerically show that DQN often returns a policy that performs worse than the initial one. Second, we offer a theoretical explanation for this phenomenon in linear DQN, a simplified version of DQN that uses linear function approximation in place of neural networks while retaining the other key components such as $ε$-greedy exploration, experience replay, and target network. Using tools from differential inclusion theory, we prove that the limit points of linear DQN correspond to fixed points of projected Bellman operators. Crucially, we show that these fixed points need not relate to optimal -- or even near-optimal -- policies, thus explaining linear DQN's sub-optimal behaviors. We also give a scenario where linear DQN always identifies the worst policy. Our work fills a longstanding gap in understanding the convergence behaviors of Q-learning with function approximation and $ε$-greedy exploration.
Evaluating the Efficiency of Regulation in Matching Markets with Distributional Disparities
Venue: arXiv cs.GT 2025
Year: 2025

Cap-based regulations are widely used to address distributional disparities in matching markets, but their efficiency relative to alternative instruments such as subsidies remains poorly understood. This paper develops a framework for evaluating policy interventions by incorporating regional constraints into a transferable utility matching model. We show that a policymaker with aggregate-level match data can implement a taxation policy that maximizes social welfare and outperforms any cap-based policy. Using newly collected data from the Japan Residency Matching Program, we estimate participant preferences and simulate counterfactual match outcomes under both cap-based and subsidy-based policies. The results reveal that the status quo cap-based regulation generates substantial efficiency losses, whereas small, targeted subsidies can achieve similar distributional goals with significantly higher social welfare.