Multiplex Graph Representation Learning via Bi-level Optimization

Yudi Huang, Yujie Mo, Yujing Liu, Ci Nie

Abstract

Multiplex graphs, which contain multiple types of relationships between nodes, present unique challenges for representation learning. Existing methods often struggle with "edge starvation"—where unlabeled nodes lack structural supervision—and fail to capture negative relationships between dissimilar nodes. We present MGBO, a framework that decouples graph structure learning from downstream tasks using bi-level optimization. By optimizing a self-expression matrix in the inner loop and a Graph Convolutional Network (GCN) in the outer loop, MGBO effectively captures global structural patterns and improves generalization across various benchmarks. Experiments on four datasets show that MGBO consistently outperforms state-of-the-art baselines and effectively addresses the edge starvation problem.

Introduction

Multiplex graphs are prevalent in real-world scenarios, such as citation networks or social media platforms, where nodes are linked by diverse interaction types. Traditional Graph Neural Networks (GNNs) often fail to fully exploit these structures due to two primary issues: the neglect of negative relationships and the "edge starvation" problem. Most models rely on non-negative similarity metrics, ignoring nodes that should be explicitly disconnected. Furthermore, training structure and classification simultaneously often leads to overfitting on limited labeled data, leaving unlabeled nodes with poor structural guidance.

Methodology: Bi-level Optimization Framework

MGBO addresses these limitations through a nested optimization strategy. The framework consists of an inner level for structure learning and an outer level for representation learning, linked via hypergradient optimization.

The MGBO architecture illustrating the inner and outer optimization loops for structure and representation learning.

Inner Level: Structure Learning

The inner loop optimizes a self-expression matrix $C$, where each node is represented as a linear combination of others. Crucially, the coefficients in $C$ can be negative, allowing the model to identify dissimilar nodes. This process is guided by a graph learning loss ($L_{GL}$) that is independent of labels, ensuring the learned structure reflects the global topology rather than just the labeled subset.

Outer Level: Representation Learning

The outer loop optimizes the GCN parameters using a standard cross-entropy loss ($L_{CE}$) on labeled nodes. To link the levels, the outer level's parameters are updated based on the hypergradient of the inner level's optimal structure. An attention-based fusion mechanism combines the original multiple graph topologies with the learned self-expression matrix into a single, high-quality aggregated graph ($S$).

Experimental Results

The MGBO model was evaluated on four benchmark datasets: ACM, DBLP, IMDB, and Freebase. It consistently outperformed nine strong baselines, including HAN, MAGNN, and HGSL.

Comparison of Micro-F1 scores between MGBO and its variant MGBO-N across four datasets, highlighting the performance gain from the full bi-level framework.

Ablation studies, as shown in the figure above, demonstrate the importance of the full bi-level optimization framework. MGBO consistently achieves higher Micro-F1 scores compared to the MGBO-N variant. Removing the self-expression loss ($L_{GL}$) led to an average performance drop of approximately 2.1%, confirming that global structural relationships are critical. Furthermore, the model showed a significant 2.5% improvement on "starved nodes," confirming its ability to generalize structural information to unlabeled regions of the graph.

Conclusion

MGBO introduces a robust bi-level optimization approach to multiplex graph learning. By decoupling structure learning from the classification task and incorporating a self-expression mechanism, it overcomes the limitations of edge starvation and non-negative similarity. While bi-level optimization increases computational complexity, the resulting improvements in generalization and structural fidelity provide a powerful solution for complex graph representation tasks.

Summary updated

BibTeX
@inproceedings{huang2024multiplex,
  author = {Yudi Huang and Yujie Mo and Yujing Liu and Ci Nie},
  title = {{Multiplex Graph Representation Learning via Bi-level Optimization}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure