These are the most intriguing AI research papers that have been published in the last year. It blends AI with data science developments. It is chronologically organized and provides a link to a longer article.

Robust Query Processing: Mission Possible

In the design of industrial-strength database engines, robust query processing with solid performance guarantees is an exceedingly desirable goal. Despite concerted attempts over several decades, it has proven to be a largely intractable and elusive subject. The good news is that there have recently been a slew of intriguing technological breakthroughs at various levels of database design that combined promise to alleviate this problem meaningfully. The researchers discuss these unique research methodologies in this article, characterize their strengths and limits, and list open technological difficulties that must be solved to make robust query processing a modern reality.

Mining Top-k Pairs of Correlated Subgraphs in a Large Network

Frequent subgraph mining (FSM) finds all subgraphs in a graph that appear more than a value. It involves producing a candidate subgraph and calculating its support. The researchers look at the subject of correlated subgraphs mining (CSM), which aims to find pairs of subgraph patterns that regularly co-occur in close vicinity inside a single graph. Correlated subgraph patterns differ from frequent subgraph patterns because of the flexibility in connections between constituent subgraph instances. 

Hence, existing FSM algorithms cannot be applied to CSM. Furthermore, calculating the degree of correlation between two patterns necessitates enumerating and calculating distances between every pair of subgraph instances of both patterns. This work is both memory-intensive and computationally difficult. 

The researchers suggest two holistic best-first exploration algorithms to do this: CSM-E (an exact method) and CSM-A (a more efficient approximate method with near-optimal quality). To boost performance even further, they suggest a top-k pruning technique, while to reduce memory footprint, the researchers build Replica. This compressed data structure saves all instances of a subgraph pattern on demand. Their empirical results show that the proposed algorithms mine intriguing correlations and scale well across vast networks.

ChiSeL: Graph Similarity Search using Chi-Squared Statistics in Large Probabilistic Graphs

Subgraph querying is a fundamental primitive in many applications. Although the area of deterministic graphs is thoroughly explored, the graphs are probabilistic in many circumstances. In this work, the researchers address the challenge of subgraph querying in large probabilistic labelled graphs. They deploy ChiSeL, a unique algorithmic framework that employs the concept of statistical significance for approximation subgraph matching on uncertain graphs with uncertain edges. The researchers compute the statistical significance of each candidate matching vertex in the target network that matches a query vertex using the chi-squared statistic. 

The search method then explores the vertex neighbours with the highest chi-square score in a greedy manner. The researchers demonstrate how ChiSeL can manage uncertainty in labels and vertices in addition to edge uncertainty. Experiments on big real-world graphs demonstrate our algorithm's efficiency and effectiveness.

Image source: Unsplash