Fully-inductive Node Classification on Arbitrary Graphs

We thank the reviewer for acknowledging the merits of our work. Below, we would like to comment on the identified weaknesses and answer your questions.

W1. Lack of baselines that generalize to more datasets.

We agree with the reviewer that some LLM-based approaches can generalize to new datasets based on text descriptions. However, this paper aims to study a more fundamental setting of generalizing across datasets purely based on arbitrary continuous features and categorical labels. LLM-based approaches can’t fit into this challenging setting, since most datasets don’t have text descriptions in our experiments.

While GCN and GAT seem to be not strong enough, we additionally consider stronger baselines that work well for both homophilic and heterophilic datasets, including ACM-SGC and ACM-GNN [Luan et al., 2022]. As shown in Table 6, GraphAny achieves better or comparable performance using much less computational resources (a detailed discussion is provided in Appendix E.2).

W2 and Q1: Comparison of GraphAny against a fixed combination of 5 LinearGNN components.

We thank the reviewer for the feedback. We have those results in Figure 9 actually (although not explicitly discussed). The transductive results at batch 0 (green line) are the requested random-initialization result, which are much worse than the final performance of GraphAny.

Besides, we provide additional results in Figure 10, where GraphAny is compared with the baseline that averages all the predictions (denoted as MeanAgg). It is obvious that GraphAny consistently outperforms the baseline MeanAgg by a significant margin, demonstrating the necessity of learning the coefficients rather than using fixed ones.

Q2: Any insight why LinearSGC1 and LinearSGC2 tend to get higher weights.

Your observation that LinearSGC1 and LinearSGC2 are the most effective graph convolution kernels is correct. This finding aligns with the standard homophily assumption, which suggests that connected nodes are likely to share similar labels, making simpler convolutional kernels like LinearSGC1 and LinearSGC2 particularly effective in such settings.

Regarding transferability, we believe that simpler graph kernels might exhibit stronger inductive generalization due to introducing less inductive bias. This reduced bias allows these kernels to generalize better to new graphs. However, it is important to note that these simple kernels might also have less expressive power and, hence, weaker transductive performance, as they may not fully fit the complex distributions during training. Therefore, we believe that there exists a potential tradeoff for designing inductive graph models: one might need to balance transductive performance (specialized for a specific graph) and inductive generalization (transferability to new graphs).

Reference

[Luan et al., 2022] Revisiting Heterophily For Graph Neural Networks. NeuriPS 2022.

We thank the reviewer for acknowledging the merits of our work. Below, we would like to comment on the identified weaknesses.

W1. LinearGNN is a data preprocessing method.

Yes, your understanding is correct. We recognize LinearGNN as a fast and solvable solution for node classification, which enables GraphAny’s inductive inference without training. We don’t think this is a weakness, since GraphAny learns inductive attention scores to combine predictions from multiple LinearGNNs.

W2. Any model that can be solved analytically is fully-inductive. GraphAny is overclaimed.

Fully-inductive not only implies inference on any graph, but also generalization to new graphs. We would like to highlight that LinearGNNs, and other GNNs with solvable weights actually yield a transductive function $f=\mathbb{R}^{d} \rightarrow \mathbb{R}^c$ and cannot generalize to any new datasets with different feature and label spaces that require $f’=\mathbb{R}^{d’} \rightarrow \mathbb{R}^{c’}$.

By contrast, the function $f_\theta: \mathbb{R}^{t(t-1)} \rightarrow \mathbb{R}^t$ learned by GraphAny operates on a fixed dimension input regardless of the dataset, and thereby generalizes to new datasets. Hence, GraphAny should be considered as fully-inductive.

W3. A recent work, GraphControl, is also fully-inductive.

Thank you for bringing the recent related work on GraphControl to our attention. We have reviewed this work and acknowledge its relevance. However, GraphControl is still a transductive model with the pre-training-fine-tuning pipeline, which cannot transfer to new graphs with different label spaces. For example, the graph-prompt features and the output layer for prediction must be learned end-to-end for a new graph task. In contrast, we focus on the more challenging fully-inductive setting, where the model must generalize to unseen graphs without additional training. Therefore, the presence of this related work does not diminish the unique contribution of GraphAny. We’ve also updated the manuscript and discussed GraphControl in the related work session.

W4. Provide the data split ratios for test datasets.

We thank the reviewer for the comment and updated the dataset split ratio in Table 3. It’s noteworthy to highlight that we did not tweak the dataset training ratio to make our results look better. We strictly follow the splits of the original data source (e.g. DGL and PyG) if they exist. For those that don’t provide splits, we follow the standard semi-supervised settings (20 labeled nodes per class for training and the same amount of data for valid and test sets).

W5. GraphAny has an advantage over the setting of semi-supervised learning, not in the opposite way.

We respectfully disagree with your claim that GraphAny has an additional advantage over the semi-supervised training baselines. The ways where semi-supervised models and GraphAny use training labels are totally different: semi-supervised models use training labels to perform gradient descent, while GraphAny only uses training labels for inference, without changing any of its parameters. We emphasize that semi-supervised models have to train 31 separate models (with 31 different sets of hyperparameters) in order to perform inference on 31 datasets. By contrast, GraphAny only trains 1 model using 1 dataset and can perform inference on 31 datasets. Since semi-supervised models additionally leverage the training labels to tune parameters and the validation sets to search hyperparameters, they are supposed to have an advantage over GraphAny.

Besides, your understanding of LinearGNNs is correct, they do rely on the training labels of the inductive datasets to perform training-free inference.

Here, we discuss the proposed questions:

Q1. How to get the attention scores?

We don’t sum up the $P_u^{t}$ in the Equation 10 to obtain the attention score. The $P_u(i,j)$ is a dimension of the entropy-normalized feature for the attention function. As explained in Section 3.3, The learnable weights of GraphAny is the inductive attention module$f_\theta: \mathbb{R}^{t(t-1)} \rightarrow \mathbb{R}^t$, which computes the attention score for fusing LinearGNN predictions based on their interactions.

Q2. Experimental settings in Figure 5.

The experiments in Figure 5 illustrate the probability distribution of different features for inductive attention. Specifically, we compare the distributions between Euclidean distances (the first row) and entropy-normalized (the second row) features between five channels: $\boldsymbol{F} = \boldsymbol{X}$ (Linear), $\boldsymbol{F} = \bar{\boldsymbol{A}} \boldsymbol{X}$ (LinearSGC1), $\boldsymbol{F}=\bar{\boldsymbol{A}}^2 \boldsymbol{X}$ (LinearSGC2), $\boldsymbol{F}=(\\boldsymbol{I}-\bar{\boldsymbol{A}}) \boldsymbol{X}$ (LinearHGC1) and $\boldsymbol{F} = (\boldsymbol{I} - \bar{\boldsymbol{A}})^2 \boldsymbol{X}$ (LinearHGC2) with $\bar{\boldsymbol{A}}$ denoting the row normalized adjaceny matrix. The density means the estimated density of the empirical distribution function based on the observed distribution of distances/features. The Euclidean distances are computed by features normalized to unit length, the entropy-normed features are normalized via dynamically determining the sigma for each node (check the explanation under equation 10).

Q3. Why transductive models are cheating?

Please refer to our response to W3.

Reference

[Luan et al., 2023] Revisiting Heterophily For Graph Neural Networks. NeurIPS 2023.

We sincerely thank the reviewer for pointing out areas of improvement for our paper. Below, we address each of the identified weaknesses:

W1. Many methodology details are missing

W1.1 We sincerely thank the reviewer for the constructive feedback on the experimental settings of Figure 5. We’ve updated the caption of Figure 5 to make it clear and self-contained.

W1.2 The attention vector $\alpha$ is predicted by the attention module $f_\theta$ based on the entropy-normalized features, as shown in the bottom right of Figure 3. In practice, we implement $f_\theta$ as an MLP and all the learnable parameters are the parameters of that MLP, as stated in line 330-334.

W1.3 We thank the reviewer for pointing this out. We call $\hat{y}_u^{(i)}$ node features because they serve as input to our inductive attention module for node $u$. We understand this slightly abuses the term “node features” used in node classification. To distinguish $\hat{y}_u^{(i)}$ against $X$, we have revised to call $\hat{y}_u^{(i)}$ “features for inductive attention”.

W2: LinearGNNs are not non-parametric since they involve a learnable weight matrix W.

By non-parametric, we refer to having no learnable parameters. Although LinearGNNs do have weights (which we solve analytically through the pseudoinverse), they are not learnable. Besides, it is noteworthy to point out that the LinearGNNs are still transductive models that do not transfer any knowledge across graphs, whereas GraphAny learns inductive functions of LinearGNNs predictions that can generalize to unseen graphs without additional training.

W3 and Q3: Why are transductive models cheating in the fully-inductive setting?

For the standard transductive setting, separate models with different sets of parameters and hyperparameters are trained for different datasets. In fully-inductive settings, one set of parameters is trained for different datasets and generalize to new graph without additional training. That said, transductive models cannot perform fully-inductive inference in the first place as the input and output spaces vary. However, the transductive models can be viewed as strong baselines for inductive models: as they leverage unobserved validation sets of inductive data to optimize parameters when training the model (e.g. optimizer, learning rate, dropout ratio, number of epochs) and tuning hyperparameters (e.g. selecting the depth of graph convolutions).

As mentioned in Section 3.3 and our responses in W1.2, GraphAny is a fully-inductive model, which does not model the input and output spaces and learns to fuse different predictions. Once trained, the learned inductive attention $f_\theta: \mathbb{R}^{t(t-1)} \rightarrow \mathbb{R}^t$ is ready to generalize to arbitrary graphs.

W4. GAT outperforms GraphAny on 18 out of 31 datasets. First, as we have mentioned in our response to W3, it is unfair to compare a fully-inductive model to a transductive model like GAT as transductive models are trained on known labeled nodes and leverage validation sets to select hyperparameters for each of the 31 datasets. GraphAny runs inference on all new unseen graphs outside its small training set (eg, training on Wisconsin and running inference on 30 other graphs). Nevertheless, even in the fully-inductive setting, GraphAny outperforms several transductive baselines.

To further ease your concerns, we added two recent baselines, ACM-SGC and ACM-GNN [Luan et al., 2022], which have good homophilic and heterophilic performance. As shown in Table 6, GraphAny achieves better or comparable performance using much less computational resources (a detailed discussion is provided in Appendix E.2).

W5. How does the different values of t influence the performance of GraphAny? We thank the reviewer’s advice and have added the ablations on t in Appendix E.1. As shown in Figure 10, for different graph convolution operators, such as LinearGNNs, Chebyshev polynomials, and personalized page rank, increasing t has diverse effects. For LinearGNNs, increasing t and adding low-pass graph convolutions (LinearSGC1 and LinearSGC2) significantly enhance performance. In contrast, for Chebyshev graph convolutions, adding high-order convolutions reduces performance. For personalized PageRank, adding more local channels consistently improves results.

We thank the reviewer for the constructive feedback. Below we would like to comment on the identified weaknesses.

W1. Why can GraphAny transfer to unseen graphs?

Above all, the proposed distance features capture the node-level message-passing pattern and infer the optimal attention for fusing LinearGNN predictions. Here we give an intuitive example: We know that LinearSGC2 is a good prediction channel for homophilic graphs and MLP is a good channel for heterophilic graphs (Figure 7 left). Hence, for an unseen graph, a logical guess would be to assign higher attention weights to LinearSGC2 if the graph displays homophilic properties. From Figure 5, we observe that homophilic and heterophilic information can be inferred from the entropy-normalized features (bottom row), where homophilic graphs like Cora, Arxiv, and FullCora exhibit similar patterns. These message-passing patterns are leveraged by GraphAny to predict inductive attention scores.

Moreover, it is important to note that our inductive attention operates at the node level, as specified in Equation 5. This means that even given an unseen graph with new structure/feature/label spaces, as long as the node of interest exhibits distance feature patterns akin to those of a node in a previously observed graph, GraphAny will likely assign similar attention weights. Luckily, even when training on one small graph, say Wisconsin with 120 nodes, there might be sufficiently diverse node-level message passing patterns, as observed in [Luan et al., 2022]. This enables the remarkable transferability of GraphAny to transfer to unseen graphs even trained on one dataset.

W2. Insights on why GraphAny fails on some datasets and how to improve it.

The reason why GraphAny doesn’t outperform transductive baselines on some datasets is that GraphAny is evaluated in a more challenging inductive setting. Specifically, the transductive models have additional advantages compared with GraphAny by leveraging unobserved validation sets of inductive data to optimize parameters when training the model (e.g. optimizer, learning rate, dropout ratio, number of epochs) and tuning hyperparameters (e.g. selecting the depth of graph convolutions).

Second, one limitation of GraphAny is that to achieve training-free inference, we leverage LinearGNNs with analytical solutions but with limited expressivity. As a consequence, the performance is bounded by the linear combination of those LinearGNNs. There are several straightforward solutions to improve the performance of GraphAny, though all at the cost of breaking the fully-inductive assumption. One possible solution is to relax this constraint and train transductive non-linear models first and learn how to combine their predictions using the interactions between them. Although sacrificing the training-free property of GraphAny, this should give a better transductive performance, especially for those datasets with complex non-linear patterns.

W3. Comparison against strong baselines that consider both homophily and heterophily. Following the reviewer’s suggestion, we included the required ACM-GNN [Luan et al., 2022] as a baseline due to its good performance on both homophilic and heterophilic graphs. However, ACM-GNN faces scalability issues that prevent its application to large graphs. Using the authors’ implementation, we encountered out-of-memory for a GPU of 40GB on four large datasets: Questions, Reddit, Arxiv, and Product. This prevents us from adding ACM-GNN to our main table. Hence, we evaluated ACM-GNN on the remaining 27 graphs, with results reported in Table 6.

Our observations are as follows: Tuning ACM-GNN is highly time-consuming, requiring 672 GPU hours on 27 graphs, while GraphAny requires only 4 GPU hours (168× more efficient), showcasing its efficiency and the advantage of inductive inference. In terms of performance, GraphAny outperforms ACM-SGC and is only slightly (1-2%) below ACM-GCN. However, this slight difference is not a significant disadvantage for GraphAny, given the unfair advantage transductive models have by leveraging the inductive validation sets for parameter and hyperparameter tuning, as well as the substantial difference in runtime.