G-SPARC: SPectral ARchitectures tackling the Cold-start problem in Graphs

Thank you for recognizing the significance of our work, the versatility of our proposed method, the rigor of our experiments, and the clarity of our writing. We also sincerely appreciate the insightful questions you raised. Below are our detailed responses to your questions:

Q1a) We appreciate the suggestion to compare with graph structure learning methods like [a1] and have reviewed the work. While graph structure learning can enhance nodes with limited connections, it assumes some connectivity information in addition to feature similarity, which does not address the cold-start problem we focus on—nodes with no connectivity information. Our work (Line 495) shows the limitations of feature-based methods that ignore adjacency, as seen in Figure 6. The results indicate that relying solely on features for predictions leads to performance variability across datasets, making this approach unsuitable for addressing the cold-start node problem in datasets where graph structure plays a larger role.

Q1b) The use of spectral embeddings is rooted in well-established spectral theory, which is mathematically designed to capture the underlying graph structure. Rather than learning arbitrary node representations, spectral embedding enforces a direct connection to the graph's intrinsic structure. Our framework ensures that the embeddings are meaningful to capture the graph structure and also suitable for various tasks such as node classification, node clustering, and link prediction when integrated into a graph learning method.

Q2) Our current focus is on showcasing how the SPARC framework integrates with two graph learning models—Spectral-GCN and NAGphormer. These examples highlight the flexibility of SPARC, which integrates with existing architectures. SPARC is designed to be model-agnostic, meaning its spectral embedding can be easily incorporated into any graph learning method. The core innovation of our framework is its ability to transition nodes into a spectral embedding that captures the graph structure, allowing generalization to cold-start nodes. This embedding is directly applicable for predicting the neighborhoods of cold-start nodes, which can then be used for all graph learning methods that use the node neighbors. While our current experiments focus on Spectral-GCN and NAGphormer, the SPARC embedding can be effortlessly integrated into other methods like Difformer, as well as future advances in graph learning.

Q3a) We acknowledge this gap and agree that including more baselines specifically tailored to cold-start scenarios would strengthen our comparisons. However, we found that such baselines are surprisingly scarce in the literature. This observation further underscores the novelty and importance of our contribution to this underexplored area of graph learning. In addition, G-SAGE and C-BREW are introduced in the related work section.

Q3b) Thank you for pointing out the results in Table 6. The observed degradation in performance for non-cold-start nodes is a consequence of the experimental setup. Specifically, the results reflect the accuracy of node classification on non-cold-start nodes when the model is trained on an incomplete graph (i.e., excluding cold-start node links during training).

We thank the reviewer for their thoughtful and detailed feedback. We appreciate their recognition of the strengths of our method and their valuable suggestions, which have helped us identify areas for further clarification and improvement.

C1.The scenario described, where node features are random or based on mean values, is different from the type of cold-start problem our method addresses. Our focus is on nodes with meaningful features but no connections, which is a common setting in graph learning. Also in recommendation systems, the cold-start problem often involves new items or users that come with associated information but lack connections, rather than nodes initialized with entirely uninformative features.

C2. This is an excellent and highly relevant point, particularly in the context of the cold-start scenario, where graph structures are often subject to dynamic changes. While our proposed method is not explicitly designed to handle dynamic graphs in its current form, we recognize the importance of this challenge and its relevance to real-world applications. One potential approach to extending our method for dynamic graphs is to leverage the evolving graph structure—specifically, newly added or removed edges—as an additional signal for learning. This can be achieved by incorporating a dynamic link prediction loss into the finding of /mathcal{F}. The idea would be to use the spectral embeddings produced by our method to predict the presence of edges and compute a loss by comparing these predictions with the actual changes in the graph structure. This additional loss would allow the model to adapt its spectral embeddings in response to dynamic changes, potentially enhancing its robustness to evolving graph properties. Although this direction is beyond the scope of our current work, it represents an exciting avenue for future research, with the potential to address dynamic graph learning and strengthen the applicability of spectral methods in such scenarios. We appreciate this insightful observation and believe it highlights an important opportunity for further development.

C3. In the current version, we primarily focus on convergence behavior as a measure of computational efficiency. While the spectral embedding computation involves an eigen-decomposition step, which can be computationally intensive, we mitigate this through efficient approximations, particularly for large graphs. We will ensure that these trade-offs are explicitly detailed in the final version of the paper. In Figure 4, we isolated the graph to evaluate the "quality" of the mini-batches, which aligns with our intention to continue exploring this approach for parallel training. Furthermore, our parametric map that learns the spectral embedding of nodes is not only generalizable but also faster than other eigendecomposition techniques. Both models, Spectral-GCN and NAGphormer, use eigendecomposition in their architectures: Spectral GCN employs the Laplace operator, while NAGphormer utilizes positional encoding, making the preprocesses comparable across the datasets used.

C4. Thank you for pointing this out. We appreciate your careful attention to detail and for bringing this to our attention. This paper will be publicly published soon, and we’ll change the citation accordingly.

C5. We acknowledge this gap and agree that including more baselines specifically tailored to cold-start scenarios would strengthen our comparisons. However, we found that such baselines are surprisingly scarce in the literature. This observation further underscores the novelty and importance of our contribution to this underexplored area of graph learning.

Thank you for your thoughtful review, we appreciate you found our paper clear, with strong motivation, and comprehensive experiments. We also appreciate your constructive feedback these insights are invaluable for improving our approach. Below are our detailed responses to your questions:

Q1. Handling directed graphs and asymmetric relationships is undoubtedly important, but it is not a common requirement in graph learning. A significant portion of research in this field focuses on undirected graphs, which are both highly relevant and widely studied across various domains. Our proposed method aligns with the majority of the papers in graph learning.

Q2. As the percentage of cold-start nodes is very high, such as 50%, the graph structure becomes significantly sparse. In such scenarios, the connectivity within the graph diminishes, leading to a substantial loss of structural information. Consequently, the graph effectively transitions from a structure-based representation to a feature-based one, with limited connections between nodes to propagate meaningful information. It is important to note that in real-world cold-start scenarios, the percentage of cold-start nodes is typically not this large. For instance, in social media platforms, where cold-start problems are prominent, the fraction of new users introduced at any time is often much smaller. Our experiments and analysis in the paper primarily focus on cold-start percentages that align with these realistic scenarios, demonstrating the effectiveness of the proposed method under practical conditions.

Q3. In the paper, we present experiments evaluating feature-based methods that completely ignore graph structure (see Figure 6). The results indicate that relying solely on features for predictions leads to performance variability across datasets, making this approach unsuitable for addressing the cold-start node problem.