Timezone: »
The graph retrieval problem is to search in a large corpus of graphs for ones that are most similar to a query graph. A common consideration for scoring similarity is the maximum common subgraph (MCS) between the query and corpus graphs, usually counting the number of common edges (i.e., MCES). In some applications, it is also desirable that the common subgraph be connected, i.e., the maximum common connected subgraph (MCCS). Finding exact MCES and MCCS is intractable, but may be unnecessary if ranking corpus graphs by relevance is the goal. We design fast and trainable neural functions that approximate MCES and MCCS well. Late interaction methods compute dense representations for the query and corpus graph separately, and compare these representations using simple similarity functions at the last stage, leading to highly scalable systems. Early interaction methods combine information from both graphs right from the input stages, are usually considerably more accurate, but slower. We propose both late and early interaction neural MCES and MCCS formulations. They are both based on a continuous relaxation of a node alignment matrix between query and corpus nodes. For MCCS, we propose a novel differentiable network for estimating the size of the largest connected common subgraph. Extensive experiments with seven data sets show that our proposals are superior among late interaction models in terms of both accuracy and speed. Our early interaction models provide accuracy competitive with the state of the art, at substantially greater speeds.
Author Information
Indradyumna Roy (IIT Bombay)
Soumen Chakrabarti (Indian Institute of Technology Bombay)
Abir De (IIT Bombay)
More from the Same Authors
-
2021 Spotlight: Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems »
Subhabrata Dutta · Tanya Gautam · Soumen Chakrabarti · Tanmoy Chakraborty -
2023 Poster: Locality Sensitive Hashing in Fourier Frequency Domain For Soft Set Containment Search »
Indradyumna Roy · Rishi Agarwal · Soumen Chakrabarti · Anirban Dasgupta · Abir De -
2023 Poster: Learning to Select a Subset of Training Examples to Generalize Efficient Model Training »
Eeshaan Jain · Tushar Nandy · Gaurav Aggarwal · Ashish Tendulkar · Rishabh Iyer · Abir De -
2022 Spotlight: Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection »
Abir De · Soumen Chakrabarti -
2022 Spotlight: Maximum Common Subgraph Guided Graph Retrieval: Late and Early Interaction Networks »
Indradyumna Roy · Soumen Chakrabarti · Abir De -
2022 Spotlight: Learning Recourse on Instance Environment to Enhance Prediction Accuracy »
Lokesh N · Guntakanti Sai Koushik · Abir De · Sunita Sarawagi -
2022 Poster: Neural Estimation of Submodular Functions with Applications to Differentiable Subset Selection »
Abir De · Soumen Chakrabarti -
2022 Poster: Learning Recourse on Instance Environment to Enhance Prediction Accuracy »
Lokesh N · Guntakanti Sai Koushik · Abir De · Sunita Sarawagi -
2021 Poster: Learning to Select Exogenous Events for Marked Temporal Point Process »
Ping Zhang · Rishabh Iyer · Ashish Tendulkar · Gaurav Aggarwal · Abir De -
2021 Poster: Redesigning the Transformer Architecture with Insights from Multi-particle Dynamical Systems »
Subhabrata Dutta · Tanya Gautam · Soumen Chakrabarti · Tanmoy Chakraborty -
2021 Poster: Active Assessment of Prediction Services as Accuracy Surface Over Attribute Combinations »
Vihari Piratla · Soumen Chakrabarti · Sunita Sarawagi -
2021 Poster: Differentiable Learning Under Triage »
Nastaran Okati · Abir De · Manuel Rodriguez -
2021 Poster: Training for the Future: A Simple Gradient Interpolation Loss to Generalize Along Time »
Anshul Nasery · Soumyadeep Thakur · Vihari Piratla · Abir De · Sunita Sarawagi -
2021 Poster: Counterfactual Explanations in Sequential Decision Making Under Uncertainty »
Stratis Tsirtsis · Abir De · Manuel Rodriguez -
2019 : Poster Session »
Ayse Cakmak · Yunkai Zhang · Srijith Prabhakarannair Kusumam · Mohamed Osama Ahmed · Xintao Wu · Jayesh Choudhari · David I Inouye · Thomas Taylor · Michel Besserve · Ali Caner Turkmen · Kazi Islam · Antonio Artés · Amrith Setlur · Zhanghua Fu · Zhen Han · Abir De · Nan Du · Pablo Sanchez-Martin -
2018 Poster: Deep Reinforcement Learning of Marked Temporal Point Processes »
Utkarsh Upadhyay · Abir De · Manuel Gomez Rodriguez -
2016 Poster: Learning and Forecasting Opinion Dynamics in Social Networks »
Abir De · Isabel Valera · Niloy Ganguly · Sourangshu Bhattacharya · Manuel Gomez Rodriguez