OpenRaiser/Intern-Atlas huggingface dataset:
Maintaining an EDCS in General Graphs: Simpler, Density-Sensitive and with Worst-Case Time Bounds
Venue: arXiv cs.DS 2021
Year: 2021

In their breakthrough ICALP'15 paper, Bernstein and Stein presented an algorithm for maintaining a $(3/2+ε)$-approximate maximum matching in fully dynamic {\em bipartite} graphs with a {\em worst-case} update time of $O_ε(m^{1/4})$; we use the $O_ε$ notation to suppress the $ε$-dependence. Their main technical contribution was in presenting a new type of bounded-degree subgraph, which they named an {\em edge degree constrained subgraph (EDCS)}, which contains a large matching -- of size that is smaller than the maximum matching size of the entire graph by at most a factor of $3/2+ε$. They demonstrate that the EDCS can be maintained with a worst-case update time of $O_ε(m^{1/4})$, and their main result follows as a direct corollary. In their followup SODA'16 paper, Bernstein and Stein generalized their result for general graphs, achieving the same update time of $O_ε(m^{1/4})$, albeit with an amortized rather than worst-case bound. To date, the best {\em deterministic} worst-case update time bound for {\em any} better-than-2 approximate matching is $O(\sqrt{m})$ [Neiman and Solomon, STOC'13], [Gupta and Peng, FOCS'13]; allowing randomization (against an oblivious adversary) one can achieve a much better (still polynomial) update time for approximation slightly below 2 [Behnezhad, Lacki and Mirrokni, SODA'20]. In this work we\footnote{\em quasi nanos, gigantium humeris insidentes} simplify the approach of Bernstein and Stein for bipartite graphs, which allows us to generalize it for general graphs while maintaining the same bound of $O_ε(m^{1/4})$ on the {\em worst-case} update time. Moreover, our approach is {\em density-sensitive}: If the {\em arboricity} of the dynamic graph is bounded by $α$ at all times, then the worst-case update time of the algorithm is $O_ε(\sqrtα)$.
PyParSVD: A streaming, distributed and randomized singular-value-decomposition library
Venue: arXiv cs.MS 2021
Year: 2021

We introduce PyParSVD\footnote{https://github.com/Romit-Maulik/PyParSVD}, a Python library that implements a streaming, distributed and randomized algorithm for the singular value decomposition. To demonstrate its effectiveness, we extract coherent structures from scientific data. Futhermore, we show weak scaling assessments on up to 256 nodes of the Theta machine at Argonne Leadership Computing Facility, demonstrating potential for large-scale data analyses of practical data sets.
Topo2vec: Topography Embedding Using the Fractal Effect
Venue: arXiv cs.LG 2021
Year: 2021

Recent advances in deep learning have transformed many fields by introducing generic embedding spaces, capable of achieving great predictive performance with minimal labeling effort. The geology field has not yet met such success. In this work, we introduce an extension for self-supervised learning techniques tailored for exploiting the fractal-effect in remote-sensing images. The fractal-effect assumes that the same structures (for example rivers, peaks and saddles) will appear in all scales. We demonstrate our method's effectiveness on elevation data, we also use the effect in inference. We perform an extensive analysis on several classification tasks and emphasize its effectiveness in detecting the same class on different scales. To the best of our knowledge, it is the first attempt to build a generic representation for topographic images.
Sentence-T5: Scalable Sentence Encoders from Pre-trained Text-to-Text Models
Venue: arXiv cs.CL 2021
Year: 2021

We provide the first exploration of sentence embeddings from text-to-text transformers (T5). Sentence embeddings are broadly useful for language processing tasks. While T5 achieves impressive performance on language tasks cast as sequence-to-sequence mapping problems, it is unclear how to produce sentence embeddings from encoder-decoder models. We investigate three methods for extracting T5 sentence embeddings: two utilize only the T5 encoder and one uses the full T5 encoder-decoder model. To support our investigation, we establish a new sentence representation transfer benchmark, SentGLUE, which extends the SentEval toolkit to nine tasks from the GLUE benchmark. Our encoder-only models outperforms Sentence-BERT and SimCSE sentence embeddings on both SentEval and SentGLUE transfer tasks, including semantic textual similarity (STS). Scaling up T5 from millions to billions of parameters is found to produce consistent further improvements. Finally, our encoder-decoder method achieves a new state-of-the-art on STS when using sentence embeddings. Our models are released at https://tfhub.dev/google/collections/sentence-t5/1.
CenterPoly: real-time instance segmentation using bounding polygons
Venue: arXiv cs.CV 2021
Year: 2021

We present a novel method, called CenterPoly, for real-time instance segmentation using bounding polygons. We apply it to detect road users in dense urban environments, making it suitable for applications in intelligent transportation systems like automated vehicles. CenterPoly detects objects by their center keypoint while predicting a fixed number of polygon vertices for each object, thus performing detection and segmentation in parallel. Most of the network parameters are shared by the network heads, making it fast and lightweight enough to run at real-time speed. To properly convert mask ground-truth to polygon ground-truth, we designed a vertex selection strategy to facilitate the learning of the polygons. Additionally, to better segment overlapping objects in dense urban scenes, we also train a relative depth branch to determine which instances are closer and which are further, using available weak annotations. We propose several models with different backbones to show the possible speed / accuracy trade-offs. The models were trained and evaluated on Cityscapes, KITTI and IDD and the results are reported on their public benchmark, which are state-of-the-art at real-time speeds. Code is available at https://github.com/hu64/CenterPoly
Augmenting Implicit Neural Shape Representations with Explicit Deformation Fields
Venue: arXiv cs.CV 2021
Year: 2021

Implicit neural representation is a recent approach to learn shape collections as zero level-sets of neural networks, where each shape is represented by a latent code. So far, the focus has been shape reconstruction, while shape generalization was mostly left to generic encoder-decoder or auto-decoder regularization. In this paper we advocate deformation-aware regularization for implicit neural representations, aiming at producing plausible deformations as latent code changes. The challenge is that implicit representations do not capture correspondences between different shapes, which makes it difficult to represent and regularize their deformations. Thus, we propose to pair the implicit representation of the shapes with an explicit, piecewise linear deformation field, learned as an auxiliary function. We demonstrate that, by regularizing these deformation fields, we can encourage the implicit neural representation to induce natural deformations in the learned shape space, such as as-rigid-as-possible deformations.
A Framework for Neural Topic Modeling of Text Corpora
Venue: arXiv cs.CL 2021
Year: 2021

Topic Modeling refers to the problem of discovering the main topics that have occurred in corpora of textual data, with solutions finding crucial applications in numerous fields. In this work, inspired by the recent advancements in the Natural Language Processing domain, we introduce FAME, an open-source framework enabling an efficient mechanism of extracting and incorporating textual features and utilizing them in discovering topics and clustering text documents that are semantically similar in a corpus. These features range from traditional approaches (e.g., frequency-based) to the most recent auto-encoding embeddings from transformer-based language models such as BERT model family. To demonstrate the effectiveness of this library, we conducted experiments on the well-known News-Group dataset. The library is available online.
Unified Representation of Geometric Primitives for Graph-SLAM Optimization Using Decomposed Quadrics
Venue: arXiv cs.RO 2021
Year: 2021

In Simultaneous Localization And Mapping (SLAM) problems, high-level landmarks have the potential to build compact and informative maps compared to traditional point-based landmarks. In this work, we focus on the parameterization of frequently used geometric primitives including points, lines, planes, ellipsoids, cylinders, and cones. We first present a unified representation based on quadrics, leading to a consistent and concise formulation. Then we further study a decomposed model of quadrics that discloses the symmetric and degenerated properties of a primitive. Based on the decomposition, we develop geometrically meaningful quadrics factors in the settings of a graph-SLAM problem. Then in simulation experiments, it is shown that the decomposed formulation has better efficiency and robustness to observation noises than baseline parameterizations. Finally, in real-world experiments, the proposed back-end framework is demonstrated to be capable of building compact and regularized maps.
Application of Adversarial Examples to Physical ECG Signals
Venue: arXiv cs.LG 2021
Year: 2021

This work aims to assess the reality and feasibility of the adversarial attack against cardiac diagnosis system powered by machine learning algorithms. To this end, we introduce adversarial beats, which are adversarial perturbations tailored specifically against electrocardiograms (ECGs) beat-by-beat classification system. We first formulate an algorithm to generate adversarial examples for the ECG classification neural network model, and study its attack success rate. Next, to evaluate its feasibility in a physical environment, we mount a hardware attack by designing a malicious signal generator which injects adversarial beats into ECG sensor readings. To the best of our knowledge, our work is the first in evaluating the proficiency of adversarial examples for ECGs in a physical setup. Our real-world experiments demonstrate that adversarial beats successfully manipulated the diagnosis results 3-5 times out of 40 attempts throughout the course of 2 minutes. Finally, we discuss the overall feasibility and impact of the attack, by clearly defining motives and constraints of expected attackers along with our experimental results.
Uniformity Testing in the Shuffle Model: Simpler, Better, Faster
Venue: arXiv cs.DS 2021
Year: 2021

Uniformity testing, or testing whether independent observations are uniformly distributed, is the prototypical question in distribution testing. Over the past years, a line of work has been focusing on uniformity testing under privacy constraints on the data, and obtained private and data-efficient algorithms under various privacy models such as central differential privacy (DP), local privacy (LDP), pan-privacy, and, very recently, the shuffle model of differential privacy. In this work, we considerably simplify the analysis of the known uniformity testing algorithm in the shuffle model, and, using a recent result on "privacy amplification via shuffling," provide an alternative algorithm attaining the same guarantees with an elementary and streamlined argument.
Weakly-supervised Joint Anomaly Detection and Classification
Venue: arXiv cs.CV 2021
Year: 2021

Anomaly activities such as robbery, explosion, accidents, etc. need immediate actions for preventing loss of human life and property in real world surveillance systems. Although the recent automation in surveillance systems are capable of detecting the anomalies, but they still need human efforts for categorizing the anomalies and taking necessary preventive actions. This is due to the lack of methodology performing both anomaly detection and classification for real world scenarios. Thinking of a fully automatized surveillance system, which is capable of both detecting and classifying the anomalies that need immediate actions, a joint anomaly detection and classification method is a pressing need. The task of joint detection and classification of anomalies becomes challenging due to the unavailability of dense annotated videos pertaining to anomalous classes, which is a crucial factor for training modern deep architecture. Furthermore, doing it through manual human effort seems impossible. Thus, we propose a method that jointly handles the anomaly detection and classification in a single framework by adopting a weakly-supervised learning paradigm. In weakly-supervised learning instead of dense temporal annotations, only video-level labels are sufficient for learning. The proposed model is validated on a large-scale publicly available UCF-Crime dataset, achieving state-of-the-art results.
Spatiotemporal Texture Reconstruction for Dynamic Objects Using a Single RGB-D Camera
Venue: arXiv cs.CV 2021
Year: 2021

This paper presents an effective method for generating a spatiotemporal (time-varying) texture map for a dynamic object using a single RGB-D camera. The input of our framework is a 3D template model and an RGB-D image sequence. Since there are invisible areas of the object at a frame in a single-camera setup, textures of such areas need to be borrowed from other frames. We formulate the problem as an MRF optimization and define cost functions to reconstruct a plausible spatiotemporal texture for a dynamic object. Experimental results demonstrate that our spatiotemporal textures can reproduce the active appearances of captured objects better than approaches using a single texture map.
A Contactless Fingerprint Recognition System
Venue: arXiv cs.CV 2021
Year: 2021

Fingerprints are one of the most widely explored biometric traits. Specifically, contact-based fingerprint recognition systems reign supreme due to their robustness, portability and the extensive research work done in the field. However, these systems suffer from issues such as hygiene, sensor degradation due to constant physical contact, and latent fingerprint threats. In this paper, we propose an approach for developing a contactless fingerprint recognition system that captures finger photo from a distance using an image sensor in a suitable environment. The captured finger photos are then processed further to obtain global and local (minutiae-based) features. Specifically, a Siamese convolutional neural network (CNN) is designed to extract global features from a given finger photo. The proposed system computes matching scores from CNN-based features and minutiae-based features. Finally, the two scores are fused to obtain the final matching score between the probe and reference fingerprint templates. Most importantly, the proposed system is developed using the Nvidia Jetson Nano development kit, which allows us to perform contactless fingerprint recognition in real-time with minimum latency and acceptable matching accuracy. The performance of the proposed system is evaluated on an in-house IITI contactless fingerprint dataset (IITI-CFD) containing 105train and 100 test subjects. The proposed system achieves an equal-error-rate of 2.19% on IITI-CFD.
Does Preprocessing help in Fast Sequence Comparisons?
Venue: arXiv cs.DS 2021
Year: 2021

We study edit distance computation with preprocessing: the preprocessing algorithm acts on each string separately, and then the query algorithm takes as input the two preprocessed strings. This model is inspired by scenarios where we would like to compute edit distance between many pairs in the same pool of strings. Our results include: Permutation-LCS: If the LCS between two permutations has length $n-k$, we can compute it \textit{ exactly} with $O(n \log(n))$ preprocessing and $O(k \log(n))$ query time. Small edit distance: For general strings, if their edit distance is at most $k$, we can compute it \textit{ exactly} with $O(n\log(n))$ preprocessing and $O(k^2 \log(n))$ query time. Approximate edit distance: For the most general input, we can approximate the edit distance to within factor $(7+o(1))$ with preprocessing time $\tilde{O}(n^2)$ and query time $\tilde{O}(n^{1.5+o(1)})$. All of these results significantly improve over the state of the art in edit distance computation without preprocessing. Interestingly, by combining ideas from our algorithms with preprocessing, we provide new improved results for approximating edit distance without preprocessing in subquadratic time.
TabGNN: Multiplex Graph Neural Network for Tabular Data Prediction
Venue: arXiv cs.LG 2021
Year: 2021

Tabular data prediction (TDP) is one of the most popular industrial applications, and various methods have been designed to improve the prediction performance. However, existing works mainly focus on feature interactions and ignore sample relations, e.g., users with the same education level might have a similar ability to repay the debt. In this work, by explicitly and systematically modeling sample relations, we propose a novel framework TabGNN based on recently popular graph neural networks (GNN). Specifically, we firstly construct a multiplex graph to model the multifaceted sample relations, and then design a multiplex graph neural network to learn enhanced representation for each sample. To integrate TabGNN with the tabular solution in our company, we concatenate the learned embeddings and the original ones, which are then fed to prediction models inside the solution. Experiments on eleven TDP datasets from various domains, including classification and regression ones, show that TabGNN can consistently improve the performance compared to the tabular solution AutoFE in 4Paradigm.
ReGenMorph: Visibly Realistic GAN Generated Face Morphing Attacks by Attack Re-generation
Venue: arXiv cs.CV 2021
Year: 2021

Face morphing attacks aim at creating face images that are verifiable to be the face of multiple identities, which can lead to building faulty identity links in operations like border checks. While creating a morphed face detector (MFD), training on all possible attack types is essential to achieve good detection performance. Therefore, investigating new methods of creating morphing attacks drives the generalizability of MADs. Creating morphing attacks was performed on the image level, by landmark interpolation, or on the latent-space level, by manipulating latent vectors in a generative adversarial network. The earlier results in varying blending artifacts and the latter results in synthetic-like striping artifacts. This work presents the novel morphing pipeline, ReGenMorph, to eliminate the LMA blending artifacts by using a GAN-based generation, as well as, eliminate the manipulation in the latent space, resulting in visibly realistic morphed images compared to previous works. The generated ReGenMorph appearance is compared to recent morphing approaches and evaluated for face recognition vulnerability and attack detectability, whether as known or unknown attacks.
deep unfolding for non-negative matrix factorization with application to mutational signature analysis
Venue: arXiv cs.IT 2021
Year: 2021

Non-negative matrix factorization (NMF) is a fundamental matrix decomposition technique that is used primarily for dimensionality reduction and is increasing in popularity in the biological domain. Although finding a unique NMF is generally not possible, there are various iterative algorithms for NMF optimization that converge to locally optimal solutions. Such techniques can also serve as a starting point for deep learning methods that unroll the algorithmic iterations into layers of a deep network. Here we develop unfolded deep networks for NMF and several regularized variants in both a supervised and an unsupervised setting. We apply our method to various mutation data sets to reconstruct their underlying mutational signatures and their exposures. We demonstrate the increased accuracy of our approach over standard formulations in analyzing simulated and real mutation data.
Towards Photorealistic Colorization by Imagination
Venue: arXiv cs.CV 2021
Year: 2021

We present a novel approach to automatic image colorization by imitating the imagination process of human experts. Our imagination module is designed to generate color images that are context-correlated with black-and-white photos. Given a black-and-white image, our imagination module firstly extracts the context information, which is then used to synthesize colorful and diverse images using a conditional image synthesis network (e.g., semantic image synthesis model). We then design a colorization module to colorize the black-and-white images with the guidance of imagination for photorealistic colorization. Experimental results show that our work produces more colorful and diverse results than state-of-the-art image colorization methods. Our source codes will be publicly available.
Additive Polycyclic Codes over $\mathbb{F}_{4}$ Induced by Binary Vectors and Some Optimal Codes
Venue: arXiv cs.IT 2021
Year: 2021

In this paper we study the structure and properties of additive right and left polycyclic codes induced by a binary vector $a$ in $\mathbb{F}_{2}^{n}.$ We find the generator polynomials and the cardinality of these codes. We also study different duals for these codes. In particular, we show that if $C$ is a right polycyclic code induced by a vector $a\in \mathbb{F}_{2}^{n}$, then the Hermitian dual of $C$ is a sequential code induced by $a.$ As an application of these codes, we present examples of additive right polycyclic codes over $\mathbb{F}_{4}$ with more codewords than comparable optimal linear codes as well as optimal binary linear codes and optimal quantum codes obtained from additive right polycyclic codes over $\mathbb{F}_{4}.$
Parsing Birdsong with Deep Audio Embeddings
Venue: arXiv cs.LG 2021
Year: 2021

Monitoring of bird populations has played a vital role in conservation efforts and in understanding biodiversity loss. The automation of this process has been facilitated by both sensing technologies, such as passive acoustic monitoring, and accompanying analytical tools, such as deep learning. However, machine learning models frequently have difficulty generalizing to examples not encountered in the training data. In our work, we present a semi-supervised approach to identify characteristic calls and environmental noise. We utilize several methods to learn a latent representation of audio samples, including a convolutional autoencoder and two pre-trained networks, and group the resulting embeddings for a domain expert to identify cluster labels. We show that our approach can improve classification precision and provide insight into the latent structure of environmental acoustic datasets.
Network-wide link travel time and station waiting time estimation using automatic fare collection data: A computational graph approach
Venue: arXiv cs.LG 2021
Year: 2021

Urban rail transit (URT) system plays a dominating role in many megacities like Beijing and Hong Kong. Due to its important role and complex nature, it is always in great need for public agencies to better understand the performance of the URT system. This paper focuses on an essential and hard problem to estimate the network-wide link travel time and station waiting time using the automatic fare collection (AFC) data in the URT system, which is beneficial to better understand the system-wide real-time operation state. The emerging data-driven techniques, such as computational graph (CG) models in the machine learning field, provide a new solution for solving this problem. In this study, we first formulate a data-driven estimation optimization framework to estimate the link travel time and station waiting time. Then, we cast the estimation optimization model into a CG framework to solve the optimization problem and obtain the estimation results. The methodology is verified on a synthetic URT network and applied to a real-world URT network using the synthetic and real-world AFC data, respectively. Results show the robustness and effectiveness of the CG-based framework. To the best of our knowledge, this is the first time that the CG is applied to the URT. This study can provide critical insights to better understand the operational state in URT.