Dismantling complex networks based on higher-order graph neural network

Why breaking networks can protect us

From stopping epidemics and online rumors to disrupting criminal or fragile financial networks, many urgent problems boil down to a simple idea: how do we break a complex web of connections as efficiently as possible? This paper introduces a smarter way to find the few hidden points in a network whose removal most effectively causes the whole structure to fall apart, using tools that look not just at direct links but at richer group interactions.

From real life to webs of links

Modern science often represents systems as networks, where nodes might be people, proteins, or cities and links show who interacts with whom. The strength of such systems depends on how well the network stays connected when some nodes fail or are removed. Finding the smallest set of nodes that shatters the network into many small pieces is called network dismantling. It underlies tasks like immunizing a population, stopping malware in the internet, or weakening organized crime groups. Past approaches mostly looked at simple pairwise connections, such as how many neighbors a node has or how many shortest paths run through it, and then removed the highest scoring nodes.

Why simple links miss hidden influencers

Real systems rarely work through pairs alone. Scientific teams, group chats, protein complexes, and ecological communities involve three or more participants acting together. These higher order interactions cannot be reduced to a simple sum of pair ties. Two nodes may seem unremarkable when judged only by direct links yet be crucial in many overlapping groups. Traditional methods often ignore the way nodes share roles across the whole network or how they behave inside these small group patterns. As a result, they can leave behind clusters that continue to function almost normally, even after many high degree nodes have been removed.

Seeing roles from far away and up close

The authors propose a framework called SPR, short for Structural and Processual Role aware Network Dismantling, built on a more general Higher order Graph Neural Network (HoGNN). First, they translate a real system into a network and compute a set of basic features for each node, capturing both local traits such as number of neighbors and global traits such as closeness to others. From a wide angle, SPR learns each node’s structural role in the overall architecture: for example, hubs, bridges between communities, or boundary nodes. Nodes that play similar roles, even if far apart, are grouped into higher order connections called hyperedges. From a close up angle, SPR tracks how a node participates inside many overlapping small groups of different sizes, revealing its processual role, that is, how its influence shifts across triangles and larger groupings.

Letting the network learn what matters

HoGNN then passes information along these higher order structures, using attention mechanisms to let the model focus more on the roles and groups that matter most for breaking the network. It combines information from macro structural roles and micro processual roles into a single dismantling score for each node, interpreted as the probability that this node belongs to the target attack set. During training, the method is guided by a loss function that balances two goals: shrinking the largest connected piece of the network while removing as few nodes as possible. Once trained, SPR simply ranks nodes by score and removes them one by one until the largest remaining piece falls below a chosen size.

How well does the method work in practice

The researchers test SPR on nine real world networks drawn from social, biological, and communication settings, as well as on several synthetic network models. Compared with twenty leading methods, including classic centrality scores and advanced machine learning techniques, SPR usually needs fewer node removals to collapse the network. It is particularly strong in networks rich in tightly knit groups and overlapping higher order structures, where traditional, degree based methods can be misled by dense cliques. SPR also performs well on synthetic networks with different connection patterns and stays effective as networks grow larger or denser, though denser systems naturally demand more removals.

What this means for controlling complex systems

In everyday terms, this work shows that looking only at who is connected to whom is not enough to find the true pressure points in a complex web. By also considering who acts together in groups, and how nodes share similar roles across the system, SPR can uncover subtle yet critical players whose removal best fragments the network. While the study focuses on dismantling, the same ideas could help in tasks like choosing which people to vaccinate to slow disease, which accounts to monitor to prevent financial contagion, or which elements to support to keep vital systems stable.

Citation: Zhou, W., Tan, S., Fang, Y. et al. Dismantling complex networks based on higher-order graph neural network. Commun Phys 9, 181 (2026). https://doi.org/10.1038/s42005-026-02601-y

Keywords: network dismantling, complex networks, graph neural networks, higher order interactions, network robustness