核心速递
图神经网络的鲁棒性;
- 从非马尔可夫约简到马尔可夫动力学：有噪声的投票模型的老化的情况;
- 基于Transformer架构的实现虚假新闻态势检测挑战任务（FNC-1）迁移学习;
- 基于机器学习方法通过Facebook墙检测用户的可疑行;
- 用于计算保留异构多层网络结构和语义社区的一种高效框架;
- 用于社会网络的自适应混合算法从单独成员中选择群体;
- 统计分析和随机利率模型用于评估未来减缓气候变化的影响;
原文标题：Certifiable Robustness to Graph Perturbations地址：http://arxiv.org/abs/1910.14356作者：Aleksandar Bojchevski, Stephan Günnemann摘要：尽管人们对图形神经网络的兴趣与日俱增，但很少有人去验证和改进它们的鲁棒性。鉴于最近的研究结果表明，它们极易受到对图形结构和节点属性的敌对攻击，这一点更令人担忧。我们提出了一种方法来研究一类包含图神经网络和标签/特征传播的一般模型对图扰动的鲁棒性。通过利用与PageRank和马尔科夫决策过程的连接，我们的算法可以有效地（并且在许多威胁模型下准确地）计算。此外，我们还研究了在保持或提高干净预测精度的同时，增加鲁棒节点数的鲁棒训练过程。
G2SAT：学习生成SAT公式
G2SAT: Learning to Generate SAT Formulas http://arxiv.org/abs/1910.13445Jiaxuan You, Haoze Wu, Clark Barrett, Raghuram Ramanujan, Jure Leskovec摘要：布尔可满足性（SAT）问题是典型的NP-complete 问题，是计算机科学的基础，在规划、验证和定理证明中有着广泛的应用。开发和评估实用的SAT解算器依赖于对一组现实世界基准公式的广泛经验测试。然而，这种现实世界中SAT公式的可用性是有限的。虽然这些基准公式可以用综合生成的公式来增强，但现有的方法却大量基于人工，不能同时捕获真实世界SAT实例所展示的广泛特征。在这项工作中，我们提出了G2SAT，这是第一个学习从给定的输入公式集生成SAT公式的深度生成框架。我们的关键见解是，SAT公式可以转化为潜在的二分图表示，我们使用特定的的深度生成神经网络建模。我们证明G2SAT可以生成与给定的真实SAT实例非常相似的SAT公式，这可以通过图形度量和SAT解算器行为来衡量。此外，我们还展示了我们的合成SAT公式可用于改善SAT解算器在现实世界基准上的性能，这为SAT解算器的持续发展和对其性能的深入理解提供了新的机会。Rank-size law, financial inequality indices and gain concentrations by cyclist teams. The case of a multiple stage bicycle race, like Tour de France http://arxiv.org/abs/1910.13803摘要：本文基于财务收益计算秩和法（RSL）研究了在最著名的男性多阶段专业自行车赛——环法自行车赛，结束时对参赛队的财务分配。应用RSL，本文发现财务分配是双曲型的，具有一个非常简单的衰减指数-1。然而，财务收益的分布却出乎意料地不服从帕累托因子稀疏原理。接下来，本文考虑了八个不等式指标：熵、赫希曼-赫芬达尔指数、泰尔指数、皮埃特拉-胡佛指数、基尼指数、罗森布卢斯指数、变异系数和浓度指数，以勾勒多样性测度这些指标与它们的意义之间的联系。研究结果表明，技能与团队策略对财务收益分配有显著的贡献。事实上，金钱奖励规则与舞台难度相结合，可能会影响或加强（或恶化）团体比赛中纯粹的运动性。Kinetic modelling of multiple interactions in socio-economic systemshttp://arxiv.org/abs/1910.13843 Giuseppe Toscani, Andrea Tosin, Mattia Zanella摘要：不同于经典的稀薄气体动力学理论，气体分子之间的微观相互作用被描述为二元碰撞，多智能体系统中社会经济现象的建模自然需要考虑在各种情况下个体之间的多重相互作用。本文收集和讨论了一些与经济和赌博活动有关的例子。特别地，我们着重于多重相互作用的线性化策略，这大大简化了此类系统的动力学描述，同时保持了它们的所有基本聚集特征，包括平衡分布。Group Centrality Maximization for Large-scale Graphshttp://arxiv.org/abs/1910.13874 Eugenio Angriman, Alexander van der Grinten, Aleksandar Bojchevski, Daniel Zügner, Stephan Günnemann, Henning Meyerhenke摘要：节点中心度测度的研究是网络分析的一个重要方面。自然地，这种中心性度量被推广到节点群；对于常用的度量，证明了最中心群的问题是NP-hard的。因此，最近引入了近似算法来最大化群中心度。由于群接近度中心性在大型网络上相当慢，我们引入GED-Walk中心性，一种受Katz中心性启发的新中心性度量。与封闭性和中间性相比，它考虑任何长度游走，而不是最短路径，较短的游走具有更高的贡献。我们的算法（i）近似地逼近给定群的GED-Walk中心性得分，并且（ii）近似地逼近具有最高GED-Walk中心性得分群（被证明是NP-hard问题）。在几个真实数据集上的实验表明，GED-Walk算法获得的分数提高了一般图挖掘任务（如集合分类和图级分类）的性能。经验运行时间的评估表明，与群间近似和群大小相比，最大化GED-Walk中心性比群接近度中心性近似快两个数量级。对于具有几千万个边缘的图，近似的GED-Walk中心性最大化通常需要不到一分钟。此外，实验表明，最大化算法与输入图的大小和群大小成线性关系。
原文标题：
Interplay between Topology and Social Learning over Weak Graphs
http://arxiv.org/abs/1910.13905Vincenzo Matta, Virginia Bordignon, Augusto Santos, Ali H. Sayed摘要：本文考虑一个分布式社会学习问题。我们主要研究弱连通图，其中网络被分为发送部分和接收部分。主体收集的数据可能是异构的，这意味着不同的子网络可能由不同的统计模型管理。例如，一些子网络可能故意从一个假的假设生成数据，以便影响其他主题。这项工作的重点是两步扩散策略，其中每个主体：i）使用其私有数据单独更新其信念函数；ii）通过对其邻居的对数信念的线性组合求幂来计算新的信念函数。本文有两个主要贡献。首先，我们检查主体在弱连通图（社会学习问题）上学习什么。我们得到了不同智能体的极限信念的闭式分析公式，这使得我们可以更详细地研究每个智能体的学习性能。这些公式揭示了主体的检测能力和网络拓扑如何相互作用，从而影响主体的渐近信念。特别是，这些公式允许我们预测是否和何时可能出现领导-跟随行为，其中一些发送主体可以通过强迫他们选择特定的假设来控制接收主体的思想。其次，我们考虑揭示主体学习方式的双重或反向学习问题：给定在接收主体处收集的信念流，我们希望发现任何发送组件对该接收主体的全局影响（拓扑学习问题）。观察到了社会学习和拓扑学习之间一种显著的、可能出乎意料的相互作用：给定H假设和S发送部件，当
时拓扑学习是可行的，后者只是一个必要条件，然后我们研究了两类有用问题的拓扑学习的可行性。分析表明，在发送子网的统计模型中，保证可靠的拓扑学习的一个关键因素是足够的多样性。
从非马尔可夫约简
到马尔可夫动力学：
有噪声的投票模型的老化的情况
Reduction from non-Markovian to Markovian dynamics: The case of aging in the noisy-voter model http://arxiv.org/abs/1910.13976 Antonio F. Peralta, Nagi Khalil, Raul Toral摘要：我们研究与记忆相关的二元状态动力学，重点是噪声投票者模型。这是一个非马尔可夫过程，如果我们将种群的二进制状态集视为描述变量，或者如果我们将年龄与保持相同状态的时间相结合，作为描述的一部分。我们证明，在某些情况下，该模型可以简化为一个客观的马尔可夫过程，在这个过程中，种群的年龄分布迅速平衡到一个准稳态，而系统的全局状态是不平衡的。这一客观马尔可夫过程与非线性有噪声的选民模型具有相同的现象学性质，并且我们在这两个扩展的有噪声的选民模型之间建立了明显的并行性。Elites, communities and the limited benefits of mentorship in electronic musichttp://arxiv.org/abs/1908.10968Milan Janosov, Federico Musciotto, Federico Battiston, Gerardo Iñiguez摘要：虽然在创造性职业中成功的出现，例如音乐，已经被广泛研究，但是个人成功和协作之间的联系还没有完全揭示出来。在这里，我们的目标是填补这一空白，通过分析纵向数据的共同发布和指导模式，数据来源于流行的电子音乐艺术家出现在年度排名前100名的DJ杂志。我们发现，虽然这个人气排行榜公布了100个名字，但随着时间的推移，只有前20名是稳定的，显示了电子音乐精英的锁定效应。基于顶级音乐人的时间协同发布网络，我们提取出一个具有电子音乐产业特征的多元化社区结构。这些艺术家群体在时间上是分离的，依次围绕着领军音乐家形成，代表着音乐流派的变化。我们发现，音乐社区形成的一个主要驱动力是导师制：进入前100名的音乐家中，约有一半在进入排行榜之前就已经接受过现任领导人物的导师制。我们还发现，受试者不太可能进入前20名，但比那些没有接受指导的人有更高的期望最佳排名。这意味着指导有助于提高人才，但成为一个历史明星更需要更多努力。我们的研究结果揭示了成功与合作在电子音乐中相互交织的作用，突出了塑造电子音乐艺术精英的形成机制。 Phase Transitions for Detecting Latent Geometry in Random Graphshttp://arxiv.org/abs/1910.14167 Matthew Brennan, Guy Bresler, Dheeraj Nagaraj摘要：具有潜在几何结构的随机图是社会网络和生物网络的常用模型，其应用范围从网络用户分析到电路设计。这些图在计算机科学、概率论和统计学中也具有纯粹的理论意义。关于这些模型的一个基本的初始问题是：这些随机图何时被它们的潜在几何所分割，何时它们与没有潜在结构的简单模型？我们讨论了两个研究最深入的具有潜在几何的随机图模型——随机交集图和随机几何图。研究表明，组合变元、直接耦合和信息不等式应用的混合。具有潜在几何的随机图与G（n，p）之间总变差距离的上界通常不是组合的，也不是信息论的，而这种相互作用对于我们的上界的尖锐性是必不可少的。 RLINK: Deep Reinforcement Learning for User Identity Linkage http://arxiv.org/abs/1910.14273 Xiaoxue Li, Yanan Cao, Yanmin Shang, Yangxi Li, Yanbing Liu, Jianlong Tan摘要：用户身份链接是通过不同的社交网络（SN）识别同一用户身份的任务。以往的工作主要是通过估计不同SN中的两个身份之间的成对相似性，预测身份对的标签或根据相似性得分、选择最相关的身份对来解决这一问题。然而，这些方法大多忽略了先前匹配恒等式的结果，这可能有助于后续匹配步骤中的链接。为了解决这个问题，我们将用户身份链接转化为序列决策问题，并提出了一个强化学习模型，从全局的角度优化链接策略。我们的方法充分利用了社会网络结构和历史匹配身份，并探索了当前匹配对后续决策的长期影响。我们进行了不同类型的数据集的实验，结果表明，我们的方法比其他最新的方法取得了更好的性能。
基于Transformer架构的
实现虚假新闻态势检测
挑战任务（FNC-1）迁移学习
Transfer Learning from Transformers to Fake News Challenge Stance Detection (FNC-1) Task http://arxiv.org/abs/1910.14353摘要：本文报道了虚假新闻挑战第一阶段（FNC-1）态势检测任务的改进结果。这种性能上的提高是由于基于Transformer架构的大型语言模型的泛化能力，在过去两年中，这些模型被建立、训练并公开发布。具体来说（1）改进了FNC-1模型，增加了输入序列的BERT语句嵌入作为模型特征，（2）在FNC-1扩展数据集上对BERT、XLNet和RoBERTa变换器进行了优化，得到了FNC-1任务的最新结果。
基于机器学习方法通过
Facebook墙检测用户的可疑行为
原文标题：
A machine-learning approach to Detect users’ suspicious behaviour through the Facebook wall
http://arxiv.org/abs/1910.14417Aimilia Panagiotou, Bogdan Ghita, Stavros Shiaeles, Keltoum Bendiab摘要：Facebook代表了当前社交媒体的事实选择，改变了社交关系的本质。通过这个平台运行的越来越多的个人信息公开暴露了用户行为和社会趋势，从而允许通过传统的情报收集技术（如OSINT（开源智能情报））来聚合数据。本文提出了一种新的方法，通过开源智能情报技术（OSINT）和机器学习技术来检测和诊断整个Facebook用户心理的变化。我们正在使用N个游戏图表来聚合用户情绪和视图的光谱，这些图表随着时间的推移显示出明显的变化，并通过长期收集得到验证。我们假设所提出的方法可以被安全组织用来理解和评估用户心理，然后利用这些信息来预测内部威胁或防止内部攻击。 Bots, elections, and social media: a brief overview http://arxiv.org/abs/1910.01720摘要： 机器人是在社会化媒体操作软件控制账户，目前已被用于操纵和欺骗。我们研究了机器人的特点和活动与重大政治事件的关联，包括在不同国家的选举。在本文中，我们总结了2016年和2018年美国总统和中期选举以及2017年法国总统选举背景下机器人操作的影响结果。 Constant State of Change: Engagement Inequality in Temporal Dynamic Networks http://arxiv.org/abs/1910.01722Hadar Miller, Osnat Mokryn摘要： 近年来，复杂相互作用系统时间变化引起了研究领域的广泛关注。从组织和在线社区的集体动态到信息和假新闻的传播等，时间动态是理解复杂系统基础。在本工作中，我们量化了动态复杂交互系统(建模为网络)参与程度。首先，我们关注交互网络，包括交互动态与拓扑动态耦合，如在线消息、论坛和电子邮件。然后我们定义了两个指标来捕捉参与时间水平:时间网络(边缘)强度指数和时间优势不平等指数。另我们吃惊的是，这些测量对于大多数被测量网络是固定的，而忽略网络规模大小在时间上巨大波动。而且超过80%指数值周变化小于10%。最后，虽然这些指标在网络时间演化过程中是稳定的，但在不同网络则不同，分类器可很好地确定这些指标所属网络。然而在安然公司解体前一年管理层邮件往来中，我们发现例外，两个指数在整个调查期间都表现出很高的波动性。
Graph Mask Convolutional Network http://arxiv.org/abs/1910.01735 Bo Jiang, Beibei Wang, Jin Tang, Bin Luo摘要：图卷积网络(GCNs)是图数据表示和学习的重要研究对象。GCNs中的图卷积运算通常可以看作是特征聚集/传播和变换的组合。现有的GCNs通常在一个固定邻域图上进行特征聚合，其中每个节点通过聚合其所有邻居特征表示来计算其表示(由其自身表示产生偏差)。然而，这种固定聚合策略并不能保证基于GCN图数据学习中是最优，同时也会受到一些图数据结构噪声影响，如不正确或不需要的边缘连接。为了解决这些问题，我们提出了一种新的图掩罩卷积网络(GmCN)，该网络节点可以自适应地选择其特征集合中的最优邻居，从而更好地服务于GCN学习。更重要的是，GmCN可以通过一个统一正则化框架进行理论解释，在此基础上，我们推导出一个简单更新算法，来自适应地确定GmCN训练过程中的最优掩码。最后，我们在多个数据集上实验证明了该算法的有效性。
Context-Aware Graph Attention Networks http://arxiv.org/abs/1910.01736Bo Jiang, Leiling Wang, Jin Tang, Bin Luo摘要： 图神经网络(GNNs)是图数据表示和学习的重要研究对象。但是目前GNNs一般只对节点特征表示进行上下文感知学习，而忽略了对边(权重量)表示的学习。在本文中，我们提出一个新的统一GNN模型，称为上下文感知自适应图形关注网络(CaGAT)。CaGAT目的是进一步通过利用不同边缘之间上下文关系来学习每个图边缘上下文感知关注的表示。特别是CaGAT以统一方式对节点特征表示和边(权)表示协作进行并进行上下文感知学习，因此可以提高二者在网络训练中性能。随后，我们将CaGAT应用于半监督学习任务，在几个基准数据集上实验结果表明了CaGAT的有效性和优势。
用于计算保留异构多层网络
结构和语义社区的一种高效框架
An Efficient Framework for Computing Structure- And Semantics-Preserving Community in a Heterogeneous Multilayer Networkhttp://arxiv.org/abs/1910.01737 Abhishek Santra, Kanthi Sannappa Komar, Sanjukta Bhowmick, Sharma Chakravarthy摘要： 多层网络或MLN(也称为多路复用或网络的网络)被广泛用于对具有多个实体和特征类型以及相关关系数据集进行建模和分析。虽然社区概念被广泛用于聚合分析，但是对MLN缺乏一个结构和语义的定义。保留原始MLN结构和实体关系对于详细深入分析非常重要。此外，高效计算对于大量分析也是至关重要的。在本文中，我们介绍了一种结构保留MLN社区定义，以及一种使用解耦方法进行高效计算的框架。这种解耦方法将各个层社区组合起来，形成一个串行k-community，用于MLN中连接k层。此外，我们提出一种跨层配对社区新算法，并引入了一些权重指标，以利用参与社区特征从两层组合社区。除了定义之外，我们提出方法还有许多需要的特性。其特性包括:i)利用现有单图社区检测算法，ii)引入几个社区概念定制的权度量，iii)一种使用二分图对社区进行配对的新算法，iv)在广泛使用的IMDb和DBLP数据集上用实验验证了社区计算及其效率。SMP Challenge: An Overview of Social Media Prediction Challenge 2019http://arxiv.org/abs/1910.01795 Bo Wu, Wen-Huang Cheng, Peiye Liu, Zhaoyang Zeng, Jiebo Luo摘要： “SMP挑战”旨在为社交多媒体上大量数据发现新的预测任务，并寻找优秀的研究团队。通过社交多媒体数据(如照片、视频或新闻)进行预测，不仅有助于我们对未来做出更好的战略决策，还探索了先进的预测学习及各种问题和场景分析方法，如多媒体推荐、广告系统、时尚分析等。首先，在ACM多媒体2019年SMP挑战中，我们引入一种新颖的预测任务——时间流行度预测，其重点是在上传之前预测社交媒体feed中新在线帖子的未来交互或吸引力(按点击、浏览量或喜好等)。另外，我们还收集并发布一个大规模SMPD基准测试，其中包含来自69K用户的480K篇文章。综之，本文定义了挑战问题，对数据集进行概述，给出数据和注释丰富信息统计数据，设计了挑战时间流行预测准确性和相关评价的指标。
用于社会网络的自适应混合
算法来从单独成员中选择群体
An adaptive hybrid algorithm for social networks to choose groups with independent membershttp://arxiv.org/abs/1910.01875 Parham Hadikhani, Pooria Hadikhani摘要：在社交网络中选择具有独立成员的委员会是群体选择的一个问题，委员会的独立性是选择主要标准。独立性是根据群体成员之间社会距离来计算的。虽然解决社交网络中群体选择问题解决方案有很多，比如目标集的选择或者社区检测，但是只有一种解决方案是基于群体成员独立性来选择委员会成员作为群体绩效的衡量标准。本文提出了一种新的自适应混合算法来选择最佳委员会成员，使委员会独立性最大化。该算法是粒子群算法与两种局部搜索算法的结合。本工作的目标是将探索与开发相结合，以提高所提算法的效率并获得最优解。此外，为了将局部搜索算法与粒子群优化算法相结合，在搜索过程中利用有效选择机制选择合适局部搜索算法与粒子群优化算法相结合。最后，实验仿真结果与已有成功的元启发式算法进行了比较。比较结果表明，该方法至少提高了21%的群体独立性。
An adaptive hybrid algorithm for social networks to choose groups with independent members http://arxiv.org/abs/1910.01875 Parham Hadikhani, Pooria Hadikhani摘要： 电力系统长期投资规划模型通常会根据一组成本假设得到一个最优解。然而，通常有许多接近最优的选择，因为其它吸引人的特性，如社会接受度而脱颖而出。了解许多具有成本效益替代方案中存在特征，可以增强政策建议，并认识到结构模型的不确定性。本文应用模型生成的替代(MGA)方法，系统地探索了一个完全可再生的欧洲电力系统模型的近最优可行空间。在考虑复杂时空模式的同时，我们允许发电、存储和传输基础设施同时扩容，以满足线性化多周期最优的潮流。结果存在多种类似的昂贵但技术上多样化的解决方案。0.5%成本偏差已经提供了大量可能投资方案。然而，无论是海上还是陆上风能以及带储氢和输电网络的加强投资取决于将成本控制在最佳水平10%以内是至关重要的。
The Role of Active Leaders in Opinion Formation on Social Networkshttp://arxiv.org/abs/1910.01897Fabian Baumann, Igor. M Sokolov, Melvyn Tyloo摘要： 意见故意两极化和共识受控变化对任何自由社会都是潜在的有害过程。在一个简单的建设性意见交换模型框架内，我们分析研究了主动领导者在社交网络上整体意见动态中的作用。就像狂热者持有僵化观点一样，人们认为积极的领导者会遵循既定的个人议程。为此，我们描述了单个活跃的领导个体改变主流共识的能力，以及在两个对立意见领袖情况下出现的社会两极分化。同时，我们定义了观点一致性及其极化率的度量，并将这些度量与系统修正拉普拉斯量联系起来。我们将形式主义应用到合成和经验网络中，发现尽管在小世界主义中极化率降低，而在明显的社区结构中则有利于极化，但在共识变化中观点一致性则相反。
A new method for quantifying network cyclic structure to improve community detection http://arxiv.org/abs/1910.01921Behnaz Moradi-Jamei, Heman Shakeri, Pietro Poggi-Corradini, Michael J. Higgins摘要： 网络中社区一个显著特征是，周期在社区内比在社区之间更为普遍。因此，对这些群体的探测可以通过结合循环结构局部“丰富度”的测量来得到帮助。在这篇论文中，我们引入了更新非回溯随机游动(RNBRW)来量化这种结构。RNBRW为每条边赋予一个权值，该权值等于不回溯随机游走以该边完成一个循环的概率。因此，具有较大权值的边可能被认为对循环的形成更为重要。值得注意的是，由于个人随机游走可以并行执行，所以即使对于大型图，RNBRW的权值也可以很快地估计出来。仿真结果表明，通过RNBRW对边缘进行预加权可以显著提高常用社区检测算法的性能。我们的结果表明，RNBRW对于在稀疏图中检测社区尤其有挑战性的情况特别有效。
统计分析和随机利率模型
用于评估未来减缓气候变化的影响
Statistical analysis and stochastic interest rate modelling for valuing the future with implications in climate change mitigation http://arxiv.org/abs/1910.01928 Josep Perelló, Miquel Montero, Jaume Masoliver, J. Doyne Farmer, John Geanakoplos摘要： 未来高贴现率有利于针对当前支出不作为现象，而较低贴现率则建议采取更直接政治行动。在全球经济中，解决这一关键问题可能方法是，对名义利率和通货膨胀采取历史时间序列，然后构建实际利率，最后根据特定随机模型得到最终贴现率。在所有国家许多时期，普遍观察到通货膨胀高于名义利率实际长期负利率。这一特点使我们选择了统计物理学中一个著名模型——奥恩斯坦-乌伦贝克模型，作为基本动态工具。在这个模型中，实际利率会随机波动，甚至会变为负值，即使它们趋向于回归到正平均值。通过覆盖14个国家数百年历史，我们提出了不同设想。我们发现，只有4个国家长期贴现率为正，而其他10个国家长期贴现率为负。即使有人反对已经发生恶性通货膨胀的国家，我们结果也支持考虑低折现率的必要性。这14个国家提供结果大大增加了应对气候变化减缓等全球行动的优先事项。
来源：网络科学研究速递
审校：赵子鸣、郭治青
编辑：张爽
声明：Arxiv文章摘要版权归论文原作者所有，由本人进行翻译整理，未经同意请勿随意转载。本系列在微信公众号“网络科学研究速递”（微信号netsci）和个人博客 https://www.complexly.me （提供RSS订阅）进行同步更新。
集智俱乐部QQ群｜877391004
商务合作及投稿转载｜swarma@swarma.org
◆ ◆ ◆
搜索公众号：集智俱乐部
加入“没有围墙的研究所”
让苹果砸得更猛烈些吧！