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 Plus annual

Presents the access of premium content as premium feature

Premium Content

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 Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Graph alignment refers to the task of finding the vertex correspondencebetween two positively correlated graphs. Extensive study has been done onpolynomial-time algorithms for the graph alignment problem under theErd\H{o}s--R\'enyi graph pair model, where the two graphs areErd\H{o}s--R\'enyi graphs with edge probability $q_\mathrm{u}$, correlatedunder certain vertex correspondence. To achieve exact recovery of the vertexcorrespondence, all existing algorithms at least require the edge correlationcoefficient $\rho_\mathrm{u}$ between the two graphs to satisfy$\rho_\mathrm{u} > \sqrt{\alpha}$, where $\alpha \approx 0.338$ is Otter'stree-counting constant. Moreover, it is conjectured in [1] that nopolynomial-time algorithm can achieve exact recovery under weak edgecorrelation $\rho_\mathrm{u}<\sqrt{\alpha}$.  In this paper, we show that with a vanishing amount of additional attributeinformation, exact recovery is polynomial-time feasible under vanishing edgecorrelation $\rho_\mathrm{u} \ge n^{-\Theta(1)}$. We identify a local treestructure, which incorporates one layer of user information and one layer ofattribute information, and apply the subgraph counting technique to suchstructures. A polynomial-time algorithm is proposed that recovers the vertexcorrespondence for all but a vanishing fraction of vertices. We then furtherrefine the algorithm output to achieve exact recovery. The motivation forconsidering additional attribute information comes from the widely availableside information in real-world applications, such as the user's birthplace andeducational background on LinkedIn and Twitter social networks.

Efficient Algorithms for Attributed Graph Alignment with Vanishing Edge Correlation