Node Identifiers: Compact, Discrete Representations for Efficient Graph Learning

W1, W2, Q1, Q2 & Q7: Interpretability of Node IDs

The interpretability of the discrete representations of NID is not discussed in detail in the paper.

What is the interpretation of your discrete representations?

Thank you for highlighting the importance of discussing the interpretability of discrete node IDs.

Please note that we addressed this in Section 4.2 ("Qualitative Analysis"), where we demonstrate the interpretability of node IDs using the PubMed dataset. We would like to offer further explanation here.

Node IDs serve as high-level abstractions of multi-level GNN embeddings and can be considered as categorical labels of varying granularity for the nodes. For each node in the PubMed dataset, we learn a 6-dimensional ID ($c_{11},c_{12},c_{13},c_{21},c_{22}, c_{23}$), where $c_{11},c_{12},c_{13}$ are derived from the first-layer GNN embeddings, and $c_{21},c_{22}, c_{23}$ are derived from the second-layer GNN embeddings. Figure 5 illustrates the distributions of $c_{11}$ and $c_{21}$, which are the principle component codes generated by the first-tier RVQ.

The distributions of $c_{11}$ and $c_{21}$ indicate that nodes with the same codes generally belong to the same class. For instance, nodes with $c_{11}=10$ are mostly in the third class (label 2), and nodes with $c_{21}=4$ all belong to the third class. This demonstrates that the codes effectively function as categorical labels. Meanwhile, the distribution of $c_{21}$ is more concentrated, with only 5 values, compared to $c_{11}$, which takes on all 16 values. This is due to the cumulative smoothing effect of deeper GNN layers, leading to $c_{21}$ exhibiting more concentrated clustering patterns. Therefore, $c_{11}$ can be seen as fine-grained categorical labels, while $c_{21}$ can be considered more coarse-grained labels.

What does it mean by “share similar 1-hop structures” in line 71 in the description of Figure 1? Why node in case A&B, C&D have similar 1-hop structure? What is the definition of so-called similar 1-hop structures? It is vague.

Thank you for your thoughtful question, and we apologize for the confusion. To clarify, we have replaced the term "1-hop structure" with "1-hop neighborhood" in the caption of Figure 1 to ensure better understanding.

In Figure 1, the first ID code is derived from the first-layer GNN embeddings, and the second ID code is derived from the second-layer GNN embeddings. Thus, two nodes sharing the same first ID code suggests that they have similar first-layer GNN embeddings, which are computed by aggregating the features of their 1-hop neighbors.

A&B, C&D, E&F are three examples that illustrate how nodes with the same first ID code may share "similar 1-hop neighborhoods," which refers to nodes that have comparable 1-hop topology and similar distributions of labels (or features) among their immediate neighbors.

For nodes E and F, the 1-hop neighborhoods are identical. Nodes A and B have 1-hop neighbors that all share the same green label and exhibit a similar star topology. Similarly, nodes C and D have 1-hop neighbors with green and purple labels in comparable proportions, and these neighbors share a similar, though not identical, topology.

However, nodes with the same first ID code do not necessarily belong to the same class, as demonstrated by the case of E&F, which have different second ID codes.

Let’s extend the first question, so if two nodes have exactly the same second ID code in the figure 1 (but the first ID code is different), does that mean they have “similar 2-hop structures”? If yes, how can they have similar 2-hop structures on the basis of totally different 1-hop neighbors? Which neighbors of the 1-hop neighbors should be considered? If no, what does the same second ID code mean in that case?

Similarly, two nodes sharing the same second ID code suggests that they have similar second-layer GNN embeddings, which are calculated by aggregating the features of neighbors within their 2-hop neighborhood.

We provide two examples in Appendix E.3 that illustrate cases where two nodes share the same second ID code but have different first ID codes.

Nodes G and H have different first ID codes because, despite sharing a similar 1-hop topology, they differ in the label distribution of their 1-hop neighbors. However, they exhibit a similar 2-hop topology and similar label distributions among their 2-hop neighbors, which results in the same second ID code.

Nodes I and J have different first ID codes due to differences in both their 1-hop topologies and the label distributions among their 1-hop neighbors. Nevertheless, their 2-hop neighbors share similar label distributions, leading to the same second ID code, even though their 2-hop topologies are not as similar as those of nodes G and H.

This suggests that the second ID code primarily captures the similarity in the broader 2-hop neighborhood, considering both label distribution and graph topology.

Dear Reviewer aCEA,

We sincerely appreciate your thoughtful, positive, and constructive feedback. We apologize for any confusion that may have arisen from ambiguity in our expression. We hope that the clarification provided below will resolve any misunderstandings and enhance your confidence in our work.

Q3: Defintion of $M$

The definition of the M is vague. What does M mean in the size of codebook L*M?

$M$ refers to the number of levels/tiers in Residual Vector Quantization (RVQ). As stated in lines 175-177, we employ RVQ to quantize the node embeddings and produce $M$ tiers of codes for each node $v$, using $M$ distinct codebooks. Also see lines 128-134 in the updated version. The RVQ process for $L \times M$ codebooks is elaborated in Appendix E.1, where $L$ represents the number of MPNN layers. For the node embeddings produced by each MPNN layer, an $M$-level RVQ is performed. In the training objective (Eq.8), the quantization loss is aggregated across all the $L \times M$ codebooks.

W3, Q4 & Q6: Code Vectors vs. Node IDs

The introduction of codebook seems useless since the codeword is used in neither loss of VQ nor loss of tasks.

If by "codeword" you are referring to code vectors from the codebook, they are indeed integral components of the loss functions. As detailed in Equation 8, the differentiable VQ loss, $L_{VQ}$, is designed to optimize the code vectors ($\mathbf{e}\_{lm}$) and the GNN node embeddings ($\mathbf{r}\_{lm}$) simultaneously. When training is completed, the node IDs (indices of corresponding code vectors) are generated by quantizing the GNN node embeddings using the optimized codebook. Without a well-optimized codebook, meaningful node IDs cannot be generated.

If you refer to "codeword" as the indices of the code vectors, we call them node IDs (see lines 159, 160, and 184). Although these node IDs are not part of any loss functions and are not directly learned through optimization, the codebooks (i.e., the code vectors within them) are optimized. As analysed in Section 3.3, with effectively optimized codebooks, desired performance can be achieved by using the node IDs.

In subsection 3.2, the paper says that the Node_ID of each node will be sent into the MLP network, but my question is are you sending the id like “2341” (eg. 4-layer encoder) as the node representation into the MLP network? Why don’t you send the corresponding codeword into the MLP network? I know that code vectors are not used for a reconstruction task, so I am here talking about the downstream tasks.

For the argument in box 4.1, as I say, why directly use IDs as representations instead of corresponding vectors in the codebook?

Your understanding is correct: we use the indices, rather than the code vectors, to train MLPs for downstream tasks. However, it is also possible to use the corresponding code vectors for these tasks, as is common in most compression and quantization methods. These code vectors can perform similarly to the original GNN embeddings, as they have the capability to nearly fully reconstruct the GNN embeddings.

The unique contribution and novelty of our work lies in demonstrating that the indices (node IDs), which are short (mostly 6-15 dim) and discrete (int4 type), can perform competitively with, and sometimes even better than, the original GNN embeddings. It is surprising, yet not unreasonable, that these node IDs are not involved in any loss functions and not directly learned through optimization. This is because the code vectors within codebooks are optimized. Additionally, in Section 3.3, we provide a theoretical analysis to demonstrate the validity of this method. By employing a widely adopted graph data formulation, we prove that the optimized codebook can effectively distinguish nodes. As a result, we can achieve the desired classification performance by using the indices of the corresponding code vectors to train a linear layer.

This finding has significant implications. It suggests that node IDs can serve as effective high-level abstractions of graph data, revealing substantial redundancy in GNN embeddings and providing a level of interpretability that GNN embeddings lack (see further analysis below). This insight may inspire future research in graph tokenization and facilitate graph applications with LLMs.

Dear Reviewer w4zV,

We sincerely appreciate your valuable feedback and recognition of our contributions. We hope our response below will further enhance your confidence in our work.

W1: Potential Loss of Information

The quantization of node embeddings into discrete node IDs may result in the loss of important structural information, as nuanced variations in node characteristics could be oversimplified into a single codeword.

This is a valid point. Our approach may lead to some information loss, as the quantized node represenations are highly compact and discrete. Our theoretical and empirical analyses demonstrate that these representations can preserve essential information in GNN embeddings while reducing redundancy, potentially offering a high-level abstraction userful for various downstream tasks. As Reviewer K2Gp noted, "as a VQ paper, the goal is not to really 'beat' anything – just do more with less."

Interestingly, this abstraction can sometimes exceed the performance of the base GNNs, as demonstrated in Table 1 with heterophilic datasets and in Table 5's attributed graph clustering tasks. This phenomenon is intriguing and warrants further exploration.

W2 & Q1: Computational Complexity of Joint Training

The framework necessitates joint training of the GNN and vector quantization components, which raises concerns about increased time complexity. The authors should provide an analysis of this complexity, particularly focusing on the impact of joint training on computational efficiency and scalability with larger datasets.

How does the joint training of the GNN and vector quantization components affect the overall computational efficiency, especially when scaling to larger datasets?

We appreciate your suggestion. In fact, we already analyzed the computational complexity of the joint training of the GNN and vector quantization components in Appendix E.2. There, we compared the training time per epoch of our $\text{NID}_\text{SAGE}$ with standard SAGE on the largest dataset used in our experiments, ogbn-products, which contains 2,449,029 nodes. The results show that the training time of our NID model (5.9s) is comparable to that of standard SAGE (5.8s), indicating minimal computational overhead from our vector quantization components.

Following your suggestion, we have also performed additional experiments on another two large-scale datasets, ogbn-proteins and pokec, to further evaluate the efficiency of our approach. The results below confirm that our method scales efficiently without significant increases in computational demands.

Dear Reviewer k2Gp,

We sincerely appreciate your careful reading and attention to detail. Your positive comments are truly encouraging. We understand your concern regarding the surprisingly high results of vanilla GNNs, and we would like to address this.

W1, W2 & Q1: Clarification of Experimental Result

Egregious experimental result reuse raises a number of inconsistencies for the few methods the authors have recomputed.

Its difficult to place the results in context with the related work (ie the Polynormer paper results).

The core issue is that in this paper you show weak methods (e.g. GCN) performing well on datasets. Lets take Photos for example. In Polynormer, GCN is the weakest method (92%). In your paper, GCN is the strongest method (96%). This could be because you did a better grid search (good!) but if you don't similarly do a great grid search for the other baselines then I don't trust them at all :)

It makes it very hard understand how your method compares at all to the baselines. (As a VQ paper the goal is not to really "beat" anything -- just do more with less)

Firstly, we would like to address the misconception that basic GNNs, such as GCN, are inherently weak models. Recent benchmarking research [1] demonstrates that classic GNNs, including GCN, GAT, and SAGE, are actually strong models that can compete with or even surpass the latest state-of-the-art graph transformers (e.g., SGFormer or Polynormer) in node classification, when tuned within the same hyperparameter search space. This suggests that the performance of basic GNNs has been significantly underestimated due to suboptimal hyperparameter tuning.

As stated in lines 355-357 of our manuscript, we follow the experimental settings outlined in [1], as they match the hyperparameter search space used in the Polynormer paper. This approach ensures consistency and fair comparison, avoiding conducting a more extensive grid search for GNNs than for other models like Polynormer.

To further resolve your concern, we have also retrained Polynormer using the same hyperparameter search space outlined in [1] on our devices. The results align with those reported in [1], as detailed in the table below. This reaffirms our conclusion that NID performs competitively with SOTA methods on both homophilic and heterophilic graphs.

[1] Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification, NeurIPS 2024 Datasets and Benchmarks Track.

Dear Reviewer k2Gp,

We are pleased to provide an update addressing your concerns. We have retrained all baseline models in supervised node classification over homophilic and heterophilic graphs, including GPRGNN, APPNP, SGFormer, and Polynormer, using the same hyperparameter tuning search space and training environment as those employed for our NID model. This ensures fair and equitable comparisons across all methods. The retrained results are presented in the table below.

Based on the updated results, we believe it is reasonable to conclude that NID performs competitively with SOTA methods on both homophilic and heterophilic graphs.

Thanks to the authors for running additional experiments. It generally resolves my concerns and I have raised my score accordingly.

However, I must respectfully disagree about the goodness of GCN and GAT. They are fundamentally weak models. The survey you mention modifies the architectures significantly to address these weaknesses (which is good -- but not relevant to your paper since I suspect you did not perform similar modifications.).