Abstract
Traditional Graph Neural Networks (GNNs) rely on iterative diffusion processes to reach a stable fixed point for node representations, incurring significant computational costs. This paper presents Lagrangian Propagation Graph Neural Networks (LP-GNNs), which reformulate the fixed-point requirement as a constrained optimization problem. By jointly optimizing node states and model weights within a Lagrangian framework, LP-GNNs eliminate the need for per-epoch iterative unfolding, enabling deeper architectures and more efficient training.
Introduction
Standard GNN architectures typically employ a state transition function that must converge to a fixed point to represent node features accurately. This "diffusion" process is usually implemented by iterating a recurrent network until stability is reached. However, this approach is computationally expensive ($O(T)$ iterations per update) and often leads to vanishing information if the diffusion is truncated early to save time. LP-GNNs address these limitations by treating the fixed-point condition as a hard constraint, allowing node states to evolve alongside model parameters during training.
Methodology: The Lagrangian Framework
The core innovation of the LP-GNN is the transformation of the architectural fixed-point condition, $x_v = f_a(neighbors)$, into a constraint within a Lagrangian function.
Joint Optimization
Instead of the traditional two-step process—diffusion followed by weight updates—LP-GNNs utilize a gradient descent-ascent strategy. The model simultaneously updates the model weights ($\theta$), the node state variables ($x_v$), and the Lagrange multipliers ($\lambda$).
As shown in the figure above, node states do not need to be perfectly converged at the start of training; they reach the fixed point as the model weights mature. This reduces the complexity per parameter update from $O(T(|V|+|E|))$ to $O(|V|+|E|)$, effectively breaking the "shallow" barrier of traditional recurrent GNNs.
Experimental Evaluation
The authors evaluated LP-GNNs across a diverse set of benchmarks, ranging from social network analysis to isomorphism testing.
Qualitative Analysis and Benchmarks
On Zachary’s Karate Club dataset, LP-GNN demonstrated its ability to capture community structures effectively through its implicit diffusion process.
In quantitative tests, LP-GNN-Multi (a multi-layered version) achieved competitive results against state-of-the-art models:
- IMDB-B: 76.2% accuracy (surpassing GIN's 75.1%).
- MUTAG: 92.2% accuracy.
- CSL (Isomorphism): 98.9% accuracy, proving the model can effectively utilize positional encodings to solve complex graph topology problems.
Discussion and Conclusion
LP-GNNs represent a significant shift from iterative diffusion to constraint-based propagation. By avoiding the expensive "unfolding" of recurrent steps, the model can simulate deep information flow with significantly lower memory and time overhead. While the inference phase still requires a brief optimization routine for new graphs, the training efficiency and performance gains on complex datasets like CSL suggest that Lagrangian frameworks are a powerful alternative for deep graph representation learning.
Summary updated