Subhajit Sahu wolfram77

My highlighted notes for the following paper:

Kozawa, Y., Amagasa, T., & Kitagawa, H. (2017, November). GPU-accelerated graph clustering via parallel label propagation. In Proceedings of the 2017 ACM on Conference on Information and Knowledge Management (pp. 567-576).

My highlighted notes for the following paper:

Soman, J., & Narang, A. (2011, May). Fast community detection algorithm with gpus and multicore architectures. In 2011 IEEE International Parallel & Distributed Processing Symposium (pp. 568-579). IEEE.

My highlighted notes for the following paper:

Cecil, T., Peng, D., Abrams, D., Osher, S. J., & Yablonovitch, E. (2022). Advances in inverse lithography. ACS Photonics, 10(4), 910-918.

My highlighted notes are below.

My highlighted notes for the following paper:

Abdelfattah A, Ahrens W, Anzt H, Armstrong C, Brock B, Buluc A, Busato F, Cojean T, Davis T, Demmel J, Dinh G. Interface for Sparse Linear Algebra Operations. arXiv preprint arXiv:2411.13259. 2024 Nov 20.

HyDetect: A Hybrid CPU-GPU Algorithm for Community Detection; Bhowmick and Vadhiyar (2019)

Graph is parititoned for CPU and GPU.
Louvain is independently performed to get psuedo-communities.
Determine doubtful vertices which do not belong to communities formed on a device.
Doubtful vertices are exchanged between the devices.
Executes Louvain algorithm again from subgraph on devices, which includes communities formed earlier and doubtful vertices.
This results in new communities and a new set of doubtful vertices.
Doubtful vertices are exchanged again.
Graph is coarsened to form a reduced graph of new vertices.

FlexGen: High-Throughput Generative Inference of Large Language Models with a Single GPU; Sheng et al. (2023)

Motivated by latency insensitive tasks and high dependence on accelerators.
FlexGen can be run on a single commodity system with CPU, GPU, and disk.
Solves an LP problem, searching for efficient patterns to store and access tensors.
Compresses weights and attention cache to 4 bits with minimal accuracy loss (fine-grained group-wise quantization).
These enable FlexGen to have larger batch size choices and improve its throughput significantly.
Running OPT-175B on a 16GB GPU, FlexGen achieves 1 token/s throughput for the first time.
Runs HELM benchmark with a 30B model in 21 hours.

It seems DRIFT search uses vector similarity search with top-k communities in the top-most hierarchy, and then drills down to the lower hierarchy levels. They seem to use follow-up questions for this purpose. The answers are ranked based on relavance to the query. Need to check the paper for more details.

Unlike Baseline RAG, which uses embedding search from a vector database to find matching query points in the source text, GraphRAG builds a knowledge graph from the text, which is summarized hierarchically based on community clusters.

From what I understand, the knowledge graph is built by extracting entities and relations from the text, and the community clusters are formed based on the similarity of the entities and relations. The hierarchical summarization is done by summarizing the clusters at different levels of abstraction.

GraphRAG seems to use GPT-4-turbo to build the knowledge graph. However, how are the edge weights calculated? Do the summaries generated affect how the weights are calculated in the next hierarchical level?

	Loading graph /home/subhajit.sahu/Data/indochina-2004.mtx ...
	order: 7414866 size: 194109311 {}

	# Batch size 1e-07
	- batch update size: 20
	- components: 1749035
	- blockgraph-levels: 524
	- affected-vertices: 7220621
	- affected-components: 1721204
	order: 7414866 size: 195418449 {} [27803.355 ms; 000 iters.] [0.0000e+00 err.] pagerankMonolithicOmpSplit (static)