BloomGML: Graph Machine Learning through the Lens of Bilevel Optimization

Amber Yijia Zheng, Tong He, Yixuan Qiu, Minjie Wang, David Wipf

Abstract

BloomGML (BiLevel Optimization Offers More Graph Machine Learning) introduces a unifying framework that bridges the gap between diverse graph learning techniques, including Graph Neural Networks (GNNs), Knowledge Graph Embeddings (KGE), and Label Propagation. By framing graph layers as optimization steps toward minimizing an energy function, BloomGML provides a principled approach to designing interpretable, robust, and flexible models for complex graph data.

Introduction

The field of Graph Machine Learning is currently characterized by a fragmentation of methodologies. GNNs often rely on message-passing heuristics, Label Propagation utilizes classical graph smoothing, and Knowledge Graph Embeddings focus on triplet scoring. This lack of a common mathematical foundation makes it difficult to compare models or understand the underlying mechanisms of node embedding generation. BloomGML addresses this by offering a "unifying vantage point" through the lens of bilevel optimization.

Methodology: The Bilevel Perspective

The core innovation of BloomGML is the use of Bilevel Optimization. This setup consists of two distinct levels:

  1. Upper Level: Focuses on the primary task, such as node classification, using a standard loss function (e.g., cross-entropy).
  2. Lower Level: Defines an "energy function" that characterizes optimal graph representations (e.g., ensuring neighboring nodes have similar embeddings).

The authors demonstrate that standard GNN layers can be mathematically derived as descent steps taken to minimize this lower-level energy function. This insight allows for the derivation of a flexible class of energy functions and a "canonical form" for message-passing that simplifies architecture design without sacrificing expressive power. Furthermore, by incorporating optimization techniques like momentum or proximal methods directly into the layers, the model achieves faster convergence and improved performance.

Experiments and Results

BloomGML was evaluated across a broad spectrum of benchmarks, including homophilic graphs (Cora, Citeseer), heterophilic graphs (Roman, Amazon), and Knowledge Graphs (WordNet, FB15K).

Robustness to Noise

A key strength of the BloomGML framework is its inherent robustness. By utilizing a Huber loss energy function, which is less sensitive to outliers than standard squared error, the model can effectively ignore corrupted node features.

Table 1: Performance comparison on homophilic datasets with 20% feature corruption. BloomGML shows superior accuracy and a high detection ratio for corrupted nodes.

As shown in Table 1, on datasets with 20% feature corruption, BloomGML significantly outperforms standard GCNs. For example, on the Cora dataset, BloomGML achieved 65.83% accuracy compared to the GCN's 51.40%. Additionally, the model's energy-based formulation acts as a diagnostic tool, identifying corrupted nodes with over 94% accuracy.

Performance on Heterophilic Graphs

BloomGML also demonstrates state-of-the-art performance on heterophilic benchmarks, where connected nodes frequently belong to different classes.

Table 2: Accuracy on heterophilic benchmarks. BloomGML (w/ Hub.) achieves state-of-the-art results across various datasets.

Table 2 illustrates that BloomGML (with Huber loss) achieves an average accuracy of 78.68% across five heterophilic tasks, surpassing specialized models such as FAGCN and JacobiConv.

Key Insights

  • KGE as Implicit GNNs: The research reveals that training traditional KGE models is mathematically equivalent to training implicit GNNs, explaining why explicit GNN layers often provide marginal gains in KGE tasks.
  • Interpretability: The energy function allows researchers to measure how much a node "disagrees" with its neighborhood, providing a built-in mechanism for data diagnostics.
  • Internal Optimization: Applying optimization tricks like Momentum or Adam inside the GNN layers helps the model reach better solutions with fewer layers.

Conclusion and Future Work

BloomGML provides a powerful theoretical framework for unifying graph learning. While highly effective, future research will focus on scaling these bilevel approaches to massive, billion-node graphs and exploring more complex, non-convex energy functions to capture deeper structural patterns in graph data.

Summary updated

BibTeX
@inproceedings{zheng2024bloomgml,
  author = {Amber Yijia Zheng and Tong He and Yixuan Qiu and Minjie Wang and David Wipf},
  title = {{BloomGML: Graph Machine Learning through the Lens of Bilevel Optimization}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=5okCNHjCWT},
}
Figure