曲率
数学
采样(信号处理)
图形
诱导子图同构问题
组合数学
算法
里希曲率
数学优化
离散数学
计算机科学
折线图
几何学
电压图
计算机视觉
滤波器(信号处理)
作者
Dong Wook Shu,Youjin Kim,Junseok Kwon
标识
DOI:10.1016/j.patcog.2023.109475
摘要
This paper introduces a subgraph sampling method based on curvature to train large-scale graphs via mini-batch training. Owing to the difficulty in sampling globally optimal subgraphs from large graphs, we sample the subgraphs to minimize the distributional metric with combinatorial sampling. In particular, we define a combinatorial metric that distributionally measures the similarity between an original graph and all possible node and edge combinations of the subgraphs. Further, we prove that the subgraphs sampled using the probability model proportional to the discrete Ricci curvature (i.e., Ollivier-Ricci curvatures) of the edges can minimize the proposed metric. Moreover, as accurate calculation of the curvature on a large graph is challenging, we propose to use a localized curvature considering only 3-cycles on the graph, suggesting that this is a sufficiently approximated curvature on a sparse graph. We also show that the probability models of conventional sampling methods are related to coarsely approximated curvatures with no cycles, implying that the curvature is closely related to subgraph sampling. The experimental results confirm the feasibility of integrating the proposed curvature-based sampling method into existing graph neural networks to improve performance.
科研通智能强力驱动
Strongly Powered by AbleSci AI