OpenRaiser/Intern-Atlas huggingface dataset:
Theoretically and Practically Efficient Parallel Nucleus Decomposition
Venue: arXiv cs.DC 2022
Year: 2022

This paper studies the nucleus decomposition problem, which has been shown to be useful in finding dense substructures in graphs. We present a novel parallel algorithm that is efficient both in theory and in practice. Our algorithm achieves a work complexity matching the best sequential algorithm while also having low depth (parallel running time), which significantly improves upon the only existing parallel nucleus decomposition algorithm (Sariyuce et al., PVLDB 2018). The key to the theoretical efficiency of our algorithm is the use of a theoretically-efficient parallel algorithms for clique listing and bucketing. We introduce several new practical optimizations, including a new multi-level hash table structure to store information on cliques space-efficiently and a technique for traversing this structure cache-efficiently. On a 30-core machine with two-way hyper-threading on real-world graphs, we achieve up to a 55x speedup over the state-of-the-art parallel nucleus decomposition algorithm by Sariyuce et al., and up to a 40x self-relative parallel speedup. We are able to efficiently compute larger nucleus decompositions than prior work on several million-scale graphs for the first time.
Reinforcement Learning for Few-Shot Text Generation Adaptation
Venue: arXiv cs.CL 2022
Year: 2022

Controlling the generative model to adapt a new domain with limited samples is a difficult challenge and it is receiving increasing attention. Recently, methods based on meta-learning have shown promising results for few-shot domain adaptation. However, meta-learning-based methods usually suffer from the problem of overfitting, which results in a lack of diversity in the generated texts. To avoid this problem, in this study, a novel framework based on reinforcement learning (RL) is proposed. In this framework, to increase the sample utilization of RL and decrease its sample requirement, maximum likelihood estimation learning is incorporated into the RL process. When there are only a few in-domain samples available, experimental results on five target domains in two few-shot configurations show that this framework performs better than baselines.
Efficient formulation of a two-noded geometrically exact curved beam element
Venue: arXiv cs.CE 2022
Year: 2022

The paper extends the formulation of a 2D geometrically exact beam element proposed in our previous paper [1] to curved elastic beams. This formulation is based on equilibrium equations in their integrated form, combined with the kinematic relations and sectional equations that link the internal forces to sectional deformation variables. The resulting first-order differential equations are approximated by the finite difference scheme and the boundary value problem is converted to an initial value problem using the shooting method. The paper develops the theoretical framework based on the Navier-Bernoulli hypothesis, with a possible extension to shear-flexible beams. Numerical procedures for the evaluation of equivalent nodal forces and of the element tangent stiffness are presented in detail. Unlike standard finite element formulations, the present approach can increase accuracy by refining the integration scheme on the element level while the number of global degrees of freedom is kept constant. The efficiency and accuracy of the developed scheme are documented by seven examples that cover circular and parabolic arches, a spiral-shaped beam, and a spring-like beam with a zig-zag centerline. The proposed formulation does not exhibit any locking. No excessive stiffness is observed for coarse computational grids and the distribution of internal forces is not polluted by any oscillations. It is also shown that a cross effect in the relations between internal forces and deformation variables arises, i.e., the bending moment affects axial stretching and the normal force affects the curvature. This coupling is theoretically explained in the appendix.
Why Do Self-Supervised Models Transfer? Investigating the Impact of Invariance on Downstream Tasks
Venue: arXiv cs.CV 2022
Year: 2022

Self-supervised learning is a powerful paradigm for representation learning on unlabelled images. A wealth of effective new methods based on instance matching rely on data-augmentation to drive learning, and these have reached a rough agreement on an augmentation scheme that optimises popular recognition benchmarks. However, there is strong reason to suspect that different tasks in computer vision require features to encode different (in)variances, and therefore likely require different augmentation strategies. In this paper, we measure the invariances learned by contrastive methods and confirm that they do learn invariance to the augmentations used and further show that this invariance largely transfers to related real-world changes in pose and lighting. We show that learned invariances strongly affect downstream task performance and confirm that different downstream tasks benefit from polar opposite (in)variances, leading to performance loss when the standard augmentation strategy is used. Finally, we demonstrate that a simple fusion of representations with complementary invariances ensures wide transferability to all the diverse downstream tasks considered.
Reliable Actors with Retry Orchestration
Venue: arXiv cs.DC 2022
Year: 2022

Cloud developers have to build applications that are resilient to failures and interruptions. We advocate for a fault-tolerant programming model for the cloud based on actors, retry orchestration, and tail calls. This model builds upon persistent data stores and messages queues readily available on the cloud. Retry orchestration not only guarantees that (1) failed actor invocations will be retried but also that (2) completed invocations are never repeated and (3) it preserves a strict happen-before relationship across failures within call stacks. Tail calls can break complex tasks into simple steps to minimize re-execution during recovery. We review key application patterns and failure scenarios. We formalize a process calculus to precisely capture the mechanisms of fault tolerance in this model. We briefly describe our implementation. Using an application inspired by a typical enterprise scenario, we validate the functional correctness of our implementation and assess the impact of fault preparedness and recovery on performance.
Intriguing Findings of Frequency Selection for Image Deblurring
Venue: arXiv cs.CV 2022
Year: 2022

Blur was naturally analyzed in the frequency domain, by estimating the latent sharp image and the blur kernel given a blurry image. Recent progress on image deblurring always designs end-to-end architectures and aims at learning the difference between blurry and sharp image pairs from pixel-level, which inevitably overlooks the importance of blur kernels. This paper reveals an intriguing phenomenon that simply applying ReLU operation on the frequency domain of a blur image followed by inverse Fourier transform, i.e., frequency selection, provides faithful information about the blur pattern (e.g., the blur direction and blur level, implicitly shows the kernel pattern). Based on this observation, we attempt to leverage kernel-level information for image deblurring networks by inserting Fourier transform, ReLU operation, and inverse Fourier transform to the standard ResBlock. 1x1 convolution is further added to let the network modulate flexible thresholds for frequency selection. We term our newly built block as Res FFT-ReLU Block, which takes advantages of both kernel-level and pixel-level features via learning frequency-spatial dual-domain representations. Extensive experiments are conducted to acquire a thorough analysis on the insights of the method. Moreover, after plugging the proposed block into NAFNet, we can achieve 33.85 dB in PSNR on GoPro dataset. Our method noticeably improves backbone architectures without introducing many parameters, while maintaining low computational complexity. Code is available at https://github.com/DeepMed-Lab/DeepRFT-AAAI2023.
Self-dual twisted generalized Reed-Solomon codes
Venue: arXiv cs.IT 2022
Year: 2022

In this paper, by using some properties for linear algebra methods, the parity-check matrices for twisted generalized Reed-Solomon codes with any given hook $h$ and twist $t$ are presented, and then a sufficient and necessary condition for the twisted generalized Reed-Solomon code with $h\ge t$ to be self-dual is given. Furthermore, several classes of self-dual codes with small Singleton defect are constructed based on twisted generalized Reed-Solomon codes, especially some of these self-dual codes are MDS or NMDS.
LEGOStore: A Linearizable Geo-Distributed Store Combining Replication and Erasure Coding
Venue: arXiv cs.DC 2022
Year: 2022

We design and implement LEGOStore, an erasure coding (EC) based linearizable data store over geo-distributed public cloud data centers (DCs). For such a data store, the confluence of the following factors opens up opportunities for EC to be latency-competitive with replication: (a) the necessity of communicating with remote DCs to tolerate entire DC failures and implement linearizability; and (b) the emergence of DCs near most large population centers. LEGOStore employs an optimization framework that, for a given object, carefully chooses among replication and EC, as well as among various DC placements to minimize overall costs. To handle workload dynamism, LEGOStore employs a novel agile reconfiguration protocol. Our evaluation using a LEGOStore prototype spanning 9 Google Cloud Platform DCs demonstrates the efficacy of our ideas. We observe cost savings ranging from moderate (5-20\%) to significant (60\%) over baselines representing the state of the art while meeting tail latency SLOs. Our reconfiguration protocol is able to transition key placements in 3 to 4 inter-DC RTTs ($<$ 1s in our experiments), allowing for agile adaptation to dynamic conditions.
Generating Tree Structures for Hyperbolic Tessellations
Venue: arXiv cs.FL 2022
Year: 2022

We show an efficient algorithm for generating geodesic regular tree structures for periodic hyperbolic and Euclidean tessellations and experimentally verify its performance on tessellations.
A bifurcation threshold for contact-induced language change
Venue: arXiv cs.CL 2022
Year: 2022

One proposed mechanism of language change concerns the role played by second-language (L2) learners in situations of language contact. If sufficiently many L2 speakers are present in a speech community in relation to the number of first-language (L1) speakers, then those features which present a difficulty in L2 acquisition may be prone to disappearing from the language. This paper presents a mathematical account of such contact situations based on a stochastic model of learning and nonlinear population dynamics. The equilibria of a deterministic reduction of the model, describing a mixed population of L1 and L2 speakers, are fully characterized. Whether or not the language changes in response to the introduction of L2 learners turns out to depend on three factors: the overall proportion of L2 learners in the population, the strength of the difficulty speakers face in acquiring the language as an L2, and the language-internal utilities of the competing linguistic variants. These factors are related by a mathematical formula describing a phase transition from retention of the L2-difficult feature to its loss from both speaker populations. This supplies predictions that can be tested against empirical data. Here, the model is evaluated with the help of two case studies, morphological levelling in Afrikaans and the erosion of null subjects in Afro-Peruvian Spanish; the model is found to be broadly in agreement with the historical development in both cases.
Harmonic Centrality in Some Graph Families
Venue: arXiv cs.DM 2022
Year: 2022

One of the more recent measures of centrality in social network analysis is the normalized harmonic centrality. A variant of the closeness centrality, harmonic centrality sums the inverse of the geodesic distances of each node to other nodes where it is 0 if there is no path from one node to another. It is then normalized by dividing it by m-1, where m is the number of nodes of the graph. In this paper, we present notions regarding the harmonic centrality of some important classes of graphs.
Animal behavior classification via deep learning on embedded systems
Venue: arXiv cs.LG 2022
Year: 2022

We develop an end-to-end deep-neural-network-based algorithm for classifying animal behavior using accelerometry data on the embedded system of an artificial intelligence of things (AIoT) device installed in a wearable collar tag. The proposed algorithm jointly performs feature extraction and classification utilizing a set of infinite-impulse-response (IIR) and finite-impulse-response (FIR) filters together with a multilayer perceptron. The utilized IIR and FIR filters can be viewed as specific types of recurrent and convolutional neural network layers, respectively. We evaluate the performance of the proposed algorithm via two real-world datasets collected from total eighteen grazing beef cattle using collar tags. The results show that the proposed algorithm offers good intra- and inter-dataset classification accuracy and outperforms its closest contenders including two state-of-the-art convolutional-neural-network-based time-series classification algorithms, which are significantly more complex. We implement the proposed algorithm on the embedded system of the utilized collar tags' AIoT device to perform in-situ classification of animal behavior. We achieve real-time in-situ behavior inference from accelerometry data without imposing any strain on the available computational, memory, or energy resources of the embedded system.
Information Dispersal with Provable Retrievability for Rollups
Venue: arXiv cs.CR 2022
Year: 2022

The ability to verifiably retrieve transaction or state data stored off-chain is crucial to blockchain scaling techniques such as rollups or sharding. We formalize the problem and design a storage- and communication-efficient protocol using linear erasure-correcting codes and homomorphic vector commitments. Motivated by application requirements for rollups, our solution Semi-AVID-PR departs from earlier Verifiable Information Dispersal schemes in that we do not require comprehensive termination properties. Compared to Data Availability Oracles, under no circumstance do we fall back to returning empty blocks. Distributing a file of 22 MB among 256 storage nodes, up to 85 of which may be adversarial, requires in total ~70 MB of communication and storage, and ~41 seconds of single-thread runtime (<3 seconds on 16 threads) on an AMD Opteron 6378 processor when using the BLS12-381 curve. Our solution requires no modification to on-chain contracts of Validium rollups such as StarkWare's StarkEx. Additionally, it provides privacy of the dispersed data against honest-but-curious storage nodes. Finally, we discuss an application of our Semi-AVID-PR scheme to data availability verification schemes based on random sampling.
Longest Chain Consensus Under Bandwidth Constraint
Venue: arXiv cs.CR 2022
Year: 2022

Spamming attacks are a serious concern for consensus protocols, as witnessed by recent outages of a major blockchain, Solana. They cause congestion and excessive message delays in a real network due to its bandwidth constraints. In contrast, longest chain (LC), an important family of consensus protocols, has previously only been proven secure assuming an idealized network model in which all messages are delivered within bounded delay. This model-reality mismatch is further aggravated for Proof-of-Stake (PoS) LC where the adversary can spam the network with equivocating blocks. Hence, we extend the network model to capture bandwidth constraints, under which nodes now need to choose carefully which blocks to spend their limited download budget on. To illustrate this point, we show that 'download along the longest header chain', a natural download rule for Proof-of-Work (PoW) LC, is insecure for PoS LC. We propose a simple rule 'download towards the freshest block', formalize two common heuristics 'not downloading equivocations' and 'blocklisting', and prove in a unified framework that PoS LC with any one of these download rules is secure in bandwidth-constrained networks. In experiments, we validate our claims and showcase the behavior of these download rules under attack. By composing multiple instances of a PoS LC protocol with a suitable download rule in parallel, we obtain a PoS consensus protocol that achieves a constant fraction of the network's throughput limit even under worst-case adversarial strategies.
MM-Pyramid: Multimodal Pyramid Attentional Network for Audio-Visual Event Localization and Video Parsing
Venue: arXiv cs.CV 2022
Year: 2022

Recognizing and localizing events in videos is a fundamental task for video understanding. Since events may occur in auditory and visual modalities, multimodal detailed perception is essential for complete scene comprehension. Most previous works attempted to analyze videos from a holistic perspective. However, they do not consider semantic information at multiple scales, which makes the model difficult to localize events in different lengths. In this paper, we present a Multimodal Pyramid Attentional Network (\textbf{MM-Pyramid}) for event localization. Specifically, we first propose the attentive feature pyramid module. This module captures temporal pyramid features via several stacking pyramid units, each of them is composed of a fixed-size attention block and dilated convolution block. We also design an adaptive semantic fusion module, which leverages a unit-level attention block and a selective fusion block to integrate pyramid features interactively. Extensive experiments on audio-visual event localization and weakly-supervised audio-visual video parsing tasks verify the effectiveness of our approach.
Track Boosting and Synthetic Data Aided Drone Detection
Venue: arXiv cs.CV 2022
Year: 2022

This is the paper for the first place winning solution of the Drone vs. Bird Challenge, organized by AVSS 2021. As the usage of drones increases with lowered costs and improved drone technology, drone detection emerges as a vital object detection task. However, detecting distant drones under unfavorable conditions, namely weak contrast, long-range, low visibility, requires effective algorithms. Our method approaches the drone detection problem by fine-tuning a YOLOv5 model with real and synthetically generated data using a Kalman-based object tracker to boost detection confidence. Our results indicate that augmenting the real data with an optimal subset of synthetic data can increase the performance. Moreover, temporal information gathered by object tracking methods can increase performance further.
xFuzz: Machine Learning Guided Cross-Contract Fuzzing
Venue: arXiv cs.CR 2022
Year: 2022

Smart contract transactions are increasingly interleaved by cross-contract calls. While many tools have been developed to identify a common set of vulnerabilities, the cross-contract vulnerability is overlooked by existing tools. Cross-contract vulnerabilities are exploitable bugs that manifest in the presence of more than two interacting contracts. Existing methods are however limited to analyze a maximum of two contracts at the same time. Detecting cross-contract vulnerabilities is highly non-trivial. With multiple interacting contracts, the search space is much larger than that of a single contract. To address this problem, we present xFuzz, a machine learning guided smart contract fuzzing framework. The machine learning models are trained with novel features (e.g., word vectors and instructions) and are used to filter likely benign program paths. Comparing with existing static tools, machine learning model is proven to be more robust, avoiding directly adopting manually-defined rules in specific tools. We compare xFuzz with three state-of-the-art tools on 7,391 contracts. xFuzz detects 18 exploitable cross-contract vulnerabilities, of which 15 vulnerabilities are exposed for the first time. Furthermore, our approach is shown to be efficient in detecting non-cross-contract vulnerabilities as well -- using less than 20% time as that of other fuzzing tools, xFuzz detects twice as many vulnerabilities.
ModelPred: A Framework for Predicting Trained Model from Training Data
Venue: arXiv cs.LG 2022
Year: 2022

In this work, we propose ModelPred, a framework that helps to understand the impact of changes in training data on a trained model. This is critical for building trust in various stages of a machine learning pipeline: from cleaning poor-quality samples and tracking important ones to be collected during data preparation, to calibrating uncertainty of model prediction, to interpreting why certain behaviors of a model emerge during deployment. Specifically, ModelPred learns a parameterized function that takes a dataset $S$ as the input and predicts the model obtained by training on $S$. Our work differs from the recent work of Datamodels [1] as we aim for predicting the trained model parameters directly instead of the trained model behaviors. We demonstrate that a neural network-based set function class is capable of learning the complex relationships between the training data and model parameters. We introduce novel global and local regularization techniques to prevent overfitting and we rigorously characterize the expressive power of neural networks (NN) in approximating the end-to-end training process. Through extensive empirical investigations, we show that ModelPred enables a variety of applications that boost the interpretability and accountability of machine learning (ML), such as data valuation, data selection, memorization quantification, and model calibration.
Hierarchical Graph-Convolutional Variational AutoEncoding for Generative Modelling of Human Motion
Venue: arXiv cs.CV 2022
Year: 2022

Models of human motion commonly focus either on trajectory prediction or action classification but rarely both. The marked heterogeneity and intricate compositionality of human motion render each task vulnerable to the data degradation and distributional shift common to real-world scenarios. A sufficiently expressive generative model of action could in theory enable data conditioning and distributional resilience within a unified framework applicable to both tasks. Here we propose a novel architecture based on hierarchical variational autoencoders and deep graph convolutional neural networks for generating a holistic model of action over multiple time-scales. We show this Hierarchical Graph-convolutional Variational Autoencoder (HG-VAE) to be capable of generating coherent actions, detecting out-of-distribution data, and imputing missing data by gradient ascent on the model's posterior. Trained and evaluated on H3.6M and the largest collection of open source human motion data, AMASS, we show HG-VAE can facilitate downstream discriminative learning better than baseline models.