Multi-label Node Classification On Graph-Structured Data
Authors: Tianqi Zhao
Thi Ngan Dong
Alan Hanjalic
Megha Khosla
Venue: Accepted by TMLR ()

Abstract: Graph Neural Networks (GNNs) have shown state-of-the-art improvements in node classification tasks on graphs. While these improvements have been largely demonstrated in a multi-class classification scenario, a more general and realistic scenario in which each node could have multiple labels has so far received little attention. The first challenge in conducting focused studies on multi-label node classification is the limited number of publicly available multi-label graph datasets. Therefore, as our first contribution, we collect and release three real-world biological datasets and develop a multi-label graph generator to generate datasets with tunable properties. While high label similarity (high homophily) is usually attributed to the success of GNNs, we argue that a multi-label scenario does not follow the usual semantics of homophily and heterophily so far defined for a multi-class scenario. As our second contribution, we define homophily and Cross-Class Neighborhood Similarity for the multi-label scenario and provide a thorough analyses of the collected $9$ multi-label datasets. Finally, we perform a large-scale comparative study with $8$ methods and $9$ datasets and analyse the performances of the methods to assess the progress made by current state of the art in the multi-label node classification scenario. We release our benchmark at https://github.com/Tianqi-py/MLGNC.

Published in Transactions on Machine Learning Research (09/2023)
Multi-label Node Classification On Graph-Structured Data
Tianqi Zhao
T. T.Zhao-1 I.Zhao-I@tueelt..r @tudelft.nd
Deportment of Intelligent Systems Delft University of Technology
Ngan Thi Dong
dong
L3S Research Center, Hamnover, Germany
Alan Hanjalic
A. HanjjalicStudelff.... ml
Delft University of Technology
Megha Khosla
Khosla Khosla Studelft.nl
Delft University of Technology
Reviewed on OpenReview: https: // openreview. net/ net/forunt forum? id= EDD
Abstract
Graph Neural Networks (GNNs) have shown state-of-the-art improvements in node clas- sification tasks on graphs. While these improvements have been largely demonstrated in multi-class classification scenario, a more general and realistic scenario in which each node could have multiple labels has so far received little attention. The first challenge in conducting focused studies multi-label node classification is the limited number of publicly available multi-label graph datasets. Therefore, as our first contribution, we collect and release three real-world biological datasets and develop a multi-label graph generator to generate datasets with tunable properties. While high label similarity (high homophily) is usually attributed to the success of GNNs, we arguc that a multi-label scenario does not follow the usual semantics of homophily and heterophily scenario. As our second contribution, define homophily and Cross- Class Neighborhood Similarity for the multi-label scenario and provide thorough analyses of the collected 9 muuli-labed datasets. Finally, we perform a large-scale comparative study with 8 methods and 9 datasets and analyse the performances of the methods to assess the progress made by current state of the art in the multi-label node classification scenario. We release our benchmark at https:/ //github. hwmm/TianniipyMMMGG...
far defined for a multi-class
1 Introduction
Most of the existing works on graph node classification deploying Graph Neural Networks (GNNs) focus on a multi-class classification scenario while ignoring a more general and realistic sccnario of multi-label classification, in which each node could have multiple labels. This scenario holds, for example in protein- protein interaction networks, in which each protein is labeled with multiple protein functions associated with different discases, in social networks, where each user may carry multiple interest labels. In this work, we focus on multi-label node classification on graph-structured data with graph neural networks. For the sake of brevity, in what follows we will refer to multi-label node classification on graphs simply as multi-label node classification.
Regarding the approaches to deploying GNNs in multi-label node classification scenario, common practice is to transform the classification problem into multiple binary classification problems, one per label (Zhang

---

Published in Transactions on Machine Learning Research (09/2023)
& Zhou, 2013). In other words, []] binary classifiers are trained, where each classifier j is responsible for predicting the 0/1 association for the corresponding label ég E L. An assumption here, however, is that given the learned feature representations of the nodes, the labels are conditionally independent (Ma et al., 2020). The validity of this assumption cannot be assured in a GNN-based learning approach as GNNs ignore the label correlation among the neighboring nodes and only focus on node feature aggregation during the representation learning step (Jia & Benson, 2020; Ma et al., 2020).
Furthermore, we note that the success of GNNs is widely attributed to feature smoothing over neighborhoods and high label similarity among the neighboring nodes. Graphs with high similarity among labels of neighboring nodes are referred to as having high homophily. Alternatively, in heterophilic graphs, the labels of neighboring nodes usually disagree. Consequently, approaches like H2GCN (Zhu et al., 2020) have been proposed, which claim a high performance on both homophilic and heterophilic node classification datasets. A subtle point here, however, is that a network with nodes characterized by multiple labels does not obey the crisp separation of homophilic and heterophilic charactoristics. As an illustration, consider a friendship network with node labels representing user interests. Each user might share only very small fraction of the interests with his friends, which indicates low homophily in the local neighborhood. Yet her/his interests/labelt could be fully determined by looking at his one-hop neighbors. Therefore, the network is also not heterophilic in the sense that the connected users have similar interests. Consequently, the solutions taking into account higher-order neighborhoods to tackle low homophily might not always perform well in multi-label networks.
The lack of focused studies on multi-label node classification can also be attributed to the scarcity of available benchmark multi-label graph datasets. As example, there is single multi-label classification dataset, namely OGB-PROTEINS in the Open Graph Benchmark (OGB) (Hu et al., 2020). More so, the OGB-PROTEINS dataset has around 90% of the nodes unlabeled in the test set. While the OGB leaderboard reflects benchmarking of a large number of methods on DGB-PROTENT combined with the use of the Area Under the ROC Curve (AUROC) metric leads to overly exaggorated performance scores. In particular, the performance is measured by the average of AUROC scores across the L (L is the total number of labels) binary classification tasks. In such a scenario, the model already achieves very high score if it outputs high probability for the negative class for cach binary classification task.
the lack of labels in the test set
Our Contributions. Our work thoroughly investigates the problem of multi-label node classification with GNNs. Firstly, we analyze various characteristics of multi-label graph-structured datasets, including label distribution, label induced first- and second-order similarities, that influence the performance of the prediction models. We observe that a large number of nodes in the current datasets only have a single label even if the average number of labels per node relatively high. Moreover, for the popular CGBB-PROTEE dataset, around 89.38% of the nodes in the test set and 29.12% of train nodes have no label assigned.
Secondly, to remedy the gap of lack of datasets build a benchmark of multi-label graph-structured datasets with varying structural properties and label-induced similarities. In particular, we curate 3 biological graph datasets using publicly available data. Besides, we develop synthetic multi-label graph generator with lunable properties. The possibility to lune certain characteristics allows us to compare various learning methods rigorously.
Finally, we perform a largo-scale experimental study evaluating 8 methods from various categories for the node classification task over 9 datasets. We observe that simple baselines like DEEPWALK outperform more sophisticated GNNs for several datasets. We present comprehensive analysis of the performance of different methods based on their own and the datasct's 's characteristics.
2 Background and Related Work
2.1 Notations and The Problem Setting.
Notations. Let 9 = (V,8) denote a graph where V = ful, r.. ,,,, the set of vertices, E represents the sot of links/edges among the vertices. We further denote the adjacency matrix of the graph by A E {0, 1)x1 and oij denotes whether there is an edge between v and vy. A())) represents the immediate neighbors of node
2

---

Published in Transactions on Machine Learning Research (09/2023)
in the graph. Furthermore, let X = (x1,-.. .x,) E R and Y= {yi.... .n) E 10,1 represent the feature and label matrices corresponding to the nodes in V. In the feature matrix and label matrix, the i-th row represents the feature/label vector of node i. Let E(i) denote the set of labels that are assigned to node i. Finally, let F correspond to the feature set and L be the set of all labels.
Problem Setting. In this work, we focus on multi-label node classification problem on graph-structured data. In particular, we are given a set of labeled and unlabelled nodes such that each node can have more than one label. We are then interested in predicting labels of unlabelled nodes. We assume that the training nodes are completely labeled. We deal with the transductive setting multi-label node classification problem, where the features and graph structure of the test nodes are present during training.
2.2 Related Work
Multi-label classification, which assigns multiple labels for each instance simultaneously, finds applications in multiple domains ranging from text classification to protein function prediction. In this work we focus on the case when the input data is graph-structured, for example, a protein-protein protein interaction network or a social network. For completeness, we also discuss the related works on using graph neural networks for multi-label classification on non-grapp--strucuured data in Section 2.2.2. Several other paradigms of multi-label classification including extreme multi-label classification (Liu al., 2017; Song et al., 2022; Wang al., 2019), partial multi-label classification (Huynh & Elhamifar, 2020; Jain al., 2017), multi-label classification with weak supervision (Chu et al., 2018; Hu et al., 2019) ( for complete overview the recent survey (Liu et al., 2021)). are out of the scope of the current work.
2.2.1 Multi-label Classification On Graph-structured Data
Recent methods designed for multi-label node classification over graph-structured data can be categorized into four groups utilizing (1) node embedding approaches, (2) convolutional neural networks, (3) graph neural networks, and (4) the combination of label propagation and graph neural networks.
Node representation or embedding approaches (Perozzi et al., 2014; Khosla et al., 2019; Ou et al., 2016) usually generate a lookup table of representations such that similar nodes are embedded closer. The learned representations are used as input features for various downstream prediction modules. While different notions of similaritics are explored by different approaches, prominent class of method is random walk based which defines similarity among nodes by their co-ocourrence frequency in random walks. In this work, specifically use DEEPWALK (Perozzi et al., 2014) as simple baseline that uses uniform random walks to define node similarity.
Other methods like (Shi et al., 2019; Zhou et al., 2021; Song el al., 2021) use convolutional neural nerworks to first extract node representations by aggregating feature information from its local neighborhood. The extracted feature vectors are then fused with label embeddings to generate final node embeddings. Finally, these node embeddings are used as input for the classification model to generate node labels. In this work, we adopt LANC (Zhou et al., 2021) as baseline from this category, as previous works (7hou et al., 2021; Song et al., 2021) have shown its superior performance compared to other commonly used basclines for the multi-label node classification lask.
popularised by graph convolution network (Kipf & Welling, 2016) and its variants compute node representation by recursive aggregation and transformation of feature representations of its neighbors which are then passed to a classification module. Tet (k) be the feature representation of node i at layer k, (i) denote the set of its 1-hop neighbors. The k - th layer of a graph convolutional operation can then be described as
Graph neural Betworks(GNNN
(k) z AGGREGATE ((x(--)) (xft= (x Ii 1)EN)))))))
x (8) = -RANNFORR
Z (k)
For the multi-label node classification, sigmoid layer is employed as the last layer to predict the class probabilities: y + (sigmoid(2)" ()))) where corresponds to the learnable weight matrix in the classification module. GNN models mainly differ in the implementation of the aggregation layer. The simplest model is
3

---

Published in Transactions on Machine Learning Research (09/2023)
the graph convolution network (GCN) (Kipf & Welling, 2016) which employs degree-weighte aggregation over neighborhood features. GAT (Veličkovié et al., 2018) employs several stacked Graph Attention Layers, which allows nodes to attend over their neighborhoods' features. GRAPUSAGE (Hamilton et al., 2017) follows a sample and aggregate approach in which only a random sample of the neighborhood is used for the feature aggregation step. GNNs, general, show better performance on high homophilic graphs in which the connected nodes tend to share the same labels. Recent approaches like H2GCN (Zhu et al., 2020) show improvement on heterophilic graphs (in the multi-class setting). Specifically, it separates the information aggregated from the neighborhood from that of the ego node. Further, it utilizes higher-order neighborhood information to learn informative node representations.
Label propagation with GNNs. Prior to the advent of GNNs label propagation (LPA) algorithiss constituted popular approaches for the task of node classification. Both LPA and GNNs are based on message passing. While GNNs propagate and transform node features, LPA propagates node label information along the edges of the graph to predict the label distribution of the unlabelled nodes. A few recent works (Yang et al., 2021; Wang & Leskovec, 2020) have explored the possibilities of combining LPA and GNNs. (Yang et al., 2021) employs knowledge distillation in which the trained GNN model (teacher model) is distilled into a combination of GNN and parameterized label propagation modulc. GCN-LPA (Wang & Leskovee, 2020) utilizes LPA serves as regularization to assist the GCN in learning proper edge weights that lead to improved classification performance. Different. from our work both of the above works implicitly assume a multi-class setting. Moreover, (Yang et al., 2021) focuses on the interpretable extraction of knowledge from trained GNN and can only discover the patterns learned by the teacher GNN.
2.2.2 Multi-label Classification On Son-Graph-Strucee
Data Using GNNs
There has also been an increasing trend to use graph neural networks to exploit the implicit relations between the data and labels in multi-label classification problems on non-graph data. For example, (Saini et al., 2021) models the problem of extreme classification as that of link prediction in a document-label bipartite graph and uses graph neural networks together with the attention mechanism to learn superior node representations by performing graph convolutions over neighborhoods of various orders. MT-GGN((Shi et al., 2019) generates representations for the images using CNN and extracts label correlation by constructing a label-label graph from the label co-oceurrecee matrix. LaMP(Lanchanth) et al., 2019) treats labels as nodes on a cabel-interactinn graph and computes the hidden representation of each label node conditioned on the input using attention-based neural message passing. Likewise, for the task of multi-label image recognition (Chen et al., 2019) builds a directed graph over the object labels, where each label node is represented by word embeddings of the label, and GCN employed to map this label graph into a set of inter-dependent object classifiers. The above works and many more like (Li et al., 2021; Zong & Sun, 2020; Ma et al., 2021a; Zheng et al., 2022; Shi et al., 2020; Xu et al., 2021; Cheng et al., 2021; Pal et al., 2020) are not part of the current study as they are developed for non-graph structured data.
3 A detailed analysis of existing and new datasets
We commence by analyzing various properties of existing multi-label datasets including label distributions, label similarities, and cross-class neighborhood similarity which could affect the performance of prediction models. In section 3.2 we further curate new real-world biological datasets which to some extent improve the representativeness of multi-label graph datasets. Finally, in Section 4 we propose our synthetic multi-label graph generator to generate multi-label graph datasets with tunable properties. The possibility to control specific influencing properties of the dataset allows us to benchmark various learning methods effectively. We will need the following quantification of label similarity in multi-label datasets.
Label homophily. The performance of GNNs is usually argued in terms of label homophily which quant similarity among the neighboring nodes in the graph. In particular, label homophily is defined in (Zhu et al., 2020) as the fraction of the homophilic edges in the graph, where an edge considered homophilic, if it connects two nodes with the same label. This definition can not be directly used in the multi-label graph datasets, each node can have more than one label and it is rare in the multi-label datasets that the whole
4

---

Published in Transactions on Machine Learning Research (09/2023)
label sets of two connected nodes are the same. Usually, two nodes share part of their labels. We, therefore, propose new metric to measure the label homophily h of the multi-label graph datasets as follows.
Definition 1 Given multi-label groph 9, the label homophily h of g is defined as the average of the Jaccard similarity of the label set of all connected nodes in the graph:
(()
Σ (FJ)EE
(())
Label homophily is a first-order label-induced similarity in that it quantifies the similarity among neighboring nodes based on their label distributions.
Cross-Class, Neighborhood Similarity for Multi-label graphs. Going beyond the label similarity among neighboring nodes, we consider a second order label induced metric which quantifies the similarity among neighborhoods of any two nodes. Ma al. (2021b) introduced Cross-Class Neighborhood Similarity (CCNS) for multi-class graphs. Using CCNS, (Ma et al., 2021b) attributes the improved performance of GNNs to the higher similarity among neighborhood label distributions of nodes of the same class as compared to different classes. We extend their proposed CCNS measure to analyze multi-label datasets. Given two classes с and d', the CCNS score measures the similarity in the label distributions of neighborhoods of nodes belonging to e and d' and defined as follows. One can visualize the CCNS scores between all class pairs C' C' matrix where C' is the total number of classes. Common GNNs are expected to perform better on datasets which higher scores on the diagonal than off-diagonal elements of the corresponding CCNS matrix.
Given a multi-labet graph G and the set of node labels Y for all nodes, we define the multi-label cross-class neighborhood similarity between classes c, C given by
Definition 2
s(c, = DellVel iEV.JEV (((0)1(())
Σ
cos(d, dj),
(1)
where = {(i)} the set of nodes with one of their labels as c. The vector d, E RRC corvesponds to the empirical histogram (over |C| classes) of node i's neighbors' labels, i.e., the th entry of d; corresponds to the nwmber of nodes in (i) that has one of their label as and the function cos(...) measures the cosine similarity and is defined as
d; d; cos(d,, d,) ||d. |||
Note that as a node in a multi-label dataset could belong to multiple classes we exclude the possibility of comparing a node to itself. By introducing a factor of [é(i)] ((()) in the denominator we are able to normalize the contribution of multi-labeled nodes for several class pairs.
3.1 Existing datasets
We start by analyzing the four popular multi-label node classification datasets: (i) BLOGCAT (Tang & Liu, 2009), in which nodes represent bloggers and edges their relationships, the labels denote the social groups a blogger part of, YFLP (Zeng et al., 2019), which nodes correspond to the customer reviews and odges to their friendships with node labels representing the types of busincsscs and (iii) OGB-PROTEINS (Hu et al., 2020), in which nodes represent proteins, and edges indicate different types of biologically meaningful associations between the proteins, such physical interactions, co-expression, or homology (Consortium, 2018; D et al., 2019). The labels correspond to protein functions. (iili) DBLP (Akujuobi et al., 2019), in which nodes represent authors and edges the co-authorship between the authors, and the labels indicate the research areas of the authors.
We report Table 1 the charactoristics of these datascts including the label homophily. In the following, we discuss in detail the various characteristics of these datasets along with their limitations for the effective evaluation of multi-label classification.
5

---

Published in Transactions on Machine Learning Research (09/2023)
Table 1: Dataset statistics. [V] and [8] denote the number of nodes and edges the graph. [F] is the dimension of the node features. clus and Thoma denote the clustering coefficient and the label homophily, C indicates the size of all labels the graph. Emed: Emean and mas specify the median, mean, and max values corresponding the number of labels of node. '25%', '50%', and '75%' corresponds to the 25th, 50th, and 75th percentiles of the sorted list of the number of labels for node. "N.A.' means the corresponding characteristic is not available in the graph.
DATASET
V
[E]
[F]
clus
C lied Emean Loax 25%
50%
75%
BLOGCAT
10K
333K
N.A.
0.46
0.10
39
1.40
11
1
2
YELP
716K
7.34M
300
0.09
0.22
100
9.44
97
6
132K
39M
0.28
0.15
112
12.75
100
5
20
DBLP
28K
68K
300
0.61
0.76
1.18
4
1
Beggsaaing
Ogle-ptttiis
DRLP
100
50
100
Figure 1: Label distributions. BLOGCAT, the majority the nodes have one label. In OGB- CGB-PROTEINS, around 41% of total nodes have no labels, and only three nodes have the maximum number of 100 labels.
Skewed label distributions. Figure illustrates the label distributions in the four datasets. Quantitatively 72.34% nodes in BLOGCAT only have one label. However, the most labeled data points are assigned with 11 labels. YELP has a total of 100 labels, the most labeled data points have 97 labels, whereas over 50% of the nodes have equal or less than labels. Nevertheless, YELP exhibits high multi-label character with 75% of the nodes with more than labels. OGB-PROTEINS is an extreme case which 40.27% of the nodes do not have any label. DBLP is the dataset with the highest portion of nodes with single labels, with the exact. percentage of 85.4%.
Issue in evaluation using AUROC scores under high label sparsity. Another far unreported issue in multi-label datasets is the unlabeled data. In OGB-PROTEINS, 40.27% of nodes do not have labels. Moreover, 89.4% of the test nodes are unlabelled. More worrying is the use of the AUROC score metric in the OGB leaderboard to benchmark methods for multi-label classification. In particular, a model that assigns "No Label" to each node (i.e. predict negative class corresponding to each of the independent L binary classification tasks) will already show high AUROC score. We fact observed that increasing the number of training epochs (which encourage the model to decrease training loss by predicting the negative class) increased the AUROC score whereas other metrics like AP F1 score dropped stayed unchanged.
Cross-class neighborhood similarity. In Figure 2 visualize the cross-class neighborhood similarity matrix for DBLP and BLOGCAT. The cells the diagonal reflect the intra-class neighborhood similarity, whereas the other cells indicate the inter-class neighborhood similarity computed using equation 1. The contrast. in 2a means that nodes from the same class tend to have similar label distribution in their neighborhood, while nodes from different classes have rather different label distributions in their neighborhoods. We will later see in the experimental section that GNNs indoed benefit from this characteristic identify correctly the nodes in the same classes in DBLP. On the contrary, the intra- and inter-class similarity are more similar in BLOGCAT, making intricate for GNNs to classify the nodes to their corresponding classes.

---

Published in Transactions on Machine Learning Research (09/2023)
(a) Cross class Neighborhood Simi--b) Cross class Neighborhood Simi- larity in DBLP
larity in BLOGCAT
Figure 2: Cross class Neighborhood Similarity in real-world datasets
3.2 New biological interaction datasets
Motivated by the natural applicability of the multi-label classification task in various biological datasets and to improve the represcntativeness of available datascts, we collect three real-world biological datasets corresponding to different multi-label classification problems: the PCG dataset for the protein phenotype prediction, the HUMLoc, and EUKLoc datasets for the human and eukaryote protein subcellular location prediction tasks, respectively. On each dataset, we build a graph in which each protein is modeled as a node. The node label the corresponding protein's label. An edge represents known interaction between proteins retrieved from public database. The detailed pre-processing steps and the original data sources are discussed in Appendix A.1.1, A.1.2, and A.1.3. Table presents overview of the three datasets' characteristics.
Table 2: Statisties for new datasets. The column notations are the same as in Table 1.
DATASET
[V]
[
[F]
clus
Thomo
C
Emed
Emean
man
25%
50%
75%
PCG
3K
37k
32
0.34
0.17
15
1
1.93
2
HUMLoC
3.10k
18K
32
0.13
0.42
14
1
1.19
1
1
EuKLoc
7.70K
13K
32
0.14
0.46
22
1
1.15
1
1
While all the existing datasets had very low homophily, HUM- LOC, and EUKLoC show higher homophily. Moreover, these datasets improve the representativeness in terms of varying graph structure (reflected in computed clustering coelficient)) and in node, edge, and feature sizes. On the downside, these datasets also show a similar low multi-label character, with the majority nodes these datasets still having a single label. Among the three datasets, PCG shows a bit more balanced label distribution (see Figure 3) as compared to the other two. Figure provides the cross-class neighborhood similarity scores. All three datasets show different patterns according to CCNS measure which is desirable to analyse the differences in method's performance. While in PCG we see an overall high scores for CCNS, the difference in inter- and intra- class similarities is not prominent. HUMLoC shows slightly more contrasting intra- and inter-class neighborhood similarity. EUkLoc, on the other hand, show very small neighborhood label similarities for nodes of same or different. classes.
PCG
HumLoc
EukLoc
Label count per nade
Figure 3: Label distributions in biological datasets. The majority of the nodes in all datasets have one label.

---

Published in Transactions on Machine Learning Research (09/2023)
(a) Cross class Neighborhood Simi- larity in PCG
(b) Cross class Neighborhood Simi- larity in HUMLoc
(c) Cross class Neighborhood Simi- larity in EukLoc
Figure 4: Cross class Neighborhood Similarity in real-world datasets and proposed biological datasets
4 Multi-label Graph Generator Framework
In the previous sections, we analyzed various real-world dataset properties which could influence method's performance. We now develop multi-label graph generator that will allow to build datasets with tunable properties for holistic evaluation. With our proposed framework we can build datasets with high multi-label character, varying feature quality, varying label homophily, and CCNS similarity. We now describe the two main steps of our multi-label graph generator.
Multi-label generator. In the first step, we generate a multi-label dataset using MLDATAGEN (Tomás et al., 2014). We start by fixing the total number of labels and features. We then construct a hypersphere, we then generate
И R centered at the origin and has a unit radius. Corresponding to each label in smaller hypersphere with random radius but with the condition that it is contained in H. We now start populating the smaller hyperspheres with randomly generated datapoints with [F] dimensions. Note that each datapoint may lie in number of overlapping hyperspheres. The labels of the datapoint then correspond to the hyperspheres it lies in.
Graph generator. Having constructed the multi-label dataset, we now construct edges between the data points by using a social distance attachment model (Boguná et al., 2004). In particular, for two given datapoints (nodes) and j, their corresponding feature vectors are their coordinates given x; and xj respectively. The corresponding label vectors are denoted by y; and yy. We denote the hamming distance between the label vectors of nodes i and j by dzy:, We then construct an edge between datapoints (nodes) and j. (i,j) with probability given by
Pij 1+ |b -dy.),y))
(2)
where a is a homophily parameter, b is the characteristic distance at which Piş = J. Note that the edge density is dictated by both the parameters a and b. A larger would result in denser graphs. larger homophily parameter a would assign a higher connection probability the node pairs with shorter distances or nodes with similar labels. In particular, it random geometric graph model, which in the limit of large system size (number of nodes) and high homophily (large a) leads to sparsity, non-trivial clustering coefficient. and positive degree assortativity (Talaga & Nowak, 2020), properties exhibited by real-world networks. By using different combinations of values of and b, we can control the connection probability and further the label homophily of the generated synthetic graphs. We perform an extensive empirical analysis to study the relationship between a, b, and the label homophily of the generated datasets. We provide detailed instructions to use our synthetic data generator and our empirical analysis in Appendix A.2.
Synthetic datasets with fixed homophily and varying feature quality. For our experimental analysis, generate synthetic datasets with 3K nodes, 10 features, and total of 20 labels. Towards analyzing the
8

---

Published in Transactions on Machine Learning Research (09/2023)
(a) Label distribution in the syn- thetic dataset is more balanced. A relatively high multi-label character is exhibited with 50% nodes having than 3 labels.
(b) Cross-class Neighborhood Simi- larity in graph label 1.m
(c) Cross-class Neighborhood Simi-
larity in graph label 1omophilyy0044
(d) Cross-class Neighborhood Simi- larity in graph label homophily-0.6
(e) Cross-class class Neighborhood Simi- larity in graph label homophily-0.8
(f) Cross-class Neighborhood Simi-
larity in graph label homophily=1.00
Figure 5: Cross-class Neighborhood Similarity in hypersphere datasets with varying label homophily
variation in the method's performance with variation in homophily and feature quality first we constructed a dataset with fixed homophily of 0.377 (using a 8.8, = 0.12) and edge set of size 1M. We refer to this dataset as SYNTHETICI. We create five variants of SYNTHETICl with varying feature quality. In particular, add 10 random features for every node, which we refer to as irrelevant features. We then generate its variants by removing original features such that the ratio of the number of original to that of irrelevant features varies as in 01,0.8 0.5, 0.2.0). From the label distribution plot in 5a, observe the dataset is more multi-label than the real-world datasets because higher number of nodes now have multiple labels.
Synthetic datasets with varying homophily and CCNS. We also use different pairs of a and b and the same multi-label data from the first step to construct 5 synthetic graphs with label homophily (rounded up) in (0.2, 0.4, 0.6, 0.8, 1.0} to conduct the experiment where we test the influence of the label homophily the performances of the node classification methods. The detailed statistics of the synthetic datasets are provided in Appendix A.2.1 in Table 5. Figure 5 visualizes the cross-class neighborhood similarity in the five hypersphere datasets with varying homophily levels (homophily varies in [0.2, 0.4, 0.6, 0.8, 1.0)). In the synthetic graphs with low label homophily, the intra- and inter-class neighborhood similarities show no significant differences, i.e., the nodes from different classes have similar label distributions in their neighborhoods. We overall observe a high absolute value of neighborhood similarity. The reason here is that similar BLOGCAT (which also shows overall high CCNS scores) these synthetic low homophily graphs are highly connected and have a high average degree. As the label homophily gets higher, the contrast between the intra- and inter-class similarity becomes more significant.

---

Published in Transactions on Machine Learning Research (09/2023)
5
Experiments
From our dataset analysis the previous sections we observe that, unlike commonly used multi-class datasets, multi-label datasets usually have low label homophily and Moreover, similar to the case of multi-class datasets, node features might not always be available (as in BlOgCat) might be noisy. In this section, we perform large-scale empirical study comparing 8 methods over 7 real-world multi-label datasets and 2 sets of synthetic datasets with varying homophily and feature quality. Our experiments are designed to reveal and understand (i) propertics of datasets that favor cortain methods over others and (ii) the effect of varying feature quality and label homophily on method performance. The training and hyperparameter settings for each model are summarized in the Appendix A.3 in tables and 8, Our code is available at bttps://githin
varied cross-class neighborhood similarity.
com hwtp/iianniiiii Maagiiipy/MLGGG
Datasets. We employ 7 real-world datasets including BLOGCAT, YELP, OGB-PROTEINS, DBLP, PCG, HUMLoc, FUKLoc, and 2 sets of synthetic datasets with varying homophily and feature quality. These datasets are already described in Section 3. For all datasets except CGO--RROEINS, HUMLOC, and EuKLoc we generate 3 random training, validation, and test splits with 60%, 20%, and 20% of the data. For OGB- PROTEINS, HUML.o, and FUKLoc we follow the predefined data splits from (Hu et al., 2020), (Shen Chou, 2007) and (Chou Shen, 2007) respectively. As BLOGCAT has no given node features, we use an identity matrix the input feature matrix.
Compared Methods. For holistic evaluation include four classes of compared methods (i) simple methods, which include Multilayer Perceptron (MLP), which only uses node features and ignores the graph structure, and WEEPWALK, which only uses graph structure and igmores the node features (ii) Convolutional neural networks based which employ convolutional operations to extract representations from node's local neighborhoods and merge them with label embeddings for the final classification. We choose LANC as a bascline from this category, as previous works (Zhou et al., 2021; Song al., 2021) have shown its superior performance. (iii) graph neural networks including (a) GCN, GAT, and GRAPHSAGE, which known to perform well for graphs with high label homophily, and (b)H2GGN, which is designed to perform well both on homophilic and heterophilic graphs and (iii) GCN-LPA which combines label propagation and GCN for node classification. All these methods are also discussed in Section 2.
Evaluation Metrics. We report the average micro- and macro-F1 score, macro-averaged AUC-ROC score, macro-averaged average precision score, and standard deviation over the three random splits. Due to space constraints, we report average precision (AP) in the main paper, and all detailed results are available in Tables 9, 10, 11 in the Appendix A.4. Our choice of using AP over AUROC as the metric is also motivated in Appendix A.5.
6 Results and Discussion
Table 3: Mean performance scores (Average Precision) real-world datasets. The best score is marked in bold. The second best score is marked with underline. 'OOM' denotes the "Out Of Memory' error.
Method
BLOGCAT
YELP
OGB- PROTEINS
DBLP
PCG
HUMLoC
EukLoc
MLP
0.043
0.096
0.026
0.350
0.148
0.170
0.120
WEEKWALK
0.190
0.096
0.044
0.585
0.229
0.186
0.076
LANC
0.050
OOM
0.045
0.836
0.185
0.132
0.062
GcN
0.037
0.131
0.054
0.893
0.210
0.252
0.152
GAT
0.041
0.150
0.021
0.829
0.168
0.238
0.136
GRAPHSAGE
0.045
0.251
0.027
0.868
0.185
0.234
0.124
H2GCN
0.039
0.226
0.036
0.858
0.192
0.172
0.134
GCN-LPA
0.043
0.116
0.023
0.801
0.167
0.150
0.075
10

---

Published in Transactions on Machine Learning Research (09/2023)
6.1 Results real-world datasets.
Table 3 we provide the results for 7 real-world datasets. In general, on datasets with low label homophily, such as BLOGCAT and PCG, node representation or embedding learning methods such as DEEP outperform more sophisticated GNN based methods and simple MLP bascline. Classical GNNs show better performance on datasets characterized by high label homophily. H2GcN which is designed for multi-class datasets with heterophily do not. show a performance improvement. over classical GNNs on multi-label graph datasets with low homophily. Likewise, the method that combine label propagation with GNNs, achieve only comparable results to classical GNNs.
BlogCat. For BLOGGAT all GNN approaches as well as LANC and GCN-LPA obtain scores close to that of MLP which do not use any graph structure. Notably, MLP uses identity matrix as input features which in principle provides no useful information. The corresponding scores can be seen as the result of a random assignment. As method unifying the label and feature propagation, GCN-LPA does not show improvement on BLOGGAT compared to other basclines. This is because GCN-LPA uses the label propagation to adjust the edge weight and still only generates embedding by aggregating features over the weighted graph, while DEEPWALK take advantage of the informative topological structure in the graph and achieves the best performance.
Yelp, OGB- CGB-Protcins and DBLP. YELP has low label homophily and low clustering coefficient but more balanced label distribution as compared to other real-world datasets, so approaches designed specifically for low homophilic graphs and are capable of preserving information from both low- and high- order neighborhoods are expocted to perform better for this datasct. Among the GNN-bascd baselines, H2GcN which has shown improvements in low homophilic multi-class datasets outperforms GcN, and GCN-LPA but still outperformed by GRAPHSAGE. The use of CNNs in LANC to aggregate neighborhood features leads to excessive memory utilization for a graph with a very high maximum degree. This led to the out-of-memory error for YELP.
All methods perform poorly on OGB-PROTEINS with GcN and LANC slighty outperforming others. It also has low homophily which is similar to BLOCCAT, which also does not provide GNNs with any additional advantage. In particular, DEEPWALK and H2GcN outperform GAT and GRAPHSAGE as well as more sophisticated GCN-LPA. It is worth noting that the previously reported results on the OGB-PROTEINS leaderboard Hu et al. (2020) are significantly exaggerated due to the utilization of the AUROC metric in conjunction with excessive model training. When using the metic Average Precision, the scores we get is much lower that what were reported on the leaderboard.
As a co-authorship dataset, DBLP has the highest label homophily and the largest portion of nodes with a single label among all the real-world datasets. As shown in Figure 2a the section 3.1, the inter-class similarity is much weaker than the intra-class similarity. Besides, the high clustering coefficient indicates that the local neighborhood is highly connected. All of these factors further justify the best performance shown by GcN. Besides, the relatively poor performances of MLP and DEEP WALK indicate that the features or the structure alone are not sufficient for estimating node labels.
PCG, HumLoc and EukLoc. If the features are highly predictive of the labels, the simple baselines MLP using only feature information would be competitive baseline. In the experiments with the datasets, where the features are highly correlated (evident from relatively better performance of MLP) with the assigned labels, i.c., the biological interaction datascts HUMLoC and EUKLoC (shown in Table 3), GNNs and GCN-LPA tend to have better performance than DEEPWALK and LANC which only utilizes graph structure and features from the direct neighborhood. PCG exhibits low label homophily and high clustering coefficient. Consistent with observations other low homophilic datascts DREPWALK outperforms other methods PCG too. H2GCN, on the other hand, is outperformed by simpler GNN bascline like GCN.
6.2 Results on synthetic datasets
Table provides results for synthetic datasets with varying feature quality and label homophily. We provide detailed analysis and argue about performance differences in the following sections.
11

---

Published in Transactions on Machine Learning Research (09/2023)
Table 4: Average Precision (mean) on the synthetic datasets with varying levels of feature quality and homophily parameter. feat and Phome refer to the fraction of original features and the homophily parameter value, respectively.
Method
Tork / euct
Thoma
0.0
0.2
0.5
0.8
1.0
0.2
0.4
0.6
0.8
1.0
MLP
0.172
0.187
0.220
0.277
0.343
0.343
0.343
0.343
0.343
0.343
DEFPWALK
0.487
0.487
0.487
0.487
0.487
0.181
0.522
0.813
0.869
0.552
LANC
0.337
0.342
0.365
0.353
0.391
0.190
0.380
0.434
0.481
0.629
GCN
0.313
0.316
0.311
0.301
0.337
0.261
0.343
0.388
0.450
0.493
GAT
0.311
0.339
0.329
0.338
0.360
0.172
0.359
0.390
0.428
0.439
GRAPHSAGE
0.300
0.328
0.377
0.393
0.430
0.289
0.426
0.458
0.533
0.553
H2Gex
0.376
0.401
0.427
0.442
0.467
0.297
0.484
0.512
0.572
0.652
GCN-LPA
0.337
0.333
0.368
0.363
0.391
0.170
0.408
0.495
0.604
0.583
6.2.1 Effect of varying feature quality.
As simple baseline MLP and other GNN-based models use features input, we assume they will be sensitive to the varying feature quality. As DEEPWALK uses the graph structure alone, its performance would not be affected by the varying feature quality. To further validate our hypothesis and test the robustness of the methods to feature quality, we compare the method performances on variants of the generated SYNTHETIC datasot. Specifically, we vary the ratio of the original to the irrelevant features as in 0.2, 0.5, 1.03.
As shown in Table 4, under all levels of feature quality, the performances of DREPWALK do not change, as it generates representations for the nodes solely from the graph structure. The MLP is unsurprisingly the most sensitive method to the varying feature quality because it completely ignores the graph structure. LANC is also sensilive to the change of the feature quality il extracts feature vectors from the local neighborhood by performing convolutional operations on the stacked feature matrix of the direct neighbors.
The SYNTHETIC1 dataset used in this experiment has a label homophily of 0.3768, which is a relatively high label homophily for the multi-label datasets. Surprisingly, GCN-LPA which employs the label information performs only little better than GRAPHSAGE on the featuro-to-noise ratio of 0 and 0.2. H2GCN, on the other hand, outperforms all GNN-based baselines and GCN-LPA for all levels of feature quality.
6.2.2 Effect of varying label homophily.
In this subsection, we test the robustnoss of the methods to varying homophily and further argue how low label homophily has different semantics on multi-label graphs as it does on multi-class datasets. Specifically, we vary the label homophily as in (0.2, 0.4, 0.6, 0.8, 1.0].
As shown in Table 4, the performances of MLP do not change under different levels of label homophily, due to the fact that MLP only use the imput features.
H2GGN is a method that has been shown to perform well on heterophilic multi-class datasets. In the multi-label scenarios, it exhibits better performance than other GNN methods but is outperformed by simple MLP baseline in case of label homophily of 0.2.
On the other hand, with most of the attention drawn to developing new complicated mothods for the node classification task we observe simple baselines such as DEEPWALK outperform standard GNNs in several scenarios. On the synthetic datasets with the label homophily of 0.4, 0.6 and 0.8, DEEPWALK is the best- performing method. As shown in Table 4, the performance of DEEPWALK drops when the label homophily is 1.0. However, we want to emphasize that this is because we fixed the same walk length for DEEP WALK for all levels of label homophily and the improvement can be shown with a possible hyperparameter tuning.
As mentioned in section 4, the intra-class similarity is significantly stronger than the inter-class similarity in the synthetic graphs with higher label homophily, which helps GNN-based models to better distinguish the nodes from different, classes and thus achieve better results in the node classification task.
12

---

Published in Transactions on Machine Learning Research (09/2023)
7 Conclusion
We investigate the problem of multi-label node classification graph-structured data. Filling in the gaps in current literature, we (i) perform in-depth analysis on the commonly used benchmark datasets, create and release several real-world multi-label datasets and a graph generator model to produce synthetic datasets with tunable properties, (ii) compare and analyse the performances the methods from different categories for the node classification task by conducting large-scale experiments on 9 datasets and methods, and (iii) release our benchmark publicly.
We have novel and compelling insights from analysis of specific datascts and GNN approaches. For instance, uncover the pitfalls of the commonly used OGB-Protein dalaset for model evaluation. While multi-label graph datasets usually show low homophily, we show that approaches working on low homophilic multi-class datasets cannot trivially work on multi-label datasets which usually have low homophily.
While current graph-based machine learning methods are usually evaluated on multi-class dalasets, we demonstrate that the acquired improvements cannot always be translated to the more general scenario when the nodes characterized by multiple labels. We believe that work will open avenues for more future work and bring much-deserved attention to multi-label classification on graph-structured data. In future work, we plan to study the interplay of different dataset characteristics (for example edge density and label homophily) on the model performance.
References
Uchenna Akujuobi, Yufei Han, Qiamnan Zhang, and Xiangliang Zhang. Collaborative graph walk for semi- supervised multi-label node classification. CoRR, abs/1990.09906, 2019. URL attt:://axxie org/abs/ 1910.09706.
Sanmitra Bhattacharya, Viet Ha-Thue, and Padmini Srinivasan. Mesh: a window into full text for document. summarization. Bioinformatics, 27(1)):110 i128, 2011.
Marián Boguná, Romualdo Pastor-Satorras, Albert Diaz-Guilera and Alex Arenas. Models of social networks based on social distance attachment. Physical review E, 70(5) :56612,,, 2004.
Zhao-Min Chen, Xiu-Shen Wei, Peng Wang, and Yanwen Guo. Multi-label image recognition with graph convolutional networks. In Proceedings of the TERE/CVF conference on computer vision and pallern recognition, pp. 7177-5186, 2019.
Yinlin Cheng, Mengnan Ma, Xingyu Li, and Yi Zhou. Multi-label classification of fundus images based on graph convolutional network. BMC Medical Informatics and Decision Making, 21(2):1 9, 2021.
Kuo-Chen Chou and Hong-Bin Shen. Euk-mploc: a fusion classifier for large-scale eukaryotic protein subcellular location prediction by incorporating multiple sites. Journal of Proteome Research, 6(5): 1728-17344 2007.
Hong-Min Chu, Chih-Kuan Yeh, and Yu-Chiang Frank Wang. Deep generative models for weakly-supervised multi-label classification. In Proceedings of the European Conference on Computer Vision (ECCV), pp. 400-415, 2018.
Gene Ontology Consortium. The gene ontology resource: 20 years and still going strong. 47(D1)):330-D333 2018.
UniProt Consortium. Uniprot: a hub for protein information. Nucleic acids research, 43(D1)::D04-D211, 2015.
Szklarczyk D, Gable AL, Junge A Lyon D, Wyder S, Eluerta-Cepas J, Simonovic M, Doncheva NT, Morris JH, Bork P, Jensen LJ, and Mering CV. String vl1: protein-protein association networks with increased coverage, supporting functional discovery genome-wide experimental datasets. Nucleic Acids Research, 47(D1):D607-D611 -D11,, 2019.
13

---

Published in Transactions on Machine Learning Research (09/2023)
Thi Ngan Dong and Megha Khosla. Towards a consistent evaluation of mirna-discase association prediction models. In 2020 TEEE International Conference on Bioinformalics and Biomedicine (BIBM), pp. 1845.1842. LEEE, 2020.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. CoRR, abs/1706.0221 02216, 2017. URL http::/arxiv..rgg//
Mengying Hu, Hu Han, Shiguang Shan, and Xilin Chen. Weakly supervised image classification through noise regularization. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11517-11525, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. ar preprint (alu:0055000887 2020.
Dat Huynh and Ehsan Elhamifar. Interactive multi-label cmn learning with partial labels. In Proceedings of the IEEE/CVE Conference on Computer Vision and Pattern Recognition, pp. 9423 9432, 2020.
Vikas Jain, Nirbhay Modhe, and Piyush Rai. Scalable generative models for multi-label learning with missing labels. In Doina Precup and Yee Whye Tch (cds.), Proceedings of the 94th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pp. 1636 1644. PMLR, 06 -1 Aug 2017. URL. http::s///pooceddiii .olg........... pwt....res///////11 jain/aannnn1a jaimi7a.htll.
Junteng Jia and Austion R. Benson. Residual correlation in graph neural network regression. In Proceedings of the 26th ACM STGKDD International Conference on Knowledge Discovery Dala Mining, pp. 588 598, 2020.
Samuel Kerrien, Bruno Aranda, Lionel Breuza, Alan Bridge, Fiona Broackes- Brotekes-Carter, Carol Chen, Margaret Duesbury, Marine Dumousseau, Mare Feuermann, Ursula Hinz, et al. The intact molecular interaction database in 2012. Nucleic acids research, 40(D1):D841-D8A) 2012.
Megha Khosla, Jurek Leonhardt, Wolfgang Nejdl, and Avishek Anand. Node representation learning for directed graphs. In Joint European Conference Machine Learning and Knowledge Discovery in Databases, pp. 395-411. Springer, 2019.
Thomas N Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprinl XrXi 02907, 2016.
Jack Lanchantin, Arshdeep Sekhon, and Yanjun Qi. Neural message passing for multi-label classification. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 138-163. Springer, 2019.
Irene Li, Tianxiao Li, Yixin Li, Ruihai Dong, and Toyotaro Suzumura. Heterogeneous graph neural networks for multi-label text classification. CoRR, abs/ 22103.14622 2021. URL https: org.///ivorr//eeo org/abg abs/2103. 14620.
Jingzhou Liu, Wei-Cheng Chang, Yuexin Wu, and Yiming Yang. Deep learning for extreme multi-label lext classification. In Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '17, pp. 115-124, New York, NY, USA, 2017. Association for Computing Machinery. ISBN 0781450350225 doi: 10.1145/3077136 0007077713330088888 URL https: http::://doo.orr///. 1144/307713630000344. 3080834.
Weiwei Liu, Haobo Wang, Xiaobo Shen, and Ivor W Tsang. The emerging trends of multi-label learning. IEEE transactions on paltern analysis and machine intelligence, 44(11):7955 7974, 2021.
Jiaqi Ma, Bo Chang, Xuefei Zhang, and Qiaozhu Mei. Copulagmn: towards integrating representational and corrolational roles of graphs in graph neural networks. arXiv preprint arXiv:2010.00 0.00099,0,0,,,,.....00 2020.
Qianwen Ma, Chunyuan Yuan, Wei Zhou, and Songlin Hu. Label-specific dual graph neural network for multi-
label text classification. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pp. 3855 3864, 2021a.
14

---

Published in Transactions on Machine Learning Research (09/2023)
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks?
arXiv preprint ar 06.06134, 2021b.
Mingdong Ou, Peng Cui, Jian Pei, et al. Asymmetric transitivity preserving graph embedding. In Proc. of the International Conference Knowledge Discovery and Dato Mining, pp. 1105- 1115,114,, 2016.
Ankit Pal, Muru Selvakumar, and Malaikannan Sankarasubbu, Multi-label text classification using attention- based graph neural network. arXiu preprint Stt:2009.11644 2020.
Bryan Peronii, Rami AI-Rlou, and Steven Skiena. Deepwalk: Online learning of social representations. Proc. of the International Conference on Knowledge Discovery and Data Mining, 2014.
Janet Piñero, Juan Manuel Ramírez- Anguita, Josep Saüch-Pitaan Pitarch, Francesco Ronzano, Emilio Centeno, Ferran Sanz, and Laura Furlong. The disgenet knowledge platform for disease genomics: 2019 update. Nucleic acids research, (8DD1))D855-D855 2020.
Decpak Saini, Arnay Kumar Jain, Kushal Dave, Jian Jiao, Amit Singh, Ruofei Zhang, and Manik Varma. Galaxe: Graph neural networks with labelwise attention for extreme classification. WWW '21, New York, NY, USA, 2021. Association for Computing Machinery. ISBN 9781450383127, doi: 10.1145/8442381.444999 URL https://doi. org/ 1145/3442388 3449937.
Hong-Bing Shen and Kuo-Chen Chou. Hum-mploc: an ensemble classifier for large-scale human protein subcellular location prediction by incorporating samples with multiple sites. Biochemical and biophysical research communiiaaiins,, 355(4):1006 1011, 2007.
Min Shi, Yufei Tang, Xingquan Zhu, and Jianxun Liu. Multi-label graph convolutional network representation learning. CoRR, abs/1912.111555 2019. URL http:///axxiv.oogabb/////e/ 11757.
Min Shi, Yufci Tang, Xingquan Zhu, and Jianxun Liu. Multi-label graph convolutional network reprosentation learning. IEEE Transactions on Big Dala, 2020.
Dezhao Song, Andrew Vold, Kanika Madan, and Frank Schilder. Multi-label legal document classification: A deep learning- based approach with label-attention and domain-specifcc pre-training. Inf. Syst., 106(C), may 2022. ISSN 0306-4379. doi: 10.1016/j 2011.101788. URL https: http://///oooo/1..1000001 org/10.1016/ is. 2021. 101718.
Zixing Song, Ziqiao Meng, Yifei Zhang, and Irwin King. Semi-supervised multi-label learning for graph- structured data. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 1723-1733 1733, 2021.
Szymon Talaga and Andrzej Nowak. Homophily as a process generating social networks: Insights from social distance attachment. model. Journal of Arlificial Socielies and Social Simulation, 23(2):6, 2020. ISSN 1460-7425.
Lei Tang and Huan Liu. Relational learning via latent social dimensions. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, pp. 817-826, New York, NY, USA, 2009. Association for Computing Machinery. ISBN 9781605584959. doi: 00.114//1557099 1557109. URL httpp:///oi..ooo 111111.111111111111111 11111151.1.1.....1..
Jimena Torres Tomás, Newton Spolaör, Everton Alvares Cherman, and Maria Carolina Monard. framework generate synthetic multi-label datasets, Electronic Notes in Theoretical Computer Science, 302:155-176,
2014.
Petar Veličković, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. URL https: accepted as poster.
//openreview. http://rwweeeeeeteeoommtedtrtttt
Bingyu Wang, Li Chen, Wei Sun, Kochen Qin, Kefeng Li, and Hui Zhou. Ranking-based autoencoder for extreme multi-label classification. CoRR, abs/ 10991994.00937,, 2019. URL 05937.
1904.
15

---

Published in Transactions on Machine Learning Research (09/2023)
Hongwei Wang and Jure Leskovee. Unifying graph convolutional neural networks and label propagation. CoRR, has/2002.06755,, 2020. URL
Guanming Wu, Xin Feng, and Lincoln Stein. A human functional protein interaction network and its application to cancer data analysis. Genome biology, 11(5):1-234 2010.
Linli Xu, Sijie Teng, Ruoyu Zhao, Junliang Guo, Chi Xiao, Deqiang Jiang, and Bo Ren. Hierarchical multi-label text. classification with horizontal and vertical category correlations. In Proceedings of the 2021 Conference Empirical Methods in Natural Language Processing, pp. 2459 2468, Online and Punla Cana, Dominican Republic, November 2021. Association for Computational Linguistics. doi: 10.18653/ wttpa//v11222eemm/m// www.pmmmin.nneee 190. URL https: https://aclanti /aclanthool org/ emnlp-main 190.
Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and go beyond it: An effective knowledge distillation framework. In Proceedings of The Web Conference 2021 (WWW '11). ACM, 2021.
Xiaodi Yang, Shiping Yang, Qinmengge Li, Stefan Wuchty, and Ziding Zhang. Prediction of human- virus protein-protein interactions through sequence embedding- based machine learning method. Computational and structural biolechnology journal, 18:153 161, 2020.
Yang Yang, Ryan N Lichtenwalter, and Nitesh V Chawla. Evaluating link prediction methods. Knowledge and Informalion Systems, 45(3):751-74 782, 2015.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. CoRR, abs/1907.04900 2019. URL http://arxiv.org/ 04931.
Min-Ling Zhang and Zhi-Hua Zhou. A review multi-label learning algorithms. IEEE transactions on knowledge and data engineering, 26(8):1819 1837, 2013.
Xiangping Zheng, Xun Liang, and Bo Wu. Capsule graph neural network for multi-label image recognition (student abstract). In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp- 13117-13118, 2022.
Cangqi Zhou, Hui Chen, Jing Zhang, Qianmu Li, Dianming Hu, and Victor S. Sheng. Multi-label graph node classification with label attentive neighborhood convolution. Expert Systems with Applications, 180: 115063, 2021. ISSN 0957-4174. doi: attps://doi.org 10. 1016 wstp:/..esaa....11500.. sciencedirect. accoacddrrett..o////eeeeearrttc
URL attps://www.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33, 2020.
Daoming Zong and Shiliang Sun. GNN-XML: graph neural networks for extreme multi-label text classification. CoRR, abs/2012.05860, 2020. URL https://arza http://///aaw...o/////////////// wrtg/abs//02..058/58
A Appendix
Organization. We explain the construction details of the biological datasets in A.1. Furthermore, in Section A.2, we study the parameters of the graph generator and demonstrate how generate the synthetic datasets with varying label homophily. We also summarize the characteristics of the generated synthetic graphs that were used in Section 5 for the varying homophily and feature quality experiments. In Section A.3, we summarize the hyperparameters of the models we used in this work. In Section A.4, we provide the full original experiment results on all datasets reported in Micro- and Macro- F1, AUROC, and Average Precision score with the standard deviation of the 3 random splits if the dataset not pro-splitted. Note that for higher precision, the scores are provided in percentages. Last but not least, we provide the motivation for using Average Precision in the main paper in Section A.5.
16

---

Published in Transactions on Machine Learning Research (09/2023)
A.1 Biological Dataset Construction
A.1.1 The Protein phenotype prediction dataset.
A phenolype is any observable characteristic or trait of a disease. Identifying the phenolypes associated with a particular protein could help in clinical diagnostics or finding possible drug targets.
To construct the phenotype prediction dataset, we first retrieve the experimentally validatod protein-phenotype associations from the DisGeNET (Piñero al., 2020) database. We then (i) retain only those protein associations that marked "phenotype", (ii) match each disease to its first-level category in the MESH ontology (Bhattacharya et al., 2011), and (iii) remove any (phenotype) label with less than 100 associated proteins. To construct the edges, we acquire the protein functional interaction network from (Wu et al., 2010) (version 2020). We then (i) model each protein as a node in the graph, (ii) retain only the protein-protein interactions between the proteins that have the phenotype labels available, and (iii) remove any isolated nodes from the constructed graph. In the end, our dataset consists of 3, 233 proteins and 37, 351 edges. The node features the 32-dimensional sequence-based embeddings retrieved from (Consortium, 2015) and (Yang et al., 2020).
A.1.2 The human protein subcellular location prediction dataset (HumLoc).
Proteins might exist at or move between different subcellular locations. Predicting protein subcellular locations can aid the identification of drug targets'. Wo retrieve the human protein subcellular location data from (Shen & Chou, 2007) which contains 3, 106 proteins. Each protein can have one to several labels in 14 possible locations. We then generate the graph multi-label node classification data as follows:
We model each protein a node in the graph. We retrieve the corresponding protein sequences from Uniprot (Consortium, 2015). We obtain the corresponding 32-dimensional node feature reprosentation by feeding them to a pre-trained model (Yang et al., 2020) on protein sequences.
Each node's label is the one-hot encoding (i.e., 14 dimensions) generated from its sub-cellular information. Each value in the label vector represents one sub-cellular location. A value of indicates the corresponding protein exists at the respective location and means otherwise.
The edge information generated from the protein-protein interactions retrieved from the IntAct (Kerrien al., 2012) database. There exists a connection between two nodes in the graph if there exists an interaction between the corresponding protcins in IntAct. For each pair of proteins, more than interaction of different lypes might exist. Therefore, we assign each edge a label. The edge label is modeled as al-dimensional vector where each value in the vector represents the confidence score for particular connection type.
In the end, the HUMLOC dataset consists of 3,106 nodes and 18,496 odges. Each node can have one several labels in the 14 possible locations. Among the 3, 1,106 different proteins, 2,580 of them belong only to location; 480 of them belong to 2 locations; 43 of them belong to 3 locations and 3 of them belong to 4 locations. Both the accession numbers and sequences are given. None of the proteins has more than 25% sequence identily to any other in the same subset (subcellular location). For a more detailed description of the original dataset, we refer the readers to (Shen & Chou, 2007).
A.1.3 The eukaryote protein subcellular location prediction dataset (EukLoc).
We retrieve the eukaryote protein subcellular location multi-label data from (Chou & Shen, 2007). We then employ the same data sources and pre-processing strategy as described for the HUMLoG dataset generate the multi-label node classification dataset for eukaryote protein subcellular location prediction. In the end, the final pre-processed data contains 7,766 proteins (nodes) and 13,818 connections(edges)) Each protein(node) can receive one to several labels in 22 possible locations.
http:://ww..iitteeeiaroor//////s subcellular saars_oooaaaaatt Docallization_prddictti
17

---

Published in Transactions on Machine Learning Research (09/2023)
A.2 Parameter Study of the Graph Generator Model
1.0
20
0.10
Label Homophily
Label Homophily
0.8
08
Edge Density
0.30
3
04-
04-
0.25
04
04
0.25
022
044
025
10
0.00
005
0.30
0.5
0.00
025
07
03
0.4
0.5
0.6
07
0.
09
10
a
b
Label Homophily
Figure 6: Visualization of the parameter study of the Graph Generator Model. The first two subplots demonstrate the relationships between the value of a and b and the label homophily of the generated synthetic datasets. The last subplot shows the edge density and the label homophily of the generated synthetic graphs This shows with the same multi-label data, we can generate synthetic graphs with varying label homophily.
As mentioned in Section 4, the choice of a and b will directly determine the connection probability Pt,j of each pair of nodes i and j and the homophily ratio of the generated synthetic graph. Here, we demonstrate how we choose the value of a and to generate synthetic graphs with varying homophily ratios. Note that the valid range of a and b may differ when a different distance metric is used.
Firstly, we randomly choose 500 nodes from SYNTHETIC1 dataset and generate series of small synthetic graphs with varying a and b and observe the relationship between them. Since we have two hyperparameters' ranges to determine, we first fix the value of one and explore the range of the other and then vice versa. To recall, b indicates the characteristic distance at which Pi- = 1 2, and our hamming distance should be in the range of [0,1], I], we first fix to 0.05. We chose a small value of b because the larger value of would dominate the influence of a and the relationship between the homophily ratio and the change of the value of becomes unclear. The relationship between the homophily ratio of the generated synthetic graphs and the value of a is shown in Figure 6(a). As shown in the subplot, the label homophily increases monotonically the value of increases in the range of [0, 10). As is interpreted as the homophily parameler in (Boguná et al., 2004), only positive values make sense.
Similarly, we then fix a to its middle value in the valid range, i.c. 5, and explore the valid range of b and visualize the relationship of the graph level homophily ratio and the value in the subfigure, the label homophily decreases as the b increases in the range of (0, 0.25). As b increases, the node pairs with bigger distance would also have 50% of the probability to be connected, the number of edges will increase, and the label homophily ratio will decrease. As b decreases, the node pair with smaller distance would only have 50% of the probability of being connected. The model becomes cautious about connecting a node pair. The number of edges decreases and only the node pairs, which are alike will be connected, thus, the label homophily ratio increases.
Figure 6(b). As illustrated
Then, we use combinations of a and b to generate synthetic graphs with specific homophily ratios. We sample 20 as and bs uniformly from their valid ranges with the increments 0.5 and 0.0125. Since the graph label homophily has inverse linear relationship with and b, we arrange the sampled b in reverse order and then form 20 value pairs (alpha, b). We generate 20 synthetic graphs from the multi-label dataset corresponding to SYNTHETIC1 with these value pairs (a, b) and plot the homophily ratio and the edge density of the generated graphs in Figure 6(c). As shown in the subplot, using the same multi-label data, we are able to generate synthetic graphs with varying homophiles. And the edge density decreases when label homophily increases. As in higher label homophily graphs, the generator will only connect the nodes that are highly similar each other. In contrast, when the label homophily is low, the graph generator will connect every possible node pair in the graph resulting in denser graphs.
18

---

Published in Transactions on Machine Learning Research (09/2023)
A.2.1 Statistics Of The Synthetic Datasets
Here we summarize the characteristics the generated synthetic graphs with varying label homophily and Teature quality. The first row denotes the name of the synthetic graphs, where in the varying homophily experiments, the variants of datasets are named with their label homophily. The SYNTHETIC1 dataset used in the varying feature quality experiment, where we remove the relevant features create dataset variants with varying feature quality levels. Note that for all the datasets the label distribution stays the same they are just different graphs generated from the same multi-label dataset. The statistics label distribution for these datasets are given in Table 5 and Table 6.
Table The number of edges and clustering coelficient. of the synthetic datasets with varying label homophily and SYNTHETICI. The row of |El'' denotes the number of edges and the 'clustering coefficient' denotes the clustering coefficient of these datasets
Datasct
0.2
0.4
0.6
0.8
1.0
SYNTHETIC1
E
2.37M
598k
298k
79.5k
47.6k
1.00M
Clustering Coefficient
0.53
0.37
0.39
0.49
0.93
0.57
Table 6: The label distribution of the synthetic dataset used in this work. The column notations are same in Table 1.
[L]
[mmed
Vmmaa
Tmaa
25%
50%
75%
label distribution
20
3
3.23
12
5
A.3 Hyperparameter Setting
In this section, summarize all the hyperparameters used for the experiment section. The detailed setting is listed in Table 7 and 8.
More specifically, for MLP and all GNN-based methods, we summarize the number of layers, the dimension of the hiddon layer, the learning rate, the patience of the Earlystopping, the weight decay, and the number of neighbors we sample for the models that require sampling.
We use the same number of layers and the same hidden size for MLP and the other GNN-based methods. The learning rate for the synthetic datasets in the varying feature quality and homophily experiments is 0.001 instead of 0.01 as in the other models because the performance of the H2GcN is further improved. We also use Earlystopping with the patience of 100 epochs to train the models properly. For GRAPHSAGE, we sample 25 and 20 one and two hops away neighbors for aggrogation. As other GNN-based baselines do not use the sampling method, the corresponding cells are filled with 'No".
For the only mandom-walk-beee based method, we deploy the default setting for all the datasets in this work DIePWWLL already shows competitive performance. We perform 10 random walks with the walk length of 10 for each node to generate the sequence and use the window size of 5 for the training pairs, the generated embedding size is 64.
A.4 The experiment results reported four metrics
We summarize the experimental results on the real-world datascts and the synthetic datascts in Table 9, Table 10, and Table 11, respectively. For better precision, we report the scores in percentages. Specifically, for the scores reported OGB-PROTRINS, the difference between our results and those reported in the
19

---

Published in Transactions on Machine Learning Research (09/2023)
Table 7: The hyperparameter setting for MLP and GNN baselines in this work for datasets
MLP
GCN, GAT, GraphSAGE
H2GCN
GCN-LPA
GCN
Layers
2
2
5 LPA
Hidden size
256
256
256
256
real-world: 0.01
Learning rate
0.01
0.01
0.01
syuthetic: 0.001
Earlystopping patience
100
100
100
100
Weight decay
5e-4
5e-4
5e-4
1e-4
Sample for aggregation
No
GraphSAGE:(25, 10]
No
No
Table 8 The hyperparameter setting for DEEPWALK in this work for all datasets
Number of walks
Walk length
Embedding size
Window size
DeepWald Walk
10
10
64
benchmark is because 1) we use layer MLP without Node2Vec features. 2) We use Earlystopping with the patience of 100 epochs to prevent the models from being overtrained. 3) We use sampled local neighborhoods have consistent setting for all the datasets using GRAPHSAGE. The specific parameters we used are summarized in A.3. Another pre-processing we did was remove the isolated nodes in PCG. The details are described in Appendix A.1.1.
Table 9: Multi-label Node Classification results on real-world datasets. The results of BLOGČAT, YELP, PCG, and DBLP the mcan of three random splits with 60% for train-, 20% validation and 20% test dataset, while the results of OGB-PROTEINS, HUMLoC, EuKLoc reported with the built-in splil.
Dataset
Method
MICRO-F1
MACRO-F1
AUC-ROC
AP
MLP
17.11 + 0.64
2.49 + 0.18
50.30 + 1.04
4.25 + 0.63
DEEP WALK
35.59 + 0.21
19.74 0.54
73.20 - 0.58
18.55 0.17
BLOG- CAT
LANC
13.95 + 2.02
4.55 0.82
52.34 1.34-0.0
5.03 0.007
GeN
16.69 + 0.47
2.63
47.85 0.06
3.69
GAT
17.22 + 0.52
2.48 0.08
50.88 + 1.45
1.55+0.00
GRAPUSAGE
16.18 + 0.31
2.38 0.27
52.73 0.82
4.10
H2GGN
16.86 + 0.34
2.60 0.16
49.83 + 1.08
3.92
GCN-LPA
17.15 + 0.68
2.55 - 0.19
51.35 + 0.67
4.33 + 0.31
0.31
MLP
26.04 + 0.09
18.55 + 0.20
50.17 + 0.01
9.58 + 0.01
DEEPWALL
49.78 + 0.07
24.98 + 0.04
50.67 + 0.08
9.60 0.02
LANC
YELP
20

---

Published in Transactions on Machine Learning Research (09/2023)
Table 9: Multi-label Node Classification results on real-world datasets. The results of BLOGCAT, YELP, PCG, and DBLP are the mean of three random splits with 60% for train-, 20% validation and 20% test dataset, while the results of OGB-PROTEINS, HUMLoC, EukLoc are reported with the built-in split.
Dataset
Method
MICRÓ-FT
MACRÓ-F1
AUC-ROC
AP
GcN
52.21 + 0.07
27.60 + 0.04
53.81 + 0.13
13.14 + 0.06
GAT
51.24 + 0.08
26.66 0.06
67.80 + 0.05
15.00 0.07
GRAPHSAGE
56.06 + 0.10
31.26 + 0.10
81.05 + 0.25
25.09 + 0.31
H2GcN
54.12 = 0.01
30.52 0.11
75.25 + 0.46
22.57 - 0.51
GCN-LPA
50.31 + 0.29
25.68 0.43
61.09 + 2.27
11.62 0.74
MLP
2.55
2.40
54.05
2.59
OGB- PROTEINS
DEEP WALK
2.88
2.75
68.75 75
4,41
LANC
2.35
2.21
68.03
4.48
GCN
2.77
2.63
71.48
5.36
GAT
2.55
2.40
50.64
2.14
GRAPHSAGE
2.59
2.43
55.83
2.68
H2GCN
2.55
2.39
62.75
3.61
GCN-LPA
2.56
2.41
53.22
2.33
MLP
42.14 + 0.27
32.04 0.65
54.47 + 0.07
34.97 0.14
DEEP WALK
63.27 + 0.34
59.11 0.36
74.81 + 0.16
58.49 : 0.25
DBLP
LANC
81.93 = 0.29
80.39 0.42
91.76 0.36
83.55 = 0.98
GeN
87.03 + 0.20
8 0.38
94.15
89.27 0.24
GAT
83.06 + 0.17
81.26 1.26+0..1
12.57+0.0
82.93 = 0.16
GRAPUSAGE
85.22 0.23
83.89 + 0.21
94.32 + 0.02
86.84 + 0.18
H2GCN
83.99 = 0.92
82.56 + 0.86
92.14 0.57
85.82 = 0.64
GCN-LPA
82.88 0.31
81.31 0.34
90.17 + 0.43
80.07 1.24
MLP
38.04 + 1.20
18.03 + 1.29
51.07 + 0.63
14.78 + 0.60
DEEP WALK
42.26 + 1.37
31.49 - 0.90
63.58 = 0.87
22.86 + 1.00
PCG
LANC
36.28 + 0.34
56.58 0.69
18.53 + 1.14
GCN
41.46 + 1.21
25.59 +.92
0.82
21.03 + 0.34
GAT
36.91 + 1.75
1.72
56.33 4.64
2.11
GRAPHSAGE
38.89 + 1.17
24.44 1.74
13.57
18.45 0.29
H2GCN
39.05 + 0.99
24.38 2.17
58.10 + 0.14
19.19 = 0.49
GCN-LPA
39.57 + 1.12
22.90 + 1.33
54.74 + 0.95
16.71 + 0.14
MLP
42.12
18.04
66.04
16.95
WALK
45.26
23.30
65.67
18.58
HUM- LOc
LANC
39.25
11.51
59.65
13.24
GeN
51.67
25.57
67.28
25.15
GAT
47.10
17.49
72.47
23.75
GRAPUSAGE
48.05
21.22
70.30
23.42
H2GCN
45.39
18.35
64.31
17.23
GCN-LPA
45.73
18.15
62.40
14.96
MLP
43.58
11.13
66.83
12.00
DEEPWALK
34.67
6.74
56.12
7.58
LANC
36.08
4.55
51.13
6.16
EU-
Loc
GeN
45.86
12.27
70.53
15.15
K-
GAT
41.58
6.76
71.65
13.59
GRAPHSAGE
44.65
11.96
69.04
12.44
H2GCN
44.93
11.80
69.45
13.35
GCN-LPA
36.72
5.93
56.65
7.45
21

---

Published in Transactions on Machine Learning Research (09/2023)
Table 10: Multi-label Node Classification results on Synthetic dataset with varying feature quality. All results are the mean of three random splits. The Ratios of the relevant and the irrelevant features are [0, 0.2, 0.5, 0.8, 1.0].
Feature Ratios
Method
MICRO-F1
MACRO-F1
AUC-ROC
AP
MLP
67.05 = 0.91
25,15 : 0.89
50.99
17.17 0.42
WALK
86.22 0.39
47.80 0.31
84.15
48.70
LANC
69.67 + 0.26
26.68 + 1.16
75.36
33.68 = 0.88
GeN
67.09 = 0.95
25.12
0.91
31.27 0.66
GAT
66.67 = 0.71
25.09
3.97
31.10 3.17
GRAPHSAGE
67.90 = 1.40
2.5
66.47
30.01 = 0.71
H2GCN
71.12 + 1.26
27.45 1.18
80.83 0.98
37.64 1.72
GCN-LPA
70.26 + 2.00
26.70 1.47
70.58 1 2.04
33.65 1 2.61
MLP
68.37 = 0.55
26.61 + 0.47
54.47 0.19
18.70 = 0.69
WALK
86.22 0.39
47.80 0.31
84.15
48.70 0.51
LANC
70.84 = 1.75
27.62 0.74
34.24 1.42
00
GeN
67.42 = 1.07
25.31 1.09
0.87
31.59 0.63
GAT
67.07 + 1.07
25.03 1.16
64.55
33.90 0.30
GRAPHSAGE
70.14 0.60
27.99
69.44
32.84 0.79
H2GeN
73.21 = 1.07
28.85
81.78 1.24
40.12 4.24
GCN-LPA
69.67 = 1.67
26.14 1.53
71.02 = 1.71
33.33 = 1.31
MLP
68.83 = 0.78
27.57 + 1.10
61.63 + 0.74
21.95 - 0.40
DEEP WALK
86.22 0.39
47.80 0.31
84.15 0.56
48.70 0.51
LANC
73.21 = 2.79
30.02 1
77.05 1.16
36.45 = 1.30
0.5
GeN
67.55 1.08
25.39 1.08
77.25
31.14 0.61
GAT
67.76 + 1.75
25.49 1.46
64.40 1.64
32.92 0.88
GRAPDSAGE
74.70 = 0.49
+
76.24
37.65 = 0.65
H2GeN
76.16 + 0.47
32.85 0.28
84.96 0.55
42.70 = 0.27
GCN-LPA
72.11 = 1.89
27.80 0.77
74.39 = 1.26
36.84 = 1.02
MLP
70.17 1: 0.81
29.37 0.99
69.53 0.46
27.65 1 0.77
DEEPWALK
86.22 0.39
47.80 0.31
84.15 0.56
48.70 0.51
LANC
72.67 + 3.56
29.67 + 3.13
74.73 1.07
35.32 = 2.06
0.8
GeN
69.56 + 1.14
25.79 1.14
77.03+0..9
30.10 0.71
GAT
67.93 = 0.75
25.40 1.17
66.41 + 3.55
33.78 0.96
GRAPHSAGE
75.66
32.39 1.50
78.31 0.49
39.25 0.86
H2GeN
78.68 + 0.38
36.17 0.56
86.01 + 0.64
41.21 = 0.31
GCN-LPA
72.62 1.46
27.74 0.67
73.99 1.06
36.28 = 1.57
MLP
72.90 1: 0.27
31.52 0.52
75.23 0.63
34.29 1 0.07
DEEPWALK
86.22 1 0.39
47.80 0.31
84.15 0.56
48.70 0.51
LANC
74.13 1 1.61
30.38 1 1.29
75.26 1 0.93
37.47 1 0.27
01
GeN
70.74 + 0.80
26.57 0.97
79.22 0.82
33.70 0.79
GAT
70.22 + 1.27
26.35 +.98
66.52 1..52+10 1.03
36.01 + 0.72
GRAPHSAGE
78.71 0.59
3.47
80.77
43.05 0.22
H2GcN
79.97 = 0.19
38.73 0.91
87.09 1009:000 0.12
46.71 = 0.37
GCN-LPA
76.28 1.27
31.91 1.07
76.38 0.36
39.10 2.03
A.5 Challenge of the Evaluation Metrics
The Arca under the ROC curve (AUC) and the Arca under the Procision-Rocall curve (AUPR) are two widely accepted non-parametric measurement scores used by existing works. Nevertheless, as discussed in (Yang et al., 2015), the AUC score sometimes misleading for highly imbalanced datasets like those in our work. In addition, AUPR might lead over-ostimation of the modcls' performance when the number of thresholds (or unique prediction values) limited (Dong & Khosla, 2020). For such reasons, as suggested in (Dong & Khosla, 2020), instead use the Average Precision (AP) score primary evaluation metric. Following
22

---

Published in Transactions on Machine Learning Research (09/2023)
Table 11: Multi-label Node Classification results Synthetie dataset with varying label homophily. All results are the mean of three random splits. The label homophiles (rounded up) are [0.2, 0.4, 0.6, 0.8, 1.0]
Label Homophily
Method
MICRO-F1
MACRO-F1
AUC-ROC
AP 34.29 + 0.07
MLP
72.90 + 0.27
31.52 = 0.52
75.23 0.63
DEEPWALK
66.62 0.62
26.02 0.55
52.19 +
18.07 0.71
LANC
67.05 + 0.92
25.12 = 2.20
54.49 + 0.53
18.95 + 0.43
0.2
GCN
67.28 + 0.67
25.21 = 1.04
66.59 + 0.58
26.06 1.07
GAT
65.09 = 0.89
24.61 = 1.41
51.43 + 0.33
17.05 + 0.36
GRAPHSAGE
73.57 + 0.20
31.22 0.65
71.72 0.30
28.94
H2GcN
73.80 1 0.59
31.86 1 0.89
73.24 0.08
29.69 0.53
GCN-LPA
67.02 1 0.89
25.24 1.31
49.92 0.93
17.02 0.31
MLP
72.90 + 0.27
31.52 = 0.52
75.23 0.63
34.29 0.07
WEEKWALK
88.79 0.20
54.741 1.73
85.74 + 0.33
52.15 1.41
LANC
75.16 = 0.77
33.69 = 0.94
76.53 0.86
37.99 0.74
0.4
GeN
72.16 + 1.70
26.95 1.18
80.19 + 0.75
34.29 0.88
GAT
71.50 + 1.30
27.58 = 1.11
69.96 1.69
35.86 0.59
GRAPHSAGE
79.09 = 0.33
36.05 1.56
0.30
42.57 0.49
H2GCN
81.30 = 0.25
40.54 = 0.74
87.91 0.04
48.36 + 0.44
GCN-LPA
78.11 1 1.38
32.71 1 1.47
78.00 0.70
40.80 0.20
MLP
72.90 + 0.27
31.52 = 0.52
75.23 0.63
34.29 0.07
DEEPWALK
95.94
82.58 0.19
95.32 0.80
81.34 + 0.95
LANC
80.36 1:86:188 1.81
39.65 = 3.14
81.85 2.66
43.42 + 3.61
0.6
GCN
75.47
29.43 0.43
84.08 0.72
38.78 0.33
GAT
75.13 0.39
29.26 = 0.56
72.85 + 0.79
39.01 0.23
GRAPHSAGE
82.46 0.67
40.46 - 1.67
45.79 0.91
H2GCN
83.40 = 1.94
44.32 = 1.59
89.98 + 0.86
51.19 1.92
GCN-LPA
85.45 2.42
47.67 4.72
83.96 2.22
49.54 3.54
MLP
72.90 1
31.52 0.52
75.23 0.63
34.29 0.07
DEEPWALK
96.53 0.61
89.25 + 1.96
95.81 + 0.47
86.93 + 1.92
LANC
79.35 0.97
46.03 = 2.24
87.75 + 0.60 0.60
48.10 + 1.17
0.5
GCN
8..72
36.60 = 1.31
86.82 0.62
44.98 0.40
GAT
77.35 - 0.49 0.49
31.63 = 1.10
0.66
42.82 1 0.86
GRAPHSAGE
84.22 + 0.38
48.16 1.42
53.34 0.84
H2GCN
86.00 + 2.63
55.85 + 4.92
91.61 + 1.64
57.17 2.57
GCN-LPA
88.96 1 0.68
64.09 4.18
89.53 1 1.07
60.44 4.41
MLP
72.90 1 0.27
31.52 0.52
75.23 0.63
34.29 0.07
DELK
80.25 1 0.11
62.80 + 0.46
83.83 1 1.08
55.16 1 0.67
LANC
83.37 + 0.96
60.77 = 3.51
92.53 1.27
62.85 3.01
GeN
81.61 + 0.25
42.19 0.45
86.48 0.31
49.32 + 0.92
GAT
79.37 0.64
34.67 = 1.87
2.110
43.90 2.90
GRAPHSAGE
82.15 0.49
46.06 = 0.99
89.73
55.25 - 0.42
H2GCN
91.59 + 1.74
76.09 5.96
93.94
65.20 +5771
CCN-LPA
86.92 1 1.13
60.71 3.01
90.75 0.46
58.28 3.02
23

---

Published in Transactions on Machine Learning Research (09/2023)
23 E31 235
Figure 7: Cross class Neighborhood Similarity in DBLP
previous works, we also report the Fl score. As it is a threshold-basee based metric we emphasize that it might be biased when the benchmarked models have different prediction score ranges.
A.6 Cross-class Neighborhood Similarity Plots
In this section, we put the heat maps of the cross-class neighborhood similarity for all the datasets used in this work. We use color coding, where a darker shade in the cell indicates a stronger cross-class neighborhood similarity.
24

---

Published in Transactions on Machine Learning Research (09/2023)
Deegattlng
0.e
1:43
060
001
100
0.00
6.51
002
000 0006
0.00
046
000
100
1:4
6:69
0:90
0.7
8:02
0:99
0448
8:99
0.99 0.99
6:69
0.0
0.99
200
one
0:4
061
0:42
0.09
0.64
051
09
5.90
09
der
8:0 6:x
061 59
8:30
033
000
0.57
0.0
142
290
5:1
0:2
062
000
009
0:54
0:0
006
0:1
000
000
6:30
0:57
0:54
80
UM
11
1:4
0:54
0.09
001
8:00
0:77
6:90
0445
8.00 0.07 (o0d lone
1000
101
100
6.01
00e
000
p0r
064
one
100
2:4
0:99
0m
8:67
251
Ser
b48
648
040
0.
014
0:4
9:4
040
S4T
5:1
5:47
044
0:0
2.0
044
044
844
05
1001
0A4
044
042
0:4
0.00
0:00
2:4
0:80
0.00
0:00
200
0.5
0:5
2:41
0:57
0.54
057
0.00
0.99
0.99
0445
006
057
0.29
0.00
0:7
0064
0.30
030
6.89
00
0.0
0.59
047
048
2:20
6:4
3:40
0:40
0.40
257
02
0:3
054
0M
0:5
2:44
2:55
0:00
0:0
851
3:57
054
020
0:54
0:00
0:00
0:3
0.10
033
037
0:0
0.0
0000
8M
8:3
250
0:8
0:58
3:58
2:43
0:67
0:05
8:00
000
0:00
281
058
050
0:00
3:43
066
0:67
001
8.09
0:00
5:00
000
000
8:00
0:33
0.11
003
06
1.94
6:00
6:0
0:0
000
0:00
8.11
051
500
0:8
0:50
066
2:42
0:03
0:57
0:11
0:03
550
654
0:0
0:68
2:41
8:57
6:57
8:50
3:99
5.50
0:07
8:55
8:00
654
0.30
654
5.53
054
031
2.0
0:5
0:3
0:00
0.54
2:4
0:53
0:52
0.44
8:0
0.44
0:40
6.54
0:33
556
030
053
053
3:53
0:5
8:50
3:7
533
D417
054
034
8:53
0:1
035
0.30 05
033
000
6:3
0.0
0:4
064
0:88
3:57
2:41
881
8:60
0300
8:90
694
1.7
65
0.22
0:58
2:43
6:3
0.58
8:1
8:89
826
835
8:0
632
6:3
8.54
8:0
64
6:9
654
8:5
8.
0000
0.0
051
058
0:33
Figure Cross class Neighborhood Similarity BLOGCAT
25

---

Published in Transactions on Machine Learning Research (09/202)
0.01
6:11
3443
0144
0:43
2:42
01/4
041
0:33
0644
6:51
6.02
641
000
6.44
104
016
0.49
0.93
0/0
6.64
3.90
6.99
0.94
010
2.99
012
011
387
5.94
2:03
012
0.33
300
076
0.64
2.14
0.2
082
034
200
000
0.99
0.54
010
0.03
035
0.03
0.:4
1.00
0.07
070
0.5
07
277
0.7
2.55
012
0.2
0:33
3.73
0/11
639
0:59
0.11
0.5
3.55
0:44
3.55
3.54
647
0:4
0:33
3.00
0.0
0.23
2.2
001
0:44
0:7
371
082
037
0.50
0.09
07
3.00
0.00
0.0
Figure 9: Cross class Neighborhood Similarity in PCG
26

---

Published in Transactions on Machine Learning Research (09/2023)
Hamke
0.33
0.51
0:52
0.41
0.23
0.36
0.7
0.25
0.55
0.52
0.55
0.42
0.37
0.24
0.38
0.35
0.26
0.37
0.57
0.41
0.26
0.38
0.98
0.38
0.57
0.3
0.35
0.19
0.28
0.29
0.39
0.22
0.22
0.23
024
0.19
0.19
0.15
1.17
0.18
0.12
0.18
0.5
0.19
0.14
0.17
0.28
0.30
0.34
0.26
0.3
0.2
0.18
0.28
0.20
0.19
0.24
0.36
0.2
02
0.25
0.25
0.26
0.23
0.22
0.12
0.19
0.19
0.16
021
0.27
0.22
0.15
0.21
0.36
0:27
022
043
939
0.29
03/
0.36
9.2
0.4
086
0.44
0.2
0.88
-02
0.4
0.41
0:41
0.33
0.31
0.19
0.28
0.28
0.22
0.22
0.44
0.47
0.22
0.25
0.36
0.26
0.33
0.3
0.17
0.27
0.27
0.21
0.27
0.36
0.3
0.21
0.0
Figure 10: Crass class Neighborhood Similarity in HUMLoC
27

---

Published in Transactions on Machine Learning Research (09/202))
040
008
000
024
004
60T
9.4
000
081
001
004
643
008
002
293
002
001
604
0.8
022
905
002
653
031
002
00e
11
0.14
008
012
008
012
0.06
6400
045
000
611
0.88
0.1
001
027
0.6
8:55
811
028
9.00
007
838
9.6
0.08
6on
8:1
002
642
048
001
3:22
004
001
001
894
992
021
082
001
832
931
0.01
0.00
6.1
0.00
0.34
000
204
001
000
6:04
0.66
0.0
3.77
001
004
0.4
0:12
0.77
004
0.06
004
8:3
0.44
0.44
0.0
031
0.12
0.4
0.24
0.1
0.0
004
0.0
041
04
0.88
0.0
2.28
004
025
0.44
3.54
0.00
028
611
0.6
6:2
033
0.0
0.0
053
9.16
0.1
0.5
6:2
002
300
047
6:12
0:12
0.0
2.42
002
027
0.02
521
8.14
0.00
015
0.00
223
0.4
0.08
908
0.86
006
008
0.3
Figure 11: Cross class Neighborhood Similarity FUKLoC
28

---

Published in Transactions on Machine Learning Research (09/2023)
E:2
Figure 12: Cross-class Neighborhood Similarity graph label homophily=0.2
29

---

Published in Transactions on Machine Learning Research (09/202))
8:54
2:43
0.10
0100
8:53
5:53
0194
0167
0.80
2:41
1:51
0107
1100
2:99
8#
014
002
105
687
8:5
6.2
0.2
6.93
502
0.3
0:75
0.
031
0.71
0.91
m
0.78
0.26
0.66
6.69
8:90
5.83
0.61
0.66
0.9
5:85
0.63
0.90
2.80
0.99
061
641
6.64
0:03
0:01
0.82
0.90
6.54
8:80
0.4
2.43
0107
2:47
611
067
6.61
0.44
0.63
066
2.81
0.64
0664
2.74
0.6
662
0.22
0.60
5:90
2.
6.73
6:2
5:77
0.70
0.72
0:21
2.79
0.70
2.3
0.79
5.77
3.76
0.75
0.70
2:11
5.00
0.77
075
6:44
0.70
0.2
03
30
5:33
0.7
077
0:31
277
7.70
002
00
2:7
2:70
8.3
0.75
2.11
2.44
001
0755
679
Figure 13: Cross-class Neighborhood Similarity graph label homophily=0.4
30

---

Published in Transactions on Machine Learning Research (09/2023)
or
5:99
0116
0.12
8:73
5:95
0108
0.77
0113
2.90
1.9
1074
0.72
8.79
5.92
0.3
000
6:4
675
671
66
0.5
0.00
6.75
5.87
0.2
0.4
0:44
0.48
0124
6:63
8:04
0.63
0:43
0.86
0.4
0.01
0:43
0.70
6.76
8.99
8:63
0.68
0.74
6:92
6.7'
0/2
0.79
0.74
0/6
847
6.67
0:67
0:00
0.54
0.00
8.71
5.04
0.10
0.7
5.
616
0.7
0:24
5:64
0166
18.77
6.77
2.45
0.75
007
6.6
0.00
631
677
6.48
6.41
2.54
0.22
0.66
6.73
2.67
0.6
6774
0.7
2.43
2.85
0.76
0664
2.74
2:50
071
667
040
5:3
0.22
0:23
8.57
2.1
05
0.5
0:33
2:37
0.56
0.02
0.20
3.25
2.55
0.00
0.00
3.04
2.33
0.58
0.2
0.53
5:03
2.59
022
864
6:33
2:51
2.54
0.0
062
8:07
08
0:57
OC7
8:44
3:57
2:11
0.02
061
8:2
2:22
062
0/3
0:6
Figure 14: Cross-class Neighborhood Similarity graph label homophily=0.6
31

---

Published in Transactions on Machine Learning Research (09/2023)
6.43
8.3
631
028
010
8:13
1:43
046
000
010
1:42
1.49
0000
1002
8:93
5:86
016
003
6:42
6:15
83
024
046
6:00
830
037
8.3
651
616
6:2
024
628
624
1.34
8.18
014
0.6
03
032
022
0.19
606
6.5
8:58
8.37
03
0.6
6.71
8:47
048
8.97
1:00
061
0/3
0.44
0.4
0.38
3.3
0.2
021
041
6:47
030
044
028
032
538
03
0.53
m/8
644
5:44
0:17
078
011
0m
8:47
0:2
011
646
1.65
046
3.54
53
010
6:4
04
2:4
0.2
0.2
043
037
641
8443
238
025
0.5
6:33
2.3
8x2
027
05
2337
2411
060
046
5.77
5.88
056
6/8
032
8:13
233
0.2
0.22
0/0
0.4
0.3
0.27
2.13
0.6
0.30
8:35
5.5
0.77
0.5
0.3
3.25
3.26
0.29
0.20
2.27
5.0
031
628
023
648
022
031
0:33
08"
0/2
6.5
2:33
236
619
0.0
644
232
031
046
04
331
133
0.77
0.2
5.4
520
044
020
540
Figure 15: Cross-class Neighborhood Similarity graph label homophily=0.8
32

---

Published in Transactions on Machine Learning Research (09/202))
044
003
8311
5.9
0.16
0.3
1.44
5.24
022
044
036
1.24
9.27
038
083
8:43
8.66
54
038
624
631
837
6M4
013
028
837
030
615
6:10
6:1
0.43
600
0114
614
615
0:13
8:1
697
0.2
0.66
0:18
511
017
013
0/44
6:27
8.99
0.19
0.6
0.1
6.22
5.9
63
002
6:42
0.8
2.43
3.9
044
0/6
028
024
821
5:11
3.1
022
0.23
6:42
022
0.10
0:3
841
02
616
641
8:3
638
033
0.56
016
0/0
6.4
230
699
045
066
3:21
337
688
087
5.49
599
078
634
699
223
019
012
0.2
018
0.7
6.7
831
014
031
633
835
894
022
023
02
1M4
044
0/6
531
51
0.6
623
831
0.3
233
8.9
0.14
0:11
01
506
007
0.1
6:15
530
000
015
0.2
322
81
211
011
2:7
0.92
013
31
008
6.4
015
038
8.2
024
022
221
54
61
022
823
2.6
016
029
022
335
130
021
011
537
200
027
623
04
Figure 16: Cross-class Neighborhood Similarity graph label homophily=1.0
33


Reviews:
[{"review_id": "rS132Z1kLJ", "reviewer": "Reviewer_h2ys", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Below I list the strengths and weaknesses of the paper. In the weaknesses part, I also include specific questions for the authors.\n\n**Strengths**\n- The main strength of the paper has to do with  the new datasets as well as the graph generator. Both can facilitate future research in the field.\n- Besides, the paper makes interesting observations about the usage of the AUROC metric while evaluating multi-label node classification models.\n\n**Weaknesses**\n- To some extent, the main contribution of the proposed model, LFLF, is limited to an interesting combination of the feature and label propagation components. To be more specific, the feature propagation step is the same as in a GCN model (or the GraphSAGE model). The label propagation component used here is similar to traditional label propagation in semi-supervised learning.  Thus, the novel aspect of the methodology concerns the fusion by attention component.\n- The description of the proposed architecture needs further clarification. First, it is not clear how the model is trained. How are the test node treated during the training phase?\n- Does the model have an inductive learning capability? This point is particularly important point. Therefore, I would propose to further discuss this aspect in the paper.\n- The supervised loss in Eq. (5) has been proposed before in the GraphSAGE architecture to train a GNN in an unsupervised manner. However, to my understanding, it promotes homophily-based proximity. How is this suitable for the proposed architecture?\n- Looking at the experimental results in Table 3, I noticed that the GAT model outperforms GCN in two out of seven datasets. How is this explained? Besides, it seems that LFLF can be used with any message-passing architecture. Thus, I am wondering why LFLF-GAT hasn’t been considered an option here.\n- The paper does not discuss the running time complexity of the model. It would be interesting to address this aspect.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of multi-label node classification using GNN models. Specifically, it makes three different contributions. \n*(Metrics)*. First, it proposes a new metric to measure label homophily in the case of multi-label graph datasets. Four real-world datasets are explored regarding their label properties, having implications for the usage of the AUROC metric.  *(Datasets)*. Second, the paper introduces new multi-label datasets as well as a generator to produce synthetic graphs.  *(Model)*. Finally, the paper proposes a new GNN model that combines feature and label propagation with an unsupervised learning loss. The proposed methodology is evaluated on different datasets, and its performance is compared against different baseline models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please find the questions and requested changes in the 'Weaknesses' part of the review.", "broader_impact_concerns": "No concerns on the ethical implications have been identified.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4z3OD5ybgR", "reviewer": "Reviewer_WHFe", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1- Section 3 on the analysis of the existing dataset and the new datasets is an interesting contribution. The main point made by the authors is that the success of GNN is usually argued in terms of label homophily, but the empirical label homophily computed for existing datasets is pretty low.\n2- In order to understand better the possible reasons for the success of GNN, section 4 introduces a graph generator allowing the authors to tune various parameters like clustering and label homophily. This is a very interesting approach.\n\nWeaknesses:\n1- I have a general problem with the message of this paper. On the one hand, the authors show that the label homophily and the cross-class neighborhood similarity are low in real datasets, and GNN layers should take these facts into account. On the other hand, the authors propose a graph generator with a possible high level of homophily and show that on such synthetic data, their GNN layer (LFLF) is performing better. That's fine, but then what are the practical implications? I understand that LFLF has been designed to work better when homophily is high, but this is not the case in most real-world datasets. Results in Table 3 about LFLF for real datasets are then quite surprising and not explained.\n2- I find it problematic that the analysis of datasets is completely ignoring the features of the nodes. Indeed both definitions 1 and 2 only take into account the graph structure and the labels. Features on nodes are not taken into account. I do not understand why and the authors should explain this choice.\n3- The general writing of this paper should be improved. There are a lot of crucial places where the paper does not define important concepts:\na- in definition 2, define d(i) the histogram properly and define cosine similarity.\nb- on page 8, the description of the multi-label generator is completely unclear to me.\nc- LFLF defined in section 5 is unclear. What is the label correlation matrix? What is the negative sampling distribution? What changes in your model variants?\nd- in your experiments, you should be more precise. I do not understand how you get labels from node embeddings. In Section 5, your GNN learns embedding for nodes; how do you get a classifier from there? Similar question with DeepWalk? For the GCN, GAT... what task did you train them on?\ne- in section 7, how do you vary what you call the feature quality? What is the definition of feature quality? What is the definition of original versus irrelevant features?\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies multi-label node classification on graphs. It starts with analyzing existing datasets by computing the label homophily and the cross-class neighborhood similarity. The authors introduce three new biological interaction datasets as well as a multi-label graph generator to synthesize models with tunable parameters. In section 5, they introduce a variant of GNN called layerwise feature label fusion (LFLF), where both features and labels are propagated through GNN layers and then aggregated with an attention-type layer. The learning task is a link prediction task. Finally, experiments are conducted on real datasets and synthetic ones where LFLF is shown to be optimal.\n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Given the major weaknesses discussed above, I am recommending rejecting the paper. \nHere are some other required changes:\n- overall, the results obtained by DeepWalk are very strong, but there is a more advanced version Node2Vec, and comparisons should be done with Node2Vec\n- in section 3, the authors claim that OGB-Protein is not suitable for experiments because a lot of labels are missing. But then in Section 7, they use this dataset to show that their algorithm is better than others. How did they deal with the missing labels?\n- Figures 1,3, and 5a are histograms; why do the authors use these non-standard plots?\n- Figures for Cross class neighborhood similarity are not readable.\n- on page 5, I do not understand the following: \"Specifically, each node pair(i,j)would contribute a total of 1 units to CCNS similarity over all possible class pairs.\"\n- on page 6, I do not understand the following: \"We in fact observed that increasing the number of training epochs (which encourage the model to decrease training loss by predicting the negative class)increased the AUROC score whereas other metrics like AP or F1 score dropped or stayed unchanged.\"\n- on page 10, I do not understand the following: \"We comment that in our current experimental setup, to save extra computational time, we set Lk=L0 for all k but always update Lk.\"", "broader_impact_concerns": "I do not think there is a need for a BIS.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qPR85OJSau", "reviewer": "Reviewer_7Tut", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n- the paper is generally quite well-written and clear\n- the paper is very complete and explore its topic quite thoroughly\n- the authors propose new interesting insights on graphs with multi-labelled nodes, and the use of node features and node labels\n\nWeaknesses:\n- there is a somewhat lack of rigorousness and/or completeness on several notions and definitions introduced by the authors. Especially on the (few) mathematical formulations: objects are generally vaguely defined, no dimensionality is given, many notions and notations are not defined and can be ambiguous, etc.\n- For instance, the very definition of multi-label is not given: is it that, among a set of labels, a node can have several, or is it that each node is associated to a multidimensional label vector, with several number of classes for each coordinate? (I deduced that it is the first one, but it took me some back and forth reading). In this light, Def. 2 is quite not clear (what does $i \\in V_c$ means in a multi-label context?).\n- As another example, the authors should mention from the beginning which task they are adressing: I'm guessing semi-supervised learning? Transductive? Inductive? The training of the the proposed GNN is unclear: why is it a good strategy to consider purely an unsupervised graph reconstruction loss? If no label are available (inductive settings), what it the advantage of doing label propagation?\n- Similarly, in the random model, it took me some times to understand that the $x_i$ were the continuous points in the hypersphere, playing the role of node features, and not the labels, since $d(x_i,x_j)$ refers to a distance between labels! By the way, in the many existing Latent Position Models (LPM) of random graphs, it is much much more classical to consider a true distance between the $x_i$ and not the labels. Some discussion with the literature is needed here.\n- the authors mention several times the problem with the AUROC approach, but do not give true mathematical justification. Some more details would be nice.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors make several distinct contribution on the topic of multi-label node classification in graphs. They first revisit the notions of homophily and neighborhood similarity, which are generally associated with the success (or failure) of GNNs. They analyze some existing datasets under this light and comment on some discutable choices made in the literature. Then, they propose three new curated datasets of biological data for multi-label node classification. Next, they propose a simple random model for generating graphs with multi-labelled nodes, with some adjustable parameters. Finally, they propose a novel variant of GNNs that use both features and labels as input, with some attentional mechanism between the two, and benchmark several baselines and models on multi-label tasks.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above. The paper has merits, but suffers from a lack of rigorousness and completeness that would greatly improve the reading.", "broader_impact_concerns": "N/A. New datasets are provided, but new data is not collected, only curated. Sufficient reference is given.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)