Scale-Free Graph-Language Models

Dear Reviewer 7hx6,

We sincerely appreciate your recognition of the novelty and simplicity of our methods, as well as your helpful suggestions. Below, we provide detailed responses to your concerns.

W1: High labeling rates.
We further evaluate the performance of different models on the Cora and PubMed datasets under high labeling rates. Based on the standard data split, the training, evaluation, and testing sets for Cora include 140, 500, and 1,000 nodes, respectively. For PubMed, these sets contain 60, 500, and 1,000 nodes, respectively. Additionally, there are 1,068 and 18,157 unused labels in the Cora and PubMed datasets, respectively, which remain unused during training. To explore the impact of higher labeling rates, we incorporate these remaining labels into the training sets, resulting in 1,208 and 18,217 labeled training nodes for Cora and PubMed, respectively. The experimental results comparing the original data split and the complete label set for these two datasets are presented in Table 7 in Appendix A.4.

As observed, when labeled data is no longer a significant limitation, a pure DeBERTa model achieves satisfactory performance. In such cases, generating pseudo-labels becomes unnecessary, as LMs can produce high-quality text embeddings given sufficient labeled data. This outcome is reasonable, as LMs are typically larger and more powerful than GNNs for handling textual inputs. However, when working with the standard data split that includes only a few labeled nodes, generating pseudo-labels becomes crucial to enhance performance.

W2: comparison with real graphs.
We provide a case study comparing the graph structures of KNN graphs and real graphs, focusing on how well the edges in KNN graphs align with those in real graphs. In KNN graphs, the construction of edges between nodes is based on their feature similarity in a specific feature space. The feature similarity is determined by the chosen similarity metric, while the feature space is influenced by the text encoders used. Consequently, the accuracy of artificial edges matching real edges depends on the value of K, the similarity metric, and the text encoders. We conduct experiments on the Cora dataset using the same similarity metric and text encoders. Our results show that KNN graphs with K=25 and K=50 yield 2,700 and 3,422 edges, respectively, that precisely match the true edges in the real graph. While increasing K can improve accuracy by reconstructing more known edges, it also introduces a higher risk of generating noisy edges. Thus, a trade-off exists between edge accuracy and noise as K increases.

Here, we would like to emphasize that our primary goal is to investigate a real structural prior (i.e., the scale-free property) for graph generation, rather than to approximate all true edges in the real graphs. We really appreciate the reviewer for proposing the intriguing idea of approximating a real graph and look forward to exploring it in our future work.

W3: minor typos.
Thank you for pointing out the minor typos in our algorithm tables. Yes, "Textual feature X" in Algorithm 1 should be "Text sequences X," and "replace X with E" in Algorithm 2 should be "replace F with E." We will ensure these typos are corrected in the final version of the manuscript.

W4: other LLM encoders.
We appreciate the reviewer’s valuable suggestion. Following your recommendation, we adopt the E5-Mistral-7B-Instruct model as the text encoder. Additionally, based on the MTEB leaderboard, we include the BAAI/bge-en-icl model in our experiments. Due to limitations in computational resources, we are unable to fine-tune the E5-Mistral-7B-Instruct and BAAI/bge-en-icl models on our datasets. For comparison, we utilized the pretrained models to extract node features and compared them against both a pretrained and a fine-tuned DeBERTa model.

The following two tables provide a detailed comparison of the models and their performance, respectively.

Please refer to the next page for the continuation of our responses.

W4: other LLM encoders.

As observed, both the pretrained E5-Mistral-7B-Instruct and BAAI/bge-en-icl models outperform the pretrained DeBERTa model but fall short of the well-finetuned DeBERTa model. However, it is reasonable to infer that a fine-tuned E5-Mistral-7B-Instruct or BAAI/bge-en-icl model would surpass the performance of the fine-tuned DeBERTa model.

W5: only KNN graph.
In Section 4.3, the experimental results presented in Table 6 are obtained using GNN models without involving LM fine-tuning. Specifically, the GNN models are trained on KNN graphs and real graphs, respectively.

We sincerely appreciate your valuable comments, which have provided us with new insights. We hope our response effectively addresses your concerns.

Dear Reviewer mKrX,

We really appreciate you recognizing our contributions and providing constructive suggestions to improve our manuscript. Below, we address your concerns in detail.

W1: other types of networks.
At the end of our submission, we provide a case study on social networks in Appendix A.5. Specifically, we explore the degree distribution of KNN graphs on three social networks: Deezer Europe, LastFM Asia, and Facebook Page-Page.

• Deezer Europe is a user-user network of European members of the music streaming service Deezer.
• LastFM Asia is an online social network of people who use the online music streaming site LastFM and live in Asia.
• Facebook is a page-page graph of verified Facebook sites.
  For detailed descriptions of these social networks, please refer to [a1].

It is important to note that the node embeddings of citation networks and social networks differ significantly. For the citation networks, node embeddings are derived from textual sequences of nodes (i.e., natural languages). For the social networks, node embeddings are generated based on the graph structure through embedding models Diff2vec [a2]. More specific, the embedding of each node in social networks is obtained by computing an Euler tour on this node and with additional post-processing [a2]. The degree distribution of KNN graphs on these social networks with different distance metrics are shown in Figure 9 in Appendix A.5.

W2: extension on heterogeneous networks.
First of all, we would like to emphasize that this paper follows existing graph-language models, including the baselines used for comparison, and focuses on homophilic networks with textual attributes.

We really appreciate the reviewer’s suggestion on how to extend our method on heterogeneous networks. To avoid the potential bias, a feasible solution is to build several subgraphs for nodes and features with various similarity metrics, such as feature-feature similarity, feature-semantic similarity, and semantic-semantic similarity. These subgraphs can then be integrated into a unified heterogeneous graph. Besides, we can also consider a novel method proposed in [a3] for edge construction. However, it is very challenging to incorporate the scale-free property into heterogeneous graph generation. We would like to explore this interesting problem in our future study.

W3 & Q1: validation on KNN.
It is a good suggestion to compare our method with other graph generation methods. Following the reviewer’s suggestion, we compare our method with random graph generation. For random graph, we consider the Erdős–Rényi (ER) graph $G(n, p)$, which is a random graph with $n$ nodes where each pair of nodes is connected with probability $p$. In the $G(n, p)$ graph, the degree $k$ of a node follows a binomial distribution: $P(k) = \binom{n-1}{k} p^k (1-p)^{n-1-k}$. When $n$ is large and $p$ is small, the degree distribution can be approximated by a Poisson distribution: $P(k) = \frac{\lambda^k e^{-\lambda}}{k!}$, where $\lambda = np$. This is different than the power-law distribution of scale-free networks.

The performance comparison between random graph and our KNN graph on the arxiv23 dataset is shown below.

Q2: Real graph.
The real graphs used in our experiments are exactly the original graphs from the benchmark datasets. Specifically, the real graph used in Table 6 is the original graph of the arxiv23 dataset (which is an open-access dataset referenced in [a5]). This dataset contains 57,471 nodes, and the real graph contains 122,835 connections.

Please refer to the next page for the continuation of our responses.

Q3: Our thoughts on results in Table 6.
This is a good question. As shown in Table 6, the performance of using the real graph is worse than that of using KNN graph in cases with low labeling rates, such as 0.11% and 0.22%. We provide a potential explanation on this phenomenon.

In fact, beyond facilitating information transmission between node features (attributes), the graph also plays a crucial role in the propagation of label (semantic) information. Consequently, both the number of labeled nodes and the selection of specific nodes to label can significantly impact the final classification performance. Consider an extreme case: if all labeled nodes in a real graph are isolated (i.e., they have no connections with other nodes), the label information cannot propagate to the unlabeled nodes. In contrast, constructing an artificial graph for these nodes may establish connections between unlabeled nodes and these isolated labeled nodes, enabling label information propagation across the graph. Therefore, it is possible that artificial graphs outperform real graphs, particularly when the labeling rate is low.

Additionally, KNN graphs can generate a portion of the real edges. Our experimental results demonstrate that for the Cora dataset, KNN graphs generate 2,700 and 3,422 edges that precisely match the true edges in the real graphs when K=25 and K=50, respectively. Furthermore, it is important to note that real graphs may contain noisy edges. KNN reduces the risk of creating such noisy edges, as it constructs edges only between nodes with highly similar features.

Q4: LLM-obly prediction.
Thank you for the constructive suggestion. In [a3], the authors propose novel prompts for scalable link prediction on heterogeneous graphs by articulating graph details in natural language. This is a purely LLM-based approach that transforms graph details into descriptive texts. In [a4], the authors describe the multi-scale geometric structure of graphs using natural language and then fine-tune an LLM with instruction learning to perform various graph tasks. Since the authors [a4] also focus on the node classification task, we conduct an empirical comparison between our method and theirs on the PubMed dataset.

Comparison under the same labeling rate using the standard data splitting (i.e., 60 labeled nodes):

Comparison under different labeling rates:

As we can see, our proposed method with iterative training outperforms the approach presented in [a4] under the standard data split and achieves comparable performance even at lower labeling rates.

Please refer to the next page for the continuation of our responses.

Q5: experimental details.
We conduct experiments on different labeling rates. The Cora dataset contains 7 classes, so we adopt 70, 140, 210, and 420 labeled nodes for experiments, where we randomly select 10, 20, 30, 60 nodes in each class as the labeled nodes. Additionally, we experiment with 600 labeled nodes, where 420 nodes are consistent with the previous case, and an additional 180 nodes are randomly selected. This labeling strategy is also applied to the PubMed dataset. For the ogbn-arxiv and arxiv23 datasets, we randomly select 50, 100, 150, 300, and 500 nodes from the original labeled set in the standard data split, designating them as labeled nodes while treating the remaining nodes as unlabeled. For all datasets and labeling rates, we conduct five independent experiments using different random seeds and report the average testing accuracy along with the standard deviation.

The iterative algorithm is employed exclusively for Table 2 in Section 4.3. This demonstrates that improved text embeddings facilitate the generation of higher-quality pseudo-labels, which, in turn, further enhance the discriminability of the text embeddings. Detailed descriptions of the algorithms can be found in Appendix A.3, as well as in Algorithms 1 and 2.

We sincerely appreciate your valuable suggestions and insightful feedback, and we hope that our response addresses your concerns.

[a1] Multi-scale attributed node embedding. Rozemberczki, B., Allen, C., & Sarkar, R. Journal of Complex Networks, 2021.
[a2] Fast sequence-based embedding with diffusion graphs. Rozemberczki, B., & Sarkar, R. In Complex Networks IX: Proceedings of the 9th Conference on Complex Networks CompleNet, 2018.
[a3] Bi B, Liu S, Wang Y, et al. Lpnl: Scalable link prediction with large language models[C]//Findings of the Association for Computational Linguistics ACL 2024. 2024: 3615-3625.
[a4] Ye R, Zhang C, Wang R, et al. Natural language is all a graph needs[J]. arXiv preprint arXiv:2308.07134, 2023, 4(5): 7.
[a5] He et al, Harnessing explanations: Llm-to-lm interpreter for enhanced text-attributed graph representation learning. ICLR, 2024.

Q2: extension on social networks.
In Section 6, we present the limitation of this work which includes how to extend our observations and strategies to other types of networks. We provide a case study in Appendix A.5 to examine the degree distribution of KNN graphs on different social networks [a5]. It is important to highlight the significant differences between the node embeddings of citation networks and social networks. In citation networks, node embeddings are derived from textual sequences (i.e., natural languages) associated with the nodes. In contrast, for the social networks, node embeddings are generated based on the graph structure using embedding models like Diff2vec [a6]. Specifically, the embedding of each node in social networks is obtained by computing an Euler tour on the node, followed by additional post-processing steps [a6].

This paper primarily focuses on graph-language models for classifying nodes with textual attributes (natural language). Since the node attributes in these social networks are not textual sequences, applying language models to them would neither be appropriate nor reasonable. As a result, we provide the case study in Appendix A.5 to investigate the degree distribution on these social networks.

We sincerely appreciate your valuable comments and insightful suggestions. We hope our response effectively addresses your concerns.

[a1] Mathew D. Penrose. Random Geometric Graphs. 2003.
[a2] Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286 (5439):509–512, 1999.
[a3] Albert-Laszlo Barabasi and Eric Bonabeau. Scale-free networks. Scientific American, 288(5):60–69, 2003.
[a4] Albert-Laszlo Barabasi and Marton Posfai. Network science. Cambridge University Press, Cambridge, 2016.
[a5] Rozemberczki, B., Allen, C., & Sarkar, R. Multi-scale attributed node embedding. Journal of Complex Networks, 2021.
[a6] Rozemberczki, B., & Sarkar, R. Fast sequence-based embedding with diffusion graphs. In Complex Networks IX: Proceedings of the 9th Conference on Complex Networks CompleNet, 2018.

Dear Reviewer dcB6,

Thank you very much for recognizing our contributions and for providing constructive comments. We address your concerns as below.

W1 and Q1: additional theoretical explanation.
Thank you for this constructive comment. We begin by discussing a simple case using a random geometric graph (RGG) and then elaborate on why analyzing the degree distribution of KNN graphs on real-world data from a theoretical perspective presents significant challenges.

Consider a random geometric graph $G(X_n; r_n)$ with $n$ nodes $X_n = \\{x_1, …, x_n\\}$ sampled independently from a probability density $f(x)$ in $\mathbb{R}^d$, where two nodes $x_i, x_j$ are connected only if $\\|x_i - x_j\\| \leq r_n$, and $r_n$ is the connection radius of the graph, which depends on $n$ and determines the graph’s density.

We define the maximum degree of the graph $G(X_n; r_n)$ as $\theta_{max} = \max_{1 \leq i \leq n} \deg(x_i)$ where $\deg(x_i)$ is the degree of the node $x_i$, i.e., the number of neighbors of $x_i$ within radius $r_n$, and define a binary indicator function $h^*(\{0, x_1, \ldots, x_k\})$ on a subgraph $G(Y; 1)$, where $Y = \\{0, x_1, \ldots, x_k\\}$. Here, $h^*(Y) = 1$ if the subgraph $G(Y; 1)$ has at least one vertex with degree $k$, and $0$ otherwise. $G(Y; 1)$ is the induced subgraph on the subset $Y \subset \mathbb{R}^d$ using a unit connection radius, where an edge exists between two vertices $u, v \in Y$ if and only if the Euclidean distance $\\|u - v\\| \leq 1$.

Based on the above definitions, we have the following theorem [a1]:

Let $k \in \mathbb{N}$, $\lambda > 0$. If $n^{(k+1)/k} r_n^d \to \lambda^{1/k}$ as $n \to \infty$, then $\lim_{n \to \infty} P[\theta_{max} = k-1] = 1 - \lim_{n \to \infty} P[\theta_{max} = k]$ $= \exp\left( -\frac{\lambda}{(k+1)!} \int_{\mathbb{R}^d} f(x)^{k+1} dx \times \int_{(\mathbb{R}^d)^k} h^* (\{0, x_1, \ldots, x_k\}) d(x_1, \ldots, x_k) \right),$ where $P[\theta_{max} = k]$ refers to the probability that the maximal degree equals to k.

This theorem provides an asymptotic result for the distribution of $\theta_{max}$ as the number of nodes $n\to \infty$, under the scaling condition $n^{(k+1)/k} r_n^d \to \lambda^{1/k}$ as $n \to \infty$. As we can see, the maximum degree is affected by several factors, including:

• Distribution density $f(x)$. The density $f(x)$ impacts the likelihood of finding clusters of $k$ points near a given node.
• Connection radius $r_n$. The probability of achieving a maximum degree $k$ depends on how nodes cluster locally, which is controlled by the scaling of $r_n$.
• Local structure $h^*(Y)$. This determines if the subgraph $G(Y; 1)$ satisfies the condition of having at least one node of degree $k$.

Similarly, the degree distribution of KNN graphs is also primarily shaped by several critical factors:

• Node distribution (similar to the $f(x)$ in RGG). Determining the node distribution of real-world data without prior knowledge is not feasible. Even if the original node distribution is known, the node distribution remains indeterminate due to the reshaping effect of the text encoders used.
• The value of K (similar to the $r_n$ in RGG). The selection of K influences the magnitude of degrees.
• The choice of similarity metrics (similar to the $h^*(Y)$ in RGG). Even with assumptions about the embedding distribution of nodes, the degree distribution is further complicated by the choice of similarity metrics, as different similarity metrics result in varying connections between nodes.

Consequently, we believe that determining the degree distribution in KNN graphs for different real-world datasets should primarily rely on empirical evidence.

Additionally, the scale-free property of networks can be effectively explained by the well-known Barabási–Albert (BA) model [a2, a3, a4]. We analyze the key differences between the BA model and KNN graphs. The BA model operates under the following conditions:

• Growth: the number of nodes continuously increases over time.
• Preferential attachment: starting with an initial set of edges, new nodes are more likely to connect to high-degree nodes, with edges directed from new nodes to existing nodes.
• No node attributes: The BA model does not take node features or attributes into account when constructing edges.

In contrast, KNN graphs have a fixed size, no initial edges, and allow edges to have arbitrary directions. Connections between nodes are determined solely based on their feature similarity. Notably, KNN graph edges can be determined in parallel, whereas edges in the BA model must be constructed sequentially. This distinction makes KNN graphs more practical and efficient for real-world applications.

Please refer to the next page for the continuation of our responses.

Dear Reviewer dcB6,

Thank you very much for recognizing the contributions and novelty of our work. In Response Parts 1-2, we have provided additional theoretical explanations using random geometric graphs and clarified why applying graph-language models to social networks may not be appropriate. We would greatly appreciate it if you might consider updating the score after reading our response.

Thank you once again for your time and effort!

Sincerely,
Authors

W3: discuss with other related work.
The primary distinction between our method and these approaches lies in the following aspects:

• Our approach does not rely on extensive labeled data for fine-tuning language models (LMs), making it more practical in scenarios with limited supervision.
• Our method does not require a given graph structure, allowing it to operate flexibly in situations where the graph needs to be generated.
• Unlike these methods, which focus either on graph generation or text embedding, we integrate both into a unified GLM framework, addressing them simultaneously rather than separately.

Q1: downstream task.
In Section 2.1, Problem Definition, we articulate our task as follows:
Given a set of documents denoted as $\mathcal{D}=\\{\mathcal{X}_L, \mathcal{X}_U, \mathcal{Y}_L\\}$, where $\mathcal{X}_L=\\{\mathbf{x}_i\\}^{m}$ and $\mathcal{X}_U=\\{\mathbf{x}_i\\}^{n}$ represent the text sequences of $m$ labeled and $n$ unlabeled documents, respectively, and $\mathcal{Y}_L=\\{\mathbf{y}_i\\}^{m}$ is the label set for the labeled samples, with $m\ll n$ indicating a scarcity of labeled nodes compared to the abundance of unlabeled ones, we tackle a graph-based semi-supervised classification task that involves training a model on $\mathcal{D}$ to classify unlabeled documents $\mathcal{X}_U$.

The downstream task of our proposed model is node classification, i.e., training a model on $\mathcal{D}$ to classify unlabeled nodes $\mathcal{X}_U$. In Section 3.3 Classification, we further clarify that we solve the classification task by training a graph-based semi-supervised learning model on $\mathbf{E}$ and $\mathbf{A}$ using the available labels $\mathcal{Y}_L$.

Q2: undirected graph.
In GNN training stage, the graph used is undirected. As mentioned in line 269, we consider a binary graph, which aligns with the setup of the baselines we compared against. In Figure 5, we present the in-degree distribution of KNN graphs. This is because the out-degree of KNN graphs is constant for all nodes, as it is determined by the fixed parameter K.

Q3: Previous artificial assumption and our structure prior.
In Section 5, lines 507-512, we discuss the artificial assumptions made by previous LGI methods regarding the underlying edge distribution. For example, Zhang et al. (2010) impose a uniformity assumption on edge weights. Lu et al. (2018) introduce a block diagonal prior to the graph Laplacian matrix. Jin et al. (2020) apply a sparsity and low rankness assumption on the adjacency matrix. ix. Fatemi et al. (2021) assume that a graph structure effective for predicting features should also be effective for predicting labels. These methods rely on specific optimizations and additional model training across the entire dataset. And the artificial assumptions they adopt may not accurately represent the true structural properties of real-world data.

In this paper, we focus on a fundamental characteristic of real edge distributions in citation networks: the scale-free property. This property is ubiquitous in real-world networks, particularly in citation networks, and reflects an inherent attribute of the data rather than an imposed assumption. Leveraging this scale-free property, we construct a graph-based pseudo-labeler that offers complementary supervision for fine-tuning language models (LMs).

Q4: requirement of LM finetuning.
When we mentioned the requirements for LM fine-tuning, we emphasized the need for extensive annotations rather than computational demand. We list out related publications in Section 5, lines 514-523.

Following your suggestion, we provide an overview of the computational demands of some commonly used LMs. According to [a3] (https://arxiv.org/abs/2401.15569), the computation demands are as follows:

Q5: alpha estimation.
In lines 251-253, we provide alpha estimations for the three tested datasets. The details of the estimation method are available in [a4]. Notably, the estimation method presented in the book https://academic.oup.com/book/27303 originates from the paper [a4]. The author of the book is also an author of [a4].

Please refer to the next page for the continuation of our responses.

Q10: performance.
Thank you for the suggestion. The comparison results between our method and the SOTA methods are mainly presented in Table 1. As shown, our proposed method outperforms the SOTA methods in most cases, particularly under very low labeling rates. Due to space constraints, we were unable to include the performance improvements in the Introduction and Abstract. However, we will consider moving some of the ablation study results to the Appendix to create space for highlighting these improvements in the Introduction and Abstract.

Q11: time/space complexity analysis of different modules.
The table below presents the time and space complexity analysis of different modules on the ogbn-arxiv dataset.

We sincerely appreciate your valuable comments and insightful suggestions. We hope our response effectively addresses your concerns.

[a1] Yang et al. GraphFormers: GNN-nested Transformers for Representation Learning on Textual Graph. NeurIPS 21.
[a2] Duan et al. SimTeG: A Frustratingly Simple Approach Improves Textual Graph Learning. Arxiv 23.
[a3] Zhu et al. Efficient Tuning and Inference for Large Language Models on Textual Graphs. IJCAI 24.
[a4] Clauset et al. Power-Law Distributions in Empirical Data. SIAM 2009.
[a5] Clauset et al. Scale-free networks are rare. Nature Communications 2019.
[a6] Voitalov et al. Scale-Free Networks Well Done. Physical Review Research. 2019.
[a7] Albert-László Barabási. Love is All You Need – Clauset's fruitless search for scale-free networks. 2018.
[a8] Zhao et al. Heterogeneous Graph Structure Learning for Graph Neural Networks. AAAI 2021.
[a9] Bi B, Liu S, Wang Y, et al. Lpnl: Scalable link prediction with large language models[C]//Findings of the Association for Computational Linguistics ACL 2024. 2024: 3615-3625.

Q5: alpha estimation.
It is important to highlight that $\alpha \in [2, 3)$ unequivocally indicates a scale-free network, while $\alpha>3$ still reflects a power-law distribution. The paper [a5] (https://www.nature.com/articles/s41467-019-08746-5) is very controversial. Contrary to its assertions, scale-free networks are, in fact, ubiquitous. As demonstrated in [a6], real-world scale-free networks are definitely not as rare as one would conclude based on the popular but unrealistic assumption that real-world data comes from power laws of pristine purity, void of noise and deviations. According to [a6], a network is scale-free if its degree distribution approaches a power law as the network keeps growing following the same mechanisms. Thus, fluctuations that make a network fail a statistical test would not matter, because if one let the network evolve, it could soon pass the test.

Furthermore, as shown in [a7] (https://uploads-ssl.webflow.com/58bcae2c9d6c401e73a26fed/5aa01d3e24eebb000199a0a2_loveisallyouneed.pdf) , Albert-László Barabási, who introduced the concept of scale-free networks in 1999, strongly disputes the claim that scale-free networks are rare. At the end of [a7], Albert-László Barabási said: “So before accepting the attention-grabbing claims of the BC paper [a5], you must peek under its hood. And if you take the time to do that, you will find that the study is oblivious to 18 years of knowledge accumulated in network science. You will also find a fictional criterion of scale-free networks. Most important, you will find that their central criterion fails the most elementary tests. And those are only the big problems - if you are willing to devote time to it, you will discover additional technical lapses - but this piece must have an end. What you will not find, is a careful and unbiased statistical study that upends a paradigm.”

Q6: log-log sorted degree.
Thank you for the suggestion. In Figure 1, our goal is to illustrate the heavy-tailed nature of the power-law distribution in scale-free networks. This figure emphasizes the characteristic distribution, where a few hubs with high degrees coexist with numerous small nodes with low degrees (which is a hallmark of scale-free networks). To better visualize this heavy-tailed structure, Figure 1 is not plotted using a log-log sorted degree template.

In contrast, Figure 5 presents the degree distribution using a log-log sorted degree template. In this format, the power-law distribution appears as a straight line, making it easier to confirm the scale-free property in the log-log space. These complementary visualizations help to illustrate different perspectives of the power-law distribution in scale-free networks.

Q7: node distribution.
It is node distribution. Edges do not exist that is why we use KNN to establish connections between nodes.

Q8: K estimation.
The adjacency matrix is unavailable. As described in Problem Definition, Section 2.1, we are only given a set of documents, denoted as $\mathcal{D}=\\{\mathcal{X}_L, \mathcal{X}_U, \mathcal{Y}_L\\}$. Our task it to train a model on $\mathcal{D}$ to classify the unlabeled documents $\mathcal{X}_U$. Since the graph structure (i.e., the adjacency matrix) is not provided, in Introduction and Related Work, we introduce various latent graph inference methods which are specifically designed to generate a graph (with an adjacency matrix).

In addition, our approach aims to approximate the scale-free property rather than the true adjacency matrix. More importantly, a low approximation error to the real adjacency matrix does not necessarily translate to better performance. As demonstrated in Table 6, even when using the real graph, it may not achieve optimal performance.

Q9: homophily assumption and comparison with related approaches.
We would like to emphasize that this paper builds upon existing graph-language models, including the baselines used for comparison, with a specific focus on homophilic graphs with textual attributes. In the related work, all referenced approaches are also based on the assumption of homophily. The primary difference between our method and these approaches is listed in W3, Response Part 2.

In the literature, there are also heterogeneous latent graph inference methods [a8, a9], which could be considered for graph construction in heterogeneous settings. However, this falls outside the scope of our paper. Additionally, incorporating the scale-free property into heterogeneous graph generation is challenging. We plan to explore this problem in our future research.

Please refer to the next page for the continuation of our responses.

Dear Reviewer NtXH,

Thank you very much for your valuable suggestions and detailed comments. We address your concerns as below.

W1: clarification on our contributions.
As listed at the end of Introduction, our key contributions are threefold:

• We identify two key challenges in existing GLMs: artificial structural assumptions for graph generation and unreliable LM finetuning for text embedding. We propose addressing these challenges sequentially by leveraging a well-grounded graph structural prior.
• We explore the scale-free edge distribution in real networks as our graph structural prior. Our empirical validation and analysis reveal that a KNN graph, constructed using cosine similarity with an appropriately chosen $k$, closely approximates a scale-free network.
• To the best of our knowledge, this work is the first attempt to integrate graph generation and text embedding into a unified GLM framework.

We would like to further clarify the third point. As mentioned in our Introduction section, existing graph-language models (GLMs) can be broadly categorized into latent graph inference (LGI) models and language-assisted graph (LAG) models (please refer to Section 5 for a more detailed introduction to these two types of models). LGI models focus on graph generation through graph neural networks (GNNs) and usually assume that node features are given. Conversely, LAG models aim to enhance text embeddings using language models (LMs) and assume that the graph structure is provided. In this paper, we simultaneously consider both graph generation and text embedding within a unified GLM framework, rather than focusing on just one aspect.

W2: algorithm design.
Due to the page limitation (10 pages), we had to include Algorithm Tables 1 and 2 in the Appendix. However, we will consider moving some ablation study results to the Appendix and replacing them with the Algorithms in the main paper. We provide time and space complexity analysis of each part of our framework in Q11.

We further explain the roles of different modules, which are also explained in the main paper:

• Pseudo-Labeler (Section 3.2, lines 274-282). The pseudo-labeler is utilized to generate high-quality pseudo-labels that enhance language model (LM) training. Specifically, we use a GNN as the pseudo-labeler, which is trained on node features $\mathbf{F}$, the adjacency graph $\mathbf{A}$, and the available labels $\mathcal{Y}_L=\\{\mathbf{y}_i\\}^{m}$.
• Text Embedding (Section 3.2, lines 287-292). The pseudo-labels $\hat{\mathcal{Y}}_U = \\{\hat{\mathbf{y}}_j\\}^{n}$ are used to finetune a language model. The fine-tuned LM is then employed to generate text embeddings $\mathbf{E}$.
• GNN for Final Classification (Section 3.3, lines 310-312). The text embeddings $\mathbf{E}$ are subsequently used to train another GNN for the final node classification task.

W3: discuss with other related work.
The results of compared methods presented in this paper are not directly taken from the original papers. Instead, we reran all the compared baselines using their open-source codes. Notably, TAPE performed its own train/validation/test splits for the Cora and PubMed datasets, allocating 60% of the data for training, 20% for validation, and 20% for testing. This differs from the standard dataset splits, where only 140 and 60 labeled nodes are used for the training sets of the Cora and PubMed datasets, respectively. Our experimental results reveal that TAPE suffers from limited supervision. This is because finetuning a language model requires a sufficient number of labeled samples, and the standard splits provide far fewer labeled nodes. We highlight the difficulties posed by limited supervision when fine-tuning language models (lines 43-45, 416-421, and 519-523).

We briefly discuss the difference between our method and GraphFormers [a1], SimTEG [a2], and Eingne [a3] as follows.

• GraphFormers: This method incorporates GNNs nested alongside each transformer layer of the pretrained language model and focuses primarily on the link prediction task.
• SimTEG: As mentioned in lines 516-517, SimTEG performs supervised, parameter-efficient fine-tuning on a pretrained language model. It then generates node embeddings using the last hidden states of the fine-tuned LM for node classification.
• Eingne: This is a parameter- and memory-efficient fine-tuning method designed for textual graphs with a large language model (LLM) encoder. It introduces a lightweight, tunable GNN-based side structure alongside each layer of the LLM.

Please refer to the next page for the continuation of our responses.

Dear Reviewer NtXH,

Thank you very much for your time and effort in reviewing our paper. In response to your comments and concerns, we have submitted detailed answers in Response Parts 1-4.

As the discussion deadline approaches, we would greatly value your input on whether our responses have addressed your concerns and if they have helped in re-evaluating our work. Your feedback is incredibly important to us, and we would deeply appreciate it if you could share any additional thoughts or suggestions you may have.

Thank you once again for your time and consideration!

Sincerely,
Authors