1 Overview (slides)

• An introduction to graph-based applications across various domains

   (e.g., web search, KGs, social networks, drug discovery, image retrieval),

• Challenges in graph retrieval and the relevance of neural models.

• Examples of graph retrieval with applications to molecule and image retrieval

• Logistics of tutorial

• Knowledge graphs, entity disambiguation

• Outline of rest of tutorial

3 Vector Index (slides)

Introduction to Approximate Nearest Neighbor (ANN) methods and Locality-Sensitive Hashing (LSH) with a historical perspective from web search to modern applications in graph retrieval. Discussion on scalability benefits and indexing for real-time applications.

• Short history of sparse → dense document index

• Motivate need for o(corpus) retrieval with dense representation

• LSH definition, LSH as an indexing mechanism

• Hamming “master” LSH, amplification

• L1, cosine, dot, L2, LSH

• Direct application of LSH for whole-graph representation

4 Graph Alignment (slides)                                               

Presentation on recent advancements in alignment-driven modeling for graph retrieval. Explanation of alignment techniques, relevance scoring, and interpretability through alignment witnesses.

• Pros and Cons of single Vector Representations

• Graph distance as Quadratic Assignment problem (QAP)

  - Subgraph isomorphism,

  - Maximum common subgraph

  - Graph Edit Distance

• Approximation of QAP

     - Graph Distance to Set Distance

     - Permutation approximation

• Graph Indexing

Contacts:  

Indradyumna Roy: indrar.cse.jdvu@gmail.com

Soumen Chakrabarti: soumen.chakrabarti@gmail.com

Abir De: abir.iitkgp@gmail.com