Subgraph nomination: Query by Example Subgraph Retrieval in Networks
This addresses structural retrieval tasks in domains like social and biological networks, but appears incremental as it formalizes an existing problem with user feedback.
The paper tackles the problem of retrieving similarly interesting subgraphs from a network using example subgraphs, introducing the subgraph nomination inference task with a user-in-the-loop framework that incorporates light supervision. It examines the effect of user-supervision on performance analytically and through real and simulated data examples, though no concrete numbers are provided in the abstract.
This paper introduces the subgraph nomination inference task, in which example subgraphs of interest are used to query a network for similarly interesting subgraphs. This type of problem appears time and again in real world problems connected to, for example, user recommendation systems and structural retrieval tasks in social and biological/connectomic networks. We formally define the subgraph nomination framework with an emphasis on the notion of a user-in-the-loop in the subgraph nomination pipeline. In this setting, a user can provide additional post-nomination light supervision that can be incorporated into the retrieval task. After introducing and formalizing the retrieval task, we examine the nuanced effect that user-supervision can have on performance, both analytically and across real and simulated data examples.