Graph-based retrieval-augmented generation (RAG) enables large language models (LLMs) to incorporate structured knowledge via graph retrieval as contextual input, enhancing more accurate and context-aware reasoning. We observe that for different queries, it could retrieve similar subgraphs as prompts, and thus we propose SubGCache, which aims to reduce inference latency by reusing computation across queries with similar structural prompts (i.e., subgraphs). Specifically, SubGCache clusters queries based on subgraph embeddings, constructs a representative subgraph for each cluster, and pre-computes the key-value (KV) cache of the representative subgraph. For each query with its retrieved subgraph within a cluster, it reuses the pre-computed KV cache of the representative subgraph of the cluster without computing the KV tensors again for saving computation. Extensive experiments on three datasets across multiple LLM backbones and graph-based RAG frameworks demonstrate that SubGCache consistently reduces inference latency with comparable and even improved generation quality, achieving up to 6.68x reduction in time-to-first-token (TTFT).

Despite the success of Heterogeneous Graph Neural Networks (HGNNs) in modeling real-world Heterogeneous Information Networks (HINs), challenges such as expressiveness limitations and over-smoothing have prompted researchers to explore Graph Transformers (GTs) for enhanced HIN representation learning. However, research on GT in HINs remains limited, with two key shortcomings in existing work: (1) A node's neighbors at different distances in HINs convey diverse semantics; for instance, a paper's direct neighbor (a paper) in an academic graph signifies a citation relation, whereas the indirect neighbor (another paper) implies a thematic association, reflecting distinct meanings. Unfortunately, existing methods ignore such differences and uniformly treat neighbors within a given distance in a coarse manner, which results in semantic confusion. (2) Nodes in HINs have various types, each with unique semantics, e.g., papers and authors in an academic graph carry distinct meanings. Nevertheless, existing methods mix nodes of different types during neighbor aggregation, hindering the capture of proper correlations between nodes of diverse types. To bridge these gaps, we design an innovative structure named (k,t)-ring neighborhood, where nodes are initially organized by their distance, forming different non-overlapping k-ring neighborhoods for each distance. Within each k-ring structure, nodes are further categorized into different groups according to their types, thus emphasizing the heterogeneity of both distances and types in HINs naturally. Based on this structure, we propose a novel Hierarchical Heterogeneous Graph Transformer (HHGT) model, which seamlessly integrates a Type-level Transformer for aggregating nodes of different types within each k-ring neighborhood, followed by a Ring-level Transformer for aggregating different k-ring neighborhoods in a hierarchical manner. Extensive experiments are conducted on downstream tasks to verify HHGT's superiority over 14 baselines, with a notable improvement of up to 24.75% in NMI and 29.25% in ARI for node clustering task on the ACM dataset compared to the best baseline.

In social networks, dense relationships among users contribute to stable communities. Breakdowns of critical connections may cause users to leave the group. A popular model to measure the cohesiveness of a network is k-core or coreness. To identify important connections, in this paper, we propose and investigate the problem of k-core minimization problem under three different metrics. Specifically, given a graph G and a budget b, we aim to retrieve a set B of b edges for deletion purpose, which can minimize i) the number of nodes in the collapsed k-core (KNM), ii) the number of edges in the collapsed k-core (KEM), and iii) the overall coreness decreased in the target node set P (KCM). We first formally define the problems and prove that the three problems are all NP-hard. Then, a baseline greedy searching framework is developed. To scale for large graphs, optimized algorithms are developed by integrating novel pruning strategies and group-based structures. Finally, comprehensive experiments on 6 real social networks are conducted to demonstrate the efficiency and effectiveness of our proposed models and methods.

Mining cohesive subgraphs is a fundamental problem in social network analysis. The k-truss model has been widely used to measure the cohesiveness of subgraphs. Most existing studies about k-truss focus on unsigned graphs. However, in real applications, the edges in the networks can be either positive or negative, e.g., friend or foe relationships, which represents more information than unsigned networks. Therefore, the traditional k-truss model is not applicable for the signed networks. Motivated by this, in this paper, we propose a novel model, named signed (k,r)-truss, which leverages the property of balanced triangle in singed network analysis. Specifically, a signed (k,r)-truss is a subgraph where each edge has no less than k balanced support and no more than r unbalanced support. We prove that the problem of identifying the maximum signed (k,r)-truss is NP-hard. Due to the hardness of the problem, we tend to the heuristic strategies. A trivial algorithm is first presented. Then, two greedy algorithms are developed to enhance the processing. Finally, we conduct comprehensive experiments on real-world signed networks to verify the performance of proposed techniques.

Community detection is a fundamental problem in social network analysis, and most existing studies focus on unsigned graphs, i.e., treating all relationships as positive. However, friend and foe relationships naturally exist in many real-world applications. Ignoring the signed information may lead to unstable communities. To better describe the communities, we propose a novel model, named signed k-truss, which leverages the properties of k-truss and balanced triangle. We prove that the problem of identifying the maximum signed k-truss is NP-hard. To deal with large graphs, novel pruning strategies and algorithms are developed. Finally, we conduct comprehensive experiments on real-world signed networks to evaluate the performance of proposed techniques.

Bipartite graphs are widely used when modeling the relationships between two different types of entities, such as purchase relationships. In a bipartite graph, the number of butterflies, i.e., 2 × 2 biclique, is a fundamental metric for analyzing the structures and properties of bipartite graphs. Considering the deletion of critical nodes may affect the stability of bipartite graphs, we propose the butterfly minimization problem, where the attacker aims to maximize the number of butterflies removed from the graph by deleting b nodes. We prove the problem is NP-hard, and the objective function is monotonic and submodular. We adopt a greedy algorithm to solve the problem with 1 − 1/e approximation ratio. To scale for large graphs, novel methods are developed to reduce the searching space. Experiments over real-world bipartite graphs are conducted to demonstrate the advantages of proposed techniques.