From viruses to social bots, researchers unearth the structure of attacked networks

Essential functions of the cell are carried out by protein molecules, which interact with each other in varying complexity. When a virus enters the body, it disrupts their interactions and manipulates them for its own replication. This is the foundation of genetic diseases, and it is of great interest to understand how viruses operate.

Adversaries like viruses inspired Paul Bogdan, associate professor in the Ming Hsieh Department of Electrical and Computer Engineering, and recent Ph.D. graduate, Yuankun Xue, from USC's Cyber Physical Systems Group, to determine how exactly they interact with proteins in the human body. "We tried to reproduce this problem using a mathematical model," said Bogdan. Their groundbreaking statistical machine learning research on "Reconstructing missing complex networks against adversarial interventions," was published in Nature Communications journal earlier this April.

Xue, who earned his Ph.D. in electrical and computer engineering last year with the 2018 Best Dissertation Award, said: "Understanding the invisible networks of critical proteins and genes is challenging, and extremely important to design new medicines or gene therapies against viruses and even diseases like cancer."

The 'protein interaction network' models each protein as a 'node.' If two proteins interact, there is an 'edge' connecting them. Xue explained, "An attack by a virus is analogous to removing certain nodes and links in this network." Consequently, the original network is no longer observable.

"Some networks are highly dynamic. The speed at which they change may be extremely fast or slow," Bogdan said. "We may not have sensors to get accurate measurements. Part of the network cannot be observed and hence becomes invisible."

To trace the effect of a viral attack, Bogdan and Xue needed to reconstruct the original network by finding a reliable estimate of the invisible part, which was no easy task. Said Bogdan: "The challenge is that you don't see the links, you don't see the nodes, and you don't know the behavior of the virus." To solve this problem, Xue added, "The trick is to rely on a statistical machine learning framework to trace all possibilities and find the most probable estimate."

In sharp contrast to prior research, the lab's novel contribution is that they actively incorporate the influence and causality of the attack, or 'adversarial intervention', into their learning algorithm rather than treat it as a random sampling process. Bogdan explained, "Its real power lies in its generality -- it can work with any type of attack and network model."

Due to the generality of their proposed framework, their research has far-reaching applications to any network reconstruction problem involving adversarial attack, in diverse fields such as ecology, social science, neuroscience, and network security. Their paper has also demonstrated its capability to determine the influence of trolls and bots on social media users.

Bogdan plans to extend their work by experimenting with a range of attack models, more complex and varied datasets, and larger network sizes to understand their effect on the reconstructed network.