November 2016 - Dm-meeting - mailman.cs.vt.edu

DM-Meeting next week
by Liangzhe Chen 25 Nov '16

25 Nov '16

Please join us for our next DM-Meeting. ===DM-Meeting Fall 2016=== WHO: Xinfeng Xu WHEN: Tuesday, Nov 29, 2016 @ 12:15 noon WHERE: Torg 3160 A WHAT: Xinfeng will talk about the following three papers. 1. *On the Connectivity of Multi-layered Networks: Models, Measures and Optimal Control, ICDM'15* Networks appear naturally in many high-impact real-world applications. In an increasingly connected and coupled world, the networks arising from many application domains are often collected from different channels, forming the socalled multi-layered networks, such as cyber-physical systems, organization-level collaboration platforms, critical infrastructure networks and many more. Compared with single-layered networks, multi-layered networks are more vulnerable as even a small disturbance on one supporting layer/network might cause a ripple effect to all the dependent layers, leading to a catastrophic/cascading failure of the entire system. The state-of-theart has been largely focusing on modeling and manipulating the cascading effect of two-layered interdependent network systems for some specific type of network connectivity measure. This paper generalizes the challenge to multiple dimensions. First, we propose a new data model for multi-layered networks (MULAN), which admits an arbitrary number of layers with a much more flexible dependency structure among different layers, beyond the current pair-wise dependency. Second, we unify a wide range of classic network connectivity measures (SUBLINE). Third, we show that for any connectivity measure in the SUBLINE family, it enjoys the diminishing returns property which in turn lends itself to a family of provable near-optimal control algorithms with linear complexity. Finally, we conduct extensive empirical evaluations on real network data, to validate the effectiveness of the proposed algorithms. 2.* Cascading failures in interdependent networks with finite functional components, Physical Review 2016* We present a cascading failure model of two interdependent networks in which functional nodes belong to components of size greater than or equal to s. We find theoretically and via simulation that in complex networks with random dependency links the transition is first order for s 3 and continuous for s = 2. We also study interdependent lattices with a distance constraint r in the dependency links and find that increasing r moves the system from a regime without a phase transition to one with a second-order transition. As r continues to increase, the system collapses in a first-order transition. Each regime is associated with a different structure of domain formation of functional nodes. 3. *Catastrophic cascade of failures in interdependent networks, Nature 2010* Complex networks have been studied intensively for a decade, but research still focuses on the limited case of a single, non-interacting network1–14. Modern systems are coupled together15–19 and therefore should be modelled as interdependent networks. A fundamental property of interdependent networks is that failure of nodes in one network may lead to failure of dependent nodes in other networks. This may happen recursively and can lead to a cascade of failures. In fact, a failure of a very small fraction of nodes in one network may lead to the complete fragmentation of a system of several interdependent networks. A dramatic real-world example of a cascade of failures (‘concurrent malfunction’) is the electrical blackout that affected much of Italy on 28 September 2003: the shutdown of power stations directly led to the failure of nodes in the Internet communication network, which in turn caused further breakdown of power stations20. Here we develop a framework for understanding the robustness of interacting networks subject to such cascading failures. We present exact analytical solutions for the critical fraction of nodes that, on removal, will lead to a failure cascade and to a complete fragmentation of two interdependent networks. Surprisingly, a broader degree distribution increases the vulnerability of interdependent networks to random failure, which is opposite to how a single network behaves. Our findings highlight the need to consider interdependent network properties in designing robust networks. Regards, Liangzhe

1 0

Follow-up on DM meeting
by Bijaya Adhikari 22 Nov '16

22 Nov '16

Hello Everyone, We had two interesting questions in our meeting today. They were as follows: 1) Why SDNE (or auto enconder in general) uses sigmoid function ? To capture non-linear network structure, SDNE requires non-linear activation function. It seems like the authors chose sigmoid function as it is one of the standard non-linear activation function. Other activation functions commonly used by auto-encoder are ReLU and tanh. Authors have not compared sigmoid against other activation functions. 2) How are hyper-parameters optimized ? In SDNE, they use grid search (aka parameter sweep) on the validation set to tune hyper parameters. The idea is that we select reasonable set of values for each hyper parameter. Then for each combination of parameter values, we train the model on training set, and choose the combination that performs the best in the held-out validation set. Alternatives for grid search are random search, in which parameters are randomly sampled from the parameter space, and Bayesian optimization. In Bayesian optimization, we assume that there is a function that maps parameters to the objective value and we also assume prior over the 'unkown' function. After training is performed, prior is updated to form posterior distribution. Next parameters to evaluate are sampled from 'acquisition function ' constructed from the posterior. Bayesian optimization seems to do better than grid search and random search. Best regards, Bijaya.

1 0

DM-Meeting next week
by Liangzhe Chen 18 Nov '16

18 Nov '16

Please join us for our next DM-Meeting. ===DM-Meeting Fall 2016=== WHO: Bijaya Adhikari WHEN: Tuesday, Nov 22, 2016 @ 12:15 noon WHERE: Torg 3160 A WHAT: Bijaya will talk about the following three papers: 1) Structural Deep Network Embedding <http://www.kdd.org/kdd2016/papers/files/rfp0191-wangAemb.pdf> by Peng Cui et. al. KDD 2016 Network embedding is an important method to learn low-dimensional representations of vertexes in networks, aiming to capture and preserve the network structure. Almost all the existing network embedding methods adopt shallow models. However, since the underlying network structure is complex, shallow models cannot capture the highly non-linear network structure, resulting in sub-optimal network representations. Therefore, how to find a method that is able to effectively capture the highly non-linear network structure and preserve the global and local structure is an open yet important problem. To solve this problem, in this paper we propose a Structural Deep Network Embedding method, namely SDNE. More specifically, we first propose a semi-supervised deep model, which has multiple layers of non-linear functions, thereby being able to capture the highly non-linear network structure. Then we propose to exploit the first-order and second-order proximity jointly to preserve the network structure. The second-order proximity is used by the unsupervised component to capture the global network structure. While the first-order proximity is used as the supervised information in the supervised component to preserve the local network structure. By jointly optimizing them in the semi-supervised deep model, our method can preserve both the local and global network structure and is robust to sparse networks. Empirically, we conduct the experiments on five real-world networks, including a language network, a citation network and three social networks. The results show that compared to the baselines, our method can reconstruct the original network significantly better and achieves substantial gains in three applications, i.e. multi-label classification, link prediction and visualization. 2) LINE: Large-scale Information Network Embedding <https://arxiv.org/pdf/1503.03578v1.pdf>. Jian Tang et. al. WWW 2015 This paper studies the problem of embedding very large information networks into low-dimensional vector spaces, which is useful in many tasks such as visualization, node classification, and link prediction. Most existing graph embedding methods do not scale for real world information networks which usually contain millions of nodes. In this paper, we propose a novel network embedding method called the “LINE,” which is suitable for arbitrary types of information networks: undirected, directed, and/or weighted. The method optimizes a carefully designed objective function that preserves both the local and global network structures. An edge-sampling algorithm is proposed that addresses the limitation of the classical stochastic gradient descent and improves both the effectiveness and the efficiency of the inference. Empirical experiments prove the effectiveness of the LINE on a variety of real-world information networks, including language networks, social networks, and citation networks. The algorithm is very efficient, which is able to learn the embedding of a network with millions of vertices and billions of edges in a few hours on a typical single machine. The source code of the LINE is available online.1 3) Asymmetric Transitivity Preserving Graph Embedding <http://www.kdd.org/kdd2016/papers/files/rfp0184-ouA.pdf> by Mingdong Ou et. al KDD 2016 This paper studies the problem of embedding very large information networks into low-dimensional vector spaces, which is useful in many tasks such as visualization, node classification, and link prediction. Most existing graph embedding methods do not scale for real world information networks which usually contain millions of nodes. In this paper, we propose a novel network embedding method called the “LINE,” which is suitable for arbitrary types of information networks: undirected, directed, and/or weighted. The method optimizes a carefully designed objective function that preserves both the local and global network structures. An edge-sampling algorithm is proposed that addresses the limitation of the classical stochastic gradient descent and improves both the effectiveness and the efficiency of the inference. Empirical experiments prove the effectiveness of the LINE on a variety of real-world information networks, including language networks, social networks, and citation networks. The algorithm is very efficient, which is able to learn the embedding of a network with millions of vertices and billions of edges in a few hours on a typical single machine. The source code of the LINE is available online.1 Regards, Liangzhe

1 0

DM-Meeting next week
by Liangzhe Chen 04 Nov '16

04 Nov '16

Please join us for our next DM-Meeting. ===DM-Meeting Fall 2016=== WHO: Liangzhe Chen WHEN: Tuesday, Nov 08, 2016 @ 12:15 noon WHERE: Torg 3160 A WHAT: Liangzhe will present the following two papers: Regime Shifts in Streams: Real-time Forecasting of Co-evolving Time Sequences <http://www.kdd.org/kdd2016/papers/files/rfp0245-matsubaraA.pdf> Yasuko Matsubara, Yasushi Sakura. KDD'16. Given a large, online stream of multiple co-evolving event sequences, such as sensor data and Web-click logs, that contains various types of non-linear dynamic evolving patterns of different durations, how can we efficiently and effectively capture important patterns? How do we go about forecasting long-term future events? In this paper, we present REGIMECAST, an efficient and effective method for forecasting co-evolving data streams. REGIMECAST is designed as an adaptive non-linear dynamical system, which is inspired by the concept of “regime shifts” in natural dynamical systems. Our method has the following properties: (a) Effective: it operates on large data streams, captures important patterns and performs long-term forecasting; (b) Adaptive: it automatically and incrementally recognizes the latent trends and dynamic evolution patterns (i.e., regimes) that are unknown in advance; (c) Scalable: it is fast and the computation cost does not depend on the length of data streams; (d) Any-time: it provides a response at any time and generates long-range future events. Extensive experiments on real datasets demonstrate that REGIMECAST does indeed make long-range forecasts, and it outperforms state-of-the-art competitors as regards accuracy and speed. FASCINATE: Fast Cross-Layer Dependency Inference on Multi-layered Networks <http://www.kdd.org/kdd2016/papers/files/rfp0696-chenA.pdf>Chen Chen, Hanghang Tong, Lei Xie, Lei Ying, Qing He. KDD'16 Multi-layered networks have recently emerged as a new network model, which naturally finds itself in many high-impact application domains, ranging from critical inter-dependent infrastructure networks, biological systems, organization-level collaborations, to cross-platform e-commerce, etc. Cross-layer dependency, which describes the dependencies or the associations between nodes across different layers/networks, often plays a central role in many data mining tasks on such multi-layered networks. Yet, it remains a daunting task to accurately know the cross-layer dependency a prior. In this paper, we address the problem of inferring the missing crosslayer dependencies on multi-layered networks. The key idea behind our method is to view it as a collective collaborative filtering problem. By formulating the problem into a regularized optimization model, we propose an effective algorithm to find the local optima with linear complexity. Furthermore, we derive an online algorithm to accommodate newly arrived nodes, whose complexity is just linear wrt the size of the neighborhood of the new node. We perform extensive empirical evaluations to demonstrate the effectiveness and the efficiency of the proposed methods. Regards, Liangzhe

1 0