Training-free Graph Neural Networks and the Power of Labels as Features
Authors: Ryoma Sato
Venue: Accepted by TMLR ()

Abstract: We propose training-free graph neural networks (TFGNNs), which can be used without training and can also be improved with optional training, for transductive node classification. We first advocate labels as features (LaF), which is an admissible but not explored technique. We show that LaF provably enhances the expressive power of graph neural networks. We design TFGNNs based on this analysis. In the experiments, we confirm that TFGNNs outperform existing GNNs in the training-free setting and converge with much fewer training iterations than traditional GNNs.

Published in Transactions on Machine Learning Research (8/2024)
Training-free Graph Neural Networks and the Power of Labels as Features
Ryoma Sato
rsato@nil.ac..)
National Institute of Informatics
Reviewed on OpenReview: https: openreview. net/ farmm? id- 7DzU88VrNU
Abstract
We propose training-fres graph neural networks (TFGNNs), which can be used without training and can also be improved with optional training, for transductive node classification. We first advocate labels as features (TaF), which is an admissible but not explored technique. We show that LaF provably enhances the expressive power of graph neural networks. We design TFGNNs based on this analysis. In the experiments, we confirm that TFGNNs outperform existing GNNs in the training free setting and converge with much fewer training itcrations than traditional GNNs.
1 Introduction
popular machine learning models for processing graph data. GNNs show strong empirical performance in various machine learning and data mining tasks, including chemical modeling
Graph Neural Networks (GNNs) 12
10
1g
question answering 34 and recommender systems
55
One of the standard problem settings for GNNs is transductive node classification, where the goal is to predict the labels of the test nodes a graph given the labels other nodes. This setting has many applications, including document classification including Graph Convolutional Networks (GCNs) 20 and Graph Attention Networks (GATs)
5d e-commerce
42 56 and social analysis 13 56
Many GNNs,
45
tackled
transductive node classification and showed excellent performance.
One of the challenges of GNNs is the computational cost. There are many huge graphs in practice, such as social networks and Web graphs, which contain billions of nodes. It is sometimes prohibitive to even scan the entire graph, c.g., the whole World Wide Web. Many mothods to speed up GNNs have been proposed. The basic approach is sampling nodes and/or edges to reduce the graph size A Sato al. A0 proposed constant time graph neural networks by neighbor sampling. Although drastically roduces the computational cost per iteration, it still requires many training iterations. PinSAGE ( adopts parallel training with MapReduce well importance pooling to speed up the training. Although PinSAGE succeeded in training GNNs with Web-scale graphs, it requires massive computational resources. It is still challenging to instantly use GNNs with limited computational resources.
56 bg
In the extreme case,
In this paper, we propose training-fres graph neural networks (TFGNNs).
To design TFGNNs, we first introduce the idca of labels as fcatures (LaF). LaF uses the node labels features, which is admissible in the framework of transductive node classification. GNNs with LaF can utilize the label information, such the class distribution in the neighboring nodes, to compute the node embeddings, which contain much more information than the embeddings with only the node features. We show that LaF provably enhances the expressive power of GNNs.
TEGNNs can be used without training and deployed instantly as soon as the model is initialized. This property reduces the burden of hyperparameter tuning as no training process is involved in this mode. TFGNNs can also be improved with optional training. Users can use TFGNNs with the training- free mode train TFGNNs for few iterations when the computational resources for training are limited. This property

---

Published in Transactions on Machine Learning Research (8/2024)
is useful for online learning, where training data come in streaming manner, and the model should be updated instantly. Users can also fully train TFGNNs when the computational resources are abundani the accuracy is required. TFGNNs enjoy the best of both worlds of nonparametric models and GNNs.
In the experiments, we confirm that TEGNNs outperform existing GNNs in the training- free setting and converge with much fewer training iterations than traditional GNNs.
The contributions of this paper are as follows:
We advocate the use of LaF in transductive learning.
We formally show that LaF strengthens the expressive power of GNNs.
We proposed training-free graph neural networks (TFGNNs).
We confirm that TEGNNs outperform existing GNNs in the training-free sctting.
Reproducibility: Our code is available http:///ggthuub.oooooiiisiiiieee
2 Background
2.1 Notations
For every positive integer n E Z4, [n]] denotes the set (1, A graph is defined as tuple of (i) the set V of nodes, (ii) the set F. of edges, and (iii) the node features X [a) ; 22...., x.,] Raxd, Without loss of generality,
assume that the nodes numbered with 1, y denotes the set of labels. ye E R denotes the one-hot encoding of the label of node c. For every node v E V, N()) denotes the set of neighbors of node v. We adopt the numpy-like notation for indexing. For example, X,1 denotes the first column of X, - denotes the last column of X, x denotes the last five columns of X, and X denotes all the columns except for the last five columns X.
2.2 Transductive Node Classification
Problem (Transductive Node Classification).
Input: A graph G = (V, E, X), labelled nodes Virain C V, and node labels Yrrain E Verain of Virain- Output: Predicted labels Yest E Viees of Viest = Virain-
There are two settings for the node classification problem: transductive and inductive. In transductive node classification, one graph and the labels some of its nodes are given, and we predict the labels of the remaining nodes. This setting uses the same graph for training and testing. This the inductive setting, which uses different graphs for training and testing, For example, in spam account detection, annotating spam accounts Facebook and using the trained model Facebook is example of the transductive setting, while using the trained model on X (Twitter) is an example of the inductive setting.
contrast
Transductive node classification is a popular setting in the GNN community; it has been employed in well- known studies, such as GCNs 20 and GATs 45,, and has been adopted in popular benchnarks such as Cora, PubMed, and CiteSoer. There are also many practical applications of transductive node classification, such document classification
20 54 and fraud detection X
46
2

---

Published in Transactions on Machine Learning Research (8/2024)
2.3 Graph Neural Networks
GNNs are popular solution for transductive node classification. We follow the message-possingg framework
of GNNs [0]. A message passing GNN is defined as follows:
h Bv
VoEV);
(1)
h = J (1 ((h--)) ( (uE)())))
(vl E [L],vV] E
(2)
y. Sredd ( (1)
(VoEV),
where Sagg is the aggregation function and fpred is the prediction head, which are typically modeled by neural networks.
3 LaF is Admissible, but Not Explored Well
We ask the readers recall the problem setting of transductive node classification. We are given node labels feed node features ay for training
yo of the training nodes. A typical approach for this problem node to the model, predict the labels of node v, compute the loss based the ground truth label you and update the model parameters. However, how we use yo is not limited. We can use ye as features of node v as well as for the loss function. This is the idea of LaF.
GNNs with LaF initialize the node embeddings in Eq.
as
h (0)
( Øol E 1+++++
(4)
where [ denotes the concatenation of vectors, and
[1: yel
(v E Virsta;
y. =
(5)
0 O
(v E Vuest,
is the label vector of node u, and O₂ is the zero vector of dimension d. LaF enables GNNs to utilize the label information, such as the class distribution in the neighboring nodes, to compute the node embeddings. Such embeddings are expected to be more informative than the embeddings without the label information. LaF is admissible in the sense that it uses only the information available in the transductive setting.
We emphasize that LaF has not been explored well in the literature GNNs, regardless of its simplicity, with some notable exceptions |I 50 (see Section 7 for detailed discussions). For example, GCNs 20 and GATs 45 adopt the transductive setting, and they are allowed to use the label information as features. However, they initialize the node embeddings as ( De without using the label information. One of the contributions of this paper that aflirm that LaF allowed in the transductive setting.
We should be careful when training GNNs with LaF. LaF may harm the generalization performance by inducing shorteut of copying the label feature h ( ddd-1 to the prediction. To prevent this, we should remove the label of the center nodes in the minibatch and treat them as test nodes. Specifically, let B C Virain be the set of nodes in the minibatch and set
[1:
(u E Virain \ B),
y.
(6)
0
(v E Viest U B),
and predict the label 9. for v E B, and compute the loss based on Go and yv- This simulates the transductive setting where the label information of the test nodes is missing, and GNNs learn how to predict the labels of the test nodes based on the label information and node features of the surrounding nodes.
4 LaF Strengthens the Expressive Power of GNNs
We show that LaF provably strengthens the expressive power of GNNs. Specifically, we show that GNNs with LaF can represent label propagation 58 important model for transductive node classification, while
3

---

Published in Transactions on Machine Learning Research (8/2024)
GNNs without LaF cannot. This result is interesting in its own right, and it also motivates the design of TFGNNs.
Label propagation is a classic method for transductive node classification. It starts random walks from a test node and outputs the label distribution the labeled nodes the random walks first hit. The following theorem shows that GNNs with LaF can represent. label propagation.
Theorem 4.1. GNNs with LaF can approzimate label propagation with any precision. Specifically, there crists series of GNNs { (fagg) and fpred such that for any positive E, for any connected graph G (V, E, X), for any labeled nodes Virain C V and node labels traain VVrre and test node E V Virain; there erists I. E 2+ such that 122 L)-th GNN (Jaggn...; (1) with the error at most E, i.e.,
S ppoad with LoF oulpuls the approzimation of label propogation
1 10 LP
S E,
(7)
where j.P is the oulput of label propogation for test node v.
Proof. We prove the theorem by construction. Let
PLus def Pr[The random walk from node v hits Virain within steps and the first hit label i].
(8)
For the labeled nodes, this a constant, i.c.,
Pta 1li yo] (Vl E Zza, v E Vrrain i E )/)
(9)
For the other nodes, this can be recursively computed as follows:
Po,r. 0
(Vu E V Virain i i J)).
(10)
Pl,yi
Σ
Pr[The first step + u] Pr[The random walk from node v hits Virain within
(11)
uEN(o)
steps and the first hit label is i The first step is + u]
= Σ
Pr[The random walk from node u hits Visan within (1 - 1) steps and the first hit label is
deg(v)
(12)
(o)(())
P1-
(13)
deg(v)
uEN(u)
These equations can be represented by GNNs with LaF, Specifically, the base case
Po.v. 1li yol (v E Virain),
(14)
E Verain),
can be computed from yn in h
(0) Let /agg always concal the first argument (i.e., h (1-1) in Eq.
(1)
2
the output so that the GNN can keep the information of the input. f(() handles two cases by To.1 {0,1), 1), i.e., whether is in Virain not. If U is in Virain f just outputs 1 = yul, which can (l)) computed by To (1-1) If v is not in Virains fagg aggregates Pt-1,u,i from u in (wv) and takes (!)) the average, i.c., Eq. 13). which can be realized by message passing in the second argument of fags.

---

Published in Transactions on Machine Learning Research (8/2024)
The final output of the GNN is Pl,v,. The output of label propagation can be decomposed as follows:
gL.
= PPr[The first hit label is i]
(15)
= Pr[[The random walk from node v hits Virain within / steps and the first hit label is i]
+ Pr[The random walk from node e does not hit Virain within steps and the first hit label i]
(16)
= -t,
+ Pr[The random walk from node o does not hit Viaan within steps and the first hit label is i]
(17)
As the second term converges to zero as increases, the GNNs approximate label propagation with any precision by increasing l.
We then show that GNNs without LaF cannot represent label propagation.
Proposition 4.2. GNNs withoout LaF camnol approzimate label propagation. Specificully, for any series of GNNs [ )t and fpred, there erists positive E, a connected graph = (V, E, X), labelled nodes Verain C V,, node labels Y train Voon and test node V Virain, such that for any 1, GNN (fage.... f p without LaF has the error at least E, i.e.
D E.
(18)
where "f. is the output of label propagation for test node v.
Proof. We construct counterexample. Let G be cycle of four nodes. The nodes are numbered 1,2,3,4 4 in the clockwise direction. All the nodes have the same node features Let Verain {1,2) and Ytrain [1, O] Label propagation classifies node 4 as class 1 and node 3 class 0. However, GNNs without LaF always predict the same label for nodes 3 and 4 since they are isomorphic. Therefore, for any GNN without LaF, there is an irreducible error either for node 3 or 4.
Theorem and Proposition 4.2 show that LaF provably enhances the expressive power of GNNs. These results indicate that GNNs with LaF are more powerful than traditional message passing GNNs such GCNs, GATs, and GINs without LaF. Note that GINs have been considered to be the most expressive message passing GNNs, but GINs cannot represent label propagation without LaF while message passing GNNs with LaF can. This does not lead to a contradiction since the original GINs do not take the label information as input. Put differently, the input domains of the functions differ. These results indicate that it is important to consider what to input to GNNs as well as the architecture of GNNs.
5 Training- free Graph Neural Networks
We propose training-free graph neural networks (TFGNNs) based on the analysis in the previous section. TFGNNs can used without training and can also be improved with optional training.
First, we define training-free models.
Definition 5.1 (Training-free Model). We say a paramotric model is training-free can be used without optimizing the parameters.
It should noted that nonparametric models are training-free by definition. The real worth of TEGNNs is that it training-free while it can be improved with optional training. Users can enjoy the best of both worlds of parametric and nonparametric models by choosing the trade-off based on the computational resources for training and the accuracy required.
5

---

Published in Transactions on Machine Learning Research (8/2024)
Random
Random
S -
0
O
0
0
Random
Random
T i
W0
0
0
O
0
0
U
O
Figure 1: Initialization of TFGNNs. The parameters the last (1 + (D1) rows or |>] rows are initialized by or in special pattern
The core idea of TFGNNs to embed label propagation in GNNs by Theorem 4.1 TFGNNs are defined follows:
[xvi [v]
(Ve E V),
(19)
ReLU ((0) ((-1) + [e]]]] EvEN(y) v@nu ((hd-1)) (o Verain / E [4]).
(20)
ReLU ((ins--) + (W(1)) EvEr(O) w(nk! (v Viest, E [Z]),
9. (oftmax(UU!!))
(Ve V).
(21)
The architocture of TEGNNs is standard, i.c. TFGNNs transform the center nodes and carry out mean aggregation from the neighboring nodes. The key to TFGNNs lies in initialization. The parameters are initialized as follows:
(0))
-11+ MD)
(Vl [4]),
(22)
5(( - I I++1
(Al [4]),
(23)
(1))
(Al E [4]),
(24)
-(++))))
(1)
(Al E [L]),
(25)
(1+D7))
()
(Al [4]),
(26)
-1++D)): (1+ 21)
(1
-(1+D)) (1++D)) I++1'
(Al [4]),
(27)
UA 0,
(28)
U.-1- 1
(29)

---

Published in Transactions on Machine Learning Research (8/2024)
i.c., the parameters of the last (1+ (31) rows |}] rows initialized by or 1 in special pattern (Figure D. Other parameters are initialized randomly, e.g,, by Xavier initialization 11 The following proposition shows that the initialized TFGNNs approximate label propagation.
Proposition 5.2. The initialized TFGNNs approzimate label propegation. Specifically,
(4) v (1)))++1 PL,
(30)
holds, where PL, is defined in Eq.
and
arg arg max Yos
arg max PL,u,
(31)
holds, and PL,vä + Der as L -000
Proof. By the definitions of TFGNNS,
h (0)
Yo
(u E Virain);
(32)
Olyl
(v E Veest),
(1-1) h
(u Virain / [4])
h [
-D%:
(33)
(1-1) [No EMEN())
(u Viest, E [4].
This recursion is the same as Eqp.
9
13
Therefore,
(1))+++1 = PL,
(34)
holds. As U picks the last [
dimensions, and softmax is monotone,
arg max yor arg max PL,
(35)
holds. PL,vi + g1. as + oo is shown in the proof of Theorem 4.1
Therefore, the initialized TFGNNs can be used for transductive node classification as are without training. The approximation algorithm of label propagation seamlessly embedded the model parameters, and TFGNNs can also be trained as usual GNNs.
6
Experiments
6.1
Experimental Setup
We use the Planetoid datasets (Cora, CiteSeer, PubMed) 54 Coauthor datasets, and Amazon datasets 22 in the experiments. We use 20 nodes per class for training, 500 nodes for validation, and the rest for testing in the Planetoid datasets following Kipf et al. 20 and use 20 nodes per class for training, 30 nodes per class for validation, and the rest for testing in the Coauthor and Amazon datasets following Shchur et al. [22. We use GCNs [20] and GAT' [5] for the baselines. We use three layered models with the hidden dimension 32 unless otherwise specified. We train all the models with AdamW 25 with learning rate 0.0001
and weight. decay 0.01.
6.2 TFGNNs Outperform Existing GNNs in Training- free Setting
We compare the performance of TFGNNs with GCNs and GATs in the training free setting by assessing the accuracy of the models when the parameters are initialized. The results are shown Table [ TFGNNs outperform GCNs and GATs in all the datasets. Specifically, both GCNs and GATs are almost random in the training-free setting, while TFGNNs achieve non-trivial accuracy. These results validate that TFGNNs

---

Published in Transactions on Machine Learning Research (8/2024)
Table 1: Node classification accuracy in the training-free free setting. The best results are shown in bold. CS: Coauthor CS, Physics: Coauthor Physics, Computers: Amazon Computers, Photo: Amazon Photo. TFGNNs outperform GCNs and GATs in all the datasets. These results indicate that TFGNNs are training- free. Note that we use three-layered TFGNNs to make the comparison fair although deeper TFGNNs perform
better in the training-free setting as we confirm in Section 6.3
Cora
CiteSeer
PubMed
CS
Physics
Computers
Photo
GCNs
0.163
0.167
0.180
0.079
0.101
0.023
0.119
GCNs + LaF
0.119
0.159
0.407
0.080
0.146
0.061
0.142
GAI's
0.177
0.229
0,180
0.040
0.163
0.058
0.122
GAI's + LaF'
0.319
0.077
0.180
0.076
0.079
0.025
0.044
TFGNNs random initialization
0.149
0.177
0,180
0.023
0.166
0.158
0.090
TFGNNs (proposed)
0.600
0.362
0.413
0.601
0.717
0.730
0.637
0.7
0.6
Accuracy
0.5
0.4
0.3
2
3
5
10 Number of Layers
7
8
11
12
13
14
15
16
Figure 2: Deep TFGNNs perform better in the training-free setting, The x-axis is the number of layers, and the y-axis is the accuracy of the models for the Cora dataset in the training- free setting. These results show that deeper TFGNNs perform better in the training-free setting.
meet the definition 5.1 of training-fres models. We can also observe that GCNs, GATs, and TFGNNs do not benefit from LaF in the training-free settings if randomly initialized. These results indicate that both LaF and the initialization of TFGNNs are important for training-free performance.
6.3 Deep TFGNNs Perform Better in Training-fres free Setting
We confirm that deeper TFGNNs perform better in the training-fres setting. We have used three-layered TFGNNs so far to make the comparison fair with existing GNNss. Proposition 5.2 shows that the initialized TEGNNs converge to label propagation as the depth goes to infinity, and we expect that deeper TFGNNs perform better the training-free setting. Figure 2 shows the accuracy of TFGNNs with different depths for the Cora dataset. We can observe that deeper TFGNNs perform better in the training-fres setting until the depth reaches around 10, where the performance saturates. It is noteworthy that GNNs have been known to suffer from the oversmoothing problem [22] 33 and the performance of GNNs degrades the depth incrcases. It is interesting that TFGNNs do not suffer from the oversmoothing problem in the training- free setting. It should be noted that it does not necessarily mean that deeper models perform better in the optional training mode because the optional training may break the structure introduced by the initialization of TFGNNs and may lead oversmoothing and/or overfitting. We leave it as a future work overcome these problems by adopting countermeasures such as initial residual and identity mapping 5, MADReg 3 and DropEdge 855
8

---

Published in Transactions on Machine Learning Research (8/2024)
Validation Accuracy
0.8
TFGNNs
0.6
training-fres free
accuracy
0.4
GCNs
0.2
0
1000
2000
3000
4000
Training Iterations
Figure 3: TFGNNs converge fast. The x-axis is the number of training iterations, and the y-axis is the validation accuracy of the models for the Cora dataset. These results show that TFGNNs in the optional training mode converge much faster than GCNs.
0.8
0.7
Accuracy
TFGNNs
0.6
0.5
0.4
GCNs
0.3
1e-2
1e-1
1e0
1e1
1e2
1e3
1e4
1e5
Noise Level
Figure 4: TFGNNs are robust to feature noise. The x-axis the standard deviation of the Gaussian noise added to the node features, and the y-axis the accuracy of the models for the Cora dataset. Both models are trained. These results show that TFGNNs are more robust to feature noise than GCNs.
6.4 TFGNNs Converge Fast
In the following, investigate the optional training mode of TFGNNs. We train the models with three random seeds and report the average accuracy and standard deviation. We baseline GCNs without LaF (i.e., the original GCNs) the baseline.
First, we confirm that TFGNNs in the optional training mode converge faster than GCNs. We show the training curves of TFGNNs and GCNs for the Cora dataset in Figure 3 TFGNNs converge much faster than GCNs. We hypothesize that TFGNNs converge faster because the initialized TFGNNs are in a good starting point, while GCNs start from completely random point and require many iterations to reach a good point. We can also observe that fully trained TFGNNs perform on par with GCNs. These results indicate that TFGNNs enjoy the best of both worlds: TFGNNs perform well without training and can be trained faster with optional training.
6.5 TFGNNs are Robust to Feature Noise
As TFGNNs use both node features and label information while traditional GNNs rely only on node features, we expect that TFGNNs are more robust to feature noise than traditional GNNs, We confirm this in this section. We add i..dd. Gaussian noise with standard deviation
the node features and evaluate the accuracy of the models. We train TFGNNs and GCNs with the Cora dataset. The results are shown in Figure 4 TFGNNs more robust to feature noise especially in high noise regimes where the performance

---

Published in Transactions on Machine Learning Research (8/2024)
of GCNs degrades significantly. These results indicate that TFGNNs are more robust to ii.d. Gaussian noise to the node features than traditional GNNs.
7 Related Work
7.1 Labels as Features and Training-free GNNs
The most relevant work is Wang et al. Mil, who proposed to use node labels in GNNs. This technique was also used in Addanki et al. [ and analyzied Wang al. [5]. The underlying idca common with LaF, i.e, use of label information input to transductive GNNs. A similar result as Theorem 4.1 was also shown in b-]. However, the focus is different, and there are different points between this work and theirs, We propose the training-free + optional training framework for the first time. The notable characteristics of GNNs are (i) TFGNNs receive both original features and LaF, (ii) TFGNNs can be deployed without training, and (iii) TFGNNs can be improved with optional training. Besides, we provide detailed analysis and experiments including the speed of convergence and noise robustness. Our results provide complementary insights to the existing works.
Another related topic is graph echo state networks g 24 which lead to lightweight models for graph data. The key idea is to use randomly initialized fixed weights for aggregation. The main difference is that graph echo state networks still require to train the output layer, while TFGNNs can be used without training, These methods are orthogonal, and it is an interesting direction to combine them to further improve the performance.
7.2 Speeding up GNNs
Varions methods have been proposed to speed up GNNs to handle large graph data. GraphSAGE B is one of the earliest methods to speed up GNNs. GraphSAGE employs neighbor sampling to reduce the computational cost of training and inference. It samples a fixed number of neighbors for each node and aggregates the features of the sampled neighbors. An alternative sampling method is layer-wise sampling introduced in FastGCN 4. Huang et al. [66] further improved FastGCN by using adaptive node sampling technique to reduce the variance of estimators. LADIES 5g combined neighbor sampling and layer-wise sampling to take the best of both worlds. Another approach is to use smaller training graphs. ClusterGCN 6 uses a cluster of nodes as a mini-batch. GraphSAINT mini-batch.
50 samples subgraphs by random walks for cach
It should also be noted that general techniques to speed up neural networks, such as mixed -eeeed-preciion training quantization
30,
17
21
3
48
52
and pruning 2 can be applied to GNNs.
These methods mitigate the training cost of GNNs, but they still require many training iterations. In this paper, we propose training- free GNNs, which can be deployed instantly as soon as the model is initialized. Besides, our method can be improved with optional training. In the optional training mode, the speed up techniques mentioned above can be combined with our method to reduce the training time further.
7.3 Expressive Power of GNNs
Expressive power (or representation power) means what kind of functional classes a model family can realize. The expressive power of GNNs an important field of research in its own right. If GNNs cannot represent the true function, we cannot expect GNNs to work well however we train them. Therefore, it is important to elucidate the expressive power of GNNs. Originally, Morris et al. [I and Xu et al. passing GNNs are at most as powerful as the 1-WL test, and they proposed k-GNNs and GINs, which are as powerful as the WL and 1-WL tests, respectively. GINs are the most powerful message- message-passing GNNs. Sato BN By and Loukas 2 showed that pressage-passing GNNs are as powerful as a computations model of distributed local algorithms, and they proposed GNNs that are as powerful as port- nort-numbering and randomized local algorithms. Loukas 26 showed that GNNs are Turing-complete under certain conditions (i.e., with unique node ids and infinitely increasing depths). Some other works showed that GNNs can solve cannot solve some specific problems, e.g., GNNs can recover the underlying geometry 37. GNNs cannot
53 showed that message-
10

---

Published in Transactions on Machine Learning Research (8/2024)
recognize bridges and articulation points bri There various efforts to improve the expressive power of We refer the readers to survey papers 18 36 for
GNNs by non-messag-passinng architectures 27 more details on the expressive power of GNNs.
28 32
We contributed to the field of the expressive power of GNNs by showing that GNNs with LaF are more powerful than GNNs without LaF. Specifically, we showed that GNNs with LaF can represent an important model, label propagation, while GNNs without LaF cannot. It should be emphasized that GLNs, the most powerful messagg-passing GNNs, and
GNNs cannot represent label propagation without LaF because they do not have access to the label information label propagation uses, and also noted that GINs traditionally do not use LaF. This result indicates that it is important to consider what to input to the GNNs as well as the architecture of the GNNs for the expressive power of GNNs. This result provides a new insight into the field of the expressive power of GNNs.
8 Limitations
Our work has several limitations. First, LaF and TFGNNs cannot be applied to inductive settings while most GNNSs can. We do not regard this as negative point. Popular GNNs such GCNs and GATs are applicable to both transductive and inductive settings and are often used for transductive settings. However, this also means that they do not take advantage of transductive-speeffe structures (those that are not present in inductive settings). We believe that it is important to exploit inductive-specific techniques for inductive settings and transductive-specific techniques (such as LaF) for transductive settings in order to pursue maximum performance.
Second, TFGNNs cannot be applicd hetcrophilious graphs, or its performance degrades as TFGNNs are based label propagation. The same argument mentioned above applies. Relying on homophilious graphs is not a negative point in pursuing maximum performance. Tt should be noted that LaF may also be exploited in heterophilious settings well. Developing training- free GNNs for heterophilious graphs based on LaFF is an interesting future work.
Third, we did not aim to achieve the state-of-the-art performance. Exploring the combination of LaF with fancy techniques to achieve state-of-the-art performance is left as future work.
Finally, we did not explore applications of LaF other than TFGNNs. LaF can help other GNNs in non- training-fres free settings well. Exploring the application of LaF to other GNNs is left future work.
9 Conclusion
In this paper, we made the following contributions.
We advocated the use of LaF in transductive learning (Section 3
We confirmed that LaF is admissible in transductive learning, but LaF has not been explored in the field of GNNs such as GCNs and GATs.
We formally showed that LaF strengthens the expressive power of GNNs (Section
We showed that GNNs with LaF can represent label propagation (Theorem 4.1 while GNNs without LaF cannot (Proposition 1.2
We proposed training-free graph neural networks, TFGNNs (Section
We showed that TFGNNs defined by Eqs. 19
29 meet the requirements of training-free free
models (Definition 5.1 by showing that the initialized TEGNNs approximate label propagation
in Proposition 5.2
We confirmed that TFGNNs outperform existing GNNs in the training free setting. (Section 6
We showed that TFGNNs outperform GCNs and GATs in all of the seven datasets in the training-free setting (Table I.
11

---

Published in Transactions on Machine Learning Research (8/2024)
TFGNNs achieve non-trivial accuracy without training and can be deployed instantly as soon as the model is initialized. These results corroborate that TFGNNs are training-free (Definition 5.1
We also note that our idea can be applied to other machine learning models than graph neural networks. We hope that this papers opens the door to new research direction of training-free neural nelworks.
References
[1] R. Addanki, P. W. Battaglia, D. Budden, A. Deac, J. Godwin, T. Keck, W. T. S. Li, A. Sanchez- Gonzalez, J. Stott, S. Thakoor, and P. Velickovic. Large-scale graph representation learning with very deep gnns and self-supervision. arXiv, 2021. URL https://arxiv. wwtgg//bb/1/0..../ 09422
[2] D. W. Blalock, J. J. G. Ortiz, J. Frankle, and J. V. Guttag. What is the state of neural network pruning? In Proceedings of Machine Learning and Systems 2020, MLSSs, 2020.
[3] D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the 34th AAAI Conference on Artificial Intelligence, AAAI, pages 3438-3445, 3445, 2020.
[4] J. Chen, T. Ma, and C. Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In Proceedings of the 6th International Conference on Learning Representations, ICLR, 2018.
[5] M. Chen, Z. Wei, Z. Huang, B. Ding, and Y. Li. Simple and deep graph convolutional networks. In Proceedings of the 37th International Conference on Machine Learning, ICML, pages 1725 1735, 2020.
[6] W. Chiang, X. Liu, S. Si, Y. Li, S. Bengio, and C. Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 257-266, 2019.
[7] W. Fan, Y. Ma, Q Li, Y. He, Y. E. Zhao, J. Tang, and D. Yin. Graph neural networks for social recommendation. In The Web Conference 2019, WWW, pages 417-426, 2019.
[8] C. Gallicchio and A. Micheli. Graph echo state networks. In International Joint Conference on Neural Networks, IJCNN, pages 1 1-8, 2010.
[9] C. Gallicchio and A. Micheli. Fast and deep graph neural networks. In Proceedings of the 34th AAAT Conference on Artificial Intelligence, AAAI, pages 3898 3905, 2020.
[10] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning, 1CML, pages 1263- 1272, 2017.
[1]] X. Glorot and Y. Bengio. Understanding the difficulty of training deep feodforward ncural networks. In Proceedings of the Thirleenth International Conference on Artificial Intelligence and Statistics, AIS- TATS, pages 249 249-256, 256, 2010.
[12] M. Gori, G. Monfardini, and F. Scarselli. A new model for learning in graph domains. In Proceedings of the International Joint Conference on Neural Networks, IJCNN, volume 2, pages 729-734, 2005.
[13] W. L. Hamilton, Z. Ying, and J. Leskovec. Inductive representation lcarning on large graphs. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, NewrIPS, pages 1024 1034, 2017.
[14] S. Han, J. Pool, J. Tran, and W. J. Dally. Learning both weights and connections for efficient neural network. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, NeurIPS, pages 1135 1143, 2015.
[15] X. He, K. Deng, X. Wang, Y. Li, Y. Zhang, and M. Wang. Lightgen: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, SIGIR, pages 639-648. 2020.
[16] W. Huang, T. Zhang, Y. Rong, and J. Huang. Adaptive sampling towards fast graph representation learning. In Advances in Neural Information Processing Systems 31, NewrIPS, 2018
12

---

Published in Transactions on Machine Learning Research (8/2024)
[17] B. Jacob, S. Kligys, B. Chen, M. Zhu, M. Tang, A. G. Howard, H. Adam, and D. Kalenichenko. Quantization and training of neural networks for efficient integer-arithmeticoonly inference. In 2018 IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pages 2704 2713, 2018.
[18] S. Jegelka. Theory of graph neural networks: Representation and learning. ar abs/2204.07697, 2022.
[19] J. Jo, S. Lee, and S. J. Hwang. Score- generative modeling of graphs via the system of stochastic differential equations. In International Conference on Machine Learning, ICML, pages 10362-10338 10388, 2022.
[20] T. N. Kipf and M. Welling, Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Learning Represenlations, ICLR, 2017.
[21] R. Krishnamoorthi. Quantizing deep wowwolutionoloooooooooooooooooi. networks networks for efficient inference: A whitepaper. ar abs/1806.00
2018. URL http:/pp///arit.oor////////000.0
[22] Q. Li, Z. Han, and X. Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the 32nd AAAI Conference Artificial Intelligence, AAAI, pages 3538- 3545, 2018.
233 7. Liu, C. Chen, X. Yang, J. Zhou, X. Li, and L. Song. Heterogeneous graph neural networks for malicious account detection. In Proceedings of the 27th ACM International Conference Information and Knowledge Management, CIKM, pages 2077-2087 2018.
[24] 7. Liu, C. Chen, L. Lí, J. Zhou, X. Ti, L. Song, and Y. Qi. Geniepath: Graph neural networks with adaptive receptive paths. In The Thirty Third AAAI Conference on Artificial Intelligence, AAAI, pages 4424-4431, 2019.
25 I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In 7th International Conference on Learning Representations, ICLR, 2019.
[26] A. Loukas. What graph neural networks cannot learn: depth vs width. In Proceedings of the 8th International Conference Learning Representations, ICLR, 2020.
[27] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS, pages 2153 2164, 2019.
[28] H. Maron, H. Hen-Hamm, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In Proceedings of the 7th International Conference Learning Representations, ICLR, 2019.
[29] A. Micheli and D. Tortorella. Addressing heterophily in node classification with graph echo state networks. Neurocomputing, 550:126506, 2023.
(30]
Micikevicius, S. Narang, J. Alben, G. F. Diamos, E. Elsen, D. García, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, and H. Wu. Mixed precision training. In 6th International Conference on Learning Representations, ICLR, 2018.
[31] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence, AAAI, pages 4602-4609, 2019.
[32] R. L. Murphy, B. Srinivasan, V. A. Rao, and B. Ribeiro. Relational pooling for graph representations. In Proceedings of the 36th International Conference Machine Learning, TCML, pages 4663-4673 2019.
[33] K. Oono and T. Suzuki. Graph neural networks exponentially lose expressive power for node classifica- tion. In Proceedings of the 8th International Conference on Learning Representations, ICLR, 2020.
[34] N. Park, A. Kan, X. L. Dong, T. Zhao, and C. Faloutsos. Estimating node importance in knowledge graphs using graph neural networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD, pages 596-606, 2019.
335] Y. Rong, W. Huang, T. Xu, and J. Huang. Dropedge: Towards deep graph convolutional networks on node classification. In 8th International Conference on Learning Representations, ICLR, 2020.
13

---

Published in Transactions on Machine Learning Research (8/2024)
[36] R. Sato. A survey on the expressive power of graph neural networks. arXiu, abs abs/2003.04078, 2020. URL httt:://arxiv.oo//bbb////// 04078
[37] R. Sato. Graph neural networks can recover the hidden features solely from the graph structure. Tn International Conference on Machine Learning, 1CML, pages 30062-30000 20022,, 2023.
[38] R. Sato, M. Yamada, and H. Kashima. Approsimation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS, pages 4083 4092, 2019.
[39] R. Sato, M. Yamada, and H. Kashima. Random features strengthen graph neural networks. In Pro- ceedings of the 2021 STAM International Conference on Data Mining, SDM, pages 333-341, 2021.
[40] R. Sato, M. Yamada, and H. Kashima. Constant time graph neural networks. ACM Trans. Knowl. Dis- cov. Data, 16(5):92 92:31, 2022. doi: 10.1145/3502723 URL https::/doi..rrg 10. 1145/35273333
[41] F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. TEEE Trans. Neural Networks, 20(1):61 80, 2009. doi: 10.1109/TNN, 200..N20000002000000.... URL https://doi. org/10. 110.1111TTTN,... 2008. 2005605
[22] O. Shchur, M. Mumme, A. Bojchevski, and S. Günnemann. Pitfalls of graph neural network evaluation. Xiv, 2018.
[43] X. Sun, N. Wang, C. Chen, J. Ni, A. Agrawal, X. Cui, S. Venkataramani, K. E. Maghraoui, V. Srinivasan, and K. Gopalakrishnan. Ultra-low precision 4-bit training of deep neural networks. In Advances in Newral Information Processing Systems 33: Annual Conference on Nearal Information Processing Systems 2020, NewrIPS, 2020.
[44] Y. Tian, H. Song, Z. Wang, H. Wang, Z. Hu, F. Wang, N. V. Chawla, and P. Xu. Graph neural prompting with large language models. In Thirty-Eighth AAAI Conference on Artificial Intelligence,
A AAAT, AT, pages 19080-19088, 2024.
[45] P. Velickovic, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks.
In Proceedings of the 6th International Conference Learning Representations, ICLR, 2018.
[46] D. Wang, Y. J.Qi, J. Lin, P. Cui, Q. Jia, Z. Wang, Y. Fang, Q Yu, J. Zhou, and S. Yang. A semi-supervised graph attentive nerw for financial fraud detection. In 2019 IEEE International Conference on Dala Mining, ICDM, pages 598 1188607,220 2019.
[47] H. Wang, M. Zhao, X. Xie, W. Li, and M. Guo. Knowledge graph convolutional networks for recom- mender systems. In The World Wide Web Conference, WWW, pages 3307-3313, 2019.
[48] N. Wang, J. Choi, D. Brand, C. Chen, and K. Gopalakrishnan. Training deep neural networks with 8-bit floating point numbers. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NewrTPS, pages 7686 7686-7695, 2018.
[49) X. Wang, X. He, Y. Cao, M. Liu, and T. Chua. KGAT: knowledge graph attention network for recommendation. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 950 958, 2019.
[0] Y. Wang, J. Jin, W. Zhang, Y. Yu, Z. Zhang, and D. Wipf. Bag of tricks for node classification with graph neural networks. arXiv preprint arXiv:2103. 13355, 2021.
[51] Y. Wang, J. Jin, W. Zhang, Y. Yang, J. Chen, Q. Gan, Y. Yu, Z. Zhang, Z. Huang, and D. Wipf. Why propagate alone? parallel use of labels and features on graphs. In The Tenth International Conference on Learning Representations, ICLR, 2022.
[22] H. WU, P. Judd, X. Zhang, M. Isacv, and P. Micikevicius. Integer quantization for deep learning inference: Principles and empirical evaluation. arXiv, abs/2004.09603 2020. URL https://arxix: org/abs/2004. 09602
[33] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations, ICLR, 2019.
[54] Z. Yang, W. W. Cohen, and R. Salakhutdinov. Revisiting semi-supervised learning with graph embed- dings. In Proceedings of the 33rd International Conference on Machine Learning, ICML, pages 40-48, 2016.
14

---

Published in Transactions on Machine Learning Research (8/2024)
[55] R. Ying, R. He, K. Chen, P. Eksombatchai, W. L. Hamilton, and J. Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD, pages 974 983, 2018.
[66] H. Zeng, H. Zhou, A. Srivastava, R. Kannan, and V. K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Represenlations, ICLR, 2020.
[77]
B. Zhang, S. Luo, L. Wang, and D. He. Rethinking the expressive power of gnns via graph biconnectivity,
In The Eleventh International Conference on Learning Representations, ICLR, 2023.
58
X. Zhu and Z. Ghahramani. Learning from labeled and unlabeled data with label propagation. 2002.
[99
D. Zou, Z. Hu, Y. Wang, S. Jiang, Y. Sun, and Q. Gu. Layer-dependent importance sampling for training
deep and large graph convolutional networks. In Advances in Neural Information Processing Systems
82: Annual Conference on Newral Information Processing Systems 2019, NewrIPS, pages 11247-11256.
2019.
15


Reviews:
[{"review_id": "aIMVQAJ20g", "reviewer": "Reviewer_uEBa", "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:\t\n\nThe idea is simple and elegant. It is surprising that this obvious fact was not used before, so it's good for the authors to illustrate it.\n\nThe paper is admirably clear.\n\nThe approach does seem to work well, at least on the small examples tried.\n\nOverall I see why it has been submitted to TMLR, as it is clearly an interesting and useful contribution, yet one which might be rejected from other conferences for being \"too simple\" (in reality, a strength).\n\nWeaknesses:\n\n- The experimental section is a good demonstration of the approach, but it’s still relatively limited. I think the claims made aren't completely supported by the experiments. See requested changes, I think this is easily fixable.\n\n- I did not get any deep insight from the proof about label propagation (it seems to just point out the obvious fact that one can’t propagate labels if one doesn’t know the labels).\n\n- This is more a weakness of me as a reviewer, but I don't know whether or not there is some work out in the broader graph-machine-learning (not just graph neural network) literature that would make this approach less novel or less interesting.", "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 authors propose the somewhat strange yet defensible idea of graph neural networks which work without any training. The idea is that in many situations, graph neural networks are used for transductive node classification, where the goal is to take a graph and impute information about neighboring nodes from some known nodes on the same graph. In particular, the authors point out that it is completely admissible in this setting to treat the label information on the known nodes as feature information (this is not “training on the test set”, since the labels of the target nodes are still unknown). The authors then show the somewhat straightforward fact that with labels as features, transductive GNNs can implement the classic algorithm of label propagation, while in general they cannot without labels as features. Finally, they describe their training-free graph neural networks (TFGNN). These are initialized to approximate label propagation and can therefore be immediately used, without any training, to perform transductive node classification. But they are also just regular graph neural networks which can still be trained for improved performance. In experiments on small standard datasets, the authors show that TF-GNNs outperform other GNNs in a number of interesting ways.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Comments for authors: the discussion around equation 6 is a little unclear to me still. My sense is that doing things this way is necessary for good generalization, but that it would not actually be incorrect to simply train on the labels as features. If so, I think that should be made explicit, as “leaking information” sounds like something which would make any reported results invalid, rather than just being something that happens during training and hurts performance. [non-critical change]\n\nSubsections 6.5 and 6.6:\n\nThese are reasonable experiments, which are suggestive evidence for the benefits of TF-GNNs, but I think the claims made in the text are too strong given the experiments. I would ask the authors to simply add some small amount of hedging and qualifying language to acknowledge the more limited scope of the experiments, which should not be difficult. I have nonetheless answered \"Yes\" to the claims and evidence question on the review form, because I think these changes should be pretty small [critical change].", "broader_impact_concerns": "I don't see any broader impact concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "c8kM74VGeM", "reviewer": "Reviewer_KtFe", "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. The label as feature technique is simple but seems effective with experimental results.\n2. The effect of LaF are sufficiently proven.\n3. The TFGNN shows impressive performance compared with existing baselines in a training-free setting.\n\nWeakness:\n1. It seems the initialization of TFGNN is an important technique. But it lacks explanation of why such initialization works.\n2. It lacks sufficient comparison of TFGNN and other GNN baselines when conducting optimal training. Furthermore, in training-free setting, the baselines is not sufficient. For example, what will happen if you replace LaF to other features such as random feature or laplacian eigen-vectors?\n3. TFGNN is limited in transudative learning and in a semi-supervised learning setting. In my opinion, the training-free benefits come from the following aspects (not limited to): 1) annotation is expensive, 2) training large graph is expensive. However, the proposed TFGNN is relied on the annotations (they use labels as features). Furthermore, the scalability of TFGNN is not demonstrated when graph is very large. Although this is an interesting work, the value of \"training-free\" is limited.\n4. TFGNN is heavily relied on the labels. But in reality, there are many scenario that the labels are sparse. Is this method robust to these scenarios?\n5. The concerns of training and inference latency. This method needs to sample subgraphs for each target node, thus it has low efficiency.", "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": "1. The authors advocate the labels as features for transductive learning. And they formally demonstrate the LaF can strengthen the expressive power of GNN. \n2. They propose the TFGNN based on the LaF technique, which is training-free and can be promoted by training as well.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Please refer to Weakness 1. Please add explanations of why such initialization works.\n2. Please refer to Weakness 2. Please add suggested experimental results on both training-free and training setting to make it more convincing.\n3. Please refer to Weakness 3. Please demonstrate the value of \"training-free\" of your proposed method.\n4. Please refer to Weakness 4. Please add experiments and discussion on scenario with sparse labels.\n5. Please refer to Weakness 5. Please add experiments on training and inference latency.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DDlcIDNRaJ", "reviewer": "Reviewer_9hwo", "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": "This article is clearly written, tackles an important problem, and provide an interesting approach, which is both easy to deploy and backed up by theoretical guarantees in the context of transductive node classification. To me, the main weaknesses are about some imprecisions in the text, as well as some missing details and results in the experiments. Overall, I think it is well suited for TMLR after some clarifications have been made (see below).", "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 artice, the authors propose a new methodology for performing transductive node classification within a graph, where the task is to classify some nodes of a given graph, given some other nodes (on the same graph) on which the labels are known. For this, the authors suggest to use labels as features (LaF), that is, to encode the ground-truth labels (of the training nodes) as explicit features for message-passing graph neural network (GNN) architectures, instead of only using external features for the GNNs and then inferring the labels from the GNNs outputs. On the theoretical side, the authors demonstrate that, upon careful initialization of the GNN weights, and even without any training, the GNNs fed with LaF are at least as powerful as label propagation, where labels are inferred from the first training nodes reached by random walks originating from the test node to classify. On the experimental side, the authors designed experiments where untrained message-passing GNNs with LaF and clever initialization achieved better accuracies than other untrained GNN architectures (even with LaF). They also empirically showed faster convergence to the saturating accuracies, as well as better robustness to external feature noise.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "p3, first paragraph in section 3: the vector y_v has not beed defined. I figured from the text that it must be some sort of one-hot encoding of the labels, but this should be made explicit.\n\np5, last line in the proof of theorem 4.1: the second term has to converge to zero (the result is not true if this term only diminishes, as it could decrease to a minimum other than zero). Furthermore, I think this convergence has to be uniform across all nodes for the result to hold in the case of graphs with infinitely many nodes (if the graph is assumed to be finite, simple convergence is enough).\n\np6: a complementary figure could definitely be useful to illustrate equations (22) to (28).\n\np6: the role of the matrix U is unclear to me. What are the coefficients of the columns 0 to -|Y|-1 (in numpy notations)? If they are nonzero, then I don't see why \"U picks the last |Y| dimensions\" (as claimed at the end of the page). If they are zero, then 1. it should be mentioned explicitly, 2. the external features (other than the labels) are not used at all when building the predictions.\n\np7, table 1: why are there no variances in the results? It would be more convincing to make several runs with different training nodes, and provide the average + standard deviations of the accuracies. Also, it would be nice to explain / comment on the fact that for other GNN architectures, adding LaF actually degrades the accuracy (such as, e.g., GAT in CiteSeer), which looks counter-intuitive.\n\np8, Figure 1: why is there no variance in the curve whereas there is variance in Figures 2 and 3?\n\np8, Sections 6.4 and 6.5: were the GCNs trained with or without LaF? Providing both (and thus making three curves in Figs 2 and 3; one for TFGNNs, one for GCNs without LaF, one for GCNs with LaF) would be better.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is interesting to the GNN community, and proposes terminology and mapping of existing and new ideas that allow the training-free approach of Graph Neural Networks. There is a clear consensus among the reviewers that the paper should be accepted.
Decision: Accept (poster)