[Talk Summary] Anomaly Detection in Large Graphs

Professor Christos Faloutsos from Carnegie Mellon University held a talk on "Anomaly Detection in Large Graphs" on February, 24, 2017 at University of Pittsburgh. Given a large graph such as who-follows-whom, who-calls-whom, or who-likes-whom, observing some patterns in the graph can we tell what is normal behaviors and what is abnormal behaviors, which probably are resulted from fraudulent activities? And how graph evolves over time? Prof. Faloutsos presented two parts: (1) how to mine patterns and how to detect fraud in a static graph, and (2) patterns and anomalies in large time-evolving graphs.

 In the first part, Prof. Faloutsos claimed that real graphs are not random, for example, in- and out- degree distributions. He gave a list of laws and patterns of graphs, including:

  1. The power law in the degree distribution (connected component sizes): we can find patterns about the degree of graph.
  2. Singular values and eigen values: also used to find patterns about degree distribution.
  3. Triangle "Laws": real social networks have a lot of triangles and they follow the rule. Based on the rule of number of triangles corresponding to a user's friend list, we can find the fraud.
  4. K-core patterns: k-core of a graph, the degeneracy of a graph, and the coreness of a vertex.

How can we do anomaly detection or find "suspicious" groups? He presented CopyCatch (graph patterns and lockstep behaviors) which is used on Facebook to find abnormal blocks, spectral methods (spectral subspace plot to measure suspiciousness), and belief propagation demonstrated with E-bay fraud detection.

 For the second part of the talk, he discussed about anomaly detection in time-evolving graphs. The graphs growing over time can be model as tensors, for example, author-keyword-date tensors. To detect anomaly in tensors, he presented tensor factorization which is based on matrix factorization (SVD) to find abnormal blocks, and gave an example about anomaly communities in phone call data.

 In the end of the talk, he summarized that for big data, patterns and anomaly go hand in hand; the large data set can help us discover patterns/outliers that are invisible; and tensor is a powerful tool that can help us to analyze the time-evolving data.

 02/24/2017
3 floor, School of Information Sciences
University of Pittsburgh

Comments

Post a Comment

Popular posts from this blog

Personalized Access to Scientific Publications: from Recommendation to Explanation

Dario De Nart, Felice Ferrara, and Carlo Tasso ( UMAP-2013 ) http://link.springer.com/chapter/10.1007/978-3-642-38844-6_26 In the paper “Personalized Access to Scientific Publications: from Recommendation to Explanation”, Dario De Nart et al. present a Recommender and Explanation System (RES) that is able to recommend scientific publication and show explanation to users.  In order to do recommendation, Dario De Nart et al., firstly, use the The Dikpe Keyphrase extraction algorithm introduced by Pudota (2010) to extract keyphrases from papers. Each keyphrase has a weight called keyphraseness that reveals the several lexical and statistical indicators exploited in the extraction process. Higher is the keyphraseness, more relevant is the KP. For each paper in the collection, they represent it as a conceptual graph. Each node in the graph is a term broken down from a KP. Two nodes are connected when they appear in the same KP. For instance, the KP “document retrieval” is split into tw
Read more

[Talk Summary 2] Dynamic Information Retrieval Model

Image
In this seminar, prof essor Grace Hui Yang presents a dynamic information retrieval model which helps users explore the information space in order to find out which documents are relevant and which aren't, satisfying their information need. The dynamic IR task aims to find relevant documents for a session of multiple queries. It happens when information needs are complex, vague, evolving, often containing multiple subtopics. A dynamic system is one which changes or adapts over time, based on a sequence of events. While static IR does not learn directly from users and the parameters are updated periodically, dynamic IR is developed from interactive IR which exploits users' feedback to give recommendation or improve the search result or optimize ranking, which is called dynamic ranking principle. But interactive IR just treat interaction independently and response to immediate feedback. Dynamic IR tries to optimize over all interaction, uses it for long term gain and models
Read more

FolkTrails: Interpreting Navigation Behavior in a Social Tagging System

Thomas Niebler, Martin Becker, Daniel Zoller, Stephan Doerfel, & Andreas Hotho ( CIKM-2016 ) http://dl.acm.org/citation.cfm?doid=2983323.2983686 In the paper “FolkTrails: Interpreting Navigation Behavior in a Social Tagging System”, Niebler et al. present an investigate navigation trails in the popular scholarly social tagging system BibSonomy. They tried to understand users’ dynamic browsing behaviors on this kind of systems, how individual users behave differently on navigation, and whether the semantic nature of the underlying folksonomy can help to explain navigation. Firstly, Niebler et al. study different hypotheses about the navigational user behavior in Bibsonomy, a social bookmarking system. They test these hypotheses by using HypTrails, an approach utilizing first-order Markov chain models and Bayesian inference for expressing and comparing hypotheses about human trails. These hypotheses include: Uniform hypothesis: serves as a baseline, users randomly pick a l
Read more