When Do MLPs Excel in Node Classification? An Information-Theoretic Perspective

We thank the reviewer for the insightful comments and constructive suggestions. Below are our answers to the weaknesses and questions.

W1: Claims in Section 3.1 are not well justified.

The data generation process behind our assumption.

The conclusion in Section 3.1 is indeed based on an assumption of graph-structured data generation. Specifically, our hypothesis posits that for a graph $G = (X, A)$, its generation process involves generating raw node features X for the nodes, and the graph structure A is generated based on the node features and additional confounder factors. This assumption is adopted by the research in the study of generative models for graphs [1]. In addition, many real-world graphs can be considered to be generated based on this assumption. For example,

• Citation networks: Consider citation networks where the node features are the raw text of papers, and the edges represent citation relationships. In this case, we can hypothesize that the textual content of papers is generated first. Then, based on the content of the papers and authors' actions, citation relationships are formed.
• Social networks: Consider social networks where the node features are user profiles, including attributes like occupation and interests, and the edges represent friendship relationships. We posit that users are initially generated with their individual attributes. Subsequently, friendship relationships are formed among users based on shared interests, real-world interactions, and other factors.

Therefore, our assumption regarding the generation process of graph data is reasonable. Based on this assumption, we provide the analysis in Section 3.1. We will provide a detailed explanation of this assumption in the revised paper.

The balanced stochastic block model.

The first example provided by the reviewer, on the one hand, does not align with the generation process we consider for graph-structured data. On the other hand, this synthetic dataset is too specific and may not represent real-world graph datasets. Furthermore, in the examples provided by the reviewer, it cannot be demonstrated that MLPs can achieve the same performance as GNNs. The reviewer seems to consider only the transductive setting, where all the nodes (including the testing nodes) are involved in the training process. However, in the inductive setting, once testing nodes are not involved in the training process, for a new testing node with features represented as one-hot IDs, the MLP model clearly cannot make correct predictions, while the GNN model can easily classify it based on which block it belongs to

We are comparing the generalization ability of MLP and GNN.

Regarding the second point, we are indeed considering the generalization ability of MLP, and we appreciate the reviewer's input. In fact, the expressive power of MLP can hardly be enhanced because its input information and MLP's structure are fixed. The reason why GNN performs so well in semi-supervised learning is largely due to its utilization of graph structural information to enhance its generalization ability to non-training data, as mentioned in recent literature [2].

The performance of $X' = [X, A]$ under MLP classifiers.

Thanks for the suggestions. We agree with the reviewer that our claim needs to be empirically verified. Therefore, we follow the reviewer's suggestions and try learning an MLP classifier over the augmented node features $X' = [X, A]$. In addition, we can consider other simpler examples. On the one hand, SGC can be seen as an MLP model that takes the convoluted node features as input, and in this case, SGC has achieved performance similar to GNN. On the other hand, we can also use node structural embeddings (e.g., derived from DeepWalk) as an additional input for the MLP. In the table below, we provide the performance using the reviewer's example $X' = [X, A]$, as well as the performance with structural embeddings as input for the MLP model:

As presented in the table, various approaches that use structural information as input for MLPs can enable them to achieve performance comparable to GNNs.

We appreciate the constructive criticism provided by the reviewer regarding Section 3.1 of our paper. The feedback has allowed us to better introduce the background and implications of our research. We hope that our response addresses your concerns.

References:

[1] Ma, Jiaqi, et al. "A flexible generative framework for graph-based semi-supervised learning." NIPS 2019.

[2] Yang, Chenxiao, et al. "Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs." ICLR. 2023.

Q1: Theorem 1: Why the equality can hold.

If $\hat{A} = f(X)$ is a fully free function, the equality can be obtained when $H(X|\hat{A}) = 0$, since we can simply let $\hat{A} = X$ (when $N = d$) or let $\hat{A} = {\rm concat}(X, 0)$ (when $N > d$). We understand the reviewer's concern might be that the above formulation of $\hat{A}$ is very special and unusual, while we think $H(A|X) = \inf\limits_{f}H(A|\hat{A})$ is more accurate. (The equation suggested by the reviewer is correct as well)

Q2: Testing time of SGC

The training/testing time of SGC includes the graph convolution step and, therefore, is larger than other MLPs. If we view the graph convolution as a preprocessing step (which is reasonable), the training/testing time will be the same as MLPs. We've revised it in the updated paper, and thanks a lot for pointing it out.

Q3: Comparison of the performance of $Z_{\rm aug}$ and $Z_{\rm mlp}$

Thank you for the valuable comments. The sentence you pointed out is a typo, and has been revised to be "Furthermore, the node embeddings $Z_{\rm mlp}$ are utilized to predict the node labels". In fact, $Z_{\rm aug}$ cannot be directly compared to $Z_{\rm mlp}$ because in our model, the cross-entropy loss for downstream classification tasks is applied to $Z_{\rm mlp}$ rather than $Z_{\rm aug}$. To meet the reviewer's request, we independently trained a classification model based on $Z_{\rm aug}$. In the table below, we provide the performance obtained with $Z_{\rm aug}$ in the transductive setting and compare it to $Z_{\rm mlp}$.

As we can see, $Z_{\rm aug}$ generally performs worse on these datasets compared to $Z_{\rm mlp}$. We suspect that this is because the regularization loss employed by InfoMLP not only helps $Z_{\rm mlp}$ learn graph structural information but also includes a decorrelation loss, which encourages different dimensions of the embedding to be relatively independent. This, in turn, helps $Z_{\rm mlp}$ to obtain an embedding space that is more distinguishable and beneficial for classification.

Furthermore, since $Z_{\rm aug}$ itself utilizes graph structural information as an input to the encoder, it is natural that it can achieve good performance when node features alone do not contain sufficient graph structural information. For example, on the Arxiv dataset, $Z_{\rm aug}$ effortlessly achieved a classification accuracy of $70.82\pm 0.16$.

W2: Gap between $H(A|X)$ and $H(A|\hat{A})$

The gap between $H(A|X)$ and $H(A|\hat{A})$ is determined by how the function $\hat{A} = g(X)$ is formulated. Since $|H(A|X) - H(A|\hat{A})| = I(X;A|\hat{A}) = I(X;A) - I(X;A;\hat{A}) = {\rm const} - I(A;\hat{A})$. We cannot provide a specific bound because the constant value $I(X;A)$ is non-tractable. Luckily, since we do not care about the absolute value between the gaps, we can resort to the mutual information between the original graph adjacency matrix and the estimated graph structure matrix $\hat{A}$, i.e., $I(A;\hat{A})$ for reference. To be detailed, to make this bound tighter, we only need the estimated adjacency matrix to be very close to the true adjacency matrix.

We choose the $\ell_2$ distance primarily motivated by the well-known graph homophily theory, which suggests that nodes with similar features are more likely to be connected than nodes with dissimilar features. Therefore, the $\ell_2$ distance between two nodes based on their features can, to some extent, be used to infer whether two nodes are connected.

The greatest advantage of this approach is that $g(X)$ is non-parametric, so it can be used as a plug-and-play method for any dataset without the need to train a separate model. Even with such a simple formulation, it is already sufficient to capture the graph structure information and the correlation between node features in graph datasets. It can also explain why MLP-typed models exhibit drastically different performance on different graph datasets, as presented in Table 2 and Figure 2. For instance, on datasets with smaller $H(A|\hat{A})$ (e.g., Cora, Citeseer, Pubmed, and Coauthor-CS), the performance of MLP-typed models is evidently closer to powerful GNN models than datasets of larger $H(A|\hat{A})$ (e.g., Amazon-Computer).

W3: Empirical results on large graphs are not satisfying

Thank you for carefully checking our results on the large graphs. Our response is divided into two parts: 1) The suboptimal performance of InfoMLP on some large-scale graphs is due to the significant information gap between node features $X$ and the graph adjacency matrix $A$. 2) MLP-typed methods have an unparalleled advantage over GNNs in cold-start scenarios.

The suboptimal performance of InfoMLP on some large-scale graphs is due to the significant information gap between $X$ and $A$.

Critically, the suboptimal performance of InfoMLP is not caused by the large graph size but by the information gap between node features and graph structures, which is endemic to the quality of data. At the end of Section 3.2, we have concluded three representative cases of the scale of $H(A|\hat{A})$. The third case (large $H(A|\hat{A})$) has pointed out that when the node features $X$ fail to contain adequate information about the graph structure $A$, the performance of the MLP model can hardly be improved to the level of GNNs. This is the common case for large-scale graphs since $N\times N \gg N \times d$ when $N$ is large while $d$ is small. For example, Arxiv is a citation network with over 160k nodes, while the node attributes consist of 128-dimensional encoded features from raw textual features using skip-gram. The resulting information gap endemic to the data hampers the ability to train an MLP model with enough expressive power comparable to GNNs.

The empirical results in Figure 5, Appendix E.4, in the original paper also support our arguments. As depicted in Figure 5, the pos/neg distributions are heavily overlapped, leading to large conditional entropy $H(A|\hat{A})$. It is precisely because the node features $X$ do not contain enough information to recover the graph structure $A$ that MLP-typed methods fail to compete with GNNs

MLP-typed methods have an unparalleled advantage over GNNs in cold-start scenarios.

As explained in the second paragraph of Sec. 1, our study is motivated by addressing the two-fold limitations of conventional GNNs: 1) the efficiency issues and 2) the challenges in achieving good performance in cold-start scenarios. While it is true that shallow GNNs can partially alleviate the first issue, they are less preferable than MLPs in cold-start scenarios. We conducted additional experiments on Reddit and Arxiv datasets for cold-start scenarios and presented the results in the table below.

Compared to the results in the transductive scenario, GCN experiences a significant performance drop in the cold-start scenario, falling far behind our InfoMLP. So, we believe that even though our proposed InfoMLP may not be as competitive as GNNs in some datasets in the transductive scenario, its advantages in the cold-start scenario demonstrate its value.

We appreciate the reviewer's insightful comments and suggestions for improvement. However, we also noticed that some of the questions might arise from a potential misunderstanding of the setting studied by our paper. We address these points in the following answers.

W1 & W2: Not good results in standard datasets (e.g. Cora).

We'd like to first clarify upfront the three different experimental settings we considered, where in each case, the models should be compared in different manners given their different input information.

1. In the transductive setting, all nodes and edges are observed during both the training and testing phases.
2. In the inductive setting, testing nodes and their related edges are unobserved during training but are accessible when testing.
3. Cold-start setting is an extreme case of the inductive setting, wherein the edges related to the testing nodes are inaccessible during testing as well. (We call it cold-start setting since this is similar to the cold-start recommendation problem where the historical interactions are inaccessible for new users)

These different settings pose different levels of learning difficulties for GNN-based and MLP-based approaches since both model classes use different information as input. Let $X_{train}$ and $X_{test}$ be the training/testing node attributes, and let $E_{train}$ and $E_{test}$ be the edges related to the training and testing do, respectively. The following tables compare the observed information for two model classes.

Based on the experimental settings, we next illustrate how our achieved results serve to validate the effectiveness of our model.

Table 3 in our paper presents the results for transductive setting (where MLP and GNN use the same information), and the proposed InfoMLP significantly outperforms all GNN baselines in such a setting.

Table 4 in our paper reports the results for inductive and cold-start settings. Please notice the differences between these two settings. In the inductive setting, GNNs can leverage additional information ($E_{\rm test}$ during the testing phase) over MLP-based models, which allows GNN to utilize the connection information of testing nodes. Hence, it is natural for GNN to outperform the MLP model in the inductive setting. But for cold-start settings, as shown in Table 4, our proposed InfoMLP yields significant improvements.

To sum up, when both model classes use the same input information and are compared in a fair setting, our InfoMLP exhibits clear superiority.

Q3: Entropy estimation is very terse (positive vs negative distribution).

Thank you for the constructive suggestion. To ensure our results are interpreted in a precise way, we'd like to point out the difference between the estimated values of $H(A|\hat{A})$ (in the titles of Figure 2) and the divergence of positive/negative edge distribution. The calculation method of the conditional entropy $H(A|\hat{A})$ used in this paper is rigorously derived through the definition of conditional entropy (see Equation 1 and Appendix D in the submitted paper). It is merely in the derivation process that we found its calculation is closely related to the positive/negative edge distributions. Therefore, the plotting of distributions in Figure 2 is only an illustrative representation.

We agree with the reviewer's suggestion that computing the numerical metrics for measuring the distance between two distributions can add value to our paper. Therefore, we add new experiments calculating the relative entropy (KL-divergence) to measure the difference between the distributions of positive edges and negative edges. The table below shows the difference between the distributions of positive edges and negative edges measured by KL-divergence.

A larger KL-divergence value indicates a more significant difference between the two distributions. As expected, the KL-divergence values exhibit a clear negative correlation with the estimated values of $H(A|\hat{A})$ in Figure 2, which is consistent to our results. E.g., Computer dataset has the largest $H(A|\hat{A})$ while the smallest $\mathcal{D}\_{kl}(A|\hat{A})$. By contrast, CS dataset has the smallest $H(A|\hat{A})$ while the largest $\mathcal{D}_{kl}(A|\hat{A})$.

Q1: How critical is the augmented representation?

The graph-augmented node feature matrix $X_{\rm aug}$ plays an important role in the proposed InfoMLP, since we aim to minimize $H(A|X_{\rm aug})$ such that $X_{\rm aug}$ contains enough information about the graph structure. In our paper, we assume $X_{\rm aug} = g(X, A) = \sum\limits_{k=1}^K \gamma_k \tilde{A}^{k}X$, and for simplicity we let $\gamma_k = 1/K$. In this way, we only need to tune $K$ to obtain a proper $X_{\rm aug}$.

In Figure 3 of the original paper, we studied the impacts of different instantiations of $X_{\rm aug}$ on InfoMLP's performance by adjusting $K$. Our observation is that there is a positive correlation between InfoMLP's performance and $H(A|X_{\rm aug})$ estimated by our estimators. Additionally, we observe that when $K=1$, $H(A|X_{\rm aug})$ is in general, larger (and InfoMLP has suboptimal performance). However, as $K$ increases to 2 and beyond, $H(A|X_{\rm aug})$ quickly converges to smaller values, and at this point, InfoMLP's performance also approaches the optimum. This indicates that, for the graphs studied in Figure 3, combining the information of 2-5 order neighborhoods with node attributes is sufficient for $X_{\rm aug}$ to reconstruct the original graph structure $A$.

In addition, we supplement more discussions on the impact of $\gamma_k$ on the performance of InfoMLP. We let $\gamma_k = \alpha(1-\alpha)^k$ such that the definition of $X_{\rm aug}$ recovers the classical Personalized PageRank embeddings[1]. This specification leads to the property that with increasing $K$, the weight of each hop is $(1-\alpha)$ times the weight of the previous layer, thereby gradually reducing the importance of higher-order neighbors when $0 < \alpha < 1$. We let $\alpha_k = 0.2$, and present the performance of InfoMLP on Cora dataset in the transductive setting w.r.t. to $K$ in the table below.

We have similar observations and results as in Figure 3. This indicates that InfoMLP can adapt to different instantiations of $X_{\rm aug}$.

Q2: How critical is the MI simplified loss?.

Thanks for the nice suggestion that can help to improve our work. The Rényi estimator is indeed an important method for measuring mutual information between two variables. However, as shown in Equation 3, our learning objective is to maximize $I(Z_1, Z_2)$, which will be used to update the model's trainable parameters. This requires the MI estimator to be differentiable for backpropagation. Unfortunately, the Rényi estimator does not meet this requirement, making it unsuitable for our context.

In addition to the loss used in this paper, based on the reviewer's suggestion, we supplement new experiments with the InfoNCE MI estimator [2] and the Mutual Information Neural Estimator (MINE) [3]. They have both been proven to have lower bounds on MI[4], making it suitable as the learning objective (the MI can maximized by maximizing the estimator). In the following table, we present the mean accuracy of InfoMLP with these estimators:

The InfoNCE MI estimator provides competitive performance as the feature-decorrelation-based loss used in our paper (even better on some datasets), while MINE in general, yields inferior performance. This is because MINE has a very large variance in MI estimation, which results in less accurate estimates (see discussions in [4]). Although InfoNCE provides strong results, its computational complexity is O(N^2d), which makes it time and memory-consuming to calculate the InfoNCE loss on medium-sized graphs. Considering these, we use the estimator, which is efficient and produces competitive results in our paper.

References:

[1] Gasteiger, Johannes, Stefan Weißenberger, and Stephan Günnemann. "Diffusion improves graph learning." Advances in neural information processing systems 32 (2019).

[2] Oord, Aaron van den, Yazhe Li, and Oriol Vinyals. "Representation learning with contrastive predictive coding." arXiv preprint arXiv:1807.03748 (2018).

[3] Belghazi, Mohamed Ishmael, et al. "Mutual information neural estimation." International conference on machine learning. PMLR, 2018.

[4] Poole, Ben, et al. "On variational bounds of mutual information." International Conference on Machine Learning. PMLR, 2019.

We thank the reviewer for the constructive comments and insightful suggestions.

What are the differences between $Z_{aug}$ and $Z_{mlp}$? The term "ideal" node representation is vague; a more rigorous definition might be needed here.

Differences between $Z_{\rm aug}$ and $Z_{\rm mlp}$

$Z_{\rm mlp}$ and $Z_{\rm aug}$ are the embedding matrix outputted from the same encoder MLP model, while with the different input information. Specifically, let ${\rm MLP}\_{\theta}$ be the MLP encoder parameterized by $\theta$, $Z_{\rm mlp}$ is ${\rm MLP}\_{\theta}$'s output using the raw node features as input, e.g., $Z_{\rm mlp} = \rm{MLP}\_{\theta} (X)$, while $Z_{\rm aug}$ is ${\rm MLP}\_{\theta}$'s output using the graph-augmented node features as input, e.g., $Z_{\rm aug} = \rm{MLP}\_{\theta} (X_{\rm aug})$. Since $X_{aug}$ is defined as a function of both the vanilla node features and the graph adjacency matrix, i.e., $X_{\rm aug} = g(X, A)$, $Z_{\rm aug}$ naturally encodes the graph structure information into the embeddings, while $Z_{\rm mlp}$ does not.

A more rigorous definition of "ideal" node representations

The term "ideal" node representations in the beginning of Section 3.3 refers to the node representations that, given the conditions presented in Figure 1, would perform satisfactorily in downstream tasks. To improve the clarity, we have updated the description "the node representations that are expected to perform well in downstream tasks given the condition depicted in Figure 1" in the revised paper.

The maximization of $H(A|X)$ is not clear, I can only see a non-parametric mapping that somehow fuses the representation of $X$ and $A$ together into a single representation. However, there is no guarantee nor intuitive explanation of why and how $X_{\rm aug}$ maximizes $H(A|X)$.

Thanks for the question. The reviewer should be referring to the minimization of $H(A|X_{\rm aug})$ (rather than maximization). The minimization of $H(A|X_{\rm aug})$ is achieved via tuning the optimal $\gamma_k$ and K in Equation 2. We provide a detailed explanation below.

Since $X_{aug}$ is defined as the function output of the vanilla node features $X$ and the graph adjacency matrix $A$, i.e., $X_{\rm aug}(X, A)$, we can formulate the optimization problem as

$$\min\limits_{X_{\rm aug}} H(A|X_{\rm aug}) = \min\limits_{g}H(A|g(X,A)).$$

However, the search space for $g$ is very large, as $g$ can be any function. Therefore, we choose to reduce the searching space for g using the form of Eq. 6, which is the popular graph diffusion mechanism for aggregating multi-hop neighborhood information.

$$g(X, A) = X_{\rm aug} = \sum\limits_{k=1}^K \gamma_k \tilde{A}^kX .$$

In this way, the optimization problem is transformed into selecting the optimal $K$ and $\gamma_k$ such that $H(A|X)$ is minimized, which is much easier to solve.