OpenRaiser/Intern-Atlas huggingface dataset:
First-Order Model-Checking in Random Graphs and Complex Networks
Venue: arXiv cs.DM 2020
Year: 2020

Complex networks are everywhere. They appear for example in the form of biological networks, social networks, or computer networks and have been studied extensively. Efficient algorithms to solve problems on complex networks play a central role in today's society. Algorithmic meta-theorems show that many problems can be solved efficiently. Since logic is a powerful tool to model problems, it has been used to obtain very general meta-theorems. In this work, we consider all problems definable in first-order logic and analyze which properties of complex networks allow them to be solved efficiently. The mathematical tool to describe complex networks are random graph models. We define a property of random graph models called $α$-power-law-boundedness. Roughly speaking, a random graph is $α$-power-law-bounded if it does not admit strong clustering and its degree sequence is bounded by a power-law distribution with exponent at least $α$ (i.e. the fraction of vertices with degree $k$ is roughly $O(k^{-α})$). We solve the first-order model-checking problem (parameterized by the length of the formula) in almost linear FPT time on random graph models satisfying this property with $α\ge 3$. This means in particular that one can solve every problem expressible in first-order logic in almost linear expected time on these random graph models. This includes for example preferential attachment graphs, Chung-Lu graphs, configuration graphs, and sparse Erdős-Rényi graphs. Our results match known hardness results and generalize previous tractability results on this topic.
Blockchain-Aided Flow Insertion and Verification in Software Defined Networks
Venue: arXiv cs.NI 2020
Year: 2020

The Internet of Things (IoT) connected by Software Defined Networking (SDN) promises to bring great benefits to cyber-physical systems. However, the increased attack surface offered by the growing number of connected vulnerable devices and complex nature of SDN control plane applications could overturn the huge benefits of such a system. This paper addresses the vulnerability of some unspecified security flaw in the SDN control plane application (such as a zero-day software vulnerability) which can be exploited to insert malicious flow rules in the switch that do not match network policies. Specifically, we propose a blockchain-as-a-service (BaaS) based framework that supports switch flow verification and insertion; and additionally provides straightforward deployment of blockchain technology within an existing SDN infrastructure. While use of an external BaaS brings straightforward deployment, it obscures knowledge of the blockchain agents who are responsible for flow conformance testing through a smart blockchain contract, leading to potential exploitation. Thus, we design a strategy to prevent the blockchain agents from acting arbitrarily, as this would result in what is termed a "moral hazard". We achieve this by developing a novel mathematical model of the fair reward scheme based on game theory. To understand the performance of our system, we evaluate our model using a Matlab based simulation framework. The simulation results demonstrate that the proposed algorithm balances the needs of the blockchain agents to maximise the overall social welfare, i.e. the sum of profits across all parties.
Determining Image similarity with Quasi-Euclidean Metric
Venue: arXiv cs.CV 2020
Year: 2020

Image similarity is a core concept in Image Analysis due to its extensive application in computer vision, image processing, and pattern recognition. The objective of our study is to evaluate Quasi-Euclidean metric as an image similarity measure and analyze how it fares against the existing standard ways like SSIM and Euclidean metric. In this paper, we analyzed the similarity between two images from our own novice dataset and assessed its performance against the Euclidean distance metric and SSIM. We also present experimental results along with evidence indicating that our proposed implementation when applied to our novice dataset, furnished different results than standard metrics in terms of effectiveness and accuracy. In some cases, our methodology projected remarkable performance and it is also interesting to note that our implementation proves to be a step ahead in recognizing similarity when compared to
Constant-Depth and Subcubic-Size Threshold Circuits for Matrix Multiplication
Venue: arXiv cs.DS 2020
Year: 2020

Boolean circuits of McCulloch-Pitts threshold gates are a classic model of neural computation studied heavily in the late 20th century as a model of general computation. Recent advances in large-scale neural computing hardware has made their practical implementation a near-term possibility. We describe a theoretical approach for multiplying two $N$ by $N$ matrices that integrates threshold gate logic with conventional fast matrix multiplication algorithms, that perform $O(N^ω)$ arithmetic operations for a positive constant $ω< 3$. Our approach converts such a fast matrix multiplication algorithm into a constant-depth threshold circuit with approximately $O(N^ω)$ gates. Prior to our work, it was not known whether the $Θ(N^3)$-gate barrier for matrix multiplication was surmountable by constant-depth threshold circuits. Dense matrix multiplication is a core operation in convolutional neural network training. Performing this work on a neural architecture instead of off-loading it to a GPU may be an appealing option.
Dialog as a Vehicle for Lifelong Learning
Venue: arXiv cs.CL 2020
Year: 2020

Dialog systems research has primarily been focused around two main types of applications - task-oriented dialog systems that learn to use clarification to aid in understanding a goal, and open-ended dialog systems that are expected to carry out unconstrained "chit chat" conversations. However, dialog interactions can also be used to obtain various types of knowledge that can be used to improve an underlying language understanding system, or other machine learning systems that the dialog acts over. In this position paper, we present the problem of designing dialog systems that enable lifelong learning as an important challenge problem, in particular for applications involving physically situated robots. We include examples of prior work in this direction, and discuss challenges that remain to be addressed.
Supermasks in Superposition
Venue: arXiv cs.LG 2020
Year: 2020

We present the Supermasks in Superposition (SupSup) model, capable of sequentially learning thousands of tasks without catastrophic forgetting. Our approach uses a randomly initialized, fixed base network and for each task finds a subnetwork (supermask) that achieves good performance. If task identity is given at test time, the correct subnetwork can be retrieved with minimal memory usage. If not provided, SupSup can infer the task using gradient-based optimization to find a linear superposition of learned supermasks which minimizes the output entropy. In practice we find that a single gradient step is often sufficient to identify the correct mask, even among 2500 tasks. We also showcase two promising extensions. First, SupSup models can be trained entirely without task identity information, as they may detect when they are uncertain about new data and allocate an additional supermask for the new training distribution. Finally the entire, growing set of supermasks can be stored in a constant-sized reservoir by implicitly storing them as attractors in a fixed-sized Hopfield network.
Self-Scaling Clusters and Reproducible Containers to Enable Scientific Computing
Venue: arXiv cs.DC 2020
Year: 2020

Container technologies such as Docker have become a crucial component of many software industry practices especially those pertaining to reproducibility and portability. The containerization philosophy has influenced the scientific computing community, which has begun to adopt - and even develop - container technologies (such as Singularity). Leveraging containers for scientific software often poses challenges distinct from those encountered in industry, and requires different methodologies. This is especially true for HPC. With an increasing number of options for HPC in the cloud (including NSF-funded cloud projects), there is strong motivation to seek solutions that provide flexibility to develop and deploy scientific software on a variety of computational infrastructures in a portable and reproducible way. The flexibility offered by cloud services enables virtual HPC clusters that scale on-demand, and the Cyberinfrastructure Resource Integration team in the XSEDE project has developed a set of tools which provides scalable infrastructure in the cloud. We now present a solution which uses the Nix package manager in an MPI-capable Docker container that is converted to Singularity. It provides consistent installations, dependencies, and environments in each image that are reproducible and portable across scientific computing infrastructures. We demonstrate the utility of these containers with cluster benchmark runs in a self-scaling virtual cluster using the Slurm scheduler deployed in the Jetstream and Aristotle Red Cloud OpenStack clouds. We conclude this technique is useful as a template for scientific software application containers to be used in the XSEDE compute environment, other Singularity HPC environments, and cloud computing environments.
Domain Contrast for Domain Adaptive Object Detection
Venue: arXiv cs.CV 2020
Year: 2020

We present Domain Contrast (DC), a simple yet effective approach inspired by contrastive learning for training domain adaptive detectors. DC is deduced from the error bound minimization perspective of a transferred model, and is implemented with cross-domain contrast loss which is plug-and-play. By minimizing cross-domain contrast loss, DC guarantees the transferability of detectors while naturally alleviating the class imbalance issue in the target domain. DC can be applied at either image level or region level, consistently improving detectors' transferability and discriminability. Extensive experiments on commonly used benchmarks show that DC improves the baseline and state-of-the-art by significant margins, while demonstrating great potential for large domain divergence.
Trust-by-Design: Evaluating Issues and Perceptions within Clinical Passporting
Venue: arXiv cs.CR 2020
Year: 2020

A substantial administrative burden is placed on healthcare professionals as they manage and progress through their careers. Identity verification, pre-employment screening and appraisals: the bureaucracy associated with each of these processes takes precious time out of a healthcare professional's day. Time that could have been spent focused on patient care. In the midst of the COVID-19 crisis, it is more important than ever to optimize these professionals' time. This paper presents the synthesis of a design workshop held at the Royal College of Physicians of Edinburgh (RCPE) and subsequent interviews with healthcare professionals. The main research question posed is whether these processes can be re-imagined using digital technologies, specifically Self-Sovereign Identity? A key contribution in the paper is the development of a set of user-led requirements and design principles for identity systems used within healthcare. These are then contrasted with the design principles found in the literature. The results of this study confirm the need and potential of professionalising identity and credential management throughout a healthcare professional's career.
On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering
Venue: arXiv cs.DS 2020
Year: 2020

Editing a graph into a disjoint union of clusters is a standard optimization task in graph-based data clustering. Here, complementing classic work where the clusters shall be cliques, we focus on clusters that shall be 2-clubs, that is, subgraphs of diameter two. This naturally leads to the two NP-hard problems 2-Club Cluster Editing (the allowed editing operations are edge insertion and edge deletion) and 2-Club Cluster Vertex Deletion (the allowed editing operations are vertex deletions). Answering an open question from the literature, we show that 2-Club Cluster Editing is W[2]-hard with respect to the number of edge modifications, thus contrasting the fixed-parameter tractability result for the classic Cluster Editing problem (considering cliques instead of 2-clubs). Then focusing on 2-Club Cluster Vertex Deletion, which is easily seen to be fixed-parameter tractable, we show that under standard complexity-theoretic assumptions it does not have a polynomial-size problem kernel when parameterized by the number of vertex deletions. Nevertheless, we develop several effective data reduction and pruning rules, resulting in a competitive solver, clearly outperforming a standard CPLEX solver in most instances of an established biological test data set.
SASO: Joint 3D Semantic-Instance Segmentation via Multi-scale Semantic Association and Salient Point Clustering Optimization
Venue: arXiv cs.CV 2020
Year: 2020

We propose a novel 3D point cloud segmentation framework named SASO, which jointly performs semantic and instance segmentation tasks. For semantic segmentation task, inspired by the inherent correlation among objects in spatial context, we propose a Multi-scale Semantic Association (MSA) module to explore the constructive effects of the semantic context information. For instance segmentation task, different from previous works that utilize clustering only in inference procedure, we propose a Salient Point Clustering Optimization (SPCO) module to introduce a clustering procedure into the training process and impel the network focusing on points that are difficult to be distinguished. In addition, because of the inherent structures of indoor scenes, the imbalance problem of the category distribution is rarely considered but severely limits the performance of 3D scene perception. To address this issue, we introduce an adaptive Water Filling Sampling (WFS) algorithm to balance the category distribution of training data. Extensive experiments demonstrate that our method outperforms the state-of-the-art methods on benchmark datasets in both semantic segmentation and instance segmentation tasks.
Computing all $s$-$t$ bridges and articulation points simplified
Venue: arXiv cs.DS 2020
Year: 2020

Given a directed graph $G$ and a pair of nodes $s$ and $t$, an $s$-$t$ bridge of $G$ is an edge whose removal breaks all $s$-$t$ paths of $G$. Similarly, an $s$-$t$ articulation point of $G$ is a node whose removal breaks all $s$-$t$ paths of $G$. Computing the sequence of all $s$-$t$ bridges of $G$ (as well as the $s$-$t$ articulation points) is a basic graph problem, solvable in linear time using the classical min-cut algorithm. When dealing with cuts of unit size ($s$-$t$ bridges) this algorithm can be simplified to a single graph traversal from $s$ to $t$ avoiding an arbitrary $s$-$t$ path, which is interrupted at the $s$-$t$ bridges. Further, the corresponding proof is also simplified making it independent of the theory of network flows.
Denotational recurrence extraction for amortized analysis
Venue: arXiv cs.PL 2020
Year: 2020

A typical way of analyzing the time complexity of functional programs is to extract a recurrence expressing the running time of the program in terms of the size of its input, and then to solve the recurrence to obtain a big-O bound. For recurrence extraction to be compositional, it is also necessary to extract recurrences for the size of outputs of helper functions. Previous work has developed techniques for using logical relations to state a formal correctness theorem for a general recurrence extraction translation: a program is bounded by a recurrence when the operational cost is bounded by the extracted cost, and the output value is bounded, according to a value bounding relation defined by induction on types, by the extracted size. This previous work supports higher-order functions by viewing recurrences as programs in a lambda-calculus, or as mathematical entities in a denotational semantics thereof. In this paper, we extend these techniques to support amortized analysis, where costs are rearranged from one portion of a program to another to achieve more precise bounds. We give an intermediate language in which programs can be annotated according to the banker's method of amortized analysis; this language has an affine type system to ensure credits are not spent more than once. We give a recurrence extraction translation of this language into a recurrence language, a simply-typed lambda-calculus with a cost type, and state and prove a bounding logical relation expressing the correctness of this translation. The recurrence language has a denotational semantics in preorders, and we use this semantics to solve recurrences, e.g analyzing binary counters and splay trees.
Nearest Neighbour Based Estimates of Gradients: Sharp Nonasymptotic Bounds and Applications
Venue: arXiv cs.LG 2020
Year: 2020

Motivated by a wide variety of applications, ranging from stochastic optimization to dimension reduction through variable selection, the problem of estimating gradients accurately is of crucial importance in statistics and learning theory. We consider here the classic regression setup, where a real valued square integrable r.v. $Y$ is to be predicted upon observing a (possibly high dimensional) random vector $X$ by means of a predictive function $f(X)$ as accurately as possible in the mean-squared sense and study a nearest-neighbour-based pointwise estimate of the gradient of the optimal predictive function, the regression function $m(x)=\mathbb{E}[Y\mid X=x]$. Under classic smoothness conditions combined with the assumption that the tails of $Y-m(X)$ are sub-Gaussian, we prove nonasymptotic bounds improving upon those obtained for alternative estimation methods. Beyond the novel theoretical results established, several illustrative numerical experiments have been carried out. The latter provide strong empirical evidence that the estimation method proposed works very well for various statistical problems involving gradient estimation, namely dimensionality reduction, stochastic gradient descent optimization and quantifying disentanglement.
End-to-end training of deep kernel map networks for image classification
Venue: arXiv cs.CV 2020
Year: 2020

Deep kernel map networks have shown excellent performances in various classification problems including image annotation. Their general recipe consists in aggregating several layers of singular value decompositions (SVDs) -- that map data from input spaces into high dimensional spaces -- while preserving the similarity of the underlying kernels. However, the potential of these deep map networks has not been fully explored as the original setting of these networks focuses mainly on the approximation quality of their kernels and ignores their discrimination power. In this paper, we introduce a novel "end-to-end" design for deep kernel map learning that balances the approximation quality of kernels and their discrimination power. Our method proceeds in two steps; first, layerwise SVD is applied in order to build initial deep kernel map approximations and then an "end-to-end" supervised learning is employed to further enhance their discrimination power while maintaining their efficiency. Extensive experiments, conducted on the challenging ImageCLEF annotation benchmark, show the high efficiency and the out-performance of this two-step process with respect to different related methods.
Cutting Polygons into Small Pieces with Chords: Laser-Based Localization
Venue: arXiv cs.CG 2020
Year: 2020

Motivated by indoor localization by tripwire lasers, we study the problem of cutting a polygon into small-size pieces, using the chords of the polygon. Several versions are considered, depending on the definition of the "size" of a piece. In particular, we consider the area, the diameter, and the radius of the largest inscribed circle as a measure of the size of a piece. We also consider different objectives, either minimizing the maximum size of a piece for a given number of chords, or minimizing the number of chords that achieve a given size threshold for the pieces. We give hardness results for polygons with holes and approximation algorithms for multiple variants of the problem.
Person Re-identification by analyzing Dynamic Variations in Gait Sequences
Venue: arXiv cs.CV 2020
Year: 2020

Gait recognition is a biometric technology that identifies individuals in a video sequence by analysing their style of walking or limb movement. However, this identification is generally sensitive to appearance changes and conventional feature descriptors such as Gait Energy Image (GEI) lose some of the dynamic information in the gait sequence. Active Energy Image (AEI) focuses more on dynamic motion changes than GEI and is more suited to deal with appearance changes. We propose a new approach, which allows recognizing people by analysing the dynamic motion variations and identifying people without using a database of predicted changes. In the proposed method, the active energy image is calculated by averaging the difference frames of the silhouette sequence and divided into multiple segments. Affine moment invariants are computed as gait features for each section. Next, matching weights are calculated based on the similarity between extracted features and those in the database. Finally, the subject is identified by the weighted combination of similarities in all segments. The CASIA-B Gait Database is used as the principal dataset for the experimental analysis.
Bookworm continual learning: beyond zero-shot learning and continual learning
Venue: arXiv cs.CV 2020
Year: 2020

We propose bookworm continual learning(BCL), a flexible setting where unseen classes can be inferred via a semantic model, and the visual model can be updated continually. Thus BCL generalizes both continual learning (CL) and zero-shot learning (ZSL). We also propose the bidirectional imagination (BImag) framework to address BCL where features of both past and future classes are generated. We observe that conditioning the feature generator on attributes can actually harm the continual learning ability, and propose two variants (joint class-attribute conditioning and asymmetric generation) to alleviate this problem.
Region-of-interest guided Supervoxel Inpainting for Self-supervision
Venue: arXiv cs.CV 2020
Year: 2020

Self-supervised learning has proven to be invaluable in making best use of all of the available data in biomedical image segmentation. One particularly simple and effective mechanism to achieve self-supervision is inpainting, the task of predicting arbitrary missing areas based on the rest of an image. In this work, we focus on image inpainting as the self-supervised proxy task, and propose two novel structural changes to further enhance the performance of a deep neural network. We guide the process of generating images to inpaint by using supervoxel-based masking instead of random masking, and also by focusing on the area to be segmented in the primary task, which we term as the region-of-interest. We postulate that these additions force the network to learn semantics that are more attuned to the primary task, and test our hypotheses on two applications: brain tumour and white matter hyperintensities segmentation. We empirically show that our proposed approach consistently outperforms both supervised CNNs, without any self-supervision, and conventional inpainting-based self-supervision methods on both large and small training set sizes.