OpenRaiser/Intern-Atlas huggingface dataset:
A Survey of Signed Network Mining in Social Media
Venue: arXiv cs.SI 2016
Year: 2016

Many real-world relations can be represented by signed networks with positive and negative links, as a result of which signed network analysis has attracted increasing attention from multiple disciplines. With the increasing prevalence of social media networks, signed network analysis has evolved from developing and measuring theories to mining tasks. In this article, we present a review of mining signed networks in the context of social media and discuss some promising research directions and new frontiers. We begin by giving basic concepts and unique properties and principles of signed networks. Then we classify and review tasks of signed network mining with representative algorithms. We also delineate some tasks that have not been extensively studied with formal definitions and also propose research directions to expand the field of signed network mining.
Rényi Information Complexity and an Information Theoretic Characterization of the Partition Bound
Venue: arXiv cs.CC 2016
Year: 2016

We introduce a new information-theoretic complexity measure $IC_\infty$ for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity ($IC$) and logarithm of partition complexity ($\text{prt}$), which have so far appeared conceptually quite different from each other. $IC_\infty$ is an external information complexity measure based on Rényi mutual information of order infinity. In the definition of $IC_\infty$, relaxing the order of Rényi mutual information from infinity to 1 yields $IC$, while $\log \text{prt}$ is obtained by replacing protocol transcripts with what we term "pseudotranscripts," which omits the interactive nature of a protocol, but only requires that the probability of any transcript given the inputs $x$ and $y$ to the two parties, factorizes into two terms which depend on $x$ and $y$ separately. Further understanding $IC_\infty$ might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity. We also show that applying both the above relaxations simultaneously to $IC_\infty$ gives a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than Kerenidis et al., using an arguably more direct proof.
Learning with Memory Embeddings
Venue: arXiv cs.AI 2016
Year: 2016

Embedding learning, a.k.a. representation learning, has been shown to be able to model large-scale semantic knowledge graphs. A key concept is a mapping of the knowledge graph to a tensor representation whose entries are predicted by models using latent representations of generalized entities. Latent variable models are well suited to deal with the high dimensionality and sparsity of typical knowledge graphs. In recent publications the embedding models were extended to also consider time evolutions, time patterns and subsymbolic representations. In this paper we map embedding models, which were developed purely as solutions to technical problems for modelling temporal knowledge graphs, to various cognitive memory functions, in particular to semantic and concept memory, episodic memory, sensory memory, short-term memory, and working memory. We discuss learning, query answering, the path from sensory input to semantic decoding, and the relationship between episodic memory and semantic memory. We introduce a number of hypotheses on human memory that can be derived from the developed mathematical models.
A note on APN permutations in even dimension
Venue: arXiv cs.CR 2016
Year: 2016

APN permutations in even dimension are vectorial Boolean functions that play a special role in the design of block ciphers. We study their properties, providing some general results and some applications to the low-dimension cases. In particular, we prove that none of their components can be quadratic. For an APN vectorial Boolean function (in even dimension) with all cubic components we prove the existence of a component having a large number of balanced derivatives. Using these restrictions, we obtain the first theoretical proof of the non-existence of APN permutations in dimension 4. Moreover, we derive some contraints on APN permutations in dimension 6.
Typical sumsets of linear codes
Venue: arXiv cs.IT 2016
Year: 2016

Given two identical linear codes $\mathcal C$ over $\mathbb F_q$ of length $n$, we independently pick one codeword from each codebook uniformly at random. A $\textit{sumset}$ is formed by adding these two codewords entry-wise as integer vectors and a sumset is called $\textit{typical}$, if the sum falls inside this set with high probability. We ask the question: how large is the typical sumset for most codes? In this paper we characterize the asymptotic size of such typical sumset. We show that when the rate $R$ of the linear code is below a certain threshold $D$, the typical sumset size is roughly $|\mathcal C|^2=2^{2nR}$ for most codes while when $R$ is above this threshold, most codes have a typical sumset whose size is roughly $|\mathcal C|\cdot 2^{nD}=2^{n(R+D)}$ due to the linear structure of the codes. The threshold $D$ depends solely on the alphabet size $q$ and takes value in $[1/2, \log \sqrt{e})$. More generally, we completely characterize the asymptotic size of typical sumsets of two nested linear codes $\mathcal C_1, \mathcal C_2$ with different rates. As an application of the result, we study the communication problem where the integer sum of two codewords is to be decoded through a general two-user multiple-access channel.
Iterative Instance Segmentation
Venue: arXiv cs.CV 2016
Year: 2016

Existing methods for pixel-wise labelling tasks generally disregard the underlying structure of labellings, often leading to predictions that are visually implausible. While incorporating structure into the model should improve prediction quality, doing so is challenging - manually specifying the form of structural constraints may be impractical and inference often becomes intractable even if structural constraints are given. We sidestep this problem by reducing structured prediction to a sequence of unconstrained prediction problems and demonstrate that this approach is capable of automatically discovering priors on shape, contiguity of region predictions and smoothness of region contours from data without any a priori specification. On the instance segmentation task, this method outperforms the state-of-the-art, achieving a mean $\mathrm{AP}^{r}$ of 63.6% at 50% overlap and 43.3% at 70% overlap.
Compressive Sensing Based Multi-User Detector for the Large-Scale SM-MIMO Uplink
Venue: arXiv cs.IT 2016
Year: 2016

Conventional spatial modulation (SM) is typically considered for transmission in the downlink of small-scale MIMO systems, where a single one of a set of antenna elements (AEs) is activated for implicitly conveying extra bits. By contrast, inspired by the compelling benefits of large-scale MIMO (LS- MIMO) systems, here we propose a LS-SM-MIMO scheme for the uplink (UL), where each user having multiple AEs but only a single radio frequency (RF) chain invokes SM for increasing the UL-throughput. At the same time, by relying on hundreds of AEs but a small number of RF chains, the base station (BS) can simultaneously serve multiple users whilst reducing the power consumption. Due to the large number of AEs of the UL-users and the comparably small number of RF chains at the BS, the UL multi-user signal detection becomes a challenging large-scale under-determined problem. To solve this problem, we propose a joint SM transmission scheme and a carefully designed structured compressive sensing (SCS)-based multi-user detector (MUD) to be used at the users and BS, respectively. Additionally, the cyclic- prefix single-carrier (CPSC) is used to combat the multipath channels, and a simple receive AE selection is used for the improved performance over correlated Rayleigh-fading MIMO channels. We demonstrate that the aggregate SM signal consisting of SM signals of multiple UL-users in one CPSC block appears the distributed sparsity. Moreover, due to the joint SM transmission scheme, aggregate SM signals in the same transmission group exhibit the group sparsity. By exploiting these intrinsically sparse features, the proposed SCS-based MUD can reliably detect the resultant SM signals with low complexity. Simulation results demonstrate that the proposed SCS-based MUD achieves a better signal detection performance than its counterparts even with higher UL-throughtput.
The Partial Visibility Representation Extension Problem
Venue: arXiv cs.CG 2016
Year: 2016

For a graph $G$, a function $ψ$ is called a \emph{bar visibility representation} of $G$ when for each vertex $v \in V(G)$, $ψ(v)$ is a horizontal line segment (\emph{bar}) and $uv \in E(G)$ iff there is an unobstructed, vertical, $\varepsilon$-wide line of sight between $ψ(u)$ and $ψ(v)$. Graphs admitting such representations are well understood (via simple characterizations) and recognizable in linear time. For a directed graph $G$, a bar visibility representation $ψ$ of $G$, additionally, puts the bar $ψ(u)$ strictly below the bar $ψ(v)$ for each directed edge $(u,v)$ of $G$. We study a generalization of the recognition problem where a function $ψ'$ defined on a subset $V'$ of $V(G)$ is given and the question is whether there is a bar visibility representation $ψ$ of $G$ with $ψ(v) = ψ'(v)$ for every $v \in V'$. We show that for undirected graphs this problem together with closely related problems are \NP-complete, but for certain cases involving directed graphs it is solvable in polynomial time.
Value-passing CCS for Trees: A Theory for Concurrent Systems
Venue: arXiv cs.LO 2016
Year: 2016

In this paper, we extend the theory CCS for trees (CCTS) to value-passing CCTS (VCCTS), of which symbols have the capacity for receiving and sending data values, and a nonsequential semantics is proposed in an operational approach. In this concurrent model, a weak barbed congruence and a localized early weak bisimilarity are defined, and the latter relation is proved to be sufficient to justify the former. As an illustration of potential applications of VCCTS, a semantics based on VCCTS is given to a toy multi-threaded programming language featuring a core of C/C++ concurrency; and a formalization based on the operational semantics of VCCTS is proposed for some relaxed memory models, and a DRF-guarantee property with respect to VCCTS is proved.
Distributed Real-Time Power Balancing in Renewable-Integrated Power Grids with Storage and Flexible Loads
Venue: arXiv cs.SY 2016
Year: 2016

The large-scale integration of renewable generation directly affects the reliability of power grids. We investigate the problem of power balancing in a general renewable-integrated power grid with storage and flexible loads. We consider a power grid that is supplied by one conventional generator (CG) and multiple renewable generators (RGs) each co-located with storage,and is connected with external markets. An aggregator operates the power grid to maintain power balance between supply and demand. Aiming at minimizing the long-term system cost, we first propose a real-time centralized power balancing solution, taking into account the uncertainty of the renewable generation, loads, and energy prices. We then provide a distributed implementation algorithm, significantly reducing both computational burden and communication overhead. We demonstrate that our proposed algorithm is asymptotically optimal as the storage capacity increases and the CG ramping constraint loosens. Moreover, the distributed implementation enjoys a fast convergence rate, and enables each RG and the aggregator to make their own decisions. Simulation shows that our proposed algorithm outperforms alternatives and can achieve near-optimal performance for a wide range of storage capacity.
Actions ~ Transformations
Venue: arXiv cs.CV 2016
Year: 2016

What defines an action like "kicking ball"? We argue that the true meaning of an action lies in the change or transformation an action brings to the environment. In this paper, we propose a novel representation for actions by modeling an action as a transformation which changes the state of the environment before the action happens (precondition) to the state after the action (effect). Motivated by recent advancements of video representation using deep learning, we design a Siamese network which models the action as a transformation on a high-level feature space. We show that our model gives improvements on standard action recognition datasets including UCF101 and HMDB51. More importantly, our approach is able to generalize beyond learned action categories and shows significant performance improvement on cross-category generalization on our new ACT dataset.
Equal-image-size source partitioning: Creating strong Fano's inequalities for multi-terminal discrete memoryless channels
Venue: arXiv cs.IT 2016
Year: 2016

This paper introduces equal-image-size source partitioning, a new tool for analyzing channel and joint source-channel coding in a multi-terminal discrete memoryless channel environment. Equal-image-size source partitioning divides the source (combination of messages and codewords) into a sub-exponential number of subsets. Over each of these subsets, the exponential orders of the minimum image sizes of most messages are roughly equal to the same entropy term. This property gives us the strength of minimum image sizes and the flexibility of entropy terms. Using the method of equal-image-size source partitioning, we prove separate necessary conditions for the existence of average-error and maximum-error codes. These necessary conditions are much stronger than the standard Fano's inequality, and can be weakened to render versions of Fano's inequality that apply to codes with non-vanishing error probabilities. To demonstrate the power of this new tool, we employ the stronger average-error version of Fano's inequality to prove the strong converse for the discrete memoryless wiretap channel with decaying leakage, which heretofore has been an open problem.
Strong and Provably Secure Database Access Control
Venue: arXiv cs.CR 2016
Year: 2016

Existing SQL access control mechanisms are extremely limited. Attackers can leak information and escalate their privileges using advanced database features such as views, triggers, and integrity constraints. This is not merely a problem of vendors lagging behind the state-of-the-art. The theoretical foundations for database security lack adequate security definitions and a realistic attacker model, both of which are needed to evaluate the security of modern databases. We address these issues and present a provably secure access control mechanism that prevents attacks that defeat popular SQL database systems.
Approximated and User Steerable tSNE for Progressive Visual Analytics
Venue: arXiv cs.CV 2016
Year: 2016

Progressive Visual Analytics aims at improving the interactivity in existing analytics techniques by means of visualization as well as interaction with intermediate results. One key method for data analysis is dimensionality reduction, for example, to produce 2D embeddings that can be visualized and analyzed efficiently. t-Distributed Stochastic Neighbor Embedding (tSNE) is a well-suited technique for the visualization of several high-dimensional data. tSNE can create meaningful intermediate results but suffers from a slow initialization that constrains its application in Progressive Visual Analytics. We introduce a controllable tSNE approximation (A-tSNE), which trades off speed and accuracy, to enable interactive data exploration. We offer real-time visualization techniques, including a density-based solution and a Magic Lens to inspect the degree of approximation. With this feedback, the user can decide on local refinements and steer the approximation level during the analysis. We demonstrate our technique with several datasets, in a real-world research scenario and for the real-time analysis of high-dimensional streams to illustrate its effectiveness for interactive data analysis.
Type Theory and its Meaning Explanations
Venue: arXiv cs.LO 2016
Year: 2016

At the heart of intuitionistic type theory lies an intuitive semantics called the "meaning explanations"; crucially, when meaning explanations are taken as definitive for type theory, the core notion is no longer "proof" but "verification". We'll explore how type theories of this sort arise naturally as enrichments of logical theories with further judgements, and contrast this with modern proof-theoretic type theories which interpret the judgements and proofs of logics, not their propositions and verifications.
Recognition from Hand Cameras
Venue: arXiv cs.CV 2016
Year: 2016

We revisit the study of a wrist-mounted camera system (referred to as HandCam) for recognizing activities of hands. HandCam has two unique properties as compared to egocentric systems (referred to as HeadCam): (1) it avoids the need to detect hands; (2) it more consistently observes the activities of hands. By taking advantage of these properties, we propose a deep-learning-based method to recognize hand states (free v.s. active hands, hand gestures, object categories), and discover object categories. Moreover, we propose a novel two-streams deep network to further take advantage of both HandCam and HeadCam. We have collected a new synchronized HandCam and HeadCam dataset with 20 videos captured in three scenes for hand states recognition. Experiments show that our HandCam system consistently outperforms a deep-learning-based HeadCam method (with estimated manipulation regions) and a dense-trajectory-based HeadCam method in all tasks. We also show that HandCam videos captured by different users can be easily aligned to improve free v.s. active recognition accuracy (3.3% improvement) in across-scenes use case. Moreover, we observe that finetuning Convolutional Neural Network consistently improves accuracy. Finally, our novel two-streams deep network combining HandCam and HeadCam features achieves the best performance in four out of five tasks. With more data, we believe a joint HandCam and HeadCam system can robustly log hand states in daily life.
Inter-Vehicle Range Estimation from Periodic Broadcasts
Venue: arXiv cs.NI 2016
Year: 2016

Dedicated short-range communication (DSRC) enables vehicular communication using periodic broadcast messages. We propose to use these periodic broadcasts to perform inter-vehicle ranging. Motivated by this scenario, we study the general problem of precise range estimation between pairs of moving vehicles using periodic broadcasts. Each vehicle has its own independent and unsynchronized clock, which can exhibit significant drift between consecutive periodic broadcast transmissions. As a consequence, both the clock offsets and drifts need to be taken into account in addition to the vehicle motion to accurately estimate the vehicle ranges. We develop a range estimation algorithm using local polynomial smoothing of the vehicle motion. The proposed algorithm can be applied to networks with arbitrary number of vehicles and requires no additional message exchanges apart from the periodic broadcasts. We validate our algorithm on experimental data and show that the performance of the proposed approach is close to that obtained using unicast round-trip time ranging. In particular, we are able to achieve sub-meter ranging accuracies in vehicular scenarios. Our scheme requires additional timestamp information to be transmitted as part of the broadcast messages, and we develop a novel timestamp compression algorithm to minimize the resulting overhead.
Pseudo-Bayesian Robust PCA: Algorithms and Analyses
Venue: arXiv cs.CV 2016
Year: 2016

Commonly used in computer vision and other applications, robust PCA represents an algorithmic attempt to reduce the sensitivity of classical PCA to outliers. The basic idea is to learn a decomposition of some data matrix of interest into low rank and sparse components, the latter representing unwanted outliers. Although the resulting optimization problem is typically NP-hard, convex relaxations provide a computationally-expedient alternative with theoretical support. However, in practical regimes performance guarantees break down and a variety of non-convex alternatives, including Bayesian-inspired models, have been proposed to boost estimation quality. Unfortunately though, without additional a priori knowledge none of these methods can significantly expand the critical operational range such that exact principal subspace recovery is possible. Into this mix we propose a novel pseudo-Bayesian algorithm that explicitly compensates for design weaknesses in many existing non-convex approaches leading to state-of-the-art performance with a sound analytical foundation. Surprisingly, our algorithm can even outperform convex matrix completion despite the fact that the latter is provided with perfect knowledge of which entries are not corrupted.
Approximation-Friendly Discrepancy Rounding
Venue: arXiv cs.DS 2016
Year: 2016

Rounding linear programs using techniques from discrepancy is a recent approach that has been very successful in certain settings. However this method also has some limitations when compared to approaches such as randomized and iterative rounding. We provide an extension of the discrepancy-based rounding algorithm due to Lovett-Meka that (i) combines the advantages of both randomized and iterated rounding, (ii) makes it applicable to settings with more general combinatorial structure such as matroids. As applications of this approach, we obtain new results for various classical problems such as linear system rounding, degree-bounded matroid basis and low congestion routing.
Projection Theorems for the Rényi Divergence on $α$-Convex Sets
Venue: arXiv cs.IT 2016
Year: 2016

This paper studies forward and reverse projections for the Rényi divergence of order $α\in (0, \infty)$ on $α$-convex sets. The forward projection on such a set is motivated by some works of Tsallis {\em et al.} in statistical physics, and the reverse projection is motivated by robust statistics. In a recent work, van Erven and Harremoës proved a Pythagorean inequality for Rényi divergences on $α$-convex sets under the assumption that the forward projection exists. Continuing this study, a sufficient condition for the existence of forward projection is proved for probability measures on a general alphabet. For $α\in (1, \infty)$, the proof relies on a new Apollonius theorem for the Hellinger divergence, and for $α\in (0,1)$, the proof relies on the Banach-Alaoglu theorem from functional analysis. Further projection results are then obtained in the finite alphabet setting. These include a projection theorem on a specific $α$-convex set, which is termed an {\em $α$-linear family}, generalizing a result by Csiszár for $α\neq 1$. The solution to this problem yields a parametric family of probability measures which turns out to be an extension of the exponential family, and it is termed an {\em $α$-exponential family}. An orthogonality relationship between the $α$-exponential and $α$-linear families is established, and it is used to turn the reverse projection on an $α$-exponential family into a forward projection on a $α$-linear family. This paper also proves a convergence result of an iterative procedure used to calculate the forward projection on an intersection of a finite number of $α$-linear families.