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

The ability of graph neural networks (GNNs) to count certain graphsubstructures, especially cycles, is important for the success of GNNs on awide range of tasks. It has been recently used as a popular metric forevaluating the expressive power of GNNs. Many of the proposed GNN models withprovable cycle counting power are based on subgraph GNNs, i.e., extracting abag of subgraphs from the input graph, generating representations for eachsubgraph, and using them to augment the representation of the input graph.However, those methods require heavy preprocessing, and suffer from high timeand memory costs. In this paper, we overcome the aforementioned limitations ofsubgraph GNNs by proposing a novel class of GNNs -- $d$-Distance-RestrictedFWL(2) GNNs, or $d$-DRFWL(2) GNNs. $d$-DRFWL(2) GNNs use node pairs whosemutual distances are at most $d$ as the units for message passing to balancethe expressive power and complexity. By performing message passing amongdistance-restricted node pairs in the original graph, $d$-DRFWL(2) GNNs avoidthe expensive subgraph extraction operations in subgraph GNNs, making both thetime and space complexity lower. We theoretically show that the discriminativepower of $d$-DRFWL(2) GNNs strictly increases as $d$ increases. Moreimportantly, $d$-DRFWL(2) GNNs have provably strong cycle counting power evenwith $d=2$: they can count all 3, 4, 5, 6-cycles. Since 6-cycles (e.g., benzenerings) are ubiquitous in organic molecules, being able to detect and count themis crucial for achieving robust and generalizable performance on moleculartasks. Experiments on both synthetic datasets and molecular datasets verify ourtheory. To the best of our knowledge, our model is the most efficient GNN modelto date (both theoretically and empirically) that can count up to 6-cycles.

Distance-Restricted Folklore Weisfeiler-Leman GNNs with Provable Cycle Counting Power