通过具有联合权重学习和传播的集体分类，基于图的安全性和隐私分析

摘要

许多安全问题可以作为图分类问题来建模，其中图中的节点同时通过集体分类来进行分类。基于以下范例：为图的边缘分配权重，在加权的图中迭代的传播节点的信誉得分，并使用最终的信誉得分对节点进行分类。关键是分配边缘权重。关键的挑战是分配边缘权重，以便如果两个对应的节点具有相同的标签，则边缘的权重较大，否则，权重较小。尽管人们已经研究了集体分类并将其应用于安全和隐私问题，但是如何应对这一挑战仍然是一个悬而未决的问题。例如，大多数现有方法只是对所有边缘设置恒定的权重。

在这项工作中，我们提出了一个新颖的集体分类框架来应对这一长期挑战。首先，我们将学习权重公式化为一个优化问题，从而量化了我们旨在实现的最终声誉得分的目标。但是，由于最终声誉得分以非常复杂的方式取决于边缘权重，因此解决优化问题的计算难度很大。为了解决计算难题，我们建议共同学习边缘权重并传播信誉分数，这实际上是优化问题的一种近似解决方案。

1 介绍

collective classification【集体分类】：集体分类旨在同时对未标记的节点进行分类。

定义：给定1）可以是无向或有向的图，以及2）训练数据集，其由一些标记为正的节点和/或标记为负的节点组成，集体分类是同时将其余未标记的节点分类为正或负。对于不同的安全和隐私应用程序，节点表示不同的实体，边缘表示不同的关系，并且标签“正”和“负”具有不同的语义。

集体分类方法的三个关键步骤：1.根据训练数据集为图表中的每个节点分配优先信誉分数，例如负节点赋值为-1。   2. 将权重分配给图中的边，其中较大的边缘权重（u,v）表示u和v可能具有相同的标签。 3.迭代的在加权图中传播先验信誉分数，以获得每个节点的后验信誉分数，后验信誉分数用于对节点进行分类或排名。3中使用基于随机游走（random walk）的方法，或者是基于循环信任传播（loopy belief propagation）的方法。

如果u和v具有相同的标记，则边缘（u，v）被认为是同质的，否则被认为是异质的。步骤III中的传播要求同质边具有较大的权重，异质边具有较小的权重。

然而，现有方法面临关键限制：在步骤II中，它们将较小的权重分配给大量的均匀边缘，和/或将较大的权重分配给大量的异构边缘。具体而言，大多数现有方法都只是设置了较大的恒定权重到所有边缘，忽略同质和异质边缘之间的差异。一些方法[14]，[22]提出了使用从节点特征和图结构中提取的特征来学习边缘权重的方法。

SybilFuse [22]从图结构中为每个节点提取特征，使用训练数据集学习分类器以预测每个节点的先前信誉分数，并使用先前信誉分数来分配边缘权重。尤其是，如果边缘的两个节点更可能具有相同的标签，则该边缘的权重较大，其中节点的标签由其先前的信誉评分确定。由于先验信誉分数在确定节点的标签时不准确（否则，在步骤III中，我们无需传播先验信誉分数即可获得后验信誉分数），因此为大量异构边缘分配了较大的权重，而为大量同类节点分配了权重边缘分配较小的权重。

在这项工作中，我们提出了一个新的框架来学习基于图的安全性和隐私分析的边缘权重。我们的框架适用于基于RW和基于LBP的方法。我们的主要直觉是，通过集体分类方法得出的边缘权重和最终后验信誉得分应满足两个目标。首先，训练数据集中的标记正节点和标记负节点应具有较高和较低的后验信誉分数。其次，边缘权重和后信誉得分应保持一致。具体来说，我们使用最终的后信誉评分来预测节点的标签；如果预测边缘的两个节点具有相同的标签，则预测边缘是同质的；否则，预测边缘是异构的。边缘权重和后信誉评分之间的一致性意味着，预测为同质的边缘应具有较大的权重，而预测为异质的边缘应具有较小的权重。

我们将学习边缘权重公式化为使目标函数最小化，如果达到两个目标，则目标函数很小。为了解决计算难题，我们建议共同学习边缘权重并传播后验信誉分数，这可以看作是我们提出的优化问题的一种近似解决方案。我们的关键思想是在步骤III中迭代更新后验信誉分数，因此我们使用当前后验信誉分数而不是最终的后验信誉分数迭代地学习边缘权重。具体来说，给定第t次迭代中的后信誉分数，我们学习新的边缘权重，然后使用学习到的边缘权重更新第（t + 1）次迭代中的后信誉分数。我们旨在学习边缘权重以满足两个目标：1）对于训练数据集中的标记正节点和负节点，第（t + 1）次迭代中的后信誉得分应分别大和小。 2）学习到的边缘权重应该与第二次迭代中的后验信誉分数一致。在我们的框架下，学习边缘权重是有效的，因为第（t + 1）次迭代中训练数据集中节点的后验信誉分数仅取决于训练数据集中节点的边缘权重。

2 相关工作

基于RW的方法：

首先先给节点分配先验信誉分数，例如正节点为1，负节点为-1。在步骤II中，大多数基于RW的方法只是对所有边缘设置恒定的权重。在步骤III中，不同的方法使用不同的随机游走来传播信誉分数。 例如，在无向图中，RW-N，RW-P和RW-FLW迭代地将节点的当前信誉得分分配给其邻居，并且节点将从其邻居分配的信誉得分求和，作为其新的信誉得分。 特别地，节点u与邻居v共享其信誉分数的一部分，其中该分数是边缘权重除以u的加权度。 在有向图上，RW-N [26]（或RW-P [12]，[27]）与每个出站（或入站）邻居共享节点u当前信誉分数的一部分，其中该部分是边缘权重除以 用u的传出（或传入）边的总权重。 RW-B适用于无向图，并使用不同的随机游走传播信誉分数。 具体来说，分数是边缘权重除以v的加权度，而不是u在u与邻居v共享其信誉得分时的权重。

基于LBP的方法

在步骤III中，这些基于LBP的方法利用标准LBP或优化的LBP来在加权图中传播信誉分数。优化的LBP比标准LBP效率高一个数量级。在无向图上，优化的LBP将节点u的信誉分数的一部分与其邻居v共享，其中分数只是边缘权重，而节点将其先前信誉分数与邻居共享的信誉分数相加，作为新节点每次迭代中的信誉得分。在有向图上，如果有向边（u，v）和（v，u）都存在，则优化的LBP像在无向图上一样，将节点u的信誉得分与其邻居v共享。但是，当u仅与输出边连接v时，仅当u当前的信誉得分为负时，优化的LBP才会像无向图中那样与v共享u的信誉得分。当u仅与传入边缘连接v时，优化的LBP仅在u当前信誉分数为正时才与v共享u信誉分数。

3 问题定义

集体分类问题：我们得到一张图G=(V,E)，还得到一个训练数据集，含有标记的节点，集体分类是对图中未标记的节点进行分类。

我们还使用鲁棒性来标记训练数据集中的噪声，以评估集体分类方法。特别地，假设训练数据集中的节点的α％被错误地标记，并且一种方法使用这种训练数据获得β的AUC。然后，我们说该方法在标签噪声处于α％的水平时具有β的鲁棒性。

4 架构

我们首先总结最先进的集体分类方法。 特别地，后验信誉分数本质上是方程组的解决方案。 然后，我们将学习优势权重公式化为一个优化问题，从而根据后验信誉分数对目标进行量化。 然而，解决该优化问题在计算上具有挑战性，因为后声誉分数以非常复杂的方式取决于边缘权重。 最后，我们介绍了交替学习边缘权重和传播后验信誉分数的策略。 我们的策略是解决我们制定的优化问题的一种近似解决方案。

A. 背景

在最新的集体分类中，后验信誉分数是以下方程组的解决方案： p=f(q,W,p) 其中p是后验信誉分数，q是前验信誉分数，w是权重矩阵。

基于LBP的方法在无向图上：

设是u的先验信誉分数，设置为 1（正）0（未知）-1（负）。

如果节点u和v无连接，则w=0.否则==w(u,v).

w(u,v)的值取决于u,v具有相同标签的可能性有多大。 w(u,v) >0，表示相同标签，否则不同标签。

函数f如下：f(q,W,p)=q+Wp.  后验信誉得分首先初始化为初始分数，然后迭代更新后验分数，直至收敛。 = f(q,W,). 是第t次迭代的后验分数，w在迭代过程中固定不变，直至收敛，如果后验分数为正，则节点为正。

基于LBP的方法在有向图上的定义略。

B. 把学习边缘权重作为优化问题

我们的主要直觉是，通过集体分类方法得出的边缘权重和后期信誉得分应满足以下两个目标。

•目标1.训练数据集中标记为阳性的节点和标记为阴性的节点的后信誉评分应分别为大和小。

•目标2。边缘权重和后信誉得分应保持一致。特别是，我们使用后验信誉评分来预测节点标签；如果两个对应的节点被预测为具有相同的标签，则该边缘将被预测为同质，否则该边缘将被预测为异构。一致性意味着预测为均匀的边缘应具有正权重，而预测为异构的边缘应具有负权重。

量化目标1：给定训练数据集L，我们将目标1量化为找到边缘权重矩阵W，以使标记节点及其标记的后信誉评分之间的差异最小。形式上，我们的目标是找到一个最小化以下函数的边缘权重矩阵W：

边缘权重矩阵W

其中pl是节点l的后验信誉得分，yl是节点l在训练数据集中的标签，其中u = 1（如果u为正），yl = -1，否则。在机器学习中，L（W）被称为训练数据集的损失函数。

量化目标2：当1）预测u和v具有相同标签（即pupv> 0）且Wuv为正，或2）u和v时，边缘权重wuv与u和v的后信誉得分一致预测具有不同的标签（即pupv <0），并且Wuv为负。因此，为了捕获目标2，我们旨在学习权重矩阵W，该函数将最大化以下功能：

权重矩阵w

其中C(W)测量给定矩阵的一致性。

C. 联合权重学习与传播

略

实验  略

讨论 

1. 将基于LBP的集体分类方法推广到了没有训练数据集的情况下。他们的关键思想是从图中随机采样一些节点并将其视为标记节点（其中一些节点标记不正确，即训练数据有噪声）。然后，他们对采样的训练数据应用基于LBP的方法。由于基于LBP的方法对训练数据中的某些噪声具有鲁棒性，因此它们会多次重复采样过程，并设计一些方法来选择标签噪声较小的采样试验。【55】

2。 与其他基于图的分类方法相比：基于图的分类问题也可以通过图嵌入方法和图卷积网络（GCN）来解决[56]。特别地，图嵌入方法首先通过无监督学习来学习节点的特征向量，然后基于特征向量和训练数据集学习分类器（在我们的实验中为逻辑回归分类器）。