提出XNQ方法,高效精准估算大规模图中各类节点比例。
Efficient quantification on large-scale networks
- 结合随机递归GNN嵌入与期望最大化算法,实现无监督灵活量化
- 在多种网络上显著优于现有方法,准确率提升明显
- 训练速度最快快100倍,适合大规模图数据应用
网络量化(NQ)旨在估计未标记节点子集中各类节点的比例。当存在先验概率偏移时,仅先分类再统计的方法无法有效应对。相比非关系量化,NQ需具备更强的灵活性以捕捉多样连接模式,抵御异质性挑战,并可扩展至大规模网络。为此,我们提出XNQ,融合随机递归图神经网络生成的无监督节点嵌入,与一种量化感知的期望最大化算法,对校准后的节点分类器输出概率进行鲁棒调整。在广泛评估中,包括通过详尽消融实验验证设计选择,结果表明XNQ持续且显著超越现有最佳方法,确立了该任务的新基准。此外,相较于基于图学习的方法,XNQ训练速度最高提升10倍至100倍。
原文摘要 · Abstract (English)
Network quantification (NQ) is the problem of estimating the proportions of nodes belonging to each class in subsets of unlabelled graph nodes. When prior probability shift is at play, this task cannot be effectively addressed by first classifying the nodes and then counting the class predictions. In addition, unlike non-relational quantification, NQ demands enhanced flexibility in order to capture a broad range of connectivity patterns, resilience to the challenge of heterophily, and scalability to large networks. In order to meet these stringent requirements, we introduce XNQ, a novel method that synergizes the flexibility and efficiency of the unsupervised node embeddings computed by randomized recursive Graph Neural Networks, with an Expectation-Maximization algorithm that provides a robust quantification-aware adjustment to the output probabilities of a calibrated node classifier. In an extensive evaluation, in which we also validate the design choices underpinning XNQ through comprehensive ablation experiments, we find that XNQ consistently and significantly improves on the best network quantification methods to date, thereby setting the new state of the art for this challenging task. XNQ also provides a training speed-up of up to 10x-100x over other methods based on graph learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。