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/

Zendy Plus

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

Zendy Tools

Zendy Open

The minimum cost multicut problem is the NP-hard/APX-hard combinatorialoptimization problem of partitioning a real-valued edge-weighted graph such asto minimize the total cost of the partition. While graph convolutional neuralnetworks (GNN) have proven to be promising in the context of combinatorialoptimization, most of them are only tailored to or tested on positive-valuededge weights, i.e. they do not comply to the nature of the multicut problem. Wetherefore adapt various GNN architectures including Graph ConvolutionalNetworks, Signed Graph Convolutional Networks and Graph Isomorphic Networks tofacilitate the efficient encoding of real-valued edge costs. Moreover, weemploy a reformulation of the multicut ILP constraints to a polynomial programas loss function that allows to learn feasible multicut solutions in a scalableway. Thus, we provide the first approach towards end-to-end trainablemulticuts. Our findings support that GNN approaches can produce good solutionsin practice while providing lower computation times and largely improvedscalability compared to LP solvers and optimized heuristics, especially whenconsidering large instances.

Learning to solve Minimum Cost Multicuts efficiently using Edge-Weighted Graph Convolutional Neural Networks