Title: Mastering Timing and Placement: Adaptive Virtual Nodes for Dynamic Message Passing in Graphs

Abstract

Although Virtual Nodes (VNs) are frequently employed in Message Passing Neural Networks (MPNNs) to enhance message propagation, current VN-based approaches suffer from significant constraints. These include mandating that every node links to an identical number of VNs, establishing connections prior to the execution of MPNNs, and facilitating node-to-VN associations independently of other nodes sharing that same VN. To address these issues, we introduce MAVN, an end-to-end differentiable MPNN framework that enables unconstrained connectivity between nodes and VNs. MAVN dynamically generates VNs as needed, responding to the changing representations of nodes across different layers.

The framework learns to intelligently decide when (specifically, at which layer) and where (which nodes) to introduce and link VNs, relying on the relative significance of these connections. From a reservoir of candidate VNs, MAVN identifies the requisite VNs for each layer, ensuring that each selected VN connects to a non-empty group of nodes. This selection process is driven by a dual-perspective scoring mechanism that simultaneously evaluates the nodes’ preferences for VNs and the VNs’ preferences for nodes. We provide a theoretical proof demonstrating that for any given node-VN connectivity pattern, there exists a corresponding set of MAVN parameters capable of simulating that pattern. Empirical evaluations across nine real-world datasets show that MAVN consistently boosts the performance of backbone MPNNs, delivering improvements of up to 46.5% over the base models and surpassing existing baselines.

Source: arXiv Generated at: 2026-06-03 00:00:00 UTC