Formulating Node Labelling as Node Classification or Link Prediction in Different Graph Representations
Authors: Tobias Möller
Borun Shi
Venue: Accepted by TMLR ()

Abstract: Message-passing Graph Neural Networks (GNNs) are increasingly used for predictive tasks on graphs. Much work has been done to improve GNN architectures, but how the actual data graph should be designed is not well studied. In this paper, we investigate how two different graph representations impact the performance of GNN models across datasets with varying characteristics grouped by homophily, heterogeneity, and number of labels per node. A unique phenomenon is that the same abstract predictive task of labelling nodes is formulated as a node classification problem on one representation and as a link prediction problem on the other. Our work is the first to blur the line between these two basic and fundamental tasks in graph learning. Our experiments on 12 real-world datasets suggest that different representations (and tasks) are optimal for different datasets, models, and hyperparameters. We derive empirical heuristics of choosing between the two and pave the way towards a criterion of choosing the optimal graph representations and towards formally understanding the interconnection between node classification and link prediction.

Published in Transactions on Machine Learning Research (07/2025)
Formulating Node Labelling as Node Classification or Link Prediction in Different Graph Representations
Tobias Möller*
tobios Aibias@moller.see
Institut Polytechnique de Paris
Borun Shi
brian.shi@@eenn com
Neo4j
Reviewed on OpenReview:
htips: // openreview. net/ met/ forum? id- LK7t jysjss
Abstract
Message-passing Graph Neural Networks (GNNs) are increasingly used for predictive tasks on graphs. Much work has been done improve GNN architectures, but how the actual data graph should be designed is not well studied. In this paper, investigate how two different graph representations impact the performance of GNN models across datasets with varying characteristics grouped by homophily, heterogeneity, and number of labels per node. A unique phenomenon is that the same abstract predictive task of labelling nodes is formulated as a node classification problem on one representation and as a link prediction problem on the other. Our work the first to blur the line between these two basic and fundamental tasks in graph learning. Our experiments on 12 real-world datasets suggest that different representations (and tasks) are optimal for different datasets, models, and hyperparameters. We derive empirical heuristics of choosing between the two and pave the way towards critcrion of choosing the optimal graph representations and towards formally understanding the interconnection ween node classification and link prediction.
1 Introduction
Message-passinn Graph Neural Networks (ONNs)(Hamilne et al., 2018 Veličković et al. 2018 Kipf & Welling 2017) have been proven to be effective for analyzing graph-structured data and are widely used in numerous domains (Zhou et al. 2021 Hamilton 2020
Two of the common tasks on large graphs are node classification (NC) and link prediction (LP). Identifying fraudulant accounts in financial transaction network Wang al. 2023), assigning academic papers with subject categories in citation graph MMcCallum et al. 2000) and classifying types of businesses or products in Web-based graph (Zeng et al. 2020) are typically defined as NC problems. Recommending friends and users to follow in a social network Kishky et al. 2022) and predicting missing physical or chemical associations in biomedical graph (iishatt et al. 2017 Szklarczyk et al. 2019) are typical LP problems. These tasks are formulated nol only on homogeneous graphs, but also on real-world heterogeneous graphs that have rich node- and edge-type information as well feature attributes. Several extensions of classical GNN models
explictly leverage heterogeneity Wang et al. 2019 Chen & Chen 2021 in an attempt to improve lcarning performance.
Although GNNs have shown good performance for NC and LP on variety of graphs, there are also known issues such as over-smoothing! Rusch et al., 2023)) and over-squashing Topping et al.] (022) which limit the expressiveness of GNNs and consequently their performance. The root cause stems from the fact that the computation graph is exactly the same as the data graph, which allows GNNs possess strong inductive bias. Rewiring methods methods(Topping Topping et al. 2022 Arnaiz- Modii--odriguez al. 2022 that usually involve adding
* Work done while the author Neo4j.

---

Published in Transactions on Machine Learning Research (07 (07/2025)
edges virtual nodes have been introduced. There is also bag of tricks Wang al. that incrementally improve GNN performance.
2021 Chen et al.
2022)
Despite all the progress, very little effort has been put into how the data graph should be represented in the first place. Existing work benchmarks on predefined NC and LP tasks on the given representations of datasets. However, there no canonical way of constructing the data graph and there are numerous ways of representing the same abstract information. Consider the example of modeling users tagging music with genre in graph, one could define User and Music nodes, and assign Tag edges with properties being one-hot encoding of genre. An alternative might be having User, Music and Genre nodes, and assigning User-Music- Genre hyperedge (an edge connecting three nodes). The optimal representation (or schema) depends on the workload, downstream models, and predictive tasks.
B
c
B
(a) The node classification representation: A graph Gi where the specific information is stored as node features in every node.
(b) The link prediction representation: graph G2 where the specific information represented by nodes different types connected with new edges.
Figure Two ways of representing the same abstract graph G. Colors represent different node and edge types. Letters represent information about nodes.
In this paper, systematically compare representations that general and fundamental, shown in Figure When we have discrete properties about the nodes, could represent them as labels on the nodes (Figurdl la or as distinct nodes with edges connecting them (Figure Ib]. This means that for a predictive task on the discrete properties, the lask is formulated as NC using the data graph in Figure la while it becomes LP using the data graph in Figure [b] Note that even the formal task differs; a phenomenon of these two representations. This implies that such a decision of picking the data graph early the machine learning pipeline has profound impact, since entirely separate training and testing processes, such as data splits and metrics, well as model architectures, can be used and compared across NC and T.P for the same end problem. Concretely, investigate the following research questions:
How do different representations of the same abstract graph afTect the performance of a predictive task defined on it?
What the characteristics of graph that determine whether node classification representation link prediction representation is preferred?
Contributions. We give answers to the research questions by evaluating how well different GNNs perform across a wide variety of graphs using NC and LP representations in the transductive setting. We make three key contributions:
We pose the basic and important question of how the abstract graph should be represented and highlight two general and fundamental representations where even the formal predictive task of NC and LP differs for the same end problem.
We rigorously map out ways to fairly examine NC and LP representations by defining comparable data splits, evaluation metrics, negative sampling (as unique step of T.P) and model architectures.
We conduct extensive experiments using datasets of varying characteristies based on homophily index, level of heterogeneity, and number of labels per node.
2

---

Published in Transactions on Machine Learning Research (07/)025)
Our results show that the optimal representation varies for different datasets and depends on the specific GNN used. Although most of the existing benchmarks adopt the NC representation by default, we found that the LP representation indeed sometimes yields better results in fair comparisons. For example, we found that GraphSAGE(Hamiltor et al.) 2018) is consistently better on the LP version of widely benchmarked ogbn- al. 2018) on L.P versions of DBLP(multt) (Akujuob) ct al. 2019) and CiteSeers(Giles et al., 1998). Our work implies that the question of constructing optimal data graphs shall not be ignored and simply using the default representations in benchmarks is insufficient. Our result provides the groundwork for future research towards formal and general criterion of designing optimal graph representations and a new perspectives which unifies node classification and link prediction.
arxiv et al. 2020) and similarly GAT GAATVVelikovii
2 Preliminary
Definition 2.1 (Graph)- A graph 9 = (V,A, consists of a set of nodes V, a set of node types A, a set of edges T _ V x x V, and a set of relation types R. Each node e E V has one or more node types a(v) S A. Each edge (vi, r, u/) T, has a relation type r E R which specifics the type of relation between nodes 02 and By. Each node a has an imitial node embedding 2v Rd for some dimension d.
Features for all nodes are abbreviated as X E Rl A homogeneous graph has |A| = | = 1. Let L be a set of labels for the nodes. The partial labelling function L V. + P(C) \ 0 assigns some of the nodes their labels. Let Vy be the domain of L. V C represents the subset of nodes that are labelled. If the graph is not multilabeled, then [[(x]| for all defined Vz.
Definition 2.2 (Transductive Node Classification). Given a graph G with node features X and a partial labelling function L where Ve C V, we want to assign labels to the nodes in Ve by some flg.x. : V. P(C).
Definition 2.3 (Transductive Link Prediction). Given a graph g with node features X and an incomplete set of odges T C V x R V, we want to predict new set of edges T' c xV CV R x V) T by some flg.x T (0,
Definition 2.4 (K-hop Homophily Index). The K-hop homophily index Bx of a graph is given by
1
lu E (K)( L())) Iu Eu
8K
FEV
N (K) is the K-hop neighbourhood of u that includes all nodes that are connected to with some path of length at most K. When K K= 1 and the graph is single-labelled, our K-hop homophily index reduces to the common homophily index 3 that measures the proportion of nodes that share labels with their neighbours defined in Pei et al. (2020).
2.1 Graph Neural Network
A message-passing GNN iteratively aggregates node embeddings from a node's neighbourhood and updates embedding. These embeddings are initialized as some feature vectors of the nodes. The embeddings and learnable weights are optimised with some objective on the graph. Formally, the message passing step Gilmer et al. 2017 is
h (k+1) ( (1.4)) ACGREGATE ((h(), (u Vu e e((6)))
(1)
MEAN, MAX, MIN are commonly used for AGGREGATE. UPDATE is usually some differentiable non-linear func- tion, such as UPDATE(x, y)= oWW1 x + W2y) with non-linearity a and learnable weights W1, W2. Note that the neighbourhood function N (ww) does not have to include the full neighborhood of GraphSAGE (Hamilton et al. 2018) samples the neighbourhoods to improve model scalability. GAT CAT et al. 2018 learns attention coefficients between pairs of nodes. AGGREGATE being set-function ensures the embeddings are
3

---

Published in Transactions on Machine Learning Research (07 (07/2025)
permutation equivariant. CCN(Kips & Welling 2016) defines the message passing step the first-order ap- proximation of localized spectral filters. GIN et al. 2018) is an architecture that is provably expressive as the classical WL-test WL-test/Weiifeil Weisfeiler & Lehman
1968) in separating non non-isomorphic graphs.
Since the computation structure directly follows the underlying data graph, a strong inductive bias of the underlying graph is baked into the model.
Equation [ could be applied to heterogeneous graphs by simply ignoring the node and edge type informa- tion. A natural extension that takes advantage of heterogeneity is to apply Equation separately for each triplet type A x R. x A as distinct channels, effectively treating them as separate homogeneous subgraphs, and aggregate the messages at the node level. A pictorial illustration of the computation graph is given in Appendix A.1 WAN(Wang et al. 2019) and MAGNN FFu et al. 2020) use predefined metapaths (list of node and relation types) to induce metapath- induced neighbourhoods as another way to explicitly leverage heterogeneity.
3 Node Classification and Link Prediction on Two Representations
Given graph 9 (V,A,T, and the partial labelling function L: P(C), we define our representations formally, There are many different representations that can encode the same information specified by G. The same end task may may not be defined in the same way, depending on the concrete representations. Among many different ways of representing G for various predictive tasks, we will focus on studying the impact of using the NC representation (Figure Iab and the LP representation (Figure 1b for predictive tasks on nodes in the transductive setting.
3.1 Description
Definition 3.1 (Node classification representation). Gvc = AV, is our data graph.
Definition 3.2 (Link prediction representation). GLP CLp=(VUL)) (U),, TUT", RU()() is our data graph. C is a now set nodes disjoint from the original set, VnL 6. is a new node type where a(v) = * for all v E x' is a new edge type. T' = ((v,*' x11) : : V, C. L(u) e I/].
With these definitions of concrete graph representations, we can define learning tasks on them. We will define PNO to be the node classification task on GNC, and PLP to be the link prediction task on GLP. Definition 3.3 (Pxc: Transductive node classification on GNC). Given GNe with node features Xy and partial labelling function L, we want to learn fl, : V\VV + L.
Definition 3.4 (PLP: Transductive link prediction GLP). Given GLP with node features Xvuc. We want to learn boolean function f'G2r.x (V {+'} L) \ T" + (0, The set { E V, [r, * 1) = }} therefore represents the predicted edges.
The learned function flG X. from task Pno using GN naturally answers the questions on assigning labels to unlabelled nodes in G. We can interpret the output of fla.r. function fla..x V Ve - P(C) where f(N) 3 > f(u, x'1) 1. flGLex therefore solves transductive node classification in Definition 2.2 GLP introduces linear overhead in terms of parameters and time complexity to GNC. An example detailed
analysis is provided in Appendix A.6
A.7
3.2 Graph Data Splits
Now that we have defined the two tasks PNC and Pt. on two graphs Gve and GLe, we need to define how splits can be done so that trained models are generalisable (to assign labels for nodes). In order to measure the impact of different representations, we need to ensure that the splits are comparable.
The split for PNo on GN simply partitioning the train, validation, and test set where Viaain Vnatid U Viest Ve where the random partitioning is determined by some seed. While the computation graph provided by GLP is different. from that of GNC, need to somehow ensure that the information available
4

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
A
?
B
(a) GNe with Vusin-
(b) GNC with Vval.
(c) GNe with Vieat
B
(d) Gep with Tunin mp in solid lines and Twain sup dashed lines.
(e) GLp with Teat mp in solid lines and Tvat Teat_aup sup in dashed lines.
(I) GLP with Tins up in solid lines and Tust_ sup in dashed lines.
Figure 2: An example of equivalent splits for Pwo GxC and PLP on GLP. The graph g has 5 nodes and 4 edges with all nodes having some label. (a)(b)(c) show the partition of V into Virains Veat, Viest in the GNe representation. (f) show the message- passsigg and supervision edge splits in GLP, created according to Equation 2
for training the models remains equivalent. This allows comparisons to be made purely on the representations of the information.
The split is less apparent for GLP. The set of edges in each split is further divided into message-asssngg edges (for the computation graph) and supervision edges (for the objective function). Thus, the training data partitioned and used by the learning method two different ways, with the partition ratio being a hyperparameter.
Given any Virainy Voalid, Viest for GNC, we construct the set of edges for GLP and their message-passing and supervision subsets as:
T Tirain = +1) L(v) a BLAVE Virasnd: Tirain mp UT
UT -train_sso Stupin_sup sup
= Th Tirains T Traain mp T tup sup = 0 (2)
T Terain mp = T'rain mp UT, Ttrain sup = T T
(3)
Touldd my Terain my U Uiroiin supt Tvalid_eup sup {1V, x,,') L(v) e aIAVE Vvatial
(4)
Thest mp = Tealid mp U Tealid eups Trest_eup {1v, (]) L(v) e SIVEE Vieeth
(5)
Tirain_ mp and Ti Tirain_sup Equation 2 are partitions of Tirain according to some supervision ratio hyper- parameter. Terain_ ma are the musssage-psssing edges, used in the forward pass during training, which means they are used to determine the neighbourhood N in Equation I Terain_een sup the supervision edges, which the positive samples.
are used by the objective function (typically cross-cntropy)
Note that as a phenomenon of the equivalence of PtP and PNC for solving the same end task on different graph representations GLP, GNc, a unique new step appears since the models solving PLP use information from the graph topology for both the computation graph and the objective, whereas for PNc, only the computation graph is based on the topology. An illustration of the equivalent splits is shown in Figure 2
ressage-passing and supervision data splitting

---

Published in Transactions on Machine Learning Research (07/ (025)
3.3 Negative Sampling
The existence of supervision edges ensures a model generalises beyond seen edges and is able to predict new ones. However, without negative data present in the learning process, the models are likely to converge towards classifying all edges as positive. Since the graph topology is used explicitly as the computation graph for inductive bias in the architecture, as a unique advantage of GNNs, negative samples are normally utilised by the objective function (e.g binary cross-entropy).
There is rich literature of negative sampling techniques (Nguyen & Fang 2024 Ying et al. 2018 Yang al, 2020) for the general link prediction task (of the abstract Definition 2.3 where heuristically 'representative and difficult" node pairs are chosen negative edges. However, for our PLP GLP, only want to learn function flo.r. over (V x x x L) TT (i.e between the V nodes to the L nodes) and not the entire () x (+') x (VUL). C). As a result, we indeed have a true set of negalive samples ((v,+',1) v E Ve A L(u) & I.. We do not require any negative samples (nor supervision edges) over the subgraph V x R.
4
Experiments
We experimentally compare how the two different representations and tasks perform on variely of 12 real- world datasets and 7 synthetic graphs of different characteristics, using two backbone models (GraphSAGE, GAT) and their heterogeneous extensions as specified in Section 2.1 (Appendix A.1) All experiments use a T4 16G GPU and our code is available on Github
4.1 Setup
For each dataset G, and for every seed, an 80 80/10/10 split is obtained on GNC and the equivalent split is created on GLP following Equation 2
30% of the label edges Tirain are encoded as message- passing edges Troin mp: the remaining 70% of Train are used as supervision edges Traai sup The mutual paeemmaarestess (number of epochs and learning rate) and the optimizer (Adam) are the same in both cases. Early stopping is applied on the validation score. The test score with the highest validation score is recorded. Batching is used on larger datascts. For GLP, make sure that all the L nodes are present in every batch.
3 4
Accuracy is calculated for single-labeled datasets, and average precision (AP) is used for multi-labelled ones. We report the average scores for each task cask/representation and model on cach dataset together with the standard deviation. We report a direct comparison of scores for each fixed split and model, on the two representations, and calculate the ratio of LP being better than NC in column <. We also report the p-value of the statistics of the NC and LP models, calculated with the independent two-sample unequal-variance t-test (Welch's t-test). Whenever p < 0.001, we mark it as 0 in the tables. Small values of (< 0.05) indicate the scores are statistically different, which means we can conclude that the different representions lead to different prediction performances. Additional experimental details are specified in Appendix A.2
4.2 Datasets
We compare three sets of real-world datasets that exhibit different levels of homophily, heterogeneity, and number of labels per node, to identify generalisable trends that correlate to specific dataset characteristics. We additionally use set of generated random graphs to validate the heuristics we observe.
For homophilic and heterophilic data, six datasets from Rossi et al. (2023) with varying degrees of 1-hop homophily index were used. The homophilic datasets are CiteSeer (Giles et al. 1998 Bojchevski & Gün-
nemann 2018), Cora-ML. (McCallum al. 2000 Bojchevski & Günnemann, 2018 and ogbn-Arxiv (Hu)
et al. 2020), and the heterophilic datascts are Chameleon (Rozemberczki et al. 2021 Squirrel (Rozember-
czki et. al. 2021), and Roman- (Platonov et al., 2024). We additionally provide statistics of K-hop
homophily index and neighbourhood sizes for them in Appendix A.3 (Table 9 10
1Github:

---

Published in Transactions on Machine Learning Research (07 (07/2025)
GraphSAGE
GAT
NC
LP
P
NC
LP
CiteSeer
96.36 0.90
94.39 + 1.02
0
90.02 0.94
04.54
100
0
Cora-ML
88.63 1.18
86.00 + 2.80
0
0.018
86.60 + 1.86
84.57
0.025
OGBN-Arxiv
69.53 0.32
72.17 0.30
100
0
69.76
7
60
0.107
Chameleon
65.13 + 2.60
#7.5433.3
0
0
73.38
67.76
Squireel
43.88 = 1.66
40.88 + 1.09
20
0.012
44.73 2.54
38.15 2.26
0.002
Roman Empire
78.18 + 0.69
76.37 + 0.92
0
0
62.07 + 1.09
56.02 + 4.01
10
Table 1: Test scores on the homophilic and heterophilic datasets, using models with two layers. < represents
the percentage of runs where GLP is a better representation than GNC- p represents the p-value, we report whenever it is smaller than 0.001.
GraphSAGE
GAT
NC
LP
<
p
NC
LP
p
CiteSeer
95.86 + 0.85
95.44 +: 1.08
50
0.347
90.12 :: 1.44
94.35 + 0.87
100
Cora-ML
87.37 1.49
82.33 + 4.73
0
0.008
+4.00
20
0.342
OGBN-Arxiv
70.37 0.32
72.14 0.41
100
0
69.84:
65.59
Chamelcon
63.95=4..
556.93 2.79
0
0
73.16443.28
50.5613.79
Squirrel
44.12 2.47
37.73 + 2.59
0
0.004
42.15 2.64
31.96 4.01
0.002
Roman Empire
78.99 + 0.65
74.47 + 1.22
0
0
43.67 1.79
37.05 = 3.55
10
Test scores the homophilic and heterophilic datasels, using models with three layers. < represents the percentage of runs where GLP is a better representation than GNe- p represents the p-value, we report 0 whenever it is smaller than 0.001.
Table 2:
Heterogeneous datasets are ACM, DBLP, and IMDB from Wang et al. (2019) and multi-labelled datasets DBLP-multi (Akujuobi et al. 2019). BlogCat (Tang & Liu 2009), and Yelp (Zeng et al. 2020).
All of the datasets by default adopt the NC representation and NC benchmarks in the original work. All datasets in GNe form have node features Xv. except BlogCat, which we initialise randomly, For BlogCat, we also found that the split from Tang & Liu (2009) is the only split where the score remained consistent instead of random splits. We initialise Xe for the
the training, validation, and test sets, which C nodes in GLP with onc-hot encodings.
4.3 Results on Homophilic and Heterophilic Datasets
Tables 1 and present comparisons between NC and LP on homophilic and heterophilic datasets. Both models consistently perform better on the NC representations for heterophilic datasets. This is perhaps counterintuitive since the extra edges 7" in GLP directly connect the lamella nodes far apart in G For homophilic datasets, we observe that GAT on CiteScerLp performs better than with CiteSeerne- This gap can be as significant as +4%. Furthermore, the advantage of CiteSeer observed consistently across every scod (with LP NC at 100%).
More interestingly, two-layer GraphSAGE perform better the LP representations of the widely bench- marked ogbn-arxiv datasets, opposed to it's default NC presentation. A similar trend is observed with two-layer GAT, although the increase of GAT on ogbn-arxivep to ogbn-arxivnc is not statistically significant (p (p=00 0.107.. The highest average score is obtained by GraphSAGE on ogbn-arxivi.p The behaviour of three- layer models varies significantly. For example, GAT on agbu-arxivne obtains consistent scores when using two three layers, but drops significantly on ogbn-arxiv1, with thrce layers. The behaviour is different for GraphSAGE, where two- and three-layer GraphSAGE consistently and on average performs better on ogbn-arxivi. than ogbn-arxivNC-

---

Published in Transactions on Machine Learning Research (07 (07/2025)
NC
LP
<
p
DBLP (single)
93.15 + 1.13
93.45 + 1.61
50
0.636
IMDB
67.99 + 2.26
56.80 + 3.27
0
0
ACM
92.15 + 1.71
36.39 + 6.83
0
Table 3: Test scores on the heterogeneous datasets with HAN as the model. < represents the percentage of runs where GLP is a better representation than GNC- p represents the p-value, we report whenever is smaller than 0.001.
GraphSAGE
GAT
NC
I.P
NC
L.P
P
DBLP (multi)
93.41 + 0.55
94.24 + 0.26
100
91.46 + 0.41
93.36 + 0.32
100
0
BlogCat
99.83 + 0.21
11.94 = 1.20
58.08 + 0.95
9.05 = 2.07
0
0
Yelp
62.32 + 0.55
39.21 2.80
0.003
42.59 0.75
26.34 + 1.09
0
0
Table 4: Test scores on the multi-labelled datasets, using models with two layers. < represents the percentage of runs where GLP is a better representation than GNC- p represents the p-value, we report whenever it is smaller than 0.001.
4.4 Results on Heterogeneous Datasets
We experiment with fundamentally heterogeneous datasets and melapath-based heterogeneous GNNs to understand whether the NC and LP representations make difference in this case. Performance results for heterogencous datasets using HAN are summarized in Table 3 LP and NC achieve comparable results on DBLP (single). In contrast, NC significantly outperforms LP on IMDB and ACM. The detailed dataset description and the metapaths used are specified in Appendix A.4
4.5 Results on Multi-labeled Datasets
Results Tables and 5 demonstrate that both two-layer models perform better on DBLP(multi)uP than on (BLP(mulli)xc: and both three-layer models achieve comparable results on the two representations. For BlogCat and Yelp, NC outperforms LP. The extremely large gap shown by BlogCat is not surprising as the dataset is particularly sensitive to splits.
4.6 Results Random Graphs
We plot distributions of the node degrees of the 12 real-world datasets in Figures in Appendix A.3
We obscrve pattern in that most of the real-world datasets which LP performs better (CiteSeer,
OGBN-Arxiv, DBLP (multi)) are sparse with many low-degree nodes and few exremely high-degree nodes.
GraphSAGE
GAT
NC
T.P
p
NC
L.P
DBLP (multi)
93.68 + 0.42
93. 78 0.49
80
0.63
91.63 + 0.49
91.57 + 0.39
60
0.766
BlogCat
99.58 + 0.29
12.59 1.81
34.00
1.86
11.36 1.32
Yelp
61.41 0.62
37.77 3.02
0.004
40.83 0.53
27.05 1.02
Table 5: Test scores on the multi-labelled datasets, using models with three layers. < represents the percentage of runs where GLP is better representation than GNC- p represents the p-value, we report 0 whenever it is smaller than 0.001.
8

---

Published in Transactions on Machine Learning Research (07/2025)
GraphSAGE
GAT
NC
L.
P
10-1000-10-homm
91.43 5.95
90.0 + 6.88
0.625
92.30 + 5.30
90.0 + 6,19
0.384
bb-100-100 10-0000----p---
84.29 5.65
82.85 5.71
10
0.578
83.81 6.10
84.29 + 5.65
10
0.858
sbm-5-20-50
78.50 1::00::00 8.96
74.50 = 11.5
50
0,398
84.50 + 10.11
75.00 + 10.72
10
0.056
sbm-5-1-50
75.0 9.21
78.0 13.8
0.575
81.0 1 8.31
66.0 8.31
sbm-1-0.2-1000
57.2 2.49
89.8 = 1.14
100
89.7 1.23
7.79
0.001
sbm- 1om-1-0.2-1000
61.4 = 2.31
89.6 - 1.77
100
89.3 1.39
81.8 + 4.29
10
0bm.00.50005-20000
60.32 + 3.81
90.69 0.51
100
90.51 + 0.58
85.89 + 6.32
10
0.046
Table 6: Test scores on the random graphs. bb-ma-my-mode represents a barbell graph of my clique sizes and m2 path length with mode either hom or splil. Moon--Pame-Piii--loookee
represents a sbm graph of four blocks of blocksize number of nodes, Psame x 10 probability of edges in a block and Pair Paix x10= probability of edges across block. When Psame > Paiff the graphs are generally homophilie. When Psame < Paiff the graphs are generally heterophilic. Two sbm-1-0.2 1-10000000000000 graphs are generated with different seeds.
(a) I-hop ego graph (colored by true label) of node 720.
(b) 2-hop ego graph (colored by true label) of node 720.
Figure 3: Example one-hop and two-hop neighbourhoods of a node id 720 in the sbm-0.5-0.05-200 graph in GN representation. Node 720 is highlighted in black. Nodes share the same label are in lightblue. Nodes of the other label are in orange.
Heuristically, there seems to be trend of LP is sometimes better than NC on sporse and weakly homophilic graphs with few high-degree nodes. We extend our experiments to a set of random graphs generated under different distributions and various label assignments.
A barbell graph consists of two cliques of my number of nodes connected by a path of length m2- We assign binary labels with a method hom, where each clique with half of the path being one label. We assign binary labels with another method split, where both cliques label. Both methods produce homophilic graphs. A stochastic block model (sbm) graph consists of blocks with probabilitics Psame and Paift of creating edges over nodes of the same and different blocks respectively. We create sbm graphs with four blocks of varying sizes and edge probabilities. We assign binary labels: one label for two blocks of nodes, and another label for the other two blocks. We randomly flip node labels for 10% of nodes for all graphs. While the graph generation and node labelling process is random, the graph function learn is non-trivial. The label flipping introduces additional noise which the models need learn to not overfit We generate all GNG graphs and transform them into Gte.
assigned the same label, and the path the other

---

Published in Transactions on Machine Learning Research (07 (07/2025)
LPA
NC
LP
p
CiteSecr
98.71 + 1.67
93.59 1.56
10
0.873
Cora-ML
87.03 2.11
86.87 2.03
0.859
OGBNN-rxiv
7
73.27
20
0.626
Chameleon
40.13
39.65 3.99
10
0.792
Squirrel
30.23
29.90 = 1.54
10
0.647
Roman Empire
5.56 + 0.33
5.52 + 0.39
50
0.810
DBLP(multi)
90.05 0.41
91.08 0.41
100
BlogCat
13.43 0.18
16.97 0.31
3
0
Yelp
32.47 = 0.18
32.08 = 0.17
0
0
Table 7: Test scores using LPA with three layers. < represents the percentage of runs where GI. p is better representation than GNc- represents the p-value, we report 0 whenever it is smaller than 0.001. Note that the LP column represents rumning LPA on variant of GLP to classify the original set of nodes, therefore not solving the link prediction task.
Our result is shown in Table 6 Similar trends observed in real-world datasets can be found again. For example, NC is better for dense (homophilic) graphs bb-100-10-*. For sparse and weakly homophilic graphs such sbm-0.5-0.05-20000 LP is +-30% better for GraphSAGE than NC on average and for every split. As the graphs become more sparse, the performance of GAT improves LPP but not NC. As an example, we plot in Figure 3 the one-hop and two-hop neighbourhoods of a particular node in sbm-0..-0.05-200000 LP classified correctly but not NC with GraphSAGE. The interpretation is that while the node is homophilic (over both one and two hops), there is still a portion of nodes of the opposite label. However, under the GLP representation, it's two-hop neighbourhood of sabellabelled nodes will explode disproportionately. This dominant scaling of neighbourhoods over higher k-hops imply more message passing from same-labelled nodes in GLP.
which
4.7 Results on Additional Models
In addition to GraphSAGE and GAT, there are many other alternative models as well as classical algo- rithmns that can used to label nodes. One such example is the label propagation algorithm (LPA) (Zhu & Ghahramani] 2002). Message-passing GNNs could be viewed as a continuous extension of LPA where the propagation and aggregation functions are parameterised and learnt. LPA is fundamentally a node classifi- cation algorithm that cannot solve PLP. However, we still apply LPA all the labels on V, and solve the node classification problem on the subset of nodes V (and not the L nodes). In this setup, the added C nodes and 7" edges according to Definition 3.2 are simply rewiring the graph. We run LPA on the homopphllic/heterphhiit and multi-labelled datasets and report the results in Table 7
variant of GLP, by keeping
The performance of (3-layer) TPA closely positively correlate with the level of (3-hop) homophily in- dex (Appendix A.3 Table D on both Gxc and the rewired GLP. Perhaps surprisingly, for all the het- hoohiiic/hooohhiiic datasets, LPA yields comparable results (any difference is statistically insignificant). However, LPA performs better the rewired GLP graphs for DBLP(multi and BlogCat. Studying LPA on GNC and GLP will likely offer intermediate insights towards formally and fully bridging PNC and PLP-
We also experiment with GCN Kipf & Welling 2016) and GIN et al.) 2018) which are common GNN baselines. However, neither models work out-of-ther box on GLP since they are unable to handle heteroge- ncous graphs. We describe in detail the nccessary modifications as well as experimental results for GCN Appendix B and for GIN in Appendix C Neither model yields insightful results for PLP likely due to the adhoe heterogeneous adaptation we have to make.
10

---

Published in Transactions on Machine Learning Research (07/2025)
GraphSAGE
GAT
LP
4
LP
1 A
CiteSeor
95.34 + 0.97
0.1%
94.06 + 1.49
0.29%
OGBN-Arxiv
69.63 1.52
2.51%
59.84 5.23
5.75%
Roman Empire
66.19 + 1.86
8.28%
34.74 = 5.65
2.31%
Table 8: Test scores when using 80% message-passing edges, [T train_mpp /rrrtrrrmmna A represents the changes in average scores.
8/2 instead of 3/7.
4.8 Hyperparameter Analysis
There is a spectrum of model architecture and learning hyperparameter choices that impact the performance of different. models solve PnC on GNC and PtP on GL.. hyperparameter unique to LP but not NC is the training message-passingg and supervision edge ratio. Table shows the results when we use 80% edges for message passing instead of 30%. We also examine the impact of embedding dimensions in represenlative datasets in Appendix A.5 Table 12 Variations for different datasets validate that the common impact of hyperparamcter choices carry over to the different graph representations.
5 Related Work
Rewiring. There are several recent works that modify the computation graphs from the underlying data graph in order to remediate over-smoothing or over-squashing effects of GNNs, or to improve empirical performance. Topping et al. (2022) reduces over-squashing by removing bottlenects the graph by examining their curvature, Barbero et al. (2024) improves connectivity while preserving locality (distant nodes are kept separate). Qian et al. (2024) introduces virtual-nodes that allows efficient message passing over originally long-distance nodes. Rossi al. (2023) show that treating heterophílic graphs directed can improve the performance of GNNs when they are appropriately extended to directed- GL-G. The approach of rewiring often introduces nodes edges that are not part of the data whereas we take the perspective of considering different data representations on an abstract graph. Unique to our two representations, the appropriate formal task becomes different, whereas none of the rewiring methods affect the end task.
Using label information. Our LP representation encodes the label information of nodes as new nodes and edges in the concrete data graph itself. There are several other works that utilise node-label information for learning. Wang et al. (2021) combines node label and feature information together by propagating them in parallel. This approach dates back to the classical label propagation algorithm (Zhu & Ghahramani 2002) extending them by introducing traning-free GNNs that approximate label propagation.
with Sato 2024
Node classification and link prediction. There is very limited work that connects these two basic and fundamental learning tasks on graphs. Fadace & Hacri (0019) are the first to point out a connection between classification and link prediction. They propose an algorithm that labels Fuclidean data by using k-nearest neighbour create graph and apply a variant of the Adamic-Adar index constructed graph. Our work could be considered graphs, in particular
index(Adamic Adamic Adar 22003) on the extension of their work to the context of learning step towards answering the general question of how representations affect cyessag--passing GNNs. Abboud & Ismail îlknn Ceylan (2021) studies jointly the task of transductive node classification over incomplete graphs and link prediction over graphs with node features.
Wu et al. (2022)
Bilgic et al. (2007) similarly jointly learns node classification and link prediction. Daza et al. (2021) evaluates
entity representations that are learnt with I.P objective.
6 Conclusion
In this paper, we investigate how different representations of the same abstract graph affect the performance of predicted task defined on We study one of the most common predictive tasks of labelling nodes. It turns out that among many different possible general representations, one could assign nodes with labels
11

---

Published in Transactions on Machine Learning Research (07 (07/2025)
and formulate the task as node classification problem, or construct new label-nodes, with edge connections representing label assignment to other nodes, thereby formulating the task a link prediction problem.
Our work makes a connection between two basic and fundamental tasks in graph learning at the input graph representation level. The line between benchmarking on each task now bluree.. Our experiments show that different representations and their respective tasks are optimal for different. graphs, models and hyperparameters. The majority of such predictive tasks have been only benchmarked as a node classification problem, which now know is insufficient. In line with many recent works that challenges graph learning (Luo
benchmarks Luo et al. 2024 Lv et al. 2021 Bechler-Speicher al. 2025 Coupette et al. 2025 the use of complex GNNs, graph structures themselves and hyperparameter choices, our work adds new considcration to all past and future benchmarks.
Our results also empirically suggest heuristics of when a representation is better than the other. It appears that relatively homophilic sparse graphs with few high-degrec nodes may be suitable for link prediction representations. We also observe that several of the graphs that link prediction perform better are subsets of citation networks, suggesting correlation with more muanced characteristics, such as node features higher-order graph properties.
We pave the way for formally and fundamentally understanding the interconnection between the key problems of node classification and link prediction. We demonstrate the importance of considering different graph representations and call for more comprehensive future benchmarks. We hope our work a step towards a general and provable criterion of defining the optimal representation and task.
7 Limitations and Future Work.
Our paper empirical in nature. Given that there no prior work on the question studied, we allempt to first answer the question of whether different representations matter. The answer turns out to be positive. A valuable future direction will be formally establishing the connections between different representations, in particular for the node classification and link prediction representations, as well as the respective tasks.
Our work focuses only on the transductive setting due to the amount interdependent components in the entire learning process, such as initialisation, model choices, model and training process hyperparameters, and datasets. Future empirical work could extend our problem definitions inductive cases. Such an extension will be nontrivial, for example, the optimal way of defining and sampling negative edges in the inductive case is unobvious.
Acknowledgments
This work an extension of Tobias Möller's master's thesis(Möller 2025) while at Neo4j and Lund University. The authors thank Alexandros Sopasakis and Donglin Liu (Lund University) for helpful discussions and comments.
References
Ralph Abboud and ismail Îlkan Ceylan. Node classification meets link prediction on knowledge graphs, 2021. URL
Lada A. Adamic and Eytan Adar. Friends and neighbors the web. Soc. Networks, 25:211-230, 2003. URL http:///ppppeeeaaaaccccocoor.rrr :22 2262951
Uchenna Akujuobi, Han Yufei, Qiannan Zhang, and Xiangliang Zhang. Collaborative graph walk for semi- 09706
supervised multi-label node classification, 2019. URL
Adrian Rodriguz, Ahmed Begga, Francisco Escolano, and Nuria Oliver. Diffwire: Inductive graph rewiring via the lovász bound, 2022. URL htttp::/aaxxvv..r///a/////2
Federico Barbero, Ameya Velingker, Amin Saberi, Michael Bronstein, and Francesco Di Giovanni. Locality- aware graph-rewiring in gnns, 2024. URL
12

---

Published in Transactions on Machine Learning Research (07/)025)
Maya Bechler-Speichee Ben Finkelshtein, Fabrizio Frasca, Luis Muller, Jan Tönshoff, Antoine Siraudin, Viktor Zaverkin, Michael M. Bronstein, Mathias Niepert, Bryan Perozzi, Mikhail Galkin, and Christopher Morris. Position: Graph learning will lose relevance due to poor benchmarks, 2025. URL https://arxiv
org/ 255/2222250... 14546
Mustafa Bilgic, Galileo Mark Namata, and Lise Getoor. Combining collective classification and link predic- tion. In Seventh IEEE International Conference Data Mining Workshops (ICDMW 2007), pp. 381-386, 2007. doi: 10.1109/ 10.1109/CCDMW CCGDM.2000..00
Derrick Blakely, Jack Lanchantin, and Yanjun Qi. Time and space complexity of graph convolutional networks. Unpublished manuscript, University of Virginia, 2019.
Aleksandar Bojchevski and Stephan Günnemann. Deep gaussian embedding of graphs: Unsupervised induc- live learning via ranking, 2018. URL
03815
Jun Chen and Haopeng Chen. Edge-featured graph attention network, 2021. URL https://arxiv.orrs abs/2101.07677
Tianlong Chen, Kaixiong Zhou, Keyu Duan, Wenqing Zheng, Peihao Wang, Xia Hu, and Zhangyang Wang. Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study, 2022. URL
(ttps://arxiv.org/atte 2208. 10521
Corinna Coupette, Jeremy Wayland, Emily Simons, and Bastian Rieck. No metric to rule them all: Toward principled evaluations of graph-learning datasets, 2025. URL
02379
Daniel Daza, Michael Cochez, and Paul Groth. Inductive entity representations from text via link prediction. In Proceedings of the Web Conference 2021, WWW '21 pp. 798 808. ACM, April 2021. doi: 10.1145/ 33450141.. URL http:://xx..o...rrg........ 10g.//0............. 2ttp:/00..11//4442223333444111 3450141
Ahmed El-Kishky, Thomas Markovich, Serim Park, Chetan Verma, Backjin Kim, Ramy Eskander, Yury Malkov, Frank Portman, Soffa Samanicgo, Ying Xiao, and Aria Haghighi. Twhin: Embedding the twitter heterogeneous information network for personalized recommendation. In Proceedings of the 28th ACM SIGKDD Conference Knowledge Discovery and Data Mining, KDD '22 pp. 2842 2850. ACM, August 2022. doi:
URL http:://x.ddo doi. org/ 10. 1 145/3534678.... 3539000
Seyed Amin Fadace and Maryam Amir Haeri. Classification using link prediction. Neurocomputing, 359: 397-407, 2019.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Munifolds, 2019.
Xinyu Fu, Jiani Zhang, Ziqiao Meng, and Irwin King. Magnn: Metapath aggregated graph neural network for heterogeneous graph embedding. In Proceedings of The Web Conference 2020, WWW '20. ACM, April 2020. doi: 10.1145/33313 33664333633333 3380297. 3366427.3350299. URL http://dx. doi. org/ /00 11111113333642.3.. 2ttp//33366423333322777
C. Lee Giles, Kurt D. Bollacker, and Steve Lawrence. Citeseer: an automatic citation indexing system. In Proceedings of the Third ACM Conference on Digital Libraries, DL '98, pp. 89-98, New York, NY, USA, 1998. Association for Computing Machinery. ISBN 0897919653. doi: 10.1145/276675.27668 URL https://doi.onn htt.://0///0.11////776... 276685
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry, In International conference on machine leorning, pp. 1263 1272. PMLR, 2017.
William L. Hamilton. Graph representation learning. Synthesis Lectures on Artificial Intelligence and
Machine Learning, 14(3) 2020.
William L. Hamilton, Rex Ying, and Jure Leskovee. Inductive representation learning on large graphs, 2018 URL httpatpp:///xxivooo//a////////at 02216
13

---

Published in Transactions on Machine Learning Research (07/2025)
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. Tn H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, http:pt:///rocceddnggge newrins...pp... cttps.ccppeeee wwtppcpppppaaeeeeeeeeeeee files/ pp. 22122 22133. Curran Associates, Inc., 2020. URL
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprinl 1rxiv:1600 1099. 609.02907, 2016.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks, 2017.
URL https://arxii: owg.riiiiiorrooooooooooo hwtp://ggggaa////aeeeeeee http:/abs//......00 http//6699.00000000
Yuankai Luo, Lei Shi, and Xiao-Ming Wu. Classic guns are strong basclines: Reassessing gnns for node classification, 2024. URL htttps://arxi: http:///oawwoooooaa///////// 2406 08993
Qingsong Lv, Ming Ding, Qiang Liu, Yuxiang Chen, Wenzheng Fong, Siming Hc, Chang Zhou, Jianguo Jiang, Yuxiao Dong, and Jie Tang. Are we really making much progress? revisiting, benchmarking, and refining heterogeneous graph neural networks, 2021. URL httpp://arxxv..rr/abbb/////// 2212..49361 14936
Andrew K. McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163 103,,16,--0 2000. doi: 10.1023/A:
1009953814968.
Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference artificial intelligence, volume 33, pp. 4602 4609, 2019.
Tobias Möller. Reprosentations of graphs and their impact graph neural networks. Master's thesis, Lund Universily, 2025. LUTFMA-3572-2025 ISSN 1404-6342, ISSN 2025:E15.
Trung-Kien Nguyen and Yuan Fang. Diffusion-based negative sampling on graphs for link prediction, 2024.
URL https://arxivu http///rxivv..rr/aa///0.00.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. CoRR, abs/2002.052877, 2020. URL https://arxiv http:///www.rrr/ra/////////////0
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of guns under heterophily: Are we really making progress?, 2024. URL https:
org/ //axxiv.org//bs/2202.111 abs// 11640 11640
Chendi Qian, Andrei Manolache, Christopher Morris, and Mathias Niepert. Probabilistic graph rewiring via virtual nodes, 2024. URL htttp:://axiv..rrgg 2205111./2201111
Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael Bronstein. Edge directionality improves learning on heterophilic graphs, 2023. URL https:
//axxiv.org/abs//200 10498
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, 2021. URL
attps://arxiv.orr//bbs/////
13021
T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks, 2023. URL
10993
Ryoma Sato. Training-free graph neural networks and the power of labels as features, 2024. URL https:
//arxiv.org//bs//4004... 19288
Damian Szklarezyk, Annika L Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta-Cepas, Milan Simonovic, Nadezhda T Doncheva, John H Morris, Peer Bork, Lars Jensen, and Christian von Mering. String v11: protcin-protcin association networks with increased coverage, supporting functional discovery in genome-wide experimental datasets. Nucleic Acids Reseorch, 47(D1))D607-D66 -D613, 2019. ISSN 0305-1048. doi: 10. N0.1093/nar/gky
14

---

Published in Transactions on Machine Learning Research (07/2025)
Lei Tang and Huan Liu. Relational learning via latent social dimensions. pp. 817-826, 06 2009. doi: 10.1145/1667119.556 1555100.
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bron- stein. Understanding over-squashing and bottlenecks on graphs via curvature, 2022. URL https:
//axxvv.rrg/bb///111..11 14522
Petar Veličkovié, Guillem Cucurull, Aranixa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks, 2018. URL http:///wwxxiv.ooraabb///aa///// 10903
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Peng Cui, Philip S. Yu, and Yanfang Ye. Heterogeneous graph attention network. CoRR,
2019. URL
Yangkun Wang, Jiarui Jin, Weinan Zhang, Yong Yu, Zheng Zhang, and David Wipf. Bag of tricks for node classification with graph neural networks, 2021. URL https://arxiv: www./ag/////..ooooo abs//133. 13355
Yuchen Wang, Jinghui Zhang, Zhengjie Huang, Weibin Li, Shikun Feng, Ziheng Ma, Yu Sun, Dianhai Yu, Fang Dong, Jiahui Jin, Beilun Wang, and Junzhon Luo. Label information enhanced fraud detection against low homophily in graphs. In Proceedings of the ACM Web Conference 2023, WWW '23, pp. 406 416. ACM, April 2023. doi: 241145/3543507.355 3583373. URL http://dx: doi. wtt.:.o./////....1111. 10////00111///33500 3583374
Boris Weisfeiler and A. A. Lehman. A Reduction of Graph to a Canonical Form and an Algebra Arising During This Reduction. Nauchno-Tedde Technicheskaya Informatsia, Ser. 2(N9): 1968.
David S Wishart, Yannick D Feunang, An C Guo, Elvis J Lo, Ana Marcu, Jason R Grant, Tanvir Sajed, Daniel Johnson, Carin Li, Zinat Sayeeda, Nazanin Assempour, Ithayavani lynkkaran, Yifeng Liu, Adam Maciejewski, Nicola Gale, Alex Wilson, Lucy Chin, Ryan Cummings, Diana Le, Allison Pon, Craig Knox, and Michael Wilson. Drugbank 5.0: a major update to the drugbank database for 2018. Nucleic Acids Research, 46(D1):D1074 D1082, 11 2017. ISSN 0305-1048. doi: 10.1093/nai 20093/ar//// htt///ar/ggx00000 g037 URL https: //doi org/ 10/./1..1500 100.1099//aarr/kx103/7
Zougqian Wu, Mengmeng Zhan, Haiqi Zhang, Qimin Luo, and Kun Tang. Mtgen: A multi- approach for node classification and link prediction in graph data. Information Processing & Management, 59(3): 102902, 2022. ISSN 0306-4573. doi:
20t........222.2...2222222222220 URL https:// htttss://www.
sciencedirects gciencadirect.ccmmcccciiie
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint Xrx::1810.000226 2018
Zhen Yang, Ming Ding, Chang Zhou, Hongxia Yang, Jingren Zhou, and Jie Tang. Understanding negative sampling in graph representation learning, 2020. URL https://arxiv.. org/ ab05 09863
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L. Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery Eamp; Data Mining, KDD '18, pp. 974-983. ACM, July 2018 doi: 10.1145/32198819.22159
URL http://dx. /tw. www.ddii..ooooooo www/r0.../00. 0144/1111//1111 32198990
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method, 2020. URL /ttpp:://axxi.....
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications, 2021. URL
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propagation. 2002. URL www.s//wwwmiiicoooooooooorrrruue
15

---

Published in Transactions on Machine Learning Research (07 (07/202) 2025)
X paper
label
d
14]
SAGE/GAT (paper->paper)
SAGE//AA (naper-llabe) +label)
SAGE/GAT (label- ppppr)
61
RcLU
64
ReLU
64
RcLU
SAGE/GAT (paper-opaper)
SAGE/ GAT /GAT (label- ppppe))
SAGE/GAT (paper-llabl)
RcLU
48
ReLU
48
ReLU
18
SAGE/GAT (paper-ppaper
SAGE/GAT
SAGE/GAT
(label -paper)
32
ReLU
32
ReLU
+
32
RcLU
32
out paper
out label
Figure The architecture of a heterogeneous GNN for graph with two node types A (paper, label} and relation type R {*) with no edges between label nodes. This example GNN has three layers. A separate channel is instantiated for each triplet type. @ denotes aggregation of embeddings, in this paper, PyG's default aggregator, summation, is used.
A Appendix
A.1 Computation graph of heterogeneous GNN
An example computation graph of heterogeneous GNN is illustrated in Figure 4 This implementation is directly supported by PyG's to _heteroe) function on HeteroData & Lenssen 2019) This implementation is a basic and natural extension of homogeneous GNNs without adding metapaths which represent additional heuristics that strengthen the models. The models with three layers have layer sizes (64, 48, 32), while the models with two layers have layer sizes (64, 32). In the GAT models, four attention heads are used. For both task representations, the decoder single linear layer on either nodes (for NC) or node-pairs (for LP).
A.2 Additional experimental setups
For the smaller real-workd datascts and all synthetic graphs we used 10 random seeds. For larger datascts, use 5 seeds for obgn-arxig and Squirrel and 3 seeds for BlogCat and Yelp if the results are consistent. Default learning rate = 0.01. Default hidden channels = 64 and embedding size = 32.
The homogencous GraphSAGE and GAT encoders consist of either two or three SAGE GAT-layers with U-ativvviit functions between them. The models with three layers have layer sizes (64, 48, 32), while the models with two layers have layer sizes (64, 32). In the GAT models, four attention heads used. For
16

---

Published in Transactions on Machine Learning Research (07/2025)
1-hop
2-hop
3-hop
RW 2-hop
RW 3-hop
CITESEER,
0.96
0.94
0.92
0.95
0.93
Homophilic
CORA-ML
0.81
0.73
0.58
0.77
0.61
OGBN-ARXIV
0.64
0.50
0.37
0.58
0.42
CHAMELEON
0.25
0.25
0.23
0.30
0.23
Hcterophilic
SQUIRREL
0.22
0.21
0.20
0.26
0.21
M-MANEEMIIRE
0.05
0.07
0.07
0.29
0.11
Table 9: Homophily numbers for the different datasets the heterophilic and homophilic comparison, before and after rewiring with 80/10/10 split. RW denotes homophily numbers for the rewired graph.
1-hop
2-hop
3-hop
RW 1-hop
RW 2-hop
RW 3-hop
CITESEER
2.5
16.7
42.5
2.76
57.6
186.9
CORA-ML
5.4
71.8
294.7
5.7
99.3
422.3
OGBN-ARXIV
13.7
3484.2
18469.6
13.9
4151.7
22579.6
CHAMELEON
27.6
558.7
1066.3
27.8
580.8
1312.3
SQUIRREL
76.3
1692.1
3538.5
76.5
1736.1
3836.9
ROMAN-EMPIRE
2.9
7.1
12.8
3.1
121.2
750.6
Neighbourhood sizes for the different datasets in the heterophilic and homophilic comparison, Table 10:
before and after rewiring with an 80/10/10 split. RW denotes neighborhood sizes for the rewired graph.
both lask representations, the decoder single linear layer on either nodes (for NC) or node-pairs (for LP).
The HAN model only consists of one layer, since the metapaths allow for message passing in neighbourhoods larger than one-hop. Following Wang et al.) eight attention heads are used together with dropout rate of 0.6, and 128 hidden channels. The decoder architectures are the same as for GraphSAGE. and GAT.
A.3 Dataset Statistics
Number nodes, number of edges, number classes, average degree, and node feature size for every dataset can be found in Table I1 For each dataset, the node degree distribution visualised Figures 5 and For the heterogeneous datasets, the node degree distribution is calculated on the computation graph induced by the meta-paths.
A.4 Heterogeneous Dataset Information
ACM is network of papers, authors, and subjects, where the papers are divided into three classes (database, wireless communication, data mining). Paper features correspond to elements of bag-of-words representa- tion of keywords. The meta-path set (PAP, PSP] is used in Wang et al. (2019).
DBLP network of authors, papers, conferences and terms. The labels indicate research areas of the authors, and one of database, data miniing, machine learning, and information retrieval. Author features contain the elements of bag-of-words represented by keywords. The meta-path set employed in Wang et al.) (019 is (APA, APCPA, APTPA).
IMDB is a dataset containing movies, actors, and directors. Each movie is divided into one out of three classes (Action, Comedy, Drama). Movie features correspond to elements of a bag-of-words representation of plots. The meta-path set {MAM, MDM) is used in Wang et al. 2019
The new GLP representations of these graphs make it possible define new meta-paths which include label nodes. Studying this is out. of the scope of this paper. The same meta-path sets used as in the
17

---

Published in Transactions on Machine Learning Research (07/202) 2025)
6113
3812
2333
1000
300
110
30:000
10-400
110
13.00
10kane
6st 1000
a
CiteSeer
(b) Cora-ML
220000
15900
100000
hooks
300
50000
24175
2.8
10:3000
1.3
11.00
tec
301 emo
301
dat
segrne Hange
(c) OGBN-Arxi
(d) Chameleon
70000
2953
fodees
15000
2333
12000
2
M0
kab
122
2
38.00
20
1000
M4 aaage
Dig Kange
Squirrel
Roman- Roman-Empire
Figure 5: Node degree distributions for the six datasets with varying label homophily levels.
18

---

Published in Transactions on Machine Learning Research (07 (07/202)) /025)
V
T
Number of Classes
d
Average Degree
CiteSeer
4,230
10,674
6
602
2.5
Cora-MI.
2,995
16,316
7
2,879
5.4
OGBN-Arxiv
169,343
1,166,243
40
128
13.7
Chameleon
2,277
36,101
5
2,325
27.6
Squirrel
5,201
217,073
2,089
76.3
Roman Empire
22,662
65,854
18
300
2.9
DBLP (single)
4,057
119,783
4
334
5,942.9
IMDB
4,932
20,172
3,489
48.1
ACM
3,025
273,000
3
1,902
4,124.3
DBLP (multi)
28,702
68,335
4
223
4.8
BlogCat
10,312
333,983
39
0
64.8
Yelp
716,847
7,340,000
100
300
19.5
Table 11: Statistics of all real-world datasets used in the paper, where [V] is the number of nodes, [7] the number of edges, and d is the size of node features. All statistics are based on the GNe representation.
Sunterr 6ffoci
3903
2203
800
200
110
3tpp
25p
20.30
20:400
Ibote
1:0
2110
2014 sea
Day 00 Pance
Deore Ragg
(a) DBLP (single)
(b) IMDB
150
2250
Numo
$0,30
204000
Dogie farge
(c) ACM
Figure 6: Node degree distributions for the computational graph (only involving meta-paths) of heteroge- ncous datascts.
19

---

Published in Transactions on Machine Learning Research (07/202) /025)
232.0
23330
2584
13000
2000
1000
Nurber
2000
1040
1259
347
with Foee
120
30 doa
Depres
Degrez fange
(a) DBLP (multi)
(b) BlogCat
100000
123p
Digren Tango
Yelp
Figure 7: Node degree distributions for the multi-labeled datasets.
GraphSAGE
GAT
NC
LP
NC
LP
P
CiteSeer
96.24 0.97
94.3 + 1.32
10
0.002
90.26 + 1.26
94.09 + 0.93
100
OGBN-Arxiv
67.99 = 3.76
70.95 + 1.00
80
0.155
69.57
0.17
65.69 = 0.66
0
Roman Empire
80.27 1.36
72.44 + 1.11
0
42.41 + 2.90
38.05 + 2.52
10
0.002
Table 12: Test scores reprosentative datascts using models with three layers. Hidden channel dimensions are smooth interpolations of the input and out dimensions. p represents the p-value, report 0 whenever it is smaller than 0.001.
original paper. The added nodes and message-passing edges will still yield added information in the L.P representation.
A.5 Hyperparameter analysis on embedding dimensions
Table 12 shows the test. scores on selected datasets when the hidden channel embedding dimension are not fixed to 64, but instcad smoothly interpolate between input and output embedding sizes. For example, if input feature has dimension 4000, output embedding has dimension 1000, then the three-layer models have embeddings 000-3300-2000-1100
A.6 Time complexity analysis
To better understand the trade-off between the two representations, a high-level time complexity analysis is performed for the scenario of running GraphSAGE single-labeled homogeneous graph. Following the
20

---

Published in Transactions on Machine Learning Research (07 (07/2025)
description in Section 3.1 the two representations:
GNC (V,A,, and = UU
are studied. GN has [V] nodes and [T] edges, where each node has a feature size of d. As result of the introduced label nodes and edges, GLP will consist of [VU nodes and [TUT edges, where each introduced label node has feature vector of dimension [C].
Since GraphSAGE is the model of choice, cach round of message passing will include an aggregation from fixed number of neighbors. Let the maximum number of sampled neighbours be S. The forward pass of one GraphSAGE layer 1, with input and output embedding sizes emb- and emb has three distinct operations:
1. Neighbourhood aggregation: Every node aggregates embeddings from S neighbours, cach embedding having dimension emby-1- Over all [V] nodes, this results in time complexity of O(VI . S emb--1).
Message passing: After aggregation, each node's current embedding is concatenated with the embedding of the neighbourhood. This concatenation step is (embr-1)) followed by a multiplication by weight matrix Wemm 2embb-1 of time complexity O(embr 1emb;-1) O(embr emb:-1). For all nodes, the time complexity of one round of message passing would be O([V] -emby emb;-1).
Non-linear activation: Activation functions are applied element-wise on emby-sized embeddings. This has time complexity of [[V]] emb;)
The above operations give total time complexity of
O 1) O(VI emb, emb;-1) + O(V) embr) O(VV -mbr emb;-1).
The complexity of a backward pass is analogous to the forward pass due to reverse-mode automatic differen- tiation, which is used in NyYochh(Blakk,) et al. 2019). This gives forward backdwd pass time complexity of O([V) - cmb, emb;-1) for Gvc.
However, because of the heterogeneity GLP, the model architecture must take node and edge types into consideration (see Figure 4). This results in the architecture of the model for GLP having three times the amount of GraphSAGE layers. The time complexity of be denoted as TNO for GNc:
pass for the 3-layer model can
TNC = - . d)+ cmbb2 emb11) + O([VI embys emb12)
(6)
and Trp for GLP:
TLP = - - d) + 0(22 embb1)
+0 eembee embς1) + O([4) emb emb11)
+ +20([V) embra embb2) + O(C embr3 embz2). (7)
Equations and yield
TrP = 2- Twe + 0([[ embr.) + 0([ embr, emb.,. + O([C) embra embra).
Assuming V > [C] and d > [C], which hold for all datasets used as well as in general, we have
TNo 0 embı1) 0(C[) emb12 embbi) + O([C) embra embr2).
Finally, this yields
2. TxG < TIP < TwC-
21

---

Published in Transactions on Machine Learning Research (07 (025)
A.7 Number of learnable parameters
Building on Section A.6 similar analysis can be made for the number of learnable parameters for the two representations. As previously stated, for each GraphSAGE layer, the weight matrix is Wemb, X Including the bias, there are 2- eebyy. cmb--1+ emby learnable parameters per layer. Using the same scenario as in Section A.6 the number of learnable parameters CNc for the model used on GNC is
ONC = embba embr2 emb emb embra + emb + embra + embra.
(9)
Similarly, with the same the number of learnable parameters for the model used GLP are
CLP = 2- (embzi - d + embre embz1 + embys emb22 + embb1 - embbz + embbs)
+ +emb11 [C] + emb22 embb1 + emby3 embu2 + embb1 + embr2 + embrs. (10)
With the assumption of > [4], Equations and 10 yield
CNc > emb11
[4] + emb12 embb1 + embra emb + emby1 + emb + emb
which gives
2 Cxe CLP <3 CNc-
(11)
B GCN
We conduct experiments for GCN on various datasets. For each dataset, rumning GCN on representation Gve is standard. However, applying GCN on GLP requires additional modifications. The GCN convolution is defined as
Hh+1 =0
(12)
where W is the k-layer weights and À = A IN is the adjacency matrix with added self-loops. Diagonal matrix D. = E.
the heterogeneous GLP graph two issues arise. Firstly, Equation 12 is defined only for square adjacency matrices and therefore cannot handle the bipartite relations (T' Definition 3.2). Secondly, it assumes all nodes have the same embedding dimension and are initialised similarly, which is not the case for sets of nodes V and L in GLP-
To solve this, we decompose the computation graph in a HeteroConv similar to Figure 4 Taking an example of a paper-citation graph (with label nodes in GLP) the HeteroConv is:
HeteroConv (p, cites, p), (p. (p. is, rev is, p)}
(1,re__is,p)
aggr=mean"
GCNConv GraphConv
GraphiConv
where separate channels mean-aggregated at the node level after each layer. GCN is preserved the homogeneous citation subgraph, while the bipartite edges between papers and labels are handled by simple GraphCony ( et al. 2019) without edge weights, defined as:
h s+I
w + W Σ h
(13)
JEN(()
which allows different embedding dimensions for source (æ:) and target (æz) nodes in message passing.
Results for the heterophilic/ helerophili//hhnophhiee homophilic and multi-labelled datasets are shown in Table 13 It can be observed that for some datasets such as CiteSeer, models perform similarly on the two representations. For most other datasots, the LP representation either yields significantly worse performance, sometimes wildly different results that varies across seeds (such for Roman Empire). This likely due to the ad hoc definition of our heterogeneous GCN.
22

---

Published in Transactions on Machine Learning Research (07 (07/2025)
GCN
NC
LP
P
CiteSeer
95.48 0.92
95.41 + 1.08
40
0.876
Cora-ML
86.80 + 1.19
62.33
0.001
OGBN-Arxiv
70.86 0.00
23.9
10
0.140
Chamelcon
67.23 + 3.98
4..47
0
0
Squirrel
39.15 = 2.81
10
0.008
Roman Empire
41.55 + 0.75
38.42 + 12.3
40
0.443
(BLP(multi)
94.29 0.41
56.76 + 0.13
BlogCat
80.04 0.96
4.86 + 1.42
0
Yelp
42.41 + 0.32
16.0 = 0.47
0
0.01
Table 13: Test scores using GCN with 3 layers. represents the percentage of runs where GL. is better representation than GNc. represents the p-value, we report 0 whenever it is smaller than 0.001.
C GIN
GIN was initially proposed as an 1-WL expressive architecture to solve graph classification problems involving non-isomorphic graphs that may be difficult to separate with other architoctures. Although there is no evidence suggest higher expressivily (when measured by WL) helps with labelling nodes on sets of graphs, we conduct experiments of GIN the 6 heterophilic/homophiio datasets.
A GIN layer is defined as:
h (()++)
En JEN())
(14)
While applying GIN on GNe is again standard, directly adding h4 and summed hy implies it does not work on GLP.
Therefore, for each node lype, add learnable linear layer that maps the input node embeddings into common latent space with the same dimension, and then use the GINConv layer to hetero (onNCon)...)) in the same way as the GraphSAGE. and GAT (Figure for GLP.
Our results are shown in Table 14 GIN on GLP somelimes produces wildly different results than on GNC- It performs generally better on GN and sometimes indifferent (e.g Squirrel).
GIN
NC
P
CiteSeer
95.27 + 1.31
93.88 +: 2.98
30
0.1994
Cora-MT.
86.43 + 1.69
81.73 + 3.05
0
0
OGBNN-rxiv
68.36 +: 0.57
4.20
0
0.006
Chameleon
43.33 - 8.68
19.9666.55
10
0.001
Squirrel
32.50 2.96
33.88 3.22
0.499
Roman Empire
45.08 + 1.99
37.82 6.12
10
0.004
Table 14: Test scores using GIN with 3 layers. < represents the percentage of runs where GLP better representation than GNC- p represents the p-value, we report 0 whenever it is smaller than 0.001.
23


Reviews:
[{"review_id": "yXsu9kR9wJ", "reviewer": "Reviewer_EsZR", "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**\n\n1. The paper explains a novel empirical problem and important for graph representation learning community but often neglect in practise \n2. A detailed empirical study is conducted with careful handle of data split and evaluation metrics\n3. The formulation of transformation from NC to LP tasks (seems) is novel\n4. The paper is generally easy to follow and well-written\n\n**weakness**\n\n1. All empirical experiments and results are not very useful (e.g. not much to say about when to formulate LP or NC task, what is the trade-offs, why sometimes one way of formulation is preferred and what should be done when this happens)\n2. No theoretical analysis and hence make this paper sounds like a scientific report\n3. Lack of reason why pick GraphSAGE and GAT and why under transductive setting only\n4. I think the formulation of graph structure is a very strong inductive bias and should be data-dependent, not sure if I am convinced on results reported based on architeture.\n5. May lack of variety of models used for evaluation, and the motivation for this research could framed a bit better", "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 examines how the same graph modelling problem can be formulated either as node classification (NC) or link prediction (LP), depending on how the underlying graph is constructed. It conduct a through empirical study across different datasets and settings, based on two graph backbone models (GraphSAGE and GAT). The core conclusion is that the choice of graph structural representation (how it is constructed) can significantly impact model performance.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refers to the weakness section, I think adding more theoretical analysis is not required but would be nice if the authors could address it somehow (W2). I would expect the authors to response to all my other points in the weakness section (W1, W3-W5).", "broader_impact_concerns": "N/ A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "lioHdGHg5H", "reviewer": "Reviewer_U6bd", "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:\n\n- This work introduces a novel, data-centric perspective on graph representation design.\n- The paper conducts comprehensive experiments to elucidate how alternative graph encodings influence model performance.\n\nWeaknesses:\n\n- No theoretical insights explaining why LP helps in sparse graphs; a more in-depth analysis could strengthen the paper.\n- Only vanilla GraphSAGE/GAT/HAN are evaluated; more powerful architectures might behave differently.", "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 study examines how different graph encodings influence node-label prediction with message-passing GNNs, demonstrating that a link-prediction formulation can, in certain settings, surpass the conventional node-classification approach.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I wonder how does the different graph representations affect non-parametric graph learning methods such as label propagation. It would be interesting to explore in this perspective.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "7yDFTbINbC", "reviewer": "Reviewer_N3cy", "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\n- The issue of problem encoding is an interesting topic that has not been widely studied.\n- The conclusions, if valid, could impact future model choice and design.\n- The evaluations are fairly broad, even though they are limited to single graph datasets.\n\n# Weaknesses\n- This manuscript is not well-polished.\n- There are a number of lacking descriptions leading to challenges in comprehension.\n- There are numerous typos and similar mistakes leading to challenges in comprehension.\n- The problem setup is not well-defined, which could imply a vacuous conclusion.\n- Conclusions are drawn without the use of statistical significance, which could imply a vacuous conclusion.", "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 work compares two different problem settings that achieve the same goal. Namely, it compares node classification and link prediction on a modified graph instance. The authors discuss strategies for fair comparison and finally conduct experiments on 12 datasets observing different graph properties correlating with performance.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Page 1 \"users tagging music with genre\". Why are you using quotes here? What are you quoting? Also, the quote symbols used are not proper. This example is generally poorly chosen since this work focuses on the comparison between node classification and link prediction, but this example compares labeled link prediction to hyperedge prediction.\n2. Page 3 partial labelling function L. Why are you referring to this function as a partial labeling function? It assigns every vertex a set (which might be empty) of labels. It is not clear whether you are implying that there are labels missing or simply referring to the fact that some nodes have an empty set of labels.\n3. Page 3 \\mathcal V_L. Due to the previous issue, it is unclear how \\mathcal V_L is defined.\n4. Page 3 \\beta_K definition. In this definition, you use \\mathcal N^K, which has not been defined. Likely you are referring to the k-hop neighborhood, however, there are two common definitions of this, one including all nodes with paths of length at most K, the other including all nodes with paths of length exactly K.\n5. Page 3 message passing GNN. You seem to be using the definition of the Message Passing Neural Network (not Graph Neural Network) defined by Gilmer (\"Neural Message Passing for Quantum Chemistry\" 2017) without citing this work. Please correct this.\n6. Page 3 Formally the message passing step as (should be is)\n7. Page 3, Equation 1. There is a missing closing brace.\n8. Page 3 after equation 1. You state that the UPDATE function is a learnable MLP, however, the UPDATE functions takes as input a tuple, which is not a standard input for an MLP. This should be clarified.\n9. Page 3 Model choice. You chose to evaluate GraphSAGE and GAT but do not justify your choice. Standard alternatives that are more common in general are the graph convolutional network (GCN) and graph isomorphism network (GIN). Please justify this choice adequately based on related work.\n10. Page 3 The GNN formula ... . Please specify what you are referring to with \"GNN formula\".\n11. Page 3 \\mathcal A \\times \\mathcal R \\times \\mathcal A. It is unclear from this description how you would use equation 1 to deal with heterogenous graphs.\n12. Page 4 abstract graph. What is an abstract graph? This has not been defined.\n13. Page 4 use mostly default font ... . This description is not at all adequate. Please specify in detail how you transform the original graph using calligraphic font into the graphs in definitions 3.1-3.4.\n14. Page 4 Definition 3.3-3.4 You use P_{NC} and P_{LP}, however, it is not clear that these are descriptions of these definitions. Perhaps add more surrounding text explaining the context and add the description P_{NC} and P_{LP} into their definition defining what exactly this term refers to.\n15. Page 4 Definition 3.4 (V \\times *' \\times V). There is a set missing here. It should be (V \\times \\{*'\\} \\times V).\n16. Page 4 and beyond set unions. You are commonly defining set unions that are disjoint. Perhaps you could use \\cupdot to clarify that these are disjoint unions and thus partitions of some larger set.\n17. Page 4 \", both as information used by the learning method\". I do not understand the implication or point of this part of the sentence.\n18. Page 4 equation 2-5. The description of these equations and, thus, your transformation is inadequate. You should clearly define all subindices like train_mp and train_sup. You should also clearly define what you mean by message passing and supervision edges. Further, you should give a clear motivation for this transformation and describe your goal.\n19. Page 5 Figure 2. Figure 2 is not sufficiently explained. What are dotted and non-dotted lines referring to? How are these graphs equivalent? You should extend the description of Figure 2 to fully explain what is depicted.\n20. Page 5 Section 4.1. You write |T'_{train_mp}\\setminus T'_{train_sup}| = 3/7; however, these two sets are likely disjoint, and the quantity you are computing is unclear. It would be better to state that the size of the first set is 30% of all edges and that the size of the second set is 70% of edges.\n21. Starting on Page 6 Section 4.3. You never describe how hyperparameter tuning was performed. Importantly, you are comparing models that might need different parameters to perform well. If no hyperparameter tuning is performed then how do you pose that any of your evaluations are comparable?\n22. Starting in Table 1. In your tables, you mark the best-performing model in bold. Importantly, this should be described in each table's caption. However, you do not consider the statistical significance of the difference. For example, in Table 1 Cora-ML using GraphSAGE NC vs LP, the difference is within one standard deviation and thus likely not significant. Please perform a t-test significance test using your 10 (or in some cases less) seeds and indicate in each table whether the difference is significant. For example, if it is not significant, you could mark both as bold or the second-best performing one (which is only insignificantly worse) with an underline. After this, you should reevaluate your conclusions. I suspect that you will not be able to draw many conclusions, which would invalidate some of your points.\n23. Page 7 and 9. It seems that there are some formatting issues in your manuscript. Pages 7 and 9 contain empty spaces and are not formatted well. Please resolve this issue and place the respective tables where they are used.\n24. Page 8 mega-nodes. I am not familiar with this term.\n25. Page 8 SBM graphs. In the description in Section 4.6, you consider SBMs built with 4 blocks, but you later refer to \"We assign binary labels to each of the two blocks of nodes\". Are there two blocks or 4 blocks?\n26. Page 8 random flipping. It is not clear how randomly flipping node labels makes the graphs non-trivial.\n27. Page 9 Table 6. Table 6 is too big for the page.\n28. Page 6 Figure 3. It is bad style to include images with text in them where this can be avoided. Remove the text from both images and replace this with subcaptions.\n29. Page 10 Related Work. Your related work on Rewiring is rather extensive, even though it is unclear how rewiring is related to your work. On the other hand, related work closely related to this manuscript is rather sparse. Consider doing an extended literature review. For example, you did not include Fadaee and Haeri (\"Classification using Link prediction\" 2019) or Bligic et al. (\"Combining Collective Classification and Link Prediction\" 2007) which a cursory glance revealed suggesting there are more works that are closely related to your work and perhaps implying that this is not the first time this question has been considered. Consider further narrowing of your claims in the Introduction regarding your work.\n30. Page 10 Section 6 Title. Discussion and Future Work is filled with conclusion (not discussion), future work, and limitations (not mentioned). Perhaps consider separating these into individual sections, or choose a better section title.\n31. General. In general, I suggest that you expand the captions on all figures and tables. Include a take-home message or conclusion as a first sentence for each followed by a detailed description that fully summarizes the figure or table. Generally, I also suggest that you move tables either to the top or bottom of each page for legibility (consider Figure 1 which is surrounded by text).", "broader_impact_concerns": "There are no such concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Decision: Accept (poster)