Researchers in many fields use networks to represent interactions between entities in complex systems. To study the large-scale behavior of complex systems, it is useful to examine mesoscale structures in networks as building blocks that influence such behavior. In this paper, we present an approach to describe low-rank mesoscale structures in networks. We find that many real-world networks possess a small set of latent motifs that effectively approximate most subgraphs at a fixed mesoscale. Such low-rank mesoscale structures allow one to reconstruct networks by approximating subgraphs of a network using combinations of latent motifs. Employing subgraph sampling and nonnegative matrix factorization enables the discovery of these latent motifs. The ability to encode and reconstruct networks using a small set of latent motifs has many applications in network analysis, including network comparison, network denoising, and edge inference.
POTION : Optimizing Graph Structure for Targeted Diffusion
The problem of diffusion control on networks has been
extensively studied, with applications ranging from
marketing to controlling infectious disease. However,
in many applications, such as cybersecurity, an attacker
may want to attack a targeted subgraph of a network,
while limiting the impact on the rest of the network
in order to remain undetected. We present a model
POTION in which the principal aim is to optimize
graph structure to achieve such targeted attacks. We
propose an algorithm POTION-ALG for solving the
model at scale, using a gradient-based approach that leverages Rayleigh quotients and pseudospectrum theory. In addition, we present a condition for certifying that a
targeted subgraph is immune to such attacks. Finally, we demonstrate the effectiveness of our approach through experiments on real and synthetic networks.
more »
« less
- PAR ID:
- 10213632
- Date Published:
- Journal Name:
- SIAM Data Mining Conference
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
Abstract In many real-world networks, the ability to withstand targeted or global attacks; extinctions; or shocks is vital to the survival of the network itself, and of dependent structures such as economies (for financial networks) or even the planet (for ecosystems). Previous attempts to characterise robustness include nestedness of mutualistic networks or exploration of degree distribution. In this work we present a new approach for characterising the stability and robustness of networks with all-positive interactions by studying the distribution of the k-shell of the underlying network. We find that high occupancy of nodes in the inner and outer k-shells and low occupancy in the middle shells of financial and ecological networks (yielding a “U-shape” in a histogram of k-shell occupancy) provide resilience against both local targeted and global attacks. Investigation of this highly-populated core gives insights into the nature of a network (such as sharp transitions in the core composition of the stock market from a mix of industries to domination by one or two in the mid-1990s) and allow predictions of future network stability, e.g., by monitoring populations of “core” species in an ecosystem or noting when stocks in the core-dominant sector begin to move in lock-step, presaging a dramatic move in the market. Moreover, this “U-shape” recalls core-periphery structure, seen in a wide range of networks including opinion and internet networks, suggesting that the “U-shaped” occupancy histogram and its implications for network health may indeed be universal.more » « less
-
Physical, technological, and social networks are often at risk of intentional attack. Despite the wide-spanning importance of network vulnerability, very little is known about how criminal networks respond to attacks or whether intentional attacks affect criminal activity in the long-run. To assess criminal network responsiveness, we designed an empirically-grounded agent-based simulation using population-level network data on 16,847 illicit drug exchanges between 7,295 users of an active darknet drug market and statistical methods for simulation analysis. We consider three attack strategies: targeted attacks that delete structurally integral vertices, weak link attacks that delete large numbers of weakly connected vertices, and signal attacks that saturate the network with noisy signals. Results reveal that, while targeted attacks are effective when conducted at a large-scale, weak link and signal attacks deter more potential drug transactions and buyers when only a small portion of the network is attacked. We also find that intentional attacks affect network behavior. When networks are attacked, actors grow more cautious about forging ties, connecting less frequently and only to trustworthy alters. Operating in tandem, these two processes undermine long-term network robustness and increase network vulnerability to future attacks.more » « less
-
Network tomography is a powerful tool to monitor the internal state of a closed network that cannot be measured directly, with broad applications in the Internet, overlay networks, and all-optical networks. However, existing network tomography solutions all assume that the measurements are trust-worthy, leaving open how effective they are in an adversarial environment with possibly manipulated measurements. To understand the fundamental limit of network tomography in such a setting, we formulate and analyze a novel type of attack that aims at maximally degrading the performance of targeted paths without being localized by network tomography. By analyzing properties of the optimal attack, we formulate novel combinatorial optimizations to design the optimal attack strategy, which are then linked to well-known problems and approximation algorithms. Our evaluations on real topologies demonstrate the large damage of such attacks, signaling the need of new defenses.more » « less
-
The classic problem of exact subgraph matching returns those subgraphs in a large-scale data graph that are isomorphic to a given query graph, which has gained increasing importance in many real-world applications such as social network analysis, knowledge graph discovery in the Semantic Web, bibliographical network mining, and so on. In this paper, we propose a novel and effective graph neural network (GNN)-based path embedding framework (GNN-PE), which allows efficient exact subgraph matching without introducing false dismissals. Unlike traditional GNN-based graph embeddings that only produce approximate subgraph matching results, in this paper, we carefully devise GNN-based embeddings for paths, such that: if two paths (and 1-hop neighbors of vertices on them) have the subgraph relationship, their corresponding GNN-based embedding vectors will strictly follow the dominance relationship. With such a newly designed property of path dominance embeddings, we are able to propose effective pruning strategies based on path label/dominance embeddings and guarantee no false dismissals for subgraph matching. We build multidimensional indexes over path embedding vectors, and develop an efficient subgraph matching algorithm by traversing indexes over graph partitions in parallel and applying our pruning methods. We also propose a cost-model-based query plan that obtains query paths from the query graph with low query cost. Through extensive experiments, we confirm the efficiency and effectiveness of our proposed GNN-PE approach for exact subgraph matching on both real and synthetic graph data.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- The DOI is not currently available.
