OpenRaiser/Intern-Atlas huggingface dataset:
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
Venue: arXiv cs.DS 2021
Year: 2021

We study a variant of Min Cost Flow in which the flow needs to be connected. Specifically, in the Connected Flow problem one is given a directed graph $G$, along with a set of demand vertices $D \subseteq V(G)$ with demands $\mathsf{dem}: D \rightarrow \mathbb{N}$, and costs and capacities for each edge. The goal is to find a minimum cost flow that satisfies the demands, respects the capacities and induces a (strongly) connected subgraph. This generalizes previously studied problems like the (Many Visits) TSP. We study the parameterized complexity of Connected Flow parameterized by $|D|$, the treewidth $tw$ and by vertex cover size $k$ of $G$ and provide: (i) $\mathsf{NP}$-completeness already for the case $|D|=2$ with only unit demands and capacities and no edge costs, and fixed-parameter tractability if there are no capacities, (ii) a fixed-parameter tractable $\mathcal{O}^{\star}(k^{\mathcal{O}(k)})$ time algorithm for the general case, and a kernel of size polynomial in $k$ for the special case of Many Visits TSP, (iii) a $|V(G)|^{\mathcal{O}(tw)}$ time algorithm and a matching $|V(G)|^{o(tw)}$ time conditional lower bound conditioned on the Exponential Time Hypothesis. To achieve some of our results, we significantly extend an approach by Kowalik et al.~[ESA'20].
Multi-accent Speech Separation with One Shot Learning
Venue: arXiv cs.SD 2021
Year: 2021

Speech separation is a problem in the field of speech processing that has been studied in full swing recently. However, there has not been much work studying a multi-accent speech separation scenario. Unseen speakers with new accents and noise aroused the domain mismatch problem which cannot be easily solved by conventional joint training methods. Thus, we applied MAML and FOMAML to tackle this problem and obtained higher average Si-SNRi values than joint training on almost all the unseen accents. This proved that these two methods do have the ability to generate well-trained parameters for adapting to speech mixtures of new speakers and accents. Furthermore, we found out that FOMAML obtains similar performance compared to MAML while saving a lot of time.
Self-sovereign identity as a tool for digital democracy
Venue: arXiv cs.CY 2021
Year: 2021

The importance of digital identity as a foundation for digital public services is considered. As the classical, centralised model digital identity has proven to be subject to several limitations, self-sovereign identities are proposed as replacement, especially in the context of e-government platforms and direct participation to policymaking (e.g. through e-voting tools).
Modeling of Personalized Privacy Disclosure Behavior: A Formal Method Approach
Venue: arXiv cs.CR 2021
Year: 2021

In order to create user-centric and personalized privacy management tools, the underlying models must account for individual users' privacy expectations, preferences, and their ability to control their information sharing activities. Existing studies of users' privacy behavior modeling attempt to frame the problem from a request's perspective, which lack the crucial involvement of the information owner, resulting in limited or no control of policy management. Moreover, very few of them take into the consideration the aspect of correctness, explainability, usability, and acceptance of the methodologies for each user of the system. In this paper, we present a methodology to formally model, validate, and verify personalized privacy disclosure behavior based on the analysis of the user's situational decision-making process. We use a model checking tool named UPPAAL to represent users' self-reported privacy disclosure behavior by an extended form of finite state automata (FSA), and perform reachability analysis for the verification of privacy properties through computation tree logic (CTL) formulas. We also describe the practical use cases of the methodology depicting the potential of formal technique towards the design and development of user-centric behavioral modeling. This paper, through extensive amounts of experimental outcomes, contributes several insights to the area of formal methods and user-tailored privacy behavior modeling.
User Identification across Social Networking Sites using User Profiles and Posting Patterns
Venue: arXiv cs.LG 2021
Year: 2021

With the prevalence of online social networking sites (OSNs) and mobile devices, people are increasingly reliant on a variety of OSNs for keeping in touch with family and friends, and using it as a source of information. For example, a user might utilise multiple OSNs for different purposes, such as using Flickr to share holiday pictures with family and friends, and Twitter to post short messages about their thoughts. Identifying the same user across multiple OSNs is an important task as this allows us to understand the usage patterns of users among different OSNs, make recommendations when a user registers for a new OSN, and various other useful applications. To address this problem, we proposed an algorithm based on the multilayer perceptron using various types of features, namely: (i) user profile, such as name, location, description; (ii) temporal distribution of user generated content; and (iii) embedding based on user name, real name and description. Using a Twitter and Flickr dataset of users and their posting activities, we perform an empirical study on how these features affect the performance of user identification across the two OSNs and discuss our main findings based on the different features.
Lower and Upper Bounds on the VC-Dimension of Tensor Network Models
Venue: arXiv cs.LG 2021
Year: 2021

Tensor network methods have been a key ingredient of advances in condensed matter physics and have recently sparked interest in the machine learning community for their ability to compactly represent very high-dimensional objects. Tensor network methods can for example be used to efficiently learn linear models in exponentially large feature spaces [Stoudenmire and Schwab, 2016]. In this work, we derive upper and lower bounds on the VC dimension and pseudo-dimension of a large class of tensor network models for classification, regression and completion. Our upper bounds hold for linear models parameterized by arbitrary tensor network structures, and we derive lower bounds for common tensor decomposition models~(CP, Tensor Train, Tensor Ring and Tucker) showing the tightness of our general upper bound. These results are used to derive a generalization bound which can be applied to classification with low rank matrices as well as linear classifiers based on any of the commonly used tensor decomposition models. As a corollary of our results, we obtain a bound on the VC dimension of the matrix product state classifier introduced in [Stoudenmire and Schwab, 2016] as a function of the so-called bond dimension~(i.e. tensor train rank), which answers an open problem listed by Cirac, Garre-Rubio and Pérez-García in [Cirac et al., 2019].
Notes on the H-measure of classifier performance
Venue: arXiv cs.LG 2021
Year: 2021

The H-measure is a classifier performance measure which takes into account the context of application without requiring a rigid value of relative misclassification costs to be set. Since its introduction in 2009 it has become widely adopted. This paper answers various queries which users have raised since its introduction, including questions about its interpretation, the choice of a weighting function, whether it is strictly proper, and its coherence, and relates the measure to other work.
Enhanced Separable Disentanglement for Unsupervised Domain Adaptation
Venue: arXiv cs.CV 2021
Year: 2021

Domain adaptation aims to mitigate the domain gap when transferring knowledge from an existing labeled domain to a new domain. However, existing disentanglement-based methods do not fully consider separation between domain-invariant and domain-specific features, which means the domain-invariant features are not discriminative. The reconstructed features are also not sufficiently used during training. In this paper, we propose a novel enhanced separable disentanglement (ESD) model. We first employ a disentangler to distill domain-invariant and domain-specific features. Then, we apply feature separation enhancement processes to minimize contamination between domain-invariant and domain-specific features. Finally, our model reconstructs complete feature vectors, which are used for further disentanglement during the training phase. Extensive experiments from three benchmark datasets outperform state-of-the-art methods, especially on challenging cross-domain tasks.
Any equation is a forest: Symbolic genetic algorithm for discovering open-form partial differential equations (SGA-PDE)
Venue: arXiv cs.NE 2021
Year: 2021

Partial differential equations (PDEs) are concise and understandable representations of domain knowledge, which are essential for deepening our understanding of physical processes and predicting future responses. However, the PDEs of many real-world problems are uncertain, which calls for PDE discovery. We propose the symbolic genetic algorithm (SGA-PDE) to discover open-form PDEs directly from data without prior knowledge about the equation structure. SGA-PDE focuses on the representation and optimization of PDE. Firstly, SGA-PDE uses symbolic mathematics to realize the flexible representation of any given PDE, transforms a PDE into a forest, and converts each function term into a binary tree. Secondly, SGA-PDE adopts a specially designed genetic algorithm to efficiently optimize the binary trees by iteratively updating the tree topology and node attributes. The SGA-PDE is gradient-free, which is a desirable characteristic in PDE discovery since it is difficult to obtain the gradient between the PDE loss and the PDE structure. In the experiment, SGA-PDE not only successfully discovered nonlinear Burgers' equation, Korteweg-de Vries (KdV) equation, and Chafee-Infante equation, but also handled PDEs with fractional structure and compound functions that cannot be solved by conventional PDE discovery methods.
Energy hardware and workload aware job scheduling towards interconnected HPC environments
Venue: arXiv cs.DC 2021
Year: 2021

New HPC machines are getting close to the exascale. Power consumption for those machines has been increasing, and researchers are studying ways to reduce it. A second trend is HPC machines' growing complexity, with increasing heterogeneous hardware components and different clusters architectures cooperating in the same machine. We refer to these environments with the term heterogeneous multi-cluster environments. With the aim of optimizing performance and energy consumption in these environments, this paper proposes an Energy-Aware-Multi-Cluster (EAMC) job scheduling policy. EAMC-policy is able to optimize the scheduling and placement of jobs by predicting performance and energy consumption of arriving jobs for different hardware architectures and processor frequencies, reducing workload's energy consumption, makespan, and response time. The policy assigns a different priority to each job-resource combination so that the most efficient ones are favored, while less efficient ones are still considered on a variable degree, reducing response time and increasing cluster utilization. We implemented EAMC-policy in Slurm, and we evaluated a scenario in which two CPU clusters collaborate in the same machine. Simulations of workloads running applications modeled from real-world show a reduction of response time and makespan by up to 25% and 6% while saving up to 20% of total energy consumed when compared to policies minimizing runtime, and by 49%, 26%, and 6% compared to policies minimizing energy.
DetectX -- Adversarial Input Detection using Current Signatures in Memristive XBar Arrays
Venue: arXiv cs.CR 2021
Year: 2021

Adversarial input detection has emerged as a prominent technique to harden Deep Neural Networks(DNNs) against adversarial attacks. Most prior works use neural network-based detectors or complex statistical analysis for adversarial detection. These approaches are computationally intensive and vulnerable to adversarial attacks. To this end, we propose DetectX - a hardware friendly adversarial detection mechanism using hardware signatures like Sum of column Currents (SoI) in memristive crossbars (XBar). We show that adversarial inputs have higher SoI compared to clean inputs. However, the difference is too small for reliable adversarial detection. Hence, we propose a dual-phase training methodology: Phase1 training is geared towards increasing the separation between clean and adversarial SoIs; Phase2 training improves the overall robustness against different strengths of adversarial attacks. For hardware-based adversarial detection, we implement the DetectX module using 32nm CMOS circuits and integrate it with a Neurosim-like analog crossbar architecture. We perform hardware evaluation of the Neurosim+DetectX system on the Neurosim platform using datasets-CIFAR10(VGG8), CIFAR100(VGG16) and TinyImagenet(ResNet18). Our experiments show that DetectX is 10x-25x more energy efficient and immune to dynamic adversarial attacks compared to previous state-of-the-art works. Moreover, we achieve high detection performance (ROC-AUC > 0.95) for strong white-box and black-box attacks. The code has been released at https://github.com/Intelligent-Computing-Lab-Yale/DetectX
Empathy and Hope: Resource Transfer to Model Inter-country Social Media Dynamics
Venue: arXiv cs.SI 2021
Year: 2021

The ongoing COVID-19 pandemic resulted in significant ramifications for international relations ranging from travel restrictions, global ceasefires, and international vaccine production and sharing agreements. Amidst a wave of infections in India that resulted in a systemic breakdown of healthcare infrastructure, a social welfare organization based in Pakistan offered to procure medical-grade oxygen to assist India -- a nation which was involved in four wars with Pakistan in the past few decades. In this paper, we focus on Pakistani Twitter users' response to the ongoing healthcare crisis in India. While #IndiaNeedsOxygen and #PakistanStandsWithIndia featured among the top-trending hashtags in Pakistan, divisive hashtags such as #EndiaSaySorryToKashmir simultaneously started trending. Against the backdrop of a contentious history including four wars, divisive content of this nature, especially when a country is facing an unprecedented healthcare crisis, fuels further deterioration of relations. In this paper, we define a new task of detecting \emph{supportive} content and demonstrate that existing \emph{NLP for social impact} tools can be effectively harnessed for such tasks within a quick turnaround time. We also release the first publicly available data set at the intersection of geopolitical relations and a raging pandemic in the context of India and Pakistan.
Towards Consistent Predictive Confidence through Fitted Ensembles
Venue: arXiv cs.LG 2021
Year: 2021

Deep neural networks are behind many of the recent successes in machine learning applications. However, these models can produce overconfident decisions while encountering out-of-distribution (OOD) examples or making a wrong prediction. This inconsistent predictive confidence limits the integration of independently-trained learning models into a larger system. This paper introduces separable concept learning framework to realistically measure the performance of classifiers in presence of OOD examples. In this setup, several instances of a classifier are trained on different parts of a partition of the set of classes. Later, the performance of the combination of these models is evaluated on a separate test set. Unlike current OOD detection techniques, this framework does not require auxiliary OOD datasets and does not separate classification from detection performance. Furthermore, we present a new strong baseline for more consistent predictive confidence in deep models, called fitted ensembles, where overconfident predictions are rectified by transformed versions of the original classification task. Fitted ensembles can naturally detect OOD examples without requiring auxiliary data by observing contradicting predictions among its components. Experiments on MNIST, SVHN, CIFAR-10/100, and ImageNet show fitted ensemble significantly outperform conventional ensembles on OOD examples and are possible to scale.
Long-Range Time-Synchronisation Methods in LoRaWAN-based IoT
Venue: arXiv cs.NI 2021
Year: 2021

LoRa (Long-Range) is an LPWAN (low-power wide-area network) protocol that is part of the IoT family that focusses on long-range communication of up to 14km, albeit with delay-inherent transmissions. Three IoT-based time synchronisation methodologies are analysed, and their efficacy measured through a systematic critical literature review. These include a GNSS-based method, an off-the-shelf GPS hardware resampling method, and the LongShoT method, within the context of vehicular ad-hoc networks (VANET), wireless sensor networks (WSN), and long-range wide area network (LoRaWAN) respectively. Although two of the three methods are not LoRaWAN-specific, the findings obtained from the research are applied to the context of LoRa in the proposed methodology. A methodology for selecting a time synchronisation methodology with regards to LoRa specifically is posited, whereby each requirement of synchronisation objective, energy consumption and costs, scenario and security analysis, application requirements, microcontroller requirements and transceiver requirements are taken into consideration. These are then followed by a fine-grain approach to the selection of a particular time-sync method. The resultant methodology may not only have implications in the field of research, where practitioners may adopt this literature review as a baseline understanding of time synchronisation methods and obstacles encountered toward LoRa, however developers of applications for the LoRaWAN may adapt the analysed methods outlined within.
Improving Transformer-based Sequential Recommenders through Preference Editing
Venue: arXiv cs.IR 2021
Year: 2021

One of the key challenges in Sequential Recommendation (SR) is how to extract and represent user preferences. Traditional SR methods rely on the next item as the supervision signal to guide preference extraction and representation. We propose a novel learning strategy, named preference editing. The idea is to force the SR model to discriminate the common and unique preferences in different sequences of interactions between users and the recommender system. By doing so, the SR model is able to learn how to identify common and unique user preferences, and thereby do better user preference extraction and representation. We propose a transformer based SR model, named MrTransformer (Multi-preference Transformer), that concatenates some special tokens in front of the sequence to represent multiple user preferences and makes sure they capture different aspects through a preference coverage mechanism. Then, we devise a preference editing-based self-supervised learning mechanism for training MrTransformer which contains two main operations: preference separation and preference recombination. The former separates the common and unique user preferences for a given pair of sequences. The latter swaps the common preferences to obtain recombined user preferences for each sequence. Based on the preference separation and preference recombination operations, we define two types of SSL loss that require that the recombined preferences are similar to the original ones, and the common preferences are close to each other. We carry out extensive experiments on two benchmark datasets. MrTransformer with preference editing significantly outperforms state-of-the-art SR methods in terms of Recall, MRR and NDCG. We find that long sequences whose user preferences are harder to extract and represent benefit most from preference editing.
NAX: Co-Designing Neural Network and Hardware Architecture for Memristive Xbar based Computing Systems
Venue: arXiv cs.ET 2021
Year: 2021

In-Memory Computing (IMC) hardware using Memristive Crossbar Arrays (MCAs) are gaining popularity to accelerate Deep Neural Networks (DNNs) since it alleviates the "memory wall" problem associated with von-Neumann architecture. The hardware efficiency (energy, latency and area) as well as application accuracy (considering device and circuit non-idealities) of DNNs mapped to such hardware are co-dependent on network parameters, such as kernel size, depth etc. and hardware architecture parameters such as crossbar size. However, co-optimization of both network and hardware parameters presents a challenging search space comprising of different kernel sizes mapped to varying crossbar sizes. To that effect, we propose NAX -- an efficient neural architecture search engine that co-designs neural network and IMC based hardware architecture. NAX explores the aforementioned search space to determine kernel and corresponding crossbar sizes for each DNN layer to achieve optimal tradeoffs between hardware efficiency and application accuracy. Our results from NAX show that the networks have heterogeneous crossbar sizes across different network layers, and achieves optimal hardware efficiency and accuracy considering the non-idealities in crossbars. On CIFAR-10 and Tiny ImageNet, our models achieve 0.8%, 0.2% higher accuracy, and 17%, 4% lower EDAP (energy-delay-area product) compared to a baseline ResNet-20 and ResNet-18 models, respectively.
Noisy Adaptive Group Testing via Noisy Binary Search
Venue: arXiv cs.IT 2021
Year: 2021

The group testing problem consists of determining a small set of defective items from a larger set of items based on a number of possibly-noisy tests, and has numerous practical applications. One of the defining features of group testing is whether the tests are adaptive (i.e., a given test can be chosen based on all previous outcomes) or non-adaptive (i.e., all tests must be chosen in advance). In this paper, building on the success of binary splitting techniques in noiseless group testing (Hwang, 1972), we introduce noisy group testing algorithms that apply noisy binary search as a subroutine. We provide three variations of this approach with increasing complexity, culminating in an algorithm that succeeds using a number of tests that matches the best known previously (Scarlett, 2019), while overcoming fundamental practical limitations of the existing approach, and more precisely capturing the dependence of the number of tests on the error probability. We provide numerical experiments demonstrating that adaptive group testing strategies based on noisy binary search can be highly effective in practice, using significantly fewer tests compared to state-of-the-art non-adaptive strategies.
Bailouts in Financial Networks
Venue: arXiv cs.SI 2021
Year: 2021

We consider networks of banks with assets and liabilities. Some banks may be insolvent, and a central bank can decide which insolvent banks, if any, to bail out. We view bailouts as an optimization problem where the central bank has given resources at its disposal and an objective it wants to maximize. We show that under various assumptions and for various natural objectives this optimization problem is NP-hard, and in some cases even hard to approximate. Furthermore, we also show that given a fixed central bank bailout objective, banks in the network can make new debt contracts to increase their own market value in the event of a bailout (at the expense of the central bank).