Multi-Label Graph Convolutional Network Representation Learning

Multi-label learning is a classical research problem in the machine learning community with applications ranging from document classification and gene function prediction to automatic image annotation [16]. In a multi-label learning task, each instance is associated with multiple labels represented by a sparse label vector. The objective is to learn a classifier that can automatically assign an instance with the most relevant subset of labels [8]. Techniques for multi-label classification learning can be broadly divided into two categories [17]: the problem transformation-based and the algorithm adaption-based. The former class of methods generally transforms the multi-label classification task into a series of binary classification problems [6, 18] while adaption-based methods try to generalize some popular learning algorithms to enable a multi-label learning setting [19, 20].

Multi-label learning methods for graph-based data did not attract much attention in the past. DeepWalk [21] was proposed to learn graph representations that are then used for training a multi-label classifier. However, DeepWalk only exploits graph structures, with valuable label and label correlation information not preserved in learned node embeddings. Wang et al. [4] and Huang et al. [14] proposed to leverage labeling information along with graph structures for enriched representation learning. However, these methods either consider simplex-label graphs or treat multiple labels as plain attribute genes to support graph structure modeling. Such paradigms still neglect frequent label correlations and dependencies which are demonstrably helpful properties in multi-label learning problems [9, 10].

Graph representation learning [1, 22] seeks to learn low-dimensional vector representations of a given network, such that various downstream analytic tasks like link prediction and node classification can be benefited. Traditional methods in this area are generally developed based on shallow neural models, such as DeepWalk[21], Node2vec[23] and LINE[24]. To preserve the node neighborhood relationships, they typically perform truncated random walk over the whole graph to generate a collection of fixed-length node sequences, where nodes within the same sequences are assumed to have semantic connections and will be mapped to be close in the learned embedding space. However, above methods only consider modeling the edge links to constrain node relations, which may be insufficient especially when the network structures are very sparse. To mitigate this issue, many methods [3, 25] are proposed to additionally embed the rich network contents or features associated such as the user profiles in a social network and the publication descriptions in a citation network. For example, TriDNR [26] was proposed to learn simultaneously from the network structures and textual contents, where structures and texts are mutually boosted to collectively constrain the similarities between learned node representations. In general, most real-word graphs are sparse in connectivity (e.g., each node only connects several others in the huge node space), while node contents or features can be leveraged to either enhance node relevance or repair the missing links in the original network structures [27].

However, above representation learning methods belong to the class of shallow neural models, which may have limitations in learning complex relational patterns between graph nodes. Recently, there is growing interest in adapting deep neural networks to handle the non-Euclidean graph data [12, 28]. Several works seek to apply the concepts of convolutional neural networks to process arbitrary graph structures [15, 24], with GCN [15] achieving state-of-the-art representation learning and node classification performance on a number of benchmark graph datasets. Following this success, Yao el al. [29] proposed a Text GCN for document embedding and text classification based on a constructed heterogeneous word-document graph. Graph Attention Networks (GAN) [12] are another recently proposed end-to-end neural network structure similar to GCNs, which introduce attention mechanisms that assign larger weights to the more important nodes, walks, or models. Inspired by these deep neural models targeted at mostly the simplex-label graphs, we generalize GCN and propose a novel training framework, ML-GCN, to address the multi-label graph learning problem in this paper.

A multi-label graph is represented as $G=(\mathbf{v},\mathbf{e},\mathbf{l},\mathbf{A},\mathbf{B},\mathbf{X})$, where $\mathbf{v}=\{v_{i}\}_{i=1,\cdots,n}$ is a set of unique nodes, $\mathbf{e}=\{e_{i,j}\}_{{i,j}=1,\cdots,n;~{}i\neq j}$ is a set of edges and $\mathbf{l}=\{c_{r}\}_{r=1,\cdots,m}$ is a set of unique labels, respectively. $n$ is the total number of nodes in the graph and $m$ is the total number of labels in the labeling space. $\mathbf{A}$ is a $n\times n$ adjacency matrix with $\mathbf{A}_{i,j}=w_{i,j}>0$ if $e_{i,j}\in\mathbf{e}$ and $\mathbf{A}_{i,j}=0$ if $e_{i,j}\notin\mathbf{e}$. $\mathbf{B}$ is a $n\times m$ affiliation matrix of labels with $\mathbf{B}_{i,r}=1$ if $v_{i}$ has label $c_{r}\in\mathbf{l}$ or otherwise $\mathbf{B}_{i,r}=0$. Finally, $\mathbf{X}\in\mathbb{R}^{n\times d_{i}}$ is a matrix containing all $n$ nodes with their features, $i.e.$, $\mathbf{X}_{i}\in\mathbb{R}^{d_{i}}$ represents the feature vector of node $v_{i}$, where $d_{i}$ is the feature vector’s dimension.

In this paper, the multi-label graph learning aims to represent nodes of graph $G$ in a new $m$-dimensional feature space $\mathcal{H}^{m}$, embedding information of graph structures, features, labels and label correlations preserved, i.e., learning a mapping $f:G\rightarrow\{\mathbf{h}_{i}\}_{i=1,\cdots,n}$ such that $\mathbf{h}_{i}\in\mathcal{H}^{m}$ can be used to accurately infer labels associated with node $v_{i}$.

GCN [22] is a general class of convolutional neural networks that operate directly on graphs for node representation learning and classification by encoding both the graph structures and node features. In this paper, we focus on the spectral-based GCN [16], which assumes that neighborhood nodes tend to have identical labels guaranteed by each node gathers features from all neighbors to form its representation. Given a network $G=(\mathbf{v},\mathbf{e},\mathbf{X})$, which has $n$ nodes and each node has a set of $d_{i}$-dimensional features ($\mathbf{X}\in\mathbb{R}^{n\times{d_{i}}}$ denotes the feature vector matrix of all nodes), GCN takes this graph as input and obtains the new low-dimensional vector representations of all nodes though a convolutional learning process. More specifically, with one convolutional layer, GCN is able to preserve the 1-hop neighborhood relationships between nodes, where each node will be represented as a $m-$dimension vector. The output feature matrix for all nodes $\mathbf{X}^{(1)}\in\mathbb{R}^{n\times m}$ can be computed by:

where $\tilde{\mathbf{A}}=\mathbf{D}^{-\frac{1}{2}}(\mathbf{I}+\mathbf{A})\mathbf{D}^{-\frac{1}{2}}$ is the normalized symmetric adjacency matrix. $\mathbf{D}$ is the degree matrix of $(\mathbf{I}+\mathbf{A})$ and $\mathbf{I}$ is an identity matrix with corresponding shape. $\mathbf{X}^{(0)}\in\mathbb{R}^{n\times d_{i}}$ is the input feature matrix (e.g., $\mathbf{X}^{(0)}=\mathbf{X}$ ) for GCN and $\mathbf{W}_{0}\in\mathbb{R}^{d_{i}\times m}$ is a weight matrix for the first convolutional layer. $\rho$ is an activation function such as the ReLU represented by $\rho(x)=\max(0,x)$. If it is necessary to encode $k$-hop neighborhood relationships, one can easily stack multiple GCN layers, where the output node features of the $j$th (1 $\leq$ $j$ $\leq$ $k$) layer is calculated by:

where $\mathbf{W}_{j}\in\mathbb{R}^{d_{h}\times d_{h}}$ is the weight matrix for the $j$th layer and $d_{h}$ is the feature vector dimension output in the hidden convolutional layer.

As discussed in previous sections, the key and challenge for multi-label graph learning are to simultaneously learn from the graph structures, features, labels and label correlations, where different aspects of learning could enhance each other to achieve a global good network representation. To support the incorporation of labels, we can simply build a heterogeneous node-label graph similar to the text GCN [29], where common nodes and label nodes are directly connected by their labeling relationships. However, such a diagram makes it hard to model the higher-order label correlations since labels must reach each other through common nodes, i.e., one cannot directly encode $k$-hop neighborhood node relations and label correlations by a GCN with $k$ convolutional layers. To enable immediate and flexible label interactions, we consider a stratified graph structure shown in Fig. 2(a), which is defined as follows:

Such a construction of the layered multi-label graph in Fig. 2(a) could bring three main favorable properties. First, the label-label connectivity allows direct and efficient higher-order label interactions by simply adjusting the number of convolutional layers in GCN. In addition, common nodes as attributes of the label nodes enable to encode graph community information in learned label representations, as nodes with identical labels tend to form a cluster or community. Lastly, the learned node representations can naturally preserve labels, label correlations and graph community information by taking label nodes as attributes of the node-node graph.

Fig. 2(b) shows the proposed ML-GCN model that contains two Siamese GCNs to simultaneously learn the label and node representations from the given multi-label graph, where input feature vectors of both the attributed label and common nodes will be regularly updated during the training. First, the high-layer GCN learns label representations from the label-label-node graph through supervised single-label classification. Let $\mathbf{Y}\in\mathbb{R}^{m\times d_{i}}$ be the input feature matrix of all $m$ label nodes, $\mathbf{C}$ be the $m\times m$ adjacency matrix recording the co-occurrence relations between label nodes, and $\mathbf{F}$ be the $(n+m)\times(n+m)$ adjacency matrix of the input label-label-node graph. The first convolutional layer aggregates information from both the neighborhood label nodes and the associated common nodes (e.g., label node L1 in Fig. 2(a)), where the new $m$-dimensional label node feature matrix $\mathbf{L}^{(1)}\in\mathbb{R}^{n\times m}$ is computed by:

where $\rho$ is an activation function, such as the ReLU represented by $\rho(x)=\max(0,x)$, $\mathbf{W}_{0}^{l}\in\mathbb{R}^{d_{i}\times m}$ is a weight matrix for the first label-label-node GCN layer and $\mathbf{Y}^{*}=[\mathbf{Y};\mathbf{X}]^{T}$ is a vertically stacked $(m+n)\times d_{i}$ feature matrix. $\tilde{\mathbf{F}}^{*}$ is a truncated normalized symmetric adjacency matrix obtained by:

where $\mathbf{I}_{m+n}$ is the identity matrix, $\mathbf{D}_{f}$ is the degree matrix with $\mathbf{D}_{f,ii}=\sum_{j}\mathbf{F}^{*}_{ij}$. One layer GCN only incorporates immediate label node neighbors. When higher order label correlations need to be preserved, we can easily stack multiple GCN layers (e.g., the layer number $k\geq 2$) by:

where $\tilde{\mathbf{C}}=\mathbf{D}_{c}^{-\frac{1}{2}}(\mathbf{C}+\mathbf{I}_{m})\mathbf{D}_{c}^{-\frac{1}{2}}$ is the normalized symmetric adjacency matrix and $\mathbf{D}_{c,ii}=\sum_{j}(\mathbf{C}+\mathbf{I}_{m})_{ij}$. The last layer output label embeddings have the same size as the total number of labels, $m$, and are through a softmax classifier to perform the single-label classification (e.g., assume we consider a two-layer GCN) by:

where $\mathbf{W}_{0}^{l}\in\mathbb{R}^{d_{i}\times d_{h}}$ and $\mathbf{W}_{1}^{l}\in\mathbb{R}^{d_{h}\times m}$ are the weight matrices for the first and second label-label-node GCN layers, respectively. Let $\mathbf{Y}^{l}$ be the one-hot label indicator matrix of all label nodes, the classification loss can be defined as the cross-entropy error computed by:

Then, the low-layer GCN learns node representations from the node-node-label graph. Similarly, in the first layer each convolution node aggregates information from both the neighborhood common nodes and the associated attributed label nodes (e.g., take node V2 in Fig. 2(a) as an example). Let $\mathbf{E}$ be the $(n+m)\times(n+m)$ adjacency matrix of the input node-node-label graph, the $d_{o}$-dimensional node embeddings output by the first GCN layer are computed as:

where $\mathbf{W}^{v}_{0}\in\mathbb{R}^{d_{i}\times m}$ is a weight matrix for the first node-node-label GCN layer, $\mathbf{X}^{*}=[\mathbf{X};\mathbf{Y}]^{T}$ and $\tilde{\mathbf{E}}^{*}$ is a truncated normalized symmetric adjacency matrix obtained by:

where $\mathbf{D}_{e}$ is the degree matrix with $\mathbf{D}_{e,ii}=\sum_{j}\mathbf{E}^{*}_{ij}$. As in the label-label-node graph, we can also incorporate $k$-hop neighborhood information by stacking multiple GCN layers:

where $\tilde{\mathbf{A}}=\mathbf{D}_{a}^{-\frac{1}{2}}(\mathbf{A}+\mathbf{I}_{m})\mathbf{D}_{a}^{-\frac{1}{2}}$ and $\mathbf{D}_{a,ii}=\sum_{j}(\mathbf{A}+\mathbf{I}_{n})_{ij}$. The node embeddings output by the last layer have size $m$ and are passed through a sigmoid transformation to perform supervised multi-label classification with the collective cross-entropy loss (e.g., the two-layer GCN are used in this paper) over all labeled nodes computed by:

where $\mathbf{W}^{v}_{0}\in\mathbb{R}^{d_{i}\times d_{h}}$ and $\mathbf{W}^{v}_{1}\in\mathbb{R}^{d_{h}\times m}$ are the weight matrices for the first and second node-node-label GCN layers, respectively, $\mathbf{y}$ is the set of node indices that have labels. Let $\mathbf{Y}^{v}$ be the one-hot label indicator matrix of all common nodes, then $\mathcal{L}_{2}^{*}$ is calculated:

The above two aspects of representation learning for labels and nodes are trained together and impact one another by sharing the common classification labeling space of $\mathbf{l}$ from the target graph $G$, and in the meantime a subset of input features, i.e., through the attributed label nodes in the low-level node-node graph and the attributed common nodes in the high-level label-label graph. Let the total training epoch for ML-GCN be $I$, after $N$-epoch training of common node representations, the input feature matrix for the label-label-node graph will be updated:

and in the meantime, after $M$-epoch training of label representations, the input feature matrix for the node-node-label graph will be updated:

where $\mathbf{W}^{v}\in\mathbb{R}^{m\times d_{i}}$ and $\mathbf{W}^{l}\in\mathbb{R}^{m\times d_{i}}$ are weight matrices. The collective training procedure for the ML-GCN model has been summarized in Algorithm 1.

As can be seen from Algorithm 1, the node representations and label representations are not learned independently, but depend on each other through shared embedding features learned from two reciprocally enhanced GCNs. In addition, the two level GCNs conduct two supervised classification tasks within the same labelling space: the top label-label-node GCN is doing a single-label classification and the bottom node-node-label GCN is doing a multi-label node classification. Finally, The global learning objective is to minimize the following collective classification loss:

In this paper, all weight parameters are optimized using gradient descent as in [15] and [29].

The training of ML-GCN is efficient in terms of the computational complexity. In this paper, we adopt a two-layer GCN and one-layer GCN for learning the node and feature representations, respectively. Since multiplication of the adjacency matrix (e.g., $\mathbf{A}$ for the node-node graph and $\mathbf{F}$ for the label-label graph) and feature matrix (e.g., $\mathbf{Y}^{*}$ and $\mathbf{X}^{*}$ in Eqs. (6) and (12), respectively) can be implemented as a product of a sparse matrix with a dense matrix, the algorithm complexity of ML-GCN can be represented as $O((Ed_{i}d_{h}m+nd_{i})+(Ld_{i}m+md_{i}))$, where $n$ and $m$ are the number of nodes and labels, $E$ and $L$ are the number of edges in node-node-label graph and label-label-node graph, respectively. $d_{i}$ is the dimension (for both nodes and labels) of input feature vectors. $d_{h}$ is dimension of the hidden feature vectors produced in the first node-node-label GCN layer of all common nodes. In addition, because for most networks $m$, $L$ and $n$ are generally far more less than $E$ (e.g., as we will see in section V, for the Filckr dataset, $E$ is 4,332,620, compared with $m$, $L$ and $n$ are merely 194, 3,716 and 8,052, respectively), therefore the complexity of ML-GCN is approximately equivalent to $O(Ed_{i}d_{h}m)$, which is the same as GCN. Meanwhile, since Eqs. (15) and (16) are not computed in each epoch (e.g., every 50 epoch), the complexity for our model is still $O(Ed_{i}d_{h}m)$, the same theoretical asymptotic complexity as the GCN.

We collect three multi-label networks [13, 21], BlogCatalog, Flickr, and YouTube, as the benchmark. They are described as follows.

BlogCatalog is a network of social relationships among 10,312 blogger authors (nodes), where the node labels represent bloggers’ interests such as Education, Food and Health. There are 39 unique labels in total and each node may be associated with one or multiple labels. It is easy to find that users’ labels of interest often interact and correlate with each other to enhance the affinities between blogger authors. For example, food is highly related with Health in real life, where two users have both labels food and life should be much closer compared with those whom only share either label food or label life. There are 615 co-occurrence relationships (e.g., correlations) among all 39 labels in this dataset.

Flickr is a photo-sharing network between users, where node labels represent user interests, such as Landscapes and Travel. There are 8,052 users and 4,332,620 interactions (e.g., edges) among them. Each user could have one or multiple labels of interest from the same labeling space of 194 labels in total.

YouTube is a social network formed by video-sharing behaviors, where labels represent the interest groups of users who enjoy common video genres such as anime and wrestling. Table I summaries their detailed statistic information. There are 22,693 users and 192,722 links between them. Each pair of linked users may share multiple identical labels out of the total 47 labels. The number of correlations between these labels is 1,079.

The detailed statistic information of the above three multi-label networks are summarized in Table 1.

We compare the performance of the proposed method with the following state-of-the-art methods for multi-label node classification:

• •

  DeepWalk [21] is a shallow network embedding model that only preserves the topology structures. It captures the node neighborhood relations based on random walks and then derives node representations based on SkipGram model.

• •

  LINE [30] is also a structure preserving method. It optimizes a carefully designed objective function that preserves both the local and global network structures, compared with the DeepWalk that encodes only the local structures.

• •

  Node2vec [23] adopts a more flexible neighborhood sampling process than DeepWalk to capture the node relations. The biased random walk of Node2vec can capture second-order and high-order node proximity for representation learning.

• •

  GENE [13] is a network embedding method that simultaneously preserves the topology structures and label information. Different from the proposed approach in this paper, GENE simply models labels as plain attributes to enhance structure-based representation learning process, whereas our model considers multi-label correlation and network structure for representation learning.

• •

  GCN [15] is a state-of-the-art method that can naturally learn node relations from network structures and features, where each node forms its representation by adopting a spectral-based convolutional filter to recursively aggregate features from all its neighborhood nodes.

• •

  Text GCN [29] is built on GCN that aims to embed heterogeneous information network. In this paper, we construct heterogeneous node-label graph, where common nodes and label nodes are directly connected by their labeling relationships.

• •

  ML-GCN_node is a variant of the proposed ML-GCN model that removes attributes of common nodes from the label-label-node graph. Therefore, the community information is not preserved in this method.

• •

  ML-GCN_1n is a variant of the proposed ML-GCN model. The only difference with ML-GCN is that ML-GCN_1n takes only one convolutional layer while learning from the node-node-label graph.

• •

  ML-GCN_2l is a variant of the proposed ML-GCN model, which adopts a two consecutive convolutional layers to learn from the label-label-node graph, compared with one layer in GCN.

• •

  ML-GCN is our proposed multi-label learning approach in this paper. It considers a two-layer graph structure–a high-level label-label-node graph which allows the preservation of label correlations and meanwhile a low-level node-node-label graph that enables the label correlation-enhanced node representation learning.

The above baselines can be roughly separated into three categories based on the types of information (e.g., network structures and labels) and how it is incorporated in the graph embedding models. The first class belongs to methods that only preserve graph structures, including DeepWalk, Node2vec, LINE, GCN (e.g., we use the structure-based identity matrix as the original features of all node). The second class includes GENE and Text GCN that preserve both the graph structures and label information, where the labels are modeled as plain attribute information to enhance structure-based representation learning. The proposed method MG-GCN and its variants (ML-GCN_node, ML-GCN_1n, and ML-GCN_2l) represent the thrid class, which not only preserve structural and label information, but also the correlations between labels.

It is worth noting that we designed three variants of MG-GCN (including ML-GCN_node, ML-GCN_1n, and ML-GCN_2l) to validate its performance under different settings. This allows us to fully observe ML-GCN’s performance and conclude which part is playing major roles for multiple-label GCN learning.

There are many hyper-parameters involved. Some are empirically set [29] while others are selected through sensitivity experiments. For ML-GCN, we use two-layer and one-layer GCNs to learn from the node-node-label graph and the label-label-node graph respectively. We test hidden embedding size, $d_{h}$, between 50 to 500, training ratios, $\alpha$, of supervised labeled instances between 0.025 and 0.2, and updating frequencies $N$ and $M$ from 10 to 100, respectively. We also compare the performance of ML-GCN through differing numbers of GCN convolutional layers (e.g., ML-GCN_1n and ML-GCN_2l). For comparison, we set the learning rate $\eta$ for gradient decent as 0.02, training epoch as 300, dropout probability as 0.5, $L_{2}$ norm regularization weight decay as 0, and the default values of $d_{h}$, $\alpha$, $N$ and $M$ as 400, 0.2, 50 and 50, respectively. After selecting the labeled training instances, the rest is split into two parts: 10% as validation set and 90% for testing set.

It is necessary to mention that all baselines are set to conduct the multi-label node classification (e.g., each node can belong to multiple labels) within the same environmental settings. As metrics used in [21] and [30], we adopt Micro-F1 and Macro-F1 to evaluate the node classification performance, which are defined as follows:

where $\mathbf{l}$ is the set of labels from the target graph G. $TP^{i}$, $FN^{i}$ and $FP^{i}$ denote the number of true positives, false negatives and false positives w.r.t the $i$th label category, respectively. All experiments are repeated 10 times with the average results and their standard deviations reported.

Table II presents the comparative results of all methods with respect to the multi-label classification performance within the same environment settings, where the top three best results have been highlighted. From the table, we have the following four main observations.

• •

  Among all methods that encode only the graph topology structures, the shallow neural networks-based methods (e.g., DeepWalk, LINE and Node2vec) perform poorly with a wide gap compared with deep model GCN over all three datasets, i.e., on BlogCatalog network, the classification performance of GCN improved 30.6% and 70.9% over Node2vec w.r.t Micro-F1 and Macro-F1, respectively. This is because shallow models have limitations in learning complex relational patterns among nodes [1]. For example, although Node2vec relies on a carefully designed random walk process to capture the node neighborhood relationships, it cannot differentiate the affinities between a node and others within the same walk sequence. In comparison, GCN uses a more efficient way to constrain the neighborhood relations between nodes, where each node only interact with its neighbors in each convolution layer. Such a learning paradigm is more accurate to maintain the actual node relevance reflected by the edge links without introducing noise neighborhood relationships as in Node2vec.

• •

  In terms of the performance of methods (GENE and Text GCN) that have incorporated the labels to enhance the structures modeling. GENE is built on DeepWalk to additionally preserve the label information. We can observe that GENE performs slightly better than DeepWalk on both Flickr and YouTube datasets. The reason is that each label is considered as the higher-level summation of a group of similar nodes, thus can be used to supervise and distinguish the neighborhood affinities between nodes within the same random walk sequence. Nevertheless, LINE and Node2vec can perform better than GENE in most cases over three datasets, i.e., the Micro-F1 performance of LINE and Node2vec on BlogCatalog increased 2.0% and 4.6%, respectively. The reason is probably that they have adopted more efficient random walk process to capture node neighborhood relationships. In addition, as we can see from Table II, the label-preserved model, Text GCN, has no advantages compared with the basic GCN model. The reason is probably that the labels are considered as attributes that have not been leveraged in a meaningful manner. In other words, only the labeled nodes have the attribute of labels in the supervised node representation leaning and training, the scattered labels could have become the noisy information to confuse the neighborhood relationships modeling between nodes.

  

  

  

  

  

  

• •

  For deep models that both preserved graph structures, labels and label correlations, we can observe that ML-GCN is consistently superior to the Text GCN in leaning multi-label graphs over all three datasets. The reasons are mainly in three-fold. First, ML-GCN allows immediate and efficient label correlation modeling without depending on common nodes, i.e., labels directly interact with each other over the label-label graph in the proposed model. Second, it is common to use different numbers of convolutional layer (e.g., based on the results observed by comparing ML-GCN and ML-GCN_2l, where the former performs far more better) to learn from the label and node graphs respectively, since the node-node graph is much more complicated than the label-label graph that involves simple label interaction patterns. To obtain a model that best fits the given label and node graphs of different scales, one can easily change the number of layers used by the two-layer graph modelings in ML-GCN independently. But this is hard for Text GCN to coordinate the layer settings that are most suitable to model node relations and label relations simultaneously in the node-label graph. Finally, in the structure design of ML-GCN, each label has preserved the community information by taking all related common nodes as attributes, which make the node relations modeling and the label correlations modeling more dependent on each other to optimize the global network representation learning, i.e., the node representations of one label could refine the node representation learning of another correlated label, as we will demonstrate in the case study later.

• •

  In terms of the performance of different variants for the proposed ML-GCN, we can condlude that Ml-GCN is superior to ML-GCN_node, ML-GCN_1n and ML-GCN_2l, where the possible reasons are given as follows: 1) The comparison between ML-GCN and ML-GCN_node demonstrates that taking the common nodes as attributes of the label-label network is beneficial, where labels could learn more enriched representations (with encoding label correlations and the node communities) to refine the neighborhood feature aggregation for node representation learning in the low-level node-node graph; 2) ML-GCN performs better than ML-GCN_2l, which illustrates a single-layer GCN is appropriate to model the label correlations, since compared with the node-node interactions, the label-label interactions are generally simple and explicit; 3) ML-GCN_2l is poorly performed than ML-GCN, which demonstrates that exploring the high-order neighborhood relationships between nodes is important.

We designed extensive experiments to test the sensitivities of various parameters between a wider range of values, such as the training ratio $\alpha$ of labeled nodes, the feature updating frequencies $N$ and $M$, and the embedding size of the first hidden convolution layer while modeling the node-node-label graph. Fig. 3 shows the impacts of different portions of labeled training instances. In general, for all test models, we can observe that both the Micro-F1 (e.g., Fig. 3(a)) and Macro-F1 (e.g., Fig. 3(b)) performances increase with more labeled training nodes. This is reasonable since all these models adopt a supervised node representation learning and training manner, where the model parameters can be fully trained with larger labeled data [29]. Fig. 4 shows the influence of the input feature-updating frequencies controlled by $N$ and $M$ (e.g., used in Eqs. (15) and (16)). We can see from Fig. 4(a) where the performance changes with $N$ but no clear patterns can be observed in Micro-F1, while Fig. 4(b) shows an deceasing trend with larger values of $N$ in the Macro-F1 scores. In comparison, from Fig. 4(c) and Fig. 4(d) the accuracy first increases then decreases with larger values of $M$ w.r.t. both Micro-F1 and Macro-F1 scores. We also test the impact of node embedding size generated by the first convolutional layer with the trend shown in Fig. 5(a). The accuracy fluctuates before peaking at 400 and 450 w.r.t. Micro-F1 and Macro-F1 results, followed by a sharp decline.

To illustrate how label correlations affect the multi-label graph learning performance, we present the classification results through four related label categories shown in Fig. 6. Fig. 7 presents their correlation matrix, where deeper colors imply higher correlation between two corresponding labels, i.e., L1 and L2 are highly correlated. We can see in Fig. 6 that ML-GCN and GCN perform similarly with respect to the node classification of category L1. However, the accuracy of MC-GCN improved over GCN with respect to categories L2, L3 and L4. It is interesting to note how much these categories improved (e.g., L2 $>$ L3 $>$ L4) is related to how frequently they correlate with label L1 respectively. This phenomenon might be caused by the fact that the L1 has an impact on its correlated labels during training. This also verifies that label interaction is critical for multi-label graph learning, and our proposed ML-GCN model can effectively capture and utilize this property.