Robust graph convolutional networks with directional graph adversarial training

Graph convolutional networks (GCNs), an emerging type of neural network model on graphs, have presented state-of-the-art performance on the node classification task. However, recent studies show that neural networks are vulnerable to the small but deliberate perturbations on input features. And GCNs could be more sensitive to the perturbations since the perturbations from neighbor nodes exacerbate the impact on a target node through the convolution. Adversarial training (AT) is a regularization technique that has been shown capable of improving the robustness of the model against perturbations on image classification. However, directly adopting AT on GCNs is less effective since AT regards examples as independent of each other and does not consider the impact from connected examples. In this work, we explore AT on graph and propose a graph-specific AT method, Directional Graph Adversarial Training (DGAT), which incorporates the graph structure into the adversarial process and automatically identifies the impact of perturbations from neighbor nodes. Concretely, we consider the impact from the connected nodes to define the neighbor perturbation which restricts the perturbation direction on node features towards their neighbor nodes, and additionally introduce an adversarial regularizer to defend the worst-case perturbations. In this way, DGAT can resist the impact of worst-case adversarial perturbations and reduce the impact of perturbations from neighbor nodes. Extensive experiments demonstrate that DGAT can effectively improve the robustness and generalization performance of GCNs. Specially, GCNs with DGAT can provide better performance when there are rare few labels available for training.

     

Xheal: a localized self-healing algorithm using expanders

We consider the problem of self-healing in reconfigurable networks e.g., peer-to-peer and wireless mesh networks. For such networks under repeated attack by an omniscient adversary, we propose a fully distributed algorithm, Xheal, that maintains good expansion and spectral properties of the network, while keeping the network connected. Moreover, Xheal does this while allowing only low stretch and degree increase per node. The algorithm heals global properties like expansion and stretch while only doing local changes and using only local information. We also provide bounds on the second smallest eigenvalue of the Laplacian which captures key properties such as mixing time, conductance, congestion in routing etc. Xheal has low amortized latency and bandwidth requirements. Our work improves over the self-healing algorithms Forgiving tree [PODC 2008] and Forgiving graph [PODC 2009] in that we are able to give guarantees on degree and stretch, while at the same time preserving the expansion and spectral properties of the network.     

DEX: self-healing expanders

We present a fully-distributed self-healing algorithm dex that maintains a constant degree expander network in a dynamic setting. To the best of our knowledge, our algorithm provides the first efficient distributed construction of expanders—whose expansion properties hold deterministically—that works even under an all-powerful adaptive adversary that controls the dynamic changes to the network (the adversary has unlimited computational power and knowledge of the entire network state, can decide which nodes join and leave and at what time, and knows the past random choices made by the algorithm). Previous distributed expander constructions typically provide only probabilistic guarantees on the network expansion which rapidly degrade in a dynamic setting; in particular, the expansion properties can degrade even more rapidly under adversarial insertions and deletions. Our algorithm provides efficient maintenance and incurs a low overhead per insertion/deletion by an adaptive adversary: only \(O(\log n)\) rounds and \(O(\log n)\) messages are needed with high probability (n is the number of nodes currently in the network). The algorithm requires only a constant number of topology changes. Moreover, our algorithm allows for an efficient implementation and maintenance of a distributed hash table on top of dex  with only a constant additional overhead. Our results are a step towards implementing efficient self-healing networks that have guaranteed properties (constant bounded degree and expansion) despite dynamic changes.     

基于改进投影梯度下降算法的图卷积网络投毒攻击

图神经网络在面对节点分类、链路预测、社区检测等与图数据处理相关的任务时,容易受到对抗性攻击的安全威胁。基于梯度的攻击方法具有有效性和高效性,被广泛应用于图神经网络对抗性攻击,高效利用攻击梯度信息与求取离散条件下的攻击梯度是攻击离散图数据的关键。提出基于改进投影梯度下降算法的投毒攻击方法。将模型训练参数看作与扰动相关的函数,而非固定的常数,在模型的对抗训练中考虑了扰动矩阵的影响,同时在更新攻击样本时研究模型对抗训练的作用,实现数据投毒与对抗训练两个阶段的结合。采用投影梯度下降算法对变量实施扰动,并将其转化为二进制,以高效利用攻击梯度信息,从而解决贪婪算法中时间开销随扰动比例线性增加的问题。实验结果表明,当扰动比例为5%时,相比Random、DICE、Min-max攻击方法,在Citeseer、Cora、Cora＿ml和Polblogs数据集上图卷积网络模型被该方法攻击后的分类准确率分别平均降低3.27%、3.06%、3.54%、9.07%,在时间开销和攻击效果之间实现了最佳平衡。     

Fully dynamic biconnectivity in graphs

We present an algorithm for maintaining the biconnected components of a graph during a sequence of edge insertions and deletions. It requires linear storage and preprocessing time. The amortized running time for insertions and for deletions isO(m ^2/3 ), wherem is the number of edges in the graph. Any query of the form ‘Are the verticesu andv biconnected?’ can be answered in timeO(1). This is the first sublinear algorithm for this problem. We can also output all articulation points separating any two vertices efficiently. If the input is a plane graph, the amortized running time for insertions and deletions drops toO(√n logn) and the query time isO(log² n), wheren is the number of vertices in the graph. The best previously known solution takes timeO(n ^2/3 ) per update or query.     

The robustness of stability under link and node failures

In the area of communication systems, stability refers to the property of keeping the amount of traffic in the system always bounded over time. Different communication system models have been proposed in order to capture the unpredictable behavior of some users and applications. Among those proposed models the adversarial queueing theory (aqt) model turned out to be the most adequate to analyze an unpredictable network. Until now, most of the research done in this field did not consider the possibility of the adversary producing failures on the network structure. The adversarial models proposed in this work incorporate the possibility of dealing with node and link failures provoked by the adversary. Such failures produce temporal disruptions of the connectivity of the system and increase the collisions of packets in the intermediate hosts of the network, and thus the average traffic load. Under such a scenario, the network is required to be equipped with some mechanism for dealing with those collisions.In addition to proposing adversarial models for faulty systems we study the relation between the robustness of the stability of the system and the management of the queues affected by the failures. When the adversary produces link or node failures the queues associated to the corresponding links can be affected in many different ways depending on whether they can receive or serve packets, or rather that they cannot. In most of the cases, protocols and networks containing very simple topologies, which were known to be universally stable in the aqt model, turn out to be unstable under some of the newly proposed adversarial models. This shows that universal stability of networks is not a robust property in the presence of failures.     

基于非鲁棒特征的图卷积神经网络对抗训练方法

图卷积神经网络可以通过图卷积提取图数据的有效信息,但容易受到对抗攻击的影响导致模型性能下降。对抗训练能够用于提升神经网络鲁棒性,但由于图的结构及节点特征通常是离散的,无法直接基于梯度构造对抗扰动,而在模型的嵌入空间中提取图数据的特征作为对抗训练的样本,能够降低构造复杂度。借鉴集成学习思想,提出一种基于非鲁棒特征的图卷积神经网络对抗训练方法VDERG,分别针对拓扑结构和节点属性两类特征,构建两个图卷积神经网络子模型,通过嵌入空间提取非鲁棒特征,并基于非鲁棒特征完成对抗训练,最后集成两个子模型输出的嵌入向量作为模型节点表示。实验结果表明,提出的对抗训练方法在干净数据上的准确率平均提升了0.8%,在对抗攻击下最多提升了6.91%的准确率。     

Intrinsic graph topological correlation for graph convolutional network propagation

Recently, Graph Convolutional Networks (GCNs) and their variants become popular to learn graph-related tasks. These tasks include link prediction, node classification, and node embedding, among many others. In the node classification problem, the input is a graph with some labeled nodes and the features associated with these nodes and the objective is to predict the unlabeled nodes. While the GCNs have been successfully applied to this problem, some caveats that are inherited from classical deep learning remain unsolved. One such inherited caveat is that, during classification, GCNs only consider the nodes that are a few neighbors away from the labeled nodes. However, considering only a few steps away nodes could not effectively exploit the underlying graph topological information. To remedy this problem, the state-of-the-art methods leverage the network diffusion approaches, such as personalized PageRank and its variants, to fully account for the graph topology. However, these approaches overlook the fact that the network diffusion methods favour high degree nodes in the graph, resulting in the propagation of the labels to the unlabeled,hub nodes. In order to overcome bias, in this paper, we propose to utilize a dimensionality reduction technique, which is conjugate with personalized PageRank. Testing on four real-world networks that are commonly used in benchmarking GCNs’ performance for the node classification task, we systematically evaluate the performance of the proposed methodology and show that our approach outperforms existing methods for wide ranges of parameter values. Since our method requires only a few training epochs, it releases the heavy training burden of GCNs. The source code of the proposed method is freely available at https://github.com/mustafaCoskunAgu/ScNP/blob/master/TRJMain.m.     

Rendezvous in networks in spite of delay faults

Two mobile agents, starting from different nodes of an unknown network, have to meet at a node. Agents move in synchronous rounds using a deterministic algorithm. Each agent has a different label, which it can use in the execution of the algorithm, but it does not know the label of the other agent. Agents do not know any bound on the size of the network. In each round an agent decides if it remains idle or if it wants to move to one of the adjacent nodes. Agents are subject to delay faults: if an agent incurs a fault in a given round, it remains in the current node, regardless of its decision. If it planned to move and the fault happened, the agent is aware of it. We consider three scenarios of fault distribution: random (independently in each round and for each agent with constant probability \(0<p<1\)), unbounded adversarial (the adversary can delay an agent for an arbitrary finite number of consecutive rounds) and bounded adversarial (the adversary can delay an agent for at most c consecutive rounds, where c is unknown to the agents). The quality measure of a rendezvous algorithm is its cost, which is the total number of edge traversals. For random faults, we show an algorithm with cost polynomial in the size n of the network and polylogarithmic in the larger label L, which achieves rendezvous with very high probability in arbitrary networks. By contrast, for unbounded adversarial faults we show that rendezvous is not possible, even in the class of rings. Under this scenario we give a rendezvous algorithm with cost \(O(n\ell )\), where \(\ell \) is the smaller label, working in arbitrary trees, and we show that \(\varOmega (\ell )\) is the lower bound on rendezvous cost, even for the two-node tree. For bounded adversarial faults, we give a rendezvous algorithm working for arbitrary networks, with cost polynomial in n, and logarithmic in the bound c and in the larger label L.     

基于MapReduce的图结构聚类算法

图结构聚类（SCAN）是一种著名的基于密度的图聚类算法。该算法不仅能够找到图中的聚类结构,而且还能发现图中的Hub节点和离群节点。然而,随着图数据规模越来越大,传统的SCAN算法的复杂度为O（m^1.5）（m为图中边的条数）,因此很难处理大规模的图数据。为了解决SCAN算法的可扩展性问题,本文提出了一种新颖的基于MapReduce的海量图结构聚类算法MRSCAN。具体地,我们提出了一种计算核心节点,以及两种合并聚类的MapReduce算法。最后,在多个真实的大规模图数据集上进行实验测试,实验结果验证了算法的准确性、有效性,以及可扩展性。     

Reconstructing a Minimum Spanning Tree after Deletion of Any Node

Abstract. Updating a minimum spanning tree (MST) is a basic problem for communication networks. In this paper we consider single node deletions in MSTs. Let G=(V,E) be an undirected graph with n nodes and m edges, and let T be the MST of G . For each node v in V , the node replacement for v is the minimum weight set of edges R(v) that connect the components of T-v . We present a sequential algorithm and a parallel algorithm that find R(v) for all V simultaneously. The sequential algorithm takes O(m log n) time, but only O(m α (m,n)) time when the edges of E are presorted by weight. The parallel algorithm takes O(log ² n) time using m processors on a CREW PRAM.     

Centralized asynchronous broadcast in radio networks

We study asynchronous broadcasting in packet radio networks. A radio network is represented by a directed graph, in which one distinguished source node stores a message that needs to be disseminated among all the remaining nodes. An asynchronous execution of a protocol is a sequence of events, each consisting of simultaneous deliveries of messages. The correctness of protocols is considered for specific adversarial models defined by restrictions on events the adversary may schedule. A protocol specifies how many times the source message is to be retransmitted by each node. The total number of transmissions over all the nodes is called the work of the broadcast protocol; it is used as complexity measure. We study computational problems, to be solved by deterministic centralized algorithms, either to find a broadcast protocol or to verify the correctness of a protocol, for a given network. The amount of work necessary to make a protocol correct may have to be exponential in the size of network. There is a polynomial-time algorithm to find a broadcast protocol for a given network. We show that certain problems about broadcasting protocols for given networks are complete in NP and co-NP complexity classes.     

A new approach for approximating node deletion problems

We present a new approach for approximating node deletion problems by combining the local ratio and the greedy multicovering algorithms. For a function , our approach allows to design a 2+max_v∈V(G)logf(v) approximation algorithm for the problem of deleting a minimum number of nodes so that the degree of each node v in the remaining graph is at most f(v). This approximation ratio is shown to be asymptotically optimal. The new method is also used to design a 1+(log2)(k−1) approximation algorithm for the problem of deleting a minimum number of nodes so that the remaining graph contains no k-bicliques.     

一种面向图神经网络的图重构防御方法

近年来,图神经网络在图表示学习领域中取得了较好表现广泛应用于日常生活中,例如电子商务、社交媒体和生物学等.但是研究表明,图神经网络容易受到精心设计的对抗攻击迷惑,使其无法正常工作.因此,提高图神经网络的鲁棒性至关重要.已有研究提出了一些提高图神经网络鲁棒性的防御方法,然而如何在确保模型主任务性能的前提下降低对抗攻击的攻击成功率仍存在挑战.通过观察不同攻击产生的对抗样本发现,对抗攻击生成的对抗连边所对应的节点对之间通常存在低结构相似性和低节点特征相似性的特点.基于上述发现,提出了一种面向图神经网络的图重构防御方法GRD-GNN,分别从图结构和节点特征考虑,采用共同邻居数和节点相似度2种相似度指标检测对抗连边并实现图重构,使得重构的图结构删除对抗连边,且添加了增强图结构关键特征的连边,从而实现有效防御.最后,论文在3个真实数据集上展开防御实验,验证了GRD-GNN相比其他防御方法均能取得最佳的防御性能,且不影响正常图数据的分类任务.此外,利用可视化方法对防御结果做解释,解析方法的有效性.     

基于节点相似性的图注意力网络表示学习模型

图注意力网络(GAT)通过注意力机制聚合节点的邻居信息以提取节点的结构特征,然而并没有考虑网络中潜在的节点相似性特征。针对以上问题,提出了一种考虑网络中相似节点的网络表示学习方法NSGAN。首先,在节点层面上,通过图注意力机制分别学习相似网络和原始网络的结构特征;其次,在图层面上,将两个网络对应的节点嵌入通过基于图层面的注意力机制聚合在一起,生成节点最终的嵌入表示。在三个数据集上进行节点分类实验,NSGAN比传统的图注意力网络方法的准确率提高了约2%。     

Lifetime maximizing dynamic energy efficient routing protocol for multi hop wireless networks

Energy efficiency is recognized as a critical problem in wireless networks. Many routing schemes have been proposed for finding energy efficient routing paths with a view to extend lifetime of the networks – however it has been observed that the energy efficient path depletes quickly. Further, an unbalanced distribution of energy among the nodes may cause early death of nodes as well as network. Hence, balancing the energy distribution is a challenging area of research in wireless networks. In this paper we propose an energy efficient scheme that considers the node cost of nodes for relaying the data packets to the sink. The node cost considers both the remaining energy of the node as well as energy efficiency. Using this parameter, an energy efficient routing algorithm is proposed which balances the data traffic among the nodes and also prolongs the network lifetime. Simulation shows that proposed routing scheme improves energy efficiency and network lifetime than widely used methods viz., Shortest Path Tree (SPT) and Minimum Spanning Tree (MST) based PEDAP, Distributed Energy Balanced Routing (DEBR) and Shortest Path Aggregation Tree Based Routing Protocol.     

The design and analysis of an efficient load balancing algorithm employing the symmetric balanced incomplete block design

In order to maintain load balancing in a distributed network, each node should obtain workload information from all the nodes in the network. To accomplish this, this processing requires O(v²) communication complexity, where v is the number of nodes. First, we present a new synchronous dynamic distributed load balancing algorithm on a (v, k + 1, 1)-configured network applying a symmetric balanced incomplete block design, where v = k² + k + 1. Our algorithm designs a special adjacency matrix and then transforms it to (v, k + 1, 1)-configured network for an efficient communication. It requires only communication complexity and each node receives workload information from all the nodes without redundancy since each link has the same amount of traffic for transferring workload information. Later, this algorithm is revised for distributed networks and is analyzed in terms of efficiency of load balancing.     

Fast message dissemination in random geometric networks

We analyze information dissemination in random geometric networks, which consist of n nodes placed uniformly at random in the square ${[0,\sqrt{n}]^{2}}$ . In the corresponding graph two nodes u and v are connected by a (directed) edge, i.e., u is an (incoming) neighbor of v, if and only if the distance between u and v is smaller than the transmission radius assigned to u. In order to study the performance of distributed communication algorithms in such networks, we adopt here the ad-hoc radio communication model with no collision detection mechanism available. In this model the topology of network connections is not known in advance. Also a node v is capable of receiving a message from its neighbor u if u is the only (incoming) neighbor transmitting in a given step. Otherwise a collision occurs prompting interference that is not distinguishable from the background noise in the network. First, we consider networks modeled by random geometric graphs in which all nodes have the same radius ${r > \delta \sqrt{\log n}}$ , where δ is a sufficiently large constant. In such networks, we provide a rigorous study of the classical communication problem of distributed gossiping (all-to-all communication). We examine various scenarios depending on initial local knowledge and capabilities of network nodes. We show that in many cases an asymptotically optimal distributed O(D)-time gossiping is feasible, where D stands for the diameter of the network. Later, we consider networks in which the transmission radii of the nodes vary according to a power law distribution, i.e., any node is assigned a transmission radius r > r _min according to probability density function ρ(r) ~ r ^?α . More precisely, ${\rho(r) = (\alpha-1)r_{\min}^{\alpha-1} r^{-\alpha}}$ , where ${\alpha \in (1, 3)}$ and ${r_{\min} > \delta \sqrt{\log n}}$ with δ being a large constant. In this case, we develop a simple broadcasting algorithm that runs in time O(log log n) (i.e., O(D)) always surely, and we show that this result is asymptotically optimal. Finally, we consider networks in which any node is assigned a transmission radius r > c according to the probability density function ρ(r) =  (α?1)c ^α-1 r ^?α , where α is a constant from the same range as before and c is a constant. In this model the graph is usually not strongly connected, however, there is one giant component with Ω(n) nodes, and there is a directed path from each node of this giant component to every other node in the graph. We assume that the message which has to be disseminated is placed initially in one of the nodes of the giant component, and every node is aware of its own position in ${[0,\sqrt{n}] \times [0,\sqrt{n}]}$ . Then, we show that there exists a randomized algorithm which delivers the broadcast message to all nodes in the network in time O(D . (log log n)²), almost always surely, where D stands for the diameter of the giant component of the graph. One can conclude from our studies that setting the transmission radii of the nodes according to a power law distribution brings clear advantages. In particular, one can design energy efficient radio networks with low average transmission radius, in which broadcasting can be performed exponentially faster than in the (extensively studied) case where all nodes have the uniform low transmission power.     

图对抗攻击研究综述

将深度学习用于图数据建模已经在包括节点分类、链路预测和图分类等在内的复杂任务中表现出优异的性能,但是图神经网络同样继承了深度神经网络模型容易在微小扰动下导致错误输出的脆弱性,引发了将图神经网络应用于金融、交通等安全关键领域的担忧。研究图对抗攻击的原理和实现,可以提高对图神经网络脆弱性和鲁棒性的理解,从而促进图神经网络更广泛的应用,图对抗攻击已经成为亟待深入研究的领域。介绍了图对抗攻击相关概念,将对抗攻击算法按照攻击策略分为拓扑攻击、特征攻击和混合攻击三类;进而,归纳每类算法的核心思想和策略,并比较典型攻击的具体实现方法及优缺点。通过分析现有研究成果,总结图对抗攻击存在的问题及其发展方向,为图对抗攻击领域进一步的研究和发展提供帮助。     

基于改进图注意机制的网络嵌入方法研究及应用

网络已被广泛用作抽象现实世界系统以及组织实体之间关系的数据结构;网络嵌入模型是将网络中的节点映射为连续向量空间表示的强大工具;基于图卷积（Graph convolutional neural, GCN）的网络嵌入方法因受其模型迭代过程参数随机优化和聚合函数的影响,容易造成原始节点特征信息丢失的问题;为有效提升网络嵌入效果,针对于图神经网络模型在网络嵌入中节点表征学习的局限性,提出了一种基于二阶邻域基数保留策略的图注意力网络SNCR-GAT（Second-order Neighborhood Cardinality Retention strategy Graph attention network）,通过聚合二阶邻域特征基数的方式,解决网络节点潜在特征学习过程中重要信息保留问题;通过在节点分类和可视化两个网络嵌入应用任务上进行实验,结果表明,SNCR-GAT模型在网络嵌入上的性能表现相比较基准方法更具优越性。