OpenRaiser/Intern-Atlas huggingface dataset:
Adaptive Massively Parallel Algorithms for Cut Problems
Venue: arXiv cs.DS 2022
Year: 2022

We study the Weighted Min Cut problem in the Adaptive Massively Parallel Computation (AMPC) model. In 2019, Behnezhad et al. [3] introduced the AMPC model as an extension of the Massively Parallel Computation (MPC) model. In the past decade, research on highly scalable algorithms has had significant impact on many massive systems. The MPC model, introduced in 2010 by Karloff et al. [16], which is an abstraction of famous practical frameworks such as MapReduce, Hadoop, Flume, and Spark, has been at the forefront of this research. While great strides have been taken to create highly efficient MPC algorithms for a range of problems, recent progress has been limited by the 1-vs-2 Cycle Conjecture [20], which postulates that the simple problem of distinguishing between one and two cycles requires $Ω(\log n)$ MPC rounds. In the AMPC model, each machine has adaptive read access to a distributed hash table even when communication is restricted (i.e., in the middle of a round). While remaining practical [4], this gives algorithms the power to bypass limitations like the 1-vs-2 Cycle Conjecture. We give the first sublogarithmic AMPC algorithm, requiring $O(\log\log n)$ rounds, for $(2+ε)$-approximate weighted Min Cut. Our algorithm is inspired by the divide and conquer approach of Ghaffari and Nowicki [11], which solves the $(2+ε)$-approximate weighted Min Cut problem in $O(\log n\log\log n)$ rounds of MPC using the classic result of Karger and Stein [15]. Our work is fully-scalable in the sense that the local memory of each machine is $O(n^ε)$ for any constant $0 < ε< 1$. There are no $o(\log n)$-round MPC algorithms for Min Cut in this memory regime assuming the 1-vs-2 Cycle Conjecture holds. The exponential speedup in AMPC is the result of decoupling the different layers of the divide and conquer algorithm and solving all layers in $O(1)$ rounds.
Contrastive Learning Rivals Masked Image Modeling in Fine-tuning via Feature Distillation
Venue: arXiv cs.CV 2022
Year: 2022

Masked image modeling (MIM) learns representations with remarkably good fine-tuning performances, overshadowing previous prevalent pre-training approaches such as image classification, instance contrastive learning, and image-text alignment. In this paper, we show that the inferior fine-tuning performance of these pre-training approaches can be significantly improved by a simple post-processing in the form of feature distillation (FD). The feature distillation converts the old representations to new representations that have a few desirable properties just like those representations produced by MIM. These properties, which we aggregately refer to as optimization friendliness, are identified and analyzed by a set of attention- and optimization-related diagnosis tools. With these properties, the new representations show strong fine-tuning performance. Specifically, the contrastive self-supervised learning methods are made as competitive in fine-tuning as the state-of-the-art masked image modeling (MIM) algorithms. The CLIP models' fine-tuning performance is also significantly improved, with a CLIP ViT-L model reaching 89.0% top-1 accuracy on ImageNet-1K classification. On the 3-billion-parameter SwinV2-G model, the fine-tuning accuracy is improved by +1.5 mIoU / +1.1 mAP to 61.4 mIoU / 64.2 mAP on ADE20K semantic segmentation and COCO object detection, respectively, creating new records on both benchmarks. More importantly, our work provides a way for the future research to focus more effort on the generality and scalability of the learnt representations without being pre-occupied with optimization friendliness since it can be enhanced rather easily. The code will be available at https://github.com/SwinTransformer/Feature-Distillation.
FadMan: Federated Anomaly Detection across Multiple Attributed Networks
Venue: arXiv cs.LG 2022
Year: 2022

Anomaly subgraph detection has been widely used in various applications, ranging from cyber attack in computer networks to malicious activities in social networks. Despite an increasing need for federated anomaly detection across multiple attributed networks, only a limited number of approaches are available for this problem. Federated anomaly detection faces two major challenges. One is that isolated data in most industries are restricted share with others for data privacy and security. The other is most of the centralized approaches training based on data integration. The main idea of federated anomaly detection is aligning private anomalies from local data owners on the public anomalies from the attributed network in the server through public anomalies to federate local anomalies. In each private attributed network, the detected anomaly subgraph is aligned with an anomaly subgraph in the public attributed network. The significant public anomaly subgraphs are selected for federated private anomalies while preventing local private data leakage. The proposed algorithm FadMan is a vertical federated learning framework for public node aligned with many private nodes of different features, and is validated on two tasks correlated anomaly detection on multiple attributed networks and anomaly detection on an attributeless network using five real-world datasets. In the first scenario, FadMan outperforms competitive methods by at least 12% accuracy at 10% noise level. In the second scenario, by analyzing the distribution of abnormal nodes, we find that the nodes of traffic anomalies are associated with the event of postgraduate entrance examination on the same day.
Multimodal Masked Autoencoders Learn Transferable Representations
Venue: arXiv cs.CV 2022
Year: 2022

Building scalable models to learn from diverse, multimodal data remains an open challenge. For vision-language data, the dominant approaches are based on contrastive learning objectives that train a separate encoder for each modality. While effective, contrastive learning approaches introduce sampling bias depending on the data augmentations used, which can degrade performance on downstream tasks. Moreover, these methods are limited to paired image-text data, and cannot leverage widely-available unpaired data. In this paper, we investigate whether a large multimodal model trained purely via masked token prediction, without using modality-specific encoders or contrastive learning, can learn transferable representations for downstream tasks. We propose a simple and scalable network architecture, the Multimodal Masked Autoencoder (M3AE), which learns a unified encoder for both vision and language data via masked token prediction. We provide an empirical study of M3AE trained on a large-scale image-text dataset, and find that M3AE is able to learn generalizable representations that transfer well to downstream tasks. Surprisingly, we find that M3AE benefits from a higher text mask ratio (50-90%), in contrast to BERT whose standard masking ratio is 15%, due to the joint training of two data modalities. We also provide qualitative analysis showing that the learned representation incorporates meaningful information from both image and language. Lastly, we demonstrate the scalability of M3AE with larger model size and training time, and its flexibility to train on both paired image-text data as well as unpaired data.
When Is Recoverable Consensus Harder Than Consensus?
Venue: arXiv cs.DC 2022
Year: 2022

We study the ability of different shared object types to solve recoverable consensus using non-volatile shared memory in a system with crashes and recoveries. In particular, we compare the difficulty of solving recoverable consensus to the difficulty of solving the standard wait-free consensus problem in a system with halting failures. We focus on the model where individual processes may crash and recover and the large class of object types that are equipped with a read operation. We characterize the readable object types that can solve recoverable consensus among a given number of processes. Using this characterization, we show that the number of processes that can solve consensus using a readable type can be larger than the number of processes that can solve recoverable consensus using that type, but only slightly larger.
A Framework for Simulating Real-world Stream Data of the Internet of Things
Venue: arXiv cs.PF 2022
Year: 2022

With the rapid growth in the number of devices of the Internet of Things (IoT), the volume and types of stream data are rapidly increasing in the real world. Unfortunately, the stream data has the characteristics of infinite and periodic volatility in the real world, which cause problems with the inefficient stream processing tasks. In this study, we report our recent efforts on this issue, with a focus on simulating stream data. Firstly, we explore the characteristics of the real-world stream data of the IoT, which helps us to understand the stream data in the real world. Secondly, the pipeline of simulating stream data is proposed, which can accurately and efficiently simulate the characteristics of the stream data to improve efficiency for specific tasks. Finally, we design and implement a novel framework that can simulate various stream data for related stream processing tasks. To verify the validity of the proposed framework, we apply this framework to stream processing task running in the stream processing system. The experimental results reveal that the related stream processing task is accelerated by at least 24 times using our proposed simulation framework with the premise of ensuring volatility and trends of stream data.
Temporal graph patterns by timed automata
Venue: arXiv cs.DB 2022
Year: 2022

Temporal graphs represent graph evolution over time, and have been receiving considerable research attention. Work on expressing temporal graph patterns or discovering temporal motifs typically assumes relatively simple temporal constraints, such as journeys or, more generally, existential constraints, possibly with finite delays. In this paper we propose to use timed automata to express temporal constraints, leading to a general and powerful notion of temporal basic graph pattern (BGP). The new difficulty is the evaluation of the temporal constraint on a large set of matchings. An important benefit of timed automata is that they support an iterative state assignment, which can be useful for early detection of matches and pruning of non-matches. We introduce algorithms to retrieve all instances of a temporal BGP match in a graph, and present results of an extensive experimental evaluation, demonstrating interesting performance trade-offs. We show that an on-demand algorithm that processes total matchings incrementally over time is preferable when dealing with cyclic patterns on sparse graphs. On acyclic patterns or dense graphs, and when connectivity of partial matchings can be guaranteed, the best performance is achieved by maintaining partial matchings over time and allowing automaton evaluation to be fully incremental.
Towards Communication-Learning Trade-off for Federated Learning at the Network Edge
Venue: arXiv cs.LG 2022
Year: 2022

In this letter, we study a wireless federated learning (FL) system where network pruning is applied to local users with limited resources. Although pruning is beneficial to reduce FL latency, it also deteriorates learning performance due to the information loss. Thus, a trade-off problem between communication and learning is raised. To address this challenge, we quantify the effects of network pruning and packet error on the learning performance by deriving the convergence rate of FL with a non-convex loss function. Then, closed-form solutions for pruning control and bandwidth allocation are proposed to minimize the weighted sum of FL latency and FL performance. Finally, numerical results demonstrate that 1) our proposed solution can outperform benchmarks in terms of cost reduction and accuracy guarantee, and 2) a higher pruning rate would bring less communication overhead but also worsen FL accuracy, which is consistent with our theoretical analysis.
Investigating End-user Acceptance of Last-mile Delivery by Autonomous Vehicles in the United States
Venue: arXiv cs.CY 2022
Year: 2022

This paper investigates the end-user acceptance of last-mile delivery carried out by autonomous vehicles within the United States. A total of 296 participants were presented with information on this technology and then asked to complete a questionnaire on their perceptions to gauge their behavioral intention concerning acceptance. Structural equation modeling of the partial least squares flavor (PLS-SEM) was employed to analyze the collected data. The results indicated that the perceived usefulness of the technology played the greatest role in end-user acceptance decisions, followed by the influence of others, and then the enjoyment received by interacting with the technology. Furthermore, the perception of risk associated with using autonomous delivery vehicles for last-mile delivery led to a decrease in acceptance. However, most participants did not perceive the use of this technology to be risky. The paper concludes by summarizing the implications our findings have on the respective stakeholders and proposing the next steps in this area of research.
Contrastive Learning for Multi-Modal Automatic Code Review
Venue: arXiv cs.SE 2022
Year: 2022

Automatic code review (ACR), aiming to relieve manual inspection costs, is an indispensable and essential task in software engineering. The existing works only use the source code fragments to predict the results, missing the exploitation of developer's comments. Thus, we present a Multi-Modal Apache Automatic Code Review dataset (MACR) for the Multi-Modal ACR task. The release of this dataset would push forward the research in this field. Based on it, we propose a Contrastive Learning based Multi-Modal Network (CLMN) to deal with the Multi-Modal ACR task. Concretely, our model consists of a code encoding module and a text encoding module. For each module, we use the dropout operation as minimal data augmentation. Then, the contrastive learning method is adopted to pre-train the module parameters. Finally, we combine the two encoders to fine-tune the CLMN to decide the results of Multi-Modal ACR. Experimental results on the MACR dataset illustrate that our proposed model outperforms the state-of-the-art methods.
MC-GEN:Multi-level Clustering for Private Synthetic Data Generation
Venue: arXiv cs.LG 2022
Year: 2022

With the development of machine learning and data science, data sharing is very common between companies and research institutes to avoid data scarcity. However, sharing original datasets that contain private information can cause privacy leakage. A reliable solution is to utilize private synthetic datasets which preserve statistical information from original datasets. In this paper, we propose MC-GEN, a privacy-preserving synthetic data generation method under differential privacy guarantee for machine learning classification tasks. MC-GEN applies multi-level clustering and differential private generative model to improve the utility of synthetic data. In the experimental evaluation, we evaluated the effects of parameters and the effectiveness of MC-GEN. The results showed that MC-GEN can achieve significant effectiveness under certain privacy guarantees on multiple classification tasks. Moreover, we compare MC-GEN with three existing methods. The results showed that MC-GEN outperforms other methods in terms of utility.
Deep Learning with Label Noise: A Hierarchical Approach
Venue: arXiv cs.LG 2022
Year: 2022

Deep neural networks are susceptible to label noise. Existing methods to improve robustness, such as meta-learning and regularization, usually require significant change to the network architecture or careful tuning of the optimization procedure. In this work, we propose a simple hierarchical approach that incorporates a label hierarchy when training the deep learning models. Our approach requires no change of the network architecture or the optimization procedure. We investigate our hierarchical network through a wide range of simulated and real datasets and various label noise types. Our hierarchical approach improves upon regular deep neural networks in learning with label noise. Combining our hierarchical approach with pre-trained models achieves state-of-the-art performance in real-world noisy datasets.
Fine-Grained Buy-Many Mechanisms Are Not Much Better Than Bundling
Venue: arXiv cs.GT 2022
Year: 2022

Multi-item revenue-optimal mechanisms are known to be extremely complex, often offering buyers randomized lotteries of goods. In the standard buy-one model, it is known that optimal mechanisms can yield revenue infinitely higher than that of any "simple" mechanism -- the ones with size polynomial in the number of items -- even with just two items and a single buyer (Briest et al. 2015, Hart and Nisan 2017). We introduce a new parameterized class of mechanisms, buy-$k$ mechanisms, which smoothly interpolate between the classical buy-one mechanisms and the recently studied buy-many mechanisms (Chawla et al. 2019, Chawla et al. 2020, Chawla et al. 2022). Buy-$k$ mechanisms allow the buyer to buy up to $k$ many menu options. We show that restricting the seller to the class of buy-$n$ incentive-compatible mechanisms suffices to overcome the bizarre, infinite revenue properties of the buy-one model. Our main result is that the revenue gap with respect to bundling, an extremely simple mechanism, is bounded by $O(n^2)$ for any arbitrarily correlated distribution $\mathcal{D}$ over $n$ items for the case of an additive buyer. Our techniques also allow us to prove similar upper bounds for arbitrary monotone valuations, albeit with an exponential factor in the approximation. On the negative side, we show that allowing the buyer to purchase a small number of menu options does not suffice to guarantee sub-exponential approximations, even when we weaken the benchmark to the optimal buy-$k$ deterministic mechanism. If an additive buyer is only allowed to buy $k = Θ(n^{1/2-\varepsilon})$ many menu options, the gap between the revenue-optimal deterministic buy-$k$ mechanism and bundling may be exponential in $n$. In particular, this implies that no "simple" mechanism can obtain a sub-exponential approximation in this regime.
Feature subset selection for kernel SVM classification via mixed-integer optimization
Venue: arXiv cs.LG 2022
Year: 2022

We study the mixed-integer optimization (MIO) approach to feature subset selection in nonlinear kernel support vector machines (SVMs) for binary classification. First proposed for linear regression in the 1970s, this approach has recently moved into the spotlight with advances in optimization algorithms and computer hardware. The goal of this paper is to establish an MIO approach for selecting the best subset of features for kernel SVM classification. To measure the performance of subset selection, we use the kernel-target alignment, which is the distance between the centroids of two response classes in a high-dimensional feature space. We propose a mixed-integer linear optimization (MILO) formulation based on the kernel-target alignment for feature subset selection, and this MILO problem can be solved to optimality using optimization software. We also derive a reduced version of the MILO problem to accelerate our MILO computations. Experimental results show good computational efficiency for our MILO formulation with the reduced problem. Moreover, our method can often outperform the linear-SVM-based MILO formulation and recursive feature elimination in prediction performance, especially when there are relatively few data instances.
Speech Augmentation Based Unsupervised Learning for Keyword Spotting
Venue: arXiv cs.SD 2022
Year: 2022

In this paper, we investigated a speech augmentation based unsupervised learning approach for keyword spotting (KWS) task. KWS is a useful speech application, yet also heavily depends on the labeled data. We designed a CNN-Attention architecture to conduct the KWS task. CNN layers focus on the local acoustic features, and attention layers model the long-time dependency. To improve the robustness of KWS model, we also proposed an unsupervised learning method. The unsupervised loss is based on the similarity between the original and augmented speech features, as well as the audio reconstructing information. Two speech augmentation methods are explored in the unsupervised learning: speed and intensity. The experiments on Google Speech Commands V2 Dataset demonstrated that our CNN-Attention model has competitive results. Moreover, the augmentation based unsupervised learning could further improve the classification accuracy of KWS task. In our experiments, with augmentation based unsupervised learning, our KWS model achieves better performance than other unsupervised methods, such as CPC, APC, and MPC.
Object-wise Masked Autoencoders for Fast Pre-training
Venue: arXiv cs.CV 2022
Year: 2022

Self-supervised pre-training for images without labels has recently achieved promising performance in image classification. The success of transformer-based methods, ViT and MAE, draws the community's attention to the design of backbone architecture and self-supervised task. In this work, we show that current masked image encoding models learn the underlying relationship between all objects in the whole scene, instead of a single object representation. Therefore, those methods bring a lot of compute time for self-supervised pre-training. To solve this issue, we introduce a novel object selection and division strategy to drop non-object patches for learning object-wise representations by selective reconstruction with interested region masks. We refer to this method ObjMAE. Extensive experiments on four commonly-used datasets demonstrate the effectiveness of our model in reducing the compute cost by 72% while achieving competitive performance. Furthermore, we investigate the inter-object and intra-object relationship and find that the latter is crucial for self-supervised pre-training.
Do We Really Need to Use Constraint Violation in Constrained Evolutionary Multi-Objective Optimization?
Venue: arXiv cs.NE 2022
Year: 2022

Constraint violation has been a building block to design evolutionary multi-objective optimization algorithms for solving constrained multi-objective optimization problems. However, it is not uncommon that the constraint violation is hardly approachable in real-world black-box optimization scenarios. It is unclear that whether the existing constrained evolutionary multi-objective optimization algorithms, whose environmental selection mechanism are built upon the constraint violation, can still work or not when the formulations of the constraint functions are unknown. Bearing this consideration in mind, this paper picks up four widely used constrained evolutionary multi-objective optimization algorithms as the baseline and develop the corresponding variants that replace the constraint violation by a crisp value. From our experiments on both synthetic and real-world benchmark test problems, we find that the performance of the selected algorithms have not been significantly influenced when the constraint violation is not used to guide the environmental selection.
Strengthening Skeletal Action Recognizers via Leveraging Temporal Patterns
Venue: arXiv cs.CV 2022
Year: 2022

Skeleton sequences are compact and lightweight. Numerous skeleton-based action recognizers have been proposed to classify human behaviors. In this work, we aim to incorporate components that are compatible with existing models and further improve their accuracy. To this end, we design two temporal accessories: discrete cosine encoding (DCE) and chronological loss (CRL). DCE facilitates models to analyze motion patterns from the frequency domain and meanwhile alleviates the influence of signal noise. CRL guides networks to explicitly capture the sequence's chronological order. These two components consistently endow many recently-proposed action recognizers with accuracy boosts, achieving new state-of-the-art (SOTA) accuracy on two large datasets.