Teaching graph models to exchange messages as topology unfolds

Learning while the graph takes shape

A graph represents entities as nodes and relationships as edges. In a typical message-passing graph neural network, each node repeatedly combines its own representation with information from neighboring nodes. These updates are useful, but their distinguishing power has a mathematical ceiling: standard message-passing models are bounded by the one-dimensional Weisfeiler–Leman test, which cannot separate some structurally different graphs.

Persistent homology offers a complementary perspective. Rather than inspecting only the complete graph, it follows a nested sequence of subgraphs called a filtration. As nodes and edges appear, connected components form and merge, while cycles emerge. A persistence diagram records when these features appear and, where applicable, disappear.

In their November 4, 2026 preprint, the researchers introduce Message-Passing Graph Persistence, or MGP. Its central change is to update node representations on the intermediate filtration subgraphs themselves, rather than computing persistence separately from those updates.

What MGP records

MGP assigns filtration values to edges. A non-isolated node enters when its first incident edge appears; isolated nodes receive a birth value of zero. After the edges for a filtration step have been added, active nodes exchange messages using the connections currently available.

Each node contributes a tuple containing a birth value, a component-representative death value and a learned embedding. When a representative dies in a merger, the tuple uses its embedding from that step. Representatives surviving to the end use their final embeddings and an infinite death value. Cycle-creating edges contribute a separate collection of one-dimensional persistence tuples.

The choice of which representative survives a merger also depends on learned information. MGP orders representatives by their terminal embeddings—the representations obtained after the complete filtration-wise computation. The algorithm can therefore compute embeddings first and perform persistence pairing afterward. This avoids basing representative selection solely on early embeddings that may not yet reveal later structural differences.

Processing every distinct filtration value can require many updates. The authors also group values into a configurable number of quantile steps, keeping equal-valued edges together. This limits the number of message-passing stages, although computation still depends on the number of steps, rounds and filtrations used.

A theoretical gain with explicit conditions

The authors prove that MGP is invariant under graph isomorphism under a partial-injectivity assumption. In practical terms, renaming nodes should not change the descriptor. The assumption requires equal embeddings among the states considered to correspond to identical symbolic computation trees, ensuring that exact ties in representative selection do not alter the output. This is a condition of the guarantee, not an unconditional property of arbitrary learned neural-network weights.

They also prove that the MGP descriptor family is strictly more expressive than RePHINE. The comparison concerns whether some descriptor within each family can distinguish a pair of non-isomorphic graphs.

A simple example is a uniformly colored four-node star versus a four-node path. RePHINE gives them identical diagrams under the paper’s setup. An injective MGP update distinguishes their different degree patterns. This establishes the stated advantage over RePHINE; it does not show that MGP distinguishes every non-isomorphic graph pair.

Predictive gains, but little benchmark separation

The experiments cover five graph-classification datasets and the 12,000-molecule ZINC regression subset. Methods share a selected GINE backbone for each dataset. Results are reported as means and standard deviations across five training seeds.

MGP obtains the best mean results on PTC MR, PROTEINS, NCI109 and ZINC. On ZINC, where lower mean absolute error is better, it scores 0.110 ± 0.011, compared with 0.142 ± 0.013 for RePHINE. RePHINE leads on NCI1, while conventional persistent homology leads on MUTAG. These are benchmark outcomes, not evidence of uniform superiority.

On BREC, a collection of 400 non-isomorphic graph pairs, MGP and RePHINE distinguish approximately the same proportion of pairs. The evaluation includes random relabelings to check descriptor reliability. The theoretical expressivity advantage therefore does not translate into a substantial separation in this experiment.

How far the evidence reaches

The comparisons have important qualifications. MGP receives a larger backbone search and substantially more descriptor tuning than the baselines. SpectRe is evaluated using a reduced implementation that samples spectral information at every third event; the authors note that tied filtration values can make this setting not exactly permutation invariant. The classification experiments also use one fixed train–validation–test split, rather than multiple independently sampled splits.

Finally, the work studies graphs, not higher-order structures such as simplicial or cell complexes. Its contribution is a specific integration of message passing and persistence, supported by conditional theory and promising—but bounded—experimental evidence.