OpenRaiser/Intern-Atlas huggingface dataset:
New $(α,β)$ Spanners and Hopsets
Venue: arXiv cs.DS 2020
Year: 2020

An $f(d)$-spanner of an unweighted $n$-vertex graph $G=(V,E)$ is a subgraph $H$ satisfying that $dist_H(u, v)$ is at most $f(dist_G(u, v))$ for every $u,v \in V$. We present new spanner constructions that achieve a nearly optimal stretch of $O(\lceil k /d \rceil)$ for any distance value $d \in [1,k^{1-o(1)}]$, and $d \geq k^{1+o(1)}$. We show the following: 1. There exists an $f(d)$-spanner $H \subseteq G$ with $f(d)\leq 7k$ for any $d \in [1,\sqrt{k}/2]$ with expected size $O_{k}(n^{1+1/k})$. This in particular gives $(α,β)$ spanners with $α=O(\sqrt{k})$ and $β=O(k)$. 2. For any $ε\in (0,1/2]$, there exists an $(α,β)$-spanner with $α=O(k^ε)$, $β=O_ε(k)$ and of expected size $O_{k}(n^{1+1/k})$. This implies a stretch of $O(\lceil k/d \rceil)$ for any $d \in [\sqrt{k}/2, k^{1-ε}]$, and for every $d\geq k^{1+ε}$. In particular, it provides a constant stretch already for vertex pairs at distance $k^{1+o(1)}$ (improving upon $d=(\log k)^{\log k}$ that was known before). Up to the $o(1)$ factor in the exponent, and the constant factor in the stretch, this is the best possible by the girth argument. 3. For any $ε\in (0,1)$ and integer $k\geq 1$, there is a $(3+ε, β)$-spanner with $β=O_ε(k^{\log(3+8/ε)})$ and $O_{k,ε}(n^{1+1/k})$ edges. We also consider the related graph concept of hopsets introduced by [Cohen, J. ACM '00]. We present a new family of $(α,β)$ hopsets with $\widetilde{O}(k \cdot n^{1+1/k})$ edges and $α\cdot β=O(k)$. Most notably, we show a construction of $(3+ε,β)$ hopset with $\widetilde{O}_{k,ε}(n^{1+1/k})$ edges and hop-bound of $β=O_ε(k^{\log(3+9/ε)})$, improving upon the state-of-the-art hop-bound of $β=O(\log k /ε)^{\log k}$ by [Elkin-Neiman, '17] and [Huang-Pettie, '17].
Compressing deep quaternion neural networks with targeted regularization
Venue: arXiv cs.LG 2020
Year: 2020

In recent years, hyper-complex deep networks (such as complex-valued and quaternion-valued neural networks) have received a renewed interest in the literature. They find applications in multiple fields, ranging from image reconstruction to 3D audio processing. Similar to their real-valued counterparts, quaternion neural networks (QVNNs) require custom regularization strategies to avoid overfitting. In addition, for many real-world applications and embedded implementations, there is the need of designing sufficiently compact networks, with few weights and neurons. However, the problem of regularizing and/or sparsifying QVNNs has not been properly addressed in the literature as of now. In this paper, we show how to address both problems by designing targeted regularization strategies, which are able to minimize the number of connections and neurons of the network during training. To this end, we investigate two extensions of l1 and structured regularization to the quaternion domain. In our experimental evaluation, we show that these tailored strategies significantly outperform classical (real-valued) regularization approaches, resulting in small networks especially suitable for low-power and real-time applications.
Influence maximization in unknown social networks: Learning Policies for Effective Graph Sampling
Venue: arXiv cs.SI 2020
Year: 2020

A serious challenge when finding influential actors in real-world social networks is the lack of knowledge about the structure of the underlying network. Current state-of-the-art methods rely on hand-crafted sampling algorithms; these methods sample nodes and their neighbours in a carefully constructed order and choose opinion leaders from this discovered network to maximize influence spread in the (unknown) complete network. In this work, we propose a reinforcement learning framework for network discovery that automatically learns useful node and graph representations that encode important structural properties of the network. At training time, the method identifies portions of the network such that the nodes selected from this sampled subgraph can effectively influence nodes in the complete network. The realization of such transferable network structure based adaptable policies is attributed to the meticulous design of the framework that encodes relevant node and graph signatures driven by an appropriate reward scheme. We experiment with real-world social networks from four different domains and show that the policies learned by our RL agent provide a 10-36% improvement over the current state-of-the-art method.
AuditShare: Sensitive Data Sharing with Reliable Leaker Identification
Venue: arXiv cs.CR 2020
Year: 2020

As Personally Identifiable Information (PII) data sharing among multiple parties becomes increasingly common, so does the potential for data leakage. As required by new data protection regulations and laws, when PII leakage occurs, one must be able to reliably identify the leaking sources. Existing solutions utilize watermark technologies or data object allocation strategies to differentiate the data shared with different parties to identify potential leakers. However, these solutions lose their effectiveness under several attack scenarios, e.g., a data sender may leak the data and a receiver may deny the reception of certain shared data. Worse yet, multiple receivers might collude and apply a set of operations such as intersection, complement, and union to their received datasets before leaking them, making the task of leaker identification even more difficult. In this paper, we propose AuditShare, a PII dataset sharing system with reliable leaking source identification. Firstly, taking advantage of the intrinsic properties of PII data, AuditShare allocates data objects to individual sharing parties by PII attributes. Secondly, AuditShare obliviously transfers data between the sender and each receiver and uses a Merkle Tree as an immutable record of the sharing. Thirdly, a knowledge-based identification algorithm is proposed to identify a guilty sender or colluding/non-colluding receivers. Through our evaluation, we show that: (i) With a modest amount of leaked data, AuditShare can accurately (accuracy>99.99%) and undeniably identify all the guilty parties in different cases; (ii) It only takes 0.5 second to share 100,000 data objects in AuditShare, which is practical in real-world deployment.
Context Model for Pedestrian Intention Prediction using Factored Latent-Dynamic Conditional Random Fields
Venue: arXiv cs.CV 2020
Year: 2020

Smooth handling of pedestrian interactions is a key requirement for Autonomous Vehicles (AV) and Advanced Driver Assistance Systems (ADAS). Such systems call for early and accurate prediction of a pedestrian's crossing/not-crossing behaviour in front of the vehicle. Existing approaches to pedestrian behaviour prediction make use of pedestrian motion, his/her location in a scene and static context variables such as traffic lights, zebra crossings etc. We stress on the necessity of early prediction for smooth operation of such systems. We introduce the influence of vehicle interactions on pedestrian intention for this purpose. In this paper, we show a discernible advance in prediction time aided by the inclusion of such vehicle interaction context. We apply our methods to two different datasets, one in-house collected - NTU dataset and another public real-life benchmark - JAAD dataset. We also propose a generic graphical model Factored Latent-Dynamic Conditional Random Fields (FLDCRF) for single and multi-label sequence prediction as well as joint interaction modeling tasks. FLDCRF outperforms Long Short-Term Memory (LSTM) networks across the datasets ($\sim$100 sequences per dataset) over identical time-series features. While the existing best system predicts pedestrian stopping behaviour with 70\% accuracy 0.38 seconds before the actual events, our system achieves such accuracy at least 0.9 seconds on an average before the actual events across datasets.
Spartan: Sparse Robust Addressable Networks
Venue: arXiv cs.DC 2020
Year: 2020

A Peer-to-Peer (P2P) network is a dynamic collection of nodes that connect with each other via virtual overlay links built upon an underlying network (usually, the Internet). P2P networks are highly dynamic and can experience very heavy churn, i.e., a large number of nodes join/leave the network continuously. Thus, building and maintaining a stable overlay network is an important problem that has been studied extensively for two decades. In this paper, we present our \Pe overlay network called Sparse Robust Addressable Network (Spartan). Spartan can be quickly and efficiently built in a fully distributed fashion within $O(\log n)$ rounds. Furthermore, the Spartan overlay structure can be maintained, again, in a fully distributed manner despite adversarially controlled churn (i.e., nodes joining and leaving) and significant variation in the number of nodes. Moreover, new nodes can join a committee within $O(1)$ rounds and leaving nodes can leave without any notice. The number of nodes in the network lies in $[n, fn]$ for any fixed $f\ge 1$. Up to $εn$ nodes (for some small but fixed $ε> 0$) can be adversarially added/deleted within {\em any} period of $P$ rounds for some $P \in O(\log \log n)$. Despite such uncertainty in the network, Spartan maintains $Θ(n/\log n)$ committees that are stable and addressable collections of $Θ(\log n)$ nodes each for $O(polylog(n))$ rounds with high probability. Spartan's committees are also capable of performing sustained computation and passing messages between each other. Thus, any protocol designed for static networks can be simulated on Spartan with minimal overhead. This makes Spartan an ideal platform for developing applications. We experimentally show that Spartan will remain robust as long as each committee, on average, contains 24 nodes for networks of size up to $10240$.
On the Realization and Analysis of Circular Harmonic Transforms for Feature Detection
Venue: arXiv cs.CV 2020
Year: 2020

Circular-harmonic spectra are a compact representation of local image features in two dimensions. It is well known that the computational complexity of such transforms is greatly reduced when polar separability is exploited in steerable filter-banks. Further simplifications are possible when Cartesian separability is incorporated using the radial apodization (i.e. weight, window, or taper) described here, as a consequence of the Laguerre/Hermite correspondence over polar/Cartesian coordinates. The chosen form also mitigates undesirable discretization artefacts due to angular aliasing. The possible utility of circular-harmonic spectra for the description of simple features is illustrated using real data from an airborne electro-optic sensor. The spectrum is deployed in a test-statistic to detect and characterize corners of arbitrary angle and orientation (i.e. wedges). The test-statistic considers uncertainty due to finite sampling and clutter/noise.
Tackling Ordinal Regression Problem for Heterogeneous Data: Sparse and Deep Multi-Task Learning Approaches
Venue: arXiv cs.LG 2020
Year: 2020

Many real-world datasets are labeled with natural orders, i.e., ordinal labels. Ordinal regression is a method to predict ordinal labels that finds a wide range of applications in data-rich domains, such as natural, health and social sciences. Most existing ordinal regression approaches work well for independent and identically distributed (IID) instances via formulating a single ordinal regression task. However, for heterogeneous non-IID instances with well-defined local geometric structures, e.g., subpopulation groups, multi-task learning (MTL) provides a promising framework to encode task (subgroup) relatedness, bridge data from all tasks, and simultaneously learn multiple related tasks in efforts to improve generalization performance. Even though MTL methods have been extensively studied, there is barely existing work investigating MTL for heterogeneous data with ordinal labels. We tackle this important problem via sparse and deep multi-task approaches. Specifically, we develop a regularized multi-task ordinal regression (MTOR) model for smaller datasets and a deep neural networks based MTOR model for large-scale datasets. We evaluate the performance using three real-world healthcare datasets with applications to multi-stage disease progression diagnosis. Our experiments indicate that the proposed MTOR models markedly improve the prediction performance comparing with single-task ordinal regression models.
Neural Mention Detection
Venue: arXiv cs.CL 2020
Year: 2020

Mention detection is an important preprocessing step for annotation and interpretation in applications such as NER and coreference resolution, but few stand-alone neural models have been proposed able to handle the full range of mentions. In this work, we propose and compare three neural network-based approaches to mention detection. The first approach is based on the mention detection part of a state of the art coreference resolution system; the second uses ELMO embeddings together with a bidirectional LSTM and a biaffine classifier; the third approach uses the recently introduced BERT model. Our best model (using a biaffine classifier) achieves gains of up to 1.8 percentage points on mention recall when compared with a strong baseline in a HIGH RECALL coreference annotation setting. The same model achieves improvements of up to 5.3 and 6.2 p.p. when compared with the best-reported mention detection F1 on the CONLL and CRAC coreference data sets respectively in a HIGH F1 annotation setting. We then evaluate our models for coreference resolution by using mentions predicted by our best model in start-of-the-art coreference systems. The enhanced model achieved absolute improvements of up to 1.7 and 0.7 p.p. when compared with our strong baseline systems (pipeline system and end-to-end system) respectively. For nested NER, the evaluation of our model on the GENIA corpora shows that our model matches or outperforms state-of-the-art models despite not being specifically designed for this task.
Augmented Reality Applied to LEGO Construction: AR-based Building Instructions with High Accuracy & Precision and Realistic Object-Hand Occlusions
Venue: arXiv cs.HC 2020
Year: 2020

BRICKxAR is a novel Augmented Reality (AR) instruction method for construction toys such as LEGO. With BRICKxAR, physical LEGO construction is guided by virtual bricks. Compared with the state-of-the-art, accuracy of the virtual - physical model alignment is significantly improved through a new design of marker-based registration, which can achieve an average error less than 1mm throughout the model. Realistic object occlusion is accomplished to reveal the true spatial relationship between physical and virtual bricks. LEGO players' hand detection and occlusion are realized to visualize the correct spatial relationship between real hands and virtual bricks, and allow virtual bricks to be "grasped" by real hands. The integration of these features makes AR instructions possible for small-parts assembly, validated through a working AR prototype for constructing LEGO Arc de Triomphe, quantitative measures of the accuracies of registration and occlusions, and heuristic evaluation of AR instruction features.
ICE: An Interactive Configuration Explorer for High Dimensional Categorical Parameter Spaces
Venue: arXiv cs.GR 2020
Year: 2020

There are many applications where users seek to explore the impact of the settings of several categorical variables with respect to one dependent numerical variable. For example, a computer systems analyst might want to study how the type of file system or storage device affects system performance. A usual choice is the method of Parallel Sets designed to visualize multivariate categorical variables. However, we found that the magnitude of the parameter impacts on the numerical variable cannot be easily observed here. We also attempted a dimension reduction approach based on Multiple Correspondence Analysis but found that the SVD-generated 2D layout resulted in a loss of information. We hence propose a novel approach, the Interactive Configuration Explorer (ICE), which directly addresses the need of analysts to learn how the dependent numerical variable is affected by the parameter settings given multiple optimization objectives. No information is lost as ICE shows the complete distribution and statistics of the dependent variable in context with each categorical variable. Analysts can interactively filter the variables to optimize for certain goals such as achieving a system with maximum performance, low variance, etc. Our system was developed in tight collaboration with a group of systems performance researchers and its final effectiveness was evaluated with expert interviews, a comparative user study, and two case studies.
Code based Cryptography: Classic McEliece
Venue: arXiv cs.CR 2020
Year: 2020

This article addresses code-based cryptography and is designed to depict the complete outline of a code based public key cryptosystem. This report includes basic mathematics and fundamentals of coding theory which are useful for studying code-based cryptography. Here, we briefly describe the first scheme of code based public key cryptosystems given by R. J. McEliece in 1978 and its improved version given by H. Niederreiter in 1986. We discuss the hard problems of coding theory which are used in code based cryptography and some classic attacks on it like information-set decoding (ISD). Successful implementation of the ISD attack on McEliece cryptosystem for some small parameters set is executed and the code for the same is provided in the Appendix. This report elaborates a key encapsulation mechanism (KEM), namely Classic McEliece, based on algebraic coding theory to establish a symmetric key for two users.
GENESIS: Generative Scene Inference and Sampling with Object-Centric Latent Representations
Venue: arXiv cs.LG 2020
Year: 2020

Generative latent-variable models are emerging as promising tools in robotics and reinforcement learning. Yet, even though tasks in these domains typically involve distinct objects, most state-of-the-art generative models do not explicitly capture the compositional nature of visual scenes. Two recent exceptions, MONet and IODINE, decompose scenes into objects in an unsupervised fashion. Their underlying generative processes, however, do not account for component interactions. Hence, neither of them allows for principled sampling of novel scenes. Here we present GENESIS, the first object-centric generative model of 3D visual scenes capable of both decomposing and generating scenes by capturing relationships between scene components. GENESIS parameterises a spatial GMM over images which is decoded from a set of object-centric latent variables that are either inferred sequentially in an amortised fashion or sampled from an autoregressive prior. We train GENESIS on several publicly available datasets and evaluate its performance on scene generation, decomposition, and semi-supervised learning.
Temporal Coding in Spiking Neural Networks with Alpha Synaptic Function: Learning with Backpropagation
Venue: arXiv cs.NE 2020
Year: 2020

The timing of individual neuronal spikes is essential for biological brains to make fast responses to sensory stimuli. However, conventional artificial neural networks lack the intrinsic temporal coding ability present in biological networks. We propose a spiking neural network model that encodes information in the relative timing of individual neuron spikes. In classification tasks, the output of the network is indicated by the first neuron to spike in the output layer. This temporal coding scheme allows the supervised training of the network with backpropagation, using locally exact derivatives of the postsynaptic spike times with respect to presynaptic spike times. The network operates using a biologically-plausible alpha synaptic transfer function. Additionally, we use trainable synchronisation pulses that provide bias, add flexibility during training and exploit the decay part of the alpha function. We show that such networks can be trained successfully on noisy Boolean logic tasks and on the MNIST dataset encoded in time. The results show that the spiking neural network outperforms comparable spiking models on MNIST and achieves similar quality to fully connected conventional networks with the same architecture. We also find that the spiking network spontaneously discovers two operating regimes, mirroring the accuracy-speed trade-off observed in human decision-making: a slow regime, where a decision is taken after all hidden neurons have spiked and the accuracy is very high, and a fast regime, where a decision is taken very fast but the accuracy is lower. These results demonstrate the computational power of spiking networks with biological characteristics that encode information in the timing of individual neurons. By studying temporal coding in spiking networks, we aim to create building blocks towards energy-efficient and more complex biologically-inspired neural architectures.
A direct approach for function approximation on data defined manifolds
Venue: arXiv cs.LG 2020
Year: 2020

In much of the literature on function approximation by deep networks, the function is assumed to be defined on some known domain, such as a cube or a sphere. In practice, the data might not be dense on these domains, and therefore, the approximation theory results are observed to be too conservative. In manifold learning, one assumes instead that the data is sampled from an unknown manifold; i.e., the manifold is defined by the data itself. Function approximation on this unknown manifold is then a two stage procedure: first, one approximates the Laplace-Beltrami operator (and its eigen-decomposition) on this manifold using a graph Laplacian, and next, approximates the target function using the eigen-functions. Alternatively, one estimates first some atlas on the manifold and then uses local approximation techniques based on the local coordinate charts. In this paper, we propose a more direct approach to function approximation on \emph{unknown}, data defined manifolds without computing the eigen-decomposition of some operator or an atlas for the manifold, and without any kind of training in the classical sense. Our constructions are universal; i.e., do not require the knowledge of any prior on the target function other than continuity on the manifold. We estimate the degree of approximation. For smooth functions, the estimates do not suffer from the so-called saturation phenomenon. We demonstrate via a property called good propagation of errors how the results can be lifted for function approximation using deep networks where each channel evaluates a Gaussian network on a possibly unknown manifold.