Multiplex Graph Representation Learning via Bi-level Optimization

Yudi Huang, Yujie Mo, Yujing Liu, Ci Nie, Guoqiu Wen, Xiaofeng Zhu

Multiplex Graph Representation Learning via Bi-level Optimization

Multiplex graphs are essential for modeling complex real-world systems where entities (nodes) are linked by diverse types of relationships (edges). For instance, in an academic network, papers might be connected via shared authors, citations, or common venues. However, effectively learning representations from such data is hindered by two primary issues: noisy or incomplete graph structures and "edge starvation." The latter occurs when the supervision signal from labeled nodes fails to propagate to distant, unlabeled parts of the graph, leading to poor generalization.

To address these challenges, the Multiplex Graph Representation Learning via Bi-level Optimization (MGBO) framework decouples the learning of graph structures from the downstream classification task. Unlike traditional methods that treat the input graph as a fixed gold standard, MGBO views the graph topology as a learnable parameter optimized through a bi-level objective.

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

The MGBO Framework

The core of MGBO is a nested optimization loop that treats graph structure learning and representation learning as distinct but interdependent tasks:

  • Inner Level (Graph Structure Learning): This stage focuses on refining the graph topology. Instead of relying on local similarity metrics, MGBO employs a self-expression property, assuming each node can be represented as a linear combination of all other nodes. This allows the model to capture global dependencies and, crucially, "negative relationships"—identifying pairs of nodes that should remain disconnected. The inner loop optimizes this self-expression matrix guided by a graph learning loss ($L_{GL}$).
  • Outer Level (Representation Learning): The refined structure is fused with the original multiplex layers using a channel attention mechanism. This aggregated graph is then passed to a Graph Convolutional Network (GCN). The outer loop optimizes the GCN parameters based on the cross-entropy loss ($L_{CE}$) of the downstream task.

The interaction between these levels is managed via hypergradient optimization, where the gradient of the task loss in the outer loop informs the updates in the inner loop, ensuring the learned structure is optimal for the final prediction task.

Key Insights

MGBO's success stems from several innovative design choices. By using a self-expression matrix, the model moves beyond local neighborhoods to capture global feature correlations. Furthermore, separating structure learning from label supervision prevents the model from overfitting the graph topology to the small set of available training labels, effectively mitigating the edge starvation problem. Finally, MGBO recognizes that identifying nodes that are dissimilar is as critical for discriminative learning as identifying similar ones.

Performance and Results

MGBO was evaluated on four benchmark datasets: ACM, DBLP, IMDB, and Freebase. It consistently outperformed state-of-the-art baselines like HAN, GAT, and HGSL.

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

As shown in the experimental results, the full MGBO model provides a clear performance boost over its variants. Specifically, on the DBLP dataset, MGBO achieved a Macro-F1 of 95.2%. Ablation studies confirmed that the self-expression loss is vital, as its removal led to an average performance drop of 2.1%. Furthermore, MGBO demonstrated superior performance on "starved" nodes, showing a 2.5% improvement over non-bi-level counterparts.

Conclusion

MGBO offers a robust solution for multiplex graph representation learning by treating structure discovery as a fundamental part of the optimization process. While the bi-level approach introduces some computational complexity due to the $N \times N$ self-expression matrix, its ability to handle noisy data and solve edge starvation makes it a powerful tool for complex network analysis. Future work may focus on improving the scalability of the framework for massive graphs and extending it to dynamic, time-varying networks.

Summary updated

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