Robust Detection of Planted Subgraphs in Semi-Random Models

• URL: http://arxiv.org/abs/2508.02158v1
• Date: Mon, 04 Aug 2025 07:59:42 GMT
• Title: Robust Detection of Planted Subgraphs in Semi-Random Models
• Authors: Dor Elimelech, Wasim Huleihel,
• Abstract summary: Detection of planted subgraphs in Erd"os-R'enyi random graphs has been extensively studied.<n>Most prior work assumes a purely random generative model, making the resulting algorithms potentially fragile in the face of real-world perturbations.<n>We study semi-random models for the planted subgraph detection problem, wherein an adversary is allowed to remove edges outside the planted subgraph before the graph is revealed to the statistician.<n>Our results establish the first robust framework for planted subgraph detection and open new directions in the study of semi-random models, computational-statistical trade-offs, and robustness in
• Score: 7.320365821066746
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Detection of planted subgraphs in Erd\"os-R\'enyi random graphs has been extensively studied, leading to a rich body of results characterizing both statistical and computational thresholds. However, most prior work assumes a purely random generative model, making the resulting algorithms potentially fragile in the face of real-world perturbations. In this work, we initiate the study of semi-random models for the planted subgraph detection problem, wherein an adversary is allowed to remove edges outside the planted subgraph before the graph is revealed to the statistician. Crucially, the statistician remains unaware of which edges have been removed, introducing fundamental challenges to the inference task. We establish fundamental statistical limits for detection under this semi-random model, revealing a sharp dichotomy. Specifically, for planted subgraphs with strongly sub-logarithmic maximum density detection becomes information-theoretically impossible in the presence of an adversary, despite being possible in the classical random model. In stark contrast, for subgraphs with super-logarithmic density, the statistical limits remain essentially unchanged; we prove that the optimal (albeit computationally intractable) likelihood ratio test remains robust. Beyond these statistical boundaries, we design a new computationally efficient and robust detection algorithm, and provide rigorous statistical guarantees for its performance. Our results establish the first robust framework for planted subgraph detection and open new directions in the study of semi-random models, computational-statistical trade-offs, and robustness in graph inference problems.

Related papers

• SubSearch: Robust Estimation and Outlier Detection for Stochastic Block Models via Subgraph Search [2.082364067210557]
  We propose an algorithm for robustly estimating SBM parameters by exploring the space of subgraphs in search of one that closely aligns with the model's assumptions.<n>Our approach also functions as an outlier detection method, properly identifying nodes responsible for the graph's deviation from the model and going beyond simple techniques like pruning high-degree nodes.
  arXiv  Detail & Related papers  (2025-06-04T07:47:25Z)
• Asymptotically Optimal Linear Best Feasible Arm Identification with Fixed Budget [55.938644481736446]
  We introduce a novel algorithm for best feasible arm identification that guarantees an exponential decay in the error probability.<n>We validate our algorithm through comprehensive empirical evaluations across various problem instances with different levels of complexity.
  arXiv  Detail & Related papers  (2025-06-03T02:56:26Z)
• Learning to Bound Counterfactual Inference in Structural Causal Models from Observational and Randomised Data [64.96984404868411]
  We derive a likelihood characterisation for the overall data that leads us to extend a previous EM-based algorithm. The new algorithm learns to approximate the (unidentifiability) region of model parameters from such mixed data sources. It delivers interval approximations to counterfactual results, which collapse to points in the identifiable case.
  arXiv  Detail & Related papers  (2022-12-06T12:42:11Z)
• Calibrated Nonparametric Scan Statistics for Anomalous Pattern Detection in Graphs [4.756490355031122]
  Nonparametric scan statistics (NPSSs) identify connected subgraphs with a higher than expected proportion of significant nodes. NPSSs fail to account for the multiplicity of the recently calibrated statistic over the anomalous subgraphs. We develop a new statistical approach to recalibrate NPSSs, correctly adjusting for multiple hypothesis testing and taking the underlying graph structure into account.
  arXiv  Detail & Related papers  (2022-06-26T04:59:13Z)
• Minimax rate of consistency for linear models with missing values [0.0]
  Missing values arise in most real-world data sets due to the aggregation of multiple sources and intrinsically missing information (sensor failure, unanswered questions in surveys...). In this paper, we focus on the extensively-studied linear models, but in presence of missing values, which turns out to be quite a challenging task. This eventually requires to solve a number of learning tasks, exponential in the number of input features, which makes predictions impossible for current real-world datasets.
  arXiv  Detail & Related papers  (2022-02-03T08:45:34Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• Projected Sliced Wasserstein Autoencoder-based Hyperspectral Images Anomaly Detection [42.585075865267946]
  We propose the Projected Sliced Wasserstein (PSW) autoencoder-based anomaly detection method. In particular, the computation-friendly eigen-decomposition method is leveraged to find the principal component for slicing the high-dimensional data. Comprehensive experiments conducted on various real-world hyperspectral anomaly detection benchmarks demonstrate the superior performance of the proposed method.
  arXiv  Detail & Related papers  (2021-12-20T09:21:02Z)
• Distributionally Robust Semi-Supervised Learning Over Graphs [68.29280230284712]
  Semi-supervised learning (SSL) over graph-structured data emerges in many network science applications. To efficiently manage learning over graphs, variants of graph neural networks (GNNs) have been developed recently. Despite their success in practice, most of existing methods are unable to handle graphs with uncertain nodal attributes. Challenges also arise due to distributional uncertainties associated with data acquired by noisy measurements. A distributionally robust learning framework is developed, where the objective is to train models that exhibit quantifiable robustness against perturbations.
  arXiv  Detail & Related papers  (2021-10-20T14:23:54Z)
• Bayes DistNet -- A Robust Neural Network for Algorithm Runtime Distribution Predictions [1.8275108630751844]
  Randomized algorithms are used in many state-of-the-art solvers for constraint satisfaction problems (CSP) and Boolean satisfiability (SAT) problems. Previous state-of-the-art methods directly try to predict a fixed parametric distribution that the input instance follows. This new model achieves robust predictive performance in the low observation setting, as well as handling censored observations.
  arXiv  Detail & Related papers  (2020-12-14T01:15:39Z)
• Interpretable Anomaly Detection with Mondrian P{\'o}lya Forests on Data Streams [6.177270420667713]
  Anomaly detection at scale is an extremely challenging problem of great practicality. Recent work has coalesced on variations of (random) $k$emphd-trees to summarise data for anomaly detection. These methods rely on ad-hoc score functions that are not easy to interpret. We contextualise these methods in a probabilistic framework which we call the Mondrian Polya Forest.
  arXiv  Detail & Related papers  (2020-08-04T13:19:07Z)
• Improving Maximum Likelihood Training for Text Generation with Density Ratio Estimation [51.091890311312085]
  We propose a new training scheme for auto-regressive sequence generative models, which is effective and stable when operating at large sample space encountered in text generation. Our method stably outperforms Maximum Likelihood Estimation and other state-of-the-art sequence generative models in terms of both quality and diversity.
  arXiv  Detail & Related papers  (2020-07-12T15:31:24Z)
• Instability, Computational Efficiency and Statistical Accuracy [101.32305022521024]
  We develop a framework that yields statistical accuracy based on interplay between the deterministic convergence rate of the algorithm at the population level, and its degree of (instability) when applied to an empirical object based on $n$ samples. We provide applications of our general results to several concrete classes of models, including Gaussian mixture estimation, non-linear regression models, and informative non-response models.
  arXiv  Detail & Related papers  (2020-05-22T22:30:52Z)

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.