OpenRaiser/Intern-Atlas huggingface dataset:
Adversarial Information Bottleneck
Venue: arXiv cs.LG 2021
Year: 2021

The information bottleneck (IB) principle has been adopted to explain deep learning in terms of information compression and prediction, which are balanced by a trade-off hyperparameter. How to optimize the IB principle for better robustness and figure out the effects of compression through the trade-off hyperparameter are two challenging problems. Previous methods attempted to optimize the IB principle by introducing random noise into learning the representation and achieved state-of-the-art performance in the nuisance information compression and semantic information extraction. However, their performance on resisting adversarial perturbations is far less impressive. To this end, we propose an adversarial information bottleneck (AIB) method without any explicit assumptions about the underlying distribution of the representations, which can be optimized effectively by solving a Min-Max optimization problem. Numerical experiments on synthetic and real-world datasets demonstrate its effectiveness on learning more invariant representations and mitigating adversarial perturbations compared to several competing IB methods. In addition, we analyse the adversarial robustness of diverse IB methods contrasting with their IB curves, and reveal that IB models with the hyperparameter $β$ corresponding to the knee point in the IB curve achieve the best trade-off between compression and prediction, and has best robustness against various attacks.
Cache Placement Optimization in Mobile Edge Computing Networks with Unaware Environment -- An Extended Multi-armed Bandit Approach
Venue: arXiv cs.NI 2021
Year: 2021

Caching high-frequency reuse contents at the edge servers in the mobile edge computing (MEC) network omits the part of backhaul transmission and further releases the pressure of data traffic. However, how to efficiently decide the caching contents for edge servers is still an open problem, which refers to the cache capacity of edge servers, the popularity of each content, and the wireless channel quality during transmission. In this paper, we discuss the influence of unknown user density and popularity of content on the cache placement solution at the edge server. Specifically, towards the implementation of the cache placement solution in the practical network, there are two problems needing to be solved. First, the estimation of unknown users' preference needs a huge amount of records of users' previous requests. Second, the overlapping serving regions among edge servers cause the wrong estimation of users' preference, which hinders the individual decision of caching placement. To address the first issue, we propose a learning-based solution to adaptively optimize the cache placement policy. We develop the extended multi-armed bandit (Extended MAB), which combines the generalized global bandit (GGB) and Standard Multi-armed bandit (MAB). For the second problem, a multi-agent Extended MAB-based solution is presented to avoid the mis-estimation of parameters and achieve the decentralized cache placement policy. The proposed solution determines the primary time slot and secondary time slot for each edge server. The proposed strategies are proven to achieve the bounded regret according to the mathematical analysis. Extensive simulations verify the optimality of the proposed strategies when comparing with baselines.
Learning-Based Phase Compression and Quantization for Massive MIMO CSI Feedback with Magnitude-Aided Information
Venue: arXiv cs.IT 2021
Year: 2021

Massive MIMO wireless FDD systems are often confronted by the challenge to efficiently obtain downlink channel state information (CSI). Previous works have demonstrated the potential in CSI encoding and recovery by take advantage of uplink/downlink reciprocity between their CSI magnitudes. However, such a framework separately encodes CSI phase and magnitude. To improve CSI encoding, we propose a learning-based framework based on limited CSI feedback and magnitude-aided information. Moving beyond previous works, our proposed framework with a modified loss function enables end-to-end learning to jointly optimize the CSI magnitude and phase recovery performance. Simulations show that the framework outperforms alternate approaches for phase recovery over overall CSI recovery in indoor and outdoor scenarios.
Discovering Dense Correlated Subgraphs in Dynamic Networks
Venue: arXiv cs.SI 2021
Year: 2021

Given a dynamic network, where edges appear and disappear over time, we are interested in finding sets of edges that have similar temporal behavior and form a dense subgraph. Formally, we define the problem as the enumeration of the maximal subgraphs that satisfy specific density and similarity thresholds. To measure the similarity of the temporal behavior, we use the correlation between the binary time series that represent the activity of the edges. For the density, we study two variants based on the average degree. For these problem variants we enumerate the maximal subgraphs and compute a compact subset of subgraphs that have limited overlap. We propose an approximate algorithm that scales well with the size of the network, while achieving a high accuracy. We evaluate our framework on both real and synthetic datasets. The results of the synthetic data demonstrate the high accuracy of the approximation and show the scalability of the framework.
Weighted Ancestors in Suffix Trees Revisited
Venue: arXiv cs.DS 2021
Year: 2021

The weighted ancestor problem is a well-known generalization of the predecessor problem to trees. It is known to require $Ω(\log\log n)$ time for queries provided $O(n\mathop{\mathrm{polylog}} n)$ space is available and weights are from $[0..n]$, where $n$ is the number of tree nodes. However, when applied to suffix trees, the problem, surprisingly, admits an $O(n)$-space solution with constant query time, as was shown by Gawrychowski, Lewenstein, and Nicholson (Proc. ESA 2014). This variant of the problem can be reformulated as follows: given the suffix tree of a string $s$, we need a data structure that can locate in the tree any substring $s[p..q]$ of $s$ in $O(1)$ time (as if one descended from the root reading $s[p..q]$ along the way). Unfortunately, the data structure of Gawrychowski et al. has no efficient construction algorithm, limiting its wider usage as an algorithmic tool. In this paper we resolve this issue, describing a data structure for weighted ancestors in suffix trees with constant query time and a linear construction algorithm. Our solution is based on a novel approach using so-called irreducible LCP values.
Learning Large-scale Location Embedding From Human Mobility Trajectories with Graphs
Venue: arXiv cs.SI 2021
Year: 2021

An increasing amount of location-based service (LBS) data is being accumulated and helps to study urban dynamics and human mobility. GPS coordinates and other location indicators are normally low dimensional and only representing spatial proximity, thus difficult to be effectively utilized by machine learning models in Geo-aware applications. Existing location embedding methods are mostly tailored for specific problems that are taken place within areas of interest. When it comes to the scale of a city or even a country, existing approaches always suffer from extensive computational cost and significant data sparsity. Different from existing studies, we propose to learn representations through a GCN-aided skip-gram model named GCN-L2V by considering both spatial connection and human mobility. With a flow graph and a spatial graph, it embeds context information into vector representations. GCN-L2V is able to capture relationships among locations and provide a better notion of similarity in a spatial environment. Across quantitative experiments and case studies, we empirically demonstrate that representations learned by GCN-L2V are effective. As far as we know, this is the first study that provides a fine-grained location embedding at the city level using only LBS records. GCN-L2V is a general-purpose embedding model with high flexibility and can be applied in down-streaming Geo-aware applications.
Real-time Updating of Dynamic Social Networks for COVID-19 Vaccination Strategies
Venue: arXiv cs.SI 2021
Year: 2021

Vaccination strategy is crucial in fighting against the COVID-19 pandemic. Since the supply is limited, contact network-based interventions can be most powerful to set an optimal strategy by identifying high-risk individuals or communities. However, due to the high dimension, only partial and noisy network information can be available in practice, especially for dynamical systems where the contact networks are highly time-variant. Furthermore, numerous mutations of SARS-CoV-2 impact considerably the current infectious probability, requiring real-time network updating algorithms. In this study, we propose a sequential network updating approach based on data assimilation techniques to combine different sources of temporal information. We then prioritise the individuals with high-degree or high-centrality, obtained from the assimilated networks, for vaccination. The assimilation-based approach is compared with the standard method (based on partially observed networks) and a random selection strategy in terms of vaccination effectiveness in a SIR model. The numerical comparison is first carried out using real-world face-to-face dynamical networks collected in a high school, following by sequential multi-layer networks, generated relying on the Barabasi-Albert model emulating the department of Computing at Imperial College London in the UK as an example.
Where the Action is: Let's make Reinforcement Learning for Stochastic Dynamic Vehicle Routing Problems work!
Venue: arXiv cs.AI 2021
Year: 2021

There has been a paradigm-shift in urban logistic services in the last years; demand for real-time, instant mobility and delivery services grows. This poses new challenges to logistic service providers as the underlying stochastic dynamic vehicle routing problems (SDVRPs) require anticipatory real-time routing actions. Searching the combinatorial action space for efficient routing actions is by itself a complex task of mixed-integer programming (MIP) well-known by the operations research community. This complexity is now multiplied by the challenge of evaluating such actions with respect to their effectiveness given future dynamism and uncertainty, a potentially ideal case for reinforcement learning (RL) well-known by the computer science community. For solving SDVRPs, joint work of both communities is needed, but as we show, essentially non-existing. Both communities focus on their individual strengths leaving potential for improvement. Our survey paper highlights this potential in research originating from both communities. We point out current obstacles in SDVRPs and guide towards joint approaches to overcome them.
An Efficient Indexing and Searching Technique for Information Retrieval for Urdu Language
Venue: arXiv cs.IR 2021
Year: 2021

Indexing techniques are used to improve retrieval of data in response to certain search condition. Inverted files are mostly used for creating indexes. This paper proposes indexing technique for Urdu language. Language processing step in Index creation is different for a particular language. We discuss index creation steps specifically for Urdu language. We explore morphological rules for Urdu language and implement these rules to create Urdu stemmer. We implement our proposed technique with different implementations and compare results. We suggest that indexes should be created without stop words and also index file should be an order index file.
Towards Conversational Humor Analysis and Design
Venue: arXiv cs.CL 2021
Year: 2021

Well-defined jokes can be divided neatly into a setup and a punchline. While most works on humor today talk about a joke as a whole, the idea of generating punchlines to a setup has applications in conversational humor, where funny remarks usually occur with a non-funny context. Thus, this paper is based around two core concepts: Classification and the Generation of a punchline from a particular setup based on the Incongruity Theory. We first implement a feature-based machine learning model to classify humor. For humor generation, we use a neural model, and then merge the classical rule-based approaches with the neural approach to create a hybrid model. The idea behind being: combining insights gained from other tasks with the setup-punchline model and thus applying it to existing text generation approaches. We then use and compare our model with human written jokes with the help of human evaluators in a double-blind study.
CREATe: Clinical Report Extraction and Annotation Technology
Venue: arXiv cs.CL 2021
Year: 2021

Clinical case reports are written descriptions of the unique aspects of a particular clinical case, playing an essential role in sharing clinical experiences about atypical disease phenotypes and new therapies. However, to our knowledge, there has been no attempt to develop an end-to-end system to annotate, index, or otherwise curate these reports. In this paper, we propose a novel computational resource platform, CREATe, for extracting, indexing, and querying the contents of clinical case reports. CREATe fosters an environment of sustainable resource support and discovery, enabling researchers to overcome the challenges of information science. An online video of the demonstration can be viewed at https://youtu.be/Q8owBQYTjDc.
PyCG: Practical Call Graph Generation in Python
Venue: arXiv cs.PL 2021
Year: 2021

Call graphs play an important role in different contexts, such as profiling and vulnerability propagation analysis. Generating call graphs in an efficient manner can be a challenging task when it comes to high-level languages that are modular and incorporate dynamic features and higher-order functions. Despite the language's popularity, there have been very few tools aiming to generate call graphs for Python programs. Worse, these tools suffer from several effectiveness issues that limit their practicality in realistic programs. We propose a pragmatic, static approach for call graph generation in Python. We compute all assignment relations between program identifiers of functions, variables, classes, and modules through an inter-procedural analysis. Based on these assignment relations, we produce the resulting call graph by resolving all calls to potentially invoked functions. Notably, the underlying analysis is designed to be efficient and scalable, handling several Python features, such as modules, generators, function closures, and multiple inheritance. We have evaluated our prototype implementation, which we call PyCG, using two benchmarks: a micro-benchmark suite containing small Python programs and a set of macro-benchmarks with several popular real-world Python packages. Our results indicate that PyCG can efficiently handle thousands of lines of code in less than a second (0.38 seconds for 1k LoC on average). Further, it outperforms the state-of-the-art for Python in both precision and recall: PyCG achieves high rates of precision ~99.2%, and adequate recall ~69.9%. Finally, we demonstrate how PyCG can aid dependency impact analysis by showcasing a potential enhancement to GitHub's "security advisory" notification service using a real-world example.
Virus-MNIST: A Benchmark Malware Dataset
Venue: arXiv cs.CR 2021
Year: 2021

The short note presents an image classification dataset consisting of 10 executable code varieties and approximately 50,000 virus examples. The malicious classes include 9 families of computer viruses and one benign set. The image formatting for the first 1024 bytes of the Portable Executable (PE) mirrors the familiar MNIST handwriting dataset, such that most of the previously explored algorithmic methods can transfer with minor modifications. The designation of 9 virus families for malware derives from unsupervised learning of class labels; we discover the families with KMeans clustering that excludes the non-malicious examples. As a benchmark using deep learning methods (MobileNetV2), we find an overall 80% accuracy for virus identification by families when beneware is included. We also find that once a positive malware detection occurs (by signature or heuristics), the projection of the first 1024 bytes into a thumbnail image can classify with 87% accuracy the type of virus. The work generalizes what other malware investigators have demonstrated as promising convolutional neural networks originally developed to solve image problems but applied to a new abstract domain in pixel bytes from executable files. The dataset is available on Kaggle and Github.
Identification of Significant Permissions for Efficient Android Malware Detection
Venue: arXiv cs.CR 2021
Year: 2021

Since Google unveiled Android OS for smartphones, malware are thriving with 3Vs, i.e. volume, velocity, and variety. A recent report indicates that one out of every five business/industry mobile application leaks sensitive personal data. Traditional signature/heuristic-based malware detection systems are unable to cope up with current malware challenges and thus threaten the Android ecosystem. Therefore recently researchers have started exploring machine learning and deep learning based malware detection systems. In this paper, we performed a comprehensive feature analysis to identify the significant Android permissions and propose an efficient Android malware detection system using machine learning and deep neural network. We constructed a set of $16$ permissions ($8\%$ of the total set) derived from variance threshold, auto-encoders, and principal component analysis to build a malware detection engine that consumes less train and test time without significant compromise on the model accuracy. Our experimental results show that the Android malware detection model based on the random forest classifier is most balanced and achieves the highest area under curve score of $97.7\%$, which is better than the current state-of-art systems. We also observed that deep neural networks attain comparable accuracy to the baseline results but with a massive computational penalty.
A simple method for improving the accuracy of Chung-Lu random graph generation
Venue: arXiv cs.SI 2021
Year: 2021

Random graph models play a central role in network analysis. The Chung-Lu model, which connects nodes based on their expected degrees is of particular interest. It is widely used to generate null-graph models with expected degree sequences as well as implicitly define network measures such as modularity. Despite its popularity, practical methods for generating instances of Chung-Lu model-based graphs do relatively poor jobs in terms of accurately realizing many degree sequences. We introduce a simple method for improving the accuracy of Chung-Lu graph generation. Our method uses a Poisson approximation to define a linear system describing the expected degree sequence to be output from the model using standard generation techniques. We then use the inverse of this system to determine an appropriate input corresponding to the desired output. We give a closed form expression for this inverse and show that it may be used to drastically reduce error for many degree distributions.
Model-Agnostic Defense for Lane Detection against Adversarial Attack
Venue: arXiv cs.CV 2021
Year: 2021

Susceptibility of neural networks to adversarial attack prompts serious safety concerns for lane detection efforts, a domain where such models have been widely applied. Recent work on adversarial road patches have successfully induced perception of lane lines with arbitrary form, presenting an avenue for rogue control of vehicle behavior. In this paper, we propose a modular lane verification system that can catch such threats before the autonomous driving system is misled while remaining agnostic to the particular lane detection model. Our experiments show that implementing the system with a simple convolutional neural network (CNN) can defend against a wide gamut of attacks on lane detection models. With a 10% impact to inference time, we can detect 96% of bounded non-adaptive attacks, 90% of bounded adaptive attacks, and 98% of patch attacks while preserving accurate identification at least 95% of true lanes, indicating that our proposed verification system is effective at mitigating lane detection security risks with minimal overhead.
Robust learning under clean-label attack
Venue: arXiv cs.LG 2021
Year: 2021

We study the problem of robust learning under clean-label data-poisoning attacks, where the attacker injects (an arbitrary set of) correctly-labeled examples to the training set to fool the algorithm into making mistakes on specific test instances at test time. The learning goal is to minimize the attackable rate (the probability mass of attackable test instances), which is more difficult than optimal PAC learning. As we show, any robust algorithm with diminishing attackable rate can achieve the optimal dependence on $ε$ in its PAC sample complexity, i.e., $O(1/ε)$. On the other hand, the attackable rate might be large even for some optimal PAC learners, e.g., SVM for linear classifiers. Furthermore, we show that the class of linear hypotheses is not robustly learnable when the data distribution has zero margin and is robustly learnable in the case of positive margin but requires sample complexity exponential in the dimension. For a general hypothesis class with bounded VC dimension, if the attacker is limited to add at most $t>0$ poison examples, the optimal robust learning sample complexity grows almost linearly with $t$.
BERT-based knowledge extraction method of unstructured domain text
Venue: arXiv cs.CL 2021
Year: 2021

With the development and business adoption of knowledge graph, there is an increasing demand for extracting entities and relations of knowledge graphs from unstructured domain documents. This makes the automatic knowledge extraction for domain text quite meaningful. This paper proposes a knowledge extraction method based on BERT, which is used to extract knowledge points from unstructured specific domain texts (such as insurance clauses in the insurance industry) automatically to save manpower of knowledge graph construction. Different from the commonly used methods which are based on rules, templates or entity extraction models, this paper converts the domain knowledge points into question and answer pairs and uses the text around the answer in documents as the context. The method adopts a BERT-based model similar to BERT's SQuAD reading comprehension task. The model is fine-tuned. And it is used to directly extract knowledge points from more insurance clauses. According to the test results, the model performance is good.
Meta-Learning an Inference Algorithm for Probabilistic Programs
Venue: arXiv cs.LG 2021
Year: 2021

We present a meta-algorithm for learning a posterior-inference algorithm for restricted probabilistic programs. Our meta-algorithm takes a training set of probabilistic programs that describe models with observations, and attempts to learn an efficient method for inferring the posterior of a similar program. A key feature of our approach is the use of what we call a white-box inference algorithm that extracts information directly from model descriptions themselves, given as programs. Concretely, our white-box inference algorithm is equipped with multiple neural networks, one for each type of atomic command, and computes an approximate posterior of a given probabilistic program by analysing individual atomic commands in the program using these networks. The parameters of the networks are learnt from a training set by our meta-algorithm. We empirically demonstrate that the learnt inference algorithm generalises well to programs that are new in terms of both parameters and model structures, and report cases where our approach achieves greater test-time efficiency than alternative approaches such as HMC. The overall results show the promise as well as remaining challenges of our approach.