Engineering Motif Search for Large Graphs
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Describes engineering techniques for motif search in large graphs, focusing on scalable algorithms and implementation choices to handle big graph data; covers specific methods for finding small subgraph patterns (motifs) efficiently and practical optimizations to improve performance on large instances.
AI-written summary · about
chapters (18)
- 0:00Start
- 1:28A coarse-grained view
- 5:08Complexity of motif search
- 6:21Parameterization
- 6:39Dependence on k
- 7:14Tightness (conditional)
- 8:19Tight results
- 9:16Theory background for tight algorithm
- 9:59The algebraic view
- 11:39Connected sets to multilinearity
- 13:40Evaluation algorithm at point (x,y)
- 16:48Engineering an implementation
- 20:07Hardware configurations
- 20:35Edge-linear scaling
- 22:06Exponential scaling in k
- 23:53Summary (engineering)
- 25:00Summary (theory)
- 28:21Limited background on motif search
related talks
49mGraph Based Processing of Big Images
37m"Algorithms" is Not a Four-Letter Word
23mWorst-Case to Expander-Case Reductions
41mSearching for Products by Photo
50mGeometry on Steroids: Practical Experience Porting Heavy Computation to GPU
19mLeveraging Scene Graphs for Generative AI and Innovative Data Products
34mNew Tools for Peak Memory Scheduling
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)