OpenRaiser/Intern-Atlas huggingface dataset:
Minimum Stable Cut and Treewidth
Venue: arXiv cs.CC 2025
Year: 2025

A stable or locally-optimal cut of a graph is a cut whose weight cannot be increased by changing the side of a single vertex. In this paper we study Minimum Stable Cut, the problem of finding a stable cut of minimum weight. Since this problem is NP-hard, we study its complexity on graphs of low treewidth, low degree, or both. We begin by showing that the problem remains weakly NP-hard on severely restricted trees, so bounding treewidth alone cannot make it tractable. We match this hardness with a pseudo-polynomial DP algorithm solving the problem in time $(Δ\cdot W)^{O(tw)}n^{O(1)}$, where $tw$ is the treewidth, $Δ$ the maximum degree, and $W$ the maximum weight. On the other hand, bounding $Δ$ is also not enough, as the problem is NP-hard for unweighted graphs of bounded degree. We therefore parameterize Minimum Stable Cut by both $tw$ and $Δ$ and obtain an FPT algorithm running in time $2^{O(Δtw)}(n+\log W)^{O(1)}$. Our main result for the weighted problem is to provide a reduction showing that both aforementioned algorithms are essentially optimal, even if we replace treewidth by pathwidth: if there exists an algorithm running in $(nW)^{o(pw)}$ or $2^{o(Δpw)}(n+\log W)^{O(1)}$, then the ETH is false. Complementing this, we show that we can, however, obtain an FPT approximation scheme parameterized by treewidth, if we consider almost-stable solutions, that is, solutions where no single vertex can unilaterally increase the weight of its incident cut edges by more than a factor of $(1+\varepsilon)$. Motivated by these mostly negative results, we consider Unweighted Minimum Stable Cut. Here our results already imply a much faster exact algorithm running in time $Δ^{O(tw)}n^{O(1)}$. We show that this is also probably essentially optimal: an algorithm running in $n^{o(pw)}$ would contradict the ETH.
A C++17 Thread Pool for High-Performance Scientific Computing
Venue: arXiv cs.DC 2025
Year: 2025

We present a modern C++17-compatible thread pool implementation, built from scratch with high-performance scientific computing in mind. The thread pool is implemented as a single lightweight and self-contained class, and does not have any dependencies other than the C++17 standard library, thus allowing a great degree of portability. In particular, our implementation does not utilize any high-level multithreading APIs, and thus gives the programmer precise low-level control over the details of the parallelization, which permits more robust optimizations. The thread pool was extensively tested on both AMD and Intel CPUs with up to 40 cores and 80 threads.
A Constant-factor Approximation for Weighted Bond Cover
Venue: arXiv cs.DS 2025
Year: 2025

The Weighted $\mathcal{F}$-Vertex Deletion for a class ${\cal F}$ of graphs asks, weighted graph $G$, for a minimum weight vertex set $S$ such that $G-S\in{\cal F}.$ The case when ${\cal F}$ is minor-closed and excludes some graph as a minor has received particular attention but a constant-factor approximation remained elusive for Weighted $\mathcal{F}$-Vertex Deletion. Only three cases of minor-closed ${\cal F}$ are known to admit constant-factor approximations, namely Vertex Cover, Feedback Vertex Set and Diamond Hitting Set. We study the problem for the class ${\cal F}$ of $θ_c$-minor-free graphs, under the equivalent setting of the Weighted $c$-Bond Cover problem, and present a constant-factor approximation algorithm using the primal-dual method. For this, we leverage a structure theorem implicit in [Joret, Paul, Sau, Saurabh, and Thomassé, SIDMA'14] which states the following: any graph $G$ containing a $θ_c$-minor-model either contains a large two-terminal protrusion, or contains a constant-size $θ_c$-minor-model, or a collection of pairwise disjoint constant-sized connected sets that can be contracted simultaneously to yield a dense graph. In the first case, we tame the graph by replacing the protrusion with a special-purpose weighted gadget. For the second and third case, we provide a weighting scheme which guarantees a local approximation ratio. Besides making an important step in the quest of (dis)proving a constant-factor approximation for Weighted $\mathcal{F}$-Vertex Deletion, our result may be useful as a template for algorithms for other minor-closed families.
A Euclidean Distance Matrix Model for Convex Clustering
Venue: arXiv cs.DM 2025
Year: 2025

Clustering has been one of the most basic and essential problems in unsupervised learning due to various applications in many critical fields. The recently proposed sum-of-norms (SON) model by Pelckmans et al. (2005), Lindsten et al. (2011) and Hocking et al. (2011) has received a lot of attention. The advantage of the SON model is the theoretical guarantee in terms of perfect recovery, established by Sun et al. (2018). It also provides great opportunities for designing efficient algorithms for solving the SON model. The semismooth Newton based augmented Lagrangian method by Sun et al. (2018) has demonstrated its superior performance over the alternating direction method of multipliers (ADMM) and the alternating minimization algorithm (AMA). In this paper, we propose a Euclidean distance matrix model based on the SON model. An efficient majorization penalty algorithm is proposed to solve the resulting model. Extensive numerical experiments are conducted to demonstrate the efficiency of the proposed model and the majorization penalty algorithm.
Graph Neural Networks for Knowledge Enhanced Visual Representation of Paintings
Venue: arXiv cs.CV 2025
Year: 2025

We propose ArtSAGENet, a novel multimodal architecture that integrates Graph Neural Networks (GNNs) and Convolutional Neural Networks (CNNs), to jointly learn visual and semantic-based artistic representations. First, we illustrate the significant advantages of multi-task learning for fine art analysis and argue that it is conceptually a much more appropriate setting in the fine art domain than the single-task alternatives. We further demonstrate that several GNN architectures can outperform strong CNN baselines in a range of fine art analysis tasks, such as style classification, artist attribution, creation period estimation, and tag prediction, while training them requires an order of magnitude less computational time and only a small amount of labeled data. Finally, through extensive experimentation we show that our proposed ArtSAGENet captures and encodes valuable relational dependencies between the artists and the artworks, surpassing the performance of traditional methods that rely solely on the analysis of visual content. Our findings underline a great potential of integrating visual content and semantics for fine art analysis and curation.
Copyright in Generative Deep Learning
Venue: arXiv cs.CY 2025
Year: 2025

Machine-generated artworks are now part of the contemporary art scene: they are attracting significant investments and they are presented in exhibitions together with those created by human artists. These artworks are mainly based on generative deep learning techniques, which have seen a formidable development and remarkable refinement in the very recent years. Given the inherent characteristics of these techniques, a series of novel legal problems arise. In this article, we consider a set of key questions in the area of generative deep learning for the arts, including the following: is it possible to use copyrighted works as training set for generative models? How do we legally store their copies in order to perform the training process? Who (if someone) will own the copyright on the generated data? We try to answer these questions considering the law in force in both the United States of America and the European Union, and potential future alternatives. We then extend our analysis to code generation, which is an emerging area of generative deep learning. Finally, we also formulate a set of practical guidelines for artists and developers working on deep learning generated art, as well as some policy suggestions for policymakers.
How Packed Is It, Really?
Venue: arXiv cs.CG 2025
Year: 2025

The congestion of a curve is a measure of how much it zigzags around locally. More precisely, a curve $π$ is $c$-packed if the length of the curve lying inside any ball is at most $c$ times the radius of the ball, and its congestion is the minimum $c$ for which $π$ is $c$-packed. This paper presents a randomized $42$-approximation algorithm for computing the congestion of a curve (or any set of segments in the plane). It runs in $O( n \log^2 n)$ time and succeeds with high probability. Although the approximation factor is large, the running time improves over the previous fastest constant approximation algorithm, which took $\widetilde{O}(n^{4/3})$ time. We carefully combine new ideas with known techniques to obtain our new near-linear time algorithm.
GraphFM: Graph Factorization Machines for Feature Interaction Modeling
Venue: arXiv cs.LG 2025
Year: 2025

Factorization machine (FM) is a prevalent approach to modeling pairwise (second-order) feature interactions when dealing with high-dimensional sparse data. However, on the one hand, FM fails to capture higher-order feature interactions suffering from combinatorial expansion. On the other hand, taking into account interactions between every pair of features may introduce noise and degrade prediction accuracy. To solve the problems, we propose a novel approach, Graph Factorization Machine (GraphFM), by naturally representing features in the graph structure. In particular, we design a mechanism to select the beneficial feature interactions and formulate them as edges between features. Then the proposed model, which integrates the interaction function of FM into the feature aggregation strategy of Graph Neural Network (GNN), can model arbitrary-order feature interactions on the graph-structured features by stacking layers. Experimental results on several real-world datasets have demonstrated the rationality and effectiveness of our proposed approach. The code and data are available at https://github.com/CRIPAC-DIG/GraphCTR}{https://github.com/CRIPAC-DIG/GraphCTR
A beginner guide to Iris, Coq and separation logic
Venue: arXiv cs.LO 2025
Year: 2025

Creating safe concurrent algorithms is challenging and error-prone. For this reason, a formal verification framework is necessary especially when those concurrent algorithms are used in safety-critical systems. The goal of this guide is to provide resources for beginners to get started in their journey of formal verification using the powerful tool Iris. The difference between this guide and many others is that it provides (i) an in-depth explanation of examples and tactics, (ii) an explicit discussion of separation logic, and (iii) a thorough coverage of Iris and Coq. References to other guides and to papers are included throughout to provide readers with resources through which to continue their learning.
Rater Equivalence: Evaluating Classifiers in Human Judgment Settings
Venue: arXiv cs.LG 2025
Year: 2025

In many decision settings, the definitive ground truth is either non-existent or inaccessible. We introduce a framework for evaluating classifiers based solely on human judgments. In such cases, it is helpful to compare automated classifiers to human judgment. We quantify a classifier's performance by its rater equivalence: the smallest number of human raters whose combined judgment matches the classifier's performance. Our framework uses human-generated labels both to construct benchmark panels and to evaluate performance. We distinguish between two models of utility: one based on agreement with the assumed but inaccessible ground truth, and one based on matching individual human judgments. Using case studies and formal analysis, we demonstrate how this framework can inform the evaluation and deployment of AI systems in practice.
Deep Switching State Space Model (DS$^3$M) for Nonlinear Time Series Forecasting with Regime Switching
Venue: arXiv cs.LG 2025
Year: 2025

Modern time series data often display complex nonlinear dependencies along with irregular regime-switching behaviors. These features present technical challenges in modeling, inference, and in offering insightful understanding into the underlying stochastic phenomena. To tackle these challenges, we introduce a novel modeling framework known as the Deep Switching State Space Model (DS$^3$M). This framework is engineered to make accurate forecasts for such time series while adeptly identifying the irregular regimes hidden within the dynamics. These identifications not only have significant economic ramifications but also contribute to a deeper understanding of the underlying phenomena. In DS$^3$M, the architecture employs discrete latent variables to represent regimes and continuous latent variables to account for random driving factors. By melding a Recurrent Neural Network (RNN) with a nonlinear Switching State Space Model (SSSM), we manage to capture the nonlinear dependencies and irregular regime-switching behaviors, governed by a Markov chain and parameterized using multilayer perceptrons. We validate the effectiveness and regime identification capabilities of DS$^3$M through short- and long-term forecasting tests on a wide array of simulated and real-world datasets, spanning sectors such as healthcare, economics, traffic, meteorology, and energy. Experimental results reveal that DS$^3$M outperforms several state-of-the-art models in terms of forecasting accuracy, while providing meaningful regime identifications.
Test Script Intention Generation for Mobile Application via GUI Image and Code Understanding
Venue: arXiv cs.SE 2025
Year: 2025

Testing is the most direct and effective technique to ensure software quality. Test scripts always play a more important role in mobile app testing than test cases for source code, due to the GUI-intensive and event-driven characteristics of mobile applications (app). Test scripts focus on user interactions and the corresponding response events, which is significant for testing the target app functionalities. Therefore, it is critical to understand the test scripts for better script maintenance and modification. There exist some mature code understanding (i.e., code comment generation) technologies that can be directly applied to functionality source code with business logic. However, such technologies will have difficulties when being applied to test scripts, because test scripts are loosely linked to apps under test (AUT) by widget selectors, and do not contain business logic themselves. In order to solve the test script understanding gap, this paper presents a novel approach, namely TestIntention, to infer the intention of GUI test scripts. Test intention refers to the user expectations of app behaviors for specific operations. TestIntention formalizes test scripts with an operation sequence model. For each operation within the sequence, TestIntention extracts the target widget selector and links the selector to the GUI layout information or the corresponding response events. For widgets identified by XPath, TestIntention utilizes the image understanding technologies to explore the detailed information of the widget images, the intention of which is understood with a deep learning model. For widgets identified by ID, TestIntention first maps the selectors to the response methods with business logic, and then adopts code understanding technologies to describe code in natural language form. Results of all operations are combined to generate test intention for test scripts.
Chimera: Efficiently Training Large-Scale Neural Networks with Bidirectional Pipelines
Venue: arXiv cs.DC 2025
Year: 2025

Training large deep learning models at scale is very challenging. This paper proposes Chimera, a novel pipeline parallelism scheme which combines bidirectional pipelines for efficiently training large-scale models. Chimera is a synchronous approach and therefore no loss of accuracy, which is more convergence-friendly than asynchronous approaches. Compared with the latest synchronous pipeline approach, Chimera reduces the number of bubbles by up to 50%; benefiting from the sophisticated scheduling of bidirectional pipelines, Chimera has a more balanced activation memory consumption. Evaluations are conducted on Transformer based language models. For a GPT-2 model with 1.3 billion parameters running on 2,048 GPU nodes of the Piz Daint supercomputer, Chimera improves the training throughput by 1.16x-2.34x over the state-of-the-art synchronous and asynchronous pipeline approaches.
Finitely Bounded Homogeneity Turned Inside-Out
Venue: arXiv cs.LO 2025
Year: 2025

Deciding the amalgamation property for a given class of finite structures is an important subroutine in classifying countable finitely homogeneous structures. We study the computational complexity of the amalgamation decision problem for finitely bounded classes, i.e., classes specified by a finite set of forbidden finite substructures, or equivalently by a finite set of universal axioms. We link the amalgamation decision problem to the problem of testing the containment between the reducts of two given finitely bounded amalgamation classes to a given common subset of their signatures. On the one hand, this link enables polynomial-time reductions from various decision problems that can be represented within the reduct containment problem for finitely bounded amalgamation classes, e.g., the 2-exponential square tiling problem, leading to a new lower bound for the complexity of the amalgamation decision problem: 2NEXPTIME-hardness. On the other hand, the link also allows us to show that the amalgamation decision problem is decidable under the assumption that every finitely bounded strong amalgamation class has a computable finitely bounded Ramsey expansion. The runtime of our conditional decision procedure depends 2-exponentially on the size of a minimal Ramsey expansion. We subsequently prove that the closely related problem of testing homogenizability is already undecidable, by a polynomial-time reduction from the regularity of context-free languages. Our results indicate that the relationship between finitely bounded amalgamation classes and arbitrary finitely bounded classes shares similarities with the relationship between regular grammars and context-free grammars. A key difference is that the regularity of context-free grammars can be tested in linear time, while the problem of testing the amalgamation property for finitely bounded classes is 2NEXPTIME-hard.
Information Bottleneck Approach to Spatial Attention Learning
Venue: arXiv cs.CV 2025
Year: 2025

The selective visual attention mechanism in the human visual system (HVS) restricts the amount of information to reach visual awareness for perceiving natural scenes, allowing near real-time information processing with limited computational capacity [Koch and Ullman, 1987]. This kind of selectivity acts as an 'Information Bottleneck (IB)', which seeks a trade-off between information compression and predictive accuracy. However, such information constraints are rarely explored in the attention mechanism for deep neural networks (DNNs). In this paper, we propose an IB-inspired spatial attention module for DNN structures built for visual recognition. The module takes as input an intermediate representation of the input image, and outputs a variational 2D attention map that minimizes the mutual information (MI) between the attention-modulated representation and the input, while maximizing the MI between the attention-modulated representation and the task label. To further restrict the information bypassed by the attention map, we quantize the continuous attention scores to a set of learnable anchor values during training. Extensive experiments show that the proposed IB-inspired spatial attention mechanism can yield attention maps that neatly highlight the regions of interest while suppressing backgrounds, and bootstrap standard DNN structures for visual recognition tasks (e.g., image classification, fine-grained recognition, cross-domain classification). The attention maps are interpretable for the decision making of the DNNs as verified in the experiments. Our code is available at https://github.com/ashleylqx/AIB.git.
KCNet: An Insect-Inspired Single-Hidden-Layer Neural Network with Randomized Binary Weights for Prediction and Classification Tasks
Venue: arXiv cs.LG 2025
Year: 2025

Fruit flies are established model systems for studying olfactory learning as they will readily learn to associate odors with both electric shock or sugar rewards. The mechanisms of the insect brain apparently responsible for odor learning form a relatively shallow neuronal architecture. Olfactory inputs are received by the antennal lobe (AL) of the brain, which produces an encoding of each odor mixture across ~50 sub-units known as glomeruli. Each of these glomeruli then projects its component of this feature vector to several of ~2000 so-called Kenyon Cells (KCs) in a region of the brain known as the mushroom body (MB). Fly responses to odors are generated by small downstream neutrophils that decode the higher-order representation from the MB. Research has shown that there is no recognizable pattern in the glomeruli--KC connections (and thus the particular higher-order representations); they are akin to fingerprints--even isogenic flies have different projections. Leveraging insights from this architecture, we propose KCNet, a single-hidden-layer neural network that contains sparse, randomized, binary weights between the input layer and the hidden layer and analytically learned weights between the hidden layer and the output layer. Furthermore, we also propose a dynamic optimization algorithm that enables the KCNet to increase performance beyond its structural limits by searching for a more efficient set of inputs. For odorant-perception tasks that predict the perceptual properties of an odorant, we show that KCNet outperforms existing data-driven approaches, such as XGBoost. For image classification tasks, KCNet achieves reasonable performance on benchmark datasets (MNIST, Fashion-MNIST, and EMNIST) without any data-augmentation methods or convolutional layers and shows a particularly fast running time.
Fed-TGAN: Federated Learning Framework for Synthesizing Tabular Data
Venue: arXiv cs.LG 2025
Year: 2025

Generative Adversarial Networks (GANs) are typically trained to synthesize data, from images and more recently tabular data, under the assumption of directly accessible training data. Recently, federated learning (FL) is an emerging paradigm that features decentralized learning on client's local data with a privacy-preserving capability. And, while learning GANs to synthesize images on FL systems has just been demonstrated, it is unknown if GANs for tabular data can be learned from decentralized data sources. Moreover, it remains unclear which distributed architecture suits them best. Different from image GANs, state-of-the-art tabular GANs require prior knowledge on the data distribution of each (discrete and continuous) column to agree on a common encoding -- risking privacy guarantees. In this paper, we propose Fed-TGAN, the first Federated learning framework for Tabular GANs. To effectively learn a complex tabular GAN on non-identical participants, Fed-TGAN designs two novel features: (i) a privacy-preserving multi-source feature encoding for model initialization; and (ii) table similarity aware weighting strategies to aggregate local models for countering data skew. We extensively evaluate the proposed Fed-TGAN against variants of decentralized learning architectures on four widely used datasets. Results show that Fed-TGAN accelerates training time per epoch up to 200% compared to the alternative architectures, for both IID and Non-IID data. Overall, Fed-TGAN not only stabilizes the training loss, but also achieves better similarity between generated and original data. Our code is released at https://github.com/zhao-zilong/Fed-TGAN.