【CIKM 2019论文】从头开始学习识别BC最高节点：一种新的图神经网络方法（Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach）

论文题目： Learning to Identify High Betweenness Centrality Nodes from Scratch: A Novel Graph Neural Network Approach

论文摘要：

Betweenness centrality (BC)是网络分析中广泛使用的一种中心性度量，它试图通过最短路径的比例来描述网络中节点的重要性。它是许多有价值的应用的关键，包括社区检测和网络拆除。由于时间复杂度高，在大型网络上计算BC分数在计算上具有挑战性。许多基于采样的近似算法被提出以加速BC的估计。然而，这些方法在大规模网络上仍然需要相当长的运行时间，并且它们的结果对网络的微小扰动都很敏感。

在这篇论文中，我们主要研究如何有效识别图中BC最高的top k节点，这是许多网络应用程序所必须完成的任务。与以往的启发式方法不同，我们将该问题转化为一个学习问题，并设计了一个基于encoder-decoder的框架作为解决方案。具体来说，encoder利用网络结构将每个节点表示为一个嵌入向量，该嵌入向量捕获节点的重要结构信息。decoder将每个嵌入向量转换成一个标量，该标量根据节点的BC来标识节点的相对rank。我们使用pairwise ranking损失来训练模型，以识别节点的BC顺序。通过对小规模网络的训练，该模型能够为较大网络的节点分配相对BC分数，从而识别出高排名的节点。在合成网络和真实世界网络上的实验表明，与现有的baseline相比，我们的模型在没有显著牺牲准确性的情况下大大加快了预测速度，甚至在几个大型真实世界网络的准确性方面超过了最先进的水平。

论文作者：

Muhao Chen在加州大学洛杉矶分校获得了计算机科学博士学位，目前是丹·罗斯教授的博士后研究员。广泛研究了机器学习和自然语言处理的主题，包括关系学习、序列建模、词汇语义和图表示学习。最近的研究全面扩展了表示学习模型，以捕获多关系数据的各种属性，包括可转移性、不确定性和逻辑属性。