SA-MLP: Distilling Graph Knowledge from GNNs into Structure-Aware MLP
Authors: Jie Chen
Mingyuan Bai
Shouzhen Chen
Junbin Gao
Junping Zhang
Jian Pu
Venue: Accepted by TMLR ()

Abstract: The recursive node fetching and aggregation in message-passing cause inference latency when deploying Graph Neural Networks (GNNs) to large-scale graphs. One promising inference acceleration direction is to distill GNNs into message-passing-free student Multi-Layer Perceptrons (MLPs). However, the MLP student without graph dependency cannot fully learn the structure knowledge from GNNs, which causes inferior performance in heterophilic and online scenarios. To address this problem, we first design a simple yet effective Structure-Aware MLP (SA-MLP) as a student model. It utilizes linear layers as encoders and decoders to capture features and graph structures without message-passing among nodes. Furthermore, we introduce a novel structure-mixing knowledge distillation technique. It generates virtual samples imbued with a hybrid of structure knowledge from teacher GNNs, thereby enhancing the learning ability of MLPs for structure information. Extensive experiments on eight benchmark datasets under both transductive and online settings show that our SA-MLP can consistently achieve similar or even better results than teacher GNNs while maintaining as fast inference speed as MLPs. Our findings reveal that SA-MLP efficiently assimilates graph knowledge through distillation from GNNs in an end-to-end manner, eliminating the need for complex model architectures and preprocessing of features/structures. Our code is available at https://github.com/JC-202/SA-MLP.

Published in Transactions on Machine Learning Research (08/2024)
SA-MLP: Distilling Graph Knowledge from GNNs into Structure-Aware MLP
Jie Chen Fudan University
chenj19@fudan edu..nnneddnnn
Mingyuan Bai
mingyuan.bar riken.jp
RIKEN AIP
Shouzhen Chen Fudon University
chens:/90fudanncdo edu.cn
Junbin Gao University of Sydney
junbin. gao sydney.edu.ar
Junping Zhang Fudan University
jpzhang @ fudan. edu..nnneennn
Jian Pu
jianpu @ www.weefwaaaa...cmmmmm edu.en
Fudan University
Reviewed on OpenReview:
Abstract
The recursive node fetching and aggregation message-passing cause inference latency when de- ploying Graph Neural Networks (GNNs) to large-scale graphs. One promising inference accelera- tion direction is to distill GNNs into caassagepassing--ee frre student Multi-I Layer Perceptrons (MIPs MM.Ps). However, the MLP student without graph dependency cannot fully learn the structure knowledge from GNNs, which causes inferior performance heterophilic and online scenarios. To address this problem, we first design a simple yet effective Structure- Aware MLP (SA-MLP) as a student model. utilizes linear layers as encoders and decoders to capture features and graph structures without message-passing among nodes. Furthermore, we introduce novel structure-mixing knowledge dis- tillation technique. It generates virtual samples imbued with hybrid of structure knowledge from teacher GNNs, thereby enhancing the learning ability of MLPs for structure information. Exten- sive experiments on eight benchmark datasets under both transductive and online settings show that our SA-MLP can consistently achieve similar or even better results than teacher GNNs while main- taining as fast inference speed as MLPs. Our findings reveal that SA-MLP efficiently assimilates graph knowledge through distillation from GNNs in an end-to-end manner, eliminating the need for complex model architectures and preprocessing of features/structures. Our code is available https: /
Introduction
Hamilton et al. 2017 have rapidly gained prominence for analyzing graph datasets in diverse domains such as social networks (Sankar et al.
Graph Neural Networks (GNNs) (Kipf & Welling 2017
2021). traffic networks (Wang et al. 2020) and recommendation systems (He et al. 2020 Liu et al., 2021). The primary success of GNNs stems from the pessage-passing mechanism (Gilmer et al. 2017 that extracts graph knowledge by aggregating neighborhood features via graph structures. This iterative aggregation process help nodes capture long-range neighbor and structure information, ultimately generating more expressive node representation for downstream tasks. However, the number

---

Published in Transactions on Machine Learning Research (08/2024)
Teacher GNNs: Inference recursive neighbor expansion aggregation
GNN
Saft
2
GNN
Targets
GNN
GNN Layer
GNN Layer
Mix Structure
Structure-Mixine Knowledge Distillaiton
Mix Targets Distil
Output
Decsuple Eucuder
Linear Decoder
Node Featres Local Structure
SA-MLP
Student SA-MLP: Inference message-passing
Figure 1: An overview of our distillation framework. A structure-aware MLP student learns from GNNs via structure-mixing KD strategy achieve substantially faster inference without sacrificing performance.
of neighbors for each node would exponentially increase as the number of layers increases (Zhang al.) 2022 Yan
al. 2020). Therefore, the recursive neighbor fetching induced by message-passing leads inference latency, making GNNs hard to deploy for latency-constrained applications, especially for large-scale graphs (Hu et al. 2020).
Common inference acceleration methods, such as pruning (Zhou et al. 2021) and quantization (Tailor et al. 2021 Zhao et al. 2020), can speed up GNNs to some extent by reducing the Cuutiplicatio-and--CCuuumlal operations. However, they are limited by the recursive aggregation of GNNs. Knowledge distillation (KD) is an- other generic neural network learning paradigm for deployment that transfers knowledge from high-performance but resource-intee inntureeinteessve teacher models essource-efficien students (Hinton et al., 2015). Motivated by the impressive results of MLP-like models in computer vision (Melas- Kyriazi 2021] Liu al.) 2022), one promising direction is to utilize KD to learn efficient student MLP with the knowledge from pre-trained teacher GNNs (Zang al. 2022 Tian et al. 2023), After mimicking the output (soft labels) of GNNs, student MLPs can be deployed for faster inference while maintaining performance.
(MAC)
However, limited by the model structure and distillation strategy, MLPs are still unable to fully learn graph knowledge from GNNs. Specifically, 1) The standard MLPs only process node features (Zhang al. 2022) or pre-computed DeepWalk embedding (Tian al.) 2023). The performance gain when distilling GNNs into MLPs can be primarily attributed to the strong memory capabilities (Szegedy et al. 2013) of MLPs, i.e., large MLPs memorize outputs of GNNs on all observed nodes under transductive scenarios (Zhang et al.) (002)). Therefore, the distilled MLP may fail in heterophilic scenarios, where node labels are highly correlated with structural information (Zhu et al. 2020). Similarly, in online scenarios (Si et al., 2023) where test nodes are not available to be pre-computed and distilled during training, the MLP may also struggle. 2) Compared to other complex relational or hidden distillation methods, logit-based KD benefits from marginal computational and storage costs (Zhao et al., 2022). Although logit-based KD easy to deploy in practical applications, its performance inferior when distilling GNNs into MLPs (Zhang et al. 2022). The reason lies in the logits' limited capacity convey comprehensive graph knowledge. Hence, the supervision signal of logit-based KD is too sparse to transfer the graph knowledge from GNNs to MLPs effectively.
To address the above problems, as shown in Figure I we first design simple yet effective Structure-Aware MLP (SA-MLP) student model, which can process structure inputs in an end-to-end and low-latency manner. utilizes two linear encoders to explicitly encode node features and local structure information separately. Then, it concatenates them for another linear decoder to generate the final prediction. The model consists of only two layers, naturally incorporating structure information while offering faster inference. Second, we propose novel cnucture-mixing knowledge distillation via the mixup (Zhang al. 2018) technique to enhance the distillation density and improve the
2

---

Published in Transactions on Machine Learning Research (08/2024)
structure-awareness awwreness of student MLP. It generates the virtual samples, which mix structures and soft labels of two nodes as additional supervision signals to guide the student MLP learning graph knowledge. This distillation strategy still only requires logits of GNNs, bypassing internal details of GNNs, making it lightweight and easy to use. Remarkably, we demonstrate that even without a sophisticated design, the linear layers the SA-MLP and the logits from GNNs are sufficient for transferring graph knowledge to the student MLPs.
We conduct extensive experiments on eight public benchmark datasets under transductive and online scenarios (Si et al. 2023). The results demonstrate that SA-MLP surpasses other MLP-like students and attains comparable even superior performance to teacher GNNs across all scenarios while offering significantly faster inference. Our contributions are summarized as follows:
We propose a message-passing free model SA-MLP, which incorporates structure information without inter- action among nodes and maintains low latency inference.
We design a structure- mixing knowledge distillation strategy that improves the performance and structure awareness of SA-MLP.
Extensive experimental results demonstrate that SA-MLP can achieve competitive performance as GNNs while inferring as fast as MLPs in both transductive and online scenarios.
2 Preliminary
2.1 Notation and Problem Setting
Consider a graph G = EV,E), with N nodes and E edges. Let A NxN be the adjacency matrix, with A., if edge(i,j) E, and 0 otherwise. Let N be the diagonal degree matrix. Each node o is given a d-dimensional feature representation and a e-dimensional one-hot class label y;. The feature inputs are then formed by X E Rxxd and the labels are represented by Y E Nxc, The labeled and unlabeled node sets are denoted as Vz and Vu, and we have V = Vz U Vy. The task of node classification is to predict the labels by exploiting the nodes' features X and the graph structure
2.2 Graph Neural Networks
Most existing GNNs follow the message- message-passing passing paradigm which contains node feature transformation and informa- tion aggregation from connected neighbors on the graph structure Gilmer et al. (017): Wu et al. (2021). The general k-th layer graph convolution for a node on can be formulated as
(k) = f (n. (1) h
{n. (k-1) :E N(u)))
(1)
where representation h; is updated iteratively in each layer by collecting messages from its neighbors denoted as N(v;). The graph convolution operator f usually implemented as a weighted sum of node representations according to the adjacent matrix A in GCN Kipf & Welling (2077) and GraphSAGE Hamilton al. (2017) the attention mechanism in GAT Veličković et al. (2018). However, this recursive expansion and aggregation of neighbors cause inference latency, because the number of neighbors fetching will exponentially increase with the increasing number of
layers Zhang et al. 2002): Yan et al. (2020).
The objective function for training GNNs is the cross-entropy of the ground truth labels Yr, and the output of the network Y, in labeled Vr,
(c)(Yr,)))) = Σ M Y IY
ΣΣ
(2)
NEV, 1=1
2.3 Distill GNNs into MLPs
Knowledge distillation Hinton et al. (2015) aims to compress knowledge pre-trained large teacher model into compact and fast-to-execute student model. The key idea is to force small student networks to imitate the soft targets
3

---

Published in Transactions on Machine Learning Research (08/2024)
generated by the teachers, e.g., minimize the Kullback-Leible (KL) divergence between the logit of teacher and student. Specifically, GLNN proposes to learn MLP student, i.e., Y* = MLP((X) to mimic the output of teacher GNN, i.e., Y GNN(X, A) with the following distillation objective:
C (1 ()-e))CE(YY, YE) + ACKD(Y Y"), CKD(Y', Y = Σ CK BEV
where À is a Hyper-parameler controlling the strength of KD. The goal of our paper is to utilize soft labels of GNNs to learn MLP-like students that can incorporate both features and structure information. Such that the learned MLP can deploy to both transductive and online scenarios, with a much lower computational cost while achieving similar or even better performance compared with GNNs.
3 Related Work
3.1 GNNs and Inference Acceleration
Most GNNs follow the message-passing passing mechanism Gilmer et al. (017). For example, GCN Kipt & Welling (017))
aggregates local neighbor information according to the Laplacian matrix, GAT Veličković et al. (2018) employs atten- tion in the aggregation, GraphS Hamilton et al. (2017) introduces learnable aggregator functions to incorporate the local neighborhood, and GCNII Chen et al. (2020) introduces residual and initial connections. However, of these methods suffer from inference latency induced by recursive aggregation. Some existing work focuses on speed- ing up GNN inference from the model compression perspective by pruning GNN parameters Zhou al.
(2021) and
(021 and Degree-quant Tailor et al. (202T). Although these approaches can reduce model parameters and MAC operations, they are still limited by the neighbor-fetching latency. By using contrastive learning to train an MLP, Graph-MLP also at- tempts to avoid neighbor fetching Hu et al. (202T). but it only considers transductive rather than more practical online settings. There are also some works for neighbor sampling Zou et al. (2019); Chen et al. (2018), normalization Kose & Shen 2023), and sparsification Kose Shen (2033) to speed up GNN training, which are complementary to our goal of inference acceleration.
quantizing with low- wwwprrccssion integer arithmetic Zhao et al. (2020), such as Binarized DGCNN Bahri al.
3.2 Knowledge Distillation for GNNs
Existing GNN KD models try to distill large GNNs into smaller GNNs Zheng et al. (2022); Joshi et al. 2022 2022)
For instance, LSP Yang et al. (2020) and TinyGNN Yan et al. (2220) conduct KD while preserving local information. whereas GFKD Deng & Zhang (02I) and DFAD Zhuang et al. (022)) achieve graph-level KD via graph generation and adversarial training. Moreover, CPF Yang et (2021) utilizes KD learn label propagation student and enjoy prior knowledge. However, these saassageppasiing-ee based methods still require information-fetching resulting in infer- ence latency Zhang et al. (022)) To eliminate message-passee passing. GLNN Zhang et al. (2022) is proposed that teacher GNN teaches pure MLP student graph knowledge via KD. However, the MLP student may fail when structure infor- mation is essential to classification. It implies that the MLP does not fully learn structure information. NOSMOG Tian Walk|Perzzzii learning with relational distillation to transfer graph knowledge from the hidden embeddings GNNs. An alterna- tive method involves using VQ- and GNN's hidden information for pretraining a structure codebook Yang et al.) (2024): Luo et al. (2024). However, these approaches require knowledge of the GNN's architecture and hidden infor- mation for distillation. Moreover, the pre-computation of Deep Walk embeddings or pretraining codebooks on large graphs can be costly. In contrast, our SA-MLP model doesn't require any pre-computation. It can learn structural knowledge end-to-end using a structure- mixing distillation strategy, which only requires soft labels of GNNs.
al. 2023) incorporates positional features from Deep Walk (Perozzi et al. (0014) into an MLP and utilizes adversarial
4
Structure-Aware MLP
4.1 Student MLP Model
The required information for node classification contains two parts, i.e. node feature and graph structure Kipf & Welling (2017); Zhu et al. (202T), which can utilize by GNNs. However, the current MI.P-like student ignores the
4

---

Published in Transactions on Machine Learning Research (08/2024)
Fealure Encoder
Feature
Hx Hxpaff
271
2
22
Sample
$1 0
Concat
Coe
86
LSED
A1, A +..
Aq:
fu
Y
Linear Decoder
Structure Inputs
Structure Encoder
Figure 2: Illustration of SA-MLP, which encodes the feature and structure information with a decouple encoder and utilizes linear decoder to generate final predictions. Moreover, to improve the learning ability of structure knowledge from teacher GNNs, we utilize structure-mixg to generate virtual sample in that contains hybrid structure knowl- edge to enhance the distillation density.
structure inputs for faster inference failed thoroughly learn structure knowledge from teacher GNNs. To effectively exploit features and structure information to generate the final prediction, shown in Figure propose the simple yet effective AiructureAware MLP (SA-MLP) model with the corresponding decouple (feature/structure) encoder and decoder. For inference efficiency, all these modules are implemented with one linear layer.
4.1.1 Decouple Encoder
For the feature encoder, same as GNNs, we simply utilize linear layer to transform input features into feature embedding that contains self-information. However, unlike GNNs, to design efficient structure encoder, the key question is how to capture the structure information in A without interaction among nodes. Inspired by natural language processing model FastText Joulin et al. 2016) which efficiently represents the sentence (line-structured of sequential words) as the summation of a bag of word embeddings, we treat each node's local structure, i.c., Ai.., as bag of context nodes for v; to extract structure information. This idea can naturally be implemented by considering columns of as features and feeding them into a linear layer to capture structure information. Therefore, we encode feature and structure information individually get feature embedding Hx E gaxdi and structure embedding HA E na by
Hx = [x(X) = XWx + bx.
(4)
= HA = -A) AWA + DA.
(5)
where mapping Wx Rdxd; bias bx Rxxd and mapping WA E Nxd2 are learnable parameters. Note that, in contrast to single-layer GNNs, the mapping WA for A serves as learnable positional embedding table for each node, akin to a word embedding table in natural language processing. This approach offers better generalization capabilities compared to the pre-computed DeepWalk positional embeddings utilized NOSMOG Perozzi et al. (2014). (Tian ett al. (003).. Moreover, we inject node centrality in the bias D E Nxd2, which measures how important a node is in the graph and is usually strong signal for graph understanding Ying et al. (202T). Specifically, the degree bias DAi: of v; learnable embedding vector specified by its degree.
4.1.2 Linear Decoder
To generate the final prediction, we fuse feature and structure information via concatenation and utilize another one layer linear decoder Eg.
Y ="= [
(6)
where a indicates a ReLU activation function. Here, we also tested other fusion mechanisms and increased the number of layers for g& but did not observe noticeable improvement, see Table 5 The reason a linear decoder suffices might be that the decoupled encoder has already learned rich graph knowledge through distillation, hence simple decoder exhibits good generalization capabilities.

---

Published in Transactions on Machine Learning Research (08/2024)
4.1.3 Scalability and Complexity
Compared to GNNs, SA-MLP discards the recursive aggregation and simplifies the handling of structural information by treating the columms of A as imput features for fw. This approach allows SA-MLP to maintain the speed of standard MLPs, benefiting from the sparsity of real-worid adjacency matrices A and the efficient sparse-dense matrix multiplication with WA- Moreover, although N may be large, such W W is similar to the widely used user/item embedding in large-scale industrial recommendation systems He et al. (2017); Barkann & Koenigstein (20T6), which is scalable due to the embedding infrastructure. When the system is dynamically increasing in the online scenarios, it possesses scalability by collecting new nodes/edges and appends node ID embedding into WA A for periodic retraining.
The time complexity of SA-MLP in each full-batch forward pass is O + K)) in which d is the hidden dimen- sion, N is the number of nodes, E is the number of edges, and K' is the number of layers. The cost is O(dE) for the first linear mapping of A and (d2) for each MLP. In fact, the operations of mapping A can be easily implemented in the sparse matrix form, which results in high time efficiency. While most GNNs have to propagate features using the adjacency in each layer, their complexity is usually O(dKE + Nd2 K), and the OddEE) term makes it difficult to deploy to large-scale graphs Yan et al. 2020).
In terms of memory complexity, SA-MLP requires additional storage for the structural embeddings WA. leading memory footprint of (Nd).. However, during the stages of model training and inference, WA A is conveniently stored as an embedding table within parameter servers Li et al. 2013), thus only the pertinent parameters required for each individual batch are retrieved. According to the structure of each batch's lines within the adjacency matrix A, the model extracts the structural embeddings of neighbors for B nodes from WA. giving rise to a memory complexity of O DdD This efficient design ensures manageable memory usage even under vast scales.
4.2 Structure-Mixing Knowledge Distillation
Although SA-MLP can efficiently encode features and structure information, discarding the message-passing among nodes still causes suboptimal performance. To allow SA-MLP to enjoy both the efficiency of MLP and the accuracy of GNNs, we conduct cross-model KD from GNNs to SA-MLP. Since the outputs of GNNs are considered to include structure information Yang et al.) (2021); Yan et al. (2020), the logit- based KD Hinton et al. (2015) has been utilized to extract graph knowledge from GNNs.
Inspired by the mixup data augmentation strategy in computer vision Zhang et al. 2018), and without relying on sophisticated KD designs and additional information about GNNs, we propose a structure- the density of graph knowledge distillation. Mixup generates virtual samples via linear combination of paired inputs X and labels Y. It can enhance the generalization of models by increasing the density of the vicinal data distribution for training Zhang et al. (2018). Our proposed structure-mixup simultaneously mixes features X, structure A, and teacher's 's output Y to generate virtual distillation samples as follows.
variant to enhance
Bela(a, a)
x= = 7X + (1 7))
Structure-Mixup
(7)
À 7 + (1-7)AB; Y x==>>'+(1->)) +(1-))
+
where the hyper-parametee a controls the strength of interpolation. The subseript means the index of the corre- sponding batch sample pair after random shuffling for linear combination, e.g., the row index of nodes from [1,2.....n] to [5.n-1.....2] after shuffling. The mixed pair of structure A, features X, and the teacher's output Y contains more comprehensive set of relations between structure inputs and labels, enhancing the density of distillation from the teacher GNN to the SA-MLP.
Note that the mixup on graphs is challenging due to the irregularity and connectivity of the input structure A for GNNs. Existing mixup methods for GNNs attempt to blend hidden embeddings through complex structure alignment techniques Baann al. (202T); Han et al. (2022). However, our approach cireumvents the challenge about how to adapt the mixed structure A to GNNs. Instead, we focus on the mixed outputs Y from existing teacher GNNs, which serve as additional supervision signals transfer knowledge student ML.ss. Then, the mixed structure À and features X

---

Published in Transactions on Machine Learning Research (08/2024)
can be naturally processed by SA-MLP generated student output Y*.
Y SSA-MLP(X,, A).
(8)
To the best of our knowledge, we are the first to introduce the mixup in the KD of GNNs to enhance the distillation density. To transfer the graph knowledge from GNNs MLP, we minimize the Kullback-Leibler (KL) divergence distance between the hybrid output Y of students and Y of teachers. Compared with relational or hidden distillation, bypasses the detail of GNNs and still only requires the soft outputs of teachers, therefore benefits from marginal computational and storage costs. The overall objective on this cmucture-mixing knowledge distillation (SKD) is:
L Y Σ VEV
(9)
4.3
Overall Training and Inference
In this section, we describe the overall training and inference process of transductive and online settings for SA-MLP.
4.3.1 Transductive:
In the transductive setting. the model can observe the structure and features of all nodes during training. Hence, the training objective contains the cross-entropy loss with the ground-truth label on training nodes and the distillation loss with the output of teacher GNNs on total nodes. The total objective is:
[ = (1 (L YL) + ACsKD Y").
(10)
However, the transductive setting may be sufficient evaluate the graph knowledge learning ability since MLP- like models may memorize all the outputs of teacher GNNs.
4.3.2 Online:
In the online setting, the model can only observe the structure and features of training set nodes. Hence the total objective only involves the training nodes:
f = (1 A-ACC YE) + ALsKD Yi, Y.).
(11)
When inference, the SA-MLP can utilize the connection from training nodes to the newest nodes, which contain Iearned structure information.
5
Experiments
5.1
Experimental Setup
5.1.1
Datasets
To evaluate the performance of the proposed SA-MLP, we consider eight public benchmark datasets, including three citation datasets Sen et al. (2008) (Cora, Citeseer, Pubmed), two larger OGB datasets Hu et al." (0200) (Arxiv, Products),
and three heterophily datasets (Chameleon, Squirrel, Arxiv-year) Pei et al. (2020); Lim et al. (2021 whose structure information is important. We used the standard public splits of OGB datasets, and ten frequently used fully supervised splits (48%/32%/2D) %/00% of nodes per class for vrain/validationneest)) provided by |Pei et al. (2020); Zhu et al. (2020) of other datasets for a fair comparison and reproduction. Note that for three small citation datasets, these splits reduce randomness and the possibility of overfitting Zhu al. (2020); Pei et al. (2020). which are stricter than the random splits used in GLNN Zhang al. (2022). The statistics are shown in Table and more details can be found in the Appendix.

---

Published in Transactions on Machine Learning Research (08/2024)
Table Statistics the datasets
Datasets
Types
#Nodes
#Edges
#Features
#Classes
Cora
Homophily
2,708
5,429
1,433
Citeseer
Homophily
3,327
4,732
3,703
Pubmed
Homophily
19,717
44,324
500
3
Arxiv
Homophily
169,343
1,166,243
128
40
Products
Homophily
2,449,029
61,859,140
100
47
Chameleon
Heterophily
2,277
36,101
2,325
Squirrel
Heterophily
5,201
217,073
2,089
Arxiv-year
Heterophily
169,343
1,166,243
128
5.1.2 Transductive and Online Setting
For the transductive setting, we use all node features and structures for training and distillation. For the online setting, we hold out all test and validation nodes (Vv) with their connections when training. For every split, we extract graph G to the subgraph 9r that only contains nodes V2 with corresponding edges, and the subgraph Gontine including 9 plus such edges from V to Vy-
Transductive: train on (9, X, Y,), KD for all nodes V, evaluate on (g. Xu, Yu).
Online: train (9t, X Y,), KD for Vy, evaluate (Gontines X Yv).
5.1.3 Baselines and Training Details
In the following experiments, as in Zhang al. (022), we also use GraphSAGE Hamilton et (007 as our basic teacher model to investigate the learning ability of the proposed SA-MLP from GNNs. Moreover, for the heterophily datasets, apply residual connections to improve the performance of GraphSAGE. Following the standard setting Hu et al. (2020); Bo et al. (202T), we fix the hidden dimension of SA-MLP as 128 for all datasets except 64 for Products. The number of layer in SA-MLP for optimization, LayerNorm Ba et al. 2016), and tune other hyper-parameters. including dropout rate from [0, 0.2, 0.5], learning rate from [0.01, 0.005, 0.05], weight decay from [0, 5e-4, 5e-5], from [0, 0.2, 0.5J, and À from [0.5, 0.8, 1] for distillation via validation sets of each dataset. We report results of GLNN and NOSMOG with the same experimental setup if available. If the results were not previously reported, conducted dyper-paramedd search based on the official codes. More comparisons with NOSMOG and GLNN under random splits can be found in the Appendix.
for all datasets for inference efficiency. We use Adam Kingma Ba (2014)
5.2 Overall Performance
Experimental results on eight datasets over two scenarios with teacher GNN, ML.,, state-of-the-art GNN-MLP distil- lation methods GLNN and NOSMOG, and SA-MLP are presented in Table 2 and 3 In summary, due to the structure awareness, our SA-MLP consistently achieves the best performance and we further observe the following results:
5.2.1 Transductive
As shown in Table 2 SA-MLP outperforms all baselines, including teacher GNN models across all datasets. The reason that SA-MLP encodes the structure information in an alternative way, which may be complementary to GNNs, especially in the heterophily datasets (Chameleon, Squirrel and Arxiv-year). Comparing SA-MLP to NOS- MOG, our SA-MLP achieves an improvement of up to 3.88%. Note that SA-MLP end-to-end learning without the pre-computed deep-walk positional embedding, the relational distillation and adversarial learning used in NOSMOG, demonstrating the simplicity but effectiveness of SA-MLP.
8

---

Published in Transactions on Machine Learning Research (08/2024)
5.2.2 Online
As shown in Table we have the following observations: 1) GLNN only improves slightly MLP and retains large performance gap compared with teacher GNNs. GLNN without graph dependency failed to mimic the output of GNNs in test nodes. Because distillation only occurs on the training nodes. 2) NOSMOG performs better than GLNN by incorporating the pre-computed deep-walk positional embedding and the relational distillation with adversarial learning. However, most cases, it is still inferior to GNNs due to the limited generalization of deep-walk in the test nodes online settings. 3) SA-MLP still consistently outperforms the others across all datasets since the SA-MLP can utilize the connection from training nodes the newest nodes. Combined with structure-mixing distillation, such structure information improve the generalization ability of SA-MLP in online settings. Hence the performance of SA-MLP is even beyond teacher GNN.
Table 2: Experiment results in node classification for the transductive setting: We report the mean test accuracy (%) and standard deviation over ten runs. A represents the improvement of SA-MLP, i.e., DGNN 2 0 indicates that it outperforms GNN.
Dataset
SAGE
MLP
GLNN
NOSMOG
SA-MLP
AGNN
AMPP
NOSMOG
Cora
86.14 74.75:12.22 86.21
87.16 87.26 +0.89
1.1((128%))
12.51(14.51%) 0.10(0.129)
Citeseer
75.13=22.2 72.41+2.18
76.15#2.19
76.34=2.14 76.67 #1.17
1.54(2.02%) 4.26(5.59%)
0.33(0.44%)
Pubmed
89.17=10.46 86.65-+0.35
89.3240.43
89.69-0.37
90.31 +0.38
1.14(1.77%) (66((.10%)
0.62(0.70%)
Arxiv
70.73:10.35 56.05:10.46
63.46::0.45
71.64=0.29 71.68 10.18
0.95(1.33%)
15.63(24.63%)
0.04(0.06%)
Product
77.17:1.32 62.47:10.10
68.86:10.46
78.45-0.38 79.02 10.15
1.85(2.36%) 16.55(24.03%) 0.57(0.74%)
Chameleon
70.61=1.76 46.36+2.52
67.98 70.72=2.88 71.09 #2.21
0.48(0.68%) 24.73(36.38%) 0.37(0.52%)
Squirrll
62.51=22.01 33.18+1.94
6..23+1.87 62.88=1.83
63.51
+2.05
1.00(1.59%) 30.33(48.74%)
0.63(1.01%)
Arxiv-year
51.85 36.711:0.1 46.2241.20 52.34-0.18 54.35 10.15
2.50(4.78%)
(66438.17%) 2.01(3.88%)
Table Experiment results in node classification for the online setting.
Dataset
SAGE
MLP
GLNN
NOSMOG
SA-MLP
AGNN
AMLP
NOSMOG
Cora
8..78
74.75+:2.22 74.98 77.52=2.86 83.60
8.85(11.80%)
6.08(7.53%)
Citeseer
1.72 72.41+2.18 12.55
73.42=1.59
2.74(3.78%)
1.73(2.36%)
Pubmed
87.98=0.666 86.65+0.335
88.86=0.00 88.25+00.33
89.21 =031
1.23(1.38%) 2.56(2.90%)
0.35(0.40%)
Arxiv
67.69-10.24 56.05:0.46 56.35+0.21
63.66=0.25 68.01 =0.240024-0
0.32(0.00% (..66(11.2%%
4.35(6.43%)
Product
65.55=0.88 62.47:0.11 62.45+00.34
65.32=0.42
1.91(2.92%)
4.99 .99%)
2.14(3.26%)
Chameleon
63.73+1.58 46.36:2.52 46.91#2.009
59.05=2.31
65.78
2.05(3.47%) 19.42(41.40%
6.73(10.56%)
Squirrel
55.65=1.47 33.18+1.94 33.27
44.16=2.24
1.31(2.97%)
23.78(71.48%)
12.80(33.00%)
Arxiv-year
48.42-1046 36.7110.21 36.92:1.110 40.85=0.36
49.75 +0.25
1.33(3266%)
13.04(35.22))
8.90(18.38%)
5.3 Ablation Study
Table 4: Ablation studies of student MLPs and KDs, while the variants and d remove the degree bias.
Table 5: Albation studies of different types of fusion
and layers decoder 9a in student MLPs.
Transductive
Online
Transductive Hete
Online
Homo
Hete
Homo
Hete
Homo
Homo
Hete
GNNs
83.48
66.94
80.67
59.69
Add Attentive
84.61
67.24
82.64
60.76
Fusion
K)
83.89
65.11
78.59
38.55
84.79
66.74
79.52
55.92
DIMD
84.59
66.68
82.29
58,94
84.44
67.21
82.60
60.12
c.MLPX..AD).KDD
84.62
67.01
82.51
59,01
Layer
84.56
67.13
82.53
60.05
J)MD
84.67
67.15
82.65
60.11
c)MLP(X,A, DDDS
84.75
67.30
82.65
61.37
Default
84.75
67.30
82.65
61.37

---

Published in Transactions on Machine Learning Research (08/2024)
88
MLP
NOSMOG SA-IPP
86
MLP
NOSMOG
GNN
GNN GLNN
SA-MLP
86
Accuracy
84
80
82
78
80
76
74
72
Model Architectures
Model Architectures
(a) Transductive
(h) Online
Figure 3: Mean accuracy over three citation datasets under different teacher architectures.
5.3.1 Variants of Student MLPs and KDs
We study the five variants of SA-MLP under homophily (Cora, Citeseer and Pubmed) and heterophily (Chameleon and Squirrel) in both transductive and online settings. Due space limits, report the average test accuracy of these variants, as shown in Table 4 and Table 5
Our findings reveal:
1) Role of structure information in student MLP: from the comparison among variants a, b, and in Table 4 the structure information A crucial for the performance of SA-MLP, especially in the online and heterophily scenarios. Moreover, the degree information D with centrality encoding in Equation equation further improve performance.
2) Role of KD strategy: By comparing variants b with d and with e, we can find that the structure structure-mixing mixing distilla- tion strategy consistently outperforms the standard logit-based distillation for both MT.P(X, A) and MIP((X, A, D) student variants. And the improvement is significant under the heterophilic graphs. The reason is that the node classification of these graphs is more stracture-oriented, and the structure-mixing distillation can reduce the sparsity of structure knowledge to improve the structure awareness of student MLPs.
3) Role of fusion and layers in decoder: We study different fusion variants and layers of decoder s, in SA-MLP as follows.
Add: It replaces the concat of Hx and HA to Hx + HA.
Attentive: It replaces the concat of Hx and HA to HH + (1-7)HH where the attentive value 7 E [0, Nx1 of nodes is generated by another linear layer sigmoid ( [ W + bb.
Layer-2/3: It replaces the linear layer in & with two or three layers of MLP.
The results in Table that these variants did not contribute to noticeable improvement various scenarios. The default fusion of concatenate of Hx and HA and the one layer of g. make SA-MLP simple but effective while maintaining fast inference.
5.3.2 Effects of Teacher GNN Architecture
We compare different teacher architectures, including SAGE Hamilton et al. (2117), GCNII(Chen et al. (2020), and GAT Veličkovó et al. (2018). We choose three citation datasets in the transductive and online settings and report the mean accuracy. As shown in Figure in the online settings, GLNN and NOSMOG suffer from weak generalization and cannot achieve similar results as teacher GNNs after being distilled. However, SA-MLP can achieve better results than different architecture teacher GNNs in all settings. The results show that structure awareness is the key the model generalization ability, and our SA-MLP and distillation strategy are general and robust to accelerate the deployment of various GNNs.
10

---

Published in Transactions on Machine Learning Research (08/2024)
Chameleon(Hett)
Cora
90
70
87
Accuracy
68
Accuracy
86
Accuracy
Online
66
85
Transductive
64
Online
84
GNN
NOSMOG
Transductive
SA-MILP
Noise Level
Figure 4: Sensitivity of parameter in mixup of structure- mixing knowledge distillation.
Figure 5: Sensitivity analysis for varying levels of noise in node features.
SA/MLP
55
SA-MLP
GLNNW8
NOSMOG
NOSMOG
SAGE-L3
X SAGE-L3
76
X SAGE-L2
GLNNW4
GLNNW8
Accuracy
GLNNW4
Accuracy
SAGE-L2
71
GLNN
45
GLNN
SAGE-L1
66
MLPs
SAGE-L1
MLPs
10a
10
10'
Log Scale Inference Time (ms)
Log Scale Inference Time (ms)
(a) Products (Homophily)
Aexiv-year (Heterophily)
Figure 6: Accuracy Inference Time among different layers of GNNs and different sizes of MLP models on large- scale datasets under transductive settings.
5.4
Sensitivity Analysis
5.4.1
Hyper-parameter Sensity of Structure-Mixing Knowledge Distillation
We also investigate the sensitivity of the parameter a, which controls the strength of mixup in structure-mise mentturremixinggggee knowl- edge distillation. As shown in Figure 4 the a was effective a wide range under both homophily and heterophily datasets transductive and online scenarios. Moreover, significantly increases the performance under the het- erophilic dataset Chameleon and online scenarios the key clue for generalization. Increasing the strength of structure-mixing can enhance the density of distillation to improve the structure knowledge of SA-MLP.
Online scenario. The reason is that structure information in heterophilic graphs
5.4.2 Robustness to Noisy Features
To illustrate the significance of structure information, following Zhang al. (2022), introduce varying levels of Gaussian noise to node features, denoted as X (1- pe, where [0. 1 represents the noise level, and is the Gaussian noise independent of X. We then visualize the mean results of the PubMed dataset in transductive and online settings at different noise levels in Figure We observe that the performance of MLP and GLNN drop significantly as p increases. However, SA-MLP remains comparable to teacher GNN and NOSMOG, as they both explicitly utilize structured inputs instead of relying solely on node features and NOSMOG employs adversarial training. Note that GNN conducts recursive aggregation from neighbors to extract graph knowledge and overcome noise, while SA-MLP directly processes structure inputs.
11

---

Published in Transactions on Machine Learning Research (08/2024)
5.5 Efficiency Comparison
To further analyze the efficiency of SA-MLP, in Figure 6 we visualize the trade-off between prediction accuracy and inference time on large-scale Products and Arxiv-year datasets. Following GLNNN Zhang et al. (0022). the log scale inference times (ms) are computed based on 10 randomly chosen nodes. We observe consistent trends in both homophily and heterophily, with SA-MLP providing an optimal balance of high accuracy and fast inference time. Notably, SA-MIPP demonstrates performance improvement over MI.P, GLNN and NOSMOG with similar inference speeds, especially for MLP and GLNN. While increasing the hidden size of GLNN to GLNNw4 (4 times wider than GLNN) and GLNNw8 (8 times wider than GLNN) improves their performance, they still lag behind SA-MLP and require longer inference times. In comparison teacher GNNs that display similar performance to SA-MLP, these models demand considerably longer inference times, making them unsuitable for many large-scale data real-world applications. For instance, the 3-layer GraphSAGE (SAGE-L3) requires 1957ms on the Products dataset, whereas SA-MIP needs only 2ms, achieving a 978x inference speed up without sacrificing performance. Although NoSMOG also performs well, it requires preprocessing of the structure with DeepWalk, which is actually very slow on large graphs. However, this preprocessing time not included the inference time. In contrast, SAMLP can directly process the raw input without the need for additional preprocessing.
6 Conclusion
We have presented a gasssage-passing free SA-MLP, a practical solution to address the deployment of GNNs via knowledge distillation. This achieved by designing a simple yet effective structure-aware student MLP model and combining with novel trructur-mixing knowledge distillation strategy. Experiments on eight benchmark datasets show that SA-MLP possesses both the accuracy of GNNs and the inference speed of MLPs, whether in homophilic heterophilic graphs, as well as in transductive and online scenarios. One future work is to investigate the application of SA-MLP to other downstream tasks, such as graph classification and link prediction on social networks.
References
Jimmy Ba. Jamie Ryan Kiros, and Geoffrey E. Hinton. Layer normalization. preprint arXiv: 2016.
Mehdi Bahri, Gaétan Bahl, and Stefanos Zafeirion. Binary graph neural networks. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 9492-9501, 2021.
Oren Barkan and Noam Koenigstein. Item2vec: neural item embedding for collaborative filtering. In IEEE 26th International Workshop on Machine Learning for Signal Processing (MLSP), pp- 1-6, 2016.
Deyu Bo, Xiao Wang, Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 3950-3957, 2021.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In 6th International Conference on Learning Representations, International Conference on Learning Representations, 2018
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional net- works. In International Conference on Machine Learning, pp. 1725-1735. PMLR, 2020.
Xiang Deng and Zhongfei Zhang. Graph-free knowledge distillation for graph neural networks, In Proceedings of the Thirtieth International Joint Conference Artificial Intelligence, 2021.
Justin Gilmer, Samuel S Schoenholz, Patrick Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In International Conference on Muchine Learning, pp. 1263-1272. JMLR. org, 2017.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1025-1035, 2017.
Xiaotian Han, Zhimeng Jiang, Ninghao Liu, and Xia Hu. G-mixup: Graph data augmentation for graph classification. In International Conference Machine Learning, 2022.
12

---

Published in Transactions on Machine Learning Research (08/2024)
Xiangnan He, Lizi Liao, Hanwang Zhang, Liqiang Nie, Xia Hu, and Tat-Seng Chua. Neural collaborative filtering. In Proceedings of the 26th International Conference on World Wide Web, pp. 173-182, 2017.
Xiangnan He, Kuan Deng. Xiang Wang. Yan Li, Yongdong Zhang. and Meng Wang. Lightgnn: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pp. 639 648, 2020.
Geoffrey Hinton, Oriol Vinyals, Jeff Dean, et al. Distilling the knowledge in a neural network. preprint arXiv:/503.02531, 2(7), 2015.
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. In Advances in Neural Informa- tion Processing Systems, 2020.
Yang Hu, Haoxuan You, Zhecan Wang, Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: node classification without message passing in graph. preprint arXiv:2106.04051, 2021.
Chaitanya K. Joshi, Fayao Liu, Xu Xun, Jie Lin, and Chuan-Shema Foo. On representation knowledge distillation for graph neural networks. preprint arXiv:211 .44944 abs/2111 1.0964, 2021.
Chaitanya K. Joshi, Fayao Liu, Xu Xun, Jie Lin, and Chuan Sheng Foo. On representation knowledge distillation for graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, pp. 1-12, 2022. doi: 10. N0.1109/NNNSS
Armand Joulin, Edouard Grave, Piotr Bojanowski, Matthijs Douze, Hérve Jégou, and Tomas Mikolov. Fasttext.zip: Compressing text classification models. preprint arXiv:16/2.03651, 2016.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, preprint arXiv: 1412.6900, 2014.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Oyku Deniz Kose and Yanning Shen. Fast&fair: Training acceleration and bias mitigation for GNNs. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL httpp::/openreevier. nwt wwtp:/eeeeeeeiiieeemoooo
nOK4XEB7Ke
Mu Li, Zhou, Zichao Yang, Aaron Li, Fei Xia, David G Andersen, and Alexander Smola. Parameter server for distributed machine learning. In Big learning NIPS workshop, volume Lake Tahoe, CA, 2013.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances Neural Information Processing Systems, 34, 2021.
Ruiyang Liu, Yinghui Li, Linmi Tao, Dun Liang, and Hai-Tao Zheng. Are we ready for a new paradigm shift? a survey on visual deep mlp. Patterns, 307):000520, 2022.
Weiwen Liu, Yin Zhang, Jianling Wang, Yun He, James Caverlee, Patrick PK Chan, Daniel S Yeung, and Pheng- Ann Heng. Item relationship graph neural networks for e-commerce. IEEE Transactions on Neural Networks and Learning Systems, 2021.
Yuankai Luo, Qijiong Liu, Lei Shi, and Xiao-Ming Wu. Structure-aware semantic node identifiers for learning on graphs. arXiv preprint arXiv:2405. 00.44055.44355 16435, 2024.
Luke Kyras-Kyriazi, Do you even need attention? stack of feed-forward layers does surprisingly well on imagenet. preprint arXiv:2105.02723, 2021.
Hongbin Pei, Bingzhe Wei, Kevin tional networks. In International Conference Learning Representations, 2020.
Chang, Yu Lei, and Bo Yang. Geom-gen gen: Geometric graph convolu-
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In ACM SIGKDD international conference Knowledge discovery and data mining, pp. 701-710, 2014.
13

---

Published in Transactions on Machine Learning Research (08/2024)
Aravind Sankar, Yozen Liu, Jun Yu, and Neil Shah. Graph neural networks for friend ranking in large-scale social platforms. In Proceedings of the Web Conference, pp. 2535-2546, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgie, Lise Getoor, Brian Galligher, and Tina Eliassi-Ran Radd. Collective classi- fication in network data, Al magazine, 29(3):93-93, 2008.
Si Si, Felix Yu, Ankit Singh Rawat, Cho-Jui Hsich, and Sanjiv Kumar. Serving graph compression for graph neu- ral networks. In The Eleventh International Conference on Learning Representations, 2023. URL https: //cpenreview. net/ forum?id=T -iTT--gt
Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus, Intriguing properties of neural networks. preprint arXiv: 1212.6131,.6199, 2013.
Shyam Anil Tailor, Javier Fernandez-Marques, and Nicholas Donald Lane. Degree-quant: Quantization-aware training for graph neural networks. In International Conference on Learning Representations, 2021.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh Chawla. Learning MLPs on graphs: A unified view of effectiveness, robustness, and efficiency. In International Conference on Learning Representations, 2023.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Xiaoyang Wang, Yao Ma, Yiqi Wang, Wei Jin, Xin Wang, Jiliang Tang, Caiyan Jia, and Jian Yu. Traffic flow prediction via spatial temporal graph neural network. In Proceedings The Web Conference, pp. 1082-1092, 2020.
Yiwei Wang, Wei Wang, Yuxuan Liang, Yujun Cai, and Bryan Hooi. Mixup for node and graph classification. ACM Web Conference, 2021.
Z. Wu. S. Pan. F. Chen, G. Long, Zhang, and S. Yu. A comprehensive survey on graph neural networks. JEEE Transactions on Neural Networks and Learning Systems, 32(1):4-24 24, 2021. doi: 10.1 S.0/TNNN.S.2000.29788..
Bencheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou. Tinygnn: Learning efficient graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, 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. In Proceedings of the Web Conference, pp. 1227-1237, 2021.
Ling Yang, Ye Tian, Minkai Xu, Zhongyi Liu, Shenda Hong. Wei Qu, Wentao Zhang, CUI Bin, Muhan Zhang, and Jure Leskovee. Vggraph: Rethinking graph representation space for bridging gnns and mlps. In The Twelfth International Conference on Learning Representations, 2024.
Yiding Yang, Jiayan Qiu, Mingli Song. Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolu- tional networks. In JEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 7074-7083, 2020.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie- Yan Liu. Do transformers really perform badly for graph representation? Advances in Neural Information Processing Systems. 34:28877-28888, 2021.
Hongyi Zhang, Moustapha Cisse, Yann N Dauphin, and David Lopez-Paz. mixup: Beyond empirical risk minimiza- tion. In International Conference Learning Representattons, 2018.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mips new tricks via distillation. In International Conference on Learning Representationss 2022.
Borui Zhao, Quan Cui, Renjie Song, Yiyu Qiu, and Jiajun Liang. Decoupled knowledge distillation. In Proceedings of the IEEE/CVF Conference on computer vision and pattern recognition, pp. 19933-1966,, 2022.
Yiren Zhao, Duo Wang, Daniel Bates, Robert Mullins, Mateja Jamnik, and Pietro Lio. Learned low precision graph neural networks. preprint XXi:22009009232 2020.
14

---

Published in Transactions on Machine Learning Research (08/2024)
Wenqing Zheng, Edward W. Huang, Nikhil S. Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete or missing neighborhoods. preprini (..iv:2/11.04400 abs/2111.04840, 2022.
Hongkuan Zhou, Ajitesh Srivastava, Hanqing Zeng, Rajgopal Kannan, and Viktor Prasanna. Accelerating large scale real-time gnn inference using channel pruning. VLDB, 14(9):197-1605, 2021.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, volume 33, 2020.
Jiong Zhu, Ryan Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen Ahmed, and Danai Koutra, Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pp. 11168- 11176, 2021.
Yu-Lin Zhuang, Lingjuan Lyu, Chuan Shi, Carl Yang, and Lichao Sun. Data-free adversarial knowledge distillation for graph neural networks. In International Joint Conferences on Artificial Intelligence Organization, 2022.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer-dependent importance sam- pling for training deep and large graph convolutional networks. Advances in Neurul Information Processing Systems, 32, 2019.
15

---

Published in Transactions on Machine Learning Research (08/2024)
A Supplementary Material of SA-MLP
A.1 Details of Datasets
We provide the details of the five homophilic datasets (connected nodes tend to the same label) and three heterophilic datasets (labels of connected nodes tend be different) in the following:
Homophilic Datasets
Citeseer, Pubmed, Cora Kipt & Welling (2017 For the basic citation datasets, nodes correspond papers, edges correspond to citation links, the sparse bag-of-words are the feature representation of each node, and the label of each node represents the topic of the paper. Note that we use the public ten data split(48%/332%/200 for
in Pei et al. (2020); Zhu et al. (2020) to reduce randomness and enhance reproducibility. Compared with the GLNN that uses only 20 nodes of each class for training, the results of our splits are more stable and reduce the possibility overfitting Zhu et al. (2020).
Arxiv Hu al. (2020): The Arxiv dataset is large-scale citation network collected from all Computer Science arXiv papers. Each node is an arXiv paper, and edges are citation relations between papers. The features are 128-dimensional averaged word embeddings of each paper, and labels are subject areas of papers.
Products Hu et al. (2020): The Products is large-scale Amazon product co-purchasing network. Nodes represent products sold in Amazon, edges indicate the products purchased together, and features are -i0-dimensional bag-of- of-words features.
Heterophilic Datasets
Squirrel, Chameleon Pei et al. (2020): Chameleon and Squirrel are web pages extracted from different topies in Wikipedia. Similar to WebKB, nodes and edges denote the web pages and hyperlinks among them, respectively, and informative nouns in the web pages are employed construct the node features in the bag-of-word form. Webpages labeled in terms of the average monthly traffic level.
Arxiv-year Lim et al. ) Modifying node labels of the Arxiv dataset to the year of paper, and the goal to predict the year paper publication that allows for evaluation of GNNs in large-scale non-homophilous settings.
A.2 Additional Comparison of Citation Datasets
We provide additional experiments for the comparison under the random splits (20 labeled nodes of each class during training) of citation datasets used GLNN and report the mean test accuracy in Table 6 We can observe that SA- MLP also consistently outperforms GLNN, NOSMOG and teacher GNN. Moreover, we conduct the production (prod) scenario that involves both inductive (ind) and transductive (Irans) settings used in GL.NN (see Table SA-MLP can also achieve the best performance across all scenarios. However, the performance of these splits that only contained 20 labeled nodes is susceptible to typer-parameter since the few training data cause the risk of overfitting.
find that
Table 6: Inductive, transductive, and production sce- nario of citation datasets under random splits.
Table 7: Comparison with GLNN+ in large-scale datasets.
Dataset
SAGE
GLNN
NOSMOG
SA-MLP
prod
79.53
77.82
81.02
81.21
Cora
81.03
73.21
81.36
81.03
Dataset
Setting
SAGE
GLNN
GLNN+
SA-MLP
trans
79.16
78.97
80.93
81.47
Arxiv
trans
70.92
63.46
72.15
71.54
online
67.69
56.35
$6.56
68.01
Citeseer
prod 68.06
ind
19.14
69.08
68.48
70.30
70.60
70.67
70.53
Products
online
trans
65.55
78.61
62.45
68. 86
77.65
62.58
67.46
79,02
frams
67.79
69.23
70.67
70.81
trany
$1.85
46.22
$1.02
53.31
Arixv-ycar
prud 74.77
74.67
75.82
76.12
online
48.42
36.92
36.81
49.55
Pubmed
ind
75.07
74.52
75.87
76.04
74.70
74.70
75.80
76.15
16

---

Published in Transactions on Machine Learning Research (08/2024)
Table 8: Speed comparison between SA-MLP and other inference acceleration of SAGE. Numbers (in ms) are infer-
ence time 10 randomly chosen nodes. "** indicates our implementation based on released codes of GLNN.
Model
Structure
Arxiv
Products
SAGE
489.49
2071.30
QSAGE
433.90
1946.49
PSAGE
465.43
2001.46
NSSAGE
V
91.03
107.31
GLNN+
3.34
7.56
SAGE*
V
386.85
1957.11
GLNN+*
3.45
8.64
NOSMOG
1.36
1.34
SA-MLP
1.18
1.12
A.3 Additional Comparison of GLNN+
GLNN also provides larger GLNN+, which scales hidden dimension from 256 1024 for Arxiv (GLNNw4) and 2048 for Product (GLNNw8), with larger capacity but slower speed. We provide additional experiments for the GLNN+ of the trans and online for large-scale OGB datasets. We omit other datasets since the performance of GLNN+ is similar to that of GLNN. From Table 7 we find that GLNN+ can improve the performance of large-scale datasets under the trans setting. However, achieves similar results to GLNN under the online setting, which implies that the improvement of trans for OGB datasets is due to the memory capacity, i.c., the larger parameters of GLNN+ can memorize all the teacher outputs. It still does not fully understand the structure information and generalizes limitedly unseen test nodes under the online setting. However, the improvement over both trans and online of SA-MLP is due explicit structure awareness.
A.4 Additional Inference Time Comparison
Following the settings GI.NN /Zang al. (2022), we also compare SA-MLP with other inference acceleration tech- niques with GNNs, including vanilla SAGE, quantized SAGE from FP32 to INT8 (QSAGE), SAGE with 50% weights pruned (PSAGE), and inference with neighbor sampling with fan-out 15 (NSSAGE). All GNNs have three layers and 256 hidden units, while GLNN+ has 1024 hidden units for Arxiv and 2048 for Products to achieve optimal perfor- mance Zhang et al. (022). As shown in Table all MLP-like students achieve substantially faster inference than GNN variants. Moreover, SA-MLP is the only method that processes structured inputs explicitly but offers the fastest infer- ence speed without sacrificing performance. Following the original paper of NOSMOG, we set the hidden size to 256 and achieved the best performance. Although processed the pre-compputed deepwalk embedding, the Setting the hidden Without considering the time cost of preprocessing by WelpWalk, NoSMOG's inference time is significantly less than that of GLNN. The reason is that uses 256 as the hidden size achieve optimal performance. Compared to GLNN+ and NOSMOG, the speedup can be attributed to Pytorch's sparse tensor multiplication with structure inputs and the smaller hidden unit size (128 for Arxiv and 64 for Products) employed in SA-MLP.
17


Reviews:
[{"review_id": "oN6Vq8vfb2", "reviewer": "Reviewer_L4dK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well-written and easy to follow. Also, the topic of knowledge distillation for GNNs has currently attracted much attention with several recent attempts to address its challenges. Therefore, I believe that the paper is interesting for at least some individuals in TMLR's audience. The proposed method is relatively novel and has shown promising results in different tasks and settings. \n\n\nThere are, however, several concerns with the evaluations and motivations. There is a lack of discussion with several recent methods (to name a few [1, 2]) that also have discussed the importance of inductive setting, showing good results in this setting as well. Not only a discussion of these studies is necessary, but it also is important to compare them with this method and provide evidence as to why we need SA-MLP in the presence of the existing methods. \n\nCurrently, there is no theoretical evidence for the performance of SA-MLP and why it can achieve good performance. When talking about large graphs, expressive models usually show better results. Is there any guarantee for the expressive power of SA-MLP? Can it preserve the power of teacher GNNs?\n\nTo my understanding, the proposed method uses more memory than existing approaches. This can be an important challenge for large graphs, which is the interest of this paper. It would be beneficial to have a memory comparison with existing methods. \n\n  \n[1] VQGraph: Rethinking Graph Representation Space for Bridging GNNs and MLPs. Yang et al. ICLR 2024.  \n[2] Structure-aware Semantic Node Identifiers for Learning on Graphs. Leo et al. 2024", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Due to the inference latency of GNNs in large-graphs, this paper presents a knowledge distillation technique to train a Structure-Aware MLP. The proposed approach is based on generating virtual samples using the structural knowledge from teacher GNNs.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "b0lKs3HntH", "reviewer": "Reviewer_XdoB", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper is overall easy to follow and understand. \n2. The problem is interesting, and the proposed method is effective in multiple settings.\n\nWeaknesses:\n1. The explanation of the structure mixup seems not clear or reasonable enough. \n2. The studied models are not large enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a novel structure-aware MLP as the student model for graph knowledge distillation. The technique includes a structure-mixup technique that can generate virtual distillation samples. Experiments on multiple datasets and different setups verify the validity of the method.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I don't quite get what the $X_*$ means in equation 7. If it is randomly shuffled among the whole graph, does it mean that features from two structurally irrelevant nodes are likely to be added up in $X_*$? If so, it seems not reasonable.\n\n2. As a contribution of this work, the ablation study of whether to use structure-mixup or not seems not included. Meanwhile, there is no experimental study on how to choose $\\gamma$ in equation 7. I only find the experiments for $\\alpha$ in Figure 4.\n\n3. I am wondering whether you can use deeper GNN models for the teacher model. What will the student model change accordingly in this case? Can you use Graph Transformer or attention-based GNN in the teacher model?", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EdVvpWettI", "reviewer": "Reviewer_csBk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- an interesting idea\n- an extensive set of experiments\n\nWeakness:\n- my main concern/confusion is about the architecture itself. Unless I am missing something, by considering the column/lines of the adjacency matrix as features (equation (5), in which I think it is the lines of $A$ that are features and not the columns as indicated by the authors), the trained MLP is specific to one graph. In particular, it is not permutation-equivariant (which is the main characteristic of graph machine-learning models), and cannot be applied to new graphs, graphs with different number of nodes (the dimension of $W_A$ will not match), and so on. For this matter, I do not understand how the online experiment are performed, since the training and testing graphs do not have the same dimension?\n\nThis seems very restrictive, and is in fact somewhat of a \"forbidden\" operation in graph machine-learning. Instead, people have to rely on embeddings such as Deepwalk, which are permutation-equivariant and can be computed/generalized on any graphs.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In this paper, the authors introduce a strategy to perform knowledge distillation for graph machine learning, which allows to transfer knowledge from GNNs to simple MLPs, which are far faster at the inference stage. While existing methods incorporate the graph structure as deepwalk embedding or ignore it altogether, the authors adopt a simple strategy in which the columns of the adjacency matrix are simply concatenated as features to each node. They also propose a mixup data augmentation strategy. They perform extensive experiments in the transductive and online settings, with ablation studies and many different datasets.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "See above, the proposed architecture is specific to one fixed graph, which is exceedingly restrictive.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is very borderline, but there are no strong specific cases of claims not matching evidence, so I'd recommend acceptance by tmlr criteria.
Decision: Accept (poster)