OpenRaiser/Intern-Atlas huggingface dataset:
Updating Dynamic Random Hyperbolic Graphs in Sublinear Time
Venue: arXiv cs.DS 2018
Year: 2018

Generative network models play an important role in algorithm development, scaling studies, network analysis, and realistic system benchmarks for graph data sets. A complex network model gaining considerable popularity builds random hyperbolic graphs, generated by distributing points within a disk in the hyperbolic plane and then adding edges between points with a probability depending on their hyperbolic distance. We present a dynamic extension to model gradual network change, while preserving at each step the point position probabilities. To process the dynamic changes efficiently, we formalize the concept of a probabilistic neighborhood: Let $P$ be a set of $n$ points in Euclidean or hyperbolic space, $q$ a query point, $\operatorname{dist}$ a distance metric, and $f : \mathbb{R}^+ \rightarrow [0,1]$ a monotonically decreasing function. Then, the probabilistic neighborhood $N(q, f)$ of $q$ with respect to $f$ is a random subset of $P$ and each point $p \in P$ belongs to $N(q,f)$ with probability $f(\operatorname{dist}(p,q))$. We present a fast, sublinear-time query algorithm to sample probabilistic neighborhoods from planar point sets. For certain distributions of planar $P$, we prove that our algorithm answers a query in $O((|N(q,f)| + \sqrt{n})\log n)$ time with high probability. This enables us to process a node movement in random hyperbolic graphs in sublinear time, resulting in a speedup of about one order of magnitude in practice compared to the fastest previous approach. Apart from that, our query algorithm is also applicable to Euclidean geometry, making it of independent interest for other sampling or probabilistic spreading scenarios.
Parallelizing Workload Execution in Embedded and High-Performance Heterogeneous Systems
Venue: arXiv cs.DC 2018
Year: 2018

In this paper, we introduce a software-defined framework that enables the parallel utilization of all the programmable processing resources available in heterogeneous system-on-chip (SoC) including FPGA-based hardware accelerators and programmable CPUs. Two platforms with different architectures are considered, and a single C/C++ source code is used in both of them for the CPU and FPGA resources. Instead of simply using the hardware accelerator to offload a task from the CPU, we propose a scheduler that dynamically distributes the tasks among all the resources to fully exploit all computing devices while minimizing load unbalance. The multi-architecture study compares an ARMV7 and ARMV8 implementation with different number and type of CPU cores and also different FPGA micro-architecture and size. We measure that both platforms benefit from having the CPU cores assist FPGA execution at the same level of energy requirements.
Device-to-Device Communications in the Millimeter Wave Band: A Novel Distributed Mechanism
Venue: arXiv cs.IT 2018
Year: 2018

In spite of its potential advantages, the large-scale implementation of the device-to-device (D2D) communications has yet to be realized, mainly due to severe interference and lack of enough bandwidth in the microwave ($μ$W) band. Recently, exploiting the millimeter wave (mmW) band for D2D communications has attracted considerable attention as a potential solution to these challenges. However, its severe sensitivity to blockage along with its directional nature make the utilization of the mmW band a challenging task as it requires line-of-sight (LOS) link detection and careful beam alignment between the D2D transceivers. In this paper, we propose a novel distributed mechanism which enables the D2D devices to discover unblocked LOS links for the mmW band communication. Moreover, as such LOS links are not always available, the proposed mechanism allows the D2D devices to switch to the $μ$W band if necessary. In addition, the proposed mechanism detects the direction of the LOS links to perform the beam alignment. We have used tools from stochastic geometry to evaluate the performance of the proposed mechanism in terms of the signal-to-interference-plus-noise ratio (SINR) coverage probability. The performance of the proposed algorithm is then compared to the one of the single band (i.e., $μ$W/mmW) communication. The simulation results show that the proposed mechanism considerably outperforms the single band communication.
Confluence Modulo Equivalence with Invariants in Constraint Handling Rules
Venue: arXiv cs.LO 2018
Year: 2018

Confluence denotes the property of a state transition system that states can be rewritten in more than one way yielding the same result. Although it is a desirable property, confluence is often too strict in practical applications because it also considers states that can never be reached in practice. Additionally, sometimes states that have the same semantics in the practical context are considered as different states due to different syntactic representations. By introducing suitable invariants and equivalence relations on the states, programs may have the property to be confluent modulo the equivalence relation w.r.t. the invariant which often is desirable in practice. In this paper, a sufficient and necessary criterion for confluence modulo equivalence w.r.t. an invariant for Constraint Handling Rules (CHR) is presented. It is the first approach that covers invariant-based confluence modulo equivalence for the de facto standard semantics of CHR. There is a trade-off between practical applicability and the simplicity of proving a confluence property. Therefore, a better manageable subset of equivalence relations has been identified that allows for the proposed confluence criterion and and simplifies the confluence proofs by using well established CHR analysis methods.
Adding transmitters dramatically boosts coded-caching gains for finite file sizes
Venue: arXiv cs.IT 2018
Year: 2018

In the context of coded caching in the $K$-user BC, our work reveals the surprising fact that having multiple ($L$) transmitting antennas, dramatically ameliorates the long-standing subpacketization bottleneck of coded caching by reducing the required subpacketization to approximately its $L$th root, thus boosting the actual DoF by a multiplicative factor of up to $L$. In asymptotic terms, this reveals that as long as $L$ scales with the theoretical caching gain, then the full cumulative (multiplexing + full caching) gains are achieved with constant subpacketization. This is the first time, in any known setting, that unbounded caching gains appear under finite file-size constraints. The achieved caching gains here are up to $L$ times higher than any caching gains previously experienced in any single- or multi-antenna fully-connected setting, thus offering a multiplicative mitigation to a subpacketization problem that was previously known to hard-bound caching gains to small constants. The proposed scheme is practical and it works for all values of $K,L$ and all cache sizes. The scheme's gains show in practice: e.g. for $K=100$, when $L=1$ the theoretical caching gain of $G=10$, under the original coded caching algorithm, would have needed subpacketization $S_1 = \binom{K}{G}= \binom{100}{10} > 10^{13}$, while if extra transmitting antennas were added, the subpacketization was previously known to match or exceed $S_1$. Now for $L=5$, our scheme offers the theoretical (unconstrained) cumulative DoF $d_L = L+G = 5+10=15$, with subpacketization $S_L=\binom{K/L}{G/L} =\binom{100/5}{10/5} = 190$. The work extends to the multi-server and cache-aided IC settings, while the scheme's performance, given subpacketization $S_L=\binom{K/L}{G/L}$, is within a factor of 2 from the optimal linear sum-DoF.
Same-different problems strain convolutional neural networks
Venue: arXiv cs.CV 2018
Year: 2018

The robust and efficient recognition of visual relations in images is a hallmark of biological vision. We argue that, despite recent progress in visual recognition, modern machine vision algorithms are severely limited in their ability to learn visual relations. Through controlled experiments, we demonstrate that visual-relation problems strain convolutional neural networks (CNNs). The networks eventually break altogether when rote memorization becomes impossible, as when intra-class variability exceeds network capacity. Motivated by the comparable success of biological vision, we argue that feedback mechanisms including attention and perceptual grouping may be the key computational components underlying abstract visual reasoning.\
Battery Energy Storage Scheduling for Optimal Load Variance Minimization
Venue: arXiv cs.SY 2018
Year: 2018

Generation portfolio can be significantly altered due to the deployment of distributed energy resources (DER) in distribution networks and the concept of microgrid. Generally, distribution networks can operate in a more resilient and economic fashion through proper coordination of DER. However, due to the partially uncontrollable and stochastic nature of some DER, the variance of net load of distribution systems increases, which raises the operational cost and complicates operation for transmission companies. This motivates peak shaving and valley filling using energy storage units deployed in distribution systems. This paper aims at theoretical formulation of optimal load variance minimization, where the infinity norm of net load is minimized. Then, the problem is reformulated equivalently as a linear program. A case study is performed with capacity-limited battery energy storage model and the simplified power flow model of a radial distribution network. The influence of capacity limit and deployment location are studied.
Metric Learning via Maximizing the Lipschitz Margin Ratio
Venue: arXiv cs.LG 2018
Year: 2018

In this paper, we propose the Lipschitz margin ratio and a new metric learning framework for classification through maximizing the ratio. This framework enables the integration of both the inter-class margin and the intra-class dispersion, as well as the enhancement of the generalization ability of a classifier. To introduce the Lipschitz margin ratio and its associated learning bound, we elaborate the relationship between metric learning and Lipschitz functions, as well as the representability and learnability of the Lipschitz functions. After proposing the new metric learning framework based on the introduced Lipschitz margin ratio, we also prove that some well known metric learning algorithms can be shown as special cases of the proposed framework. In addition, we illustrate the framework by implementing it for learning the squared Mahalanobis metric, and by demonstrating its encouraging results on eight popular datasets of machine learning.
An LSTM Recurrent Network for Step Counting
Venue: arXiv cs.LG 2018
Year: 2018

Smartphones with sensors such as accelerometer and gyroscope can be used as pedometers and navigators. In this paper, we propose to use an LSTM recurrent network for counting the number of steps taken by both blind and sighted users, based on an annotated smartphone sensor dataset, WeAllWork. The models were trained separately for sighted people, blind people with a long cane or a guide dog for Leave-One-Out training modality. It achieved 5% overcount and undercount rate.
The Importance of Norm Regularization in Linear Graph Embedding: Theoretical Analysis and Empirical Demonstration
Venue: arXiv cs.LG 2018
Year: 2018

Learning distributed representations for nodes in graphs is a crucial primitive in network analysis with a wide spectrum of applications. Linear graph embedding methods learn such representations by optimizing the likelihood of both positive and negative edges while constraining the dimension of the embedding vectors. We argue that the generalization performance of these methods is not due to the dimensionality constraint as commonly believed, but rather the small norm of embedding vectors. Both theoretical and empirical evidence are provided to support this argument: (a) we prove that the generalization error of these methods can be bounded by limiting the norm of vectors, regardless of the embedding dimension; (b) we show that the generalization performance of linear graph embedding methods is correlated with the norm of embedding vectors, which is small due to the early stopping of SGD and the vanishing gradients. We performed extensive experiments to validate our analysis and showcased the importance of proper norm regularization in practice.
Junk News on Military Affairs and National Security: Social Media Disinformation Campaigns Against US Military Personnel and Veterans
Venue: arXiv cs.SI 2018
Year: 2018

Social media provides political news and information for both active duty military personnel and veterans. We analyze the subgroups of Twitter and Facebook users who spend time consuming junk news from websites that target US military personnel and veterans with conspiracy theories, misinformation, and other forms of junk news about military affairs and national security issues. (1) Over Twitter we find that there are significant and persistent interactions between current and former military personnel and a broad network of extremist, Russia-focused, and international conspiracy subgroups. (2) Over Facebook, we find significant and persistent interactions between public pages for military and veterans and subgroups dedicated to political conspiracy, and both sides of the political spectrum. (3) Over Facebook, the users who are most interested in conspiracy theories and the political right seem to be distributing the most junk news, whereas users who are either in the military or are veterans are among the most sophisticated news consumers, and share very little junk news through the network.
Downlink User Association and Uplink Scheduling for Energy Harvesting Users in Software-Defined Mobile Networks
Venue: arXiv cs.IT 2018
Year: 2018

In this paper we consider a heterogeneous network which consists of a macro base station and some pico base stations utilizing massive MIMO and MIMO techniques, respectively. A central software-defined mobile network (SDMN) controller is adopted in order to provide user association and energy scheduling. The users are considered battery limited and are capable of simultaneous wireless information and power transfer (SWIPT) in order to harvest energy and address the energy shortage issue. These users harvest energy from the received signals in the downlink and consume it via their uplink communications. This paper deals with the downlink user association by jointly optimizing the overall sum-rate of the network and the harvested energy by introducing an appropriate utility function. In this regard, the optimum user association and power splitting factor for each user are calculated via the downlink optimization stage. Then, the process of uplink scheduling is defined as choosing the best users in each time epoch to transfer data as well as optimizing their transmit power by solving Lyapunov drift-plus-penalty function. Simulation results are provided in order to confirm the optimality of the proposed algorithm in comparison with the previous user association and uplink scheduling approaches in terms of providing fairness and battery management among users.
2-gram-based Phonetic Feature Generation for Convolutional Neural Network in Assessment of Trademark Similarity
Venue: arXiv cs.SD 2018
Year: 2018

A trademark is a mark used to identify various commodities. If same or similar trademark is registered for the same or similar commodity, the purchaser of the goods may be confused. Therefore, in the process of trademark registration examination, the examiner judges whether the trademark is the same or similar to the other applied or registered trademarks. The confusion in trademarks is based on the visual, phonetic or conceptual similarity of the marks. In this paper, we focus specifically on the phonetic similarity between trademarks. We propose a method to generate 2D phonetic feature for convolutional neural network in assessment of trademark similarity. This proposed algorithm is tested with 12,553 trademark phonetic similar pairs and 34,020 trademark phonetic non-similar pairs from 2010 to 2016. As a result, we have obtained approximately 92% judgment accuracy.
Network Flow-Based Refinement for Multilevel Hypergraph Partitioning
Venue: arXiv cs.DS 2018
Year: 2018

We present a refinement framework for multilevel hypergraph partitioning that uses max-flow computations on pairs of blocks to improve the solution quality of a $k$-way partition. The framework generalizes the flow-based improvement algorithm of KaFFPa from graphs to hypergraphs and is integrated into the hypergraph partitioner KaHyPar. By reducing the size of hypergraph flow networks, improving the flow model used in KaFFPa, and developing techniques to improve the running time of our algorithm, we obtain a partitioner that computes the best solutions for a wide range of benchmark hypergraphs from different application areas while still having a running time comparable to that of hMetis.
Document Classification Using Distributed Machine Learning
Venue: arXiv cs.IR 2018
Year: 2018

In this paper, we investigate the performance and success rates of Naïve Bayes Classification Algorithm for automatic classification of Turkish news into predetermined categories like economy, life, health etc. We use Apache Big Data technologies such as Hadoop, HDFS, Spark and Mahout, and apply these distributed technologies to Machine Learning.
Distributed NLP
Venue: arXiv cs.DC 2018
Year: 2018

In this paper we present the performance of parallel text processing with Map Reduce on a cloud platform. Scientific papers in Turkish language are processed using Zemberek NLP library. Experiments were run on a Hadoop cluster and compared with the single machines performance.
Searching isomorphic graphs
Venue: arXiv cs.DS 2018
Year: 2018

To determine that two given undirected graphs are isomorphic, we construct for them auxiliary graphs, using the breadth-first search. This makes capability to position vertices in each digraph with respect to each other. If the given graphs are isomorphic, in each of them we can find such positionally equivalent auxiliary digraphs that have the same mutual positioning of vertices. Obviously, if the given graphs are isomorphic, then such equivalent digraphs exist. Proceeding from the arrangement of vertices in one of the digraphs, we try to determine the corresponding vertices in another digraph. As a result we develop the algorithm for constructing a bijective mapping between vertices of the given graphs if they are isomorphic. The running time of the algorithm equal to $O(n^5)$, where $n$ is the number of graph vertices.
Beyond Markov Logic: Efficient Mining of Prediction Rules in Large Graphs
Venue: arXiv cs.DB 2018
Year: 2018

Graph representations of large knowledge bases may comprise billions of edges. Usually built upon human-generated ontologies, several knowledge bases do not feature declared ontological rules and are far from being complete. Current rule mining approaches rely on schemata or store the graph in-memory, which can be unfeasible for large graphs. In this paper, we introduce HornConcerto, an algorithm to discover Horn clauses in large graphs without the need of a schema. Using a standard fact-based confidence score, we can mine close Horn rules having an arbitrary body size. We show that our method can outperform existing approaches in terms of runtime and memory consumption and mine high-quality rules for the link prediction task, achieving state-of-the-art results on a widely-used benchmark. Moreover, we find that rules alone can perform inference significantly faster than embedding-based methods and achieve accuracies on link prediction comparable to resource-demanding approaches such as Markov Logic Networks.
Deep learning with t-exponential Bayesian kitchen sinks
Venue: arXiv cs.LG 2018
Year: 2018

Bayesian learning has been recently considered as an effective means of accounting for uncertainty in trained deep network parameters. This is of crucial importance when dealing with small or sparse training datasets. On the other hand, shallow models that compute weighted sums of their inputs, after passing them through a bank of arbitrary randomized nonlinearities, have been recently shown to enjoy good test error bounds that depend on the number of nonlinearities. Inspired from these advances, in this paper we examine novel deep network architectures, where each layer comprises a bank of arbitrary nonlinearities, linearly combined using multiple alternative sets of weights. We effect model training by means of approximate inference based on a t-divergence measure; this generalizes the Kullback-Leibler divergence in the context of the t-exponential family of distributions. We adopt the t-exponential family since it can more flexibly accommodate real-world data, that entail outliers and distributions with fat tails, compared to conventional Gaussian model assumptions. We extensively evaluate our approach using several challenging benchmarks, and provide comparative results to related state-of-the-art techniques.
Faster Distributed Shortest Path Approximations via Shortcuts
Venue: arXiv cs.DS 2018
Year: 2018

A long series of recent results and breakthroughs have led to faster and better distributed approximation algorithms for single source shortest paths (SSSP) and related problems in the CONGEST model. The runtime of all these algorithms, however, is $\tildeΩ(\sqrt{n})$, regardless of the network topology, even on nice networks with a (poly)logarithmic network diameter $D$. While this is known to be necessary for some pathological networks, most topologies of interest are arguably not of this type. We give the first distributed approximation algorithms for shortest paths problems that adjust to the topology they are run on, thus achieving significantly faster running times on many topologies of interest. The running time of our algorithms depends on and is close to $Q$, where $Q$ is the quality of the best shortcut that exists for the given topology. While $Q = \tildeΘ(\sqrt{n} + D)$ for pathological worst-case topologies, many topologies of interest have $Q = \tildeΘ(D)$, which results in near instance optimal running times for our algorithm, given the trivial $Ω(D)$ lower bound. The problems we consider are as follows: (1) an approximate shortest path tree and SSSP distances, (2) a polylogarithmic size distance label for every node such that from the labels of any two nodes alone one can determine their distance (approximately), and (3) an (approximately) optimal flow for the transshipment problem. Our algorithms have a tunable tradeoff between running time and approximation ratio. Our fastest algorithms have an arbitrarily good polynomial approximation guarantee and an essentially optimal $\tilde{O}(Q)$ running time. On the other end of the spectrum, we achieve polylogarithmic approximations in $\tilde{O}(Q \cdot n^ε)$ rounds for any $ε> 0$.
Understanding Convolutional Networks with APPLE : Automatic Patch Pattern Labeling for Explanation
Venue: arXiv cs.LG 2018
Year: 2018

With the success of deep learning, recent efforts have been focused on analyzing how learned networks make their classifications. We are interested in analyzing the network output based on the network structure and information flow through the network layers. We contribute an algorithm for 1) analyzing a deep network to find neurons that are 'important' in terms of the network classification outcome, and 2)automatically labeling the patches of the input image that activate these important neurons. We propose several measures of importance for neurons and demonstrate that our technique can be used to gain insight into, and explain how a network decomposes an image to make its final classification.