Multiplex Graph Representation Learning via Bi-level Optimization

1 Introduction

Multiplex graph consists of multiple graph structures and shared node features, and each graph reflects a specific relationship among nodes. Regarding the complex relationships in the multiplex graph, traditional graph representation learning (GRL) methods generally lack the capability to process it effectively [Fan et al., 2019; Yang et al., 2023; Liang et al., 2024]. Therefore, multiplex graph representation learning (MGRL) methods are proposed to learn the low-dimensional node representations by mining the hidden information in the multiplex graph [Yu et al., 2021], and have been adapted to various real-world applications, e.g., social media analysis, community anomaly detection, and recommendation systems [Chen et al., 2022; Xie et al., 2022].

Existing MGRL methods can be broadly categorized into two groups, i.e., node feature-free methods and node featurebased methods. Specifically, the former generally employ the structural information only to obtain node representations. For example, Metapath2vec [Dong et al., 2017] employs random walk to obtain the sequences on metapaths and generate node representations. MNE [Zhang et al., 2018] unifies structural information among various relationships into a shared representation space by random walk. However, these methods ignore the discriminative information in the node features, degrading node representations. Therefore, recent works are proposed to consider both node feature information and structural information in the multiplex graph. For example, MGCN [Ghorbani et al., 2019] combines structural information with node features under the framework of graph convolutional networks. HAN [Wang et al., 2019] aggregates node features using node-level attention and semantic-level attention and MAGNN [Fu et al., 2020] aggregates meta-path ends and intermediates node features.

∗Corresponding author.

Despite effectiveness, most of previous MGRL methods rely on a basic assumption, i.e., the original graph structure is reliable. This is generally unrealistic as graph structures are inevitably noisy or missing [Kang et al., 2019; Zhang and He, 2023]. To mitigate it, some MGRL works adopt graph structure learning in traditional GRL methods to improve the model performance. For example, HGSL [Zhao et al., 2021] utilizes the feature similarity to obtain the superior compositional graph structure. However, these methods still have the following limitations. First, these works optimize the graph structure with the feature similarity to measure whether nodes belong to the same class or not, so it cannot effectively capture negative relationships among nodes. Moreover, the feature similarity focuses on single pairs of nodes and cannot effectively capture the global relationships among each node and all nodes simultaneously. Second, these works optimize the parameters of graph structure learning by directly depending on the classification task. As a result, this may lead to edge starvation problem, i.e., the representation of edges is obtained by receiving less help of supervision information, leading to poor generalization ability [Fatemi et al., 2021]. Based on the above analysis, capturing globally positive and negative relationships among nodes, as well as separately conducting graph structure learning and representation learning, helps to enhance the MGRL performance.

To address the above challenges, in this paper, we propose a new MGRL framework, i.e., Multiplex Graph Representation Learning via Bi-level Optimization (MGBO), as shown in Figure 1. Specifically, we utilize the self-expression matrix to adaptively capture the globally positive and negative relationships among nodes and complement them with the local relationships in graph structures. Moreover, we consider the learning of self-expression matrix and the representation learning as a bi-level optimization problem. That is, the inner level optimizes the self-expression matrix by learning the globally positive and negative relationships among nodes, while the outer level optimizes the representation learning parameters by the classification task based on the optimized graph structure. In addition, the node representations generated in the outer level is used in the inner level to adaptively optimize the self-expression matrix. In this way, graph structure learning is detached from the directly supervision of the node classification task, so edge starvation problem are solved, and the interdependence between graph structure learning and representation learning is fully utilized.

Compared to previous MGRL methods, the contributions of the proposed method can be summarized as:

• We utilize the self-expression property to adaptively capture the globally positive and negative relationships among nodes, achieving the effectiveness MGRL.
• To the best of our knowledge, we propose the first bilevel optimization for MGRL, where the self-expression matrix and the representations learning are optimized in the inner and outer level of the model, respectively, to solve the edge starvation problem.
• We investigate a new algorithm for the proposed bi-level optimization. Comprehensive experimental results on multiple benchmark datasets demonstrate the effectiveness of our method on node classification tasks, compared to nine comparison methods.

2 RelatedWork

2.1 Graph Structure Learning

Graph structure learning aims to optimize the graph structure for better adaptation to downstream tasks. Early methods such as LDS [Franceschi et al., 2019] typically modeled each edge using Bernoulli random variables and created graph structures by sampling from these distributions. However, these direct parameterizations of the adjacency matrix are time and space consuming [Zhao et al., 2023]. An alternative approach is to provide complementary information to the graph structure based on node feature similarity. For example, IDGL [Chen et al., 2020] iteratively learns metrics to generate graph structures from node features and GNN embeddings. GLCN [Jiang et al., 2019] combines graph learning and graph convolution to learn graph structure through the smoothness of node features. ProGNN [Jin et al., 2020] iteratively reconstructs the clean graph by preserving the low rank, sparsity, and feature smoothness properties of a graph. In addition, MV-GCN [Yuan et al., 2021] proposes to improve the performance of the model by using local structure, global structure, and feature similarity. Recently, HGSL proposed graph structure learning for heterogeneous graphs via feature similarity graphs, feature propagation graphs and semantic similarity graphs.

2.2 Multiplex Graph Representation Learning

MGRL aims to obtain low-dimensional and discriminative node representations by mining information from multiplex graph structures [Mo et al., 2023b]. Depending on whether or not node features are used when performing graph representation learning, previous MGRL works can be categorized into two types, i.e., node feature-free methods and node feature-based methods.

Early MGRL methods usually fall into the category of node feature-free methods. For example, Metapath2vec [Dong et al., 2017] utilizes metapath-based random wandering with skip-gram method to obtain node representations.GATNE-T [Cen et al., 2019]fuses base embeddings and edge embeddings to form holistic embeddings and learns them through the skip-grammethod. In addition, MNE [Zhang et al., 2018] unifies information from various relation types into a shared representation space by metapath-based random walk. However, the performance of these MGRL methods is always unsatisfactory because these methods ignore the discriminative information contained in the node features.

Therefore, subsequent work attempts to improve model performance by considering both node features and structural information. For example, HAN [Wang et al., 2019] uses the attention mechanism to aggregate node features to form node-level representations and semantic-level representations. FAME [Liu et al., 2020] captures meta-paths with multiple inter-node relationships and higher-order topologies, and combines node features to learn low-dimensional representations of nodes. MAGNN [Fu et al., 2020] proposes to aggregate node features within and across meta-paths to improve the performance. MHGCN [Yu et al., 2022] uses multilayer graph convolution modules to automatically capture short and long metapath interactions across multiple relations to learn node representation. In addition, BPHGNN [Fu et al., 2023] captures locally and globally relevant information about a node from both depth and breadth patterns.

3 Method

Notations. Let G = {G (1) , G (2) , . . . , G (R) } = {V, E,X} to denote the multiplex graph, where G (r) = {V, E (r) , X} is the r-th graph in the multiplex graph, and R is the number of graphs, V = {v1, v2, · · · , vN} and E = ⋃ E (r) ⊆ V ×V represent the nodes set and the edges set of the multiplex graph, respectively, X = {xi}Ni=1 ∈ RN×F denotes the node feature matrix, where xi ∈ RF is the feature of the node vi out of N nodes, and denote the set of structural information as A = {A(1) , . . . ,A(R) }, where A(r) ∈ {0, 1}N×N is the adjacency matrix of the network G (r) , and a(r) ij = 1 if (vi, vj ) ∈ E (r) . The goal of MGRL is to obtain fused discriminative node representations H ∈ RN×d with node features and multiple graph structures, where d ≪ F is the dimension of the representation space.

3.1 Motivation

Previous MGRL methods usually adopt the graph structure learning in traditional GRL methods to optimize the graph structure by directly utilizing similarity between node features, thus improving the performance of the model. However, they usually neglect to capture the globally positive and negative relationships among nodes, resulting in sub-optimal model performance. Taking a movie multiplex graph dataset containing co-director relationship and co-actor relationship as an example. Different classes of movies can be connected by common actors and directors, but the edges between different classes of movies are not conducive for representation learning. However, the method based on the similarity of node features is only able to find the edges between movies of the same classes but not able to eliminate the edges between movies of different classes. As a result, node information propagation between two nodes from different classes may reduce node discriminability.

Furthermore, previous work usually uses a node classification task to optimize both graph structure learning and representation learning parameters, and the update of the graph structure receives supervision from the node classification task, resulting in uneven training of the graph structure. Take a training scenario with a two-layer GCN as an example, node information can only be propagated for a range of two hops. If there are no labeled nodes within two hops of an unlabeled node, the edges around the unlabeled node will lack supervision information. As a result, the updated graph structures are more inclined to fit the training set data, leading to edge starvation problem.

To address these issues, our proposed MGBO captures the globally positive and negative relationships among nodes through a self-expression matrix.

In addition, we use bi-level optimization to solve the edge starvation problem. We show the framework of the proposed method in Figure 1 and introduce the details as follows.

3.2 Self-Expression Learning

As mentioned above, previous MGRL works usually capture the relationships among nodes with the node feature similarity to mitigate the graph structure reliability assumption, as the correlation information among node features has been shown to provide complementarity to the graph structure [Yuan et al., 2021]. However, directly utilizing the similarity graph fails to capture negative relationships between two nodes because the similarity between nodes is always non-negative. Moreover, the similarity graph is usually derived by calculating the similarity between every node and its neighbors and cannot capture the global relationships among nodes. As a result, previous MGRL methods may lose discriminative information that captures the intrinsic structure of the data [Tenenbaum et al., 2000]. To solve these issues, in this paper, we utilize the self-expression property among node features to adaptively capture globally positive and negative relationships among nodes.

To do this, given the node feature matrix X, we initialize the similarity graph by the K-Nearest Neighbor (KNN) algorithm [Wu et al., 2020]. Specifically, we first obtain the feature similarity matrix M between each node pair by calculating the distance among all node pairs, i.e.,

where xi and xj are node features of vi and vi. Then we select k nodes with the highest similarity to each node as their neighbors in the distance matrix M, and thus obtaining the initial feature similarity graph C.

To further capture the negative relationships among nodes with different labels and the positive relationships among nodes with the same label, we propose to optimize the similarity graph with the self-expression property of node features. Specifically, the self-expression property assumes that each data point can be linearly reconstructed from a weighted combination of all data points. More formally, given features X = {x1, . . . , xN} of the nodes set V, for any vj ∈ V, there exists a coefficient cij ∈ R such that:

where cij is the self-expression coefficient corresponding to vi for reconstructing vj from all other nodes. As a result, each node can be represented as linear combinations of all other nodes with positive or negative coefficients.

Therefore, we propose to optimize the similarity graph to capture globally positive and negative relationships among nodes with the self-expression property, i.e.,

As a result, Eq. (3) enforces the self-expression matrix to describe each node by all nodes.

However, the self-expression matrix may easily obtain the trivial solution, i.e., the identity matrix. Therefore, we further consider two regularization terms in the above objective function to avoid the trivial solution, i.e.,

where α and β(r) are two non-negative parameter to balance the second term and the third term. In Eq. (4), the second term aims to regularize the sparsity of the self-expression matrix, while the third term aims to optimize the self-expression matrix with the guidance of graph structures to avoid the trivial solution. After that, we let C = (C+C⊤)/2 to ensure that the learned self-expression matrix is symmetric.

In this way, each element of the self-expression matrix is not constrained to be non-negative, thus adaptively capturing positive and negative relationships between two nodes. Moreover, the self-expression matrix indeed relies on all data points to describe each node, unlike previous MGRL works that only calculate the similarity between the node and its nearby nodes. As a result, the self-expression matrix also captures the global relationships of the nodes.

3.3 Graph Fusion

In the multiplex graph, an edge may connect two nodes from different classes and two nodes in the same class may not be connected. To solve these issues, in this section, we propose to fuse the graph structure with the self-expression matrix in our method. We expect to use the positive relationship among two nodes to connect two nodes in the same class and use the negative relationship among two nodes to disconnect two nodes from different classes.

To do this, we first fuse all graph structures in the multiplex graph. A simple approach would be to use the average pooling to aggregate information from different graph structures. However, such an approach is counter-intuitive because different graph structures represent different relationships among nodes, thus the importance of different graph structures is different. Therefore, we utilize the attention mechanism to learn the weights of different graph structures and perform aggregation.

Specifically, given multiple graph structures A = {A(1) , . . . ,A(R) }, we obtain the fused graph structure Atopology with the graph-level attention mechanism, i.e.,

where [A(1) ,A(2) , . . . ,A(R) ] is the stacking matrix of all graph structures. Ψ1 denotes a channel attention layer whose weight matrix WΨ1 ∈ R1×1×R indicates the importance of different graph structures.

After the attention mechanism, we further employ an attention layer to fuse the graph structure Atopology and the self-expression matrix C by:

where [Atopology,C] is a stacked matrix fused the graph structure with the self-expression matrix. Ψ2 is the channel attention layer whose weight matrix WΨ1 ∈ R1×1×2 indicates the importance of fused graph structure and selfexpression matrix. Therefore, we obtain the aggregated graph S and further let S = (S + S⊤)/2 to ensure that the aggregated graph is symmetric.

3.4 Representation Learning

Given the node feature matrix X and the aggregated graph S, we employ the graph convolutional layer g : RN×F × RN×N → RN×d to obtain node representations H by:

where σ is the activation function, and Θ is the weight matrix of the encoder g. ̂S = ˆD-1/2 (S+wIN) ˆD-1/2 ∈ RN×N is the symmetrically normalized graph structure of aggregated graph, ˆD is the degree matrix of S+wIN , and w is the weight of identity matrix IN.

In Eq. (7), H aggregates neighbors information from original topology and node features space with S. Given the node representations H, we further train our model by minimizing the cross-entropy loss between true and predicted labels. To do this, we employ a fully connected layer to obtain the predicted class based on the node representation H, i.e.,

whereW indicates the parameter of the fully connected layer, and ˆY is the class of nodes predicted by the classifier. Therefore, the cross-entropy loss can be formulated as:

where YL is the set of node indices with labels, Yl and ˆYl are the labels and prediction class of labeled nodes. As a result, the label information is adopted to guide the training process with the cross-entropy loss so that meaningful node representations H can be learned.

Based on the optimized node representations H, we consider replacing the original node features in Eq. (4) with the learned H. The reason can be attributed as follows. On the one hand, the noise or redundancy in the original node features may make it difficult for the self-expression matrix to capture the positive and negative relationships among nodes accurately [Lin et al., 2024]. On the other hand, the original node features lack sufficient discriminability, which affects the quality of the self-expression matrix. As a result, with the optimized node representations H, the self-expression learning module can be designed in a dynamically optimized mode, and Eq. (4) can be reformulated as:

Therefore, the self-expression matrix C can be optimized by minimizing LGL based on the learned node representation H.

3.5 Bi-level Optimization

With the graph structure learning in Section 3.2 and the representation learning in Section 3.4, previous MGRL works generally optimize the parameters of them jointly. As a result, these methods may lead to the edge starvation problem, as the representation learning of edges far from the labeled nodes cannot be supervised by the node classification task, while the representation learning of edges close to the labeled nodes are supervised. The resulting learned graph structure tends to fit the data of labeled nodes (i.e., the training set), leading to poor generalization to unlabeled nodes.

To address the above issues, the proposed method considers optimizing the parameters of graph structure learning and the parameters of representation learning through a bi-level manner, which has been widely used in meta-learning and model selection [Franceschi et al., 2018].

To do this, we formulate the representation learning and the self-expression learning, respectively, as an outer optimization task and an inner optimization task. Specifically, denoting the parameters as θgcn and θc, respectively, the outer optimization and the inner optimization can be optimized by the following objective functions, i.e.,

where Γout aims to optimize parameters of the representation learning module and Γin aims to optimize the parameters of the self-expression learning module. Particularly, the above objective functions can be formulated as the following bilevel optimization problem, i.e.,

For the above bi-level optimization, existing literature [Liu et al., 2021] usually first unrolls the inner optimization dynamics T steps, and then compute the hypergradient (outer gradient) from the unrolled dynamics. In this paper, we conduct the inner optimization process by the stochastic gradient

where ψt denotes the update scheme at the t-th step of the inner optimization process, T denotes the total number of iterations of the inner optimization, and ηt is the learning rate for the inner optimization. After T steps, we can formulate the inner parameters as:

where ◦ denotes the composite dynamics operation for the entire iteration. Therefore, the outer optimization is:

Based on Eq. (15), to update the outer parameters (i.e., θgcn), we need to compute the hypergradient ∇θgcn Γout(θgcn, θT c ). Recalling that θtc = ψt (θt-1 c ; θgcn ), the operation ψt is obviously dependent on θgcn directly. Moreover, the operation ψt is dependent on θgcn indirectly through θt-1 c , which is updated based on θgcn. Thus, the hypergradient of Eq. (15) can be computed by the chain rule, i.e.,

In Eq. (16), the first term indicates the direct gradient, which can be obtained directly. The second term indicates the indirect gradient, which is difficult to obtain by direct computation, especially the parameter Jacobian ∂θT c ∂θgcn . To address this issue, we further expand it as:

Obviously, Eq. (17) can be solved by the superposition of the gradients of T rounds.

By optimizing Eq. (13) and Eq. (15), the bi-level optimization considers the graph structure learning and the representation learning, respectively, as the inner optimization and the outer optimization. Moreover, the graph structure learning module is only optimized by the self-expression property at the inner optimization instead of the node classification task at the outer optimization. As a result, the graph structure module avoids the overfitting issue for labelled nodes and the underfitting issue for unlabeled nodes. Therefore, the proposed method avoids the generation of starved edges to effectively solve the edge starvation problem. This improves the generalization of the model over unlabeled nodes.

4 Experiments

In this section, we conduct extensive experiments on 4 public benchmark datasets to evaluate effectiveness of the proposed method, compared to 9 comparison methods, on the node classification task.

4.1 Experimental Setup

Datasets

The used datasets include 2 citation multiplex graph datasets, i.e., ACM [Jin et al., 2021] and DBLP [Jin et al., 2021], and two movie multiplex graph datasets, i.e., IMDB [Jin et al., 2021] and Freebase [Mo et al., 2023a].

Comparison Methods

The comparison methods include 2 single-view graph methods and 7 multiplex graph methods. Single-view graph methods include 2 baseline methods, i.e., GCN [Kipf and Welling, 2017] and GAT [Velickovic et al., 2018]. Multiplex graph methods include HAN [Wang et al., 2019], GTN [Yun et al., 2019], MAGNN [Fu et al., 2020], MAGNN-AC [Jin et al., 2021], HGSL [Zhao et al., 2021], MGDCR[Mo et al., 2023a], and MHGCN [Yu et al., 2022]). For single-view graph methods, we follow previous works [Wang et al., 2019] to separately learn the representations for every graph and report the best performance.

4.2 Effectiveness Analysis

We evaluate the effectiveness of the proposed method on the node classification task by reporting the results (i.e., MacroF1, and Micro-F1) of all methods on four datasets in Table 1. Obviously, our method achieves the best effectiveness on the node classification task.

First, our method performs substantially better than the single-view graph methods (i.e., GCN and GAT). For example, our MGBO outperforms the best single-view graph method (i.e., GAT) by an average of 6.2%, in terms of MacroF1 and Micro-F1, on all datasets. This validates the superiority of multiplex graph methods as they can efficiently capture the complex relationships among multiple graphs.

Second, the proposed method achieves the best performance among all MGRL methods, followed by MHGCN, MGDCR, HGSL, MAGNN-AC, MAGNN, GTN, and HAN. For example, the proposed method achieves 0.5% average improvement, compared to the best performing semi-supervised method (i.e., MHGCN), in terms of Macro-F1 and Micro-F1, on all datasets. This suggests that the correlations learned from node features by the proposed method can provide complementary information to graph structures and help to learn distinguishable node representations.

Third, the proposed method outperforms previous MGRL method that utilizes the graph structure learning (i.e., HGSL) by an average of 1.3%, in terms of Macro-F1 and Micro-F1, on all datasets. The reason can be attributed to the fact that the proposed method effectively captures the globally positive and negative relationships among nodes through the selfexpression matrix as well as solves the edge starvation problem with bi-level optimization.

4.3 Ablation Study

The proposed method utilizes cross-entropy loss (i.e., LCE) and graph structure loss (i.e., LGL) to optimize the node representation and self-expression matrix. Moreover, MGBO further addresses edge starvation problem through bi-level optimization. To demonstrate the effectiveness of different parts of the proposed framework, we investigate the classification performance of different combinations of these components in the model on all datasets and report the results in Table 2 . In addition, we also investigate if the self-expression matrix captures the globally positive and negative relationships in Figure 2 and if the bi-level optimization explores the edge starvation problem in Figure 3.

Effectiveness of Self-Expression Matrix

To verify the effectiveness of the self-expression matrix, we investigate the performance of the variant method with/without the graph structure loss (i.e., LGL) on all datasets and report the results in Table 2. Obviously, the variant method with the LGL achieves superior performance and obtains an average improvement of 2.1%, compared to the method without LGL. This indicates that the globally positive and negative relationships of nodes learned from the selfexpression matrix can indeed provide complementary information about the graph structure and contribute to the learning of discriminative node representations.

Effectiveness for Self-Expression Matrix To Capture the Globally Positive and Negative Relationships

Intuitively, in the self-expression matrix, the edges with positive values indicate that the connected nodes may be from same class, while the edges with negative values indicate that the connected nodes may be from different classes. To verify that the self-expression matrix indeed captures the globally Datasets positive and negative relationships among nodes, we calculate the ratio of node pairs belonging to the same/different classes in edges with positive/negative values in the self-expression matrix and reported results on all datasets in Figure 2. Obviously, the globally positive and negative relationships among nodes can be captured using the self-expression matrix, and the ratios can continue to increase as the bi-level optimization proceeds. This verifies the effectiveness of the selfexpression matrix as well as the bi-level optimization.

Figure 3: Classification performance (i.e., Micro-F1) of variants with/without bi-level optimization on nodes with starved edges.

Effectiveness of the Bi-Level Optimization To Solve the Edge Starvation Problems

To verify that the bi-level optimization indeed solves the edge starvation problems, we first filter out nodes that were not connected to any labeled nodes, and the edges around these nodes were starved edges that lacked supervision information. We then test the performance of the variant methods with/without bi-level optimization (i.e., MGBO and MGBO- N) on these nodes on all datasets and report the results in figure 3. As a result, the method with bi-level optimization is significantly better than the method without it, achieving an average improvement of 2.5%. This indicates that the bilevel optimization is effective in mitigating the edge starvation problems, thus improving the model's performance.

5 Conclusion

In this paper, we proposed a multiplex graph representation learning framework based on bi-level optimization. Specifically, we proposed to capture the globally positive and negative relationships among nodes by learning the selfexpression matrix based on node features. In addition, we updated the parameters of the self-expression learning and the parameters of the representation learning separately through bi-level optimization, which effectively solves the edge starvation problem. Extensive experimental results show that the method consistently achieves state-of-the-art performance on the node classification task.

Acknowledgements

This work was supported in part by the National Key Research & Development Program of China under Grant 2022YFA1004100, Guangxi Natural Science Foundation (2023GXNSFBA026010), Research Fund of Guangxi Key Lab of Multi-source Information Mining & Security (22-A03-02), Innovation Project of Guangxi Graduate Education (XJCY2022009).