Issues with Propagation Based Models for Graph-Level Outlier Detection

• URL: http://arxiv.org/abs/2012.12931v2
• Date: Tue, 2 Mar 2021 18:34:03 GMT
• Title: Issues with Propagation Based Models for Graph-Level Outlier Detection
• Authors: Lingxiao Zhao, Leman Akoglu
• Abstract summary: Graph-Level Outlier Detection ( GLOD) is the task of identifying unusual graphs within a graph database. This paper identifies and delves into a fundamental and intriguing issue with applying propagation based models to GLOD. We find that ROC-AUC performance of the models change significantly depending on which class is down-sampled.
• Score: 16.980621769406916
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Graph-Level Outlier Detection (GLOD) is the task of identifying unusual graphs within a graph database, which received little attention compared to node-level detection in a single graph. As propagation based graph embedding by GNNs and graph kernels achieved promising results on another graph-level task, i.e. graph classification, we study applying those models to tackle GLOD. Instead of developing new models, this paper identifies and delves into a fundamental and intriguing issue with applying propagation based models to GLOD, with evaluation conducted on repurposed binary graph classification datasets where one class is down-sampled as outlier. We find that ROC-AUC performance of the models change significantly (flips from high to low) depending on which class is down-sampled. Interestingly, ROC-AUCs on these two variants approximately sum to 1 and their performance gap is amplified with increasing propagations. We carefully study the graph embedding space produced by propagation based models and find two driving factors: (1) disparity between within-class densities which is amplified by propagation, and (2) overlapping support (mixing of embeddings) across classes. Our study sheds light onto the effects of using graph propagation based models and classification datasets for outlier detection for the first time.

Related papers

• GSpect: Spectral Filtering for Cross-Scale Graph Classification [9.800723513820046]
  We propose GSpect, an advanced spectral graph filtering model for cross-scale graph classification tasks. On open data sets, GSpect improves the performance of classification accuracy by 1.62% on average, and for a maximum of 3.33% on PROTEINS. GSpect fills the gap in cross-scale graph classification studies and has potential to provide assistance in application research like diagnosis of brain disease.
  arXiv  Detail & Related papers  (2024-08-31T03:26:32Z)
• Generation is better than Modification: Combating High Class Homophily Variance in Graph Anomaly Detection [51.11833609431406]
  Homophily distribution differences between different classes are significantly greater than those in homophilic and heterophilic graphs. We introduce a new metric called Class Homophily Variance, which quantitatively describes this phenomenon. To mitigate its impact, we propose a novel GNN model named Homophily Edge Generation Graph Neural Network (HedGe)
  arXiv  Detail & Related papers  (2024-03-15T14:26:53Z)
• Mitigating Label Noise on Graph via Topological Sample Selection [72.86862597508077]
  We propose a $textitTopological Sample Selection$ (TSS) method that boosts the informative sample selection process in a graph by utilising topological information. We theoretically prove that our procedure minimizes an upper bound of the expected risk under target clean distribution, and experimentally show the superiority of our method compared with state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-03-04T11:24:51Z)
• Graph Out-of-Distribution Generalization with Controllable Data Augmentation [51.17476258673232]
  Graph Neural Network (GNN) has demonstrated extraordinary performance in classifying graph properties. Due to the selection bias of training and testing data, distribution deviation is widespread. We propose OOD calibration to measure the distribution deviation of virtual samples.
  arXiv  Detail & Related papers  (2023-08-16T13:10:27Z)
• Graph Anomaly Detection with Unsupervised GNNs [19.772490600670363]
  We design GLAM, an end-to-end graph-level anomaly detection model based on graph neural networks (GNNs) We also propose a new pooling strategy for graph-level embedding, called MMD-pooling, that is geared toward detecting distribution anomalies which has not been considered before.
  arXiv  Detail & Related papers  (2022-10-18T01:59:58Z)
• Heterogeneous Graph Neural Networks using Self-supervised Reciprocally Contrastive Learning [102.9138736545956]
  Heterogeneous graph neural network (HGNN) is a very popular technique for the modeling and analysis of heterogeneous graphs. We develop for the first time a novel and robust heterogeneous graph contrastive learning approach, namely HGCL, which introduces two views on respective guidance of node attributes and graph topologies. In this new approach, we adopt distinct but most suitable attribute and topology fusion mechanisms in the two views, which are conducive to mining relevant information in attributes and topologies separately.
  arXiv  Detail & Related papers  (2022-04-30T12:57:02Z)
• Deep Graph-level Anomaly Detection by Glocal Knowledge Distillation [61.39364567221311]
  Graph-level anomaly detection (GAD) describes the problem of detecting graphs that are abnormal in their structure and/or the features of their nodes. One of the challenges in GAD is to devise graph representations that enable the detection of both locally- and globally-anomalous graphs. We introduce a novel deep anomaly detection approach for GAD that learns rich global and local normal pattern information by joint random distillation of graph and node representations.
  arXiv  Detail & Related papers  (2021-12-19T05:04:53Z)
• GraphAnoGAN: Detecting Anomalous Snapshots from Attributed Graphs [36.00861758441135]
  We propose GraphAnoGAN, an anomalous snapshot ranking framework. It consists of two core components -- generative and discriminative models. Experiments on 4 real-world networks show that GraphAnoGAN outperforms 6 baselines with a significant margin.
  arXiv  Detail & Related papers  (2021-06-29T15:35:37Z)
• Line Graph Neural Networks for Link Prediction [71.00689542259052]
  We consider the graph link prediction task, which is a classic graph analytical problem with many real-world applications. In this formalism, a link prediction problem is converted to a graph classification task. We propose to seek a radically different and novel path by making use of the line graphs in graph theory. In particular, each node in a line graph corresponds to a unique edge in the original graph. Therefore, link prediction problems in the original graph can be equivalently solved as a node classification problem in its corresponding line graph, instead of a graph classification task.
  arXiv  Detail & Related papers  (2020-10-20T05:54:31Z)
• Certified Robustness of Graph Classification against Topology Attack with Randomized Smoothing [22.16111584447466]
  Graph-based machine learning models are vulnerable to adversarial perturbations due to the non i.i.d nature of graph data. We build a smoothed graph classification model with certified robustness guarantee. We also evaluate the effectiveness of our approach under graph convolutional network (GCN) based multi-class graph classification model.
  arXiv  Detail & Related papers  (2020-09-12T22:18:54Z)
• Few-Shot Learning on Graphs via Super-Classes based on Graph Spectral Measures [14.932318540666545]
  We study the problem of few shot graph classification in graph neural networks (GNNs) to recognize unseen classes, given limited labeled graph examples. We propose an approach where a probability measure is assigned to each graph based on the spectrum of the graphs normalized Laplacian.
  arXiv  Detail & Related papers  (2020-02-27T17:11:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.