oddball: Spotting Anomalies in Weighted Graphs

By Leman Akoglu, Mary McGlohon, Christos Faloutsos. Pacific-Asia Conference on Knowledge Discovery and Data Mining, 2010

600 citations recorded by the source corpus.

Given a large, weighted graph, how can we find anomalies? Which rules should be violated, before we label a node as an anomaly? We propose the oddball algorithm, to find such nodes The contributions are the following: (a) we discover several new rules (power laws) in density, weights, ranks and eigenvalues that seem to govern the so-called “neighborhood sub-graphs” and we show how to use these rules for anomaly detection; (b) we carefully choose features, and design oddball, so that it is scalable and it can work un-supervised (no user-defined constants) and (c) we report experiments on many real graphs with up to 1.6 million nodes, where oddball indeed spots unusual nodes that agree with intuition.

Subfields: Artificial Intelligence, Computer Networks and Communications, Statistical and Nonlinear Physics

View Paper: https://www.semanticscholar.org/paper/a8dc47e370b17371e57ad070e669360794473efe

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Bryan Perozzi
2. Charu C. Aggarwal
3. Huan Liu
4. Xia Hu
5. Jundong Li
6. Leman Akoglu
7. Danai Koutra
8. Hanghang Tong

In Computer Networks and Communications

1. Charu C. Aggarwal
2. Huan Liu
3. Hanghang Tong
4. Jundong Li
5. Bryan Perozzi
6. Danai Koutra
7. Leman Akoglu
8. Xia Hu

In Statistical and Nonlinear Physics

1. Bryan Perozzi
2. Huan Liu
3. Charu C. Aggarwal
4. Hanghang Tong
5. Danai Koutra
6. Leman Akoglu
7. Xia Hu
8. Jundong Li

Citations in the corpus

• RolX: structural role extraction & mining in large graphs (2012, background): “In [2], the authors propose to detect abnormal nodes from weighted graphs based on features and patterns from egonets.”
• Anomaly detection in online social networks (2014, methodology): “This idea has been applied to numerous properties of the ego-net (Akoglu et al., 2010; Hassanzadeh et al., 2012), and in a comparison of various combinations of features, Hassanzadeh et al. (2012) showed that a power-law relationship between edge count, and the average betweenness centrality (see…”
• It's who you know: graph mining using recursive structural features (2011, methodology): “Another study extracts egonet features and patterns in order to detect anomalous nodes in weighted graphs[1].”
• Contextual Outlier Interpretation (2017, background): “lier detection also plays an essential role in detecting malevolence and contamination towards a secure and trustworthy cyberspace, including detecting spammers in social media [3, 53] and fraudsters”
• Outlier Analysis (2013, methodology): “Even in the context of particular kinds of outliers such as node outliers [33], it has been shown that a wide variety of definitions are possible, depending upon how the features are defined within the locality of a node.”
• Anomaly detection in dynamic networks: a survey (2015, methodology): “These techniques complement methods for static graphs [59, 27, 26, 6], as the latter cannot be easily adopted for dynamic networks.”
• A Survey of Learning Causality with Data (2018, methodology): “ts. But more efficient methods are needed for massive data. An extreme case of heterogeneous groups are anomalies. Although anomaly detection has been well studied in machine learning and data mining [1, 2, 24], detection of instances that are irregular in causal effects and relationships is still a”
• NetWalk: A Flexible Deep Embedding Approach for Anomaly Detection in Dynamic Networks (2018, methodology): “We have presented NetWalk to detect anomalies in dynamic networks, by learning faithful network representations which can be updated dynamically as the network evolves over time.”
• Local Modeling of Attributed Graphs: Algorithms and Applications (2016, methodology): “Works that aim to spot structural outliers in plain graphs include [2, 138].”
• A Survey of Learning Causality with Data: Problems and Methods (2018, background): “Although anomaly detection has been well studied in machine learning and data mining [1, 2, 24], detection of instances that are irregular in causal effects and relationships is still an open problem.”
• SybilSCAR: Sybil detection in online social networks via local rule based propagation (2017, neutral): “, ego-network) [19], [20], [21] and side information (e.”
• Graph based anomaly detection and description: a survey (2014, methodology): “[Akoglu et al., 2010] introduce egonet features such as its number of triangles, total weight, principal eigenvalue, etc. as well as their pairwise correlation patterns.”
• False Information on Web and Social Media: A Survey (2018, neutral): “Graph-based algorithms are developed to identify dense-blocks or dense subgraphs of users and information in the network [6, 16, 40, 48, 79, 106].”
• Learning Graph Representations with Recurrent Neural Network Autoencoders (2018, background): “In social network analysis, we may need to compare egonetworks to detect anomalies [1] or to identify corresponding egonetworks across multiple social networks.”
• A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, methodology): “For instance, OddBall [38] employs the statistical features (e.g., the number of 1-hop neighbors and edges, the total weight of edges) extracted from each node and its 1-hop neighbors to detect particular structural anomalies that: 1) form local structures in shape of near-cliques or stars; 2) have…”