wolfram77

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)

wolfram77

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

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

wolfram77

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

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

wolfram77

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.

wolfram77

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?

wolfram77

See below.

wolfram77

I was trying out the Misra-Gries algorithm for finding heavy hitters in a list of numbers, using vector instructions. But let me fill in some context first. I am trying to minimize the memory needed by Louvain/Leiden algorithms for community detection, and hopefully a bit of performance too. Currently the algorithms use a full-size per-thread hashtables, with each thread using |V| space for storing the associated weights for the hashtable. However, we could instead store a small hashtable, using the Misra-Gries algorithm, in the cache - obviously this might affect the performance (in terms of quality of the returned communities).

It was cool to go through step-by-step and be able to minimize the number of lines of generated machine code (with minimal conditional jumps). When you understand the vector instructions, you can write them in a higher-level logic without resorting to writing the instructions yourself, as these can be quite complicated. We let the compiler do its thing, but guide it with a short f

wolfram77

Notes on the paper Vertex Reordering for Real-World Graphs and Applications: An Empirical Evaluation.

wolfram77

Notes on the paper Joint Partitioning and Sampling Algorithm for Scaling Graph Neural Network.

wolfram77

See below.