On anti-stochastic properties of unlabeled graphs
This addresses a theoretical problem in graph theory and adversarial robustness for researchers, but it is incremental as it extends known results from labeled to unlabeled graphs.
The paper tackles the problem of vulnerability in unlabeled random graphs to local adversarial perturbations that aim to change global distribution properties, showing that anti-stochastic properties exist with probabilities as low as (2+o(1))/n^2 and (2+o(1))/(n ln n), which are optimal or near-optimal.
We study vulnerability of a uniformly distributed random graph to an attack by an adversary who aims for a global change of the distribution while being able to make only a local change in the graph. We call a graph property $A$ anti-stochastic if the probability that a random graph $G$ satisfies $A$ is small but, with high probability, there is a small perturbation transforming $G$ into a graph satisfying $A$. While for labeled graphs such properties are easy to obtain from binary covering codes, the existence of anti-stochastic properties for unlabeled graphs is not so evident. If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an anti-stochastic property that is satisfied by a random unlabeled graph of order $n$ with probability $(2+o(1))/n^2$, which is as small as possible. We also express another anti-stochastic property in terms of the degree sequence of a graph. This property has probability $(2+o(1))/(n\ln n)$, which is optimal up to factor of 2.