Characterizing the Influence of Topology on Graph Learning Tasks
This work addresses a fundamental gap in graph learning for researchers and practitioners, though it appears incremental as it builds on existing GNN frameworks.
The paper tackles the problem of understanding how graph topology influences the performance of learning models on downstream tasks by proposing a metric called TopoInf, which measures compatibility between topology and task objectives, and demonstrates its effectiveness through analysis and experiments.
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.