acceptodds
Under review as a conference paper at ICLR 2027

Persistent Tri-State Message Passing

Abstract

In stochastic message passing, an edge's sampled role changes the node states used to compute adaptive weights at later layers. Weight averaging therefore depends on whether edge roles persist across layers or are resampled at each layer. We study this dependence in Persistent Tri-State Message Passing (P3MP), which combines persistent additive, subtractive, and inactive roles with weights computed from each sample's endpoint states. For two layers, we separate target-state feedback from weight-source covariance and derive the condition under which local and shared weights reverse their preactivation ordering. Shared weights retain a fraction of the feedback for samples. The interaction is zero for a source-only scorer. Permuting complete weight vectors between samples quantifies the same role-state dependence while preserving their empirical distribution. Exact enumeration and feature-only checkpoint measurements agree with the analytical predictions. Across independently trained feature-only models, local weights yield higher accuracy and lower negative log-likelihood under persistence, while shared weights yield higher accuracy and lower loss under layerwise resampling. The same accuracy ordering holds on deduplicated Chameleon and Squirrel. The implementation and comparison methods are available at https://anonymous.4open.science/r/P3MP-F63D.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph neural networks, Graph Heterophily, Tri-State edge roles

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_NaBSOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the interaction between cross-layer edge-role sampling and adaptive message weighting in graph neural networks. The authors propose Persistent Tri-State Message Passing (P3MP), which assigns each edge an additive, subtractive, or inactive role that persists across layers, while recomputing its weight from the current endpoint representations. Through a two-layer analysis, the paper decomposes the interaction between sampling and weight sharing into target-state feedback and weight-source covariance, deriving conditions under which local and shared weights exhibit different preactivation orderings. Experiments on multiple graph benchmarks support the theoretical analysis and show that local weights perform better under persistent sampling, whereas shared weights perform better under layerwise resampling.

Critical strengths
  1. The paper investigates an interesting and underexplored interaction in stochastic message passing. This paper examines how cross-layer dependencies induced by sampling affect subsequent weight computation. This is a meaningful problem for understanding stochastic GNN architectures.
  2. The experimental design includes several informative controlled comparisons. The authors compare persistent sampling against layerwise resampling, as well as local weighting against shared weighting. Exact enumeration, checkpoint-level interventions, and distribution-preserving weight reassignment provide additional evidence for the proposed explanation beyond end-to-end performance comparisons.
  3. The empirical evaluation is reasonable. The paper evaluates P3MP on multiple graph benchmarks with varying levels of homophily and compares it against numerous established GNN baselines. The reported results are promising.
Critical weaknesses
  1. The theoretical results are primarily established for a restricted computational setting. The paper does not establish a general guarantee linking the derived interaction to the final predictive performance of an end-to-end trained GNN. Consequently, the extent to which the theoretical results explain the observed accuracy improvements remains unclear.
  2. The empirical evidence for the proposed interaction is somewhat limited. The reported accuracy interaction is approximately 1.1–2.5 percentage points on the five datasets used for the main sampling-weighting comparison. Moreover, each of the ten benchmark partitions uses only one initialization, limiting the ability to disentangle variability due to data splits from variability due to model initialization. Additional experiments would help establish the robustness and generality of the observed ordering.
  3. The relationship between the theoretical mechanism and the overall architectural improvements could be established more directly. P3MP combines persistent tri-state roles, endpoint-dependent adaptive weights, thresholding, mixture NLL, and structural regularization. Although the paper includes component ablations and controlled sampling-weighting comparisons, the theoretical analysis focuses on the interaction between sampling and weighting rather than the full training dynamics. It remains unclear how much of the end-to-end improvement can be attributed specifically to the proposed interaction, as opposed to the combined effects of the other architectural and optimization choices.
Questions for authors
  1. Can the authors extend the theoretical analysis beyond the two-layer setting to establish conditions under which the derived preactivation ordering also translates into final prediction or classification performance?
  2. How robust are the reported sampling-weighting interactions across random initializations, additional datasets, and different graph structures?
  3. Can the authors further isolate the contribution of the proposed sampling-weighting interaction from the effects of tri-state roles, adaptive endpoint scoring, thresholding, and mixture NLL?
Reviewer_3yyDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes a stochastic GNN framework where each edge is assigned one of three roles—additive, subtractive, or inactive—and that role persists across layers. The key observation is that if an edge’s sampled role changes a node’s hidden state in an early layer, then adaptive edge weights computed in later layers become statistically coupled to that earlier role.

Critical strengths
  1. The paper studies a subtle but meaningful mechanism in stochastic message passing. It identifies that persistent edge roles can couple earlier sampled roles with later adaptive weights, which is a non-trivial effect that is easy to overlook in stochastic GNN design.
  2. The analysis is relatively complete and internally consistent. The paper combines a formal two-layer decomposition, diagnostic interventions, and empirical validation. Even if the broader impact is not fully established, the explanation pipeline is coherent and helps clarify why local and shared weights behave differently under persistence versus resampling.
Critical weaknesses
  1. The motivation and scope are not fully convincing. The paper reads more like a mechanism-explanation work focused on P3MP itself. While it analyzes how cross-layer role correlation interacts with cross-sample weight sharing, it does not clearly show that this issue is broadly relevant to stochastic GNNs beyond the proposed design.
  2. The link between theory and empirical performance is not tight enough. The paper provides theoretical analysis and supporting experiments, but it does not directly establish that the observed performance differences are mainly caused by the target-state feedback term F. Some comparisons appear to change multiple factors at once, making it hard to isolate the effect of the proposed mechanism.
Questions for authors
  1. Is the cross-layer role correlation analyzed in this paper specific to P3MP, or should we expect the same phenomenon in other stochastic GNNs or DropEdge-like methods?
  2. Can the authors provide a more direct experiment showing that the performance gap is primarily driven by the target-state feedback term F?
  3. In the comparison between local and shared weights, how do the authors separate the effects of sampling strategy, adaptive weight computation, and prediction averaging?
Reviewer_L9GwOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies how different choices in stochastic message passing affect the behavior of GNNs. The authors propose P3MP, where each edge can contribute positively, negatively, or not at all. The model learns probabilities for these three roles, samples multiple edge-role assignments, and averages predictions computed using shared model parameters.

The paper compares four configurations based on two choices. First, the sampled role of each edge can either remain fixed across layers or be resampled at every layer. Second, each sample can use edge weights computed from its own node representations, or the weights can be averaged across samples and shared during message passing.

The main theoretical result is a covariance-based decomposition that characterizes how these choices interact. For a two-layer computation with fixed parameters, it gives a condition under which the ordering of expected projected preactivations between local and shared weighting reverses. The authors also examine how graph structure and network depth affect the dependence between edge roles and node representations. Experimentally, P3MP achieves the highest mean performance on seven of eight benchmarks. Across five datasets, local weighting performs better under persistence, while shared weighting performs better under resampling.

Critical strengths

S1. The paper studies an interesting question about the interaction between persistent sampling and adaptive edge weighting in GNNs. It provides a precise mathematical characterization of this interaction.

S2. The experimental results are promising. P3MP achieves the highest mean performance on seven of eight benchmarks, and the experiments show a consistent pattern across five datasets.

Critical weaknesses

W1. The architectural novelty seems somewhat limited. Stochastic edge selection, signed message passing, and adaptive weighting are existing ideas, so the main novelty appears to lie in the analysis of their interaction. The analysis is broadly applicable, but it does not specifically explain why three edge roles should be preferable to simpler alternatives.

Questions for authors

Q1. Does the analysis establish a theoretical advantage of tri-state over binary gates, or is the advantage mainly empirical?

Q2. Regarding W1, could you clarify the main conceptual advance over prior work?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.