A boosted outlier detection method based on the spectrum of the Laplacian matrix of a graph

• URL: http://arxiv.org/abs/2008.03039v2
• Date: Mon, 10 Aug 2020 10:47:16 GMT
• Title: A boosted outlier detection method based on the spectrum of the Laplacian matrix of a graph
• Authors: Nicolas Cofre
• Abstract summary: This paper explores a new outlier detection algorithm based on the spectrum of the Laplacian matrix of a graph. The sparcity of the Laplacian matrix significantly decreases the computational burden.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper explores a new outlier detection algorithm based on the spectrum of the Laplacian matrix of a graph. Taking advantage of boosting together with sparse-data based learners. The sparcity of the Laplacian matrix significantly decreases the computational burden, enabling a spectrum based outlier detection method to be applied to larger datasets compared to spectral clustering. The method is competitive on synthetic datasets with commonly used outlier detection algorithms like Isolation Forest and Local Outlier Factor.

Related papers

• Integral Operator Approaches for Scattered Data Fitting on Spheres [16.389581549801253]
  We study the approximation performance of a class of weighted spectral filter algorithms. We derive optimal Sobolev-type error estimates of weighted spectral filter algorithms.
  arXiv  Detail & Related papers  (2024-01-27T04:42:50Z)
• Spectral Entry-wise Matrix Estimation for Low-Rank Reinforcement Learning [53.445068584013896]
  We study matrix estimation problems arising in reinforcement learning (RL) with low-rank structure. In low-rank bandits, the matrix to be recovered specifies the expected arm rewards, and for low-rank Markov Decision Processes (MDPs), it may for example characterize the transition kernel of the MDP. We show that simple spectral-based matrix estimation approaches efficiently recover the singular subspaces of the matrix and exhibit nearly-minimal entry-wise error.
  arXiv  Detail & Related papers  (2023-10-10T17:06:41Z)
• Clustering Three-Way Data with Outliers [1.0435741631709405]
  An approach for clustering matrix-variate normal data with outliers is discussed. The approach, which uses the distribution of subset log-likelihoods, extends the OCLUST algorithm and uses an iterative approach to detect and trim outliers.
  arXiv  Detail & Related papers  (2023-10-08T21:27:29Z)
• An Efficient Algorithm for Clustered Multi-Task Compressive Sensing [60.70532293880842]
  Clustered multi-task compressive sensing is a hierarchical model that solves multiple compressive sensing tasks. The existing inference algorithm for this model is computationally expensive and does not scale well in high dimensions. We propose a new algorithm that substantially accelerates model inference by avoiding the need to explicitly compute these covariance matrices.
  arXiv  Detail & Related papers  (2023-09-30T15:57:14Z)
• Rethinking k-means from manifold learning perspective [122.38667613245151]
  We present a new clustering algorithm which directly detects clusters of data without mean estimation. Specifically, we construct distance matrix between data points by Butterworth filter. To well exploit the complementary information embedded in different views, we leverage the tensor Schatten p-norm regularization.
  arXiv  Detail & Related papers  (2023-05-12T03:01:41Z)
• Optimal Algorithms for the Inhomogeneous Spiked Wigner Model [89.1371983413931]
  We derive an approximate message-passing algorithm (AMP) for the inhomogeneous problem. We identify in particular the existence of a statistical-to-computational gap where known algorithms require a signal-to-noise ratio bigger than the information-theoretic threshold to perform better than random.
  arXiv  Detail & Related papers  (2023-02-13T19:57:17Z)
• Score matching enables causal discovery of nonlinear additive noise models [63.93669924730725]
  We show how to design a new generation of scalable causal discovery methods. We propose a new efficient method for approximating the score's Jacobian, enabling to recover the causal graph.
  arXiv  Detail & Related papers  (2022-03-08T21:34:46Z)
• Spectral clustering on spherical coordinates under the degree-corrected stochastic blockmodel [5.156484100374058]
  A novel spectral clustering algorithm is proposed for community detection under the degree-corrected blockmodel. Results show improved performance over competing methods in representing computer networks.
  arXiv  Detail & Related papers  (2020-11-09T16:55:38Z)
• Scalable Spectral Clustering with Nystrom Approximation: Practical and Theoretical Aspects [1.6752182911522515]
  This work presents a principled spectral clustering algorithm that exploits spectral properties of the similarity matrix associated with sampled points to regulate accuracy-efficiency trade-offs. The overarching goal of this work is to provide an improved baseline for future research directions to accelerate spectral clustering.
  arXiv  Detail & Related papers  (2020-06-25T15:10:56Z)
• A unified framework for spectral clustering in sparse graphs [47.82639003096941]
  We show that a conveniently parametrized form of regularized Laplacian matrix can be used to perform spectral clustering in sparse networks. We also exhibit important connections between this proposed matrix and the now popular non-backtracking matrix, the Bethe-Hessian matrix.
  arXiv  Detail & Related papers  (2020-03-20T10:58:37Z)

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.