Characterizing the Influence of Topology on Graph Learning Tasks
Kailong Wu Yule Xie Jiaxin Ding Yuxiang Ren Luoyi Fu Xinbing Wang Chenghu Zhou
Graph neural networks (GNN) have achieved remarkable success in a wide range
of tasks by encoding features combined with topology to create effective
representations. However, the fundamental problem of understanding and
analyzing how graph topology influences the performance of learning models on
downstream tasks has not yet been well understood. In this paper, we propose a
metric, TopoInf, which characterizes the influence of graph topology by
measuring the level of compatibility between the topological information of
graph data and downstream task objectives. We provide analysis based on the
decoupled GNNs on the contextual stochastic block model to demonstrate the
effectiveness of the metric. Through extensive experiments, we demonstrate that
TopoInf is an effective metric for measuring topological influence on
corresponding tasks and can be further leveraged to enhance graph learning.