Active Learning on Adversarially Corrupted Graphs

• URL: http://arxiv.org/abs/2607.04869v1
• Date: Mon, 06 Jul 2026 09:42:52 GMT
• Title: Active Learning on Adversarially Corrupted Graphs
• Abstract summary: An adversary seeks to hide a set of emphcorrupted vertices inside a graph $G*$.<n>The power of the adversary is measured by the size of the emphneighborhood of the corrupted vertices in $G*$.<n>We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends on both the power of the adversary and the emph expansion of $G*$.
• Score: 34.01867185404678
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Motivated by real-world scenarios where malicious entities tamper with existing networks, we define a model where an adversary seeks to hide a set of \emph{corrupted vertices} inside a graph $G^*$. To this end, the adversary can add edges between the corrupted vertices, as well as edges between the corrupted vertices and $G^*$, and its power is then measured by the size of the \emph{neighborhood} of the corrupted vertices in $G^*$. Our goal is to design an active learning algorithm that efficiently finds the subset of corrupted vertices using a small number of label queries. We devise an efficient algorithm that approximately recovers the corrupted vertices with a query complexity that depends polynomially on both the power of the adversary and the \emph{vertex expansion} of $G^*$, a fundamental measure of graph connectivity. At the heart of this result is a polynomial-time algorithm, obtained by carefully adapting sum-of-squares algorithms for approximating minimum expansion, that finds a set with small vertex expansion subject to cardinality constraints. To the best of our knowledge, this is the first time that the vertex expansion is shown to play a key role in determining the query complexity of active learning algorithms robust to structural adversarial attacks.

Related papers

• Learning-Augmented Hierarchical Clustering [29.438861266606573]
  We consider the problem of hierarchical clustering given auxiliary information from natural oracles.<n>We show that a splitting oracle enables algorithms to outperform standard HC approaches.<n>Our approaches extend to sublinear settings, in which we show new streaming and PRAM algorithms with improved guarantees.
  arXiv  Detail & Related papers  (2025-06-05T18:22:40Z)
• Linear Transformer Topological Masking with Graph Random Features [52.717865653036796]
  We show how to parameterise topological masks as a learnable function of a weighted adjacency matrix. Our efficient masking algorithms provide strong performance gains for tasks on image and point cloud data.
  arXiv  Detail & Related papers  (2024-10-04T14:24:06Z)
• A Faster Branching Algorithm for the Maximum $k$-Defective Clique Problem [18.720357905876604]
  A $k$-defective clique of an un branching graph $G$ induces a nearly complete graph with a maximum of $k$ missing edges. The maximum $k$-defective clique problem, which asks for the largest $k$-defective clique from the given graph, is important in many applications, such as social and biological network analysis.
  arXiv  Detail & Related papers  (2024-07-23T15:40:35Z)
• BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs [0.3277163122167434]
  This article introduces a new algorithm designed for the exhaustive enumeration of maximal bicliques within a bipartite graph. The algorithm, called BBK for Bipartite Bron-Kerbosch, is a new extension to the bipartite case of the Bron-Kerbosch algorithm. It is faster than the state-of-the-art algorithms and allows the enumeration on massive bipartite graphs that are not manageable with existing implementations.
  arXiv  Detail & Related papers  (2024-05-07T15:49:34Z)
• Learning-Based Heuristic for Combinatorial Optimization of the Minimum Dominating Set Problem using Graph Convolutional Networks [1.5469452301122175]
  A dominating set of a graph $mathcalG=(V, E) is a subset of vertices $SsubseteqmathcalV setminus S$ outside the dominating set. We propose a novel learning-based approach to compute solutions for the minimum dominating set problem using graph$ convolutional networks.
  arXiv  Detail & Related papers  (2023-06-06T06:22:42Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations [80.95090605985042]
  A learning agent repeatedly chooses from a set of $K$ actions after being presented with a $d$-dimensional context vector. The agent incurs and observes the loss of the chosen action, but also observes the losses of its neighboring actions in the observation structures. Two efficient algorithms are developed based on textttEXP3.
  arXiv  Detail & Related papers  (2020-12-10T15:40:07Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37:33Z)
• GeoDA: a geometric framework for black-box adversarial attacks [79.52980486689287]
  We propose a framework to generate adversarial examples in one of the most challenging black-box settings. Our framework is based on the observation that the decision boundary of deep networks usually has a small mean curvature in the vicinity of data samples.
  arXiv  Detail & Related papers  (2020-03-13T20:03:01Z)

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.