OpenRaiser/Intern-Atlas huggingface dataset:
Microbial Genetic Algorithm-based Black-box Attack against Interpretable Deep Learning Systems
Venue: arXiv cs.CV 2023
Year: 2023

Deep learning models are susceptible to adversarial samples in white and black-box environments. Although previous studies have shown high attack success rates, coupling DNN models with interpretation models could offer a sense of security when a human expert is involved, who can identify whether a given sample is benign or malicious. However, in white-box environments, interpretable deep learning systems (IDLSes) have been shown to be vulnerable to malicious manipulations. In black-box settings, as access to the components of IDLSes is limited, it becomes more challenging for the adversary to fool the system. In this work, we propose a Query-efficient Score-based black-box attack against IDLSes, QuScore, which requires no knowledge of the target model and its coupled interpretation model. QuScore is based on transfer-based and score-based methods by employing an effective microbial genetic algorithm. Our method is designed to reduce the number of queries necessary to carry out successful attacks, resulting in a more efficient process. By continuously refining the adversarial samples created based on feedback scores from the IDLS, our approach effectively navigates the search space to identify perturbations that can fool the system. We evaluate the attack's effectiveness on four CNN models (Inception, ResNet, VGG, DenseNet) and two interpretation models (CAM, Grad), using both ImageNet and CIFAR datasets. Our results show that the proposed approach is query-efficient with a high attack success rate that can reach between 95% and 100% and transferability with an average success rate of 69% in the ImageNet and CIFAR datasets. Our attack method generates adversarial examples with attribution maps that resemble benign samples. We have also demonstrated that our attack is resilient against various preprocessing defense techniques and can easily be transferred to different DNN models.
Research Explosion: More Effort to Climb onto Shoulders of the Giant
Venue: arXiv cs.DL 2023
Year: 2023

Fast-growing scientific publications present challenges to the scientific community. In this paper, we describe their implications to researchers. As references form explicit foundations for researchers to conduct a study, we investigate the evolution in reference patterns based on 60.8 million papers published from 1960 to 2015. The results demonstrate that recent papers contain more references than older ones, especially the well-cited papers compared with other papers. Well-cited papers receive 10 or more citations within 5 years of publication. Their references cover a longer period from classic research to very recent studies. Authors of well-cited papers are also farsighted to discover the reference papers with good potential to receive high citation numbers in near future. We also discover that the number of accumulative publications has a negative impact on next-5-year citation count for most fields except Chemistry, Materials science, Environmental science, Biology, and Engineering. Our findings suggest that researchers are expected to devote more effort to producing impactful research. Based on all these findings, we strongly advise against judging researchers simply based on the number of their publications. On the other hand, authors and reviewers should ensure that published papers contain adequate contributions. The code for our analysis is on GitHub: https://github.com/ECNU-Text-Computing/Research-Explosion.
AvatarFusion: Zero-shot Generation of Clothing-Decoupled 3D Avatars Using 2D Diffusion
Venue: arXiv cs.CV 2023
Year: 2023

Large-scale pre-trained vision-language models allow for the zero-shot text-based generation of 3D avatars. The previous state-of-the-art method utilized CLIP to supervise neural implicit models that reconstructed a human body mesh. However, this approach has two limitations. Firstly, the lack of avatar-specific models can cause facial distortion and unrealistic clothing in the generated avatars. Secondly, CLIP only provides optimization direction for the overall appearance, resulting in less impressive results. To address these limitations, we propose AvatarFusion, the first framework to use a latent diffusion model to provide pixel-level guidance for generating human-realistic avatars while simultaneously segmenting clothing from the avatar's body. AvatarFusion includes the first clothing-decoupled neural implicit avatar model that employs a novel Dual Volume Rendering strategy to render the decoupled skin and clothing sub-models in one space. We also introduce a novel optimization method, called Pixel-Semantics Difference-Sampling (PS-DS), which semantically separates the generation of body and clothes, and generates a variety of clothing styles. Moreover, we establish the first benchmark for zero-shot text-to-avatar generation. Our experimental results demonstrate that our framework outperforms previous approaches, with significant improvements observed in all metrics. Additionally, since our model is clothing-decoupled, we can exchange the clothes of avatars. Code are available on our project page https://hansenhuang0823.github.io/AvatarFusion.
Regression-Oriented Knowledge Distillation for Lightweight Ship Orientation Angle Prediction with Optical Remote Sensing Images
Venue: arXiv cs.CV 2023
Year: 2023

Ship orientation angle prediction (SOAP) with optical remote sensing images is an important image processing task, which often relies on deep convolutional neural networks (CNNs) to make accurate predictions. This paper proposes a novel framework to reduce the model sizes and computational costs of SOAP models without harming prediction accuracy. First, a new SOAP model called Mobile-SOAP is designed based on MobileNetV2, achieving state-of-the-art prediction accuracy. Four tiny SOAP models are also created by replacing the convolutional blocks in Mobile-SOAP with four small-scale networks, respectively. Then, to transfer knowledge from Mobile-SOAP to four lightweight models, we propose a novel knowledge distillation (KD) framework termed SOAP-KD consisting of a novel feature-based guidance loss and an optimized synthetic samples-based knowledge transfer mechanism. Lastly, extensive experiments on the FGSC-23 dataset confirm the superiority of Mobile-SOAP over existing models and also demonstrate the effectiveness of SOAP-KD in improving the prediction performance of four specially designed tiny models. Notably, by using SOAP-KD, the test mean absolute error of the ShuffleNetV2x1.0-based model is only 8% higher than that of Mobile-SOAP, but its number of parameters and multiply-accumulate operations (MACs) are respectively 61.6% and 60.8% less.
A Study on Differentiable Logic and LLMs for EPIC-KITCHENS-100 Unsupervised Domain Adaptation Challenge for Action Recognition 2023
Venue: arXiv cs.CV 2023
Year: 2023

In this technical report, we present our findings from a study conducted on the EPIC-KITCHENS-100 Unsupervised Domain Adaptation task for Action Recognition. Our research focuses on the innovative application of a differentiable logic loss in the training to leverage the co-occurrence relations between verb and noun, as well as the pre-trained Large Language Models (LLMs) to generate the logic rules for the adaptation to unseen action labels. Specifically, the model's predictions are treated as the truth assignment of a co-occurrence logic formula to compute the logic loss, which measures the consistency between the predictions and the logic constraints. By using the verb-noun co-occurrence matrix generated from the dataset, we observe a moderate improvement in model performance compared to our baseline framework. To further enhance the model's adaptability to novel action labels, we experiment with rules generated using GPT-3.5, which leads to a slight decrease in performance. These findings shed light on the potential and challenges of incorporating differentiable logic and LLMs for knowledge extraction in unsupervised domain adaptation for action recognition. Our final submission (entitled `NS-LLM') achieved the first place in terms of top-1 action recognition accuracy.
Integer sequences that are generalized weights of a linear code
Venue: arXiv cs.IT 2023
Year: 2023

Which integer sequences are sequences of generalized weights of a linear code? In this paper, we answer this question for linear block codes, rank-metric codes, and more generally for sum-rank metric codes. We do so under an existence assumption for MDS and MSRD codes. We also prove that the same integer sequences appear as sequences of greedy weights of linear block codes, rank-metric codes, and sum-rank metric codes. Finally, we characterize the integer sequences which appear as sequences of relative generalized weights (respectively, relative greedy weights) of linear block codes.
Frameless Graph Knowledge Distillation
Venue: arXiv cs.LG 2023
Year: 2023

Knowledge distillation (KD) has shown great potential for transferring knowledge from a complex teacher model to a simple student model in which the heavy learning task can be accomplished efficiently and without losing too much prediction accuracy. Recently, many attempts have been made by applying the KD mechanism to the graph representation learning models such as graph neural networks (GNNs) to accelerate the model's inference speed via student models. However, many existing KD-based GNNs utilize MLP as a universal approximator in the student model to imitate the teacher model's process without considering the graph knowledge from the teacher model. In this work, we provide a KD-based framework on multi-scaled GNNs, known as graph framelet, and prove that by adequately utilizing the graph knowledge in a multi-scaled manner provided by graph framelet decomposition, the student model is capable of adapting both homophilic and heterophilic graphs and has the potential of alleviating the over-squashing issue with a simple yet effectively graph surgery. Furthermore, we show how the graph knowledge supplied by the teacher is learned and digested by the student model via both algebra and geometry. Comprehensive experiments show that our proposed model can generate learning accuracy identical to or even surpass the teacher model while maintaining the high speed of inference.
A Local-Time Semantics for Negotiations
Venue: arXiv cs.FL 2023
Year: 2023

Negotiations, introduced by Esparza et al., are a model for concurrent systems where computations involving a set of agents are described in terms of their interactions. In many situations, it is natural to impose timing constraints between interactions -- for instance, to limit the time available to enter the PIN after inserting a card into an ATM. To model this, we introduce a real-time aspect to negotiations. In our model of local-timed negotiations, agents have local reference times that evolve independently. Inspired by the model of networks of timed automata, each agent is equipped with a set of local clocks. Similar to timed automata, the outcomes of a negotiation contain guards and resets over the local clocks. As a new feature, we allow some interactions to force the reference clocks of the participating agents to synchronize. This synchronization constraint allows us to model interesting scenarios. Surprisingly, it also gives unlimited computing power. We show that reachability is undecidable for local-timed negotiations with a mixture of synchronized and unsynchronized interactions. We study restrictions on the use of synchronized interactions that make the problem decidable.
Asymptotic SEP Analysis and Optimization of Linear-Quantized Precoding in Massive MIMO Systems
Venue: arXiv cs.IT 2023
Year: 2023

A promising approach to deal with the high hardware cost and energy consumption of massive MIMO transmitters is to use low-resolution digital-to-analog converters (DACs) at each antenna element. This leads to a transmission scheme where the transmitted signals are restricted to a finite set of voltage levels. This paper is concerned with the analysis and optimization of a low-cost quantized precoding strategy, referred to as linear-quantized precoding, for a downlink massive MIMO system under Rayleigh fading. In linear-quantized precoding, the signals are first processed by a linear precoding matrix and subsequently quantized component-wise by the DAC. In this paper, we analyze both the signal-to-interference-plus-noise ratio (SINR) and the symbol error probability (SEP) performances of such linear-quantized precoding schemes in an asymptotic framework where the number of transmit antennas and the number of users grow large with a fixed ratio. Our results provide a rigorous justification for the heuristic arguments based on the Bussgang decomposition that are commonly used in prior works. Based on the asymptotic analysis, we further derive the optimal precoder within a class of linear-quantized precoders that includes several popular precoders as special cases. Our numerical results demonstrate the excellent accuracy of the asymptotic analysis for finite systems and the optimality of the derived precoder.
Breaking 3-Factor Approximation for Correlation Clustering in Polylogarithmic Rounds
Venue: arXiv cs.DS 2023
Year: 2023

In this paper, we study parallel algorithms for the correlation clustering problem, where every pair of two different entities is labeled with similar or dissimilar. The goal is to partition the entities into clusters to minimize the number of disagreements with the labels. Currently, all efficient parallel algorithms have an approximation ratio of at least 3. In comparison with the $1.994+ε$ ratio achieved by polynomial-time sequential algorithms [CLN22], a significant gap exists. We propose the first poly-logarithmic depth parallel algorithm that achieves a better approximation ratio than 3. Specifically, our algorithm computes a $(2.4+ε)$-approximate solution and uses $\tilde{O}(m^{1.5})$ work. Additionally, it can be translated into a $\tilde{O}(m^{1.5})$-time sequential algorithm and a poly-logarithmic rounds sublinear-memory MPC algorithm with $\tilde{O}(m^{1.5})$ total memory. Our approach is inspired by Awerbuch, Khandekar, and Rao's [AKR12] length-constrained multi-commodity flow algorithm, where we develop an efficient parallel algorithm to solve a truncated correlation clustering linear program of Charikar, Guruswami, and Wirth [CGW05]. Then we show the solution of the truncated linear program can be rounded with a factor of at most 2.4 loss by using the framework of [CMSY15]. Such a rounding framework can then be implemented using parallel pivot-based approaches.
Retroactive Parametrized Monitoring
Venue: arXiv cs.LO 2023
Year: 2023

In online monitoring, we first synthesize a monitor from a formal specification, which later runs in tandem with the system under study, incrementally receiving its progress and evolving with the system. In offline monitoring the trace is logged as the system progresses to later do post-mortem analysis after the system has finished executing. In this paper we propose retroactive dynamic parametrization, a technique that allows a monitor to revisit the past log as it progresses, while still executing in an online manner. This feature allows new monitors to be incorporated into a running system and to revisit the past for particular behaviors based on new information discovered. Retroactive parametrization also allows a monitor to lazily ignore events and revisit and process them later, when it discovers that it should have followed those events. We showcase the use of retroactive dynamic parametrization to monitor denial of service attacks on a network using network logs.
An update on the coin-moving game on the square grid
Venue: arXiv cs.DM 2023
Year: 2023

This paper extends the work started in 2002 by Demaine, Demaine and Verill (DDV) on coin-moving puzzles. These puzzles have a long history in the recreational literature, but were first systematically analyzed by DDV, who gave a full characterization of the solvable puzzles on the triangular grid and a partial characterization of the solvable puzzles on the square grid. This article specifically extends the study of the game on the square grid. Notably, DDV's result on puzzles with two "extra coins" is shown to be overly broad: this paper provides counterexamples as well as a revised version of this theorem. A new method for solving puzzles with two extra coins is then presented, which covers some cases where the aforementioned theorem does not apply. Puzzles with just one extra coin seem even more complicated, and are only touched upon by DDV. This paper delves deeper, studying a class of such puzzles that may be considered equivalent to a game of "poking" coins. Within this class, some cases are considered that are amenable to analysis.
Stackelberg Vertex Cover on a Path
Venue: arXiv cs.GT 2023
Year: 2023

A Stackelberg Vertex Cover game is played on an undirected graph $\mathcal{G}$ where some of the vertices are under the control of a \emph{leader}. The remaining vertices are assigned a fixed weight. The game is played in two stages. First, the leader chooses prices for the vertices under her control. Afterward, the second player, called \emph{follower}, selects a min weight vertex cover in the resulting weighted graph. That is, the follower selects a subset of vertices $C^*$ such that every edge has at least one endpoint in $C^*$ of minimum weight w.r.t.\ to the fixed weights, and the prices set by the leader. Stackelberg Vertex Cover (StackVC) describes the leader's optimization problem to select prices in the first stage of the game so as to maximize her revenue, which is the cumulative price of all her (priceable) vertices that are contained in the follower's solution. Previous research showed that StackVC is \textsf{NP}-hard on bipartite graphs, but solvable in polynomial time in the special case of bipartite graphs, where all priceable vertices belong to the same side of the bipartition. In this paper, we investigate StackVC on paths and present a dynamic program with linear time and space complexity.
Approximation algorithms for the square min-sum bin packing problem
Venue: arXiv cs.DS 2023
Year: 2023

In this work, we study the square min-sum bin packing problem (SMSBPP), where a list of square items has to be packed into indexed square bins of dimensions $1 \times 1$ with no overlap between the areas of the items. The bins are indexed and the cost of packing each item is equal to the index of the bin in which it is placed in. The objective is to minimize the total cost of packing all items, which is equivalent to minimizing the average cost of items. The problem has applications in minimizing the average time of logistic operations such as cutting stock and delivery of products. We prove that classic algorithms for two-dimensional bin packing that order items in non-increasing order of size, such as Next Fit Decreasing Height or Any Fit Decreasing Height heuristics, can have an arbitrarily bad performance for SMSBPP. We, then, present a $\frac{53}{22}$-approximation and a PTAS for the problem.
scda: A Minimal, Serial-Equivalent Format for Parallel I/O
Venue: arXiv cs.DC 2023
Year: 2023

We specify a file-oriented data format suitable for parallel, partition-independent disk I/O. Here, a partition refers to a disjoint and ordered distribution of the data elements between one or more processes. The format is designed such that the file contents are invariant under linear (i. e., unpermuted), parallel repartition of the data prior to writing. The file contents are indistinguishable from writing in serial. In the same vein, the file can be read on any number of processes that agree on any partition of the number of elements stored. In addition to the format specification we propose an optional convention to implement transparent per-element data compression. The compressed data and metadata is layered inside ordinary format elements. Overall, we pay special attention to both human and machine readability. If pure ASCII data is written, or compressed data is reencoded to ASCII, the entire file including its header and sectioning metadata remains entirely in ASCII. If binary data is written, the metadata stays easy on the human eye. We refer to this format as scda. Conceptually, it lies one layer below and is oblivious to the definition of variables, the binary representation of numbers, considerations of endianness, and self-describing headers, which may all be specified on top of scda. The main purpose of the format is to abstract any parallelism and provide sufficient structure as a foundation for a generic and flexible archival and checkpoint/restart. A documented reference implementation is available as part of the general-purpose libsc free software library.
Planar Disjoint Paths, Treewidth, and Kernels
Venue: arXiv cs.DS 2023
Year: 2023

In the Planar Disjoint Paths problem, one is given an undirected planar graph with a set of $k$ vertex pairs $(s_i,t_i)$ and the task is to find $k$ pairwise vertex-disjoint paths such that the $i$-th path connects $s_i$ to $t_i$. We study the problem through the lens of kernelization, aiming at efficiently reducing the input size in terms of a parameter. We show that Planar Disjoint Paths does not admit a polynomial kernel when parameterized by $k$ unless coNP $\subseteq$ NP/poly, resolving an open problem by [Bodlaender, Thomass{é}, Yeo, ESA'09]. Moreover, we rule out the existence of a polynomial Turing kernel unless the WK-hierarchy collapses. Our reduction carries over to the setting of edge-disjoint paths, where the kernelization status remained open even in general graphs. On the positive side, we present a polynomial kernel for Planar Disjoint Paths parameterized by $k + tw$, where $tw$ denotes the treewidth of the input graph. As a consequence of both our results, we rule out the possibility of a polynomial-time (Turing) treewidth reduction to $tw= k^{O(1)}$ under the same assumptions. To the best of our knowledge, this is the first hardness result of this kind. Finally, combining our kernel with the known techniques [Adler, Kolliopoulos, Krause, Lokshtanov, Saurabh, Thilikos, JCTB'17; Schrijver, SICOMP'94] yields an alternative (and arguably simpler) proof that Planar Disjoint Paths can be solved in time $2^{O(k^2)}\cdot n^{O(1)}$, matching the result of [Lokshtanov, Misra, Pilipczuk, Saurabh, Zehavi, STOC'20].
Data-driven Nonlinear Parametric Model Order Reduction Framework using Deep Hierarchical Variational Autoencoder
Venue: arXiv cs.LG 2023
Year: 2023

A data-driven parametric model order reduction (MOR) method using a deep artificial neural network is proposed. The present network, which is the least-squares hierarchical variational autoencoder (LSH-VAE), is capable of performing nonlinear MOR for the parametric interpolation of a nonlinear dynamic system with a significant number of degrees of freedom. LSH-VAE exploits two major changes to the existing networks: a hierarchical deep structure and a hybrid weighted, probabilistic loss function. The enhancements result in a significantly improved accuracy and stability compared against the conventional nonlinear MOR methods, autoencoder, and variational autoencoder. Upon LSH-VAE, a parametric MOR framework is presented based on the spherically linear interpolation of the latent manifold. The present framework is validated and evaluated on three nonlinear and multiphysics dynamic systems. First, the present framework is evaluated on the fluid-structure interaction benchmark problem to assess its efficiency and accuracy. Then, a highly nonlinear aeroelastic phenomenon, limit cycle oscillation, is analyzed. Finally, the present framework is applied to a three-dimensional fluid flow to demonstrate its capability of efficiently analyzing a significantly large number of degrees of freedom. The performance of LSH-VAE is emphasized by comparing its results against that of the widely used nonlinear MOR methods, convolutional autoencoder, and $β$-VAE. The present framework exhibits a significantly enhanced accuracy to the conventional methods while still exhibiting a large speed-up factor.