# Cycle-tree guided attack of random K-core: Spin glass model and efficient message-passing algorithm

arXiv: https://arxiv.org/abs/2110.05940 · HTML: https://mlsanity.com/paper/2110.05940/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Oct 2021.

## Built on by (most cited first, 1 of 1)

- [Network Dynamics-Based Framework for Understanding Deep Neural Networks](https://mlsanity.com/paper/2501.02436/) (2025)

## Abstract (arXiv)

The K-core of a graph is the maximal subgraph within which each vertex is connected to at least K other vertices. It is a fundamental network concept for understanding threshold cascading processes with a discontinuous percolation transition. A minimum attack set contains the smallest number of vertices whose removal induces complete collapse of the K-core. Here we tackle this prototypical optimal initial-condition problem from the spin-glass perspective of cycle-tree maximum packing and propose a cycle-tree guided attack (CTGA) message-passing algorithm. The good performance and time efficiency of CTGA are verified on the regular random and Erd"os-R'enyi random graph ensembles. Our central idea of transforming a long-range correlated dynamical process to static structural patterns may also be instructive to other hard optimization and control problems.