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

DM-Meeting this week (an hour earlier than usual)
by Liangzhe Chen 26 Apr '16

26 Apr '16

Please join us for our next DM-Meeting (our meeting will be from 11-12am this week). ===DM-Meeting Spring 2016=== WHO: Sorour Ekhtiari WHEN: Wednesday, April 6, 2016 @ 11:00 am WHERE: Torg 3160 A WHAT: I will talk about the following two papers: "Weighted Graph Cuts without Eigenvectors: A Multilevel Approach" http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.63.9867&rep=rep1&t… "User-Guided Large Attributed Graph Clustering with Multiple Sparse Annotations" http://link.springer.com/chapter/10.1007/978-3-319-31753-3_11 MORE INFO: Here are the brief abstracts of the two papers: -Weighted Graph Cuts without Eigenvectors: A Multilevel Approach A variety of clustering algorithms have recently been proposed to handle data that is not linearly separable; spectral clustering and kernel k-means are two of the main methods. In this paper, we discuss an equivalence between the objective functions used in these seemingly different methods— in particular, a general weighted kernel k-means objective is mathematically equivalent to a weighted graph clustering objec- tive. We exploit this equivalence to develop a fast, high-quality multilevel algorithm that directly optimizes various weighted graph clustering objectives, such as the popular ratio cut, normalized cut, and ratio association criteria. This eliminates the need for any eigenvector computation for graph clustering problems, which can be prohibitive for very large graphs. Previous multilevel graph partitioning methods, such as Metis, have suffered from the restriction of equal-sized clusters; our multilevel algorithm removes this restriction by using kernel k- means to optimize weighted graph cuts. Experimental results show that our multilevel algorithm outperforms a state-of-the-art spectral clustering algorithm in terms of speed, memory usage, and quality. We demonstrate that our algorithm is applicable to large-scale clustering tasks such as image segmentation, social network analysis and gene network analysis. -User-Guided Large Attributed Graph Clustering with Multiple Sparse Annotations *One of the key challenges in large attributed graph clustering is how to select representative attributes. Previous studies introduce user-guided clustering methods by letting a user select samples based on his/her knowledge. However, due to knowledge limitation, a single user may only pick out the samples that s/he is familiar with while ignore the others, such that the selected samples are often biased. We propose a framework to address this issue which allows multiple individuals to select samples for a specific clustering. With wider knowledge coming from multiple users, the selected samples can be more relevant to the target cluster. The challenges of this study are two-folds. Firstly, as user selected samples are usually sparse and the graph can be large, it is non-trivial to effectively combine the different annotations given by the multiple users. Secondly, it is also difficult to design a scalable approach to cluster large graphs with millions of nodes. We propose the approach CGMA (Clustering Graphs with Multiple Annotations) to address these challenges. CGMA is able to combine the crowd’s consensus opinions in an unbiased way, and conducts an effective clustering with low time complexity. We show the effectiveness and efficiency of the proposed approach on real-world graphs, by comparing with existing attributed graph clustering approaches.* Regards, Liangzhe

1 0

DM-Meeting this week
by Liangzhe Chen 18 Apr '16

18 Apr '16

Please join us for our next DM-Meeting. ===DM-Meeting Spring 2016=== WHO: Bijaya Adhikari WHEN: Wednesday, April 20, 2016 @ 12:00 noon WHERE: Torg 3160 A WHAT: Bijaya will talk about the following two papers: 1) Nonlinear Laplacian for Digraphs and its Applications to Network Analysis <https://pdfs.semanticscholar.org/fb25/2ef22fef819363a621dcb45232086fe5a07c.…> WSDM'16 2) Rare Category Detection on Time-Evolving Graphs <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7373448&tag=1> ICDM'15 MORE INFO: Here are the brief abstracts of the two papers: 1) Nonlinear Laplacian for Digraphs and its Applications to Network Analysis <https://pdfs.semanticscholar.org/fb25/2ef22fef819363a621dcb45232086fe5a07c.…> In this work, we introduce a new Markov operator associ- ated with a digraph, which we refer to as a nonlinear Lapla- cian. Unlike previous Laplacians for digraphs, the nonlinear Laplacian does not rely on the stationary distribution of the random walk process and is well defined on digraphs that are not strongly connected. We show that the nonlinear Laplacian has nontrivial eigenvalues and give a Cheeger-like inequality, which relates the conductance of a digraph and the smallest non-zero eigenvalue of its nonlinear Laplacian. Finally, we apply the nonlinear Laplacian to the analysis of real-world networks and obtain encouraging results. 2) Rare Category Detection on Time-Evolving Graphs <http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7373448&tag=1> Rare category detection(RCD) is an important topic in data mining, focusing on identifying the initial examples from rare classes in imbalanced data sets. This problem becomes more challenging when the data is presented as time-evolving graphs, as used in synthetic ID detection and insider threat detection. Most existing techniques for RCD are designed for static data sets, thus not suitable for time-evolving RCD applications. To address this challenge, in this paper, we first propose two incremental RCD algorithms, SIRD and BIRD. They are built upon existing density-based techniques for RCD, and incrementally update the detection models, which provide ‘time- flexible’ RCD. Furthermore, based on BIRD, we propose a modified version named BIRD-LI to deal with the cases where the exact priors of the minority classes are not available. We also identify a critical task in RCD named query distribution. It aims to allocate the limited budget into multiple time steps, such that the initial examples from the rare classes are detected as early as possible with the minimum labeling cost. The proposed incremental RCD algorithms and various query distribution strategies are evaluated empirically on both synthetic and real data. Regards, Liangzhe

1 0

Fwd: [Dac-faculty] colloquium by Director of the U.S. Census Bureau (fwd)
by B. Aditya Prakash 18 Apr '16

18 Apr '16

FYI---sounds interesting! -------- Forwarded Message -------- Subject: [Dac-faculty] colloquium by Director of the U.S. Census Bureau (fwd) Date: Mon, 18 Apr 2016 11:50:49 -0400 (EDT) From: Layne T. Watson via Dac-faculty <dac-faculty(a)cs.vt.edu> Reply-To: ltwatson(a)computer.org, Layne T. Watson <ltw(a)cs.vt.edu> To: dac-faculty(a)cs.vt.edu, dac-students(a)cs.vt.edu ---------- Forwarded message ---------- Date: Mon, 18 Apr 2016 09:51:02 -0400 From: Peter Haskell <phaskell(a)math.vt.edu> To: faculty(a)math.vt.edu, grads(a)math.vt.edu, undergrads(a)math.vt.edu Subject: colloquium by Director of the U.S. Census Bureau expected to be accessible and of general interest to students considering careers in the mathematical sciences ***Special Colloquium* *Time:*Tuesday, April 19, 2016 at 3:30 pm____ *Location:*300 Seitz Hall____ __ __ *Speaker:*John Thompson, Director of the United States Census Bureau____ __ __ *Title:*Innovation at the Census Bureau: How big data, new technologies, and advanced analytics are revolutionizing how we measure America____ __ __ Director John Thompson is a Virginia Tech Alumnus. You can find his bio at https://www.science.vt.edu/alumni/HOD/thompson-bio.html _______________________________________________ Dac-faculty mailing list Dac-faculty(a)cs.vt.edu

1 0

DM-Meeting
by Liangzhe Chen 11 Apr '16

11 Apr '16

Please join us for our next DM-Meeting. ===DM-Meeting Spring 2016=== WHO: Jose Cadena WHEN: Wednesday, April 13, 2016 @ 12:00 noon WHERE: Torg 3160 A WHAT: Jose will talk about the following paper: A Unified Framework for Evaluating Graph Scan Statistics with Connectivity Constraints, KDD'16 MORE INFO: Here is a brief abstract of the paper: Detecting “hotspots” and “anomalies” in network data often involves the maximization of certain score functions over all possible connected subgraphs. A number of score functions have been proposed for different scenarios. However, there is a lack of techniques that are flexible enough to optimize different score functions. In general, optimizing these functions is NP-hard because of the connectivity requirements. We describe a unified framework for designing algorithms for optimizing a large class of parametric and nonparametric scan statistics for network subject to connectivity constraints. Regards, Liangzhe

1 0

DM-Meeting this week
by Liangzhe Chen 05 Apr '16

05 Apr '16

Hi all, this week I'll give a presentation about the following two papers: Modeling Users' Adoption Behaviors with Social Selection and Influence <http://www.engr.uconn.edu/~fwang/papers/SDM2015LiuWangZheng.pdf>, by Liu et al. SDM'15 Fast Mining of a Network of Coevolving Time Series <http://ycai.ws.gc.cuny.edu/files/2015/03/NoT_sdm15.pdf>, by Cai et al. SDM'15 See you all in the meeting tomorrow! Regards, Liangzhe

1 0