OpenRaiser/Intern-Atlas huggingface dataset:
Scalable Mining of Maximal Quasi-Cliques: An Algorithm-System Codesign Approach
Venue: arXiv cs.DC 2021
Year: 2021

Given a user-specified minimum degree threshold $γ$, a $γ$-quasi-clique is a subgraph $g=(V_g,E_g)$ where each vertex $v\in V_g$ connects to at least $γ$ fraction of the other vertices (i.e., $\lceil γ\cdot(|V_g|-1)\rceil$ vertices) in $g$. Quasi-clique is one of the most natural definitions for dense structures useful in finding communities in social networks and discovering significant biomolecule structures and pathways. However, mining maximal quasi-cliques is notoriously expensive. In this paper, we design parallel algorithms for mining maximal quasi-cliques on G-thinker, a recent distributed framework targeting divide-and-conquer graph mining algorithms that decomposes the mining into compute-intensive tasks to fully utilize CPU cores. However, we found that directly using G-thinker results in the straggler problem due to (i) the drastic load imbalance among different tasks and (ii) the difficulty of predicting the task running time and the time growth with task-subgraph size. We address these challenges by redesigning G-thinker's execution engine to prioritize long-running tasks for mining, and by utilizing a novel timeout strategy to effectively decompose the mining workloads of long-running tasks to improve load balancing. While this system redesign applies to many other expensive dense subgraph mining problems, this paper verifies the idea by adapting the state-of-the-art quasi-clique algorithm, Quick, to our redesigned G-thinker. We improve Quick by integrating new pruning rules, and fixing some missed boundary cases that could lead to missed results. Extensive experiments verify that our new solution scales well with the number of CPU cores, achieving 201$\times$ runtime speedup when mining a graph with 3.77M vertices and 16.5M edges in a 16-node cluster.
Consumer Wearables and Affective Computing for Wellbeing Support
Venue: arXiv cs.HC 2021
Year: 2021

Wearables equipped with pervasive sensors enable us to monitor physiological and behavioral signals in our everyday life. We propose the WellAff system able to recognize affective states for wellbeing support. It also includes health care scenarios, in particular patients with chronic kidney disease (CKD) suffering from bipolar disorders. For the need of a large-scale field study, we revised over 50 off-the-shelf devices in terms of usefulness for emotion, stress, meditation, sleep, and physical activity recognition and analysis. Their usability directly comes from the types of sensors they possess as well as the quality and availability of raw signals. We found there is no versatile device suitable for all purposes. Using Empatica E4 and Samsung Galaxy Watch, we have recorded physiological signals from 11 participants over many weeks. The gathered data enabled us to train a classifier that accurately recognizes strong affective states.
Boundaries of Flow Table Usage Reduction Algorithms Based on Elephant Flow Detection
Venue: arXiv cs.NI 2021
Year: 2021

The majority of Internet traffic is caused by a relatively small number of flows (so-called elephant flows). This phenomenon can be exploited to facilitate traffic engineering: resource-costly individual flow forwarding entries can be created only for elephants while serving mice over the shortest paths. Although this idea already appeared in proposed TE systems, it was not examined by itself. It remains unknown what extent of flow table occupancy and operations number reduction can be achieved or how to select thresholds or sampling rates to cover the desired fraction of traffic. In this paper, we use reproducible traffic models obtained from a 30-day-long campus trace covering 4 billion flows, to answer these questions. We establish theoretical boundaries for flow table usage reduction algorithms that classify flows since the first packet, after reaching a predefined counter threshold or detect elephants by sampling. An important finding is that simple packet sampling performs surprisingly well on realistic traffic, reducing the number of flow entries by a factor up to 400, still covering 80% of the traffic. We also provide an open-source software package allowing the replication of our experiments or the performing of similar evaluations for other algorithms or flow distributions.
Differentially Private Federated Learning with Laplacian Smoothing
Venue: arXiv cs.LG 2021
Year: 2021

Federated learning aims to protect data privacy by collaboratively learning a model without sharing private data among users. However, an adversary may still be able to infer the private training data by attacking the released model. Differential privacy provides a statistical protection against such attacks at the price of significantly degrading the accuracy or utility of the trained models. In this paper, we investigate a utility enhancement scheme based on Laplacian smoothing for differentially private federated learning (DP-Fed-LS), where the parameter aggregation with injected Gaussian noise is improved in statistical precision without losing privacy budget. Our key observation is that the aggregated gradients in federated learning often enjoy a type of smoothness, i.e. sparsity in the graph Fourier basis with polynomial decays of Fourier coefficients as frequency grows, which can be exploited by the Laplacian smoothing efficiently. Under a prescribed differential privacy budget, convergence error bounds with tight rates are provided for DP-Fed-LS with uniform subsampling of heterogeneous Non-IID data, revealing possible utility improvement of Laplacian smoothing in effective dimensionality and variance reduction, among others. Experiments over MNIST, SVHN, and Shakespeare datasets show that the proposed method can improve model accuracy with DP-guarantee and membership privacy under both uniform and Poisson subsampling mechanisms.
DriveML: An R Package for Driverless Machine Learning
Venue: arXiv cs.LG 2021
Year: 2021

In recent years, the concept of automated machine learning has become very popular. Automated Machine Learning (AutoML) mainly refers to the automated methods for model selection and hyper-parameter optimization of various algorithms such as random forests, gradient boosting, neural networks, etc. In this paper, we introduce a new package i.e. DriveML for automated machine learning. DriveML helps in implementing some of the pillars of an automated machine learning pipeline such as automated data preparation, feature engineering, model building and model explanation by running the function instead of writing lengthy R codes. The DriveML package is available in CRAN. We compare the DriveML package with other relevant packages in CRAN/Github and find that DriveML performs the best across different parameters. We also provide an illustration by applying the DriveML package with default configuration on a real world dataset. Overall, the main benefits of DriveML are in development time savings, reduce developer's errors, optimal tuning of machine learning models and reproducibility.
Can Terahertz Provide High-Rate Reliable Low Latency Communications for Wireless VR?
Venue: arXiv cs.IT 2021
Year: 2021

Wireless virtual reality (VR) imposes new visual and haptic requirements that are directly linked to the quality-of-experience (QoE) of VR users. These QoE requirements can only be met by wireless connectivity that offers high-rate and high-reliability low latency communications (HRLLC), unlike the low rates usually considered in vanilla ultra-reliable low latency communication scenarios. The high rates for VR over short distances can only be supported by an enormous bandwidth, which is available in terahertz (THz) frequency bands. Guaranteeing HRLLC requires dealing with the uncertainty that is specific to the THz channel. To explore the potential of THz for meeting HRLLC requirements, a quantification of the risk for an unreliable VR performance is conducted through a novel and rigorous characterization of the tail of the end-to-end (E2E) delay. Then, a thorough analysis of the tail-value-atrisk (TVaR) is performed to concretely characterize the behavior of extreme wireless events crucial to the real-time VR experience. System reliability for scenarios with guaranteed line-of-sight (LoS) is then derived as a function of THz network parameters after deriving a novel expression for the probability distribution function of the THz transmission delay. Numerical results show that abundant bandwidth and low molecular absorption are necessary to improve the reliability. However, their effect remains secondary compared to the availability of LoS, which significantly affects the THz HRLLC performance. In particular, for scenarios with guaranteed LoS, a reliability of 99.999% (with an E2E delay threshold of 20 ms) for a bandwidth of 15 GHz along with data rates of 18.3 Gbps can be achieved by the THz network (operating at a frequency of 1 THz), compared to a reliability of 96% for twice the bandwidth, when blockages are considered.
Approximating maximum integral multiflows on bounded genus graphs
Venue: arXiv cs.DS 2021
Year: 2021

We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.
Open Graph Benchmark: Datasets for Machine Learning on Graphs
Venue: arXiv cs.LG 2021
Year: 2021

We present the Open Graph Benchmark (OGB), a diverse set of challenging and realistic benchmark datasets to facilitate scalable, robust, and reproducible graph machine learning (ML) research. OGB datasets are large-scale, encompass multiple important graph ML tasks, and cover a diverse range of domains, ranging from social and information networks to biological networks, molecular graphs, source code ASTs, and knowledge graphs. For each dataset, we provide a unified evaluation protocol using meaningful application-specific data splits and evaluation metrics. In addition to building the datasets, we also perform extensive benchmark experiments for each dataset. Our experiments suggest that OGB datasets present significant challenges of scalability to large-scale graphs and out-of-distribution generalization under realistic data splits, indicating fruitful opportunities for future research. Finally, OGB provides an automated end-to-end graph ML pipeline that simplifies and standardizes the process of graph data loading, experimental setup, and model evaluation. OGB will be regularly updated and welcomes inputs from the community. OGB datasets as well as data loaders, evaluation scripts, baseline code, and leaderboards are publicly available at https://ogb.stanford.edu .
A survey on modern trainable activation functions
Venue: arXiv cs.LG 2021
Year: 2021

In neural networks literature, there is a strong interest in identifying and defining activation functions which can improve neural network performance. In recent years there has been a renovated interest of the scientific community in investigating activation functions which can be trained during the learning process, usually referred to as "trainable", "learnable" or "adaptable" activation functions. They appear to lead to better network performance. Diverse and heterogeneous models of trainable activation function have been proposed in the literature. In this paper, we present a survey of these models. Starting from a discussion on the use of the term "activation function" in literature, we propose a taxonomy of trainable activation functions, highlight common and distinctive proprieties of recent and past models, and discuss main advantages and limitations of this type of approach. We show that many of the proposed approaches are equivalent to adding neuron layers which use fixed (non-trainable) activation functions and some simple local rule that constraints the corresponding weight layers.
Electromigration-Aware Architecture for Modern Microprocessors
Venue: arXiv cs.AR 2021
Year: 2021

Reliability is a fundamental requirement in any microprocessor to guarantee correct execution over its lifetime. The design rules related to reliability depend on the process technology being used and the expected operating conditions of the device. To meet reliability requirements, advanced process technologies (28 nm and below) impose highly challenging design rules. Such design-for-reliability rules have become a major burden on the flow of VLSI implementation because of the severe physical constraints they impose. This paper focuses on electromigration (EM), which is one of the major critical factors affecting semiconductor reliability. EM is the aging process of on-die wires and vias and is induced by excessive current flow that can damage wires and may also significantly impact the integrated-circuit clock frequency. EM exerts a comprehensive global effect on devices because it impacts wires that may reside inside the standard or custom logical cells, between logical cells, inside memory elements, and within wires that interconnect functional blocks. The design-implementation flow (synthesis and place-and-route) currently detects violations of EM-reliability rules and attempts to solve them. In contrast, this paper proposes a new approach to enhance these flows by using EM-aware architecture. Our results show that the proposed solution can relax EM design efforts in microprocessors and more than double microprocessor lifetime. This work demonstrates this proposed approach for modern microprocessors, although the principals and ideas can be adapted to other cases as well.
Generating SOAP Notes from Doctor-Patient Conversations Using Modular Summarization Techniques
Venue: arXiv cs.CL 2021
Year: 2021

Following each patient visit, physicians draft long semi-structured clinical summaries called SOAP notes. While invaluable to clinicians and researchers, creating digital SOAP notes is burdensome, contributing to physician burnout. In this paper, we introduce the first complete pipelines to leverage deep summarization models to generate these notes based on transcripts of conversations between physicians and patients. After exploring a spectrum of methods across the extractive-abstractive spectrum, we propose Cluster2Sent, an algorithm that (i) extracts important utterances relevant to each summary section; (ii) clusters together related utterances; and then (iii) generates one summary sentence per cluster. Cluster2Sent outperforms its purely abstractive counterpart by 8 ROUGE-1 points, and produces significantly more factual and coherent sentences as assessed by expert human evaluators. For reproducibility, we demonstrate similar benefits on the publicly available AMI dataset. Our results speak to the benefits of structuring summaries into sections and annotating supporting evidence when constructing summarization corpora.
Superposition for Lambda-Free Higher-Order Logic
Venue: arXiv cs.LO 2021
Year: 2021

We introduce refutationally complete superposition calculi for intentional and extensional clausal $λ$-free higher-order logic, two formalisms that allow partial application and applied variables. The calculi are parameterized by a term order that need not be fully monotonic, making it possible to employ the $λ$-free higher-order lexicographic path and Knuth-Bendix orders. We implemented the calculi in the Zipperposition prover and evaluated them on Isabelle/HOL and TPTP benchmarks. They appear promising as a stepping stone towards complete, highly efficient automatic theorem provers for full higher-order logic.
Falsification of Cyber-Physical Systems with Robustness-Guided Black-Box Checking
Venue: arXiv cs.LO 2021
Year: 2021

For exhaustive formal verification, industrial-scale cyber-physical systems (CPSs) are often too large and complex, and lightweight alternatives (e.g., monitoring and testing) have attracted the attention of both industrial practitioners and academic researchers. Falsification is one popular testing method of CPSs utilizing stochastic optimization. In state-of-the-art falsification methods, the result of the previous falsification trials is discarded, and we always try to falsify without any prior knowledge. To concisely memorize such prior information on the CPS model and exploit it, we employ Black-box checking (BBC), which is a combination of automata learning and model checking. Moreover, we enhance BBC using the robust semantics of STL formulas, which is the essential gadget in falsification. Our experiment results suggest that our robustness-guided BBC outperforms a state-of-the-art falsification tool.
Multi-Stage Conversational Passage Retrieval: An Approach to Fusing Term Importance Estimation and Neural Query Rewriting
Venue: arXiv cs.CL 2021
Year: 2021

Conversational search plays a vital role in conversational information seeking. As queries in information seeking dialogues are ambiguous for traditional ad-hoc information retrieval (IR) systems due to the coreference and omission resolution problems inherent in natural language dialogue, resolving these ambiguities is crucial. In this paper, we tackle conversational passage retrieval (ConvPR), an important component of conversational search, by addressing query ambiguities with query reformulation integrated into a multi-stage ad-hoc IR system. Specifically, we propose two conversational query reformulation (CQR) methods: (1) term importance estimation and (2) neural query rewriting. For the former, we expand conversational queries using important terms extracted from the conversational context with frequency-based signals. For the latter, we reformulate conversational queries into natural, standalone, human-understandable queries with a pretrained sequence-tosequence model. Detailed analyses of the two CQR methods are provided quantitatively and qualitatively, explaining their advantages, disadvantages, and distinct behaviors. Moreover, to leverage the strengths of both CQR methods, we propose combining their output with reciprocal rank fusion, yielding state-of-the-art retrieval effectiveness, 30% improvement in terms of NDCG@3 compared to the best submission of TREC CAsT 2019.
Neural CRF Model for Sentence Alignment in Text Simplification
Venue: arXiv cs.CL 2021
Year: 2021

The success of a text simplification system heavily depends on the quality and quantity of complex-simple sentence pairs in the training corpus, which are extracted by aligning sentences between parallel articles. To evaluate and improve sentence alignment quality, we create two manually annotated sentence-aligned datasets from two commonly used text simplification corpora, Newsela and Wikipedia. We propose a novel neural CRF alignment model which not only leverages the sequential nature of sentences in parallel documents but also utilizes a neural sentence pair model to capture semantic similarity. Experiments demonstrate that our proposed approach outperforms all the previous work on monolingual sentence alignment task by more than 5 points in F1. We apply our CRF aligner to construct two new text simplification datasets, Newsela-Auto and Wiki-Auto, which are much larger and of better quality compared to the existing datasets. A Transformer-based seq2seq model trained on our datasets establishes a new state-of-the-art for text simplification in both automatic and human evaluation.
Information Design in Non-atomic Routing Games with Partial Participation: Computation and Properties
Venue: arXiv cs.GT 2021
Year: 2021

We consider a routing game among non-atomic agents where link latency functions are conditional on an uncertain state of the network. The agents have the same prior belief about the state, but only a fixed fraction receive private route recommendations or a common message, which are generated by a known randomization, referred to as private or public signaling policy respectively. The remaining agents choose route according to Bayes Nash flow with respect to the prior. We develop a computational approach to solve the optimal information design problem, i.e., to minimize expected social latency over all public or obedient private signaling policies. For a fixed flow induced by non-participating agents, design of an optimal private signaling policy is shown to be a generalized problem of moments for polynomial link latency functions, and to admit an atomic solution with a provable upper bound on the number of atoms. This implies that, for polynomial link latency functions, information design can be equivalently cast as a polynomial optimization problem. This in turn can be arbitrarily lower bounded by a known hierarchy of semidefinite relaxations. The first level of this hierarchy is shown to be exact for the basic two link case with affine latency functions. We also identify a class of private signaling policies over which the optimal social cost is non-increasing with increasing fraction of participating agents for parallel networks. This is in contrast to existing results where the cost of participating agents under a fixed signaling policy may increase with their increasing fraction.
AIBench Scenario: Scenario-distilling AI Benchmarking
Venue: arXiv cs.PF 2021
Year: 2021

Modern real-world application scenarios like Internet services consist of a diversity of AI and non-AI modules with huge code sizes and long and complicated execution paths, which raises serious benchmarking or evaluating challenges. Using AI components or micro benchmarks alone can lead to error-prone conclusions. This paper presents a methodology to attack the above challenge. We formalize a real-world application scenario as a Directed Acyclic Graph-based model and propose the rules to distill it into a permutation of essential AI and non-AI tasks, which we call a scenario benchmark. Together with seventeen industry partners, we extract nine typical scenario benchmarks. We design and implement an extensible, configurable, and flexible benchmark framework. We implement two Internet service AI scenario benchmarks based on the framework as proxies to two real-world application scenarios. We consider scenario, component, and micro benchmarks as three indispensable parts for evaluating. Our evaluation shows the advantage of our methodology against using component or micro AI benchmarks alone. The specifications, source code, testbed, and results are publicly available from \url{https://www.benchcouncil.org/aibench/scenario/}.
Collaborative Deanonymization
Venue: arXiv cs.CR 2021
Year: 2021

Privacy-seeking cryptocurrency users rely on anonymization techniques like CoinJoin and ring transactions. By using such technologies benign users potentially provide anonymity to bad actors. We propose overlay protocols to resolve the tension between anonymity and accountability in a peer-to-peer manner. Cryptocurrencies can adopt this approach to enable prosecution of publicly recognized crimes. We illustrate how the protocols could apply to Monero rings and CoinJoin transactions in Bitcoin.