OpenRaiser/Intern-Atlas huggingface dataset:
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
Venue: arXiv cs.DS 2023
Year: 2023

We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier $k$-sparse vector $\widehat{x} \in \mathbb{C}^{n^d}$ from observing its time domain representation $x$. In the exact $k$-sparse case the best known dimension-independent algorithm runs in near cubic time in $k$ and it is unclear whether a faster algorithm like in low dimensions is possible. Beyond that, all known approaches either suffer from an exponential dependence on the dimension $d$ or can only tolerate a trivial amount of noise. This is in sharp contrast with the classical FFT of Cooley and Tukey, which is stable and completely insensitive to the dimension of the input vector: its runtime is $O(N\log N)$ in any dimension $d$ for $N=n^d$. Our work aims to address the above issues. First, we provide a translation/reduction of the exactly $k$-sparse FT problem to a concrete tree exploration task which asks to recover $k$ leaves in a full binary tree under certain exploration rules. Subsequently, we provide (a) an almost quadratic in $k$ time algorithm for this task, and (b) evidence that a strongly subquadratic time for Sparse FT via this approach is likely impossible. We achieve the latter by proving a conditional quadratic time lower bound on sparse polynomial multipoint evaluation (the classical non-equispaced sparse FT) which is a core routine in the aforementioned translation. Thus, our results combined can be viewed as an almost complete understanding of this approach, which is the only known approach that yields sublinear time dimension-independent Sparse FT algorithms. Subsequently, we provide a robustification of our algorithm, yielding a robust cubic time algorithm under bounded $\ell_2$ noise. This requires proving new structural properties of the recently introduced adaptive aliasing filters combined with a variety of new techniques and ideas.
EGC2: Enhanced Graph Classification with Easy Graph Compression
Venue: arXiv cs.LG 2023
Year: 2023

Graph classification is crucial in network analyses. Networks face potential security threats, such as adversarial attacks. Some defense methods may trade off the algorithm complexity for robustness, such as adversarial training, whereas others may trade off clean example performance, such as smoothingbased defense. Most suffer from high complexity or low transferability. To address this problem, we proposed EGC2, an enhanced graph classification model with easy graph compression. EGC2 captures the relationship between the features of different nodes by constructing feature graphs and improving the aggregation of the node-level representations. To achieve lower-complexity defense applied to graph classification models, EGC2 utilizes a centrality-based edge-importance index to compress the graphs, filtering out trivial structures and adversarial perturbations in the input graphs, thus improving the model's robustness. Experiments on ten benchmark datasets demonstrate that the proposed feature read-out and graph compression mechanisms enhance the robustness of multiple basic models, resulting in a state-of-the-art performance in terms of accuracy and robustness against various adversarial attacks.
Satisfaction and Performance of Software Developers during Enforced Work from Home in the COVID-19 Pandemic
Venue: arXiv cs.SE 2023
Year: 2023

Following the onset of the COVID-19 pandemic and subsequent lockdowns, the daily lives of software engineers were heavily disrupted as they were abruptly forced to work remotely from home. To better understand and contrast typical working days in this new reality with work in pre-pandemic times, we conducted one exploratory (N = 192) and one confirmatory study (N = 290) with software engineers recruited remotely. Specifically, we build on self-determination theory to evaluate whether and how specific activities are associated with software engineers' satisfaction and productivity. To explore the subject domain, we first ran a two-wave longitudinal study. We found that the time software engineers spent on specific activities (e.g., coding, bugfixing, helping others) while working from home was similar to pre-pandemic times. Also, the amount of time developers spent on each activity was unrelated to their general well-being, perceived productivity, and other variables such as basic needs. Our confirmatory study found that activity-specific variables (e.g., how much autonomy software engineers had during coding) do predict activity satisfaction and productivity but not by activity-independent variables such as general resilience or a good work-life balance. Interestingly, we found that satisfaction and autonomy were significantly higher when software engineers were helping others and lower when they were bugfixing. Finally, we discuss implications for software engineers, management, and researchers. In particular, active company policies to support developers' need for autonomy, relatedness, and competence appear particularly effective in a WFH context.
The Limiting Dynamics of SGD: Modified Loss, Phase Space Oscillations, and Anomalous Diffusion
Venue: arXiv cs.LG 2023
Year: 2023

In this work we explore the limiting dynamics of deep neural networks trained with stochastic gradient descent (SGD). As observed previously, long after performance has converged, networks continue to move through parameter space by a process of anomalous diffusion in which distance travelled grows as a power law in the number of gradient updates with a nontrivial exponent. We reveal an intricate interaction between the hyperparameters of optimization, the structure in the gradient noise, and the Hessian matrix at the end of training that explains this anomalous diffusion. To build this understanding, we first derive a continuous-time model for SGD with finite learning rates and batch sizes as an underdamped Langevin equation. We study this equation in the setting of linear regression, where we can derive exact, analytic expressions for the phase space dynamics of the parameters and their instantaneous velocities from initialization to stationarity. Using the Fokker-Planck equation, we show that the key ingredient driving these dynamics is not the original training loss, but rather the combination of a modified loss, which implicitly regularizes the velocity, and probability currents, which cause oscillations in phase space. We identify qualitative and quantitative predictions of this theory in the dynamics of a ResNet-18 model trained on ImageNet. Through the lens of statistical physics, we uncover a mechanistic origin for the anomalous limiting dynamics of deep neural networks trained with SGD.
Fine-Grained Music Plagiarism Detection: Revealing Plagiarists through Bipartite Graph Matching and a Comprehensive Large-Scale Dataset
Venue: arXiv cs.SD 2023
Year: 2023

Music plagiarism detection is gaining more and more attention due to the popularity of music production and society's emphasis on intellectual property. We aim to find fine-grained plagiarism in music pairs since conventional methods are coarse-grained and cannot match real-life scenarios. Considering that there is no sizeable dataset designed for the music plagiarism task, we establish a large-scale simulated dataset, named Music Plagiarism Detection Dataset (MPD-Set) under the guidance and expertise of renowned researchers from national-level professional institutions in the field of music. MPD-Set considers diverse music plagiarism cases found in real life from the melodic, rhythmic, and tonal levels respectively. Further, we establish a Real-life Dataset for evaluation, where all plagiarism pairs are real cases. To detect the fine-grained plagiarism pairs effectively, we propose a graph-based method called Bipatite Melody Matching Detector (BMM-Det), which formulates the problem as a max matching problem in the bipartite graph. Experimental results on both the simulated and Real-life Datasets demonstrate that BMM-Det outperforms the existing plagiarism detection methods, and is robust to common plagiarism cases like transpositions, pitch shifts, duration variance, and melody change. Datasets and source code are open-sourced at https://github.com/xuan301/BMMDet_MPDSet.
DOA Estimation for Hybrid Massive MIMO Systems using Mixed-ADCs: Performance Loss and Energy Efficiency
Venue: arXiv cs.IT 2023
Year: 2023

Due to the power consumption and high circuit cost in antenna arrays, the practical application of massive multiple-input multiple-output (MIMO) in the sixth generation (6G) and future wireless networks is still challenging. Employing low-resolution analog-to-digital converters (ADCs) and hybrid analog and digital (HAD) structure is two low-cost choice with acceptable performance loss.In this paper, the combination of the mixed-ADC architecture and HAD structure employed at receiver is proposed for direction of arrival (DOA) estimation, which will be applied to the beamforming tracking and alignment in 6G. By adopting the additive quantization noise model, the exact closed-form expression of the Cramér-Rao lower bound (CRLB) for the HAD architecture with mixed-ADCs is derived. Moreover, the closed-form expression of the performance loss factor is derived as a benchmark. In addition, to take power consumption into account, energy efficiency is also investigated in our paper. The numerical results reveal that the HAD structure with mixed-ADCs can significantly reduce the power consumption and hardware cost. Furthermore, that architecture is able to achieve a better trade-off between the performance loss and the power consumption. Finally, adopting 2-4 bits of resolution may be a good choice in practical massive MIMO systems.
SGD with a Constant Large Learning Rate Can Converge to Local Maxima
Venue: arXiv cs.LG 2023
Year: 2023

Previous works on stochastic gradient descent (SGD) often focus on its success. In this work, we construct worst-case optimization problems illustrating that, when not in the regimes that the previous works often assume, SGD can exhibit many strange and potentially undesirable behaviors. Specifically, we construct landscapes and data distributions such that (1) SGD converges to local maxima, (2) SGD escapes saddle points arbitrarily slowly, (3) SGD prefers sharp minima over flat ones, and (4) AMSGrad converges to local maxima. We also realize results in a minimal neural network-like example. Our results highlight the importance of simultaneously analyzing the minibatch sampling, discrete-time updates rules, and realistic landscapes to understand the role of SGD in deep learning.
A Low-Cost Neural ODE with Depthwise Separable Convolution for Edge Domain Adaptation on FPGAs
Venue: arXiv cs.LG 2023
Year: 2023

High-performance deep neural network (DNN)-based systems are in high demand in edge environments. Due to its high computational complexity, it is challenging to deploy DNNs on edge devices with strict limitations on computational resources. In this paper, we derive a compact while highly-accurate DNN model, termed dsODENet, by combining recently-proposed parameter reduction techniques: Neural ODE (Ordinary Differential Equation) and DSC (Depthwise Separable Convolution). Neural ODE exploits a similarity between ResNet and ODE, and shares most of weight parameters among multiple layers, which greatly reduces the memory consumption. We apply dsODENet to a domain adaptation as a practical use case with image classification datasets. We also propose a resource-efficient FPGA-based design for dsODENet, where all the parameters and feature maps except for pre- and post-processing layers can be mapped onto on-chip memories. It is implemented on Xilinx ZCU104 board and evaluated in terms of domain adaptation accuracy, inference speed, FPGA resource utilization, and speedup rate compared to a software counterpart. The results demonstrate that dsODENet achieves comparable or slightly better domain adaptation accuracy compared to our baseline Neural ODE implementation, while the total parameter size without pre- and post-processing layers is reduced by 54.2% to 79.8%. Our FPGA implementation accelerates the inference speed by 23.8 times.
Continuation Newton methods with deflation techniques for global optimization problems
Venue: arXiv cs.NE 2023
Year: 2023

The global minimum point of an optimization problem is of interest in engineering fields and it is difficult to be found, especially for a nonconvex large-scale optimization problem. In this article, we consider a new memetic algorithm for this problem. That is to say, we use the continuation Newton method with the deflation technique to find multiple stationary points of the objective function and use those found stationary points as the initial seeds of the evolutionary algorithm, other than the random initial seeds of the known evolutionary algorithms. Meanwhile, in order to retain the usability of the derivative-free method and the fast convergence of the gradient-based method, we use the automatic differentiation technique to compute the gradient and replace the Hessian matrix with its finite difference approximation. According to our numerical experiments, this new algorithm works well for unconstrained optimization problems and finds their global minima efficiently, in comparison to the other representative global optimization methods such as the multi-start methods (the built-in subroutine GlobalSearch.m of MATLAB R2021b, GLODS and VRBBO), the branch-and-bound method (Couenne, a state-of-the-art open-source solver for mixed integer nonlinear programming problems), and the derivative-free algorithms (CMA-ES and MCS).
Temporal Dependencies in Feature Importance for Time Series Predictions
Venue: arXiv cs.LG 2023
Year: 2023

Time series data introduces two key challenges for explainability methods: firstly, observations of the same feature over subsequent time steps are not independent, and secondly, the same feature can have varying importance to model predictions over time. In this paper, we propose Windowed Feature Importance in Time (WinIT), a feature removal based explainability approach to address these issues. Unlike existing feature removal explanation methods, WinIT explicitly accounts for the temporal dependence between different observations of the same feature in the construction of its importance score. Furthermore, WinIT captures the varying importance of a feature over time, by summarizing its importance over a window of past time steps. We conduct an extensive empirical study on synthetic and real-world data, compare against a wide range of leading explainability methods, and explore the impact of various evaluation strategies. Our results show that WinIT achieves significant gains over existing methods, with more consistent performance across different evaluation metrics. The code for our work is publicly available at \url{https://github.com/layer6ai-labs/WinIT}.
Talk2Data: A Natural Language Interface for Exploratory Visual Analysis via Question Decomposition
Venue: arXiv cs.HC 2023
Year: 2023

Through a natural language interface (NLI) for exploratory visual analysis, users can directly "ask" analytical questions about the given tabular data. This process greatly improves user experience and lowers the technical barriers of data analysis. Existing techniques focus on generating a visualization from a concrete question. However, complex questions, requiring multiple data queries and visualizations to answer, are frequently asked in data exploration and analysis, which cannot be easily solved with the existing techniques. To address this issue, in this paper, we introduce Talk2Data, a natural language interface for exploratory visual analysis that supports answering complex questions. It leverages an advanced deep-learning model to resolve complex questions into a series of simple questions that could gradually elaborate on the users' requirements. To present answers, we design a set of annotated and captioned visualizations to represent the answers in a form that supports interpretation and narration. We conducted an ablation study and a controlled user study to evaluate Talk2Data's effectiveness and usefulness.
Synth-by-Reg (SbR): Contrastive learning for synthesis-based registration of paired images
Venue: arXiv cs.CV 2023
Year: 2023

Nonlinear inter-modality registration is often challenging due to the lack of objective functions that are good proxies for alignment. Here we propose a synthesis-by-registration method to convert this problem into an easier intra-modality task. We introduce a registration loss for weakly supervised image translation between domains that does not require perfectly aligned training data. This loss capitalises on a registration U-Net with frozen weights, to drive a synthesis CNN towards the desired translation. We complement this loss with a structure preserving constraint based on contrastive learning, which prevents blurring and content shifts due to overfitting. We apply this method to the registration of histological sections to MRI slices, a key step in 3D histology reconstruction. Results on two different public datasets show improvements over registration based on mutual information (13% reduction in landmark error) and synthesis-based algorithms such as CycleGAN (11% reduction), and are comparable to a registration CNN with label supervision. Code and data are publicly available at \url{https://github.com/acasamitjana/SynthByReg}
Motion Planning for Variable Topology Trusses: Reconfiguration and Locomotion
Venue: arXiv cs.RO 2023
Year: 2023

Truss robots are highly redundant parallel robotic systems that can be applied in a variety of scenarios. The variable topology truss (VTT) is a class of modular truss robots. As self-reconfigurable modular robots, a VTT is composed of many edge modules that can be rearranged into various structures depending on the task. These robots change their shape by not only controlling joint positions as with fixed morphology robots, but also reconfiguring the connectivity between truss members in order to change their topology. The motion planning problem for VTT robots is difficult due to their varying morphology, high dimensionality, the high likelihood for self-collision, and complex motion constraints. In this paper, a new motion planning framework to dramatically alter the structure of a VTT is presented. It can also be used to solve locomotion tasks that are much more efficient compared with previous work. Several test scenarios are used to show its effectiveness. Supplementary materials are available at https://www.modlabupenn.org/vtt-motion-planning/.
Hardness and Approximation of Submodular Minimum Linear Ordering Problems
Venue: arXiv cs.DS 2023
Year: 2023

The minimum linear ordering problem (MLOP) generalizes well-known combinatorial optimization problems such as minimum linear arrangement and minimum sum set cover. MLOP seeks to minimize an aggregated cost $f(\cdot)$ due to an ordering $σ$ of the items (say $[n]$), i.e., $\min_σ \sum_{i\in [n]} f(E_{i,σ})$, where $E_{i,σ}$ is the set of items mapped by $σ$ to indices $[i]$. Despite an extensive literature on MLOP variants and approximations for these, it was unclear whether the graphic matroid MLOP was NP-hard. We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. This is in contrast to the rounding algorithm by Iwata, Tetali, and Tripathi [ITT2012], using Lovász extension of submodular functions. We show a $(2-\frac{1+\ell_{f}}{1+|E|})$-approximation for monotone submodular MLOP where $\ell_{f}=\frac{f(E)}{\max_{x\in E}f(\{x\})}$ satisfies $1 \leq \ell_f \leq |E|$. Our theory provides new approximation bounds for special cases of the problem, in particular a $(2-\frac{1+r(E)}{1+|E|})$-approximation for the matroid MLOP, where $f = r$ is the rank function of a matroid. We further show that minimum latency vertex cover (MLVC) is $\frac{4}{3}$-approximable, by which we also lower bound the integrality gap of its natural LP relaxation, which might be of independent interest.
Comparison of modern open-source visual SLAM approaches
Venue: arXiv cs.RO 2023
Year: 2023

SLAM is one of the most fundamental areas of research in robotics and computer vision. State of the art solutions has advanced significantly in terms of accuracy and stability. Unfortunately, not all the approaches are available as open-source solutions and free to use. The results of some of them are difficult to reproduce, and there is a lack of comparison on common datasets. In our work, we make a comparative analysis of state of the art open-source methods. We assess the algorithms based on accuracy, computational performance, robustness, and fault tolerance. Moreover, we present a comparison of datasets as well as an analysis of algorithms from a practical point of view. The findings of the work raise several crucial questions for SLAM researchers.
Point Discriminative Learning for Data-efficient 3D Point Cloud Analysis
Venue: arXiv cs.CV 2023
Year: 2023

3D point cloud analysis has drawn a lot of research attention due to its wide applications. However, collecting massive labelled 3D point cloud data is both time-consuming and labor-intensive. This calls for data-efficient learning methods. In this work we propose PointDisc, a point discriminative learning method to leverage self-supervisions for data-efficient 3D point cloud classification and segmentation. PointDisc imposes a novel point discrimination loss on the middle and global level features produced by the backbone network. This point discrimination loss enforces learned features to be consistent with points belonging to the corresponding local shape region and inconsistent with randomly sampled noisy points. We conduct extensive experiments on 3D object classification, 3D semantic and part segmentation, showing the benefits of PointDisc for data-efficient learning. Detailed analysis demonstrate that PointDisc learns unsupervised features that well capture local and global geometry.
PatchRNN: A Deep Learning-Based System for Security Patch Identification
Venue: arXiv cs.CR 2023
Year: 2023

With the increasing usage of open-source software (OSS) components, vulnerabilities embedded within them are propagated to a huge number of underlying applications. In practice, the timely application of security patches in downstream software is challenging. The main reason is that such patches do not explicitly indicate their security impacts in the documentation, which would be difficult to recognize for software maintainers and users. However, attackers can still identify these "secret" security patches by analyzing the source code and generate corresponding exploits to compromise not only unpatched versions of the current software, but also other similar software packages that may contain the same vulnerability due to code cloning or similar design/implementation logic. Therefore, it is critical to identify these secret security patches to enable timely fixes. To this end, we propose a deep learning-based defense system called PatchRNN to automatically identify secret security patches in OSS. Besides considering descriptive keywords in the commit message (i.e., at the text level), we leverage both syntactic and semantic features at the source-code level. To evaluate the performance of our system, we apply it on a large-scale real-world patch dataset and conduct a case study on a popular open-source web server software - NGINX. Experimental results show that the PatchRNN can successfully detect secret security patches with a low false positive rate.