Search

This paper studies batch processing of core maintenance in hypergraph streams. We focus on updating the coreness of each vertex after the hypergraph evolves. Unlike existing works that mainly focus on exact coreness updates for the single hyperedge dynamic or approximate update, we propose the first known batch processing algorithms for exact core maintenance with insertions or deletions of multiple hyperedges. By proposing a hyperedge structure Joint Hyperedge Set, we tackle the challenges of quantifying the range of coreness change and finding potential vertices whose coreness may update. In addition, we accelerate coreness updates even further by finding structures that enable parallel execution. Extensive experiments illustrate the efficiency, scalability, and effectiveness of our batch core maintenance algorithms on real-world hypergraphs. It shows that our algorithms can be faster than the single hyperedge processing approaches by a factor of nearly half the number of hyperedges processed, and our parallel algorithms achieve linear acceleration with the increasing number of threads. [ABSTRACT FROM AUTHOR]

Decentralized machine learning has been playing an essential role in improving training efficiency. It has been applied in many real-world scenarios, such as edge computing and IoT. However, in fact, networks are dynamic, and there is a risk of information leaking during the communication process. To address this problem, we propose a decentralized parallel stochastic gradient descent algorithm (D-(DP)2SGD) with differential privacy in dynamic networks. With rigorous analysis, we show that D-(DP)2SGD converges with a rate of O 1 / K n while satisfying ε -DP, which achieves almost the same convergence rate as previous works without privacy concern. To the best of our knowledge, our algorithm is the first known decentralized parallel SGD algorithm that can implement in dynamic networks and take privacy-preserving into consideration. [ABSTRACT FROM AUTHOR]

The goal of spatio-temporal data mining is to discover previously unknown but useful patterns from the spatial and temporal data. However, explosive growth of the spatiotemporal data emphasizes the need for developing novel computationally efficient methods for large-scale data mining applications. Since lots of spatiotemporal data mining problems can be converted to an optimization problem, in this paper, we propose an efficient parameter-level parallel optimization algorithm for large-scale spatiotemporal data mining. In detail, most of previous optimization methods are based on gradient descent methods, which iteratively update the model and provide model-level convergence control for all parameters. Namely, they treat all parameters equally and keep updating all parameters until every parameter has converged. However, we find that during the iterative process, the convergence rates of model parameters are different from each other. This may cause redundant computation and reduce the performance. To solve this problem, we propose a parameter-level stochastic gradient descent (plpSGD), in which the convergence of each parameter is considered independently and only unconvergent parameters are updated in each iteration. Moreover, the updating of model parameters are parallelized in plpSGD to further improve the performance of SGD. We have conducted extensive experiments to evaluate the performance of plpSGD. The experimental results show that compared to previous SGD methods, plpSGD can significantly accelerate the convergence of SGD and achieve the excellent scalability with little sacrifice of the solution accuracy. [ABSTRACT FROM AUTHOR]

It has long been an area of interest to identify important vertices in social networks. Closeness centrality is one of the most popular measures of centrality of vertices. Generally speaking, it measures how a node is close to all other nodes on average. However, closeness centrality measures the centrality from a global view. Consequently, in real-world networks that is normally composed by some communities connected, using closeness centrality may suffer from the flaw that local central vertices within communities are neglected. To resolve this issue, we propose a new centrality measure, Hierarchical Closeness Centrality (HCC), to depict the local centrality of vertices. Experiments show that comparing with closeness centrality, HCC is a better index in finding most influential vertices and community detection. Furthermore, we present a parallel algorithm for HCC computation, by well analyzing the independence between vertices in the computation procedure. Extensive experiments on real-world datesets demonstrate that the parallel algorithm can greatly reduce the computation time compared to trivial algorithms. [ABSTRACT FROM AUTHOR]

The core number of vertices is a basic index depicting cohesiveness of a graph, and has been widely used in large-scale graph analytics. In this paper, we study the update of core numbers of vertices in dynamic graphs with edge insertions/deletions, which is known as the core maintenance problem. Different from previous approaches that just focus on the case of single-edge insertion/deletion and sequentially handle the edges when multiple edges are inserted/deleted, we investigate the parallelism in the core maintenance procedure. Specifically, we show that if the inserted/deleted edges constitute a matching, the core number update with respect to each inserted/deleted edge can be handled in parallel. Based on this key observation, we propose parallel algorithms for core maintenance in both cases of edge insertions and deletions. Extensive experiments are conducted to evaluate the efficiency, stability, parallelism and scalability of our algorithms on different types of real-world, synthetic graphs and temporal networks. Comparing with former approaches, our algorithms can improve the core maintenance efficiency significantly. [ABSTRACT FROM AUTHOR]