Current Slide

Small screen detected. You are viewing the mobile version of SlideWiki. If you wish to edit slides you will need to use a larger device.

Graph Clustering: Challenges of Finding Good Cuts

  • High computational cost
    • Many graph cut problems are computationally expensive
    • The sparsest cut problem is NP-hard
    • Need to tradeoff between efficiency/scalability and quality
  • Sophisticated graphs
    • May involve weights and/or cycles.
  • High dimensionality
    • A graph can have many vertices. In a similarity matrix, a vertex is represented as a vector (a row in the matrix) whose dimensionality is the number of vertices in the graph
  • Sparsity
    • A large graph is often sparse, meaning each vertex on average connects to only a small number of other vertices
    • A similarity matrix from a large sparse graph can also be sparse


Speaker notes:

Content Tools

Sources

There are currently no sources for this slide.