ActiveReach: an active learning framework for approximate reachability query answering in large-scale graphs.

Area of Science:

• Graph Theory
• Machine Learning
• Database Systems

Background:

• Traditional graph reachability queries provide exact answers but are slow on large graphs.
• Approximate reachability queries offer a trade-off between query time and accuracy.
• Existing methods lack efficient solutions for learning approximate reachability on large attributed graphs.

Purpose of the Study:

• To propose ActiveReach, a novel framework for learning index structures to answer approximate reachability queries.
• To develop a method that effectively balances query time and accuracy for reachability analysis.
• To address the computational challenge of computing reachability for all training data in large graphs.

Main Methods:

• A two-phase framework focusing on embedding nodes in a reachability space.
• Phase 1: Creating reachability-aware node embeddings using node attributes and positional information.
• Phase 2: Incorporating new attributes and reachability labels, employing active learning to select data for reachability computation and enhance prediction.

Main Results:

• ActiveReach effectively learns approximate reachability for large attributed graphs.
• The active learning component efficiently selects data, improving reachability prediction performance.
• Experimental studies demonstrate the effectiveness of individual components within the ActiveReach framework.

Conclusions:

• ActiveReach provides an effective solution for approximate graph reachability queries on large-scale attributed graphs.
• The framework successfully balances query efficiency and accuracy through learned index structures.
• The active learning strategy is crucial for managing computational costs while maintaining predictive performance.