Post by Daniel Daza

Neural methods for answering complex graph queries allow us to retrieve "likely" answers that might be missing if we only traversed the graph.  These methods require expensive optimization and tuning, so we were wondering: what if we used a simple heuristic? Our results on this question have been accepted in Transactions on Machine Learning 🔬in a great collaboration with Yannick Brunink, Yunjie He, and Michael Cochez, available here: https://lnkd.in/eKUH4JRd Enter query relaxation. If we have a query like "What is the location of the baseball team for which Aaron Judge plays?", we can relax it by dropping the explicit connection with Aaron judge: "What is the location of the baseball team for which *any* person plays?". This can be thought of as finding paths in the graph that partially match the query. In our experiments, we find that 1) Neural methods do not always outperform query relaxation, especially on longer path queries, 2) The kind of answers neural and relaxation methods rank high are actually different, 3) Their theoretical optimal combination leads to an upper bound in query answering performance, which confirms their complementarity. These results are exciting because they hint at heuristics for neural methods on query answering that we can use for improving future designs 🚀 They also extend recent findings on how neural methods perform poorly on harder complex queries, by Cosimo Gregucci, Bo X., Daniel Hernández, Lorenzo Loconte, Pasquale Minervini, PhD, Steffen Staab, and Antonio Vergari.