OpenRaiser/Intern-Atlas huggingface dataset:
Hybrid Semantic Recommender System for Chemical Compounds
Venue: arXiv cs.IR 2020
Year: 2020

Recommending Chemical Compounds of interest to a particular researcher is a poorly explored field. The few existent datasets with information about the preferences of the researchers use implicit feedback. The lack of Recommender Systems in this particular field presents a challenge for the development of new recommendations models. In this work, we propose a Hybrid recommender model for recommending Chemical Compounds. The model integrates collaborative-filtering algorithms for implicit feedback (Alternating Least Squares (ALS) and Bayesian Personalized Ranking(BPR)) and semantic similarity between the Chemical Compounds in the ChEBI ontology (ONTO). We evaluated the model in an implicit dataset of Chemical Compounds, CheRM. The Hybrid model was able to improve the results of state-of-the-art collaborative-filtering algorithms, especially for Mean Reciprocal Rank, with an increase of 6.7% when comparing the collaborative-filtering ALS and the Hybrid ALS_ONTO.
Learning Diverse Features with Part-Level Resolution for Person Re-Identification
Venue: arXiv cs.CV 2020
Year: 2020

Learning diverse features is key to the success of person re-identification. Various part-based methods have been extensively proposed for learning local representations, which, however, are still inferior to the best-performing methods for person re-identification. This paper proposes to construct a strong lightweight network architecture, termed PLR-OSNet, based on the idea of Part-Level feature Resolution over the Omni-Scale Network (OSNet) for achieving feature diversity. The proposed PLR-OSNet has two branches, one branch for global feature representation and the other branch for local feature representation. The local branch employs a uniform partition strategy for part-level feature resolution but produces only a single identity-prediction loss, which is in sharp contrast to the existing part-based methods. Empirical evidence demonstrates that the proposed PLR-OSNet achieves state-of-the-art performance on popular person Re-ID datasets, including Market1501, DukeMTMC-reID and CUHK03, despite its small model size.
Designing for the Long Tail of Machine Learning
Venue: arXiv cs.HC 2020
Year: 2020

Recent technical advances has made machine learning (ML) a promising component to include in end user facing systems. However, user experience (UX) practitioners face challenges in relating ML to existing user-centered design processes and how to navigate the possibilities and constraints of this design space. Drawing on our own experience, we characterize designing within this space as navigating trade-offs between data gathering, model development and designing valuable interactions for a given model performance. We suggest that the theoretical description of how machine learning performance scales with training data can guide designers in these trade-offs as well as having implications for prototyping. We exemplify the learning curve's usage by arguing that a useful pattern is to design an initial system in a bootstrap phase that aims to exploit the training effect of data collected at increasing orders of magnitude.
VeSPA: Vehicular Security and Privacy-preserving Architecture
Venue: arXiv cs.CR 2020
Year: 2020

Standardization and harmonization efforts have reached a consensus towards using a special-purpose Vehicular Public-Key Infrastructure (VPKI) in upcoming Vehicular Communication (VC) systems. However, there are still several technical challenges with no conclusive answers; one such an important yet open challenge is the acquisition of short-term credentials, pseudonym: how should each vehicle interact with the VPKI, e.g., how frequently and for how long? Should each vehicle itself determine the pseudonym lifetime? Answering these questions is far from trivial. Each choice can affect both the user privacy and the system performance and possibly, as a result, its security. In this paper, we make a novel systematic effort to address this multifaceted question. We craft three generally applicable policies and experimentally evaluate the VPKI system performance, leveraging two large-scale mobility datasets. We consider the most promising, in terms of efficiency, pseudonym acquisition policies; we find that within this class of policies, the most promising policy in terms of privacy protection can be supported with moderate overhead. Moreover, in all cases, this work is the first to provide tangible evidence that the state-of-the-art VPKI can serve sizable areas or domain with modest computing resources.
R2DE: a NLP approach to estimating IRT parameters of newly generated questions
Venue: arXiv cs.LG 2020
Year: 2020

The main objective of exams consists in performing an assessment of students' expertise on a specific subject. Such expertise, also referred to as skill or knowledge level, can then be leveraged in different ways (e.g., to assign a grade to the students, to understand whether a student might need some support, etc.). Similarly, the questions appearing in the exams have to be assessed in some way before being used to evaluate students. Standard approaches to questions' assessment are either subjective (e.g., assessment by human experts) or introduce a long delay in the process of question generation (e.g., pretesting with real students). In this work we introduce R2DE (which is a Regressor for Difficulty and Discrimination Estimation), a model capable of assessing newly generated multiple-choice questions by looking at the text of the question and the text of the possible choices. In particular, it can estimate the difficulty and the discrimination of each question, as they are defined in Item Response Theory. We also present the results of extensive experiments we carried out on a real world large scale dataset coming from an e-learning platform, showing that our model can be used to perform an initial assessment of newly created questions and ease some of the problems that arise in question generation.
Geometric Proxies for Live RGB-D Stream Enhancement and Consolidation
Venue: arXiv cs.CV 2020
Year: 2020

We propose a geometric superstructure for unified real-time processing of RGB-D data. Modern RGB-D sensors are widely used for indoor 3D capture, with applications ranging from modeling to robotics, through augmented reality. Nevertheless, their use is limited by their low resolution, with frames often corrupted with noise, missing data and temporal inconsistencies. Our approach consists in generating and updating through time a single set of compact local statistics parameterized over detected geometric proxies, which are fed from raw RGB-D data. Our proxies provide several processing primitives, which improve the quality of the RGB-D stream on the fly or lighten further operations. Experimental results confirm that our lightweight analysis framework copes well with embedded execution as well as moderate memory and computational capabilities compared to state-of-the-art methods. Processing RGB-D data with our proxies allows noise and temporal flickering removal, hole filling and resampling. As a substitute of the observed scene, our proxies can additionally be applied to compression and scene reconstruction. We present experiments performed with our framework in indoor scenes of different natures within a recent open RGB-D dataset.
Proactive Certificate Validation for VANETs
Venue: arXiv cs.CR 2020
Year: 2020

Security and privacy in Vehicular Ad-hoc Networks (VANETs) mandates use of short-lived credentials (pseudonyms) and cryptographic key pairs. This implies significant computational overhead for vehicles, needing to validate often numerous such pseudonyms within a short period. To alleviate such a bottleneck that could even place vehicle safety at risk, we propose a proactive pseudonym validation approach based on Bloom Filters (BFs). We show that our scheme could liberate computational resources for other (safety- and time-critical) operations with reasonable communication overhead without compromising security and privacy.
Analytic Properties of Trackable Weak Models
Venue: arXiv cs.LG 2020
Year: 2020

We present several new results on the feasibility of inferring the hidden states in strongly-connected trackable weak models. Here, a weak model is a directed graph in which each node is assigned a set of colors which may be emitted when that node is visited. A hypothesis is a node sequence which is consistent with a given color sequence. A weak model is said to be trackable if the worst case number of such hypotheses grows as a polynomial in the sequence length. We show that the number of hypotheses in strongly-connected trackable models is bounded by a constant and give an expression for this constant. We also consider the problem of reconstructing which branch was taken at a node with same-colored out-neighbors, and show that it is always eventually possible to identify which branch was taken if the model is strongly connected and trackable. We illustrate these properties by assigning transition probabilities and employing standard tools for analyzing Markov chains. In addition, we present new results for the entropy rates of weak models according to whether they are trackable or not. These theorems indicate that the combination of trackability and strong connectivity dramatically simplifies the task of reconstructing which nodes were visited. This work has implications for any problem which can be described in terms of an agent traversing a colored graph, such as the reconstruction of hidden states in a hidden Markov model (HMM).
Simple and Effective Graph Autoencoders with One-Hop Linear Models
Venue: arXiv cs.LG 2020
Year: 2020

Over the last few years, graph autoencoders (AE) and variational autoencoders (VAE) emerged as powerful node embedding methods, with promising performances on challenging tasks such as link prediction and node clustering. Graph AE, VAE and most of their extensions rely on multi-layer graph convolutional networks (GCN) encoders to learn vector space representations of nodes. In this paper, we show that GCN encoders are actually unnecessarily complex for many applications. We propose to replace them by significantly simpler and more interpretable linear models w.r.t. the direct neighborhood (one-hop) adjacency matrix of the graph, involving fewer operations, fewer parameters and no activation function. For the two aforementioned tasks, we show that this simpler approach consistently reaches competitive performances w.r.t. GCN-based graph AE and VAE for numerous real-world graphs, including all benchmark datasets commonly used to evaluate graph AE and VAE. Based on these results, we also question the relevance of repeatedly using these datasets to compare complex graph AE and VAE.
Caching at Base Stations with Multi-Cluster Multicast Wireless Backhaul via Accelerated First-Order Algorithm
Venue: arXiv cs.IT 2020
Year: 2020

Cloud radio access network (C-RAN) has been recognized as a promising architecture for next-generation wireless systems to \textcolor{black}{support} the rapidly increasing demand for higher data rate. However, the performance of C-RAN is limited by the backhaul capacities, especially for the wireless deployment. While C-RAN with fixed BS caching has been demonstrated to reduce backhaul consumption, it is more challenging to further optimize the cache allocation at BSs with multi-cluster multicast backhaul, where the inter-cluster interference induces additional non-convexity to the cache optimization problem. Despite the challenges, we propose an accelerated first-order algorithm, which achieves much higher content downloading sum-rate than a second-order algorithm running for the same amount of time. Simulation results demonstrate that, by simultaneously delivering the required contents to different multicast clusters, the proposed algorithm achieves significantly higher downloading sum-rate than those of time-division single-cluster transmission schemes. Moreover, it is found that the proposed algorithm allocates larger cache sizes to the farther BSs within the nearer clusters, which provides insight to the superiority of the proposed cache allocation.
BLE Beacons for Indoor Positioning at an Interactive IoT-Based Smart Museum
Venue: arXiv cs.NI 2020
Year: 2020

The Internet of Things (IoT) can enable smart infrastructures to provide advanced services to the users. New technological advancement can improve our everyday life, even simple tasks as a visit to the museum. In this paper, an indoor localization system is presented, to enhance the user experience in a museum. In particular, the proposed system relies on Bluetooth Low Energy (BLE) beacons proximity and localization capabilities to automatically provide the users with cultural contents related to the observed artworks. At the same time, an RSS-based technique is used to estimate the location of the visitor in the museum. An Android application is developed to estimate the distance from the exhibits and collect useful analytics regarding each visit and provide a recommendation to the users. Moreover, the application implements a simple Kalman filter in the smartphone, without the need of the Cloud, to improve localization precision and accuracy. Experimental results on distance estimation, location, and detection accuracy show that BLE beacon is a promising solution for an interactive smart museum. The proposed system has been designed to be easily extensible to the IoT technologies and its effectiveness has been evaluated through experimentation.
Faster and Enhanced Inclusion-Minimal Cograph Completion
Venue: arXiv cs.DS 2020
Year: 2020

We design two incremental algorithms for computing an inclusion-minimal completion of an arbitrary graph into a cograph. The first one is able to do so while providing an additional property which is crucial in practice to obtain inclusion-minimal completions using as few edges as possible : it is able to compute a minimum-cardinality completion of the neighbourhood of the new vertex introduced at each incremental step. It runs in $O(n+m')$ time, where $m'$ is the number of edges in the completed graph. This matches the complexity of the algorithm in [Lokshtanov, Mancini and Papadopoulos 2010] and positively answers one of their open questions. Our second algorithm improves the complexity of inclusion-minimal completion to $O(n+m\log^2 n)$ when the additional property above is not required. Moreover, we prove that many very sparse graphs, having only $O(n)$ edges, require $Ω(n^2)$ edges in any of their cograph completions. For these graphs, which include many of those encountered in applications, the improvement we obtain on the complexity scales as $O(n/\log^2 n)$.
Massif: Interactive Interpretation of Adversarial Attacks on Deep Learning
Venue: arXiv cs.LG 2020
Year: 2020

Deep neural networks (DNNs) are increasingly powering high-stakes applications such as autonomous cars and healthcare; however, DNNs are often treated as "black boxes" in such applications. Recent research has also revealed that DNNs are highly vulnerable to adversarial attacks, raising serious concerns over deploying DNNs in the real world. To overcome these deficiencies, we are developing Massif, an interactive tool for deciphering adversarial attacks. Massif identifies and interactively visualizes neurons and their connections inside a DNN that are strongly activated or suppressed by an adversarial attack. Massif provides both a high-level, interpretable overview of the effect of an attack on a DNN, and a low-level, detailed description of the affected neurons. These tightly coupled views in Massif help people better understand which input features are most vulnerable or important for correct predictions.
Lower Bounds Against Sparse Symmetric Functions of ACC Circuits: Expanding the Reach of $\#$SAT Algorithms
Venue: arXiv cs.CC 2020
Year: 2020

We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in $\text{Quasi-NP} = \text{NTIME}[n^{(\log n)^{O(1)}}]$ and $\text{NEXP}$ do not have small circuits from various circuit classes ${\cal C}$, by showing that ${\cal C}$ admits non-trivial satisfiability and/or $\#$SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of non-trivial $\#$SAT algorithm for a circuit class ${\mathcal C}$. Say a symmetric Boolean function $f(x_1,\ldots,x_n)$ is sparse if it outputs $1$ on $O(1)$ values of $\sum_i x_i$. We show that for every sparse $f$, and for all "typical" ${\cal C}$, faster $\#$SAT algorithms for ${\cal C}$ circuits actually imply lower bounds against the circuit class $f \circ {\cal C}$, which may be stronger than ${\cal C}$ itself. In particular: $\#$SAT algorithms for $n^k$-size ${\cal C}$-circuits running in $2^n/n^k$ time (for all $k$) imply $\text{NEXP}$ does not have $f \circ {\cal C}$-circuits of polynomial size. $\#$SAT algorithms for $2^{n^ε}$-size ${\cal C}$-circuits running in $2^{n-n^ε}$ time (for some $ε> 0$) imply $\text{Quasi-NP}$ does not have $f \circ {\cal C}$-circuits of polynomial size. Applying $\#$SAT algorithms from the literature, one immediate corollary of our results is that $\text{Quasi-NP}$ does not have $\text{EMAJ} \circ \text{ACC}^0 \circ \text{THR}$ circuits of polynomial size, where $\text{EMAJ}$ is the "exact majority" function, improving previous lower bounds against $\text{ACC}^0$ [Williams JACM'14] and $\text{ACC}^0 \circ \text{THR}$ [Williams STOC'14], [Murray-Williams STOC'18]. This is the first nontrivial lower bound against such a circuit class.
Scientific Image Tampering Detection Based On Noise Inconsistencies: A Method And Datasets
Venue: arXiv cs.CV 2020
Year: 2020

Scientific image tampering is a problem that affects not only authors but also the general perception of the research community. Although previous researchers have developed methods to identify tampering in natural images, these methods may not thrive under the scientific setting as scientific images have different statistics, format, quality, and intentions. Therefore, we propose a scientific-image specific tampering detection method based on noise inconsistencies, which is capable of learning and generalizing to different fields of science. We train and test our method on a new dataset of manipulated western blot and microscopy imagery, which aims at emulating problematic images in science. The test results show that our method can detect various types of image manipulation in different scenarios robustly, and it outperforms existing general-purpose image tampering detection schemes. We discuss applications beyond these two types of images and suggest next steps for making detection of problematic images a systematic step in peer review and science in general.
Fine-grained Analysis on Fast Implementations of Distributed Multi-writer Atomic Registers
Venue: arXiv cs.DC 2020
Year: 2020

Distributed multi-writer atomic registers are at the heart of a large number of distributed algorithms. While enjoying the benefits of atomicity, researchers further explore fast implementations of atomic reigsters which are optimal in terms of data access latency. Though it is proved that multi-writer atomic register implementations are impossible when both read and write are required to be fast, it is still open whether implementations are impossible when only write or read is required to be fast. This work proves the impossibility of fast write implementations based on a series of chain arguments among indistiguishable executions. We also show the necessary and sufficient condition for fast read implementations by extending the results in the single-writer case. This work concludes a series of studies on fast implementations of distributed atomic registers.
Non-Negative Matrix Factorization-Convolutional Neural Network (NMF-CNN) For Sound Event Detection
Venue: arXiv cs.SD 2020
Year: 2020

The main scientific question of this year DCASE challenge, Task 4 - Sound Event Detection in Domestic Environments, is to investigate the types of data (strongly labeled synthetic data, weakly labeled data, unlabeled in domain data) required to achieve the best performing system. In this paper, we proposed a deep learning model that integrates Non-Negative Matrix Factorization (NMF) with Convolutional Neural Network (CNN). The key idea of such integration is to use NMF to provide an approximate strong label to the weakly labeled data. Such integration was able to achieve a higher event-based F1-score as compared to the baseline system (Evaluation Dataset: 30.39% vs. 23.7%, Validation Dataset: 31% vs. 25.8%). By comparing the validation results with other participants, the proposed system was ranked 8th among 19 teams (inclusive of the baseline system) in this year Task 4 challenge.
AMP: Authentication of Media via Provenance
Venue: arXiv cs.MM 2020
Year: 2020

Advances in graphics and machine learning have led to the general availability of easy-to-use tools for modifying and synthesizing media. The proliferation of these tools threatens to cast doubt on the veracity of all media. One approach to thwarting the flow of fake media is to detect modified or synthesized media through machine learning methods. While detection may help in the short term, we believe that it is destined to fail as the quality of fake media generation continues to improve. Soon, neither humans nor algorithms will be able to reliably distinguish fake versus real content. Thus, pipelines for assuring the source and integrity of media will be required---and increasingly relied upon. We propose AMP, a system that ensures the authentication of media via certifying provenance. AMP creates one or more publisher-signed manifests for a media instance uploaded by a content provider. These manifests are stored in a database allowing fast lookup from applications such as browsers. For reference, the manifests are also registered and signed by a permissioned ledger, implemented using the Confidential Consortium Framework (CCF). CCF employs both software and hardware techniques to ensure the integrity and transparency of all registered manifests. AMP, through its use of CCF, enables a consortium of media providers to govern the service while making all its operations auditable. The authenticity of the media can be communicated to the user via visual elements in the browser, indicating that an AMP manifest has been successfully located and verified.
A Pseudopolynomial Algorithm to Minimize Maximum Lateness on Multiple Related Machines
Venue: arXiv cs.DS 2020
Year: 2020

In this paper, we will find a pseudopolynomial algorithm to solve $Qm \mid \mid L_{\max}$ and then we will prove that it is impossible to get any constant-factor approximation in polynomial time, and thus also impossible to have a PTAS for this problem. We will also show that the the problem when we don't assume a fixed number of machines, $P \mid \mid L_{\max}$, is strongly NP-hard.
An authentication protocol based on chaos and zero knowledge proof
Venue: arXiv cs.CR 2020
Year: 2020

Port Knocking is a method for authenticating clients through a closed stance firewall, and authorising their requested actions, enabling severs to offer services to authenticated clients, without opening ports on the firewall. Advances in port knocking have resulted in an increase in complexity in design, preventing port knocking solutions from realising their potential. This paper proposes a novel port knocking solution, named Crucible, which is a secure method of authentication, with high usability and features of stealth, allowing servers and services to remain hidden and protected. Crucible is a stateless solution, only requiring the client memorise a command, the server's IP and a chosen password. The solution is forwarded as a method for protecting servers against attacks ranging from port scans, to zero-day exploitation. To act as a random oracle for both client and server, cryptographic hashes were generated through chaotic systems.