10月21日下午，“统计大讲堂”系列讲座第一百三十三讲举行。本次讲座采用线下讲座与在线直播相结合的方式，讲座以“Graph Analysis from the Perspective of Real-World Graph Properties”为主题，由北京大学博士后刘钰主讲。统计学院教师、应用统计科学研究中心研究员王晓军、李静萍、李扬、尹建鑫、许王莉等老师参与讲座。统计学院教授吕晓玲主持本次讲座。

吕晓玲首先介绍了报告人的相关信息。刘钰是北京大学王选计算机研究所全职博士后，2018年于中国人民大学信息学院获得工学博士学位（计算机应用技术），主要研究方向为大规模图算法的分析优化、复杂图生成模型和算法、时序图神经网络模型等。

刘钰首先从历史上的“哥尼斯堡七桥问题”出发，引出了“真实图”（Real-World Graph）的概念，并简要介绍了它在社交网络、地理绘图、分子结构等方面的应用。由于经典的算法设计和分析理论在处理大数据时代真实应用图数据时往往存在实际计算效率低下的问题，因此近年来真实图的结构性质等逐渐受到关注，并以此为出发点研究适合大图计算的算法分析设计理论。

刘钰首先以节点相似度计算这一经典图计算问题为例，分别介绍如何从算法设计、算法分析和问题建模等三个层面提升图分析的理论和实际效率。真实图的相似度度量可以归纳为两种——局部相似度和全局相似度，后者与当今大热的图神经网络较为相似，且较前者计算效果更好。研究全局相似度需要引入随机游走的概念：两个点的相似度可以等价的由满足某种特定条件的随机游走来描述。已有计算方法通过确定性计算或利用蒙特卡洛算法模拟随机游走，但存在显著的计算效率问题。刘钰从算法设计的角度介绍了同时结合确定性计算和随机游走两种思想的算法设计思路，这种算法效率高，且通过使用真实图节点度的幂律分布假设可得到亚线性复杂度的算法，从复杂度理论角度解释了算法的高效性。

由于在实际应用中，通常不需要计算所有点的相似度，只需要寻找前k位相似度的点；而已有方法都采用先计算所有点相似度再进行排序，造成多余的计算。因此刘钰通过相似度计算的随机游走解释，介绍了基于多臂**（MAB）的top-k查询建模方法；并通过该建模从理论上刻画了top-k相似度查询的难度。虽然已有算法理论研究针对MAB提出了一系列基于采样和置信区间剪枝的理论最优解，但在大规模图数据上计算时仍存在实际代价过大的弊端，对此刘钰进一步引入适合大规模MAB的采样策略及基于采样策略融合的两阶段查询算法，保证了大规模图数据上最优的理论计算效率和很高的实际计算效率。

最后，刘钰介绍了新兴的图表式学习方法。图表示学习将图中的每个点映射成d维空间的一个向量，再通过机器学习算法实现节点分类、链接预测等经典图分析任务。该技术在现今社交网络、分子合成等领域已有成功实践。刘钰简介了早期的基于矩阵分解的降维技术和基于随机游走的图表示学习方法、介绍了近年大热的图卷积网络模型，以及其面向真实图数据动态变化这一性质（时序图数据）的前沿研究和社交网络、传染病学等方面的具体应用。在大数据时代，利用真实图的一系列性质进行问题建模和算法设计对面向真实应用的分析效率和效果至关重要。相比于传统统计学，图分析更关注非欧几里得数据和实际效率，但其使用的方法（如采样、MAB等）与传统统计学有异曲同工之妙。

在提问交流环节，刘钰耐心地解答提问，并进一步解释MAB模型的相关计算方法，在排疑解惑的同时进一步拓展了真实图模型。

此次讲座通过多种图分析方法的对比和改进体现真实图分析的理论进步和实践优化。此后统计大讲堂还将陆续推出多场精彩讲座，敬请关注。