English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Tools annual

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider the problem of sampling and approximately counting an arbitrarygiven motif $H$ in a graph $G$, where access to $G$ is given via queries:degree, neighbor, and pair, as well as uniform edge sample queries. Previousalgorithms for these tasks were based on a decomposition of $H$ into acollection of odd cycles and stars, denoted $\mathcal{D}^*(H)=\{O_{k_1},\ldots, O_{k_q}, S_{p_1}, \ldots, S_{p_\ell}\}$. These algorithms were shown tobe optimal for the case where $H$ is a clique or an odd-length cycle, but noother lower bounds were known.  We present a new algorithm for sampling and approximately counting arbitrarymotifs which, up to $\textrm{poly}(\log n)$ factors, is always at least as goodas previous results, and for most graphs $G$ is strictly better. The mainingredient leading to this improvement is an improved uniform algorithm forsampling stars, which might be of independent interest, as it allows to samplevertices according to the $p$-th moment of the degree distribution.  Finally, we prove that this algorithm is \emph{decomposition-optimal} fordecompositions that contain at least one odd cycle. These are the first lowerbounds for motifs $H$ with a nontrivial decomposition, i.e., motifs that havemore than a single component in their decomposition.

Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time