OpenRaiser/Intern-Atlas huggingface dataset:
The UU-test for Statistical Modeling of Unimodal Data
Venue: arXiv cs.LG 2021
Year: 2021

Deciding on the unimodality of a dataset is an important problem in data analysis and statistical modeling. It allows to obtain knowledge about the structure of the dataset, ie. whether data points have been generated by a probability distribution with a single or more than one peaks. Such knowledge is very useful for several data analysis problems, such as for deciding on the number of clusters and determining unimodal projections. We propose a technique called UU-test (Unimodal Uniform test) to decide on the unimodality of a one-dimensional dataset. The method operates on the empirical cumulative density function (ecdf) of the dataset. It attempts to build a piecewise linear approximation of the ecdf that is unimodal and models the data sufficiently in the sense that the data corresponding to each linear segment follows the uniform distribution. A unique feature of this approach is that in the case of unimodality, it also provides a statistical model of the data in the form of a Uniform Mixture Model. We present experimental results in order to assess the ability of the method to decide on unimodality and perform comparisons with the well-known dip-test approach. In addition, in the case of unimodal datasets we evaluate the Uniform Mixture Models provided by the proposed method using the test set log-likelihood and the two-sample Kolmogorov-Smirnov (KS) test.
Smoothly Navigating between Functional Reactive Programming and Actors
Venue: arXiv cs.PL 2021
Year: 2021

We formally define an elegant multi-paradigm unification of Functional Reactive Programming, Actor Systems, and Object-Oriented Programming. This enables an intuitive form of declarative programming, harvesting the power of concurrency while maintaining safety. We use object and reference capabilities to highlight and tame imperative features: reference capabilities track aliasing and mutability, and object capabilities track I/O. Formally, our type system limits the scope, impact and interactions of impure code. - Scope: Expressions whose input is pure will behave deterministically. - Impact: Data-races and synchronisation issues are avoided. The only way for an actor to behave nondeterministically, is by mutating its state based on message delivery order. - Interactions: Signals provide a functional boundary between imperative and functional code, preventing impure code from invalidating functional assumptions.
DNNExplorer: A Framework for Modeling and Exploring a Novel Paradigm of FPGA-based DNN Accelerator
Venue: arXiv cs.AR 2021
Year: 2021

Existing FPGA-based DNN accelerators typically fall into two design paradigms. Either they adopt a generic reusable architecture to support different DNN networks but leave some performance and efficiency on the table because of the sacrifice of design specificity. Or they apply a layer-wise tailor-made architecture to optimize layer-specific demands for computation and resources but loose the scalability of adaptation to a wide range of DNN networks. To overcome these drawbacks, this paper proposes a novel FPGA-based DNN accelerator design paradigm and its automation tool, called DNNExplorer, to enable fast exploration of various accelerator designs under the proposed paradigm and deliver optimized accelerator architectures for existing and emerging DNN networks. Three key techniques are essential for DNNExplorer's improved performance, better specificity, and scalability, including (1) a unique accelerator design paradigm with both high-dimensional design space support and fine-grained adjustability, (2) a dynamic design space to accommodate different combinations of DNN workloads and targeted FPGAs, and (3) a design space exploration (DSE) engine to generate optimized accelerator architectures following the proposed paradigm by simultaneously considering both FPGAs' computation and memory resources and DNN networks' layer-wise characteristics and overall complexity. Experimental results show that, for the same FPGAs, accelerators generated by DNNExplorer can deliver up to 4.2x higher performances (GOP/s) than the state-of-the-art layer-wise pipelined solutions generated by DNNBuilder for VGG-like DNN with 38 CONV layers. Compared to accelerators with generic reusable computation units, DNNExplorer achieves up to 2.0x and 4.4x DSP efficiency improvement than a recently published accelerator design from academia (HybridDNN) and a commercial DNN accelerator IP (Xilinx DPU), respectively.
Perla: A Conversational Agent for Depression Screening in Digital Ecosystems. Design, Implementation and Validation
Venue: arXiv cs.CY 2021
Year: 2021

Most depression assessment tools are based on self-report questionnaires, such as the Patient Health Questionnaire (PHQ-9). These psychometric instruments can be easily adapted to an online setting by means of electronic forms. However, this approach lacks the interacting and engaging features of modern digital environments. With the aim of making depression screening more available, attractive and effective, we developed Perla, a conversational agent able to perform an interview based on the PHQ-9. We also conducted a validation study in which we compared the results obtained by the traditional self-report questionnaire with Perla's automated interview. Analyzing the results from this study we draw two significant conclusions: firstly, Perla is much preferred by Internet users, achieving more than 2.5 times more reach than a traditional form-based questionnaire; secondly, her psychometric properties (Cronbach's alpha of 0.81, sensitivity of 96% and specificity of 90%) are excellent and comparable to the traditional well-established depression screening questionnaires.
A comprehensive survey on smart contract construction and execution: paradigms, tools, and systems
Venue: arXiv cs.CR 2021
Year: 2021

Smart contracts are regarded as one of the most promising and appealing notions in blockchain technology. Their self-enforcing and event-driven features make some online activities possible without a trusted third party. Nevertheless, problems such as miscellaneous attacks, privacy leakage, and low processing rates pre-vent them from being widely applied. Various schemes and tools have been proposed to facilitate the construction and execution of secure smart contracts. However, a comprehensive survey for these proposals is absent, hindering new researchers and developers from a quick start. This paper surveys the literature and online resources on smart contract construction and execution over the period 2008-2020. We divide the studies into three categories: (1) design paradigms that give examples and patterns on contract construction, (2) design tools that facilitate the development of secure smart contracts, and (3) extensions and alternatives that improve the privacy or efficiency of the system. We start by grouping the relevant construction schemes into the first two categories. We then review the execution mechanisms in the last category and further divide the state-of-the-art solutions into three classes: private contracts with extra tools, off-chain channels, and extensions on core functionalities. Finally, we summarize several challenges and identify future research directions toward developing secure, privacy-preserving, and efficient smart contracts.
Semipaired Domination in Some Subclasses of Chordal Graphs
Venue: arXiv cs.DM 2021
Year: 2021

A dominating set $D$ of a graph $G$ without isolated vertices is called semipaired dominating set if $D$ can be partitioned into $2$-element subsets such that the vertices in each set are at distance at most $2$. The semipaired domination number, denoted by $γ_{pr2}(G)$ is the minimum cardinality of a semipaired dominating set of $G$. Given a graph $G$ with no isolated vertices, the \textsc{Minimum Semipaired Domination} problem is to find a semipaired dominating set of $G$ of cardinality $γ_{pr2}(G)$. The decision version of the \textsc{Minimum Semipaired Domination} problem is already known to be NP-complete for chordal graphs, an important graph class. In this paper, we show that the decision version of the \textsc{Minimum Semipaired Domination} problem remains NP-complete for split graphs, a subclass of chordal graphs. On the positive side, we propose a linear-time algorithm to compute a minimum cardinality semipaired dominating set of block graphs. In addition, we prove that the \textsc{Minimum Semipaired Domination} problem is APX-complete for graphs with maximum degree $3$.
Should policy makers trust composite indices? A commentary on the pitfalls of inappropriate indices for policy formation
Venue: arXiv cs.CY 2021
Year: 2021

This paper critically discusses the use and merits of global indices, in particular, the Global Health Security Index or GHSI (Cameron et 2019) in times of an imminent crisis, like the current pandemic. The index ranked 195 countries according to their expected preparedness in case of a pandemic or other biological threat. The Covid-19 pandemic provides the background to compare each country's predicted performance from the GHSI with the actual performance. In general, there is an inverted relation between predicted versus actual performance, i.e. the predicted top performers are among those that are the worst hit. Obviously, this reflects poorly on the potential policy uses of the index in imminent crisis management. The paper also uses two different data sets, one from the Worldmeter on the spread of the Covid-19 pandemics, and the other one from the INGSA policy tracker, to make comparisons between the actual introduction of pandemic response policies and the corresponding death rate in 29 selected countries.
A Topological Framework for Deep Learning
Venue: arXiv cs.LG 2021
Year: 2021

We utilize classical facts from topology to show that the classification problem in machine learning is always solvable under very mild conditions. Furthermore, we show that a softmax classification network acts on an input topological space by a finite sequence of topological moves to achieve the classification task. Moreover, given a training dataset, we show how topological formalism can be used to suggest the appropriate architectural choices for neural networks designed to be trained as classifiers on the data. Finally, we show how the architecture of a neural network cannot be chosen independently from the shape of the underlying data. To demonstrate these results, we provide example datasets and show how they are acted upon by neural nets from this topological perspective.
Double-IRS Assisted Multi-User MIMO: Cooperative Passive Beamforming Design
Venue: arXiv cs.IT 2021
Year: 2021

Intelligent reflecting surface (IRS) has emerged as an enabling technology to achieve smart and reconfigurable wireless communication environment cost-effectively. Prior works on IRS mainly consider its passive beamforming design and performance optimization without the inter-IRS signal reflection, which thus do not unveil the full potential of multi-IRS assisted wireless networks. In this paper, we study a double-IRS assisted multi-user communication system with the \emph{cooperative} passive beamforming design that captures the multiplicative beamforming gain from the inter-IRS channel. Under the general channel setup with the co-existence of both double- and single-reflection links, we jointly optimize the (active) receive beamforming at the base station (BS) and the cooperative (passive) reflect beamforming at the two distributed IRSs (deployed near the BS and users, respectively) to maximize the minimum signal-to-interference-plus-noise ratio (SINR) of all users. Moreover, for the single-user and multi-user setups, we analytically show the superior performance of the double-IRS cooperative system over the conventional single-IRS system in terms of the maximum signal-to-noise ratio (SNR) and multi-user effective channel rank, respectively. Simulation results validate our analytical results and show the practical advantages of the proposed double-IRS system with cooperative passive beamforming designs.
Philosophy-Guided Modelling and Implementation of Adaptation and Control in Complex Systems
Venue: arXiv cs.NE 2021
Year: 2021

Control was from its very beginning an important concept in cybernetics. Later on, with the works of W. Ross Ashby, for example, biological concepts such as adaptation were interpreted in the light of cybernetic systems theory. Adaptation is the process by which a system is capable of regulating or controlling itself in order to adapt to changes of its inner and outer environment maintaining a homeostatic state. In earlier works we have developed a system metamodel that on the one hand refers to cybernetic concepts such as structure, operation, and system, and on the other to the philosophy of individuation of Gilbert Simondon. The result is the so-called allagmatic method that is capable of creating concrete models of systems such as artificial neural networks and cellular automata starting from abstract building blocks. In this paper, we add to our already existing method the cybernetic concepts of control and especially adaptation. In regard to the system metamodel, we rely again on philosophical theories, this time the philosophy of organism of Alfred N. Whitehead. We show how these new meta-theoretical concepts are described formally and how they are implemented in program code. We also show what role they play in simple experiments. We conclude that philosophical abstract concepts help to better understand the process of creating computer models and their control and adaptation. In the outlook we discuss how the allagmatic method needs to be extended in order to cover the field of complex systems and Norbert Wiener's ideas on control.
Architectural Implications of Graph Neural Networks
Venue: arXiv cs.AR 2021
Year: 2021

Graph neural networks (GNN) represent an emerging line of deep learning models that operate on graph structures. It is becoming more and more popular due to its high accuracy achieved in many graph-related tasks. However, GNN is not as well understood in the system and architecture community as its counterparts such as multi-layer perceptrons and convolutional neural networks. This work tries to introduce the GNN to our community. In contrast to prior work that only presents characterizations of GCNs, our work covers a large portion of the varieties for GNN workloads based on a general GNN description framework. By constructing the models on top of two widely-used libraries, we characterize the GNN computation at inference stage concerning general-purpose and application-specific architectures and hope our work can foster more system and architecture research for GNNs.
SAIL: Self-Augmented Graph Contrastive Learning
Venue: arXiv cs.LG 2021
Year: 2021

This paper studies learning node representations with graph neural networks (GNNs) for unsupervised scenario. Specifically, we derive a theoretical analysis and provide an empirical demonstration about the non-steady performance of GNNs over different graph datasets, when the supervision signals are not appropriately defined. The performance of GNNs depends on both the node feature smoothness and the locality of graph structure. To smooth the discrepancy of node proximity measured by graph topology and node feature, we proposed SAIL - a novel \underline{S}elf-\underline{A}ugmented graph contrast\underline{i}ve \underline{L}earning framework, with two complementary self-distilling regularization modules, \emph{i.e.}, intra- and inter-graph knowledge distillation. We demonstrate the competitive performance of SAIL on a variety of graph applications. Even with a single GNN layer, SAIL has consistently competitive or even better performance on various benchmark datasets, comparing with state-of-the-art baselines.
Coalgebraic Reasoning with Global Assumptions in Arithmetic Modal Logics
Venue: arXiv cs.LO 2021
Year: 2021

We establish a generic upper bound ExpTime for reasoning with global assumptions (also known as TBoxes) in coalgebraic modal logics. Unlike earlier results of this kind, our bound does not require a tractable set of tableau rules for the instance logics, so that the result applies to wider classes of logics. Examples are Presburger modal logic, which extends graded modal logic with linear inequalities over numbers of successors, and probabilistic modal logic with polynomial inequalities over probabilities. We establish the theoretical upper bound using a type elimination algorithm. We also provide a global caching algorithm that potentially avoids building the entire exponential-sized space of candidate states, and thus offers a basis for practical reasoning. This algorithm still involves frequent fixpoint computations; we show how these can be handled efficiently in a concrete algorithm modelled on Liu and Smolka's linear-time fixpoint algorithm. Finally, we show that the upper complexity bound is preserved under adding nominals to the logic, i.e. in coalgebraic hybrid logic.
Perceiving Humans: from Monocular 3D Localization to Social Distancing
Venue: arXiv cs.CV 2021
Year: 2021

Perceiving humans in the context of Intelligent Transportation Systems (ITS) often relies on multiple cameras or expensive LiDAR sensors. In this work, we present a new cost-effective vision-based method that perceives humans' locations in 3D and their body orientation from a single image. We address the challenges related to the ill-posed monocular 3D tasks by proposing a neural network architecture that predicts confidence intervals in contrast to point estimates. Our neural network estimates human 3D body locations and their orientation with a measure of uncertainty. Our proposed solution (i) is privacy-safe, (ii) works with any fixed or moving cameras, and (iii) does not rely on ground plane estimation. We demonstrate the performance of our method with respect to three applications: locating humans in 3D, detecting social interactions, and verifying the compliance of recent safety measures due to the COVID-19 outbreak. We show that it is possible to rethink the concept of "social distancing" as a form of social interaction in contrast to a simple location-based rule. We publicly share the source code towards an open science mission.
Say No to the Discrimination: Learning Fair Graph Neural Networks with Limited Sensitive Attribute Information
Venue: arXiv cs.LG 2021
Year: 2021

Graph neural networks (GNNs) have shown great power in modeling graph structured data. However, similar to other machine learning models, GNNs may make predictions biased on protected sensitive attributes, e.g., skin color and gender. Because machine learning algorithms including GNNs are trained to reflect the distribution of the training data which often contains historical bias towards sensitive attributes. In addition, the discrimination in GNNs can be magnified by graph structures and the message-passing mechanism. As a result, the applications of GNNs in sensitive domains such as crime rate prediction would be largely limited. Though extensive studies of fair classification have been conducted on i.i.d data, methods to address the problem of discrimination on non-i.i.d data are rather limited. Furthermore, the practical scenario of sparse annotations in sensitive attributes is rarely considered in existing works. Therefore, we study the novel and important problem of learning fair GNNs with limited sensitive attribute information. FairGNN is proposed to eliminate the bias of GNNs whilst maintaining high node classification accuracy by leveraging graph structures and limited sensitive information. Our theoretical analysis shows that FairGNN can ensure the fairness of GNNs under mild conditions given limited nodes with known sensitive attributes. Extensive experiments on real-world datasets also demonstrate the effectiveness of FairGNN in debiasing and keeping high accuracy.
HACCLE: Metaprogramming for Secure Multi-Party Computation -- Extended Version
Venue: arXiv cs.PL 2021
Year: 2021

Cryptographic techniques have the potential to enable distrusting parties to collaborate in fundamentally new ways, but their practical implementation poses numerous challenges. An important class of such cryptographic techniques is known as Secure Multi-Party Computation (MPC). Developing Secure MPC applications in realistic scenarios requires extensive knowledge spanning multiple areas of cryptography and systems. And while the steps to arrive at a solution for a particular application are often straightforward, it remains difficult to make the implementation efficient, and tedious to apply those same steps to a slightly different application from scratch. Hence, it is an important problem to design platforms for implementing Secure MPC applications with minimum effort and using techniques accessible to non-experts in cryptography. In this paper, we present the HACCLE (High Assurance Compositional Cryptography: Languages and Environments) toolchain, specifically targeted to MPC applications. HACCLE contains an embedded domain-specific language Harpoon, for software developers without cryptographic expertise to write MPC-based programs, and uses Lightweight Modular Staging (LMS) for code generation. Harpoon programs are compiled into acyclic circuits represented in HACCLE's Intermediate Representation (HIR) that serves as an abstraction over different cryptographic protocols such as secret sharing, homomorphic encryption, or garbled circuits. Implementations of different cryptographic protocols serve as different backends of our toolchain. The extensible design of HIR allows cryptographic experts to plug in new primitives and protocols to realize computation. And the use of standard metaprogramming techniques lowers the development effort significantly.
Bipartite Matching in Nearly-linear Time on Moderately Dense Graphs
Venue: arXiv cs.DS 2021
Year: 2021

We present an $\tilde O(m+n^{1.5})$-time randomized algorithm for maximum cardinality bipartite matching and related problems (e.g. transshipment, negative-weight shortest paths, and optimal transport) on $m$-edge, $n$-node graphs. For maximum cardinality bipartite matching on moderately dense graphs, i.e. $m = Ω(n^{1.5})$, our algorithm runs in time nearly linear in the input size and constitutes the first improvement over the classic $O(m\sqrt{n})$-time [Dinic 1970; Hopcroft-Karp 1971; Karzanov 1973] and $\tilde O(n^ω)$-time algorithms [Ibarra-Moran 1981; Mucha-Sankowski 2004] (where currently $ω\approx 2.373$). On sparser graphs, i.e. when $m = n^{9/8 + δ}$ for any constant $δ>0$, our result improves upon the recent advances of [Madry 2013] and [Liu-Sidford 2020b, 2020a] which achieve an $\tilde O(m^{4/3+o(1)})$ runtime. We obtain these results by combining and advancing recent lines of research in interior point methods (IPMs) and dynamic graph algorithms. First, we simplify and improve the IPM of [v.d.Brand-Lee-Sidford-Song 2020], providing a general primal-dual IPM framework and new sampling-based techniques for handling infeasibility induced by approximate linear system solvers. Second, we provide a simple sublinear-time algorithm for detecting and sampling high-energy edges in electric flows on expanders and show that when combined with recent advances in dynamic expander decompositions, this yields efficient data structures for maintaining the iterates of both [v.d.Brand et al.] and our new IPMs. Combining this general machinery yields a simpler $\tilde O(n \sqrt{m})$ time algorithm for matching based on the logarithmic barrier function, and our state-of-the-art $\tilde O(m+n^{1.5})$ time algorithm for matching based on the [Lee-Sidford 2014] barrier (as regularized in [v.d.Brand et al.]).