  Knowledge graphs (KGs) are widely acknowledged as incomplete, and new
entities are constantly emerging in the real world. Inductive KG reasoning aims
to predict missing facts for these new entities. Among existing models, graph
neural networks (GNNs) based ones have shown promising performance for this
task. However, they are still challenged by inefficient message propagation due
to the distance and scalability issues. In this paper, we propose a new
inductive KG reasoning model, MStar, by leveraging conditional message passing
neural networks (C-MPNNs). Our key insight is to select multiple query-specific
starting entities to expand the scope of progressive propagation. To propagate
query-related messages to a farther area within limited steps, we subsequently
design a highway layer to propagate information toward these selected starting
entities. Moreover, we introduce a training strategy called LinkVerify to
mitigate the impact of noisy training samples. Experimental results validate
that MStar achieves superior performance compared with state-of-the-art models,
especially for distant entities.
