OpenRaiser/Intern-Atlas huggingface dataset:
Higher-order clustering in networks
Venue: arXiv cs.SI 2018
Year: 2018

A fundamental property of complex networks is the tendency for edges to cluster. The extent of the clustering is typically quantified by the clustering coefficient, which is the probability that a length-2 path is closed, i.e., induces a triangle in the network. However, higher-order cliques beyond triangles are crucial to understanding complex networks, and the clustering behavior with respect to such higher-order network structures is not well understood. Here we introduce higher-order clustering coefficients that measure the closure probability of higher-order network cliques and provide a more comprehensive view of how the edges of complex networks cluster. Our higher-order clustering coefficients are a natural generalization of the traditional clustering coefficient. We derive several properties about higher-order clustering coefficients and analyze them under common random graph models. Finally, we use higher-order clustering coefficients to gain new insights into the structure of real-world networks from several domains.
Moment-based parameter estimation in binomial random intersection graph models
Venue: arXiv cs.SI 2018
Year: 2018

Binomial random intersection graphs can be used as parsimonious statistical models of large and sparse networks, with one parameter for the average degree and another for transitivity, the tendency of neighbours of a node to be connected. This paper discusses the estimation of these parameters from a single observed instance of the graph, using moment estimators based on observed degrees and frequencies of 2-stars and triangles. The observed data set is assumed to be a subgraph induced by a set of $n_0$ nodes sampled from the full set of $n$ nodes. We prove the consistency of the proposed estimators by showing that the relative estimation error is small with high probability for $n_0 \gg n^{2/3} \gg 1$. As a byproduct, our analysis confirms that the empirical transitivity coefficient of the graph is with high probability close to the theoretical clustering coefficient of the model.
Probabilistic $N$-$k$ Failure-Identification for Power Systems
Venue: arXiv cs.SY 2018
Year: 2018

This paper considers a probabilistic generalization of the $N$-$k$ failure-identification problem in power transmission networks, where the probability of failure of each component in the network is known a priori and the goal of the problem is to find a set of $k$ components that maximizes disruption to the system loads weighted by the probability of simultaneous failure of the $k$ components. The resulting problem is formulated as a bilevel mixed-integer nonlinear program. Convex relaxations, linear approximations, and heuristics are developed to obtain feasible solutions that are close to the optimum. A general cutting-plane algorithm is proposed to solve the convex relaxation and linear approximations of the $N$-$k$ problem. Extensive numerical results corroborate the effectiveness of the proposed algorithms on small-, medium-, and large-scale test instances, the test instances include the IEEE 14-bus system, the IEEE single-area and three-area RTS96 systems, the IEEE 118-bus system, the WECC 240-bus test system, the 1354-bus PEGASE system, and the 2383-bus Polish winter-peak test system.
Learning to Generate Long-term Future via Hierarchical Prediction
Venue: arXiv cs.CV 2018
Year: 2018

We propose a hierarchical approach for making long-term predictions of future frames. To avoid inherent compounding errors in recursive pixel-level prediction, we propose to first estimate high-level structure in the input frames, then predict how that structure evolves in the future, and finally by observing a single frame from the past and the predicted high-level structure, we construct the future frames without having to observe any of the pixel-level predictions. Long-term video prediction is difficult to perform by recurrently observing the predicted frames because the small errors in pixel space exponentially amplify as predictions are made deeper into the future. Our approach prevents pixel-level error propagation from happening by removing the need to observe the predicted frames. Our model is built with a combination of LSTM and analogy based encoder-decoder convolutional neural networks, which independently predict the video structure and generate the future frames, respectively. In experiments, our model is evaluated on the Human3.6M and Penn Action datasets on the task of long-term pixel-level video prediction of humans performing actions and demonstrate significantly better results than the state-of-the-art.
Accurately and Efficiently Interpreting Human-Robot Instructions of Varying Granularities
Venue: arXiv cs.AI 2018
Year: 2018

Humans can ground natural language commands to tasks at both abstract and fine-grained levels of specificity. For instance, a human forklift operator can be instructed to perform a high-level action, like "grab a pallet" or a low-level action like "tilt back a little bit." While robots are also capable of grounding language commands to tasks, previous methods implicitly assume that all commands and tasks reside at a single, fixed level of abstraction. Additionally, methods that do not use multiple levels of abstraction encounter inefficient planning and execution times as they solve tasks at a single level of abstraction with large, intractable state-action spaces closely resembling real world complexity. In this work, by grounding commands to all the tasks or subtasks available in a hierarchical planning framework, we arrive at a model capable of interpreting language at multiple levels of specificity ranging from coarse to more granular. We show that the accuracy of the grounding procedure is improved when simultaneously inferring the degree of abstraction in language used to communicate the task. Leveraging hierarchy also improves efficiency: our proposed approach enables a robot to respond to a command within one second on 90% of our tasks, while baselines take over twenty seconds on half the tasks. Finally, we demonstrate that a real, physical robot can ground commands at multiple levels of abstraction allowing it to efficiently plan different subtasks within the same planning hierarchy.
Boundary First Flattening
Venue: arXiv cs.GR 2018
Year: 2018

A conformal flattening maps a curved surface to the plane without distorting angles---such maps have become a fundamental building block for problems in geometry processing, numerical simulation, and computational design. Yet existing methods provide little direct control over the shape of the flattened domain, or else demand expensive nonlinear optimization. Boundary first flattening (BFF) is a linear method for conformal parameterization which is faster than traditional linear methods, yet provides control and quality comparable to sophisticated nonlinear schemes. The key insight is that the boundary data for many conformal mapping problems can be efficiently constructed via the Cherrier formula together with a pair of Poincare-Steklov operators; once the boundary is known, the map can be easily extended over the rest of the domain. Since computation demands only a single factorization of the real Laplace matrix, the amortized cost is about 50x less than any previously published technique for boundary-controlled conformal flattening. As a result, BFF opens the door to real-time editing or fast optimization of high-resolution maps, with direct control over boundary length or angle. We show how this method can be used to construct maps with sharp corners, cone singularities, minimal area distortion, and uniformization over the unit disk; we also demonstrate for the first time how a surface can be conformally flattened directly onto any given target shape.
Second-order Temporal Pooling for Action Recognition
Venue: arXiv cs.CV 2018
Year: 2018

Deep learning models for video-based action recognition usually generate features for short clips (consisting of a few frames); such clip-level features are aggregated to video-level representations by computing statistics on these features. Typically zero-th (max) or the first-order (average) statistics are used. In this paper, we explore the benefits of using second-order statistics. Specifically, we propose a novel end-to-end learnable feature aggregation scheme, dubbed temporal correlation pooling that generates an action descriptor for a video sequence by capturing the similarities between the temporal evolution of clip-level CNN features computed across the video. Such a descriptor, while being computationally cheap, also naturally encodes the co-activations of multiple CNN features, thereby providing a richer characterization of actions than their first-order counterparts. We also propose higher-order extensions of this scheme by computing correlations after embedding the CNN features in a reproducing kernel Hilbert space. We provide experiments on benchmark datasets such as HMDB-51 and UCF-101, fine-grained datasets such as MPII Cooking activities and JHMDB, as well as the recent Kinetics-600. Our results demonstrate the advantages of higher-order pooling schemes that when combined with hand-crafted features (as is standard practice) achieves state-of-the-art accuracy.
Coherent multiple-antenna block-fading channels at finite blocklength
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we consider a channel model that is often used to describe the mobile wireless scenario: multiple-antenna additive white Gaussian noise channels subject to random (fading) gain with full channel state information at the receiver. Dynamics of the fading process are approximated by a piecewise-constant process (frequency non-selective isotropic block fading). This work addresses the finite blocklength fundamental limits of this channel model. Specifically, we give a formula for the channel dispersion -- a quantity governing the delay required to achieve capacity. Multiplicative nature of the fading disturbance leads to a number of interesting technical difficulties that required us to enhance traditional methods for finding channel dispersion. Alas, one difficulty remains: the converse (impossibility) part of our result holds under an extra constraint on the growth of the peak-power with blocklength. Our results demonstrate, for example, that while capacities of $n_t\times n_r$ and $n_r \times n_t$ antenna configurations coincide (under fixed received power), the coding delay can be quite sensitive to this switch. For example, at the received SNR of $20$ dB the $16\times 100$ system achieves capacity with codes of length (delay) which is only $60\%$ of the length required for the $100\times 16$ system. Another interesting implication is that for the MISO channel, the dispersion-optimal coding schemes require employing orthogonal designs such as Alamouti's scheme -- a surprising observation considering the fact that Alamouti's scheme was designed for reducing demodulation errors, not improving coding rate. Finding these dispersion-optimal coding schemes naturally gives a criteria for producing orthogonal design-like inputs in dimensions where orthogonal designs do not exist.
An ADMM Approach to Masked Signal Decomposition Using Subspace Representation
Venue: arXiv cs.CV 2018
Year: 2018

Signal decomposition is a classical problem in signal processing, which aims to separate an observed signal into two or more components each with its own property. Usually each component is described by its own subspace or dictionary. Extensive research has been done for the case where the components are additive, but in real world applications, the components are often non-additive. For example, an image may consist of a foreground object overlaid on a background, where each pixel either belongs to the foreground or the background. In such a situation, to separate signal components, we need to find a binary mask which shows the location of each component. Therefore it requires to solve a binary optimization problem. Since most of the binary optimization problems are intractable, we relax this problem to the approximated continuous problem, and solve it by alternating optimization technique. We show the application of the proposed algorithm for three applications: separation of text from background in images, separation of moving objects from a background undergoing global camera motion in videos, separation of sinusoidal and spike components in one dimensional signals. We demonstrate in each case that considering the non-additive nature of the problem can lead to significant improvement.
(Quasi)Periodicity Quantification in Video Data, Using Topology
Venue: arXiv cs.CV 2018
Year: 2018

This work introduces a novel framework for quantifying the presence and strength of recurrent dynamics in video data. Specifically, we provide continuous measures of periodicity (perfect repetition) and quasiperiodicity (superposition of periodic modes with non-commensurate periods), in a way which does not require segmentation, training, object tracking or 1-dimensional surrogate signals. Our methodology operates directly on video data. The approach combines ideas from nonlinear time series analysis (delay embeddings) and computational topology (persistent homology), by translating the problem of finding recurrent dynamics in video data, into the problem of determining the circularity or toroidality of an associated geometric space. Through extensive testing, we show the robustness of our scores with respect to several noise models/levels, we show that our periodicity score is superior to other methods when compared to human-generated periodicity rankings, and furthermore, we show that our quasiperiodicity score clearly indicates the presence of biphonation in videos of vibrating vocal folds, which has never before been accomplished end to end quantitatively.
Energy-Efficient Low-Power Circuit Techniques for Wireless Energy and Data Transfer in IoT Sensor Nodes
Venue: arXiv cs.ET 2018
Year: 2018

In this paper, we present techniques and examples to reduce power consumption and increase energy efficiency of autonomous Wireless Sensor Nodes (WSNs) for the Internet of Things. We focus on the RF Energy Harvester (RFEH), the data receiver and the transmitter, all of which have a large impact on the device cost, lifetime and functionality. Co-design of the antenna and the electronics is explored to boost the power conversion efficiency of the RF-DC converter. As a proof of principle, a charge pump rectifier is designed, and its measurement results are presented. To boost the rectifier output voltage, a DC-DC converter that employs maximum power point tracking has been designed. A prototype circuit is also presented that can accommodate an input power level range of 1 μW to 1 mW and offers peak efficiencies of 76.3% and 82% at 1 μW and 1 mW, respectively. The co-design principle is also used at the receiver side where the antenna-electronics interface is optimized. It is shown how this technique allows improving the noise figure of the Low Noise Amplifier (LNA) without sacrificing power consumption. As a low power alternative to narrow-band wireless transmission, sub-GHz ultra-wideband is proposed. As a proof of principle, the design of a novel low-power sub-GHz Ultra-Wide-Bandwidth (UWB) transmitter which consumes only 0.28 mW is presented. Its working principle is verified by means of circuit simulations and measurements. The low power nature of the transmitter and receiver principles, combined with the power efficient RF-DC converter paves the way towards the continuous operation of a WSN.
A Network Perspective on Attitude Strength: Testing the Connectivity Hypothesis
Venue: arXiv cs.SI 2018
Year: 2018

Attitude strength is a key characteristic of attitudes. Strong attitudes are durable and impactful, while weak attitudes are fluctuating and inconsequential. Recently, the Causal Attitude Network (CAN) model was proposed as a comprehensive measurement model of attitudes, which conceptualizes attitudes as networks of causally connected evaluative reactions (i.e., beliefs, feelings, and behavior toward an attitude object). Here, we test the central postulate of the CAN model that highly connected attitude networks correspond to strong attitudes. We use data from the American National Election Studies 1980-2012 on attitudes toward presidential candidates (total n = 18,795). We first show that political interest predicts connectivity of attitude networks toward presidential candidates. Second, we show that connectivity is strongly related to two defining features of strong attitudes - stability of the attitude and the attitude's impact on behavior. We conclude that network theory provides a promising framework to advance the understanding of attitude strength.
Attacking Machine Learning models as part of a cyber kill chain
Venue: arXiv cs.CR 2018
Year: 2018

Machine learning is gaining popularity in the network security domain as many more network-enabled devices get connected, as malicious activities become stealthier, and as new technologies like Software Defined Networking emerge. Compromising machine learning model is a desirable goal. In fact, spammers have been quite successful getting through machine learning enabled spam filters for years. While previous works have been done on adversarial machine learning, none has been considered within a defense-in-depth environment, in which correct classification alone may not be good enough. For the first time, this paper proposes a cyber kill-chain for attacking machine learning models together with a proof of concept. The intention is to provide a high level attack model that inspire more secure processes in research/design/implementation of machine learning based security solutions.
Statistical Multiplexing and Traffic Shaping Games for Network Slicing
Venue: arXiv cs.NI 2018
Year: 2018

Next generation wireless architectures are expected to enable slices of shared wireless infrastructure which are customized to specific mobile operators/services. Given infrastructure costs and the stochastic nature of mobile services' spatial loads, it is highly desirable to achieve efficient statistical multiplexing amongst such slices. We study a simple dynamic resource sharing policy which allocates a 'share' of a pool of (distributed) resources to each slice-Share Constrained Proportionally Fair (SCPF). We give a characterization of SCPF's performance gains over static slicing and general processor sharing. We show that higher gains are obtained when a slice's spatial load is more 'imbalanced' than, and/or 'orthogonal' to, the aggregate network load, and that the overall gain across slices is positive. We then address the associated dimensioning problem. Under SCPF, traditional network dimensioning translates to a coupled share dimensioning problem, which characterizes the existence of a feasible share allocation given slices' expected loads and performance requirements. We provide a solution to robust share dimensioning for SCPF-based network slicing. Slices may wish to unilaterally manage their users' performance via admission control which maximizes their carried loads subject to performance requirements. We show this can be modeled as a 'traffic shaping' game with an achievable Nash equilibrium. Under high loads, the equilibrium is explicitly characterized, as are the gains in the carried load under SCPF vs. static slicing. Detailed simulations of a wireless infrastructure supporting multiple slices with heterogeneous mobile loads show the fidelity of our models and range of validity of our high load equilibrium analysis.
Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density
Venue: arXiv cs.CG 2018
Year: 2018

In the classic circle packing problem, one asks whether a given set of circles can be packed into a given container. Packing problems like this have been shown to be $\mathsf{NP}$-hard. In this paper, we present new sufficient conditions for packing circles into square and triangular containers, using only the sum of the circles' areas: For square containers, it is possible to pack any set of circles with a combined area of up to approximately 53.90% of the square's area. And when the container is a right or obtuse triangle, any set of circles whose combined area does not exceed the triangle's incircle can be packed. These area conditions are tight, in the sense that for any larger areas, there are sets of circles which cannot be packed. Similar results have long been known for squares, but to the best of our knowledge, we give the first results of this type for circular objects. Our proofs are constructive: We describe a versatile, divide-and-conquer-based algorithm for packing circles into various container shapes with optimal worst-case density. It employs an elegant subdivision scheme that recursively splits the circles into two groups and then packs these into subcontainers. We call this algorithm "Split Packing". It can be used as a constant-factor approximation algorithm when looking for the smallest container in which a given set of circles can be packed, due to its polynomial runtime. A browser-based, interactive visualization of the Split Packing approach and other related material can be found at https://morr.cc/split-packing/
Fundamental Limits of Covert Communication over MIMO AWGN Channel
Venue: arXiv cs.IT 2018
Year: 2018

Fundamental limits of covert communication have been studied in literature for different models of scalar channels. It was shown that, over $n$ independent channel uses, $\mathcal{O}(\sqrt{n})$ bits can transmitted reliably over a public channel while achieving an arbitrarily low probability of detection (LPD) by other stations. This result is well known as square-root law and even to achieve this diminishing rate of covert communication, some form of shared secret is needed between the transmitter and the receiver. In this paper, we establish the limits of LPD communication over the MIMO AWGN channel. We define the notion of $ε$-probability of detection ($ε$-PD) and provide a formulation to evaluate the maximum achievable rate under the $ε$-PD constraint. We first show that the capacity-achieving input distribution is the zero-mean Gaussian distribution. Then, assuming channel state information (CSI) on only the main channel at the transmitter, we derive the optimal input covariance matrix, hence, establishing the $ε$-PD capacity. We evaluate $ε$-PD rates in the limiting regimes for the number of channel uses (asymptotic block length) and the number of antennas (massive MIMO). We show that, in the asymptotic block-length regime, while the SRL still holds for the MIMO AWGN, the number of bits that can be transmitted covertly scales exponentially with the number of transmitting antennas. Further, we derive the $ε$-PD capacity \textit{with no shared secret}. For that scenario, in the massive MIMO limit, higher covert rate up to the non LPD constrained capacity still can be achieved, yet, with much slower scaling compared to the scenario with shared secret. The practical implication of our result is that, MIMO has the potential to provide a substantial increase in the file sizes that can be covertly communicated subject to a reasonably low delay.