Cross Local Intrinsic Dimensionality (LID)
Generative Adversarial Networks (GANs) are an elegant mechanism for data generation. However, a key challenge when using GANs is how to best measure their ability to generate realistic data. In this paper, we demonstrate that an intrinsic dimensional characterization of the data space learned by a GAN model leads to an effective evaluation metric for GAN quality. In particular, we propose a new evaluation measure, CrossLID, that assesses the local intrinsic dimensionality (LID) of real-world data with respect to neighborhoods found in GAN-generated samples. Intuitively, CrossLID measures the degree to which manifolds of two data distributions coincide with each other. In experiments on 4 benchmark image datasets, we compare our proposed measure to several state-of-the-art evaluation metrics. Our experiments show that CrossLID is strongly correlated with the progress of GAN training, is sensitive to mode collapse, is robust to small-scale noise and image transformations, and robust to sample size. Furthermore, we show how CrossLID can be used within the GAN training process to improve generation quality. …

A graph is $d$-orientable if its edges can be oriented so that the maximum in-degree of the resulting digraph is at most $d$. $d$-orientability is a well-studied concept with close connections to fundamental graph-theoretic notions and applications as a load balancing problem. In this paper we consider the d-ORIENTABLE DELETION problem: given a graph $G=(V,E)$, delete the minimum number of vertices to make $G$ $d$-orientable. We contribute a number of results that improve the state of the art on this problem. Specifically: – We show that the problem is W[2]-hard and $\log n$-inapproximable with respect to $k$, the number of deleted vertices. This closes the gap in the problem’s approximability. – We completely characterize the parameterized complexity of the problem on chordal graphs: it is FPT parameterized by $d+k$, but W-hard for each of the parameters $d,k$ separately. – We show that, under the SETH, for all $d,\epsilon$, the problem does not admit a $(d+2-\epsilon)^{tw}$, algorithm where $tw$ is the graph’s treewidth, resolving as a special case an open problem on the complexity of PSEUDOFOREST DELETION. – We show that the problem is W-hard parameterized by the input graph’s clique-width. Complementing this, we provide an algorithm running in time $d^{O(d\cdot cw)}$, showing that the problem is FPT by $d+cw$, and improving the previously best known algorithm for this case. …