Graph is a Natural Regularization: Revisiting Vector Quantization for Graph Representation Learning

Vector Quantization (VQ) has recently emerged as a promising approach for learning compressed and discrete representations for graph-structured data. However, a fundamental challenge, i.e., codebook collapse, remains underexplored in the graph domain, significantly limiting the expressiveness and generalization of graph tokens. In this paper, we present an empirical study and observe that codebook collapse consistently occurs when training VQ jointly with Graph Neural Networks under graph reconstruction tasks, even with mitigation strategies proposed in vision or language domains. Moreover, we provide a diagnosis of collapse from data and optimization perspectives, showing that collapse is associated with graph data properties such as feature redundancy and connectivity density, and is further reinforced by the training dynamics of deterministic hard assignment. To address these issues, we propose RGVQ, a novel framework that integrates graph topology and feature similarity as explicit regularization signals to enhance codebook utilization and promote token diversity. RGVQ introduces soft assignments via Gumbel-Softmax reparameterization, ensuring that all codewords receive gradient updates. In addition, RGVQ incorporates a structure-aware contrastive regularization to penalize assigning the same token to dissimilar node pairs. Extensive experiments demonstrate that RGVQ substantially improves codebook utilization and consistently boosts the performance of state-of-the-art graph VQ backbones across multiple downstream tasks, enabling more expressive and transferable graph token representations.

Graphs, like social networks, molecular structures, or recommendation systems, are everywhere, but teaching computers to understand them is tricky. One way to simplify graphs is to summarize them as a set of “tokens,” similar to words in a sentence. However, most existing methods can only make use of a few tokens and ignore the rest, making the computer’s understanding coarse and incomplete. We studied why this happens and proposed a new method that encourages computers to make full use of all tokens. It considers both how nodes are connected and how similar they are, and then summarizes graphs in a "soft" way so every token can be considered during training. The result is that computers can now create richer and more flexible representations of graphs. This helps them learn faster, adapt knowledge from one graph to another, and capture subtle relationships. In practice, this could improve anything from social network analysis to drug discovery by making graph-based machine learning smarter and more reliable.