Learning Convolutional Neural Networks for Graphs

图卷积网络(Graph Convolutional Network),顾名思义,就是把图像处理中的卷积层运用到图上,图卷积网络能够处理如下两类问题[1]——

  • 给定一系列图作为训练集,可以训练出一个函数,该函数能够对未知的图进行分类或回归。
  • 给一张很大的图,学习图的表示函数(representation),并对于未知的图,推导出一些性质,诸如判断一个节点的类型,或是消失的边权等等。

回顾卷积神经网络,一个像素的特征值,来自于该层输入中,这个像素空间上临近点的像素特征。卷积神经网络的成功,从某种意义上来说,正式借助了这种隐含的空间特征。对于NLP也是同理

但是,对于大部分图而言,并没有这么好的特征可以利用,要将CNN迁移到图上面,需要解决这两个问题——

  • 找到一部分中间点,这些中间点将各自总结其邻域节点的特征。
  • 计算每个中间点临近图的正则化表示,即向量空间中的一个可以编码这个图的表示

定义术语

首先,需要定义图的节点的标号(labeling)和排名(ranking)。标号是一个给图上每个节点赋予一个权值的映射l(u)。而排序是将图上每一个节点权值从小到大排名后的排名映射r(u)。即满足对于任意u, v \in Vr(u)<r(v)当且仅当l(u)>l(v)

倘若r(u)函数和l(u)函数都是单射的,那么使用r(u)对于图中的节点编号进行置换,可以得到A^l(G)

上述定义其实是有道理的,假设l(u)是一个能够描述节点位置的函数,那么使用r(u)映射后的图G'可以用来当做一个图的标准化(Canonicalization)结构,这个结构能够用来比较两个图是否同构(Isomorphism)。

l(u)的最优化是NP的,但是可以构造出相对有效的l(u)——用距离“中心节点”的距离函数作为l(u),这里的“中心节点”是Node Sequence Selection函数的结果。

算法流程

Node Sequence Selection

为了对图进行卷积操作,我们需要定义卷积的stride和width。实际的算法非常简单,既然我们假设了r(u)函数能够有效刻画节点空间位置,那么在按照r(u)排序后的节点序列中,使用一个width大小stride步长的滑动窗口就可以完成节点的选择了。

Neighborhood Assembly

这一个步骤,试图对于上一步得到的若干个节点,分别找到一个大小为k的领域,这里用了简单的广度优先搜索算法。

Graph Normalization

图的规范化操作使用上一步得到的中心节点及其领域,重新对于领域中的节点进行标号,进而通过标号的排名进行置换,此时的图就相对规范了。由于距离不是单射函数,所以文中引用了NAUTY的方法,对于同样距离的节点进行区分。

Convolutional Architecture

文中的模型能够同时处理点权和边权,仅需要改变CNN的stride参数即可,具体实现略

评价

  • 没有公开代码,可复现性存疑
  • 适合作为GCN的入门论文,但和现在主流的GCN不一样。

引用

  1. Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs[C]//International conference on machine learning. 2016: 2014-2023.

云计算平台故障事件与相关研究

今年来,云计算平台发生了多起故障事件,而其原因的分析以及损失估计被很多学者所研究,本文将分别列举规模较大的云计算故障事件,并加以分析,同时对于学界对云计算研究成果做综述性摘要。

经典事件

阿里云停机事件

2019年3月3日,阿里巴巴旗下阿里云发布通报称,华北2地域可用区C部分ECS服务器(云服务器)等实例出现IO HANG(IO不响应),经紧急排查处理后已全部恢复。在这一次事件中,华北相当多的互联网公司的App、网站全部瘫痪,大量程序员、运维晚上从被窝里面被拉回公司修复错误。

Amazon AWS宕机事件

2017年2月28号,一名亚马逊程序员在调试系统的时候,试图运行了一条脚本,以删除少量用于支持支付操作的服务器。但是他输错了命令,导致大量服务器被删。而被误删除的服务器集群中中,有两个非常重要的系统,一个是存放了该区域所有托管服务器的配置信息,用于处理所有GET, LIST, PUT 和 DELETE 请求的。另一个系统用于负责新服务器的分配。

为了修复这个错误,亚马逊不得不重启整个系统。对于数年没有重启过得系统,而重启系统后的完整性和安全检查耗费了非常多的时间。最终导致了震惊全球的Amazon S3宕机4个小时事件。

事后,亚马逊官方网站通告总结事件时,称整个事件的触发程序,是一个支持快速移除大量负载的命令,而我们已经将该命令进行修改,使得负载的移除更加缓慢,并且增加了足够的安全保障,当某个节点移除后,其对应的子系统剩余节点没有能力负载所有的访问,则该移除指令不会被执行。另一方面,亚马逊也修改了恢复系统,保障在将来错误发生时,恢复不再会花费那么多时间。

Azure服务器中断事件

在2012年2月28日,微软旗下的Azure云服务器发生中断,事件长达7小时,据微软官方网站通告,该中断是由于服务中一处关于闰年的计算失误导致的。问题发生后,工程师快速部署了修复代码,并在7小时候恢复了服务器的访问。

其他安全事件

对于云服务商来说,设备故障并不是唯一的灾难,安全性漏洞更为致命,在7 Most Infamous Cloud Security Breaches文章中写道,微软、Dropbox、LinkedIn、Apple iCloud、Yahoo都曾经经历过安全漏洞攻击。并产生了很大的损失。

相关研究

硬件故障是云计算平台故障中,一个非常古老的错误,有非常非常多的研究者对他进行过研究。随着云计算的发展和商业化,硬件故障所扮演的角色也在随之改变,在Wang et al. (2017)的研究中指出,这些变化有积极和消极的方面。
从积极的方面来讲,云服务商的硬件设备的质量越来越可靠,更完备的故障检测系统也被部署到了云计算平台上,从而使得故障的恢复更加高效。而且由于云计算已经是一门非常成熟的技术,面对故障,运维也有足够的经验。这一系列变化都会倾向于降低对故障事件的损失。
但是从消极的方面来讲,由于市场扩大,更多的服务商进驻云计算行业,使得运营商们更加注重成本。自然而然的,他们就会倾向于使用那些不那么可靠,但是便宜的设备。

在Lloyds ́ and AIR (2018)的研究中,对于云服务商的故障损失进行了估计,发现美国的云服务商停机3-6天对应损失可达69亿美元。其中,制造业和零售批发业首当其冲,而其中损失最严重的是财富1000强的企业。

为了控制由于云服务商故障导致的损失,催生出一个全新的保险行业,叫做网络保险(cyber-insurance),这种保险以投保者的网站的可用性作为保险项目。不同于传统的保险,网络保险作为一个新兴的品种,仍没有被大众以及保险公司所接受,一方面是人们并没有正确的认识到服务商故障的损失,另一方面是网络保险有极大的系统性风险。一个云服务商的故障可能同时美国导致124万企业的经营遭受影响,此时大规模的赔偿可能会对保险公司带来巨大的流动性风险。

对于云服务的故障原因,文章Calvesbert (2018列举了四类原因:
1)环境原因,包括自然灾害在内的,无法认为控制的故障。
2)敌对攻击,主要包括竞争对手或黑客,尝试利用网络的漏洞进行攻击。
3)意外原因,指的是日常操作维护的误操作。
4)结构性故障,由于结构缺陷、资源耗尽而产生无法预知的错误。

当然,云平台的故障并不局限于大规模停机,频次更高的是局部性错误。在Chen et al. (2014)的研究中,将这类错误分类为应用错误、配置错误与云错误。配置错误是开发者认为错误配置、重复提交任务导致的,由于开发者在发现任务失败后倾向于重复提交,因此配置错误是所有故障中最多的。其次就是应用错误,其原因为云平台本身的资源限制、以及硬件错误。最后是云错误,其来源于运节点的添加、删除与维护。

总结

经过大规模的资源不可访问的问题的四种成因,意外原因和结构性故障居多,因为这两种成因比较难以估计,与之相反,敌对攻击和环境原因都会有非常完善的防范措施。因而在近现代的宕机事件中,并不常发生。同时可以发现,不同公司在事件后的翻译也不尽相同,这可以通过修复时间,以及事后事件成因分析看出。其中,亚马逊事件后,官方公布了详细的故障原因,以及改进措施,不仅给用户一个交代,也对我们的研究有很大帮助。反之另一些宕机事件,则官方没有公布调查结果,或是寥寥几句,给用户和研究者都带来 极大的困惑。

现有的研究从各个方面为降低云计算错误做了非常重要的贡献,包括损失估计,频率分析,原因总结等等。为云计算厂商优化平台算法,增加可靠性有非常积极的作用。

引用

  • AWSCloud. 2017. Summary of the Amazon S3 Service Disruption in the Northern Virginia (US-EAST-1) Region. (2017). https://aws.amazon.com/message/41926/.
  • Contel Bradford. 2018.7 Most Infamous Cloud Security Breaches.(2018).https://blog.storagecraft.com/7-infamous-cloud-security-breaches/.
  • Gian Calvesbert. 2018. Cloud Service Failure: 3 Things to Know. (2018). https://www.air-worldwide.com/Blog/Cloud-Service-Failure–3-Things-to-Know/.
  • Xin Chen, Charng-Da Lu, and Karthik Pattabiraman. 2014. Failure analysis of jobs in computeclouds: A google cluster case study. In2014 IEEE 25th International Symposium on SoftwareReliability Engineering. IEEE, 167–177.
  • Bill Laing. 2012. Windows Azure Service Disruption Update. (2012). https://azure.microsoft.com/en-us/blog/windows-azure-service-disruption-update/.
  • Lloyd ́s and AIR. 2018.Cloud Down: Impacts on the US economy. Technical Report.
  • G. Wang, L. Zhang, and W. Xu. 2017. What Can We Learn from Four Years of Data Center Hardware Failures?. In 2017 47th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN). 25–36. https://doi.org/10.1109/DSN.2017.26