Shikhar Vashishth Chosen as Recipient of 2021 ACM India Doctoral Dissertation Award
December 29, 2020
Shikhar Vashishth of Indian Institute of Science has received the ACM India Council's 2021 Doctoral Dissertation Award for "Neural Graph Embedding Methods for Natural Language Processing."
Advisors: Partha Pratim Talukdar and Chiranjib Bhattacharyya
Abstract: Knowledge graphs are structured representations of facts in a graph, where nodes represent entities and edges represent relationships between them. Recent research has resulted in the development of several large KGs. However, all of them tend to be sparse with very few facts per entity. In the first part of the thesis, we propose two solutions to alleviate this problem: (1) KG Canonicalization, i.e., identifying and merging duplicate entities in a KG, (2) Relation Extraction which involves automating the process of extracting semantic relationships between entities from unstructured text. Traditional Neural Networks like CNNs and RNNs are constrained to handle Euclidean data. However, graphs in Natural Language Processing (NLP) are prominent. Recently, Graph Convolutional Networks (GCNs) have been proposed to address this shortcoming and have been successfully applied for several problems. In the second part of the thesis, we utilize GCNs for Document Timestamping problem and for learning word embeddings using dependency context of a word instead of sequential context. In this third part of the thesis, we address two limitations of existing GCN models, i.e., (1) The standard neighborhood aggregation scheme puts no constraints on the number of nodes that can influence the representation of a target node. This leads to a noisy representation of hub-nodes which coves almost the entire graph in a few hops. (2) Most of the existing GCN models are limited to handle undirected graphs. However, a more general and pervasive class of graphs are relational graphs where each edge has a label and direction associated with it. Existing approaches to handle such graphs suffer from over-parameterization and are restricted to learning representation of nodes only.
Honorable Mention went to Roohani Sharma of Institute of Mathematical Sciences, for "Advancing the Algorithmic Tool-kit for Parameterized Cut Problems."
Advisor: Saket Saurabh
Abstract: With this thesis we advance the algorithmic tool-kit, and contribute to the existing literature concerning parameterized (di)graph cut problems. The study has been conducted from three broad perspectives. The first is the urge to understand and contribute to the otherwise limited algorithmic tool-kit available to tackle digraph (cut) problems. The second concerns the exploration of the rich structural and algorithmic tool-kit available to tackle undirected graph cut problems, thereby resulting in engineering some of the existing techniques and exhibiting a broader scope of their applicability, together with contributing more advanced tools to the existing machinery. The third concerns building tools that allow “re-usability” of algorithms to solve problems under the presence of certain additional constraints. Towards the above objectives, the concrete questions that are addressed in the thesis are inspired from some major open problems and concerns in the field of parameterized complexity and kernelization. Some of these being the famously active open problem of the existence of a polynomial kernel for Directed Feedback Vertex/Arc Set, sub-exponential parameterized algorithms for digraph problems beyond tournaments, parameterized algorithms for partitioning problems beyond the classical partitioning problems, the existence of single exponential FPT algorithms for stable versions of classical cut problems and the parameterized complexity of Stable Multicut. We address the above questions either in full or extend the results known in literature that take steps to come closer to resolving the actual question. Below we describe the specific results that we obtain. We also remark that the below mentioned results, in several cases, lead to various enticing insights. In particular, through one of our results, we establish connections between kernelization and fault-tolerant subgraphs. Another result is based on a novel application of important separators in the design of polynomial kernels, which is a rare sight in kernelization. Yet other results give an interesting and useful combinatorial insight about the problem at hand.
The ACM India Doctoral Dissertation Award was established in 2011. This award recognizes the best doctoral dissertation from a degree-awarding institution based in India for each academic year, running from August 1 of one year to July 31 of the following year. The ACM India Doctoral Dissertation Award is accompanied by a prize of ₹2,00,000. An Honorable Mention award is accompanied by a prize of ₹1,00,000. The dissertation(s) will be published in the ACM Digital Library. Financial support for both the award and honorable mention is provided by Tata Consultancy Services (TCS). Please see the ACM India Doctoral Dissertation Award page for additional information on current and past winners.
Please join us in congratulating Shikhar Vashishth and Roohani Sharma.
Regards,
Hemant Pande, Executive Director, ACM India Council
(On behalf of the ACM India Awards Steering Committee)
