Learning MLPs on Graphs: A Unified View of Effectiveness, Robustness, and Efficiency
Authors: Yijun Tian
Chuxu Zhang
Zhichun Guo
Xiangliang Zhang
Nitesh Chawla
Venue: ICLR 2023 notable top 25% (2023)
Keywords: Graph Representation Learning
Knowledge Distillation

Abstract: While Graph Neural Networks (GNNs) have demonstrated their efficacy in dealing with non-Euclidean structural data, they are difficult to be deployed in real applications due to the scalability constraint imposed by the multi-hop data dependency. Existing methods attempt to address this scalability issue by training student multi-layer perceptrons (MLPs) exclusively on node content features using labels derived from the teacher GNNs. However, the trained MLPs are neither effective nor robust. In this paper, we ascribe the lack of effectiveness and robustness to three significant challenges: 1) the misalignment between content feature and label spaces, 2) the strict hard matching to teacher's output, and 3) the sensitivity to node feature noises. To address the challenges, we propose NOSMOG, a novel method to learn NOise-robust Structure-aware MLPs On Graphs, with remarkable effectiveness, robustness, and efficiency. Specifically, we first address the misalignment by complementing node content with position features to capture the graph structural information. We then design an innovative representational similarity distillation strategy to inject soft node similarities into MLPs. Finally, we introduce adversarial feature augmentation to ensure stable learning against feature noises. Extensive experiments and theoretical analyses demonstrate the superiority of NOSMOG by comparing it to GNNs and the state-of-the-art method in both transductive and inductive settings across seven datasets. Codes are available at https://github.com/meettyj/NOSMOG.

Published as a conference paper at ICLR 2023
LEARNING MLPs ON GRAPHS: A UNIFIED VIEW OF EFFECTIVENESS, ROBUSTNESS, AND EFFICIENCY
Yijun Tian', Chuxu Zhang", Zhichun Guo', Xiangliang Zhang', Nitesh V. Chawla' University of Notre Dame, BBaaddeis University
yijun. tian@nd. chuxuzhang wwwpchaanngrranneiiieeee eddu zguo5end. edu, #2hang33end.ess @nd.edu, nchawla@nd. edu
ABSTRACT
While Graph Neural Networks (GNNs) have demonstrated their efficacy in dealing with non- -on-uuclde structural data, they are difficult to be deployed in real upplications due to the scalability constraint imposed by the multi-hop data dependency. Existing methods attempt to address this scalability issue by training student multi-layer perceptrons (MLPs) exclusively using labels derived from the teacher GNNs. However, the trained MLPs are neither effective nor robust. In this paper, we ascribe the lack of effectiveness and robustness to three significant challenges: 1) the misalignment between content feature and label spaces, 2) the strict hard matching to teacher's output, and 3) the sensitivity to node feature noises. To address the challenges, we propose NOSMOG, a novel method to learn NOise-robust Structure-aware MLPs On Graphs, with remarkable effectiveness, robustness, and efficiency. Specifically, we first address the misalignment by complementing node content with position features to capture the graph structural information. We then design an innovative representational similarity distillation strategy to inject soft node similarities into MLPs. Finally, we introduce adversarial feature augmentation to ensure stable learning against feature noises. Extensive experiments and theoretical analyses demonstrate the superiority of NOSMOG by comparing GNNs and the state-of-the method in both transductive and inductive settings across seven datasets. Codes are available at https: sttps://github.. wtt.://....//etettttt///////////
node content features
INTRODUCTION
Graph Neural Networks (GNNs) have shown exceptional effectiveness in handling non-Euclidean structural data and have achieved state-of-the-art performance across a broad range of graph mining tasks (Hamilton et al. 2017; Kipf & Welling 2017] Veličković al., 2018). The success of modern GNNs relies on the usage of message passing architecture. which aggregates and learns node representations based on their (multi-hop) neighborhood (Wu et al. 2020 /hou et al. 2020). However, message passing is time-consuming and somputation-intensive. making it challenging to apply GNNs to real large-scale applications that are always constrained by latency and require the deployed model to infer fast (Zhang et al. 2020 2022a). To meet the latency requirement, multi-layer perceptrons (MLPs) continue to be the first choice (Zhang al. 20226), despite the fact that they perform poorly in non-euclidean data and focus exclusively on the node content information.
Inspired by the performance advantage of GNNs and the latency advantage of MLPs, researchers have explored combining GNNs and MLPs together to enjoy the advantages of both (Zhang et al. 2022b /Zheng et al. 2022 Chen et al. 202Tb. To combine them, one effective approach to use knowledge distillation (KD) (Hinton et al. 2015). where the learned knowledge is transferred from GNNs to MLPs through soft labels (Phuong & Lampert 2019). Then only MLPs are deployed for inference, with node content features input. In this way. MLPs can perform well by mimicking the output of GNNs without requiring explicit message passing, and thus obtaining a fast inference speed (Hu al. 2021). Nevertheless. existing methods are neither effective nor robust, with three major drawbacks: (1) MLPs cannot fully align the input content feature to the label space, especially when node labels are correlated with the graph structure; (2) ML.ss rely the teacher's output learn

---

Published as a conference paper at ICLR 2023
strict hard matching, jeopardizing the soft structural representational similarity among nodes; and (3) MLPs are sensitive to node feature noises that can easily destroy the performance. We thus ask: Can learn MLPs that graph structure-awen in both the feature and representation spaces, insensitive to node feature noises, and have superior performance as well as fast inference speed?
To address these issues and answer the question, propose learn KOise-robust Structure-awar MLPs On Graphs (NOSMOG), a novel method with remarkable performance, outstanding robustness and exceptional inference speed. Specifically, we first extract node position features from the graph and combine them with node content features as the input of MLPs. Thus MLPs can fully capture the graph structure as well as the node positional information. Then, we design novel representational similarity distillation strategy to transfer the node similarity information from GNNs to MLPs, so that MLPs can encode the structural node affinity and learn more effectively from GNNs through hidden layer representations. After that, we introduce the adversarial feature augmentation to make MLPs noise-resistant and further improve the performance. To fully evaluate our model, we conduct extensive experiments on 7 public benchmark datasets in both transductive and inductive settings. Experiments show that NOSMOG can outperform the state-of-the-art method and also the teacher GNNs, with robustness noises and fast inference speed. In particular, NOSMOG improves GNNs by 2.05%, MLPs by 25.22% and existing state-of oftt-offthhe-rt method by 6.63% %, averaged across 7 datasets and 2 settings. In the meantime, NOSMOG achieves comparable efficiency to the state-of-the-ar method and is 833x faster than GNNs with the same number of layers. In addition, we provide theoretical analyses based on information theory and conduct consistency measurements between graph topology and model predictions to facilitate a better understanding of the model. To summarize, the contributions of this paper are as follows:
We point out that existing works of learning MI.s on graphs are neither effective nor robust. We identify three issues that undermine their capability: the misalignment between content feature and label spaces, the strict hard matching to teacher's s output, and the sensitivity to node feature noises.
To address the issues, we propose to learn noise-robuse and structure-aware MLPs on graphs, with remarkable efffectiveness, robustness, and efficiency. The proposed model contains three key components: the incorporation of position features, representational similarity distillation, and adversarial feature augmentation.
Extensive experiments demonstrate that NOSMOG can easily outperform GNNs and the state-of- the-art method. In addition, we present theoretical analyses, robustness investigations, efficiency comparisons, and ablation studies to validate the superiority of the proposed model.
2 RELATED WORK
Graph Neural Networks. Many graph neural networks (Veličković et al. 2018 [i al. 2019 Zhang al. 2019 Chen et al.) 2020) have been proposed to encode the graph-structure data. They take advantage of the message passing paradigm by aggregating neighborhood information to learn node embeddings. For example, GCN (Kipf & Welling, 2017) introduces layer-wiss wise propagation rule to learn node features. GAT (Veličković et al. 2018 incorporates an attention mechanism to aggregate features. DeepGCNs (Li et al.. (019)) and GCNII (Chen et al. (2000) utilize residual connections to aggregate neighbors from multi-hop and further address the over-smoothing problem. However, These message passing GNNs only leverage local graph structure and have been demonstrated be no more powerful than the WL graph isomorphism test (Xu et al. 2019 Morris et al.. 2019). Recent works propose to empower graph learning with positional encoding techniques such as Laplacian Eigenmap and DeepWalk YYou et al. 2019 Wang et al. 2022 Tian et al. 2023a). so that the node's s position within the broader context the graph structure can detected. Inspired by these studies, we incorporate position features to fully capture the graph structure and node positional information.
Knowledge Distillation on Graph. Knowledge Distillation (KD) has been applied widely graph- based research and GNNs (Yang et al.) 20200) Yan et al. (2020) Guo et al.) [023 Tian et al.) (023b). Previous works apply KD primarily to learn student GNNs with fewer parameters but perform as well as the teacher GNNs. However, time-consuming message passing is still required during the learning process. For example, LSP (Yang et al. 2020) and TinyGNN (Yan et al., 2020) introduce the local and peer-aware modules that rely heavily on message passing. To overcome the latency issues, recent works start focusing on learning MLP-based student models that do not require message passing (Hu et al., 2021 Zhang et al. 2022b
Zheng et al. 2022). Specifically, MI. student
2

---

Published as a conference paper at ICLR 2023
is trained with node content features as input and soft labels from GNN teacher as targets. Although MLP can mimic GNN's s prediction, the graph structural information is explicitly overlooked from the input, resulting in incomplete learning, and the student is highly susceptible to noises that may be present in the feature. We address these concerns in our work. In addition, since adversarial learning has shown great performance in handling feature noises and enhancing model learning capability (Jiang et al. 22200) Xie et al. [2020] Tian et al.) 2022 Kong et al. (2022), we introduce the adversarial feature augmentation to ensure stable learning against noises.
PRELIMINARY
Notations. A graph is usually denoted as (V,E,C) where V represents the node set, E represents the edge set, C E R xde stands for the d.-dimensional node content attributes, and N the total number of nodes. In the node classification task, the model tries predict the category probability for each node v E V. supervised by the ground truth node category Y E R where K is the number of categories. We use superscript L to mark the properties of labeled nodes (i.e.. V.L, C² and YL), and superscript U to mark the properties of unlabeled nodes (i.e., V WVC, and YU).
Graph Neural Networks. For a given node E V, GNNs aggregate the messages from node neighbors (v) to learn node embedding h. E Rd with dimension dn. Specifically, the node embedding 1-th layer h is learned by first aggregating (AGG) the neighbor embeddings and then combining (COM) it with the embedding from the previous layer. The whole learning process can be denoted as: h COM(n!-1 (-1) AGG(( (-! (No)))).
PROPOSED MODEL
In this section, we present the details of NOSMOG, An overview of the proposed model is shown in Figure 11 We develop NOSMOG by first introducing the background of training MLPs with GNNs distillation, and then illustrating three key components in NOSMOG, i.e., the incorporation of position features (Figure 1 (b)), representational similarity distillation (Figure (c)), and adversarial feature augmentation [ (d).
Training MLPs with GNNs Distillation. The key idea of training MLPs with the knowledge distilled from GNNs is simple. Given a cumbersome pre-trained GNN, the ground truth label yu for any labeled node E VL, and the soft label x, learned by the teacher GNN for any node V. the goal is to train a lightweight MLP using both ground truth labels and soft labels. The objective function can be formulated as:
L= Σ LGT (Bu, + Σ LSL (Br (Bv. WEV
DEVL
where Ler is the cross-entropy loss between the student prediction D, and the ground truth label you Lst is the KL-divergence loss between the student prediction D. and the soft labels 2,, and X is trade-off weight for balancing two losses.
Incorporating Node Position Features. To address the issue of misalignment between content feature and label spaces as well as assist MLP in capturing node positions on graph, we propose to enrich node content by positional encoding techniques such as DeepWalk (Perozzi et al. 2014). By simply concatenating the node content features with the learned position features, MLP is able to capture node positional information within broad context of the graph structure and encode it in the feature space. The idea of incorporating position features is straightforward, yet as we will see, extremely effective. Specifically, we first learn position feature P. for node E V by running DeepWalk algorithm on G. Noticed that there are no node content features involved in this step, so the position features are solely determined by the graph structure and the node positions in the graph. Then, we concatenate (CONCAT) the content feature C, and position feature P. to form the final node feature X,,. After that, send the concatenated node feature into MLP to obtain the category prediction ÿ... The entire process is formulated as:
X,, = CONCAT P.),
9. = MM.P(X.).
Later, ÿ. is leveraged calculate Lot and LSt. (Equation
3

---

Published as a conference paper at ICLR 2023
(a)
GNN Teacher
(b)
Learn Position by Positional Encoding
Graph
0.2 0.3
0.5
Representational
0.7
0.2
Squared Error
Similarity Distillation
0.1
0.3
Concatenate
0.3
Soft Label Distillation
Learn Representational Similarity
Node Content
(d)
Features
Node Position
Adversarial Feature Augmentation (d)
Features (b)
MLP Student
Adversarial Perturbation
Figure 1: (a) The overall framework NOSMOG: A GNN teacher is trained the graph obtain the representational node similarity and soft labels. Then, an MLP student trained on node content features and position features, guided by the Icarned representational node similarity and soft labels. We also introduce the adversarial feature augmentation to ensure stable learning against feature noises. (b) Acquisition of Node Position Features: capturing node positional information by positional encoding techniques. (c) Representational Similarity Distillation: enforcing MI. to learn node similarity from GNN's representation space. (d) Adversarial
Feature Augmentation:
learning adversarial features by generating adversarial perturhation for input features.
Representational Similarity Distillation. With the aim of mitigating the constraint of strict hard matching to teacher's output, and facilitating MLP to capture the soft structural node similarity, propose the Representational Similarity Distillation (RSD) to encourage MLP to learn from GNN's representation space. RSD preserves the similarity between node embeddings, and leverages mean squared error measure the similarity discrepancy between GNN and MIPP Compared to soft labels, the relative similarity between intermediate representations of different nodes serves as a more flexible and appropriate guidance from the teacher model (Tung & Mori 2019). Specifically, given the learned GNN representations HG E -g-V xda and the MLP representations H M E IR Xdar
where de and dı indicate the representation dimension of GNN and MLP respectively, we define the intra- intra-model representational similarity SGNN, SMLP for GNN and MLP as:
SGNN HG (HG))
and SMLP H's (H')), H'M o(WM HM),
(3)
where WM E Rd xdar is the transformation matrix, a is the activation function (we use ReLU in this work), and H3 is the transformed MLP representations. We then define the RSD loss LRSD to minimize the inter-model representation similarity using the Frobenius norm ||r:
LASD(SGNN, SMLP) ||SANN SMLPII
Adversarial Feature Augmentation. MLP is highly susceptible to feature noises (Dey et al. 2017) only considers the explicit feature information associated with each node. To enhance MLP's robustness to noises, we introduce the adversarial feature augmentation to leverage the regularization power of adversarial features (Kong et al. 2022, Zhang et al. 2023). In other words, adversarial feature augmentation makes MLP invariant to small feature fluctuations and generalizes to out-of- distribution samples, with the ability to further boost performance (Wang et al. 2019). Compared to the vanilla training that original node content features C' are utilized obtain the category prediction, adversarial training learns the perturbation and sends maliciously perturbed features X + ò as input for MLP to learn. This process can be formulated the following min-max optimization problem:
min
max |
LogPPPXLP + +6))
(5)
where X represents the concatenation of node content and position features shown in Eq. 2 indicates the model parameters, is the perturbation, || IIp is the f, no-m distance metric, and is the perturbation range. Specifically, choose Projected Gradient Descent (Madry al. 2018) as
4

---

Published as a conference paper at ICLR 2023
the default attacker to generate adversarial perturbation iteratively:
6.+1 [1 [6: + s siinn (Vo (-Y
++))))
(6)
where is the perturbation step size and V5 is the calculated gradient given 6. For maximum robustness, the final perturbation = 8T is learned by updating Equation T times to generate the worst-case noises. Finally, accommodate KD, perform adversarial training using both ground truth labels y, for labeled nodes (u E V2), and soft labels 2, for all nodes in graph (v E V). Therefore, can reformulate the objective in Equation follows:
X + Ó, X
8 = ML)((X.,,
LADY = -max|- dee
Σ
yo log (i'') - Σ log(('))-
DEVL
BEV
The final objective function C is defined as the weighted combination of ground truth cross-entropy loss LCT, soft label distillation loss LSL. representational similarity distillation loss LRSD and adversarial learning loss LADV:
L = Ler \LSL + pLasD + MLADV,
(8)
where A, and are trade-off weights for balancing LSL, LRSD and LADV, respectilly...
5 EXPERIMENTS
In this section, we conduct extensive experiments to validate the effectiveness, robustness, and efficiency of the proposed model and answer the following questions: 1) Can NOSMOG outperform GNNs, MLPs, and other GNNs-MLPs methods? 2) Can NOSMOG work well under both inductive and transductive settings? 3) Can NOSMOG work well with noisy features? 4) How does NOSMOG perform in terms of inference time? 5) How does NOSMOG perform with different model components? 6) How does NOSMOG perform with different teacher GNNs? 7) How explain the superior performance of NOSMOG?
5.1 EXPERIMENT SETTINGS
Datasets. We use five widely used public benchmark datasets (i.e., Cora, Ci Cisseer, Pubmed, A-computer, and A-photo) (Zhang et al. [20226] Yang et al.) 2021), and two large OGB datasets (i.e., Arxiv and Product s) (Hu et al. 2020) to evaluate the proposed model.
Model Architectures. For fair comparison, we follow the paper (Zhang et al., 2022b) to use GraphSAGE (Hamilton et al. 2017) with GCN aggregation as the teacher model. However, we also show the impact of other teacher models including GCN (Kipf & Welling 2017). GAT (Veličkovid ct al. 2018) and APPNP (Klicpera et al., 2019) in Section [5.]
Evaluation Protocol. For experiments,
report the mean and standard deviation of ten separate with different random seeds. We adopt accuracy to measure the model performance, use validation
data to select the optimal model, and report the results on test data.
Two Settings: Transductive vs. Inductive. To fully evaluate the model, we conduct node classification in two settings: transductive (tran) and inductive (ind). For tran, we train models on G. X and Y while evaluate them on X and Y We generate soft labels for every nodes in the graph (i.e., z, for E V). For ind, we randomly select Specifically, we separate the unlabeled nodes Dd into two disjoint observed and inductive subsets (i.e., Yo = De Li V ( which leads three separate graphs G = LIGU L with no shared nodes. The edges between go Li GV and O are removed during training but are used during inference to transfer position features by average operator (Hamilton et al. (017). Node features and labels are X X
20% test data for inductive evaluation.
partitioned into three disjoint sets, i.e.,
obs U X ind and = Y LJ YU YU generate soft labels for nodes in the labeled and observed subsets (i.e., 2, for v E VL DU
pbs ind" We
5.2
CAN NOSMOG OUTPERFORM GNNS, MLPS, AND OTHER GNNS METHODS?
We compare NOSMOG to GNN, MLP, and the state-of theftthhetttttt method under the standard transductive setting and report the results in Table T which can be directly comparable to those reported in
previous literature (Zhang et al. 2022b Hu et al. 2020 Yang et al. 2021). As shown in Table [
5

---

Published as a conference paper at ICLR 2023
Table 1: NOSMOG outperforms GNN, MLP, and the state-of-the-att method GLNN all datasets under the standard setting. AGNN. AMP., AGLNN represents the difference between the NOSMOG and GNN, MLP. GLNN, respectively. Results show accuracy (higher is better).
Dutascts
SAGE
MLP
GLNN
NOSMOG
ÂGNN
AMLP
AGLNN
Cora
80.64 + 1.57
59.18 + 1.60
80.26
1.66
83.04 1.26
2.98%
10..2%%
3.46%
Ciceseer
70.49 + 1.53
58.50 + 1.86
71.22 + 1.50
73.78
1.54
4..6%%
16.12%
3.59%
Pubmed
75,56 = 2.06
68.39 + 3.09
75.59
+ 2.46
77.34
2.36
f 2.36%
113.0%
1.2.2%%
A-computer
82.82 1 1.37
67.62
2.211
82.71
1.18
84.04
1.01
1.47%
124.28%
1 11.61%
A-photo
90.85 + 0.87
77.29 + 1.79
91.95 + 1.04
93.36
0.69
2.766%
20.799%
f *1.33%
Arxiv
70.73 + 0.35
55.67
0.24
63.75
+ 0.48
71.65
0.29
1.30%
28.70%
112.39%
Products
77.17 1 0.32
60.02
0.10
63.71
1 0.31
78.45
0.38
1.66%
t 30.711%
1 23.14%
NOSMOG outperforms both teacher model and baseline methods on all datasets. Compared to the teacher GNN, NOSMOG improves the performance by 2.46% on average across different datasets, which demonstrates that NOSMOG explicit graph structure input. Compared to MLP, NOSMOG improves the performance by 26.29% on average across datasets, while the state-of-the- method GLNN can only improve MLP by 18.55%, which shows the efficacy of KD and demonstrates that NOSMOG can capture additional information that GLNN cannot. Compared to GLNN, NOSMOG improves the performance by 6.86% on average across datasets. Specifically, GLNN performs poorly in large OGB datasets (the last 2 rows) while NOSMOG learns well and shows an improvement of 12.39% % and 23. 14%, respectively. This further demonstrates the effectiveness of NOSMOG. The analyses of the capability of each model component and the expressiveness of NOSMOG are shown in Sections 5.6 5.8 respectively.
capture better structural information than GNN without
5.3 CAN NOSMOG WORK WELL UNDER BOTH INDUCTIVE AND TRANSDUCTIVE SETTINGS?
To better understand the effectiveness of NOSMOG, we conduct experiments in realistic production (prod) scenario that involves both inductive (ind) and transductive (tran) settings (see Table 2 We find that NOSMOG can achieve superior or comparable performance to the teacher model and baseline methods across all datasets and settings. Specifically, compared to GNN, NOSMOG achieves better performance in all datasets and settings, except for ind on Arxiv and P Products where NOSMOG can only achieve comparable performance. Considering these two datasets have a significant distribution shift between training data and test data (Zhang et al. 2022b). this is understandable that NOSMOG cannot outperform GNN without explicit graph structure input. However, compared to GLNN which can barely learn these two datasets, NOSMOG improves the performance extensively, i.e., 18.72% and 1 11.01% % on these two datasets, respectively. This demonstrates the capability of NOSMOG in capturing graph structural information large-scale datasets, despite the significant distribution shift. In addition, NOSMOG outperforms MLP and GLNN by great margins in all datasets and settings, with an average of 25.15% and 6.39% improvement, respectively. Therefore, we conclude that NOSMOG can achieve exceptional performance in the production environment with both inductive and transductive settings.
5.4 CAN NOSMOG WORK WELL WITH NOISY FEATURES?
Considering that MIP and GLNN are sensitive to feature noises and may not perform well when the labels are uncorrelated with the node content, we further evaluate the performance of NOSMOG with regards to noise levels in Figure 2 Experiment results are averaged across various datasets. Specifically, we add different levels of Gaussian noises to content features by
MLP
GLNN - NOSMOG
Accuracy
50
40
replacing C' with Č (1 a + an, where n represents Gaussian noises that independent from C, and a E [0. 1] incates the noise level. We find that NOSMOG achieves better comparable performance to GNNs across different a, which demonstrates the superior efficacy of NOSMOG, especially when GNNs can mitigate the impact of noises by leveraging information from neighbors and surrounding subgraphs, whereas NOSMOG only relies on content and position features. GLNN and MLP, however,
20
0.2
0.4
0.6
0.8
Noise Level
Figure 2: Accuracy vs. Feature Noises.

---

Published as a conference paper at ICLR 2023
Table 2: NOSMOG outperforms GNN, MLP, and the state-of-the-an method GLNN in a production scenario with both inductive and transductive settings. indicates the results on V tran indicates results on Veran. and prod indicates the interpolated production results of both ind and tran.
Datasets
Eval
SAGE
MLP
GLNN
NOSMOG
AGNN
AMEP
AGLYN
prod 79.53
59.18
77.82
81.02
1 1.87%
36,90%
1 14.11%
Coza
81.03 + 1.71
59.44 + 3.36
73.21 1.50
81.36
1.53
10.41%
36.88%
I 11113%
trn
79.16 + 1.60
59.12 + 1.49
78.97 1.56
80.93 1.65
2.24%
36.89%
1 2.48%
prod 68.06
58.49
69.08
70,60
3.73%
1 2.20% 20.70%
citeseer
ind
69.14 + 2.99
59.31 +: 4.56
68.48 + 2.38
70.30 2.30
f 1.68%
18.53%
1 2.66%
tran
67.79 # 2.80
58.29 + 1.94
69.23 + 2.39
70.67 2.25
1 4.25%
211.2%%
1 2.08%
prod
74.77
68.39
74.67
75.82
t 1.40%
10.86%
I 1.54%
Pubmed
75.07 +: 2.89
68.28 + 3.25
74,52 2.95
75.87
3.32
1 1.07%
11.12%
1 1.81%
74.70 2.33
68.42 4: 3.06
74.70 2.75
75.80 3.06
1.47%
10.79%
1.47%
prod 82.73
67.62 62
82.10
83.85
f 1.35%
24.00%
1 2.13%
A-corputer
ind
82.83 + 1.51
67.69 + 2.20
80.27 + 2.11
84.36 1.57
f 1.85%
24.63%%
t 5.10%
trnn
82.70 + 1.34
67.60 +: 2.23
82,56 + 1.80
83.72 1.44
1 1.233%
23.85%
1 1.41%
prod 90.45
77.29
91.34
92.47
1 2.233%
19.64%
t 1.24%
A-photo
90.56 + 1.47
77.44 + 1.50
89.50 1.12
92.61 1.09
1 2.26%
19.59%
1 3.48%
mrnn
0.68
77:25 + 1.90
91.80 0.49
92.44 0.51
1 2.23%
19.66%
1 0.70%
prod 70.69
55.35
63.50
70.90
0.30%
28.09%
t 11.65%
Asxiv
ind
70.69 + 0.58
55.29 + 0.63
59.04 + 0.46
70.09 0.55
-0.85%
26.77%
t 18.72%
man
770.69 + 0.39
55.36 + 0.34
64.61 + 0.15
71.10 0.34
1 0.58%
28.433%
1 10.05%
prod 76.93
60.02
63.47
77.33
1 0.52%
228.84%
1 21.84%
Products
ind
77.23
+: 0.24
60.02 + 0.09
63,38 0.33
77.02 0.19
J. -0.277%
28.32%
1 11.01%
tan 0.27
60.02 0.11
63.49 0.31
77.41 0.21
0.72%
28.97%
1 21.93%
drop their performance quickly increases. In the extreme case when a equals 1, the input features are completely noises and C and C' are independent. We observe that NOSMOG can still perform as good as GNNs by considering the position features, while GLNN and MLP perform poorly.
5.5 How DOES NOSMOG PERFORM IN TERMS OF INFERENCE TIME?
To demonstrate the efficiency of NOSMOG, we analyze the capacity of NOSMOG by visualizing the trade-off between prediction accuracy and model inference time on Products dataset in Figure 3 We find that NOSMOG can achieve high accuracy (78%) while maintaining fast inference time (1.35ms). Specifically, compared to other models with similar inference time, NOSMOG performs significantly better, while GLNN and MLPs can only achieve 64% and 60% accuracy, respectively. For those models that have close similar performance need a considerable amount of time for inference, e.g., 2 layers GraphSAGE (SAGE-L2) needs 144.47ms and 3 layers GraphSAGE (SAGE-L3) needs 1125,430 43ms, which is not applicable in real applications. This makes NOSMOG 107x faster than SAGE-L2 and 833x faster than SAGE-L3. In addition, since increasing the hidden size of GLNN may improve the performance. we compare NOSMOG with GLNNW4 (4-times wider than GLNN) and GLNNw8 (8-times wider than GLNN). Results show that although GLNNW4 and GLNNw8 can improve GLNN, they still perform worse than NOSMOG and even require more time for inference. We thus conclude that NOSMOG is superior to existing methods and GNNs in terms of both accuracy and inference time.
80
NOSMOG
SAGE-L3
SAGE-L2
GLNNW8
Accuracy
GLNNW4
70-
GLNN
SAGE-L1
60-
MLPs
NOSMOG, they
10'
102
10a
Log Scale Inference Time (ms)
Figure 3: Accuracy Inference Time.
5.6 How DOES NOSMOG PERFORM WITH DIFFERENT MODEL COMPONENTS?
Since NOSMOG contains various essential components (i.e., node position features (POS), representational similarity distillation (RSD), and adversarial feature augmentation (ADV)). we conduct ablation studies to analyze the contributions of different components by removing each of them independently (see Table B). From the table, we find that the performance drops when a component is removed, indicating the efficiency of each component. In general, the incorporation
7

---

Published as a conference paper at ICLR 2023
Table 3: Accuracy of different model variants. The decreasing performance of these model variants demonstrates the effectiveness of each component enhancing model.
Datasets
w/o POS
w/o RSD
w/o ADV
NOSMOG
Aros
A RSD
A ADV
Cora
80.44 + 1.51
82.11 + 1.33
82.43
1.42
83.04 + 1.26
f 3.23%
t 1.13%
0.74%
Cizeseer
73.31 + 1.55
71.61 + 1.84
72.11 = 1.68
73.78 = 1.54
0.64%
13.03%
2..22%
Pubmed
75.55 + 2.54
77.15 = 2.31
77.02 = 2.58
77.34 + 2.36
2.37%
1..25%
00.42%
A-computer
82.94 1: 0.87
84.00 + 1.65
13.15::22
84.04 + 1.01
1.33%
1 10005%
1.07%
A-photo
92.76 +: 0.58
92.97
+ 0.70
92.24
93.36 = 0.69
10.65%
1 1.442%
11.11%
Arxiv
62.69 + 0.64
71.59
+ 0.27
71.53 1 0.30
71.65 = 0.29
14.29%
1 1..08%
0.17%
Products
63.75 + 0.21
78.38
+ 0.36
78.35 + 0.40
78.45
+ 0.38
23.06%
1 0.09%
0.13%
of position features contributes the most, especially on Arxiv and Products datasets. By integrating the position features, NOSMOG can learn from the node positions and achieve exceptional performance. RSD contributes little to the overall performance across different datasets. This is because the goal of RSD is to distill more information from GNN to MLP, while MLP already learns well by mimicking GNN through soft labels. ADV contributes moderately across datasets, given that it mitigates overfitting and improves generalization. Finally, NOSMOG achieves the best performance on all datasets, demonstrating the effectiveness of the proposed model.
5.7 How DOES NOSMOG PERFORM WITH DIFFERENT TEACHER GNNs?
We use GraphSAGE to represent the teacher GNNs so far. However, different GNN architectures may have different performances across datasets, we thus study if NOSMOG can perform well with other GNNs. In Figure we show average performance with different teacher GNNs (i.e., GCN, GAT, and APPNP) across the five benchmark datasets. From the figure, we conclude that the performance of all four teachers is comparable, and NOSMOG can always learn from different teachers and outperform them, albeit with slightly diminished performance when distilled from APPNP, indicating that APPNP provides the least benefit for student. This is due to the fact that the APPNP uses node features for prediction prior to the message passing on the graph, which is very similar what the student MLP does, and therefore provides MIP with little additional information than other teachers. However, NOSMOG consistently outperforms GLNN, which further demonstrates the effectiveness of the proposed model.
GLNN
NOSMOG
Accuracy
80
75
MLP
SAGE
GON
GAT
APPNP
Model
Architectures
Figure 4: Accuracy Teacher GNN Architectures.
5.8 How CAN WE EXPLAIN THE SUPERIOR PERFORMANCE OF NOSMOG?
In this section, we analyze the superior performance and expressiveness of NOSMOG from several perspectives, including the comparison with GLNN and GNNs from information theoretical perspective, and the consistency measure of model predictions and graph topology based on Min-Cut.
The expressiveness of NOSMOG compared to GLNN and GNNs. The goal of node classification task is to fit a function f on the rooted graph glvl with label yı (a rooted graph giv) is the graph with one node v in glvl designated as the root) (Chen et al. 2021). ). From the information theoretical perspective, learning f by minimizing cross-entropy loss is equivalent maximizing the mutual information (MI) QQin et al. 2019)) i.e., ((ltel y.)) If we consider givl as joint distribution of two random variables X and [ld) that represent the node features and edges in Glvl respectively, we have: (gle yu) (x( ;,) = [g((=) y. + (x((),, (gf=)), where 1(giv); ) is the MI between edges and labels, which indicates the relevance between labels and graph structure, and [(x fl, y. gl is the MI between features and labels given edges glul, To compare the effectiveness of NOSMOG, GLNN and GNNs, we start by analyzing the objective of GNNs. For given node v, GNNs aim to learn an embedding function faNN N that computes the node embedding ze. where the objective is to maximize the likelihood of the conditional distribution Ply. approximate I(git); y.). Generally, the embedding function JaNN takes the node features X and its multi- hop neighbourhood subgraph glv] input, which be written g|vl
JaNN((X)) s.
8

---

Published as a conference paper at ICLR 2023
Correspondingly. the process of maxmizing likelihood ((ye can be expressed the process of minimizing the objective function [i(fGN (Xle), yo). Since stel contains the multi-hop neighbours, optimizing L1 captures both node features and the surrounding structure information, which approximating ( [ yo (Efe)) and ((E1));3) yo), respectively.
GLNN leverages the objective functions described in Eq. [ which approximates I(git) yo) by only maxmizing I y.lll")), while ignoring I(El" yo)- However, there are situations that node labels are not strongly correlated to node features, or labels are mainly determined by the node positions or graph structure, e.g., node degrees (Lim et al. 2021 Zhu et al., (021).
In these cases, GLNN won't be able to fit. Alternatively, NOSMOG focuses on modeling both (( yo) and ((X (1); yolgfel) by jointly considering node position features and content features. In particular, [(glo) yu) is optimized by the objective functions L2 (f pl.)) yo) and L3(fMLP (X (-), P(r)), foNN(Xl)) (())) by extending LGT and LSL in Equation g that incorporates position features. Here SMIP the embedding function that NOSMOG learns given the content feature X(1) and position feature ple), Essentially, optimizing L3 forces MLP to learn from GNN's output and eventually achieve comparable performance as GNNs. In the meanwhile, optimizing L2 allows MLP to capture node positions that may not be learned by GNNs, which is important if the label ye is correlated to the node positional information. Therefore, there is no doubt that NOSMOG can perform better, considering that ye is always correlated with glel in graph data. Even in the extreme case that when Yr is uncorrelated with T(X [o); ye [g|")), NOSMOG can still achieve superior comparable performance to GNNs, as demonstrated in Section [54
The consistency measure of model predictions and graph topology. To further validate that NOSMOG is superior to GNNs, MIPs, and GLNN in encoding graph structural information, we design the cut value CV [0, 1] measure the consistency between model predictions and graph topology (Zhang et al.) (0226). based on the approximation for the min- cut problem (Bianchi et al.) 2019). The min-cut problem divides nodes V into K disjoint subsets by removing the minimum number of edges.
Table 4:
The cut value. NOSMOG predictions are more consistent with the graph topology than GNN, MLP, and the of-te- art method GLNN
Datasets
SAGE
MLP
GLNN
NOSMOG
Cora
0.9385
0.7203
0.8908
0.9480
Citeseer
0,9535
0.8107
0.9447
0.9659
Pubmed
0,9597
0.9062
0,9298
0.9641
A-computer
0.8951
0.6764
0,8579
0.9047
A-photo
0.9014
0.7099
0,9063
0.9084
Arxiv
0,9052
0.7252
0.8126
0.9066
Products
0,9400
0.7518
0.7657
0.9456
Correspondingly,
Average
0.9276
0.7572
0.8725
0.9348
the min-cut problem can be expressed as: max 1 Σ
where C is the node class assignment, A is the adjacency matrix, and D is the degree matrix. Therefore, we design the cut value follows: (tr(tt("TDD'
Ek=1( (CT AC&)/(CT,
k
where Y the model prediction output, and the cut value CV indicates the consistency between the model predictions and the graph topology. The bigger the value is, the predictions are more consistent with the graph topology, and the model is more capable of capturing graph structural information. The cut values for different models in transductive setting are shown in Table 4 We find that the average CV for NOSMOG is 0.9348, while the average CV for SAGE, MLP, and GLNN are 0.9276, 0. 0.7572, and 0.8725, respectively. We conclude that NOSMOG achieves the highest cut value, demonstrating the superior expressiveness of NOSMOG in capturing graph topology compared GNN, MIP, and GINN
CV = tr
6 CONCLUSION
In this paper, we address three significant issues of existing GNNs-MLPs frameworks and present unified view of learning MIPs with effectiveness, robustness, and efficiency. Specifically, we propose to learn Noise-robust and Structure-aware MLPs on Graphs (NOSMOG) that considers position features, representational similarity distillation, and adversarial feature augmentation. Extensive experiments seven datasets demonstrate that NOSMOG can improve GNNs by 2.05%. MLPs by 25.22% % and the state-of-the aat method by 6.63%, meanwhile maintaining a remarkable robustness and fast inference speed of 833x compared to GNNs. Furthermore, present additional theoretical analyses as well as empirical investigations of robustness and efficiency to demonstrate the superiority of the proposed model.

---

Published as a conference paper at ICLR 2023
REFERENCES
Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Mincut pooling in graph neural networks. arXiv preprint arXiv: (at1::9970.000 1,000, 2019.
Lei Chen, Zhengdao Chen, and Joan Bruna. On graph neural networks versus graph-augmented mlps. In ICLR, 2021.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In ICML., 2020.
Prasenjit Dey, Kaustuv Nag. Tandra Pal, and Nikhil R Pal. Regularizing multilayer perceptron for robustness. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2017.
Zhichun Guo, Chunhui Zhang, Yujie Fan, Yijun Tian, Chuxu Zhang, and Nitesh Chawla. Boosting graph neural networks via adaptive knowledge distillation. In AAAI, 2023.
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Geoffrey Hinton, Oriol Vinyals. Jeff Dean, et al. Distilling the knowledge in a neural network. arXiv preprint XXXv:15533.025:1111 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. NeurIPS, 2020.
Yang Hu, Haoxuan You, Zhecan Wang. Zhicheng Wang, Erjin Zhou, and Yue Gao. Graph-mlp: node classification without message passing in graph. arXiv preprint arXiv:2106.0405/ 2021.
Ziyu Jiang, Tianlong Chen, Ting Chen, and Zhangyang Wang. Robust pre-training by adversarial contrastive learning. In NeurlPS, 2020.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Kezhi Kong, Guohao Li, Mucong Ding, Zuxuan Wu, Chen Zhu, Bernard Ghanem, Gavin Taylor, and Tom Goldstein. Flag: Adversarial data augmentation for graph neural networks. In CVPR, 2022.
Guohao Li, Mathias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In ICCV, 2019.
Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non- homophilous graphs. In WwW, 2021.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In ICLR, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. representations. In KDD, 2014.
Deepwalk:
Online learning of social
Mary Phuong and Christoph Lampert. Towards understanding knowledge distillation. In ICML, 2019.
Zhenyue Qin, Dongwoo Kim, and Tom Gedeon. Rethinking softmax with cross-entropy: Neural network classifier mutual information estimator. arXiv preprint arXiv: 106888, 2019.
10

---

Published as a conference paper at ICLR 2023
Yijun Tian, Chuxu Zhang. Zhichun Guo, Yihong Ma, Ronald Metoyer, and Nitesh V Chawla. Recipe2vec: Multi-modal recipe representation learning with graph neural networks. In IJCAI, 2022.
Yijun Tian, Kaiwen Dong, Chunhui Zhang, Chuxu Zhang, and Nitesh Chawla. Heterogeneous graph masked autoencoders. In AAAI, 2023a.
Yijun Tian, Shichao Pei, Xiangliang Zhang, Chuxu Zhang, and Nitesh V Chawla. Knowledge distillation on graphs: A survey. arXiv preprini arXiv:2302.002 2023b.
Frederick Tung and Greg Mori.
knowledge distillation. In ICCV, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua
Bengio. Graph attention networks. In ICLR, 2018.
Dilin Wang, Chengyue Gong, and Qiang Liu. Improving neural language modeling via adversarial training. In ICML, 2019.
Haorui Wang, Haoteng Yin, Muhan Zhang, and Pan Li. Equivariant and stable positional encoding for more powerful graph neural networks, In ICLR, 2022.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. comprehensive survey graph neural networks. IEEE transactions neural networks and learning systems, 2020.
Cihang Xie, Mingxing Tan, Boqing Gong, Jiang Wang, Alan L Yuille, and Quoc V Le. Adversarial examples improve image recognition. CVPR, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR, 2019.
Bencheng Yan, Chaokun Wang, Gaoyang Guo, and Yunkai Lou. Tinygnn: Learning efficient graph neural networks. KDD, 2020.
Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and beyond it: An effective knowledge distillation framework. In WWW, 2021.
Yiding Yang. Jiayan Qiu, Mingli Song. Dacheng Tao, and Xinchao Wang. Distilling knowledge from graph convolutional networks. In CVPR, 2020.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-awe aware graph neural networks. ICML, 2019.
Chunhui Zhang, Chao Huang, Yijun Tian, Qianlong Wen, Zhongyu Ouyang, Youhuan Li, Yanfang Ye, and Chuxu Zhang. Diving into unified data-model sparsity for class-imbalanced graph representation learning. arXiv preprint
2022a.
Chunhui Zhang, Yijun Tian, Mingxuan Ju, Zheyuan Liu, Yanfang Ye, Nitesh Chawla, and Chuxu Zhang. Chasing all-round graph representation robustness: Model, training, and optimization. In ICLR, 2023.
Chuxu Zhang, Dongjin Song. Chao Huang, Ananthram Swami, and Nitesh V Chawla. Heterogeneous graph neural network. In KDD, 2019.
Dalong Zhang, Xin Huang, Ziqi Liu, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Zhiqiang Zhang, Lin Wang, Jun Zhou, Yang Shuang, et al. Agl: A scalable system for industrial-purpose graph machine learning. arXiv preprint arXiv:2003. 024554 2020.
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mips new tricks via distillation. In /CLR, 2022b.
Wenqing Zheng, Edward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete or missing neighborhoods. ICLR, 2022.
11

---

Published as a conference paper at ICLR 2023
Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. Al Open, 2020.
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. Graph neural networks with heterophily. In AAAI, 2021.
12


Reviews:
[{"review_id": "y7q90x6KV0", "reviewer": "Reviewer_8WF2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work deals with the knowledge distillation between the GNNs and MLPs from the perspectives of effectiveness and the robustness, and proposes a method NOSMOG to learn structure aware and noise robust MLP. For effectiveness, NOSMOG uses position encoding to capture graph structure information and combines it with original node content information for training MLP, along with the representation similarity distillation term. Moreover, adversarial training technique is introduced to address the robustness.\n", "summary_of_the_review": "This work explores to the practical issues of structure infomation incorporation and noise-robustness in transfering knowledge from GNNs to MLP, and correpsonding solutions are fair reasonable and the effectiveness can be verified. however, there are still some parts to be further clarified and explained in the 'weakness' part above.\n", "strength_and_weaknesses": "strength\n\n(1) this work explores the structure information and noise-robustness in knowledge distillation between GNNs and MLPs, which is a practical issue of this task for real-world applications. Specifically, structure information incorporation is a beneficial component for learning graph-structure data.\n\n(2) the experimental parts are relatively comprehensive for illustrating the effectiveness of the proposed method. And some theoretical analysis, e.g., the information theory aspect, can support the claims of authors to some extent.\n\n\nweakness:\n\n(1) the solutions of this work for structure information capture with position encoding and noise robustness of adversarial training is straightforward, might limiting the novelty of this work.\n\n(2) here are some questions and concerns required to be addressed:\n\na. in the inference stage of the trained MLP, is the node positional information also taken as the input together with the node content features? if so, compared with GLNN, additional information is used, so the performance improvement is a natural result. And whether the deepwalk time is counted in the inference time comparison in figure3? \n\nb. it seems like the positional encoding features are only used in the L_GT and L_SL loss parts? are they also considered in the MLP representations HM for L_RSD loss and L_ADV loss？ if only in L_GT and L_SL, why do not utilize the positional encoding features for the remain components as the structure infomation of graphs is very important? if used for all loss terms, how to understand the performance in \"w/o POS\" in table 3 by removing each of them independently? \n\nc. for the ablation study part, what about the ablation performance for only with the POS features? and what about the performance of NOSMOG without L_adv in figure 2? that would be a baseline result for verifying the performance of L_adv with nosiy features\n\nd. except for feature dimensions, is there any other factors affecting the performance of POS? for example different encoding method? the scale of graphs? Consider the core of transfering knowledge from GNNs to MLPs is addressing the the scalability constraint under the multi-hop data dependency, would such structure information encoding also limit by the scalability?\n\ne. for RSD part, why imposing extra transformation W in the the MLP representations HM? is this part kept in the inference? and according to my understanding, in eq.(3) S_gnn and S_mlp are both calculated with dot product? why it denotes the intra-model representational similarity ? what is the meaning of the intra-model similarity?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "mFpx2Qferm", "reviewer": "Reviewer_iP1i", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work addresses three issues that current MLPs on graph methods have: 1) the misalignment between content feature and label spaces, 2) the strict hard matching to the teacher’s output, and 3) the sensitivity to node feature noises. In particular, this paper presents NOSMOG, a novel method to learn MLPs with remarkable effectiveness, robustness, and efficiency. Extensive experiments and theoretical analyses demonstrate the superiority of NOSMOG by comparing it to GNNs and state-of-the-art methods.", "summary_of_the_review": "The paper address three challenges of learning MLPs on graphs by designing a novel and effective model. The technical statements are sound, the theoretical explanations are rigorous, and the empirical results are impressive. ", "strength_and_weaknesses": "Strengths:\n\n+ The motivation for training student MLPs with teacher GNNs is interesting and important in practice. In addition, the authors identify and address three critical issues, which make the work applicable and significant in real-world cases. Really good motivation, especially since the graph datasets are becoming larger and scalability is becoming a pressing challenge.\n\n+ The idea is compelling and the proposed model is somewhat novel. The authors present three components to address each identified problem correspondingly. The introduced components are simple yet effective. The overall model structure is well-designed. In the meantime, the model facilitates efficient inference, while achieving superior and robust performance.\n\n+ This paper conducts extensive experiments and comprehensive ablation studies to evaluate the proposed model. For example, the authors compare both transductive and inductive settings, noisy input features, and different teacher architectures. The model is tested on multiple datasets and shows very promising results. The proposed model demonstrates state-of-the-art results across different settings and various scales of datasets. The results are remarkable and superior to other methods, which also suggests that NOSMOG can be very useful in practice from both performance and applicability perspectives. In addition, the authors open-source their implementation.\n\n+ The authors provide a theoretical understanding of the model, which is sound. The theoretical statements in this paper look correct to me. The authors develop theoretical insights and build a theoretical basis for the proposed model, which I think is valuable.\n\nWeaknesses and Questions:\n\n- Some technical details are not elaborated for those readers who are less familiar with the respective topics. For example, the section on the consistency measure is quite brief. For better readability, I would suggest the authors provide more information such as how the cut value indicates and measures the consistency between model predictions and graph topology.\n\n- Based on Table 3 in the ablation study, it seems that the POS contributes the most, especially on large graph datasets such as Arxiv and Products. I wonder what the performance looks like if only POS is used, instead of using all the components. Will the model variant have a similar or close performance to NOSMOG when it comes to large graph datasets? \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "hobVUAF19Mo", "reviewer": "Reviewer_yeLS", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This work extends a recent approach to train MLPs with teacher GNNs to produce models capable of performing well on relational data while preserving low inference latency by omitting belief propagation. To motivate the paper, the authors identify two major limitations to existing MLPs trained with GNNs 1) loss of positional/structural information from the graph as the MLPs only take node content features as input 2) lack of robustness to node content perturbations. \n\nTo address these limitations the authors propose augmentations to the “graph-less” MLP training pipeline. The three augmentations are 1) concatenating node position embeddings (graph embeddings0 to the node content features for MLP input 2) representational similarity distillation such that the pairwise relationships between hidden representations of training nodes are preserved in the MLP compared to the GNN 3) training on adversarial samples for which the node content features are perturbed but the node labels remain untouched. \n\nThe authors provide extensive experimental results that show the performance of their augmented MLP on transductive and inductive node classification tests. The results show that the augmented graph-less MLP (named NOSMOG) outperforms the teacher GNN in most cases as well as the current SOTA graph-less MLP (GLNN). The ablation study shows that the first augmentation (node embeddings) most improves performance. ", "summary_of_the_review": "The paper presents a unified approach to address the limitations of current graph-less MLPs, a recent approach favored for faster inference latency, and overall extends the capabilities of knowledge distillation from GNNs to MLPs. The three augmentations are clearly explained and the experimental results are very thorough, showing the effectiveness of each component under various testing environments. The main limitation of the paper currently is greater insight into why the augmentations address the motivating limitations of graph-less GNNs and whether these augmentations themselves are robust. Specifically, the node position embeddings are the most important augmentation, as shown in the ablation study, but is unclear whether the MLP is invariant to symmetric operations on the node position embeddings when the graph is re-embedded at test time. Further, the theoretical explanation in section 5.8 would benefit from better quantifying the mutual information associated with the graph structure. ", "strength_and_weaknesses": "Pros \n* The authors are able to address limitations of current graph-less MLPs in a united system. Further the system (NOSMOG) is introduced clearly and each component is well explained. \n* The experimental results are thorough and show the effectiveness of NOSMOG. The authors conduct evaluations in multiple settings (transductive vs inductive), run an ablation study, and test the robustness of using various teacher GNNs.\n\nCons\n* Concatenating the node position features (embeddings) is a critical component of NOSMOG (contributes the most to an increase in accuracy), but the paper does not specifically discuss the process of re-embedding the graph during the testing phase and the impact of re-embedding the graph. For example, for the transductive setting, is the graph re-embedded at test time or are the embeddings for unlabeled nodes carried over from the training phase? Assuming re-embedding, it is possible that the re-embedded node positions are rotations or translations of the embeddings generated during training. It would be helpful to discuss whether NOSMOG is invariant to these operations on the node position embeddings during the test phase. \n* Since many node position embeddings themselves are generated with GNNs today, it would be helpful to compare the performance of using non-message passing embeddings (i.e. the current DeepWalk embeddings) vs message passing embeddings. If NOSMOG improves with the message passing embeddings it would be helpful to discuss the tradeoff between latency and accuracy. \n* Finally, the explanation of NOSMOG’s effectiveness in section 5.8 is quite abstract and I am not sure the discussion adds to the paper. As is the section largely repeats the justifications for incorporating the node position features in the first place. To improve the section it would be helpful to quantify the term $I(E^{[v]}; y_v)$ under certain modeling assumptions. \n\nMinor comments\n* Should one of the embedding matrices in equation 3 be transposed so that S is a gram matrix? \n* I am assuming the MLP in equation 7 takes concatenated perturbed content features and node position embeddings as input though currently it only takes the content features. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "emrPEuxhEkp", "reviewer": "Reviewer_44NK", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes to learn MLPs on graphs to address the scalability issue while maintaining effectiveness, robustness, and efficiency. Specifically, the authors identify three significant challenges and propose a novel method NOSMOG. Furthermore, the authors provide theoretical analyses and conduct extensive experiments to demonstrate the superiority of the proposed model.", "summary_of_the_review": "The results and findings in this paper are insightful and would be useful for future research. The paper is also well-written with solid theoretical exposition and strong results. Overall, this is a good paper.", "strength_and_weaknesses": "Strengths:\n1. The problem is well-motivated, interesting, and important. The deployment of GNNs in real-world applications poses a fundamental scalability issue for the machine learning community. This paper addresses this scalability issue by training MLPs from GNNs, resolves three critical and pressing challenges that current methods have, and proposes a novel method to address the problems.\n\n2. The authors present a not-complicated model with a strong capability to address the problems. Three key components are designed to learn an effective, robust, and efficient MLP. The proposed model can fully capture graph structure information in both the feature and representation spaces. In the meantime, the model is insensitive to node feature noises, with superior performance and fast inference speed. The proposed method is relatively novel to me. \n\n3. The performance improvement is significant. The authors conduct extensive experiments and design thoughtful research questions to demonstrate the superiority of NOSMOG. For example, the proposed model can outperform the state-of-the-art by 12% to 23% on two large-scale OGB datasets.\n\n4. The authors analyze the model expressiveness from 1) the information theoretical perspective and 2) the consistency measure of model predictions and graph topology based on Min-Cut. The authors explain well why the proposed model is better. The theoretical analyses are convincing.\n\n5. The results and the claims are reproducible. The paper is well-written.\n\n\nWeaknesses:\n\n1. Descriptions on selecting the hyper-parameters can be introduced. In addition, considering the success of the proposed model relies on various hyper-parameters. Will the model be sensitive to different parameter values?\n\n2. Additional background knowledge can be introduced for utilizing the min-cut problem to measure consistency.\n\n3. Consistency measures for structure-only methods such as DeepWalk can be demonstrated for a comprehensive comparison. In particular, for Table 4, I am curious about the difference between the proposed method (that considers both content and structure) and DeepWalk which only considers the structural information.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: notable-top-25%