  Tenuous subgraph finding aims to detect a subgraph with few social
interactions and weak relationships among nodes. Despite significant efforts
have been made on this task, they are mostly carried out in view of
graph-structured data. These methods depend on calculating the shortest path
and need to enumerate all the paths between nodes, which suffer the
combinatorial explosion. Moreover, they all lack the integration of
neighborhood information. To this end, we propose a novel model named Graph
Neural Network with Motif-aware for tenuous subgraph finding (GNNM), a
neighborhood aggregation based GNNs framework which can capture the latent
relationship between nodes. Specially, we design a GNN module to project nodes
into a low dimensional vector combining the higher-order correlation within
nodes based on a motif-aware module. And then design greedy algorithms in
vector space to obtain a tenuous subgraph whose size is greater than a
specified constraint. Particularly, considering existing evaluation indicators
cannot capture the latent friendship between nodes, we introduce a novel
Potential Friend(PF) concept to measure the tenuity of a graph from a new
perspective. Experimental results on the real-world and synthetic datasets
demonstrate that our proposed method GNNM outperforms existing algorithms in
efficiency and subgraph quality.
