Pith Number

pith:63Q6LYCD

pith:2026:63Q6LYCDVJHTVNWPCVZBI3QV4L

not attested not anchored not stored refs resolved

Graph Neural Networks with Triangle-Based Messages for the Multicut Problem

Bjoern Andres, Jannik Irmai, Lucas Fabian Naumann

A graph neural network that passes messages only along triangles in edge-featured graphs finds higher-quality solutions to the multicut problem than existing heuristic solvers.

arxiv:2605.13673 v1 · 2026-05-13 · cs.LG

Open paper page JSON Open Graph Bundle Merged state Verified badge What is a Pith Number?

Add to your LaTeX paper

\usepackage{pith}
\pithnumber{63Q6LYCDVJHTVNWPCVZBI3QV4L}

Prints a linked badge after your title and injects PDF metadata. Compiles on arXiv. Learn more · Embed verified badge

Record completeness

1 Bitcoin timestamp

2 Internet Archive

3 Author claim open · sign in to claim

4 Citations open

5 Replications open

✓ Portable graph bundle live · download bundle · merged state

The bundle contains the canonical record plus signed events. A mirror can host it anywhere and recompute the same current state with the deterministic merge algorithm.

Claims

C1strongest claim

Experiments with synthetic and real-world instances with up to 200 nodes show that our method outperforms state-of-the-art heuristic solvers in terms of solution quality while maintaining feasible runtimes. For some instances, our method finds optimal solutions in seconds whereas exact solvers need hours to find and certify optimal solutions.

C2weakest assumption

The assumption that training the triangle-message GNN on the provided synthetic and real-world instances produces a model that generalizes reliably to new instances of the multicut problem without overfitting to the training distribution or requiring extensive hyperparameter tuning.

C3one line summary

A triangle-message GNN for multicut outperforms heuristics in solution quality on graphs up to 200 nodes and finds optimal solutions faster than exact solvers for some cases.

References

42 extracted · 42 resolved · 1 Pith anchors

[1] Learning to Solve Minimum Cost Multicuts Efficiently Using Edge-Weighted Graph Convolutional Neural Networks 2023 · doi:10.1007/978-3-031-26390-3_28

[2] and Riley, Patrick F 2017

[3] 2022 , url = 2022

[4] A State-of-the-Art Cutting Plane Algorithm for Clique Partitioning 2025

[5] Mathematical Programming Computation , year=

Cited by

1 paper in Pith

Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data

Receipt and verification

First computed	2026-05-18T02:44:17.142046Z
Builder	pith-number-builder-2026-05-17-v1
Signature	Pith Ed25519 (`pith-v1-2026-05`) · public key
Schema	pith-number/v1.0

Canonical hash

f6e1e5e043aa4f3ab6cf1572146e15e2f21d96ce9d94b21fdb3d03918bcc406d

Aliases

arxiv: 2605.13673 · arxiv_version: 2605.13673v1 · doi: 10.48550/arxiv.2605.13673 · pith_short_12: 63Q6LYCDVJHT · pith_short_16: 63Q6LYCDVJHTVNWP · pith_short_8: 63Q6LYCD

Agent API

Resolver JSON Graph JSON Events JSON Schema Signing key

Verify this Pith Number yourself

curl -sH 'Accept: application/ld+json' https://pith.science/pith/63Q6LYCDVJHTVNWPCVZBI3QV4L \
  | jq -c '.canonical_record' \
  | python3 -c "import sys,json,hashlib; b=json.dumps(json.loads(sys.stdin.read()), sort_keys=True, separators=(',',':'), ensure_ascii=False).encode(); print(hashlib.sha256(b).hexdigest())"
# expect: f6e1e5e043aa4f3ab6cf1572146e15e2f21d96ce9d94b21fdb3d03918bcc406d

Canonical record JSON

{
  "metadata": {
    "abstract_canon_sha256": "bc17fd0e50da1cae88468506639d1a7cc2a2ced156d7406118cfaeb71d16f07b",
    "cross_cats_sorted": [],
    "license": "http://arxiv.org/licenses/nonexclusive-distrib/1.0/",
    "primary_cat": "cs.LG",
    "submitted_at": "2026-05-13T15:33:13Z",
    "title_canon_sha256": "69ac531c67a3e5f79021cb24365125878aa8bfdaf19a8b66adef4501cd250282"
  },
  "schema_version": "1.0",
  "source": {
    "id": "2605.13673",
    "kind": "arxiv",
    "version": 1
  }
}