GRAPH-LESS NEURAL NETWORKS: TEACHING OLD
Year: 2021

Abstract:
Graph Neural Networks (GNNs) have recently become popular for graph machine learning and have shown great results on wide node classification tasks. Yet, GNNs 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 these nodes burdens latency-constrained applications. Existing inference acceleration methods like pruning and quantization can speed up GNNs to some extent by reducing Multiplication-and-ACcumulation (MAC) operations. However, their improvements are limited given the data dependency is not resolved. Conversely, multi-layer perceptrons (MLPs) have no dependency on graph data 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 performance infer faster than GNNs by 146×-273× and faster than other acceleration methods by 14×-27×. Meanwhile, 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. A comprehensive analysis of GLNN shows when and why GLNNs can achieve competitive results to GNNs and suggests GLNN as a handy choice for latency-constrained applications.

heading: 1 INTRODUCTION
text: 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; Veličković et al., 2017) like product prediction on co-purchasing graphs and paper category prediction on citation graphs. However, for large-scale industrial applications, MLPs remain the major workhorse, despite common (implicit) underlying graphs and suitability for GML formalisms. One reason for this academic-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-constraint 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-and-ACcumulation (MAC) operations. 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 neighbor 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, enjoy the low-latency and dependency-free nature of MLPs and the graph context awareness 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 offline, coupled with model training. In other words, we can shift considerable work from the latency-constrained inference step, where time reduction in milliseconds makes a 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 an MLP optimized through KD, so it enjoys the benefits of graph contextawareness in training but has no graph dependency in inference. Regarding speed, GLNNs have superior efficiency and are 146×-273× faster than GNNs and 14×-27× 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 comprehensively 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-Kyriazi, 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 239×-758× faster inference
than vanilla GNNs and 27×-32× faster inference than other inference acceleration methods. • We study GLNN properties comprehensively by investigating their performance under different
settings, how they work as regularizers, their inductive bias, expressiveness, and limitations.

heading: 2 RELATED WORK
text: Graph Neural Networks. The idea of GNNs started with generalizing convolution to graphs (Bruna et al., 2014; Defferrard et al., 2017) and later simplified the to a message-passing neural network (MPNN) framework by GCN (Kipf & Welling, 2016). The majority of GNNs after are build on GCN and can be put under MPNN. For example, GAT employs attention (Veličković 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 et al., 2016; Judd et al., 2016) and algorithmic improvements through pruning (Han et al., 2015), quantization (Gupta et al., 2015). For GNNs, pruning (Zhou et al., 2021) and quantizing GNN parameters (Zhao et al., 2020) have been studied. These approaches speed up GNN inference to a certain extent but do not eliminate the neighbor-fetching latency. In contrast, our cross-model KD solves this issue. Graph-MLP also tries to bypass GNN neighbor fetching (Hu et al., 2021). It trains an MLP with a neighbor contrastive loss to push together embeddings for neighboring nodes and pulls apart embeddings for far away nodes. Some sampling works focus on speed up GNN training (Zou et al., 2019; Chen et al., 2018), which are complementary to our goal on inference acceleration.
GNN distillation. Some works tried to distill large GNNs to smaller GNNs. LSP (Yang et al., 2021b) and TinyGNN (Yan et al., 2020) both do KD while preserving local information. Their student is a GNN with fewer parameters, but not necessarily fewer layers than the teacher GNN, which makes both designs still graph-dependent and require latency-inducing fetching. GFKD (Deng & Zhang, 2021) focuses on 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 train a student that works well on new data while preserving its performance on old data. CPF (Yang et al., 2021a) distills GNNs to a student with label propagation (LP) to improve model performance. The student in CPF is not a GNN, but it is still heavily graph-dependent as it uses LP.

heading: 3 PRELIMINARIES
text: Notations. For GML tasks, the input is usually a graph and its node features, which we write as G = (V, E), with V stands for all nodes, and E stands for all edges. Let N denote the total number of
nodes. We use X ∈ RN×D to represent node features, with row xv being the D-dimensional feature of node v ∈ V . We represent edges with an adjacency matrix A, with Au,v = 1 if edge (u, v) ∈ E , and 0 otherwise. For node classification, one of the most important GML applications, the prediction targets are Y ∈ RN×K , where row yv is a K-dim one-hot vector for node v. For a given G, usually a small portion of nodes will be labeled, which we mark using superscript L, i.e. VL, XL, and Y L. The majority of nodes will be unlabeled, and we mark using the superscript U , i.e. VU , XU , and Y U . Graph Neural Networks. Most GNNs fit under the message-passing framework, where the representation hv of each node v is updated iteratively in each layer by collecting messages from its neighbors denoted asN (v). For the l-th layer, h(l)v is obtained from the previous layer representation h (l−1) u (h (0) u = xu) via an aggregation operation AGGR followed by an UPDATE operation as
h (l) N(v) = AGGR({h (l−1) u : u ∈ N (v)}) and h(l)v = UPDATE(h (l) N(v),h (l−1) v )

heading: 4 MOTIVATION
text: As mentioned in Sec 1, GNNs can have considerable inference latency due to graph dependency. One more GNN layer means fetching one more hop of neighbor nodes. To infer a single node with a L-layer GNN on a graph with average degree R will require O(RL) fetches. R can be large for real-world graphs, e.g. 208 for the Twitter (Ching et al., 2015). Also, as fetching for successive layers must be done sequentially, the total latency explodes quickly as L increases. Figure 1 illustrates the dependency added by each GNN layer and the exponential explosion in the number of fetches and inference time. In contrast, the inference time of an MLP with the same number of layers is much smaller and only grows linearly. This marked gap contributes greatly to the practicality of MLPs in industrial applications over GNNs.
The node-fetching latency is exacerbated by two factors: firstly, newer GNN architectures are getting deeper, e.g. 64 layers (Chen et al., 2020), 112 layers (Li et al., 2019), and even 1001 layers (Li et al., 2021). Secondly, industrial-scale graphs are frequently too large to fit into the memory of a single machine, 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 a sparse-matrix-friendly format (often COO or CSR), these graphs are on the order of TBs and are constantly growing. Moving away from in-memory storage results in even slower neighbor-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 GraphSAGE 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 as CNNs and Transformers (Liu et al., 2021). We thus also ask: Can we bridge the best of GNNs and MLPs to get high-accuracy and low-latency models? This motivates us to do cross-model KD from GNNs to MLPs.

heading: 5 GRAPH-LESS NEURAL NETWORKS
text: We introduce GLNN and answer exploration questions of its properties: 1) How do GLNNs compare to MLPs 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 see, extremely effective. In short, we train a “boosted” MLP via KD from a teacher GNN. KD was introduced in Hinton et al. (2015), where knowledge was transferred from a cumbersome teacher to a simpler student. In our case, we generate soft targets zv for each node v with a teacher GNN. Then we train a student MLP with both true labels yv and zv. The objective is as Equation 1, with λ being a weight parameter, Llabel being the cross-entropy between yv and student predictions ŷv , Lteacher being the KL-divergence.
L = λΣv∈VLLlabel(ŷv,yv) + (1− λ)Σv∈VLteacher(ŷv, zv) (1)
The model after KD, i.e. GLNN, is essentially a MLP. Therefore, GLNNs have no graph dependency during inference and are as fast as MLPs. 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.

heading: 5.2 EXPERIMENT SETTINGS
text: Datasets. We consider all five datasets used in the CPF paper (Yang et al., 2021a), i.e. Cora, Citeseer, Pubmed, A-computer, and A-photo. To fully evaluate our method, we also include two more larger OGB datasets (Hu et al., 2020), i.e. Arxiv and Products.
Model Architectures. For consistent results, we use GraphSAGE (Hamilton et al., 2017) with GCN aggregation as the teacher. We conduct ablation studies of other GNN teachers like GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017) and, APPNP (Klicpera et al., 2019) in Section 6.
Evaluation Protocol. For all experiments in this section, we report the average and standard deviation over ten runs with different random seeds. Model performance is measured as accuracy, and results are reported on test data with the best model selected using validation data.
Transductive vs. Inductive. Given G, X , and Y L, 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 VUind ⊂ VU , which partitions VU into the disjoint inductive subset and observed subset, i.e. VU = VUobstVUind. Then we hold out v ∈ VUind and all edges connected to v ∈ VUind, which leads to two disjoint graphs G = Gobs t Gind with no shared nodes or
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 67.55 ± 2.31 75.42 ± 2.31 7.87 (11.65%) 0.03 (0.04%) 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%)
edges. Node features and labels are partitioned into three disjoint sets, i.e. X = XL tXUobs tXUind, and Y = Y L t Y Uobs t Y Uind. Concretely, the input/output of both settings become:
• tran: train on G, X , and Y L; evaluate on (XU ,Y U ); KD uses zv for v ∈ V . • ind: train on Gobs, XL, XUobs, and Y L; evaluate on (XUind,Y Uind); KD uses zv for v ∈ VL t VUobs. Note that for tran, all the nodes in the graph including the validation and test nodes are used for z generation. 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 1 are directly comparable to results reported in previous literature like Yang et al. (2021a) and Hu et al. (2020).
As shown in Table 1, 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 MLPwi1. In Figure 3 (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 as reliably maintain performance on old ones. Thus, to better understand the effectiveness of GLNN, we also consider their performance under a 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. VU = VUobs t VUind. In production, a model might be re-trained periodically, e.g. weekly. The hold-out nodes in V Uind represent new nodes entered the graph between two trainings. V U ind is usually
1-wi means i-times wider hidden layers, e.g. hidden layers of MLPw4 are 4-times wider than the given MLP. 2-Li is used to explicitly note a model with i layers, e.g. SAGE-L2 represents a 2-layer SAGE.
small compared to V Uobs – e.g. Graham (2012) estimates 5-7% for the fastest-growing tech startups. In our case, to mitigate randomness and better evaluate generalizability, we use V Uind containing 20% of the test data. We also evaluate on V Uobs 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 in 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 as well as accuracy in production. See Section 6 for an ablation study of different inductive split rates other than 20-80.
In Table 3, we see that GLNNs can still improve over MLP by large margins for inductive predictions. On 6/7 datasets, the GLNN prod performance are competitive to GNNs, which supports deploying GLNN as a much faster model with no or only slight performance loss. On the Arxiv dataset, the GLNN performance is 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
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-and-ACcumulation (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 as inference acceleration are GNN-to-GNN KD like TinyGNN (Yan et al., 2020) and Graph Augmented-MLPs (GA-MLPs) like SGC (Wu et al., 2019) or SIGN (Frasca et al., 2020). Inference of GNN-to-GNN KD is likely to be slower than a 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-preserving 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 3 (left). We see that GNN-Lis are much slower than MLPs. For GA-MLPs, since full pre-computation 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 as 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 can 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 to 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 KD can help to 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 et 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 on classes other than the ground truth provided by labels, which can 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 Lcut ∈ [0, 1] in Equation 2 to measure the consistency between model predictions and graph topology (details in Appendix C):
Lcut = Tr(Ŷ TAŶ )
Tr(Ŷ TDŶ ) (2)
Here Ŷ ∈ [0, 1]N×K is the soft classification probability output by the model, A and D are the adjacency and degree matrices. When Lcut is close to 1, it means the predictions and the graph
topology are very consistent. In our experiment, we observe that the average Lcut for SAGE over five CPF datasets is 0.9221, which means high consistency. The same Lcut for MLPs is only 0.7644, but for GLNNs it 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 Lcut 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-MLPs 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 are 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 (|X |+m−2 m−1 )2L−1
and |X | respectively. Here m denotes the max node degree, L 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 applications, node features can be high dimensional like bag-of-words, or even word embeddings, thus making |X | enormous. Like for bag-of-words, |X | is in the order of O(pD), where D is the vocabulary size, and p is the max word frequency. The expressiveness of a L-layer GNN is lower
bounded by (|X |+m−2 m−1 )2L−1
= O(pD(m−1)(2L−1)), but empirically, both MLPs and GNNs should have enough expressiveness given D is 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 G[i] and label yi . 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[i];yi) as shown in Qin et al. (2020). If we consider G[i] as a joint distribution of two random variables X [i] and E [i] representing the node features and edges in G[i] respectively, we have
I(G[i];yi) = I(X [i], E [i];yi) = I(E [i];yi) + I(X [i];yi|E [i]) (3)
I(E [i];yi) only depends on edges and labels, thus MLPs can only maximize I(X [i];yi|E [i]). In the extreme case, I(X [i];yi|E [i]) can be zero when y[i] is conditionally independent from X [i] given E [i]. 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 are often highly correlated (Lerique et 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 a low MI scenario in Section 6.

heading: 6 ABLATION STUDIES
text: 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 CPF.
Noisy node features. Following Section 5.8, we investigate failure cases of GLNN by adding different level of Gaussian noise to the node features to decrease their mutual information with labels. Specifically, we replace X with X̃ = (1− α)X + α . Here is isotropic Gaussian and independent from X , and α ∈ [0, 1] denotes the noise level. We show the inductive performance of MLPs, GNNs, and GLNN under different noise levels in the left plot in Figure 5. We see that as α increases, the accuracy of MLPs and GLNNs decrease faster than GNNs, while the performance of GLNN and GNNs are still comparable with small αs. When α reaches 1, X̃ and Y will become independent, which corresponds to the extreme case discussed in Section 5.8.
Inductive split rate. In Section 5.4, we use a 20-80 split of the test data for inductive evaluation. In the middle plot in Figure 5, 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 to 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. For experiments above, we used SAGE to represent GNNs. In Figure 5 (right), we now results with other GNNs as teachers, e.g. GCN (Kipf & Welling, 2016), GAT (Veličković et al., 2017), and APPNP Klicpera et al. (2019). We see that GLNNs can learn from different GNN teachers and improve over MLPs. Their performance with all four teachers is similar, with the GLNN distilled from APPNP slightly worse than others. In fact, a similar phenomenon has been observed in Yang et al. (2021a) as well, i.e. APPNP benefits the student the least. One possible reason is that the first step of APPNP is to utilize the node’s own feature for prediction (prior to propagating over the graph), which is very similar to what the student MLP is doing, and thus provides less extra information to MLPs than other teachers.

heading: 7 CONCLUSION AND FUTURE WORK
text: 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 in GLNNs that are 146×-273× 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 latencyconstraint models. In our experiments, the current version of GLNNs on the Arxiv dataset doesn’t show competitive inductive performance. More advanced distillation techniques can potentially improve the GLNN performance, and we leave this investigation as future work.

heading: A DETAILED EXPERIMENT SETTINGS
text: 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 are 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 statistics of these datasets.
For all datasets, we 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 to a different split. For the OGB datasets, we follow the OGB official splits based on time and popularity for Arxiv and 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 be the same as the teacher GNN, so their total number of parameters stays the same as the teacher GNN.
For GLNN s we do a 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.1 to 0.6.
A.3 KNOWLEDGE DISTILLATION
We use the distillation method proposed in Hinton et al. (2015) as in Equation 1, the hard labels are found to be helpful, so nonzero λs was suggested. In our case, we did a little tuning for λ but didn’t find nonzero λs to be very helpful. Therefore, we report all of our results with λ = 0, i.e. only the second term involving soft labels is effective. More careful tuning of λ should further improve the results since the searching space is strictly larger. We implemented a weighted version in our code, and we leave the choice of λ as future work.
A.4 THE TRANSDUCTIVE SETTING AND THE INDUCTIVE SETTING
Given G, X , and Y L, the goal of node classification can be divided into two different settings, i.e. transductive and inductive. In 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 are only seen during inference time. To create the inductive setting on a 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 VUind ⊂ VU , which partitions VU into the disjoint inductive subset and observed subset, i.e. VU = VUobs t VUind. Then we can take all the edges connected to nodes in VUind to further partition the whole graph, so we end up with G = Gobs t Gind, X = XL tXUobs tXUind, and Y = Y L t Y Uobs t Y Uind. We show the input and output of both settings using the notations below.
We visualize the difference between the inductive setting and the transductive setting in Figure 8.
A.5 CHOOSING SOFT TARGETS UNDER THE TRANSDUCTIVE SETTING
For the transductive setting in Section 5.3, all the nodes in the graph, including the validation and test nodes, are used for the soft target generation. 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 in the related work section, e.g. the CPF paper [1], where we take the dataset and model hyperparameters from. Therefore, to avoid any confusion and for a 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 GLNNs are 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. As you pointed out, this transductive setting can boil down to a sanity check when the student is sufficiently large. That is the reason why we separate the setting to be GLNN and GLNN+ and report the results in Table 1 and Table 2 separately. For GLNN, we are checking how well GLNNs can perform compared to
GNNs under the equal-parameter constraint. The point of Table 1 can be interpreted as given a 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.
Secondly, the task we focus on is node classification, which in many cases is considered as semisupervised 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 a different set of labeled data can be used for evaluation. In our case, we mimic this scenario in the following inductive setting.
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 a machine with 80 Intel(R) Xeon(R) E5-2698 v4 @ 2.20GHz CPUs, and a single NVIDIA V100 GPU with 16GB RAM.

heading: B SPACE AND TIME COMPLEXITY OF GNNS VS. MLPS
text: In Table 1, the model comparison was between equal-sized MLPs (GLNNs) and GNNs. This is how people used to compare models for the sake of fair space complexity, but it is not a completely fair comparison 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, which will take a much larger space than the model parameters. Thus, the space complexity of GNNs is actually much higher than equal-sized MLPs. 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 the left part of Figure 3 that even a 5-layer MLP with 8 times wider hidden layers still runs much faster than a single-layer SAGE. Another example of cross-model comparison is Transformers vs. RNNs. Large Transformers can have more parameters than RNNs because of the attention mechanism, but they also run faster than RNNs in general.
Moreover, the comparison of GNNs and MLPs with the same number of parameters ignores the inductive bias difference. GNNs are advantaged since they get information from two sources when they do inference, i.e. the learned parameters and the graph data. For GNNs, there is an inductive bias of neighbor nodes influencing each other, so the knowledge missing from model parameters can be complemented. For MLPs, model parameters are the only source for them to remember the learned knowledge. They are being very flexible with less inductive bias, which could require more parameters for the model to learn (see Section 5.6 for a more detailed discussion of inductive bias).
In Table 1, we saw that for equal-sized comparison, GLNNs are not as good as GNNs on the OGB datasets. Following the discussion above and given the GLNNs used in Table 1 are relatively small (3 layers and 256 hidden dimensions) for millions of nodes in the OGB datasets, we ask whether this gap can be mitigated by increasing the MLP and thus GLNN sizes. Our answer is shown in Table 2.

heading: C CONSISTENCY MEASURE OF MODEL PREDICTIONS AND GRAPH TOPOLOGY BASED ON MIN-CUT
text: We introduce a metric to measure the consistency between model predictions and graph topology based on the min-cut problem in Section 5.6. The 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
max 1
K K∑ k=1 CTk ACk CTk DCk
(4)
s.t. C ∈ {0, 1}N×K ,C1K = 1N with C being the node assignment matrix that partitions V , i.e. Ci,j = 1 if node i 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}N×K with a soft classification probability Ŷ ∈ [0, 1]N×K , a cut loss Lcut in Equation 2 can become a good approximation of Equation 4 and be used as the measuring metric.

heading: D EXPRESSIVENESS OF GNNS VS. MLPS IN TERMS OF EQUIVALENCE CLASSES OF ROOTED GRAPHS
text: In Chen et al. (2021), the expressiveness of GNNs and GA-MLPs were theoretically quantified in terms of induced equivalence classes of 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 G[i] is a graph with one node i in G[i] 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 i with label yi is to fit a function to the input-output pairs (G[i], yi).
We denote the space of rooted graphs as E . Following Chen et al. (2021), the expressive power of a 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 as the following. Given a family of functions F on E , we define an equivalence relation 'E,F among all rooted graphs such that ∀G[i],G′[j] ∈ E ,G[i] 'E,F G′[j] if and only if ∀f ∈ F , f(G[i]) = f(G′[j]). We now give a proposition to characterize the GNN expressive power (proof in Appendix E). Proposition 1. With X denotes the set of all possible node features and assuming |X | ≥ 2, with m denotes the maximum node degree and assuming m ≥ 3, the total number of equivalence classes of rooted graphs induced by an L-layer GNN is lower bounded by (|X |+m−2 m−1 )2L−1 .
As shown in Proposition 1, the expressive power of GNNs grows doubly-exponentially in the number of layers L, which means it grows linearly in L after taking log(log(·)). The expressive power GA-MLPs only grows exponentially in L as shown in Chen et al. (2021). Under this framework, the expressive power of MLPs, which corresponds to a 0-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 a difference when |X | is small. As in Chen et al. (2021), both the lower bound proof and the constructed examples
showing GNNs are more powerful than GA-MLPs assumed |X | = 2. In real applications and datasets considered in this work, the node features can be high dimensional vectors like bag-of-words, which makes |X | enormous. Thus, this gap doesn’t matter much empirically.

heading: E PROOF OF THE PROPOSITION 1
text: 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 G[i] is a depth-K rooted tree with a (possibly many-to-one) mapping from every node in the tree to some node in G[i], where (i) the root of the tree is mapped to node i, and (ii) the children of every node j in the tree are mapped to the neighbors of the node in G[i] to which j is 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 TL. Then we use TL,X ,m to denote a subset of TL, where the node features belong to X , and all the nodes have exactly degree m (m children), and at least two nodes out of these m 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 3 in Chen et al. (2021).
Proof. Since the number of equivalence classes on E 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 et al., 2021), the lower bound problem in Proposition 1 can be reduced to lower bound |TL|, which can
be further reduced to lower bound the subset |TL,X ,m|. We now show |TL,X ,m| ≥ (|X |+m−2 m−1 )2L−1 inductively.
When L = 1, the root of the tree can have |X | different choices. For the children nodes, we pick m features from |X | and repetitions are allowed. This leads to (|X |+m−1 m ) cases. Therefore,
TL+1,X ,m = |X | (|X |+m−1
m
) ≥ (|X |+m−2 m−1 ) .
Assuming the statement holds for L, we show it holds for L+ 1 by constructing trees in TL+1,X ,m from T, T ′ ∈ TL,X ,m. 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-isomorphic trees, two depth-L+1 trees constructed from T and T ′ 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 a sequence of nodes where the node features form a one-to-one mapping to an L-tuple τ ∈ {(x1, . . . , xL) : xi ∈ X}. Leaf nodes are called node under τ if the path from the root to it corresponds to τ . The children of nodes under different τs are always distinguishable, and thus any assignments lead to distinct rooted aggregation trees of depth L+ 1. The assignment of children of nodes under the same τ , on the other hand, could be overcounted. Therefore, to lower bound TL+1,X ,m, we only consider a special way of assignments to avoid over counting, which is that children of all nodes under the same τ are assigned the same set of features.
Since we assumed that at least two nodes of T have different features, there are at least 2L different τs corresponding to the path from the root to leaves. For a leaf node j under a fixed τ , one of its children needs to 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 (|X |+m−2 m−1 ) cases for each j. Then through this construction, the total number of depth-L+1 trees
from T can be lower bounded by (|X |+m−2 m−1 )2L . Finally, we have this lower bound holds for all
T ∈ TL,X ,m, so we derive TL+1,X ,m ≥ (|X |+m−2 m−1 )2L TL,X ,m, and TL,X ,m ≥ (|X |+m−2 m−1 )∑L l=1 2 l
=(|X |+m−2 m−1 )2L−1

heading: F ADVANCED GNN ARCHITECTURES AS THE TEACHER
text: In our main experiment, SAGE teacher is used throughout to avoid influence by model architecture. To show GLNN has stronger performance given a stronger teacher, we take MLP+CS from the OGB leaderboard as a new teacher, which has reported accuracy 84.18% and ranks 8 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), or require a GPU with >16GB memory, which we don’t have access to. Also, their improvement is not super significant compared to MLP+CS, i.e. 84% to 86%. The result is below. We see that with the new teacher, GLNN+ is even better than SAGE (78.61%), which shows GLNN can get stronger given a stronger teacher.
G GLNN WITH FEATURE AUGMENTATION FROM ONE-HOP NEIGHBORS
In our main experiment, the inductive performance of GLNN on the Arxiv 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 as a 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. 1-hop GA-MLP: firstly, for each node v, we collect features of its 1-hop neighbors u to augment the raw feature of v, i.e. xv → x̃v, like in SGC. Then we train an MLP on the graph with x̃v. Note if v is in the observed graph but u is in the inductive (unobserved during training) part, then v doesn’t collect features from u.
2. 1-hop GA-GLNN: Go through the same feature augmentation step as 1-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 on xv (b) MLP: single model on xv (c) GLNN: SAGE teacher and MLP student on xv (d) 1-hop GA-MLP: single model on x̃v (e) 1-hop GA-GLNN: SAGE teacher on xv , MLP student on x̃v
We show in the table below, with 1-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, but 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).
As we have shown in Figure 3, the 1-Layer GNN in our case is roughly 4 times slower than GLNN (29.31 vs. 7.56), which should be a good approximation for the speed comparison between 1-hop GA-MLP/GA-GLNN 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. We have also included the table above in our appendix. Thank you for helping us strengthen the experiments.

heading: H MODEL PERFORMANCE UNDER DIFFERENT INDUCTIVE SPLIT RATE
text: This section is a 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 on each dataset. For the following plots, the training data label rate is also reduced from 20 per class to 5 per class.
I GLNN UNDER NODE FEATURE HETEROGENEITY AND NON-HOMOPHILY
Besides the 7 datasets used in the main experiments, we consider 4 more datasets from Ivanov & Prokhorenkova (2021) and Lim et al. (2021) to further evaluate GLNN.
The House_class and VK_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 as the opposite of the bag-of-word node features in Cora and etc. Some basic statistics of the datasets are shown in the following table.
We apply the GLNN on House_class and VK_class using the best BGNN model from Ivanov & Prokhorenkova (2021) 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 on these two datasets are quite similar (difference < 0.025). We compare with these baselines by including the best result among the 4 GNN models and refer it as GNN in the table below, i.e. GNN = max(GAT, 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.
We further pick the non-homophilous Penn94 and Pokec datasets from Lim et al. (2021). Some basic statistics of the datasets are shown in the following table.
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 is a purely structural model which does not use node features at all. This shows that the Pokec 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 to this limitation. However, we still see that for most of the non-homophilous datasets, MLPs already work quite well on them, and we can use GLNN for the other ones like Penn94.

Review summaries:
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.

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.  

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:  1) the original labeled set where the GNN was trained; 2) an additional set of unlabeled nodes which are equipped with soft labels produced by the GNN.  As 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.    As 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.