Community-based anomaly detection using spectral graph filtering

• URL: http://arxiv.org/abs/2201.09936v1
• Date: Mon, 24 Jan 2022 20:02:22 GMT
• Title: Community-based anomaly detection using spectral graph filtering
• Authors: Rodrigo Francisquini, Ana Carolina Lorena, Mari\'a C. V. Nascimento
• Abstract summary: This paper proposes a community-based anomaly detection algorithm using a spectral graph-based filter. In computational experiments, the proposed strategy, called SpecF, showed an outstanding performance in successfully identifying even discrete anomalies. We present a case study to validate the proposed method to study the dissemination of COVID-19 in the different districts of Sao Jos'e dos Campos, Brazil.
• Score: 2.320417845168326
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Several applications have a community structure where the nodes of the same community share similar attributes. Anomaly or outlier detection in networks is a relevant and widely studied research topic with applications in various domains. Despite a significant amount of anomaly detection frameworks, there is a dearth on the literature of methods that consider both attributed graphs and the community structure of the networks. This paper proposes a community-based anomaly detection algorithm using a spectral graph-based filter that includes the network community structure into the Laplacian matrix adopted as the basis for the Fourier transform. In addition, the choice of the cutoff frequency of the filter considers the number of communities found. In computational experiments, the proposed strategy, called SpecF, showed an outstanding performance in successfully identifying even discrete anomalies. SpecF is better than a baseline disregarding the community structure, especially for networks with a higher community overlapping. Additionally, we present a case study to validate the proposed method to study the dissemination of COVID-19 in the different districts of S\~ao Jos\'e dos Campos, Brazil.

Related papers

• Community detection by spectral methods in multi-layer networks [0.0]
  Community detection in multi-layer networks is a crucial problem in network analysis. One algorithm is based on the sum of adjacency matrices, while the other utilizes the debiased sum of squared adjacency matrices. Numerical simulations confirm that our algorithm, employing the debiased sum of squared adjacency matrices, surpasses existing methods for community detection in multi-layer networks.
  arXiv  Detail & Related papers  (2024-03-19T08:29:47Z)
• Alleviating Structural Distribution Shift in Graph Anomaly Detection [70.1022676681496]
  Graph anomaly detection (GAD) is a challenging binary classification problem. Gallon neural networks (GNNs) benefit the classification of normals from aggregating homophilous neighbors. We propose a framework to mitigate the effect of heterophilous neighbors and make them invariant.
  arXiv  Detail & Related papers  (2024-01-25T13:07:34Z)
• HoloNets: Spectral Convolutions do extend to Directed Graphs [59.851175771106625]
  Conventional wisdom dictates that spectral convolutional networks may only be deployed on undirected graphs. Here we show this traditional reliance on the graph Fourier transform to be superfluous. We provide a frequency-response interpretation of newly developed filters, investigate the influence of the basis used to express filters and discuss the interplay with characteristic operators on which networks are based.
  arXiv  Detail & Related papers  (2023-10-03T17:42:09Z)
• ARISE: Graph Anomaly Detection on Attributed Networks via Substructure Awareness [70.60721571429784]
  We propose a new graph anomaly detection framework on attributed networks via substructure awareness (ARISE) ARISE focuses on the substructures in the graph to discern abnormalities. Experiments show that ARISE greatly improves detection performance compared to state-of-the-art attributed networks anomaly detection (ANAD) algorithms.
  arXiv  Detail & Related papers  (2022-11-28T12:17:40Z)
• MGTCOM: Community Detection in Multimodal Graphs [0.34376560669160383]
  MGTCOM is an end-to-end framework optimizing network embeddings, communities and the number of communities in tandem. Our method is competitive against state-of-the-art and performs well in inductive inference.
  arXiv  Detail & Related papers  (2022-11-10T16:11:03Z)
• Co-Membership-based Generic Anomalous Communities Detection [0.0]
  We introduce the Co-Membership-based Generic Anomalous Communities Detection Algorithm (referred as to CMMAC) CMMAC is domain-free and almost unaffected by communities' sizes and densities. We present an algorithm for generating a community-structured random network enabling the infusion of anomalous communities.
  arXiv  Detail & Related papers  (2022-03-30T12:23:55Z)
• Community detection in censored hypergraph [8.790193989856403]
  We study community detection in censored $m$-uniform hypergraph from information-theoretic point of view. We propose a spectral-time algorithm to exactly recover the community structure up to the threshold. It is also interesting to study whether a single spectral algorithm without refinement the threshold.
  arXiv  Detail & Related papers  (2021-11-04T22:03:20Z)
• A Comprehensive Survey on Community Detection with Deep Learning [93.40332347374712]
  A community reveals the features and connections of its members that are different from those in other communities in a network. This survey devises and proposes a new taxonomy covering different categories of the state-of-the-art methods. The main category, i.e., deep neural networks, is further divided into convolutional networks, graph attention networks, generative adversarial networks and autoencoders.
  arXiv  Detail & Related papers  (2021-05-26T14:37:07Z)
• On the use of local structural properties for improving the efficiency of hierarchical community detection methods [77.34726150561087]
  We study how local structural network properties can be used as proxies to improve the efficiency of hierarchical community detection. We also check the performance impact of network prunings as an ancillary tactic to make hierarchical community detection more efficient.
  arXiv  Detail & Related papers  (2020-09-15T00:16:12Z)
• Network Anomaly Detection based on Tensor Decomposition [10.285394886473217]
  Many anomaly detection methods are based on packet inspection collected at the network core routers. We propose an alternative method in which packet header inspection is not needed.
  arXiv  Detail & Related papers  (2020-04-20T21:45:05Z)
• Detecting Communities in Heterogeneous Multi-Relational Networks:A Message Passing based Approach [89.19237792558687]
  Community is a common characteristic of networks including social networks, biological networks, computer and information networks. We propose an efficient message passing based algorithm to simultaneously detect communities for all homogeneous networks.
  arXiv  Detail & Related papers  (2020-04-06T17:36:24Z)

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.