Graph-less Neural Networks: Teaching Old MLPs New Tricks Via Distillation
Authors: Shichang Zhang
Yozen Liu
Yizhou Sun
Neil Shah
Venue: ICLR 2022 Poster (2022)
Keywords: Graph Neural Networks
Distillation
Node Classification
Model Inference Acceleration

Abstract: Graph Neural Networks (GNNs) are popular for graph machine learning and have shown great results on wide node classification tasks. Yet, they are less popular for practical deployments in the industry owing to their scalability challenges incurred by data dependency. Namely, GNN inference depends on neighbor nodes multiple hops away from the target, and fetching them burdens latency-constrained applications. Existing inference acceleration methods like pruning and quantization can speed up GNNs by reducing Multiplication-and-ACcumulation (MAC) operations, but the improvements are limited given the data dependency is not resolved. Conversely, multi-layer perceptrons (MLPs) have no graph dependency and infer much faster than GNNs, even though they are less accurate than GNNs for node classification in general. Motivated by these complementary strengths and weaknesses, we bring GNNs and MLPs together via knowledge distillation (KD). Our work shows that the performance of MLPs can be improved by large margins with GNN KD. We call the distilled MLPs Graph-less Neural Networks (GLNNs) as they have no inference graph dependency. We show that GLNNs with competitive accuracy infer faster than GNNs by 146X-273X and faster than other acceleration methods by 14X-27X. Under a production setting involving both transductive and inductive predictions across 7 datasets, GLNN accuracies improve over stand-alone MLPs by 12.36% on average and match GNNs on 6/7 datasets. Comprehensive analysis shows when and why GLNNs can achieve competitive accuracies to GNNs and suggests GLNN as a handy choice for latency-constrained applications. 

Published as a conference paper at ICLR 2022
GRAPH-LESS NEURAL NETWORKS: TEACHING OLD MLPs NEW TRICKS VIA DISTILLATION
Shichang Zhang
Yozen Liu
University of California, Los Angeles sh shichange cs. ucla edu
Snap Inc. y iluu@saapp
Yizhou Sun
Neil Shah
University of California, Los Angeles yzsunêes ucla. edu
Snap Inc. nshah@ snap. com
ABSTRACT
Graph Neural Networks (GNNs) are popular for graph machine learning and have shown great results on wide node classification tasks. Yet, they are less popular for practical deployments in the industry owing to their scalability challenges incurred by data dependency. Namely, GNN inference depends on neighbor nodes multiple hops away from the target, and fetching them burdens latency latency-constrained applications. Existing inference acceleration methods like pruning and quantiza- tion can speed up GNNs by reducing operations, but the improvements are limited given the data dependency not resolved. Conversely, multi-layer perceptrons (MLPs) have no graph dependency and infer much faster than GNNs, even though they are less accurate than GNNs for node classification in general. Motivated by these complementary strengths and weaknesses, we bring GNNs and MLPs together via knowledge distillation (KD). Our work shows that the performance of MI.s be improved by large margins with GNN KD. We call the distilled MLPs Graph-less Neural Networks (GLNNs) as they have no inference graph dependency. We show that GLNNs with competitive accuracy infer faster than GNNs by 146x-273x and faster than other accelcration methods by 14x-27x. Under production setting involving both transductive and inductive predictions across 7 datasets, GLNN accuracies improve over stand-alone MLPs by 12.36% on average and match GNNs on 6/7 datasets. Comprehensive analysis shows when and why GLNNs can achieve competitive accuracies to GNNs and suggests GLNN as a handy choice for latency-constraingg applications.
(MAC)
INTRODUCTION
Graph Neural Networks (GNNs) have recently become very popular for graph machine learning (GML) research and have shown great results on node classification tasks (Kipf & Welling, 2016; Hamilton et al., 2017; Veličković al., 2017) like product prediction on co-purchasing graphs and paper category prediction on citation graphs. However, for large-scale industrial applications, MIPss remain the major workhorse, despite common (implicit) underlying graphs and suitability for GML formalisms. One reason for this academie-industrial gap is the challenges in scalability and deployment brought by data dependency in GNNs (Zhang et al., 2020; Jia et al., 2020), which makes GNNs hard to deploy for latency- conntyyconstrrinee applications that require fast inference.
Neighborhood fetching caused by graph dependency is one of the major sources of GNN latency. Inference on a target node necessitates fetching topology and features of many neighbor nodes, especially on small-world graphs (detailed discussion in Section 4). Common inference acceleration techniques like pruning (Zhou et al., 2021) and quantization (Tailor et al., 2021; Zhao et al., 2020) can speed up GNNs to some extent by reducing Multiplication-ane -nwaancumllattionnn (MAC) operations.
Work done when author snap-resea www.rreeeerrcggggggeeeeeeee ess- neura -networks
intern at Snap Inc. Code available https: //gi thub.

---

Published as a conference paper at ICLR 2022
However, their improvements are limited given the graph dependency is not resolved. Unlike GNNs, MLPs have no dependency on graph data and are easier to deploy than GNNs. They also enjoy the auxiliary benefit of sidestepping the cold-start problem that often happens during the online prediction of relational data (Wei et al., 2020), meaning MLPs can infer reasonably even when neighhor information of a new encountered node is not immediately available. On the other hand, this lack of graph dependency typically hurts for relational learning tasks, limiting MLP performance on GML tasks compared to GNNs. We thus ask: can we bridge the two worlds, enjoying the low-latency, dependency-free nature of MLPs and the graph
of GNNs at the same time?
Present work. Our key finding is that it is possible to distill knowledge from GNNs to MLPs without losing significant performance. but reducing the inference time drastically for node classification. The knowledge distillation (KD) can be done offlin,, coupled with model training. In other words, we can shift considerable work from the eeeeecc-onsttrieedd inference step, where time reduction in milliseconds makes huge difference, to the less time-sensitive training step, where time cost in hours or days is often tolerable. We call our approach Graph-less Neural Network (GLNN). Specifically, GLNN is a modeling paradigm involving KD from a GNN teacher to a student MLP; the resulting GLNN is MLP optimized through KD,, so it enjoys the benefits of graph context- awareness in training but has no graph dependency in inference. Regarding speed, GLNNs have superior efficiency and 146x-273x faster than GNNs and 14x-27x faster than other inference acceleration methods. Regarding performance, under a production setting involving both transductive and inductive predictions on 7 datasets, GLNN accuracies improve over MLPs by 12.36% on average and match GNNs on 6/7 datasets. We comprchensively study when and why GLNNs can achieve competitive results as GNNs. Our analysis suggests the critical factors for such great performance are large MLP sizes and high mutual information between node features and labels. Our observations align with recent results in vision and language, which posit that large enough (or slightly modified) MLPs can achieve similar results as CNNs and Transformers (Liu et al., 2021; Tolstikhin et al., 2021; Melas- Keriaziy 2021;
Touvron et al., 2021; Ding et al., 2021). Our core contributions are as follows:
We propose GLNN, which eliminates neighbor-fetching latency in GNN inference via KD to MLP. We show GLNNs has competitive performance as GNNs, while enjoying 146x-273x faster inference than vanilla GNNs and 14x-27x faster inference than other inference acceleration methods.
We study GLNN properties comprehensively by investigating their performance under different settings, how they work regularizers, their inductive bias, expressiveness, and limitations.
2 RELATED WORK
Graph Neural Networks. The early GNNs generalize convolution nets to graphs (Bruna et al., 2014; Defferrard et al., 2017) and later simplified to message-passing neural net (MPNN) by GCN (Kipf' & Welling, 2016). Most GNNs after can be put as MPNNs. For example, GAT employs attention (Veličković et al., 2017), PPNP employs personalized PageRank (Klicpera et al., 2019), GCNII and DeeperGCN employ residual connections and dense connections (Chen et al., 2020; Li et al., 2019).
Inference Acceleration. Inference acceleration have been proposed by hardware improvements (Chen al., 2016; Judd al., 2016) and algorithmic improvements through pruning (Han al., 2015), quantization (Gupta et al., 2015). For GNNs, pruning (Zhou et al., 2021) and quantizing GNN parameters (Zhao al., 2020) have been studied. These approaches speed up GNN inference to certain extent but do not eliminate the neighbor-fetching latency. In contrast, our cross-model KD solves this issue. Concurrently, Graph-MLP also tries to bypass GNN neighbor fetching (Hu et al., 2021) by training an MLP with neighbor contrastive loss, but it only considers transductive but not the more practical inductive setting. Some sampling works focus on speed up GNN training (Zou et al., 2019; Chen et al., 2018 8), which are complementary to our goal on inference acceleration.
GNN distillation. Existing GNN KD works try to distill large GNNs to smaller GNNs. LSP (Yang et al., 2021b) and TinyGNN (Yan et al., 2020) do KD while preserving local information. Their students are GNNs with fewer parameters but not necessarily fewer layers. Thus, both designs still require latency-inducing fetching. GFKD (Deng & Zhang, 2021) does graph-level KD via graph generation. In GFKD, data instances are independent graphs, whereas we focus on dependent nodes within a graph. GraphSAIL (Xu et al., 2020) uses KD to lear students work well on new data while preserving performance on old data. CPF (Yang et al., 2021a) combines KD and label propagation (L.P). The student in CPF is not GNN, but it is still heavily graph-dependent it uses I.P.
2

---

Published as a conference paper at ICLR 2022
164
resgrr
33008.43
MLP
MLP
GmapSAGGE
3.0
GraphSAGE
Voses Fetcted
2.5
2.0
1.5
2.0
964
0.5
2077 30
520
10
30
30
0.0
0.59
1.84
2.34
Layers
Layers
The number of fetches and the inference time of GNNs are both magnitudes more than MLPs and grow exponentially as functions of the number of layers. Left: neighbors need to be fetched for two GNN layers. Middle: the total number of fetches for inference. Right: the total inference time. (Inductive inference for 10 random nodes on OGB Products (Hu et al., 2020))
Figure 1:
3 PRELIMINARIES
Notations. For GML tasks, the input is usually a graph and its node features, which we write as EV, with V stands for all nodes, and stands for all edges. Let N denote the total number of nodes. We use X E NxD to represent node features, with row E. being the D-dimensional feature of node e E V. We represent edges with an adjacency matrix A, with Ag, and 0 otherwise. For node classification, one of the most important GML applications, the prediction targets are Y N where row y, is K-dim one-hot vector for node u. For a given G, usually small portion of nodes will be labeled, which we mark using superscript 1. i.e. V XL. and Y The majority of nodes will be unlabeled, and we mark using the superscript U i.e.e DU X and Y
if edge (u, v) E E.
Graph Neural Networks. Most GNNs fit under the message-passing passing framework, where the rep- resentation h, of each node v is updated iteratively in each layer by collecting messages from its neighbors denoted as (w). For the 1-th layer, h!"' is obtained from the previous layer representation he (t-1) (he x..)) via aggregation operation AGGR followed by an UPDATE operation and
h Nu)) = AGGR (n (-1) : : =EN()))))
h = UPDATE(H (1) N(u)> (111))
4 MOTIVATION
GNNs have considerable inference latency due to graph dependency. One more GNN layer means fetching one more hop of neighbors. To infer a node with a L-layer GNN graph with average degree requires ORR") fetches. can be large for real-world graphs, e.g. 208 for the Twitter (Ching al., 2015). Also, layer fetching must be done sequentially, the total latency explodes quickly as L increases. Figure shows the dependency added by each GNN layer and the exponential explosion of inference time. In contrast, the MIP inference time is much smaller and grows linearly. This marked gap contributes greatly to the practicality of MLPs in industrial applications over GNNs.
The node-fetching latency exacerbated by two factors: firstly, newer GNN architectures are getting deeper from 64 layers (Chen et al., 2020) to even 1001 layers (Li et al., 2021). Secondly, industrial- scale graphs are frequently too large to fit into the memory of single machine (Jin al., 2022), necessitating sharding of the graph out of the main memory. For example, Twitter has 288M monthly active users (nodes) and an estimated 60B followers (edges) as of 3/2015. Facebook has 1.39B active users with more than 400B edges as of 12/2014 (Ching et al., 2015). Even when stored in marse-matrixx -atrix- format (often COO or CSR), these graphs are on the order of TBs and are constantly growing. Moving away from in- in-memory storage results in even slower nnighbor-fetching
MLPs, on the other hand, lack the means to exploit graph topology, which hurts their performance for node classification. For example, test accuracy on Products is 78.61 for GraphSAGI. compared to 62.47 for an equal-sized MLP. Nonetheless, recent results in vision and language posit that large (or slightly modified) MLPs can achieve similar results CNNs and Transformers (Liu al., 2021). We thus also ask: Can we bridge the best GNNs and MLPs to get high- high-accuracy and low-latency models? This motivates to do cross-model KD from GNNs to ML.ss
3

---

Published as a conference paper at ICLR 2022
Offline Training with Distillation
Online Prediction New Nodes
Trained GNN
Soft Targets
nodeledgesin dashed lineg
dependency on graph grey
Deployed GLNN
Knowledge
MLP
Only Node Features
Student
Deploy
Figure The GLNN framework: In offline training, a trained GNN teacher applied on the graph for soft targets. Then, student MLP is trained on node features guided by the soft targets. The distilled MLP, now GLNN, deployed for online predictions. Since graph dependency climinated for inference, GLNNs infer much faster than GNNs, and hence the name "Graph-less Neural Network."
5 GRAPH-LESS NEURAL NETWORKS
We introduce GLNN and answer exploration questions of its properties: 1) How do GLNNs compare to MIPs and GNNs? 2) Can GLNNs work well under both transductive and inductive settings? 3) How do GLNNs compare to other inference acceleration methods? 4) How do GLNNs benefit from KD? 5) Do GLNNs have sufficient model expressiveness? 6) When will GLNNs fail to work?
5.1 THE GLNN FRAMEWORK
The idea of GLNN is straightforward, yet as we will extremely effective. In short, we train "boosted" MLP via KD from a teacher GNN. KD was introduced in Hinton et al. (2015), where knowledge transferred from cumbersome teacher soft targets 2, for each node v with a teacher GNN. Then we train a student MLP with both true labels yo and 2,. The objective is Equation with À being weight parameter, Ltahet being the cross-entropy between y, and student predictions ÿ.- Lreacher being the KL.-divergence.
simpler student. In case, we generate
L XEneve Llabel (g. Bo) + (1 AVE (ūv, z.)
The model after KD, i.e. GLNN, essentially a MI.P Therefore, GLNNs have no graph dependency during inference and fast MIPs.. On the other hand, through offline KD, GLNN parameters are optimized to predict and generalize as well as GNNs, with the added benefit of faster inference and easier deployment. In Figure 2, we show the offline KD and online inference steps of GLNNs.
5.2 EXPERIMENT SETTINGS
Datasets. We consider all five datasets used the CPF paper (Yang et al., 2021a), i.e. Cora, Citeseer, Pubmed, A-computer, and A-photo. To fully evaluate method, we also include two more larger OGB datasets (Hu et al., 2020), ie. Arxiv and Products.
Model Architectures. For consistent results, aggregation as the teacher. We conduct ablation studies of other GNN teachers like GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017) and, APPNP (Klicpera et al., 2019) in Section 6.
GraphSAGE (Hamilton al., 2017) with GCN
Evaluation Protocol. For all experiments this section, we report the average and standard deviation over ten with different random seeds. Model performance is measured accuracy, and results are reported on test data with the best model selected using validation data.
Transductive Inductive. Given G, X, and Y we consider node classification under two settings: transductive (tran) and inductive (ind). For ind, we hold out some test data for inductive evaluation only. We first select inductive nodes yd Do which partitions Do into the disjoint inductive subset and observed subset, i.e. D Du LIV Andt Then hold out a and all edges connected D
and which leads to disjoint graphs Gobs L. Gend with no shared nodes or
4

---

Published as a conference paper at ICLR 2022
Table 1: GLNNs outperform MLPs by large margins and match GNNs on of datasets under the transductive setting. AMLP (AGNN) represents difference between the GLNN and trained MLP (GNN). Results show accuracy (higher is better); AGN 20 indicates GLNN outperforms GNN.
Datasets
SAGE
MLP
GLNN
AMIP
AGNN
Cora
80.52 + 1.77
59.22 = 1.31
80.54 1.35
21.32 (36.00%)
0.02 (0.02%)
Citeseer
70.33 + 1.97
59.61 + 2.88
71.77 + 2.01
12.16 (20.40%)
1.44 (2.05%)
Pubmed
75.39 2.09
1
75.42 + 2.31
7.87 (11.65%)
0.03 (0.04%)
A A-computer
82.97 2.16
67.80 + 1.06
83.03 + 1.87
15.23 (22.46%%
0.06 (0.07%)
A-photo
90.90 +: 0.84
78.77
+ 1.74
92.11 + 1.08
13.34 (16.94%)
1.21 (1.33%)
Arxiv
70.92 +: 0.17
56.05
+ 0.46
63.46 + 0.45
7.41 (13.24%)
-7.46 (-10.52%)
Products
78.61 + 0.49
62.47 0.10
68.86 + 0.46
6.39 (10.23%)
-9.75 (-12.4%)
Table 2: Enlarged GLNNs match the performance of GNNs on the OGB datasets. For Arxiv, we use MLPw4 (GLNNw4). For P Products, we use MLPw8 (GLNNw8).
Datasets
SAGE
MLP+
GLNN+
A MLP
AGNN 0.51 (0.71%) -0.97 (-1.23%)
Arxiv
70.92 + 0.17
55.31 + 0.47
72.15 + 0.27
16.85 (30.46%)
Products
78.61 + 0.49
64.50 + 0.45
77.65 1 0.48
13.14 (20.38%)
edges. Node features and labels are partitioned into three disjoint sets, i.e. x= X ind- Concretely, the input/output of both settings become:
X
obs Li IXX
ind+
and Y = Y LI Y-
Li Y-U
Iran: train on 9, X, and YL; evaluate on (XU, YU); KD uses Zn for v E
ind: train on Gobe. XL, 2 X obs- and evaluaate
evaluate on (x! ind: Yuu); KD uses z, for u E V Li obs
Note that for tran, all the nodes in the graph including the validation and test nodes are used to generate A discussion of this choice along with other experiment details are in Appendix A.
5.3 How DO GLNNS COMPARE TO MLPs AND GNNs?
We start by comparing GLNNs to MLPs and GNNs with the same number of layers and hidden dimensions. We first consider the standard transductive setting, so our results in Table are directly comparable to results reported in previous literature like Yang et al. (2021a) and Hu et al. (2020).
As shown in Table the performance of all GLNNs improve over MLPs by large margins. On smaller datasets (first 5 rows), GLNNs can even outperform the teacher GNNs. In other words, for each task, with the same parameter budget, there exists a set of MLP parameters that has GNN-competitive performance (detailed discussion in Sections 5.6 and 5.7). For the larger OGB datasets (last 2 rows), the GLNN performance is improved over MLPs but still worse than the teacher GNNs. However, as we show in Table 2, this gap can be mitigated by increasing MLP size to MLPwi' In Figure (right), we visualize the trade-off between prediction accuracy and model inference time with different model sizes. We show that gradually increasing GLNN size pushes its performance to be close to SAGE. On the other hand, when we reduce the number of layers of SAGE2, the accuracy quickly drops to be worse than GLNNs. A detailed discussion of the rationale for increasing MLP sizes is in Appendix B.
5.4 CAN GLNNS WORK WELL UNDER BOTH TRANSDUCTIVE AND INDUCTIVE SETTINGS?
Although transductive is the commonly studied setting for node classification, it does not encompass prediction on unseen nodes. Therefore, it may not be the best way to evaluate a deployed model, which must often generate predictions for new data points as well reliably maintain performance on old ones. Thus, to better understand the effectiveness of GLNN, we also consider their performance under realistic production setting, which contains both transductive and inductive predictions.
To evaluate a model inductively, we hold out some test nodes from training to form an inductive set, i.e. D De L D A In production, a model might be re-trained periodically, e.g. weekly. The hold-out nodes in V represent new nodes entered the graph between trainings. VU usually
1 wwi means i-times wider hidden layers, c.g. hidden layers of ML.w4 are 4-times wider than the given MLP. Li is used to explicitly note model with layers, e.g. SAGE-L2 represents 2-layer SAGE.
5

---

Published as a conference paper at ICLR 2022
10a
MLP
MLPw4
33006.4
80
104
SAGE-L3
MLPW8
GLNNW8
Log Scale Inference Time
SAGE
75-
GLNNW4
SAGE-L2
10a
2071.3
Accuracy
70
10a
GLNN
101.81
17.2
65
101
29.31
7.56
SAGE-L1
+5.09
All MLPS
1.75
+3:34
60
10
0.69
1..54
1.3
1.84
2.34
10a
10a
10
# Layers
Log Scale inference Time (ms)
Figure 3: Enlarged MLPs (GLNNs) can match GNN accuracy, but infer dramatically faster. Plots under the same setting as Figure 1, Left: inference time of MLPs vs. GNN (SAGE) for different model sizes. Right: model accuracy vs. inference time. Note: time axes are log log-scaled.
Table 3: GLNNs match GNN performance production setting with both inductive and trans- ductive predictions. We use MLP for the CPF datasets, MLPw4 for Arxiv, and MLPw8 for P Products. ind results V tran results on V... and the interpolated prod results are reported.
Datasets
Eval
SAGE
MLPMLP+
GLNN/GLNN+
AMLP
AGNN
Cora
prod
79.29
58.98
78.28
19.30 (32.72%)
-1.01 (-1.28%)
ind
81.33
2.19
59.09 + 2.96
73.82 + 1.93
14.73 (24.93%)
-7.51 (-9.23%)
78.78 1.92
58.95 1.66
79.39 1.64
20.44 (34.66%)
0.61 (0. (0.77%)
Citesser
prod 68.38
$9.81
69.27
9,46 (15.82%)
0.89 (1.30%)
ind
69.75
3.59
60.06 + 5.00
69.25 + 2.25
9.19 (5.3%%
-0.5 (-0.7%)
Iran 68.04 3.34
59.75 + 2.48
69.28 + 3.12
9.63 (15 93%)
1.24 (1. (1.82%)
Pubmed
prod 74.88
66.80
74.71
7.91 (1183%)
-0.17 (-0.22%)
ind 75.26
2.57
66.85 2.96
74.30 2.61
7.45 (11.8%)
-0.96 (-1.27%)
fran
74.78 2.22
66.79 2.90
74.81 2.39
8.02 ())
0.03 (0.04%)
computer
prod 82.14
67.38
82.29
14,90 (22.
0.15 (9%1
ind 82.08
1.79 82.15
67.84 1.78
80,92 1.36
13.08 (19.28%)
-1.16 (-1.41%)
fran
67.27 1.36
82.63 1.40
15.36 (22.79%)
0.48 (0.58%)
A-photo
prod 91.08
79.25
92.38
13.13 (16.57%)
1,30 (1 (1.42%)
ind 91.50
0.79
79.44 + 1.72
91.18 + 0.81
11.74 (14.78%)
-0.32 (-0.35%)
tran 90.80
0.77
79.20 + 1.64
92.68 0.56
13.48 (17.01 %))
1.70 (1.87%)
Arxiv
prod 70.73
55.30
65.09
9.79 (17.70%)
-5.64 (-7.97%)
ind
70.64 = 0.67
55.40 0.56
60.48 + 0.46
4,3 (7.76%)
-10,94 (-15.49%)
fran 70.75
0.27
55.28 + 0.49
71.46 + 0.33
11.16 (20.18%)
-4.31 (-6.09%)
Products
prod
63.72
75.77
12.05 (18.91%)
-0833 (-1.09%)
76.89
63.70 0.66
75.16 0.34
11.44 (17.96%)
(-2.25%)
fram
76.53 00.5
63.73
75.92 0.61
12.20 (19.15%)
(-0.79%)
small compared to v c.g. Graham (2012) estimates 5-7% for the fastest-growing tech startups. In our case, to mitigate randomness and better evaluate generalizability. we use Vir containing 20% of the test data. We also evaluate on V containing the other 80% of the test data, representing the standard transductive prediction on observed unlabeled nodes, since inference is commonly redone on existing nodes real-world cases. We report both results and a interpolated production (prod) results in Table 3. The prod results paint a clearer picture of model generalization well accuracy in production. See Section 6 for an ablation study different inductive split rates other than 20-80.
In Table 3, see that GLNNS can still improve over MLP by large margins for inductive predictions. On 6/7 datasets, the GLNN prod performance are competitive GNNs, which supports deploying GLNN much faster model with
only slight performance loss. On the Arxiv dataset, the GLNN performance notably less than GNNs we hypothesize this is due to Arxiv having a particularly challenging data split which causes distribution shift between test nodes and training

---

Published as a conference paper at ICLR 2022
Table While other inference acceleration methods speed up SAGE, they are considerably slower than GLNNs. Numbers (in ms) are inductive inference time on 10 randomly chosen nodes.
Datasets
SAGE
QSAGE
PSAGE
Neighbor Sample
GLNN+
Arxiv 489.49
433.90 (1.13x)
465.43 (1.05x)
91.03 (5.37x)
3.34 (146.55x)
Products
2071.30
1946.49 (1.06x)
2001.46 (1.04x)
107.71 (19.23x)
7.56 (273.98x)
nodes, which is hard for GLNNs to capture without utilizing neighbor information like GNNs. However, we note that GLNN performance is substantially improved over MLP.
5.5 HOw DO GLNNS COMPARE TO OTHER INFERENCE ACCELERATION METHODS?
Common techniques of inference acceleration include pruning and quantization. These approaches can reduce model parameters and Multiplication-ande -nd--aaCcnullattion (MACs) operations. Still, they don't eliminate neighbor-fetching latency. Therefore, their speed gain on GNNs is less significant than on NNs. For GNNs, neighbor sampling is also used to reduce the fetching latency. We show an explicit speed comparison between vanilla SAGE, quantized SAGE from FP32 to INT8 (QSAGE), SAGE with 50% weights pruned (PSAGE), inference neighbor sampling with fan-out 15, and GLNN in Table 4. With the same setting as Figure 1, we see that GLNN is considerably faster.
Two other kinds of methods considered inference acceleration GNN-to-GNN KD like TinyGNN (Yan et al., 2020) and Graph gegmenteddMLPP. (GA-MLPs) like SGC (Wu et al., 2019) or SIGN (Frasca et al., 2020). Inference of GNN-1o-GNN KD is likely to be slower than GNN-Li with the same i as the student, since there will usually be some extra overheads like the Peer-Aware Module (PAM) in TinyGNN. GA-MLPs precompute augmented node features and apply MLPs to them. With precomputation. their inference time will be the same as MLPs for dimension preseervingge augmentation (SGC) and the same as enlarged MLPwi for augmentation involves concatenation (SIGN). Thus, for both kinds of approaches, it is sufficient to compare GLNN with GNN-Li and MLPwi, which we have already shown in Figure (left). We see that GNN-Lás are much slower than MLPs. For GA-MLPs, since full preccomputation cannot be done for inductive nodes, GA-MLPs still need to fetch neighbor nodes. This makes them much slower than MLPwi in the inductive setting, and even slower than pruned GNNs and TinyGNN shown in Zhou et al. (2021).
5.6 HOW DOES GLNN BENEFIT FROM DISTILLATION?
We showed that GNNs are markedly better than MLPs on node classification tasks. But, with KD, GLNNs often become competitive to GNNs. This indicates that there exist suitable MLP parameters which can well approximate the ideal prediction function from node features to labels. However, these parameters can be difficult learn through standard stochastic gradient descent. We hypothesize that KD helps to find them through regularization and transfer of inductive bias.
First, we show that KID can help regularize the student model. From loss curves of a directly trained MLP and the GLNN in Figure 4, we see the gap between training and validation loss is visibly larger for MLPs than GLNNs, and MLPs show obvious overfitting trends. Second, we analyze the inductive bias that makes GNNs powerful on node classification, which suggests that node inferences should be influenced by the graph topology. Whereas MLPs have less inductive bias. Similar difference exists between Transformers (Vaswani al., 2017) and MLPs. Liu et al. (2021) shows that the inductive bias in Transformers can be mitigated by a simple gate on large MLPs. For node classification, we hypothesize that KD helps to mitigate the inductive bias, so GLNNS can perform competitively. Soft labels from GNN teachers are heavily influenced by the graph topology due to inductive bias. They maintain nonzero probabilities be useful for the student to learn to complement the missing inductive bias in MLPs. To evaluate this hypothesis quantitatively, we define the cut loss Leut |0, 1] in Equation 2 to measure the consistency between model predictions and graph topology (details in Appendix C):
classes other than the ground truth provided by labels, which can
Lout Tr A
Here Y E [0, X is the soft classification probability output by the model. A and D are the adjacency and degree matrices. When Leut is close 1, it means the predictions and the graph
7

---

Published as a conference paper at ICLR 2022
MLP train
MLP valid
GLNN train
GLNN valid
2.5
2.0
2.0
2.0-
2,0
2.0
1.5
1.5
1.5
1.5
1.5
1.0-
1.0
1.0
0.5-
0.5
0.5
0.5
0.5
0.0
Cora
Citeseer
Pubmed
A-Computers
A- P-ototo
Figure 4: Loss curves on CPF datasets show GLNN distillation can help to regularize the training. Here the training loss of GLNN is on hard labels, only corresponding to the first term in Equation I.
topology are very consistent. In our experiment, we observe that the average Leut for SAGE over five CPF datasets is 0.9221, which means high consistency. The same Lewe for MLPs is only 0.7644, but for GLNNs is 0.8986. This shows that the GLNN predictions indeed benefit from the graph topology knowledge contained in the teacher outputs (the full table of Leat values in Appendix C).
5.7 Do GLNNS HAVE ENOUGH MODEL EXPRESSIVENESS?
Intuitively, the addition of neighbor information makes GNNs more powerful than MLPs when classifying nodes. Thus, a natural question regarding KD from GNNs to MLPs is whether MLPs are expressive enough to represent graph data as well as GNNs. Many recent works studied GNN model expressiveness (Xu et al., 2018; Chen et al., 2021). The latter analyzed GNNs and GA-MLP- for node classification and characterized expressiveness as the number of equivalence classes of rooted graphs induced by the model (formal definitions in Appendix D). The conclusion is that GNNs more powerful than GA-MLPs, but in most real-world cases their expressiveness is indistinguishable.
We adopt the analysis framework from Chen et al. (2021) and show in Appendix D that the number
of equivalence classes induced by GNNs and MLPs are m- (1x 21 and |X| respectively. Here m denotes the max node degree, I. denotes the number of GNN layers, and X' denotes the set of all possible node features. The former is apparently larger which concludes that GNNs are more expressive. Empirically, however, the gap makes little difference when |X] is large. In real even word embeddings,
applications, node features can be high dimensional like Bag-of-words thus making | enormous. Like for bag-of-wordde | is in the order O(pP), where D is the vocabulary size, and p is the max word frequency. The expressiveness of L-layer GNN is lower
bounded by (Ix*)+=-2) 2"-1 P(p but empirically, both MLPs and GNNs should have enough expressiveness given usually hundreds or bigger (see Table 5).
5.8 WHEN WILL GLNNS FAIL TO WORK?
As discussed in Section 5.7 and Appendix D, the goal of GML node classification is to fit a function f on the rooted graph gli and label y: From the information theoretic perspective, fitting f by minimizing the commonly used cross-entropy loss is equivalent to maximizing the mutual information (MI), I(G)), H] y.) as shown in Qin et al. (2020). If consider gldl joint distribution of two random variables X and glill representing the node features and edges in glil respectively, we have
1 (( y.) = 1(x iil ; = 1(81%); ;.) + 1(X y.lElil)
(3)
(g y:) only depends on edges and labels, thus MLPs can only maximize [(1ee, y (g.t). In the extreme case, T(X :1; y (g can be zero when I is conditionally independent from X given glil For example, when every node is labeled by its degree or whether it forms a triangle. Then MLPs won't be able to fit meaningful functions, and neither will GLNNs. However, such cases are typically rare, and unexpected in practical settings our work is mainly concerned with. For real GML tasks, node features and structural roles often highly correlated (Lerique al., 2020). hence MLPs can achieve reasonable results even only based on node features, and thus GLNNs can potentially achieve much better results. We study the failure case of GLNNs by creating low MI scenario in Section 6.
8

---

Published as a conference paper at ICLR 2022
80
MLP-ind GNN-iid GUNN-ind
GNN-ind
GNN tran
MLP
GNN
GLNN
GLNN-ind
GLNN-tran
Accuracy
60-
80
79.279.4 w7..03.7...0.......
50-
70-
30-
10
0.0
0.2
0.4
0.6
0.8
1.0
10-00
20-80
30-70
40-50
50-50
MLP
SAGE
CCN
GAT
APPNP
Noise Level
Inductive:Transdccive Ratio
Model Architectures
Figure 5: Left: Node feature noise. GLNN has comparable performance to GNNs only when nodes less noisy. Adding more noise decreases GLNN performance faster than GNNs. Middle: Inductive split rate. Altering the inductivettransductie ratio in the production setting doesn't 't affect the accuracy much. Right: Teacher GNN architecture. GLNNs can learn from different GNN teachers to improve over MIPs and achieve comparable results. Accuracies are averaged over five CPF datasets.
6 ABLATION STUDIES
In this section, we do ablation studies of GLNNs on node feature noise, inductive split rates, and teacher GNN architecture. Reported results are test accuracies averaged over five datasets in CPR. More experiments can be found in Appendix including advanced GNN teachers (Appendix F), GA-MLP student (Appendix G), and non-homogeneous data (Appendix I).
Noisy node features. Following Section 5.8, we investigate failure cases of GLNN by adding different levels of Gaussian noise node features to decrease their mutual information with labels. Specifically, replace X with X (1 a X + ae. is an isotropic Gaussian independent from X. and a E [0, 1] denotes the noise level. We show the inductive performance MLP, GNN, and GLNN under different noise levels in Figure (left). We that increases, the accuracy of MLPs and GLNNs decrease faster than GNNs, while the performance of GLNNs and GNNs are still comparable for small as. When a reaches 1, X and will become independent corresponding to the extreme case discussed in Section 5.8. A more detailed discussion is in Appendix J.
Inductive split rate. In Section 5.4, we use a 20-80 split of the test data for inductive evaluation. In Figure 5 (middle), we show the results under different split rates (More detailed plots in Appendix H). We see that as the inductive portion increase, GNN and MLP performance stays roughly the same, and the GLNN inductive performance drops slightly. We only consider rates up 50-50 since having 50% or even more inductive nodes is highly atypical in practice. When a large amount of new data are encountered, practitioners can opt to retrain the model on all the data before deployment.
Teacher GNN architecture. We used SAGE to represent GNNs so far. In Figure 5 (right), we show results with other various GNN teachers, e.g. GCN, GAT, and APPNP. We see that GLNNs can learn from different teachers and improve over MLPs. The performance is similar for all four teachers, with the GLNN distilled from APPNP very slightly worse than others. fact, a similar phenomenon has been observed in Yang et al. (2021 1a) as well, i.e. APPNP benefits the student the least, One possible reason that the first step of APPNP is to utilize the node's 's own feature for prediction (prior to propagating the graph), which is very similar what the student MLP is doing, and thus provides less additional information to MLPs than other teachers.
7 CONCLUSION AND FUTURE WORK
In this paper, we explored whether we can bridge the best of GNNs and MLPs to achieve accurate and fast GML models for deployment. We found that KD from GNNs to MLPs helps to eliminate inference graph dependency, which results GLNNs that are 146x-273x faster than GNNs while enjoying competitive performance. We do a comprehensive study of GLNN properties. The promising results on 7 datasets across different domains show that GLNNs can be a handy choice for deploying latency- constraint models. In our experiments, the current version of GLNNs the Arxiv dataset doesn't 't show competitive inductive performance. More advanced distillation techniques can potentially improve the GLNN performance, and we leave this investigation as future work.

---

Published as a conference paper at ICLR 2022
REFERENCES
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Mincut pooling in graph neural networks. CoRR, 2e4/1907.00481,, 2019. URL attp://arxat org/ abs/19011 00 88.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs, 2014.
Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. International Conference on Learning Representations, 2018. URL https:://openee
net/ forum To
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented {mlp]s. In International Conference on Learning Representations, 2021. URL https:// openreview net/ forum? id=tiqi W4JJJG..
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convo- lutional networks. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 Proceedings of Machine Learning Research, pp. 1725-1735, PMLR. 13-18 Jul 2020. URL htttps:/pproceediie chen20v. html.
mlr mtw.ppees//vv9/
Yu-Hsin Chen, Joel Emer, and Vivienne Sze. Eyeriss: A spatial architecture for energy-efficient dataflow for convolutional neural networks. In 2016 ACM/IEBE 43rd Annual International Symposium Computer Architecture (ISCA), pp. 367-379, 2016. doi: 10.1009/CC..206..
Avery Ching, Sergey Edunov, Maja Kabiljo, Dionysios Logothetis, and Sambavi Muthukrishnan. One trillion edges: Graph processing at facebook-scale. Proceedings of the VLDB Endowment, (12):1804-1815, 2015.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering, 2017.
Xiang Deng and Zhongfei Zhang. Graph-free knowledge distillation for graph neural networks, 2021.
Inderjit S. Dhillon, Yuqiang Guan, and Brian Kulis. Kernel k-means: Spectral clustering and normal- ized cuts. In Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDDD '04, pp. 551-556, New York, NY, USA, 2004. Associa- tion for Computing Machinery. ISBN 138881. doi: 40.1145/1014052,1000 1014118 URI
https://doi.org/ wttp:/...........111111 111...11111111111111111111 1014411..
Xiaohan Ding, Xiangyu Zhang, Jungong Han, and Guiguang Ding. Repmlp: Re-parameterizing
convolutions into fully-connected layers for image recognition, 2021.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks, 2020.
Paul Graham. Want to start a startup?
2012.
Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan. Deep learn- ing with limited numerical precision. In Francis Bach and David Blei (eds.), Proceedings of the 32nd International Conference on Machine Learning, volume 37 Proceedings of Machine Learning Research, pp. 1737-1746, Lille, France, 07-09 Jul 2015. PMLR. URL htttps:/pproceet http:///poopo/igeeee/e mir. press h/337//ptt11..ttmm
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural networks. In Proceedings of the 28th Intermational Conference on Neural Information Processing Systems Volume 1, NIPS' 15, pp. 1135-1143, Cambridge, MA, USA, 2015. MIT Press.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network, 2015.
10

---

Published as a conference paper at ICLR 2022
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. CoRR, abs/2005.00687, 2020. URL
baaprggabs/2000500 00687.
Yang Hu, Haoxuan You, Zhecan Wang. Zhicheng Wang. Erjin Zhou, and Yue Gao. Graph-mlp: Node classification without message passing in graph. CoRR, abs/2106.04051, 2021. URL
https: / aaw.iiii... wtt.aawwwv.rr...eaeeeeeeeeeroree als///b///// 220.6......... 04051.
Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, and Austin Benson. Combining la- bel propagation and simple models out-performs graph neural networks. In International Conference on Learning Representations, 2021. URL https: sttpp::://peee /ttp////ppeeeeeeeeeeeeeee nwt./orummt
id-8E1 1----E11--311.. F3VhX1o.
Sergei Ivanov and Liudmila Prokhorenkova. Boost then convolve: Gradient boosting meets graph neural networks. CoRR, abs/2101.08543, 2021. URL httt:s::/aaxiv.orggg./ 02100 21001 08543.
Zhihao Jia, Sina Lin, Rex Ying, Jiaxuan You, Jure Leskovec, and Alex Aiken. Redundancy- computation for graph neural networks. Proceedings the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 997-1005, 2020.
Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah. Graph condensation for graph neural networks. In ICLR, 2022.
Patrick Judd, Jorge Albericio, Tayler Hetherington, Tor M. Aamodt, Natalie Enright Jerger, and Andreas Moshovos. Proteus: Exploiting numerical precision variability in deep neural networks. In Proceedings of the 2016 International Conference on Supercomputing, pp. 23, 2016.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In ICLR (Poster), 2015. URL http:// / / aaaii.iii.v..... org/ aabs/ / /1412. 6980.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: I 609.02907, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank, 2019.
Sébastien Lerique, Jacob Levy Abitbol, and Márton Karsai. Joint embedding of structure and features via graph convolutional networks. Applied Network Science, 5(1):1-24, 2020.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgons: Can gens go deep as cnns? In Proceedings of the IEEE International Conference on Computer Vision, pp. 9267-9276, 2019.
Guohao Li, Matthias Müller, Bernard Ghanem, and Vladlen Koltun. Training graph neural networks with 1000 layers. International Conference on Machine Learning (ICML), 2021.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. CoRR, abs/2104.01404, 2021. URL 01404.
Hanxiao Liu, Zihang Dai, David So, and Quoe Le. Pay attention to mips, 2021.
Luke Melas-Kyriaze Do you even need attention? stack of feed-forward layers does surprisingly well on imagenet, 2021.
Zhenyue Qin, Dongwoo Kim, and Tom Gedeon. Rethinking softmax with cross-entropy: Neural network classifier as mutual information estimator, 2020.
Shyam Anil Tailor, Javier Femandez-Marques and Nicholas Donald Lane. Degree- quant:
Quantization training for graph neural networks. In International Conference on Learning Representations, 2021. URL https: wtw.tpppww//.eeeeee..........eee formm 1d
11

---

Published as a conference paper at ICLR 2022
Iya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Un- terthiner, Jessica Yung, Daniel Keysers, Jakob Uszkoreit, Mario Lucic, et al. Mlp-mixer: An all-mlp architecture for vision. arXiv preprint arXiv:2105.01601, 2021.
Hugo Touvron, Piotr Bojanowski, Mathilde Caron, Matthieu Cord, Alaaeldin El-Nouby, Edouard Grave, Armand Joulin, Gabriel Synnaeve, Jakob Verbeek, and Hervé Jégou. Resmlp: Feedforward networks for image classification with data-efficient training. arXiv preprint 10X.::2005.03404 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv:1710.10900 2017.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma. Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang. Deep graph library: graph-centrie, highly-performant package for graph neural networks. arXiv preprint Xiv: 1909,09993,11 2019.
Tianxin Wei, Ziwei Wu, Ruirui Li, Ziniu Hu, Fuli Feng, Xiangnan He, Yizhou Sun, and Wei Wang. Fast adaptation for cold-start collaborative filtering with meta-learning, In 2020 IEEE International Conference on Data Mining (ICDM), pp. 661-670. IEEE, 2020.
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr. au2, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 181.00800 2018
Yishi Xu, Yingxue Zhang, Wei Guo, Huifeng Guo, Ruiming Tang, and Mark Coates. Graphsail: Graph structure aware incremental learning for recommender systems. In Proceedings of the 29th ACM International Conference on Information amp; Knowledge Management, CIKM '20, pp. 2861-2868, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450368599. doi: 10. 10.1145/3340531..44 34417754 URL https: 0240531.3412777
Bencheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou. Tinygmn: Learning efficient graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery ##38; Data Mining (KDD), pp. 1848-1856, 2020.
Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and go beyond it: An effective knowledge distillation framework, 202
Yiding Yang. Jiayan Qiu, Mingli Song, Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks, 2021b.
Dalong Zhang, Xin Huang, Ziqi Liu, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Zhiqiang Zhang, Lin Wang, Jun Zhou, Yang Shuang, et al. Agl: a scalable system for industrial machine learning, arXiv preprint
culustrill-puppsse purposs graph
Ttl::2003.02455. 2020.
Yiren Zhao, Duo Wang. Daniel Bates, Robert Mullins, Mateja Jamnik, and Pictro Lio. Learned low precision graph neural networks, 2020.
Hongkuan Zhou, Ajitesh Srivastava, Hanqing Zeng, Rajgopal Kannan, and Viktor K. Prasanna. Accelerating large scale real-time GNN inference using channel pruning. CoRR, abs/2105.04525 04528, 2021. URL https:// arxiv. org/ abs/ / 2105.0.. 04528.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sampling for training deep and large graph convolutional networks. arXiv preprint 1..1v.1911.07333, 2019.
12

---

Published as a conference paper at ICLR 2022
A DETAILED EXPERIMENT SETTINGS
A.1 DATASETS
Here we provide a detailed description of the datasets we used to support our argument. Out of these datasets, 4 of them citation graphs. Cora, Citeseer, Pubmed, ogbn-arxiv with the node features being descriptions of the papers, either bag-of-word vector, TF-IDF vector, or word embedding vectors.
In Table 5, we provided the basic statisties of these datasets.
Table 5: Dataset Statistics.
Dataset
# Nodes
# Edges
Features
Classes
Cora
2,485
5,069
1,433
Citeseer
2,110
3,668
3,703
Pubmed
19,717
44,324
500
3
A-computer
13,381
245,778
767
10
A-photo 7,487
119.043
745
Arxiv 169,343
1,166,243
128
40
Products 2,449,029
61,859,140
100
47
For all datasets, follow the setting in the original paper to split the data. Specifically, for the five smaller datasets from the CPF paper, we use the CPF splitting strategy and each random seed corresponds different split. For the OGB datasets, follow the OGB official splits based time and popularity for Arxiv and P Products respectively.
A.2 MODEL HYPERPARAMETERS
The hyperparameters of GNN models on each dataset are taken from the best hyperparameters provided by the CPF paper and the OGB official examples. For the student MLPs and GLNN s, unless otherwise specified with -wi or -Li, we set the number of layers and the hidden dimension of each layer to the same as the teacher GNN, so their total number of parameters stays the same as teacher GNN.
Table 6: Hyperparameters for GNNs on five datasets from the CPF paper.
SAGE
GCN
GAT
APPNP
layers hidden dim
2
2
2
2
128
64
64
64
learning rate
0.01
0.01
0.01
0.01
weight decay
0.0005
0.001
0.01
0.01
dropout fan out attention heads
0
0.8
0.6
0.5
5.5
8
power iterations
10
Table 7: Hyperparameters for GraphSAGE OGB datasets.
Dataset
Arxiv
Products
layers
3
hidden dim
256
256
learning rate
0.01
0.003
weight decay
dropout
0.2
0.5
normalization
batch
batch
fan out
[5. 10, 15]
10, 15]
13

---

Published as a conference paper at ICLR 2022
For GLNN do hyperparameter search of learning rate from [0.01, 0.005, 0.001], weight decay from [0, 0.001, 0.002, 0.005, 0.01], and dropout from [0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6]
A.3 KNOWLEDGE DISTILLATION
We the distillation method proposed in Hinton et al. (2015) in Equation I, the hard labels found to be helpful, so nonzero Às was suggested. In our case, we did little tuning for À but didn't t find nonzero Äs to be very helpful. Therefore, we report all of our results with second term involving soft labels is effective. More careful tuning of À should further improve the results since the searching space strictly larger. We implemented a weighted version our code, and we leave the choice of À future work.
i.e. only the
A.4 THE TRANSDUCTIVE SETTING AND THE INDUCTIVE SETTING
Given G, X, and Y the goal of node classification can be divided into two different settings, iec transductive and inductive. real applications. the former can correspond to predict missing attributes of a user based on the user profile and other existing users, and the latter can correspond to predict labels of some new nodes that only seen during inference time. To create the inductive setting on given dataset, we hold out some nodes along with edges connected to these nodes during training and use them for inductive evaluation only. These nodes and edges are picked from the test data. Using notation defined above, we pick the inductive nodes V VV which partitions yo into the disjoint inductive subset and observed subset, i.e. D = obs Li ind- Then we can take all the edges connected to nodes in V to further partition the whole graph, so we end up with g = Gobs L gidd X = x XU
ohs U X ind and Y = Y YU UY We show the input and output of both settings using the notations below.
obs ind-
We visualize the difference between the inductive setting and the transductive setting in Figure 6.
Test Node
1-hop
Train graph
Test Node
New nodeledge
2-hop
1-hop
2-hop
Transductive
Inductive
Figure 6: The transductive setting and inductive setting illustrated by 2-layer GNN. The middle shows the original graph used for training. The left shows the transductive setting, where the test node in red and within the graph. The right shows the inductive setting, where the test node an unseen new node.
A.5 CHOOSING SOFT TARGETS UNDER THE TRANSDUCTIVE SETTING
For the transductive setting in Section 5.3, all the nodes the graph, including the validation and test nodes, are used for the soft target generation. It seems less practical compared to the inductive case, but is necessary step develop our argument. We now discuss the rationale behind this choice.
Firstly, the transductive setting is the most common setting for graph data and it was used in most GNN architecture works and GNN acceleration works we mentioned related work. Therefore, to avoid any confusion and for fair comparison with numbers from previous literature, we start our experiments with exactly the same input and output as the standard transductive setting. Under this setting, the inputs to GNNs include all the node features and the graph structure, so GLNN is set to be able to access the same input. As GLNN includes a teacher training step and a distillation step, the soft labels of all the nodes are intermediate outputs produced by the teacher training step, and thus used for the second distillation step for the best GLNN performance. This transductive setting can boil down to sanity check when the student is sufficiently large. Therefore, we separate the setting to be GLNN and GLNN+ and report the results in Table and Table separately. In Table checking how well GLNNs can perform compared to GNNs under the equal-parameter
14

---

Published as a conference paper at ICLR 2022
constraint. The results can be interpreted given fixed parameter budget, whether there exists one set of parameters (one instantiation of the MLP) that can achieve competitive results as the GNN. Only when this holds, should we further investigate the more interesting and challenging inductive case as Section 5.4.
Secondly, the task we focus is node classification, which in many cases is considered semi- supervised learning with very scarce labels. For example, Pubmed only uses 60 labeled nodes (20 per class) out of 20K nodes for training. Rather than design an advanced model that can do few-shot learning, our goal here is to leverage as much data as possible to simplify the model for more efficient inference. We thus utilize the soft pseudo-labels on all the unlabelled nodes for the best GLNN performance. In reality, when there is a large amount of separate unlabeled data, these unlabeled data can be used for GLNN distillation training and different set of labeled data can be used for evaluation. In our case, we mimic this scenario in the inductive setting in Section 5.4.
A.6 IMPLEMENTATION AND HARDWARD DETAILS
The experiments on both baselines and our approach are implemented using PyTorch, the DGL (Wang et al., 2019) library for GNN algorithms, and Adam (Kingma & Ba, 2015) for optimization. We run all experiments on machine with 80 Intel(R) Xeon(R) E5-2699 @ 2.20GHz CPUs, and single NVIDIA V100 GPU with 16GB RAM.
B SPACE AND TIME COMPLEXITY OF GNNS VS. MLPs
Compared to MLP and GNN, GLNN provides a handy tool for users to trade-off between model accuracy and time complexity, which does not directly focus space complexity. Given the space and time complexity are related, we now provide a more detailed discussion regarding these two complexities in our experiments.
In Table 1, the model comparison was between equal-sized MLPs (GLNNs) and GNNs. While fixing parameter budget to control space complexity is standard approach when comparing models, it is not completely fair for cross-model comparison especially for MLPs vs. GNNs. To do inference with GNNs, the graph needs to be loaded in the memory either entirely or batch by batch, and may use much larger space than the model parameters. Thus, the actual space complexity of GNNs is much higher than equal-sized MLPss From the time complexity perspective, the major inference latency of GNNs comes from the data dependency as shown in Section 4. Under the same setting as Figure 1, we show in Figure 3 Left that even 5-layer MLP with 8 times wider hidden layers still runs much faster than single-layer SAGE. Another example of modsl comparison is Transformers vs. RNNs. Large Transformers can have more parameters than RNNs because of the attention mechanism, but they are also faster than RNNs in general, which is important consideration in the context of inference time minimization.
In Table I, saw that for equal-sized comparison, GLNNs not accurate as GNNs the OGB datasets. Following the discussion above and given the GLNNs used Table are relatively small (3 layers and 256 hidden dimensions) for millions of nodes in the OGB datasets, ask whether this gap can be mitigated by increasing the MLP and thus GLNN sizes. The answer is yes as shown in Table 2.
C CONSISTENCY MEASURE OF MODEL PREDICTIONS AND GRAPH TOPOLOGY BASED ON MIN-CUT
We introduce metric measure the consistency between model predictions and graph topology based on the min-cut problem in Section 5.6. The K K-way normalized min-cut problem, or simply min-cut, partitions N nodes in V into K disjoint subsets by removing the minimum volume of edges. According to Dhillon et al. (2004), the min-cut problem can be expressed as
K C
AC C
max
(4)
K
DC
s.t. CE
1)
ClK IN
15

---

Published as a conference paper at ICLR 2022
with C' being the node assignment matrix that partitions V. i.e. Ct,, if node is assigned to class j. A being the adjacency matrix and D being the degree matrix. This quantity we try to maximize here tells us whether the assignment is consistent with the graph topology. The bigger it is. the less edges need to be removed, and the assignment is more consistent with existing connections in the graph. In Bianchi et al. (2019), the authors show that when replacing the hard assignments C' {0, 1 x with a soft classification probability Y [0, 1j cut loss Leut in Equation can become good approximation of Equation 4 and be used as the measuring metric.
Table 8: GLNN predictions are much more consistent with the graph topology than MLPs. We show the Ceut values of GNNs, MLPs, and GLNN on five CPF datasets. GLNN Ceut values become pretty close to the high Lew values of GNNs, which were closely related to the GNN inductive bias.
Datasets
SAGE
MLP
GLNN
Cora
0.9347
0.7026
0,8852
Citeseer
0.9485
0.7693
0.9339
Pubmed
0.9605
0.9455
0.9701
A-computer
0.9003
0.6976
0.8638
A A-photo
0.8664
0.7069
0.8398
Average
0.9221
0.7644
0.8986
D EXPRESSIVENESS OF GNNS vs. MLPs IN TERMS OF EQUIVALENCE CLASSES OF ROOTED GRAPHS
In Chen et al. (2021), the expressiveness of GNNs and GA-MLPs were theoretically quantified in terms of induced equivalence classes rooted graphs. We adopt their framework and perform a similar analysis for GNNs vs. MLPs. We first define rooted graphs
Definition 1 (Rooted Graph). A rooted graph, denoted as Gll is a graph with one node i in gla) designated as the root. GNNs, GA-MLPs, and MLPs can all be considered as functions on rooted graphs. The goal of a node-level task on node with label y: to fit a function the input-output pairs (G y:).
We denote the space of rooted graphs as E. Following Chen et al. (2021), the expressive power of model on graph data is evaluated by its ability to approximate functions on E. This is further characterized as the number of induced equivalence classes of rooted graphs on E, with the equivalence relation defined the following. Given family of functions F on E, we define equivalence relation =e,F among all rooted graphs such that Vgli, g' E E =E.F G'lsl if and only if Vf E f(Ght) f(G"l)). We now give a proposition to characterize the GNN expressive power (proof in Appendix E).
Proposition With X denotes the set of all possible node features and assuming |X| 2 2, with m denotes the maximum node degree and assuming 2 3, the toial number of equivalence classes of rooted graphs induced by an L-layer GNN is lower bounded by
(1x]+m-3) 2
m7
As shown in Proposition the expressive power of GNNs grows doubly-exponentially in the number of layers L, which means it grows linearly in L after taking log(lo((-)), The expressive power GA-MI.Ps only grows exponentially in shown in Chen et al. (2021). Under this framework, the expressive power of MLPs, which corresponds to O-layer GA-MLP, is [x'). Since the former is much larger than the latter, the conclusion will be GNNs are much more expressive than MLPs. The gap between these two numbers indeed exists, but empirically this gap will only make difference when | is small. As in Chen et al. (2021), I), both the lower bound proof and the constructed examples showing GNNs more powerful than GA-MLPs assumed | = 2. In real applications and datasets considered in this work, the node features can be high dimensional vectors like bag-of of words, which makes | enormous. Thus, this gap doesn't 't matter much empirically.
16

---

Published as a conference paper at ICLR 2022
E PROOF OF THE PROPOSITION 1
To prove Proposition 1, we first define rooted aggregation trees, which is similar to but different from rooted graphs.
Definition 2 (Rooted Aggregation Tree), The depth-K rooted aggregation tree of a rooted graph Gla) a depth-K K rooted tree with a (possibly many-to-one) mapping from every node in the tree some node in gla, where (i) the root of the tree is mapped to node i, and (äi) the children of every node j in the tree are mapped to the neighbors of the node in Gli to which j mapped.
A rooted aggregation tree can be obtained by unrolling the neighborhood aggregation steps in the GNNs. An illustration of rooted graphs and rooted aggregation trees can be found in Chen et al. (2021) Figure 4. We denote the set of all rooted aggregation trees of depth L using Tz- Then we use TL to denote a subset of TL. where the node features belong to X, and all the nodes have exactly degree (m children), and at least two nodes out of these nodes have different features. In other words, a node can't have all identical children. With rooted aggregation trees defined, we are ready to prove Proposition 1. The proof is adapted from the proof of Lemma in Chen et al. (2021).
Proof. Since the number of equivalence classes on & induced by the family of all depth-L GNNs consists of all rooted graphs that share the same rooted aggregation tree of depth-L. (Chen al., 2021), the lower bound problem in Proposition can be reduced to lower bound [Tz),, which can
[ 24-1
be further reduced to lower bound the subset [T. We now show [ 2 inductively.
m-1
When L = 1, the root of the tree can have | different choices. For the children nodes, we pick features from |.( and repetitions are allowed. This leads to ( (1x(++m-1) cases. Therefore,
TL+1.X,, = | (1xx) ((x)+m=1)))) 2 m--1 (l))+
Assuming the statement holds for L,, we show holds for + by constructing trees 1. from T. 7' E TI.x.-- We do this by assigning node features in X' to the m children of each leaf node in T and T". First note that when T and T" are two non-isomorppic trees, two depth-L+I trees constructed from T' and 7" will be different no matter how the node features are assigned. Now we consider all the trees can be constructed from T by assign node features of children to leaf nodes.
We first consider all paths from the root to leaves in T. Each path consists of sequence of nodes where the node features form a one-to-one mapping to an L-tuple E { ØL) 24 E X. Leaf nodes called node under if the path from the root to it corresponds to r. The children of nodes under different 78 are always distinguishable, and thus any assignments lead to distinct rooted aggregation trees of depth T. + 1. The assignment of children of nodes under the same т, on the other hand, could be overcounted. Therefore, to lower bound T ,.Y.m m. we only consider special way of assignments to avoid over counting, which is that children of all nodes under the same 7 are assigned the same set of features.
Since we assumed that least two nodes of T have different features, there are least 2 different Ts corresponding to the path from the root to leaves. For a leaf node under fixed т, one of its children needs have the same feature as j's parent node. This restriction is due to the definition of rooted aggregation trees. Therefore, we only pick features for the other m 1 nodes, which will be m-1 cases for each j. Then through this construction, the total number of depth-L+11 trees
from T can be lower bounded by ( 2"
Finally, have this lower bound holds for all
T E TL so we derive TL+1X 2 m 2'. TE.x. and TL 2 (1x1++m-2) E/ 2'
(1 2h-1
m-1
17

---

Published as a conference paper at ICLR 2022
F ADVANCED GNN ARCHITECTURES AS THE TEACHER
In our experiment, SAGE teacher is used throughout to avoid influence by model architecture. Some other GNNs like GCN are also considered in the ablation studies, but they are not the best known architecture for specific dataset. To show GLNN has stronger performance given a stronger teacher, we consider the best teacher we can access on P Products. We take MLP+CS Huang et (2021) from the OGB leaderboard as a new teacher, which has reported accuracy 84. 84.18% and ranks on the leadarboard as of Nov 2021. We choose MLP+CS instead of the other top 7 because the others either rely on raw text (additional info to the given node feature), require a large GPU with > >16GB memory, which we don't have access to. Also, their improvement not super significant compared to MLP+CS, i.c. 84% to 86%. The result with MLP+CS teacher is shown in Table 9. We that with the new teacher, performance of GLNN+ improves to be even better than SAGE (78.61%) 61)), which shows GLNN can get stronger given stronger teacher.
Table 9: GLNN+ with MLP+CS teacher Products
MLP+C&S
MLP+
GLNN+
Acc
84.18
64.50
82.94
G GLNN WITH FEATURE AUGMENTATION FROM ONE-HOP NEIGHBORS
In main experiment, the inductive performance of GLNN the Arxiv v dataset is less desirable than others. We thus consider augment the node features with their one-hop neighbors to include more graph information. This can be seen middle ground between pure GLNNs and GNNs. For this new experiment, we follow the setting in Table 3 but with two new approaches. We explain the setting of these two approaches below.
1-hop GA-MIP: firstly, for each node v, we collect features of its 1-hop neighbors u to augment the raw feature of v, i.e. Tr - T.. like in SGC. Then we train an MI. on the graph with e.. Note if in the observed graph during training) part, then u doesn't collect features from
in the inductive (unobserved
2. l-hop GA-GA--I- GANNG Go through the same feature augmentation step as l-hop GA-MLP. Then train an MLP with distillation from teacher GNN.
3. In summary, we compare 5 different models in the table below
(a) SAGE: single model Zv
(b) MLP: single model on 2e
(c) GLNN: SAGE teacher and MI. student on Zy
(d) 1-hop GA-MLP: single model on Ze
(c) I-hop GA-GLNN: SAGE teacher on MLP student on 2,
We show in the table below, with 1 I-hop neighbor features, performance of GLNN improves a lot. This is expected as we also observe significant improvement from MLP to 1-hop GA-MLP. However, we indeed see 1-hop GA-GLNN (68.83) can further improve from 1-hop GA-MLP (66.62) and nearly match the teacher (70.64).
Table 10: GLNN with feature augmentation from one-hop neighbor on Arxiv
Eval
SAGE
MLP
GLNN
1-hop GA-MLP
I-hop GA-GLNN
Arxiv
ind
70.64
55,40
60.48
66.62
68.83
tran
70.75
55.28
71.46
66.67
69.82
As we have shown Figure 3, the I-Layer GNN in our case is roughly 4 times slower than GLNN 129.31ms 7.56ms), which should be good approximation for the speed comparison between 1-hop AL-MALLGGAGGLNN and GLNN. This result is practically beneficial, as it gives practitioners more flexibility about how much accuracy they want to trade for less inference time.
18

---

Published as a conference paper at ICLR 2022
H
MODEL PERFORMANCE UNDER DIFFERENT INDUCTIVE SPLIT RATE
This section is continuation of the ablation study of inductive split rate in Section 6. It generalizes Figure 5 Middle to more split rates (from 10:90 to 90: 10), and explicitly show the inductive and transductive performance each dataset. For better visualization, the training data label rate is also reduced from 20 per class to per class in the following plots.
dataset
dataset citeseer
dataset pubmed
model
MLP GLNN
GNN
2.8
7-3 9-1
7-3 Inductwe:rransducivv Ratio
3-7
5-5
1-9 4-6
7-3 8-2
Inductie.Trandductvv Ratio
Inductiee.ransductvvv
computer
dataset
0.9
0.7
model MLP
GLNN
GNN
0.5
0.4
2-8 4.5 64
Ratio
Inductive.Trandduccmm Rabio
Figure 7: Model inductive performance comparison between MLP, GNN(SAGE). and GLNN under different inductive split rate in the production setting.
dataset cora
dataset citeseer
dataset pubmed
0.6
model
MLP
0.5
GNN
1.9
2-8
3.7
4-6
5.5
64
73
8.2 9.1
1-9 28
3-7
4-6
5.5
64
73 8.2 9-1
1/9 2.8 2.8 3.7 7.
Inductive.Trnnsducco Ratio
Tranduuee Ratio
Induccive.Tanssccttvee Ratio
dataset computer
dataset a-photo
0.9
0.8
0.7
model
MLP
0.6
GLNN
GNN
0.4
1.9
2- 5.5 733 8-2 Inductive Transuucvee Ratio
1/9 2-8 466 8.23822 Transucte Ratio
Figure 8: Model transductive performance comparison between MLP, GNN(SAGE), and GLNN under different inductive split rate in the production setting.
19

---

Published as a conference paper at ICLR 2022
1 GLNN UNDER NODE FEATURE HETEROGENBITY AND NON-HOMOPHILY
Besides the 7 datasets used in the main experiments, consider 4 more datasets from Ivanov & Prokhorenkova (2021) and Lim et al. (2021) to further evaluate GLNN.
The House_class and 7K_class datasets are from Ivanov & Prokhorenkova (2021). The node features of these two graphs are based on tabular data, which have different types, scales, and meanings the opposite of the bag-of-worts word node features in Cora and etc. Some basic statisties of the datasets are shown in the following table.
Table 11: Statistics of dataset with heterogeneous node features
Dataset
# Nodes
# Edges
# Features
# Classes
House House_clase class
20,640
182,146
6
5
classass 54,028
213,644
14
We apply the GLNN on House @ouse_class and VK_ VK_class using the best BGNN model from Ivanov & Prokhorenkova (2021) 1) as the teacher. The comparison is shown in the following table. Ivanov & Prokhorenkova (2021) also includes GAT, GCN, AGNN, and APPNP as baselines, whose performance quite similar (difference 0.025). We compare with these baselines by
on these two datasets including the best result among the 4 GNN models and refer as GNN in the table helow, i.e. GNN mAT, GCN, AGNN, APPNP). From the table, we see that GLNN can improve from MLP, outperform GNN and LightGBM, and become competitive to the teacher BGNN.
Table 12: GLNN datasets with heterogeneous node features. Numbers other than GLNN taken from Ivanov & Prokhorenkova (2021)
Dataset
LightGBM
GNNs
BGNN
MLP
GLNN
House_class 0.55
0,625
0.682
0.534
0.672
vK_class 0.57
0.577
0.683
0.567
0.641
We further pick the non-homophilous Penn94 and Pokec datasets from Lim al. (2021). Some basic statistics of the datasets are shown in the following table.
Table 13: Statistics of non-homophilous datasets
Dataset
# Nodes
# Edges
# Features
# Classes
Penn94
41,536
1,590,655
5
2
Pokec
1,632,803
30,622,564
65
2
Using the GCN teacher, we see that the performance of GLNN is improved over MLP and becomes competitive to the teacher GCN on Penn94. However, on Pokec, the simple LINK model can achieve very good performance, and it is better than most GNNs reported in Lim et al. (2021). LINK purely structural model which does not use node features at all. This shows that the Pakec dataset corresponds to the setting we discussed in Sec 5.8 (limitations of GLNN) if the node labels can be largely determined by only the graph structure, then GLNN will struggle. We observe that GLNN is not as good as LINK owing this limitation. However, we still see that for most of the non non-homophilous datasets, MLPs already work quite well on them, and we can use GLNN for the other ones like Penn94.
Table 14: GLNN on non-homophilous datasets. Numbers other than GLNN are taken from Lim et al. (2021)
Dataset
LINK
GCN
ML.P
GLNN
Penn94
80.79
82.47
73.61
81.69
Pokec
80.54
75.45
62.37
61.32
20

---

Published as a conference paper at ICLR 2022
J MODEL COMPARISON WITH NOISY NODE FEATURES
In Section 6, we conducted an ablation study to compare model performance with noisy node features, and the result is shown in the left plot in Figure 5. There are two subtle points in this plot. (1) The performance of GNN is still relatively high for high noisy features, even when a = I and the features are completely random.
(2) For completely random features, the performance of GLNN is still higher than MLP. We now discuss and explain them in more detail.
GNN Performance on Random Features. GNN still performs well because nodes with the same labels are likely to be connected and GNN can overfit the training data. We explain the detail through a toy example. Suppose there is a 4-clique containing nodes A, B, C, edge D-E connects this clique to other graph nodes. Suppose A, B, C, D all have iid random Gaussian raw features and the same class label c. Let's pick to be the inductive test node and assume E and the triangle formed by B, C, D to be in the training graph. Let's consider a simple example for 1-layer GCN and break down message passing into feature aggregation and nonlinear transformation. During training, GNN can overfit the data by learning nonlinear transformation which maps the aggregated features of B, C, D to class C. The aggregated features of B and C will just be the average of the raw features of B, C, D. Although E is also involved in D's feature aggregation step, the aggregated features of D will also be very close to this average. Then when test on A, the aggregated feature of will likely be classified to the same class с by the overfitted nonlinear transformation because is the average of raw node features of A, B, C, D. In this case, GNN can actually correctly classify A because of the overfitting. For GNNs with more layers and graphs with more neighbor nodes, the conclusion may be generalized. This is roughly sort of "majority vote" process. For test node A, many nodes, which collects features from, have the same class label and appear the training graph, then A will be classified as this class by an overfitted classifier.
the graph with only single
GLNN and MLP Performance on Random Features. The gap between MI.P and GLNN due to imbalanced datasets. The GLNN can learn the imbalance from soft labels, whereas MLPs only access uniformly picked training nodes. We explain more detail using the A computez dataset as an example, for which the gap between MLP and GLNN is obvious. The task is 10-class classification. With random node features (a=1), the inductive accuracy for MLP is 0.0652 and 0.2538 for GLNN. If the data labels are uniform, then both models should give accuracy around 0.1. However, the labels on the inductive dataset are actually imbalanced. We show the results in Figure 9. The hist on the left is the label distribution of the inductive test set. In particular, class takes about 40%. However, given this imbalance, the standard train-test split selects training nodes uniformly among MLP on random features are
labels. In this case, 20 nodes per class. Therefore, the predictions expected to be relatively uniform because the 200 nodes we train it are uniform. This gives the hist shown in the middle, where the largest class takes about 17.5%. Finally, for GLNN, we train on all the 200 training nodes with hard labels, plus soft labels of other nodes in the observed graph Gabs (see Section 5.2). Since these extra nodes are selected randomly, whose label distribution actually similar to the label distribution on the whole data and the distribution on the inductive test set. Therefore, we get the GLNN predictions hist on the right. Although for each node, we can't t assign a prediction correlated to its feature, on average the distribution very close to the true label distribution on the inductive test set and has a much higher expectation. In fact, if the prediction distribution is exactly the true distribution GLNN actually does even bit better by putting its bet more on the largest class.
the inductive test set, the expectation will be 0.2169.
E
30
15.5%
25.5%
12.0%
15.0%
11%
306
10.0
10%
Labels
MLP
GLNN
Figure 9: Inductive (predicted) label distribution on the A-computer dataset. Left: true labels. Middle:
predicted labels by MLP. Right: predicted labels by GLNN.
21


Reviews:
[{"review_id": "PwXfxl37M1", "reviewer": "Reviewer_fkQB", "summary": "", "questions": "", "limitations": "", "rating": 10, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper shows that it's possible to distill knowledge from GNNs to MLPs without sacrificing performance, while reducing inference time by orders of magnitude. The approach is very simple, which copies a classical KD approach proposed by Hinton et al. At inference, it shows significant reduction of time compared to baseline GNNs and existing approaches. The paper is well-written, motivated, without unnecessary theory, and does enough ablation studies. \n\nThe only concern is the datasets used to verify the approaches. While there are OGB ones, cora/citeseer/pubmed are quite small for this type of approaches to motivate enough KD. I would include other datasets, for example, coming with heterogeneous node features [1] (where MLP and GBM can work quite well) and heterophilous datasets [2] (where LP can work well). Results there would give additional insights onto the use cases of KD for GNNs. It's also interesting to compare performance of this approach compared to graph-agnostic baseline using GBM [1] (it should give even less inference time than MLPs and as such could be more amenable for this type of KD). \n\nI may update my score based on the authors' responses.\n\n[1] Boost then Convolve: Gradient Boosting Meets Graph Neural Networks https://arxiv.org/abs/2101.08543\n[2]  New Benchmarks for Learning on Non-Homophilous Graphs  https://arxiv.org/abs/2104.01404", "summary_of_the_paper": "The paper proposes to distill knowledge from GNNs to MLPs so that at inference time it requires less burdensome. The idea is neat and the implementation is flawless. ", "summary_of_the_review": "Practical limitations of GNNs in industry setup are quite severe for existing GNN models and this approach offers an easy way to overcome them and leverage graph topology at the same time. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "HXN1l6H5Rzb", "reviewer": "Reviewer_5DSq", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "# Interesting point\n- The MLP with a simple knowledge distillation design applied on top of a teacher GNN does show huge potentials in terms of the inference time. The aspect of bypassing fully the neighborhood fetch process during inference time is interesting.\n\n- Empirically, they show this simple design has competitive performance as the teacher GraphSAGE model while enjoying hundreds of times faster inference time and ~30x faster than other inference acceleration methods. It does show the potential of this direction.\n\n\n# Main concern\n\n**Methodology aspect**\n\n-  The novelty of the work is too limited, they only apply the original distillation formulation from Hinton et al. 2015.  There is no interesting distillation design that tailors to the unique characteristics of the dependency complication introduced by the graph.\n\n- The literature discussion is not thorough, missing out on quite some important related works which discuss the knowledge distillation in the context of graph-structured data [1] [2] [3].\n\n[1] Yang, Y., Qiu, J., Song, M., Tao, D. and Wang, X., 2020. Distilling knowledge from graph convolutional networks. In Proceedings of CVPR.\n\n[2] Deng, X. and Zhang, Z., 2021. Graph-Free Knowledge Distillation for Graph Neural Networks. arXiv preprint arXiv:2105.07519\n\n[3] Xu, Y., Zhang, Y., Guo, W., Guo, H., Tang, R. and Coates, M., 2020, October. Graphsail: Graph structure aware incremental learning for recommender systems. In Proceedings of CIKM.\n\n- Some claim discussed in the motivation section is not accurate. The authors claim that \"To infer for a single node with a L-layer GNN on a graph with average degree R will require $O(R^L)$ fetchings\", which is not accurate considering when working on large graphs, we will not use node wise sampling technique. People tend to use efficient batching and layerwise or graph-wise sampling techniques [4] [5] to greatly reduce the node fetching process. \n\n[1] Chiang, W.L., Liu, X., Si, S., Li, Y., Bengio, S. and Hsieh, C.J., 2019. Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks. In Proceedings of KDD.\n\n[2] Zeng, H., Zhou, H., Srivastava, A., Kannan, R. and Prasanna, V., 2020. GraphSAINT: Graph Sampling-Based Inductive Learning Method. In Proceedings of ICLR.\n\n- Do we really have a scenario that we can establish the existing efficient batching and graph-wise sampling techniques are unable to meet the inference time constraint? Can authors provide an intuitive example in practice?\n\n**Experimental result**\n\n- The proposed approach doesn't show competitive performance on  Arxiv and Product dataset, which are the larger datasets we care more about the inference efficiency potentially. \n\n- This simple distillation design didn't show competitive performance when the teacher model is more advanced GNN architecture, as shown in Figure 5 (c), which makes the technique less interesting. I believe establishing that distilling a more competitive teacher GNN into a student model with less performance drop will make the work much stronger.\n\n- To add on top of my argument above, the top model performance (which also uses a fashion of KD) on Arvix and Product is 76.2% and 86.4% respectively. Compared to the GLNN performance on Arvix and Product which is 63.5% and 68.9%. I'm not too sure about the accuracy and computation complexity trade-off make sense. \n\n- The baseline comparison of the paper is not thorough as I point out above regarding missing out on quite some important related works about KD in the context of graphs.  For an empirical-based paper, I do expect the experiment section to be much more thorough than what is being provided.\n", "summary_of_the_paper": "This paper applies KD in the context of the graph. It aims to distill the teacher output of a GNN model into a simple MLP model. Empirically, they show that this simple KD design is able to improve the student MLP model by a large margin and can match the results coming from a teacher GNN model. Besides, it shows empathically, the inference time can be greatly improved.", "summary_of_the_review": "The novelty of the work is limited, there is no interesting distillation design that tailors to the unique characteristics of the dependency complication introduced by the graph. Besides, the literature discussion is not thorough, missing out on quite some important related works (KD on graph-structured data). In the experimental study, this simple distillation design didn't show competitive performance when the teacher model is more advanced GNN architecture. Overall, I recommend rejecting this paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "EmmjOoLH_u", "reviewer": "Reviewer_tKyT", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "The paper is overall well written and rather easy to read, with a good introduction that describes the setting of the work, several references to prior art and an ablation study that analyzes the potential failure points of the approach (which I believe provides a good understanding of the pros and cons of the solution). To the best of my knowledge, the idea presented in the manuscript is overall novel and I believe generally interesting to the community given the performance and speed up the authors managed to achieve with their approach in the analyzed settings (e.g. 273x while losing only 2% in accuracy over OGB Products). \n\nThe experimental evaluation proposed in the manuscript is generally sound, although I do have some points I would like to highlight in my review on this matter. Unless I’m misunderstanding the content of Section 5.2, the experiments for the transductive setting presented in Table 1 I believe boil down to a sanity check. As presented in the end of Section 5.2 indeed, the MLP in the transductive setting is trained to reproduce the logits of the GNN on *all* nodes of the given graph, irrespectively on whether these belong to the training, validation or test set. If the nodes thus all show different features, a sufficiently large and deep MLP should always be able to overfit on the features of the target nodes and replicate the predictions of the GNN. As such, the experiments presented in Table 1 don’t look particularly meaningful to describe the quality of the proposed approach and I would ask the author to please clarify in their rebuttal whether they avoided training the MLP on the logits produced by the GNN for validation / test nodes and, if I’m right, to better clarify the relevance of these results in the text.\n\nFollowing the previous comment, in Table 4 the authors present two aggregated measures of the quality of the model (\\Delta_{MLP} and \\Delta_{GNN}) that should describe a typical production setting consisting of 80% unlabeled nodes that have been observed at training time and 20% of new unlabeled nodes the model has never seen before. As for the above, I believe the most interesting result here is represented by the performance of the model in the inductive scenario and I would thus suggest the authors to express the improvements in performance in the table for all the 3 different settings they described (i.e. transductive, inductive and production) instead of just the production one (it would better highlight the performance of the approach in different conditions and thus enhance clarity).\n\nFinally, Figure 5 middle, it is possible to observe how the GNN actually improves in performance over the inductive set if we increase the size of this and thus restrict the size of the transductive one (i.e. the number of nodes the model is actually able to observe at training time). While the improvement seems to be marginal from the picture, this is somehow a surprising and counterintuitive result and I wonder if the authors have an explanation for this. Additionally, I would recommend adding standard deviation bars in all the plots of Figure 5 to highlight the stability of the performance of the models over the different datasets and potentially have a different picture (or a series of pictures) in the supplementary material showing the curves for each dataset independently. \n\nBesides the points highlighted above, I believe the manuscript is in good shape and I would recommend the acceptance of the paper to the conference.\n", "summary_of_the_paper": "The paper proposes a Knowledge Distillation (KD) based approach for producing MLPs able to achieve comparable performance to Graph Neural Networks (GNNs) on node-wise classification tasks. The MLPs receive as input only the features of each target node v and it is trained to imitate the behavior of a pre-trained GNN on an extended version of the training set consisting of:\n\n1) the original labeled set where the GNN was trained;\n2) an additional set of unlabeled nodes which are equipped with soft labels produced by the GNN.\n\nAs the GNN (which operates as a teacher in this scenario) has a good inductive bias, it can learn a robust decision boundary even from a rather small training set. Such a decision boundary can then be taught (at least partially) to the simpler MLP (which operates as a student) by training the MLP on a larger training set where it learns to capture patterns in the target nodes features that correlate well with the soft labels produced by the GNN. If the GNN shows good performance over unseen condition, the MLP trained in this way ends up being more robust wrt a MLP trained only on the original labeled set as it can observe a potentially significantly wider variety of conditions at training time.  \n\nAs in this scenario the MLP doesn’t receive any descriptor representing the behavior of the neighborhood of the target nodes, the overall approach doesn’t work in all possible settings (e.g. in situations where the label of a node depends exclusively on the behavior of the neighbors). Nonetheless, the authors showed in the paper that in classic scenarios (i.e. node classification tasks on citation or product networks) it is possible to effectively train a MLP able to achieve comparable performance to a GNN, while requiring a fraction of the computational cost as no convolution is realized on the given graph.", "summary_of_the_review": "The paper proposes a novel approach for effectively training MLPs for node-wise classification tasks on graph structured data. The proposed approach allows to train architectures able to approach in most scenarios the performance of a reference GNN (SAGE) while requiring a fraction of the computational cost as no convolution is realized on the given graph. The experimental evaluation presented in the paper is generally sound and well highlights the benefits of the idea proposed in the manuscript.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "6LoQAr_tUy3", "reviewer": "Reviewer_UK5z", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "* Pros:\n\n1. The motivation of training student MLPs with teacher GNNs is very important in practice. This paper explores a novel path that is separate from typical acceleration techinique in GNNs, such as sampling and canceling nonlinear transformation. Related discussion in Section 5.5 is well made.\n2. The careful discussion on transductive and inductive learning is significant, with comprehensive experiment results in Table 3. I thought it would not work well in inductive cases, but it can.\n3. It is an intriguing discovery that GLNNs with larger widths can achieve considerable performance boost.\n4. The teacher GNN architecture is flexible, as shown in Section 6. \n\n* Concerns:\n\n1. To clarify, is the training loss of GLNNs in Figure 4 the same as the first label-loss term in (1)?\n2. There is a related work [1] that also trains MLPs on graphs instead of GNNs. They train MLPs with contrastive loss based on graph structure to guide MLPs to find good parameters in the MLP space, which is sharing similar spirits. It would be good to have a discussion on that.\n3. I am wondering whether it will enhance the performance further if the input feature is combined with 1-hop neighorhood, such summation of features in 1-hop neighneighorhood, which is very simple. (Or compare with pure 1-hop GA-MLPs.) This stands between GLNNs and GA-MLP models. The motivation is from the fact that usually low-order neighborhood is the best choice and GNNs cannot handle well with long-range information. In this sence, it will be interesting to see how GLNNs work with simply combined features from low-order neighborhood, under the supervision of GNNs.\n\n4. Since MLPs are trained to fit GNNs in different architectures, is it possible to explore the bias of different GNNs via analyzing learned parameters/functions in MLPs?\n\n[1] Graph-MLP: Node Classification without Message Passing in Graph. Yang Hu et al. ArXiv:2106.04051.", "summary_of_the_paper": "To overcome inference latency of GNN models, this paper proposes a GLNN framework that trains a student MLP with supervision from a teacher GNN model. GLNNs significantly improves performances of pure MLPs and are comparable with traditional GNNs in many cases. The paper explores different real-world settings including transductive and inductive learning. It also discusses when GLNNs will fail, which is a significant question, and address that it is rare in practice.  ", "summary_of_the_review": "I would like to recommend to accept this paper for its practical intuition, satisfying performance and comprehensive discussion on limitations.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a very simple procedure to accelerate the inference time of graph-structured Neural Networks, by distilling knowledge of a GNN into a node-wise MLP. 
Despite some concerns about the novelty of the methodology (which borrows heavily from previous KD works), reviewers generally found this empirical work well executed and providing a potentially useful baseline for large-scale applications. Therefore, the AC recommends acceptance.
Decision: Accept (Poster)