Abstract
Training Graph Neural Networks (GNNs) for semi-supervised tasks often relies on first-order optimization methods like Adam or SGD, which can suffer from slow convergence and sensitivity to hyperparameters. This paper proposes a novel optimization framework applying Natural Gradient Descent (NGD) to GNNs. By leveraging information geometry and incorporating unlabeled data into curvature estimation via Kronecker-Factored Approximate Curvature (KFAC), the authors achieve significantly faster convergence and improved accuracy across benchmark citation networks.
Introduction
Semi-supervised node classification is a cornerstone task for Graph Neural Networks (GNNs). Standard training typically employs Stochastic Gradient Descent (SGD) or Adam. However, these first-order methods treat the parameter space as Euclidean, ignoring the underlying "curvature" of the loss landscape. While second-order methods like Newton’s method account for this curvature, they are computationally prohibitive for deep learning due to the scale of the Hessian matrix.
Natural Gradient Descent (NGD) offers a middle ground by navigating the statistical manifold of the model's probability distributions. This paper adapts NGD for the unique graph-based setting where unlabeled data is abundant, proposing a preconditioning algorithm that transforms standard gradients into natural gradients.
Methodology
The core contribution is a semi-supervised preconditioning algorithm based on Natural Gradient Descent. To facilitate the mathematical discussion, the following notation is adopted:
Natural Gradient Descent and KFAC
NGD moves in the direction of steepest descent relative to the Fisher Information Matrix (FIM), ensuring invariance to model reparameterization. To handle the computational complexity of the FIM, the authors utilize Kronecker-Factored Approximate Curvature (KFAC). KFAC approximates the FIM as a block-diagonal matrix where each layer-wise block is the Kronecker product of two smaller matrices.
Semi-Supervised Fisher Estimation
A key innovation is the inclusion of unlabeled nodes in the Fisher estimation. Standard KFAC relies solely on labeled data. The proposed method uses the model’s own predictions as "pseudo-labels" for unlabeled nodes, weighted by a regularization hyperparameter $\lambda$. This hyperparameter can evolve during training via a decay factor $\gamma$, allowing the optimizer to leverage the global graph structure for more stable curvature estimation.
Experiments and Results
The framework was evaluated on three citation networks: CiteSeer, Cora, and PubMed, using various data splits (standard, public, and full).
Performance Metrics
- Accuracy: The proposed Adam-KFAC and SGD-KFAC consistently outperformed their vanilla counterparts. For instance, on CiteSeer, Adam-KFAC reached ~74.28% accuracy, a significant improvement over Adam's ~71.66%.
- Convergence: KFAC-based methods demonstrated remarkably faster convergence. SGD-KFAC reached lower validation costs in fewer epochs compared to standard SGD.
- Stability: Incorporating unlabeled data into the Fisher estimation resulted in tighter confidence intervals, suggesting a more robust training process.
Discussion
The results highlight several key insights:
- Geometric Optimization: Distributional changes provide a more meaningful metric for optimization than raw numerical weight changes.
- Value of Unlabeled Data: Beyond its use in loss functions (e.g., Laplacian regularization), unlabeled data is highly effective for estimating the geometry of the search space.
- Preconditioning vs. Heuristics: SGD preconditioned with natural gradients (SGD-KFAC) often outperformed Adam, suggesting that explicit curvature information is more powerful than the heuristic momentum used in adaptive methods.
Conclusion
This work demonstrates that Natural Gradient Descent, specifically when enhanced with semi-supervised Fisher estimation and KFAC approximations, significantly improves GNN optimization. While currently focused on standard GCN layers, future work includes extending this to complex architectures like residual networks and further optimizing the computational overhead of KFAC updates.
Summary updated