OpenRaiser/Intern-Atlas huggingface dataset:
Slim Graph: Practical Lossy Graph Compression for Approximate Graph Processing, Storage, and Analytics
Venue: arXiv cs.DS 2021
Year: 2021

We propose Slim Graph: the first programming model and framework for practical lossy graph compression that facilitates high-performance approximate graph processing, storage, and analytics. Slim Graph enables the developer to express numerous compression schemes using small and programmable compression kernels that can access and modify local parts of input graphs. Such kernels are executed in parallel by the underlying engine, isolating developers from complexities of parallel programming. Our kernels implement novel graph compression schemes that preserve numerous graph properties, for example connected components, minimum spanning trees, or graph spectra. Finally, Slim Graph uses statistical divergences and other metrics to analyze the accuracy of lossy graph compression. We illustrate both theoretically and empirically that Slim Graph accelerates numerous graph algorithms, reduces storage used by graph datasets, and ensures high accuracy of results. Slim Graph may become the common ground for developing, executing, and analyzing emerging lossy graph compression schemes.
Algebraic multigrid methods for saddle point systems arising from mortar contact formulations
Venue: arXiv cs.CE 2021
Year: 2021

In this paper, a fully aggregation-based algebraic multigrid strategy is developed for nonlinear contact problems of saddle point type using a mortar finite element approach. While the idea of extending multigrid methods to saddle point systems can already be found, e.g., in the context of Stokes and Oseen equations in literature, the main contributions of this work are (i) the development and open-source implementation of an interface aggregation strategy specifically suited for generating Lagrange multiplier aggregates that are required for coupling structural equilibrium equations with contact constraints and (ii) a review of saddle point smoothers in the context of constrained interface problems. The new interface aggregation strategy perfectly fits into an aggregation-based multigrid framework and can easily be combined with segregated transfer operators, which allow to preserve the saddle point structure on the coarse levels. Further analysis provides insight into saddle point smoothers applied to contact problems, while numerical experiments illustrate the robustness of the new method. We have implemented the proposed algorithm within the MueLu package of the open-source Trilinos project. Numerical examples demonstrate the robustness of the proposed method in complex dynamic contact problems as well as its scalability up to 23.9 million unknowns on 480 MPI ranks.
Gradient-based training of Gaussian Mixture Models for High-Dimensional Streaming Data
Venue: arXiv cs.LG 2021
Year: 2021

We present an approach for efficiently training Gaussian Mixture Model (GMM) by Stochastic Gradient Descent (SGD) with non-stationary, high-dimensional streaming data. Our training scheme does not require data-driven parameter initialization (e.g., k-means) and can thus be trained based on a random initialization. Furthermore, the approach allows mini-batch sizes as low as 1, which are typical for streaming-data settings. Major problems in such settings are undesirable local optima during early training phases and numerical instabilities due to high data dimensionalities. We introduce an adaptive annealing procedure to address the first problem, whereas numerical instabilities are eliminated by using an exponential-free approximation to the standard GMM log-likelihood. Experiments on a variety of visual and non-visual benchmarks show that our SGD approach can be trained completely without, for instance, k-means based centroid initialization. It also compares favorably to an online variant of Expectation-Maximization (EM) - stochastic EM (sEM), which it outperforms by a large margin for very high-dimensional data.
A simple framework for arriving at bounds on effective moduli in heterogeneous anisotropic poroelastic solids
Venue: arXiv cs.CE 2021
Year: 2021

The concepts of representative volume element (RVE), statistical homogeneity and homogeneous boundary conditions are invoked to arrive at bounds on effective moduli for heterogeneous anisotropic poroelastic solids. The homogeneous displacement boundary condition applicable to linear elasticity is replaced by a homogeneous displacement-pressure boundary condition to arrive at an upper bound within the RVE while the homogeneous traction boundary condition applicable to linear elasticity is replaced by a homogeneous traction-fluid content boundary condition to arrive at a lower bound within the RVE. Statistical homogeneity is then invoked to argue that the bounds obtained over the RVE are representative of the bounds obtained over the whole heterogeneous poroelastic solid.
Reconstruction of Strings from their Substrings Spectrum
Venue: arXiv cs.IT 2021
Year: 2021

This paper studies reconstruction of strings based upon their substrings spectrum. Under this paradigm, it is assumed that all substrings of some fixed length are received and the goal is to reconstruct the string. While many existing works assumed that substrings are received error free, we follow in this paper the noisy setup of this problem that was first studied by Gabrys and Milenkovic. The goal of this study is twofold. First we study the setup in which not all substrings in the multispectrum are received, and then we focus on the case where the read substrings are not error free. In each case we provide specific code constructions of strings that their reconstruction is guaranteed even in the presence of failure in either model. We present efficient encoding and decoding maps and analyze the cardinality of the code constructions, while studying the cases where the rates of our codes approach 1.
Detecting stuffing of a user's credentials at her own accounts
Venue: arXiv cs.CR 2021
Year: 2021

We propose a framework by which websites can coordinate to detect credential stuffing on individual user accounts. Our detection algorithm teases apart normal login behavior (involving password reuse, entering correct passwords into the wrong sites, etc.) from credential stuffing, by leveraging modern anomaly detection and carefully tracking suspicious logins. Websites coordinate using a novel private membership-test protocol, thereby ensuring that information about passwords is not leaked; this protocol is highly scalable, partly due to its use of cuckoo filters, and is more secure than similarly scalable alternatives in an important measure that we define. We use probabilistic model checking to estimate our credential-stuffing detection accuracy across a range of operating points. These methods might be of independent interest for their novel application of formal methods to estimate the usability impacts of our design. We show that even a minimal-infrastructure deployment of our framework should already support the combined login load experienced by the airline, hotel, retail, and consumer banking industries in the U.S.
Multi-Graph Transformer for Free-Hand Sketch Recognition
Venue: arXiv cs.CV 2021
Year: 2021

Learning meaningful representations of free-hand sketches remains a challenging task given the signal sparsity and the high-level abstraction of sketches. Existing techniques have focused on exploiting either the static nature of sketches with Convolutional Neural Networks (CNNs) or the temporal sequential property with Recurrent Neural Networks (RNNs). In this work, we propose a new representation of sketches as multiple sparsely connected graphs. We design a novel Graph Neural Network (GNN), the Multi-Graph Transformer (MGT), for learning representations of sketches from multiple graphs which simultaneously capture global and local geometric stroke structures, as well as temporal information. We report extensive numerical experiments on a sketch recognition task to demonstrate the performance of the proposed approach. Particularly, MGT applied on 414k sketches from Google QuickDraw: (i) achieves small recognition gap to the CNN-based performance upper bound (72.80% vs. 74.22%), and (ii) outperforms all RNN-based models by a significant margin. To the best of our knowledge, this is the first work proposing to represent sketches as graphs and apply GNNs for sketch recognition. Code and trained models are available at https://github.com/PengBoXiangShang/multigraph_transformer.
Deep Manifold Embedding for Hyperspectral Image Classification
Venue: arXiv cs.CV 2021
Year: 2021

Deep learning methods have played a more and more important role in hyperspectral image classification. However, the general deep learning methods mainly take advantage of the information of sample itself or the pairwise information between samples while ignore the intrinsic data structure within the whole data. To tackle this problem, this work develops a novel deep manifold embedding method(DMEM) for hyperspectral image classification. First, each class in the image is modelled as a specific nonlinear manifold and the geodesic distance is used to measure the correlation between the samples. Then, based on the hierarchical clustering, the manifold structure of the data can be captured and each nonlinear data manifold can be divided into several sub-classes. Finally, considering the distribution of each sub-class and the correlation between different subclasses, the DMEM is constructed to preserve the estimated geodesic distances on the data manifold between the learned low dimensional features of different samples. Experiments over three real-world hyperspectral image datasets have demonstrated the effectiveness of the proposed method.
RetroRenting: An Online Policy for Service Caching at the Edge
Venue: arXiv cs.NI 2021
Year: 2021

The rapid proliferation of shared edge computing platforms has enabled application service providers to deploy a wide variety of services with stringent latency and high bandwidth requirements. A key advantage of these platforms is that they provide pay-as-you-go flexibility by charging clients in proportion to their resource usage through short-term contracts. This affords the client significant cost-saving opportunities, by dynamically deciding when to host its service on the platform, depending on the changing intensity of requests. A natural policy for our setting is the Time-To-Live (TTL) policy. We show that TTL performs poorly both in the adversarial arrival setting, i.e., in terms of the competitive ratio, and for i.i.d. stochastic arrivals with low arrival rates, irrespective of the value of the TTL timer. We propose an online policy called RetroRenting (RR) and show that in the class of deterministic online policies, RR is order-optimal with respect to the competitive ratio. In addition, we provide performance guarantees for RR for i.i.d. stochastic arrival processes coupled with negatively associated rent cost sequences and prove that it compares well with the optimal online policy. Further, we conduct simulations using both synthetic and real world traces to compare the performance of RR with the optimal offline and online policies. The simulations show that the performance of RR is near optimal for all settings considered. Our results illustrate the universality of RR.
W-PoseNet: Dense Correspondence Regularized Pixel Pair Pose Regression
Venue: arXiv cs.CV 2021
Year: 2021

Solving 6D pose estimation is non-trivial to cope with intrinsic appearance and shape variation and severe inter-object occlusion, and is made more challenging in light of extrinsic large illumination changes and low quality of the acquired data under an uncontrolled environment. This paper introduces a novel pose estimation algorithm W-PoseNet, which densely regresses from input data to 6D pose and also 3D coordinates in model space. In other words, local features learned for pose regression in our deep network are regularized by explicitly learning pixel-wise correspondence mapping onto 3D pose-sensitive coordinates as an auxiliary task. Moreover, a sparse pair combination of pixel-wise features and soft voting on pixel-pair pose predictions are designed to improve robustness to inconsistent and sparse local features. Experiment results on the popular YCB-Video and LineMOD benchmarks show that the proposed W-PoseNet consistently achieves superior performance to the state-of-the-art algorithms.
OTEANN: Estimating the Transparency of Orthographies with an Artificial Neural Network
Venue: arXiv cs.CL 2021
Year: 2021

To transcribe spoken language to written medium, most alphabets enable an unambiguous sound-to-letter rule. However, some writing systems have distanced themselves from this simple concept and little work exists in Natural Language Processing (NLP) on measuring such distance. In this study, we use an Artificial Neural Network (ANN) model to evaluate the transparency between written words and their pronunciation, hence its name Orthographic Transparency Estimation with an ANN (OTEANN). Based on datasets derived from Wikimedia dictionaries, we trained and tested this model to score the percentage of correct predictions in phoneme-to-grapheme and grapheme-to-phoneme translation tasks. The scores obtained on 17 orthographies were in line with the estimations of other studies. Interestingly, the model also provided insight into typical mistakes made by learners who only consider the phonemic rule in reading and writing.
Fast and Accurate Transferability Measurement for Heterogeneous Multivariate Data
Venue: arXiv cs.LG 2021
Year: 2021

Given a set of heterogeneous source datasets with their classifiers, how can we quickly find the most useful source dataset for a specific target task? We address the problem of measuring transferability between source and target datasets, where the source and the target have different feature spaces and distributions. We propose Transmeter, a fast and accurate method to estimate the transferability of two heterogeneous multivariate datasets. We address three challenges in measuring transferability between two heterogeneous multivariate datasets: reducing time, minimizing domain gap, and extracting meaningful homogeneous representations. To overcome the above issues, we utilize a pre-trained source model, an adversarial network, and an encoder-decoder architecture. Extensive experiments on heterogeneous multivariate datasets show that Transmeter gives the most accurate transferability measurement with up to 10.3 times faster performance than its competitor. We also show that selecting the best source data with Transmeter followed by a full transfer leads to the best transfer accuracy and the fastest running time.
Proximity Search For Maximal Subgraph Enumeration
Venue: arXiv cs.DS 2021
Year: 2021

This paper proposes a new general technique for maximal subgraph enumeration which we call proximity search, whose aim is to design efficient enumeration algorithms for problems that could not be solved by existing frameworks. To support this claim and illustrate the technique we include output-polynomial algorithms for several problems for which output-polynomial algorithms were not known, including the enumeration of Maximal Bipartite Subgraphs, Maximal k-Degenerate Subgraphs (for bounded k), Maximal Induced Chordal Subgraphs, and Maximal Induced Trees. Using known techniques, such as reverse search, the space of all maximal solutions induces an implicit directed graph called "solution graph" or "supergraph", and solutions are enumerated by traversing it; however, nodes in this graph can have exponential out-degree, thus requiring exponential time to be spent on each solution. The novelty of proximity search is a formalization that allows us to define a better solution graph, and a technique, which we call canonical reconstruction, by which we can exploit the properties of given problems to build such graphs. This results in solution graphs whose nodes have significantly smaller (i.e., polynomial) out-degree with respect to existing approaches, but that remain strongly connected, so that all solutions can be enumerated in polynomial delay by a traversal. A drawback of this approach is the space required to keep track of visited solutions, which can be exponential: we further propose a technique to induce a parent-child relationship among solutions and achieve polynomial space when suitable conditions are met.
Exciting, Useful, Worrying, Futuristic: Public Perception of Artificial Intelligence in 8 Countries
Venue: arXiv cs.CY 2021
Year: 2021

As the influence and use of artificial intelligence (AI) have grown and its transformative potential has become more apparent, many questions have been raised regarding the economic, political, social, and ethical implications of its use. Public opinion plays an important role in these discussions, influencing product adoption, commercial development, research funding, and regulation. In this paper we present results of an in-depth survey of public opinion of artificial intelligence conducted with 10,005 respondents spanning eight countries and six continents. We report widespread perception that AI will have significant impact on society, accompanied by strong support for the responsible development and use of AI, and also characterize the public's sentiment towards AI with four key themes (exciting, useful, worrying, and futuristic) whose prevalence distinguishes response to AI in different countries.
Histogram Layers for Texture Analysis
Venue: arXiv cs.LG 2021
Year: 2021

An essential aspect of texture analysis is the extraction of features that describe the distribution of values in local, spatial regions. We present a localized histogram layer for artificial neural networks. Instead of computing global histograms as done previously, the proposed histogram layer directly computes the local, spatial distribution of features for texture analysis and parameters for the layer are estimated during backpropagation. We compare our method with state-of-the-art texture encoding methods such as the Deep Encoding Network Pooling, Deep Texture Encoding Network, Fisher Vector convolutional neural network, and Multi-level Texture Encoding and Representation on three material/texture datasets: (1) the Describable Texture Dataset; (2) an extension of the ground terrain in outdoor scenes; (3) and a subset of the Materials in Context dataset. Results indicate that the inclusion of the proposed histogram layer improves performance. The source code for the histogram layer is publicly available: https://github.com/GatorSense/Histogram_Layer.
Deep Representation Learning in Speech Processing: Challenges, Recent Advances, and Future Trends
Venue: arXiv cs.SD 2021
Year: 2021

Research on speech processing has traditionally considered the task of designing hand-engineered acoustic features (feature engineering) as a separate distinct problem from the task of designing efficient machine learning (ML) models to make prediction and classification decisions. There are two main drawbacks to this approach: firstly, the feature engineering being manual is cumbersome and requires human knowledge; and secondly, the designed features might not be best for the objective at hand. This has motivated the adoption of a recent trend in speech community towards utilisation of representation learning techniques, which can learn an intermediate representation of the input signal automatically that better suits the task at hand and hence lead to improved performance. The significance of representation learning has increased with advances in deep learning (DL), where the representations are more useful and less dependent on human knowledge, making it very conducive for tasks like classification, prediction, etc. The main contribution of this paper is to present an up-to-date and comprehensive survey on different techniques of speech representation learning by bringing together the scattered research across three distinct research areas including Automatic Speech Recognition (ASR), Speaker Recognition (SR), and Speaker Emotion Recognition (SER). Recent reviews in speech have been conducted for ASR, SR, and SER, however, none of these has focused on the representation learning from speech -- a gap that our survey aims to bridge.
Subexponential and Linear Subpacketization Coded Caching via Projective Geometry
Venue: arXiv cs.IT 2021
Year: 2021

Large gains in the rate of cache-aided broadcast communication are obtained using coded caching, but to obtain this most existing centralized coded caching schemes require that the files at the server be divisible into a large number of parts (this number is called subpacketization). In fact, most schemes require the subpacketization to be growing asymptotically as exponential in $\sqrt[\leftroot{-1}\uproot{1}r]{K}$ for some positive integer $r$ and $K$ being the number of users. On the other extreme, few schemes having subpacketization linear in $K$ are known; however, they require large number of users to exist, or they offer only little gain in the rate. In this work, we propose two new centralized coded caching schemes with low subpacketization and moderate rate gains utilizing projective geometries over finite fields. Both the schemes achieve the same asymptotic subpacketization, which is exponential in $O((\log K)^2)$ (thus improving on the $\sqrt[\leftroot{-1}\uproot{1}r]{K}$ exponent). The first scheme has a larger cache requirement but has at most a constant rate (with increasing $K$), while the second has small cache requirement but has a larger rate. As a special case of our second scheme, we get a new linear subpacketization scheme, which has a more flexible range of parameters than the existing linear subpacketization schemes. Extending our techniques, we also obtain low subpacketization schemes for other multi-receiver settings such as distributed computing and the cache-aided interference channel. We validate the performance of all our schemes via extensive numerical comparisons. For a special class of symmetric caching schemes with a given subpacketization level, we propose two new information theoretic lower bounds on the optimal rate of coded caching.
Visual-Semantic Graph Attention Networks for Human-Object Interaction Detection
Venue: arXiv cs.LG 2021
Year: 2021

In scene understanding, robotics benefit from not only detecting individual scene instances but also from learning their possible interactions. Human-Object Interaction (HOI) Detection infers the action predicate on a <human, predicate, object> triplet. Contextual information has been found critical in inferring interactions. However, most works only use local features from single human-object pair for inference. Few works have studied the disambiguating contribution of subsidiary relations made available via graph networks. Similarly, few have learned to effectively leverage visual cues along with the intrinsic semantic regularities contained in HOIs. We contribute a dual-graph attention network that effectively aggregates contextual visual, spatial, and semantic information dynamically from primary human-object relations as well as subsidiary relations through attention mechanisms for strong disambiguating power. We achieve comparable results on two benchmarks: V-COCO and HICO-DET. Code is available at \url{https://github.com/birlrobotics/vs-gats}.