OpenRaiser/Intern-Atlas huggingface dataset:
Improved mixing time for k-subgraph sampling
Venue: arXiv cs.DS 2020
Year: 2020

Understanding the local structure of a graph provides valuable insights about the underlying phenomena from which the graph has originated. Sampling and examining k-subgraphs is a widely used approach to understand the local structure of a graph. In this paper, we study the problem of sampling uniformly k-subgraphs from a given graph. We analyze a few different Markov chain Monte Carlo (MCMC) approaches, and obtain analytical results on their mixing times, which improve significantly the state of the art. In particular, we improve the bound on the mixing times of the standard MCMC approach, and the state-of-the-art MCMC sampling method PSRW, using the canonical-paths argument. In addition, we propose a novel sampling method, which we call recursive subgraph sampling, RSS, and its optimized variant RSS+. The proposed methods, RSS and RSS+, are significantly faster than existing approaches.
Experimental Evaluation of Human Motion Prediction: Toward Safe and Efficient Human Robot Collaboration
Venue: arXiv cs.RO 2020
Year: 2020

Human motion prediction is non-trivial in modern industrial settings. Accurate prediction of human motion can not only improve efficiency in human robot collaboration, but also enhance human safety in close proximity to robots. Among existing prediction models, the parameterization and identification methods of those models vary. It remains unclear what is the necessary parameterization of a prediction model, whether online adaptation of the model is necessary, and whether prediction can help improve safety and efficiency during human robot collaboration. These problems result from the difficulty to quantitatively evaluate various prediction models in a closed-loop fashion in real human-robot interaction settings. This paper develops a method to evaluate the closed-loop performance of different prediction models. In particular, we compare models with different parameterizations and models with or without online parameter adaptation. Extensive experiments were conducted on a human robot collaboration platform. The experimental results demonstrated that human motion prediction significantly enhanced the collaboration efficiency and human safety. Adaptable prediction models that were parameterized by neural networks achieved the best performance.
Collusion-Resilient Probabilistic Fingerprinting Scheme for Correlated Data
Venue: arXiv cs.CR 2020
Year: 2020

In order to receive personalized services, individuals share their personal data with a wide range of service providers, hoping that their data will remain confidential. Thus, in case of an unauthorized distribution of their personal data by these service providers (or in case of a data breach) data owners want to identify the source of such data leakage. Digital fingerprinting schemes have been developed to embed a hidden and unique fingerprint into shared digital content, especially multimedia, to provide such liability guarantees. However, existing techniques utilize the high redundancy in the content, which is typically not included in personal data. In this work, we propose a probabilistic fingerprinting scheme that efficiently generates the fingerprint by considering a fingerprinting probability (to keep the data utility high) and publicly known inherent correlations between data points. To improve the robustness of the proposed scheme against colluding malicious service providers, we also utilize the Boneh-Shaw fingerprinting codes as a part of the proposed scheme. Furthermore, observing similarities between privacy-preserving data sharing techniques (that add controlled noise to the shared data) and the proposed fingerprinting scheme, we make a first attempt to develop a data sharing scheme that provides both privacy and fingerprint robustness at the same time. We experimentally show that fingerprint robustness and privacy have conflicting objectives and we propose a hybrid approach to control such a trade-off with a design parameter. Using the proposed hybrid approach, we show that individuals can improve their level of privacy by slightly compromising from the fingerprint robustness. We implement and evaluate the performance of the proposed scheme on real genomic data. Our experimental results show the efficiency and robustness of the proposed scheme.
Crowd Scene Analysis by Output Encoding
Venue: arXiv cs.CV 2020
Year: 2020

Crowd scene analysis receives growing attention due to its wide applications. Grasping the accurate crowd location (rather than merely crowd count) is important for spatially identifying high-risk regions in congested scenes. In this paper, we propose a Compressed Sensing based Output Encoding (CSOE) scheme, which casts detecting pixel coordinates of small objects into a task of signal regression in encoding signal space. CSOE helps to boost localization performance in circumstances where targets are highly crowded without huge scale variation. In addition, proper receptive field sizes are crucial for crowd analysis due to human size variations. We create Multiple Dilated Convolution Branches (MDCB) that offers a set of different receptive field sizes, to improve localization accuracy when objects sizes change drastically in an image. Also, we develop an Adaptive Receptive Field Weighting (ARFW) module, which further deals with scale variation issue by adaptively emphasizing informative channels that have proper receptive field size. Experiments demonstrate the effectiveness of the proposed method, which achieves state-of-the-art performance across four mainstream datasets, especially achieves excellent results in highly crowded scenes. More importantly, experiments support our insights that it is crucial to tackle target size variation issue in crowd analysis task, and casting crowd localization as regression in encoding signal space is quite effective for crowd analysis.
Cellular Decomposition for Non-repetitive Coverage Task with Minimum Discontinuities
Venue: arXiv cs.RO 2020
Year: 2020

A mechanism to derive non-repetitive coverage path solutions with a proven minimal number of discontinuities is proposed in this work, with the aim to avoid unnecessary, costly end effector lift-offs for manipulators. The problem is motivated by the automatic polishing of an object. Due to the non-bijective mapping between the workspace and the joint-space, a continuous coverage path in the workspace may easily be truncated in the joint-space, incuring undesirable end effector lift-offs. Inversely, there may be multiple configuration choices to cover the same point of a coverage path through the solution of the Inverse Kinematics. The solution departs from the conventional local optimisation of the coverage path shape in task space, or choosing appropriate but possibly disconnected configurations, to instead explicitly explore the leaast number of discontinuous motions through the analysis of the structure of valid configurations in joint-space. The two novel contributions of this paper include proof that the least number of path discontinuities is predicated on the surrounding environment, independent from the choice of the actual coverage path; thus has a minimum. And an efficient finite cellular decomposition method to optimally divide the workspace into the minimum number of cells, each traversable without discontinuties by any arbitrary coverage path within. Extensive simulation examples and real-world results on a 5 DoF manipulator are presented to prove the validity of the proposed strategy in realistic settings.
Handling noise in image deblurring via joint learning
Venue: arXiv cs.CV 2020
Year: 2020

Currently, many blind deblurring methods assume blurred images are noise-free and perform unsatisfactorily on the blurry images with noise. Unfortunately, noise is quite common in real scenes. A straightforward solution is to denoise images before deblurring them. However, even state-of-the-art denoisers cannot guarantee to remove noise entirely. Slight residual noise in the denoised images could cause significant artifacts in the deblurring stage. To tackle this problem, we propose a cascaded framework consisting of a denoiser subnetwork and a deblurring subnetwork. In contrast to previous methods, we train the two subnetworks jointly. Joint learning reduces the effect of the residual noise after denoising on deblurring, hence improves the robustness of deblurring to heavy noise. Moreover, our method is also helpful for blur kernel estimation. Experiments on the CelebA dataset and the GOPRO dataset show that our method performs favorably against several state-of-the-art methods.
Classification of human activity recognition using smartphones
Venue: arXiv cs.CY 2020
Year: 2020

Smartphones have been the most popular and widely used devices among means of communication. Nowadays, human activity recognition is possible on mobile devices by embedded sensors, which can be exploited to manage user behavior on mobile devices by predicting user activity. To reach this aim, storing activity characteristics, Classification, and mapping them to a learning algorithm was studied in this research. In this study, we applied categorization through deep belief network to test and training data, which resulted in 98.25% correct diagnosis in training data and 93.01% in test data. Therefore, in this study, we prove that the deep belief network is a suitable method for this particular purpose.
SensAI+Expanse Emotional Valence Prediction Studies with Cognition and Memory Integration
Venue: arXiv cs.CY 2020
Year: 2020

The humans are affective and cognitive beings relying on memories for their individual and social identities. Also, human dyadic bonds require some common beliefs such as empathetic behaviour for better interaction. In this sense, research studies involving human-agent interaction should resource on affect, cognition, and memory integration. The developed artificial agent system (SensAI+Expanse) includes machine learning algorithms, heuristics, and memory as cognition aids towards emotional valence prediction on the interacting human. Further, an adaptive empathy score is always present in order to engage the human in a recognisable interaction outcome. [...] The agent is resilient on collecting data, adapts its cognitive processes to each human individual in a learning best effort for proper contextualised prediction. The current study make use of an achieved adaptive process. Also, the use of individual prediction models with specific options of the learning algorithm and evaluation metric from a previous research study. The accomplished solution includes a highly performant prediction ability, an efficient energy use, and feature importance explanation for predicted probabilities. Results of the present study show evidence of significant emotional valence behaviour differences between some age ranges and gender combinations. Therefore, this work contributes with an artificial intelligent agent able to assist on cognitive science studies. This ability is about affective disturbances by means of predicting human emotional valence contextualised in space and time. Moreover, contributes with learning processes and heuristics fit to the task including economy of cognition and memory to cope with the environment. Finally, these contributions include an achieved age and gender neutrality on predicting emotional valence states in context and with very good performance for each individual.
Artificial Intelligence, Values and Alignment
Venue: arXiv cs.CY 2020
Year: 2020

This paper looks at philosophical questions that arise in the context of AI alignment. It defends three propositions. First, normative and technical aspects of the AI alignment problem are interrelated, creating space for productive engagement between people working in both domains. Second, it is important to be clear about the goal of alignment. There are significant differences between AI that aligns with instructions, intentions, revealed preferences, ideal preferences, interests and values. A principle-based approach to AI alignment, which combines these elements in a systematic way, has considerable advantages in this context. Third, the central challenge for theorists is not to identify 'true' moral principles for AI; rather, it is to identify fair principles for alignment, that receive reflective endorsement despite widespread variation in people's moral beliefs. The final part of the paper explores three ways in which fair principles for AI alignment could potentially be identified.
Domain-Specialized Cache Management for Graph Analytics
Venue: arXiv cs.DC 2020
Year: 2020

Graph analytics power a range of applications in areas as diverse as finance, networking and business logistics. A common property of graphs used in the domain of graph analytics is a power-law distribution of vertex connectivity, wherein a small number of vertices are responsible for a high fraction of all connections in the graph. These richly-connected, hot, vertices inherently exhibit high reuse. However, this work finds that state-of-the-art hardware cache management schemes struggle in capitalizing on their reuse due to highly irregular access patterns of graph analytics. In response, we propose GRASP, domain-specialized cache management at the last-level cache for graph analytics. GRASP augments existing cache policies to maximize reuse of hot vertices by protecting them against cache thrashing, while maintaining sufficient flexibility to capture the reuse of other vertices as needed. GRASP keeps hardware cost negligible by leveraging lightweight software support to pinpoint hot vertices, thus eliding the need for storage-intensive prediction mechanisms employed by state-of-the-art cache management schemes. On a set of diverse graph-analytic applications with large high-skew graph datasets, GRASP outperforms prior domain-agnostic schemes on all datapoints, yielding an average speed-up of 4.2% (max 9.4%) over the best-performing prior scheme. GRASP remains robust on low-/no-skew datasets, whereas prior schemes consistently cause a slowdown.
Hermes: a Fast, Fault-Tolerant and Linearizable Replication Protocol
Venue: arXiv cs.DC 2020
Year: 2020

Today's datacenter applications are underpinned by datastores that are responsible for providing availability, consistency, and performance. For high availability in the presence of failures, these datastores replicate data across several nodes. This is accomplished with the help of a reliable replication protocol that is responsible for maintaining the replicas strongly-consistent even when faults occur. Strong consistency is preferred to weaker consistency models that cannot guarantee an intuitive behavior for the clients. Furthermore, to accommodate high demand at real-time latencies, datastores must deliver high throughput and low latency. This work introduces Hermes, a broadcast-based reliable replication protocol for in-memory datastores that provides both high throughput and low latency by enabling local reads and fully-concurrent fast writes at all replicas. Hermes couples logical timestamps with cache-coherence-inspired invalidations to guarantee linearizability, avoid write serialization at a centralized ordering point, resolve write conflicts locally at each replica (hence ensuring that writes never abort) and provide fault-tolerance via replayable writes. Our implementation of Hermes over an RDMA-enabled reliable datastore with five replicas shows that Hermes consistently achieves higher throughput than state-of-the-art RDMA-based reliable protocols (ZAB and CRAQ) across all write ratios while also significantly reducing tail latency. At 5% writes, the tail latency of Hermes is 3.6X lower than that of CRAQ and ZAB.
Electric Field Propagation Through Singular Value Decomposition
Venue: arXiv cs.CE 2020
Year: 2020

We demonstrate that the singular value decomposition algorithm in conjunction with the fast Fourier transform or finite difference procedures provides a straightforward and accurate method for rapidly propagating electric fields in the one-way Helmholtz formalism.
Provenance for Regular Path Queries
Venue: arXiv cs.FL 2020
Year: 2020

Regular path queries (RPQs) the ubiquitous mechanism for querying data graphs of partially known structure. RPQs are in essence regular expressions over the edge symbols. The answer to an RPQ on a given graph (database) is the set of pairs of objects, which are connected by paths spelling words in the language of the regular path query. Often the database edges come with a weights assoaciated to them. Such weights can distances, levels of discomfort, multiplicities, etc. We model weights using semiring frameworks.
Vocabulary-based Method for Quantifying Controversy in Social Media
Venue: arXiv cs.IR 2020
Year: 2020

Identifying controversial topics is not only interesting from a social point of view, it also enables the application of methods to avoid the information segregation, creating better discussion contexts and reaching agreements in the best cases. In this paper we develop a systematic method for controversy detection based primarily on the jargon used by the communities in social media. Our method dispenses with the use of domain-specific knowledge, is language-agnostic, efficient and easy to apply. We perform an extensive set of experiments across many languages, regions and contexts, taking controversial and non-controversial topics. We find that our vocabulary-based measure performs better than state of the art measures that are based only on the community graph structure. Moreover, we shows that it is possible to detect polarization through text analysis.
BasConv: Aggregating Heterogeneous Interactions for Basket Recommendation with Graph Convolutional Neural Network
Venue: arXiv cs.IR 2020
Year: 2020

Within-basket recommendation reduces the exploration time of users, where the user's intention of the basket matters. The intent of a shopping basket can be retrieved from both user-item collaborative filtering signals and multi-item correlations. By defining a basket entity to represent the basket intent, we can model this problem as a basket-item link prediction task in the User-Basket-Item~(UBI) graph. Previous work solves the problem by leveraging user-item interactions and item-item interactions simultaneously. However, collectivity and heterogeneity characteristics are hardly investigated before. Collectivity defines the semantics of each node which should be aggregated from both directly and indirectly connected neighbors. Heterogeneity comes from multi-type interactions as well as multi-type nodes in the UBI graph. To this end, we propose a new framework named \textbf{BasConv}, which is based on the graph convolutional neural network. Our BasConv model has three types of aggregators specifically designed for three types of nodes. They collectively learn node embeddings from both neighborhood and high-order context. Additionally, the interactive layers in the aggregators can distinguish different types of interactions. Extensive experiments on two real-world datasets prove the effectiveness of BasConv. Our code is available online at https://github.com/JimLiu96/basConv.
NASA-TLX Web App: An Online Tool to Analyse Subjective Workload
Venue: arXiv cs.HC 2020
Year: 2020

NASA Task Load Index (NASA-TLX) is a widely used assessment technique to compute subjective workload experienced during a task. It evaluates workload using six dimensions: mental demand, physical demand, temporal demand, frustration, effort, and performance. This paper presents a web app to assist experimenters in using NASA-TLX to commute subjective workload. The web app enables the experimenter to conduct various experiments simultaneously and offers the participants a concise interface to provide their subjective evaluation. It performs the calculations at the backend and provides the computed results comprehensively. The web app provides a dashboard for the experimenter to visualize and export the summary of results. Qualitative feedback from 12 experimenters indicated that the NASA-TLX web app is relevant, helpful, and easy to use.
Flatness and Complexity of Immediate Observation Petri Nets
Venue: arXiv cs.LO 2020
Year: 2020

In a previous paper we introduced immediate observation (IO) Petri nets, a class of interest in the study of population protocols and enzymatic chemical networks. In the first part of this paper we show that IO nets are globally flat, and so their safety properties can be checked by efficient symbolic model checking tools using acceleration techniques, like FAST. In the second part we study Branching IO nets (BIO nets), whose transitions can create tokens. BIO nets extend both IO nets and communication-free nets, also called BPP nets, a widely studied class. We show that, while BIO nets are no longer globally flat, and their sets of reachable markings may be non-semilinear, they are still locally flat. As a consequence, the coverability and reachability problem for BIO nets, and even a certain set-parameterized version of them, are in PSPACE. This makes BIO nets the first natural net class with non-semilinear reachability relation for which the reachability problem is provably simpler than for general Petri nets.
Variational Optimization on Lie Groups, with Examples of Leading (Generalized) Eigenvalue Problems
Venue: arXiv cs.LG 2020
Year: 2020

The article considers smooth optimization of functions on Lie groups. By generalizing NAG variational principle in vector space (Wibisono et al., 2016) to Lie groups, continuous Lie-NAG dynamics which are guaranteed to converge to local optimum are obtained. They correspond to momentum versions of gradient flow on Lie groups. A particular case of $\mathsf{SO}(n)$ is then studied in details, with objective functions corresponding to leading Generalized EigenValue problems: the Lie-NAG dynamics are first made explicit in coordinates, and then discretized in structure preserving fashions, resulting in optimization algorithms with faithful energy behavior (due to conformal symplecticity) and exactly remaining on the Lie group. Stochastic gradient versions are also investigated. Numerical experiments on both synthetic data and practical problem (LDA for MNIST) demonstrate the effectiveness of the proposed methods as optimization algorithms ($not$ as a classification method).
Approximations for Throughput Maximization
Venue: arXiv cs.DS 2020
Year: 2020

In this paper we study the classical problem of throughput maximization. In this problem we have a collection $J$ of $n$ jobs, each having a release time $r_j$, deadline $d_j$, and processing time $p_j$. They have to be scheduled non-preemptively on $m$ identical parallel machines. The goal is to find a schedule which maximizes the number of jobs scheduled entirely in their $[r_j,d_j]$ window. This problem has been studied extensively (even for the case of $m=1$). Several special cases of the problem remain open. Bar-Noy et al. [STOC1999] presented an algorithm with ratio $1-1/(1+1/m)^m$ for $m$ machines, which approaches $1-1/e$ as $m$ increases. For $m=1$, Chuzhoy-Ostrovsky-Rabani [FOCS2001] presented an algorithm with approximation with ratio $1-\frac{1}{e}-\varepsilon$ (for any $\varepsilon>0$). Recently Im-Li-Moseley [IPCO2017] presented an algorithm with ratio $1-1/e-\varepsilon_0$ for some absolute constant $\varepsilon_0>0$ for any fixed $m$. They also presented an algorithm with ratio $1-O(\sqrt{\log m/m})-\varepsilon$ for general $m$ which approaches 1 as $m$ grows. The approximability of the problem for $m=O(1)$ remains a major open question. Even for the case of $m=1$ and $c=O(1)$ distinct processing times the problem is open (Sgall [ESA2012]). In this paper we study the case of $m=O(1)$ and show that if there are $c$ distinct processing times, i.e. $p_j$'s come from a set of size $c$, then there is a $(1-\varepsilon)$-approximation that runs in time $O(n^{mc^7\varepsilon^{-6}}\log T)$, where $T$ is the largest deadline. Therefore, for constant $m$ and constant $c$ this yields a PTAS. Our algorithm is based on proving structural properties for a near optimum solution that allows one to use a dynamic programming with pruning.