Bayesian Robust Attributed Graph Clustering: Joint Learning of Partial Anomalies and Group Structure

By Aleksandar Bojchevski, Stephan Günnemann. 2018

77 citations recorded by the source corpus.

We study the problem of robust attributed graph clustering. In real data, the clustering structure is often obfuscated due to anomalies or corruptions. While robust methods have been recently introduced that handle anomalies as part of the clustering process, they all fail to account for one core aspect: Since attributed graphs consist of two views (network structure and attributes) anomalies might materialize only partially, i.e. instances might be corrupted in one view but perfectly fit in the other. In this case, we can still derive meaningful cluster assignments. Existing works only consider complete anomalies. In this paper, we present a novel probabilistic generative model (PAICAN) that explicitly models partial anomalies by generalizing ideas of Degree Corrected Stochastic Block Models and Bernoulli Mixture Models. We provide a highly scalable variational inference approach with runtime complexity linear in the number of edges. The robustness of our model w.r.t. anomalies is demonstrated by our experimental study, outperforming state-of-the-art competitors.

Subfields: Artificial Intelligence, Statistical and Nonlinear Physics

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

In Statistical and Nonlinear Physics

Citations in the corpus

Debiasing Community Detection: The Importance of Lowly Connected Nodes (2019, neutral): “In addition to CESNA, other methods have been proposed, such as Block-LDA [9], PAICAN [10], shared latent space models such as CLSM [7], and embedding-based approaches like LANE [11], which utilize node attributes in order to detect communities, or ELAINE [12], which utilizes”
Adversarial Attacks on Neural Networks for Graph Data (2018, background): “present in attributed graphs [4], adversarial examples are created deliberately to mislead machine learning models and often are designed to be unnoticeable.”
NetGAN: Generating Graphs via Random Walks (2018, methodology): “For the large CORA dataset and its commonly used subset of machine learning papers denoted with CORA-ML we use the same preprocessing as in Bojchevski & Günnemann (2018).”
A Comprehensive Survey on Graph Anomaly Detection With Deep Learning (2021, background): “When detecting anomalous nodes in static graphs, the differences between anomalies and regular nodes are mainly drawn from the graph structural information and nodes/edges’ attributes [41], [72], [73], [74].”
Adaptive Graph Encoder for Attributed Graph Embedding (2020, background): “[2, 5] model features as latent variables in Bayesian networks.”
Adversarial Attacks on Graph Neural Networks via Meta Learning (2019, background): “…classical approaches to node classiﬁcation (London & Getoor, 2014; Chapelle et al., 2006), recently deep learning on graphs has gained much attention (Monti et al., 2017; Bojchevski & G¨unnemann, 2018a; Battaglia et al., 2018; Perozzi et al., 2014; Bojchevski et al., 2018; Klicpera et al., 2019).”