网络推理中采样偏差的量化方法探讨

12770Towards Quantifying Sampling Bias in Network Inference0Lisette Espín-Noboa �0GESIS & University of Koblenz-LandauLisette.Espin@gesis.org0Claudia Wagner GESIS & Universityof Koblenz-LandauClaudia.Wagner@gesis.org0Fariba Karimi GESIS & University ofKoblenz-LandauFariba.Karimi@gesis.org0Kristina Lerman USC InformationSciences Institutelerman@isi.edu0摘要0关系推断利用网络中实体和链接之间的关系来从小样本中推断出关于网络的信息。当无法获取网络的全局信息或难以获得时，通常会使用这种方法。然而，从小样本进行推断的可靠性如何？网络的采样方式应该如何选择，对推断误差有何影响？网络的结构如何影响采样策略？我们通过系统地研究网络采样策略和样本大小对网络关系推断准确性的影响来回答这些问题。为此，我们生成了一系列合成网络，其中节点具有二进制属性和可调节的同质性水平。正如预期的那样，在异质网络中，即使最初只标记了网络的小样本，我们仍然可以获得很好的准确性，而采样策略无关紧要。令人惊讶的是，对于同质网络，表现良好的采样策略会导致较大的推断误差。这一发现表明，网络结构对关系分类的影响比以前认为的更加复杂。0ACM参考格式：Lisette Espín-Noboa，Claudia Wagner，FaribaKarimi和Kristina Lerman。2018年。Towards Quantifying Sampling Biasin Network Inference。在WWW '18Companion：2018年网络会议伴侣，2018年4月23日至27日，法国里昂。ACM，纽约，美国，9页。https://doi.org/10.1145/3184558.319156701 引言0网络构成了现代生活的基础设施，通过数万亿的交易，将数十亿人、组织和设备连接在一起。解决当今的问题和做出关键决策越来越需要挖掘这些网络中存储的海量数据。由于网络的规模和复杂性，分析师通常很难获得网络和其中包含的数据的全局视图，这往往是成本高昂的。相反，他们可以使用关系机器学习方法从部分样本中推断出关于网络的信息，例如从已知的几个种子节点的类别推断出未标记节点的类别。0� 这项工作是她在2017年在USC-ISI的暑期实习的一部分。0本文发表在知识共享署名4.0国际许可证（CC BY4.0）下。作者保留在个人和公司网站上传播作品的权利，并附上适当的归属。WWW '18Companion，2018年4月23日至27日，法国里昂，© 2018IW3C2（国际万维网会议委员会），根据知识共享CC BY 4.0许可证发布。ACM ISBN978-1-4503-5640-4/18/04。https://doi.org/10.1145/3184558.31915670这种推断有多可靠？种子的选择对推断误差有多大影响？网络结构对采样策略有多大影响？在这项工作中，我们通过系统地研究关系推断过程中潜在的偏差来源来解决其中一些问题：网络结构、采样、关系分类和集体推断。为了实现这个目标，我们深入研究了采样策略如何可能存在偏差，以及这种偏差在推断过程中何时可能对其有利或不利。对采样如何影响关系分类性能的新见解可能会导致新的无偏策略。0关系分类。关系分类器通过网络中已知节点的标签向未知标签进行推断。分类性能通过仅知道少数种子节点的标签时能够恢复所有节点的标签的程度来衡量。在[9]中，作者概述了集体分类的两个主要组成部分，即集体推断方法和关系分类器。他们评估了各种组件的选择和组合以及用于训练方法的标记数据百分比对分类准确性的影响。他们的结果表明，在不同情况下有两组优选技术，即最初已知少量标签和已知较多标签时，而且链接选择在分类性能中起到与传统特征选择类似的重要作用。然而，作者没有探索网络结构如何影响集体分类方法的性能。Sen等人通过将四种集体分类算法与不考虑网络的仅内容分类器进行比较来填补这一空白，这些网络在链接密度和同质性上有所不同[12]。他们发现，增加链接密度可以提高集体分类的性能，并且在所有密度水平上明显优于仅内容分类器。此外，同质性，即指具有相似标签的节点相互连接的趋势，进一步帮助集体分类器优于仅内容分类器，除了非常低的同质性水平（<0.1），在这种情况下，仅内容分类器的性能稍微更好。虽然这项工作单独探讨了同质性和网络密度，但最近的研究探讨了这些特征如何共同影响性能。在[17]中，作者表明随着网络的同质性和链接密度的增加，关系分类的准确性也会增加。与我们的研究类似，该研究侧重于节点具有单一二进制属性的平衡网络。然而，仅通过随机节点采样选择用于训练的子图。0矿山属性网络WWW 2018，2018年4月23日至27日，法国里昂CBDEAFDEAFCBCEAFBDCDEAFB12780采样偏差。先前的研究表明，通过各种网络爬虫收集的网络样本的估计结果在全球[8]和本地网络统计[14]方面可能不准确。最近的两篇论文表明，标记种子节点初始样本的选择也会影响属性推断[1，15]。然而，这些研究没有探讨网络的属性（如同质性）如何影响种子选择和分类性能。研究发现和贡献。在这项工作中，我们专注于属性推断任务，并探讨网络中集体推断的准确性如何取决于创建初始标记节点集的策略。总之，我们的主要贡献有三个方面：（i）使用合成和实证网络，我们提供了同质性在集体推断过程中起决定性作用的证据：首先，当网络是中性的（即节点随机连接而不考虑其类别标签）时，没有任何采样技术能够超越随机分类器。其次，异质性网络可以通过任何采样策略进行简单分类，并且需要至少5％的随机节点训练样本才能实现无偏分类。最后，对于同质性网络，一些适用于异质性网络的采样策略需要更大的样本。只有通过首先选择最高度节点构建样本的方法才能在同质性和异质性区域中使用小样本实现良好的分类性能。（ii）我们表明链接密度在某些条件下影响分类性能：首先，将低度节点排名靠前的采样方法受益于具有高链接密度的网络。其次，具有高链接密度的同质性网络需要更大的训练样本进行边缘、混合度和雪球采样。（iii）我们讨论了采样策略对关系分类使用集体推断的影响，并证明类别不平衡可能对推断产生负面影响。本文的剩余部分组织如下：第2节介绍背景知识。第3节描述实验、数据集和结果，第4节进行讨论。最后，我们在第5节中提出未来的工作和结论。02 背景0在这项工作中，我们主要关注不同采样技术对关系分类的影响。我们描述了（i）感兴趣的网络，（ii）分类过程和（iii）使用的网络采样技术。02.1 带属性网络0我们正式定义如下：设 G = (V, E, F) 是一个带属性的无权图，其中 V = (v1, ..., vn)是一组节点，E = {(vi, vj)} ∈ (V × V) 是一组有向或无向边，F = (f1, ..., fn)是一组特征向量。每个特征向量 fi = (fi[1], ..., fi[t]) T 将节点 vi 映射到 t个（二进制、数值或分类）属性。类标签定义为 c ∈t，并表示在分类过程中要推断的属性。链接密度被描述为 G中潜在连接的实际连接的比例，即 d = | E |0对于有向网络的 N (N -0d = 2 0对于无向网络的 N (N - 1)。该网络的平均度数为0网络捕获每个节点的平均边数：� k � = | E |0对于有向网络的 N 和 � k � = 0对于无向网络的 N。该网络0(a) 网络0(b) 样本 #10(c) 样本 #20(d) 样本 #30图1：示例。该图示了一个无权无向的节点属性网络和三个不同的样本。（a）显示了一个具有七条边和六个节点的异质性网络。每个节点被着色为红色（A、C、E）或蓝色（B、D、F）。 （b）样本#1显示了通过采样两个节点提取的子图。该样本包括节点 B 和C，反映了完美的异质性。（c）样本 #2显示了通过随机选择两条边C-E 和 B-D 采样的同质性子图。（d）该样本与样本#1类似，因为它反映了完美的异质性。然而，在这种情况下，节点 F距离最近的种子节点的3-HOP（与样本 #1中的2-HOP相比）。0同质性 H 被同类连接在总边数 | E | 中的比例所捕获。同质性的值范围从 H = 0.0 到 H= 1.0。当 H = 0.5 时，网络被称为中性，否则如果 H < 0.5，则为异质性，如果 H >0.5，则为同质性。类平衡 B捕获每个类值下的节点比例。当所有类值的节点数量相同时，网络是平衡的，否则是不平衡的网络。在这项工作中，我们专注于具有无权无向边和节点在二进制特征（例如 c= 颜色 ∈{蓝色，红色}）上平衡的属性网络。图1a显示了这样一个网络的示例，其中节点被分配给一个颜色，要么是蓝色，要么是红色，由于仅有7条边中的2条是同颜色连接，所以该网络是异质性的（H ≈ 0.3）。该网络也是平衡的（B = 3）06 = 0.5）因为蓝色节点（nb = 3）的数量等于红色节点（nr =3）的数量。请注意，在实际情况下，类平衡 B通常是未知的，以及同质性H。然而，这两个值可以被推断出来。例如，可以通过随机选择一组节点来近似平衡，并从中提取它们的真实类值，然后推断类平衡。类似地，可以通过随机选择一组边来近似同质性。这些近似超出了本工作的范围。为了评估目的，我们假设对网络有完全了解。02.2 关系分类0网络化数据的分类[5, 9,12]从观察到的数据中学习链接节点的属性值之间的相关性，然后在一个集体推理过程中使用它们。该过程可以分为四个阶段。首先，需要从网络中采样一个子图。0研讨会：挖掘属性网络 WWW 2018，2018年4月23日至27日，法国里昂Πi =hijkih k(1)12790其次，通过仅使用节点信息（例如节点属性）学习本地模型，并且可以在推理中用作类别先验。第三，相对于本地模型，关系模型从节点及其1-HOP邻居中学习信息。最后，一旦学习了模型的参数（即概率），集体推理阶段确定如何估计未知值。每个阶段都可以以不同的方式实现[9]。由于我们的工作重点是采样阶段，因此我们通过（i）从训练样本中的节点学习本地模型作为类别先验，（ii）使用贝叶斯统计从训练样本中的节点和边学习关系模型，以及（iii）使用松弛标签推断估计值来保持其他模块固定。为简单起见，我们专注于单变量网络分类，这意味着网络中的链接结构是用类标签建模的，而不使用其他属性的信息。这种设置在[9]中被称为仅网络贝叶斯分类器（NBC），以强调忽略节点的其他本地属性。02.3 网络采样0采样的目标是将网络分割为训练样本和测试样本。首先，从网络 G中提取子图 ˆ G = (ˆ V，ˆ E，ˆ F) 以学习模型参数。属于训练样本 ˆ G的节点 ˆ V � V 被称为种子节点，并且我们假设它们的边 ˆ E = {(ˆ vi，ˆvj)} ∈ (ˆ V × ˆ V) � (V × V) 和属性 ˆ F � F被分类算法知道。例如，基于图1中显示的信息，如果我们选择图1b中的样本，节点A将被正确分类为红色，因为A与一个蓝色的种子节点相连，并且样本（B-C）反映了完美的异质性。然而，如果我们选择图1c中的样本，节点A将被分类为蓝色，因为它与一个蓝色的种子节点相连，并且样本（C-E，B-D）反映了完美的同质性。图1d显示了一个不同的样本，在这种情况下，节点A和B被选为种子节点，而不管学习的模型参数如何（即蓝-蓝，蓝-红，红-蓝，红-红的连接概率），请注意节点F未连接到任何种子节点。因此，节点F的推断属性将取决于节点E的推断属性，而节点E的推断属性又取决于未标记节点C和D的估计值。如果这些估计值是错误的，则节点F的推理也可能是错误的。注意采样方法的重要性。所选节点不仅应反映网络的全局属性，如平衡性和同质性，还应尽可能接近未标记节点，以避免可能出现错误的长标签传播链。接下来，我们描述了在这项工作中评估的十种不同的采样方法。随机节点。这是最基本的采样方法，随机选择一部分 p的节点。然后，采样网络包含所选节点及其之间的所有边。随机边。该技术从所有边 E的集合中随机选择边。为了在其他采样技术之间进行公平比较（基于节点数量），我们随机选择边，直到达到特定的节点比例p。因此，这种采样方法被称为nedges。雪球。雪球采样[2，6]随机选择一个起始节点及其所有邻居以及它们邻居的邻居。0（类似于广度优先搜索）。算法会一直进行下去，直到收集到节点的一部分p。度。我们按照节点的度数（degreeDESC和degreeASC）对所有节点进行排序。这个想法是验证高（或低）度数的节点是否适合分类。因此，选择的节点的比例 p包括排名前 p × 100% 的节点。我们还通过选择 p的混合度（degreeMIX）来提供度数的混合。02 ×  100% 的高度和低度节点。PageRank .类似于按度数采样，我们按照节点的PageRank（PR）[ 11]的降序（pagerankDESC）和升序（pagerankASC）对节点进行排序。通过首先使用最高的PR，我们测试网络中最重要的节点是否是学习和测试推理的良好样本。我们预计pagerankASC的效果会较差，因为它们的低PR节点连接性不好，并且通常度数较低。最佳渗透。最佳渗透[ 10]的动机是找到一组最小的节点，称为影响者，如果激活，将导致信息在整个网络中传播。因此，我们根据节点的集体影响力按降序（percolationDESC）和升序（percolationASC）对节点进行排序。通过考虑集体影响效应，可以识别出战略影响者，也称为弱节点，它们在网络中优于中心节点。03 实验0分类过程可以总结为三个步骤。首先，将网络节点分为训练集和测试集，然后使用从训练样本中提取的子图学习局部和关系模型，最后在测试集上运行分类。训练样本中节点的选择因采样方法而异。然而，为了比较采样方法，训练样本的大小保持不变，包含来自V的5-90%的节点。03.1 合成网络0数据集。我们使用Karimi等人在[ 7]中提出的基于优先附加算法生成了11个具有给定类平衡B =0.5，同质性H ∈ {0.0，0.1，...，1.0}和起始度m =4的网络。每个网络由N = 2000个节点，| E | = 7984条边，平均度� k� = 8和链接密度d =0.00391。表1显示了一些异类亲和、中立和同类亲和网络的更多网络属性。一般来说，每个节点被分配一个二进制属性，即颜色∈{蓝色，红色}，它定义了它的类成员资格。节点vj连接到节点vi的概率由以下公式给出：0其中ki是节点vi的度数，hij是两个节点之间的同质性[ 7]。考虑到同质性是对称和互补的，我们可以假设属于蓝色类别（hbb）的节点与属于红色类别（hrr）的节点之间的连接概率相同（hbb= hrr = H），并且与类内连接概率hbr = hrb = 1 -H互补。我们变化01 由于链接密度非常小，我们将这组网络称为稀疏网络。0Track: Mining Attributed Networks WWW 2018, 2018年4月23-27日，法国里昂204060800.00.20.40.60.81.0H0.1-B0.5204060800.00.20.40.60.81.0H0.5-B0.5204060800.00.20.40.60.81.0H0.9-B0.50.912800度数升序度数降序0度数混合nedges0节点PageRank升序0pagerankDESC渗透升序0渗透降序 雪球0% 种子节点0平均RocAuc0(a) 异类亲和0% 种子节点0平均RocAuc0(b) 中立0% 种子节点0平均RocAuc0(c) 同类亲和0图2：在合成（稀疏）网络上的结果（� k � = 8，d =0.0039）。该图显示了10种采样方法在使用Karimi等人在[7]中提出的基于优先附加算法生成的异类亲和、中立和同类亲和网络上的分类的平均ROC-AUC值。样本大小显示在x轴上。值是5次运行的平均值；阴影区域表示标准偏差。0同质性从H = 0.0（完全异质性）到H = 1.0（完全同质性）。当H =0.0时，只有不共享相同属性的节点连接在一起。相反，在完全同质性的情况下，只有共享相同属性的节点相互连接。在中立网络（H =0.5）中，节点与具有任何标签的节点连接的可能性相等。这意味着在中立网络中，边的形成与节点属性在统计上是独立的。0结果。为简单起见，我们报告了具有同质性特殊情况的网络，即H∈{0.1，0.5，0.9}。这些结果显示在图2中。从图2b中可以看出，在中立网络中，所有采样方法的分类性能都是均匀的，因为链接的形成与节点属性无关。因此，关系分类器无法检测到任何有助于猜测正确属性的网络结构模式。异质性（图2a）和同质性（图2c）网络的比较表明，无论采样技术和样本大小如何，异质性网络更容易分类（即大多数ROC-AUC值为1.0），而同质性网络（在某些情况下）需要更大的训练样本才能实现完美分类。例如，如果样本大小非常小（5%），则对于节点采样、渗透ASC、雪球和nedges，整体分类性能较差（ROC-AUC≈0.6）。然而，一旦样本大小增加，ROC-AUC值迅速收敛到1.0。这种同质性和异质性（稀疏）网络之间的不对称性在图6a和6b中清晰可见，该图总结了使用不同采样策略从平衡网络中抽取的样本的分类性能。颜色表示不同的采样方法，条形图表示使分类器在两个类别中的错误率低于20%所需的最小样本大小。当通过节点、nedges、雪球和所有按升序排列节点的度量来采样时，同质性网络需要更大的样本大小才能实现良好的分类性能（通常首先是低度节点）。因此，偏向于高度节点（降序）的采样方法优于其他技术。另一方面，异质性网络更容易分类，因为10种采样方法中有8种在只包含5-10%的节点的小训练样本中对两个类别都能实现良好的性能。请注意，对于度数升序和PageRank升序的特殊情况，所有网络都需要至少40%的种子节点才能实现良好的性能。这是因为这两种采样技术首先对最低度节点进行排序，而这些节点不一定相互连接2。因此，这样的样本包含不连接的节点（即ˆE =�），这些节点对于学习模型参数没有帮助。0表1：合成（稀疏）网络属性。该表显示了本研究中分析的网络的属性。这些网络包含两个平衡的节点组（即蓝色、红色）。每个数字列代表一个具有特定同质性水平的单个网络。0属性同质性（H）0B 0.5 0.5 0.5 � k  � 8 8 8 链接密度 0.0039 0.00390.0039 节点连通性 4 4 4 度相关性 -0.06 -0.06 -0.05属性相关性 -0.8 0.01 0.8 聚类系数 0.01 0.02 0.030大小，异质性网络更容易分类（即大多数ROC-AUC值为1.0），而同质性网络（在某些情况下）需要更大的训练样本才能实现完美分类。例如，如果样本大小非常小（5%），则对于节点采样、渗透ASC、雪球和nedges，整体分类性能较差（ROC-AUC≈0.6）。然而，一旦样本大小增加，ROC-AUC值迅速收敛到1.0。这种同质性和异质性（稀疏）网络之间的不对称性在图6a和6b中清晰可见，该图总结了使用不同采样策略从平衡网络中抽取的样本的分类性能。颜色表示不同的采样方法，条形图表示使分类器在两个类别中的错误率低于20%所需的最小样本大小。同质性网络需要更大的样本大小才能实现良好的分类性能，当通过节点、nedges、雪球和所有按升序排列节点的度量来采样时（通常首先是低度节点）。因此，偏向于高度节点（降序）的采样方法优于其他技术。另一方面，异质性网络更容易分类，因为10种采样方法中有8种在只包含5-10%的节点的小训练样本中对两个类别都能实现良好的性能。请注意，对于度数升序和PageRank升序的特殊情况，所有网络都需要至少40%的种子节点才能实现良好的性能。这是因为这两种采样技术首先对最低度节点进行排序，而这些节点不一定相互连接2。因此，这样的样本包含不连接的节点（即ˆE =�），这些节点对于学习模型参数没有帮助。03.2 真实世界网络0数据集。我们选择了2005年提取的100个Facebook网络之一[13]。我们关注的是加州理工学院的网络02 实际上，这些网络的度相关性[4]大约为-0.06（即没有度相关性）。0Track：挖掘属性网络WWW 2018，2018年4月23日至27日，法国里昂204060800.00.20.40.60.81.0204060800.00.20.40.60.81.0204060800.00.20.40.60.81.012810度数升序度数降序0度数混合nedges0节点PageRank升序0pagerankDESCpercolationASC0percolationDESC snowball0％种子节点0平均RocAuc0H0.6-B0.70（a）ROC-AUC0％种子节点0平均误差0H0.6-B0.70（b）性别1（少数）的平均误差0％种子节点0平均误差0H0.6-B0.70（c）性别2（多数）的平均误差0图3：CaltechFacebook数据集的结果。从左到右，该图显示了Caltech数据集上10种不同抽样技术的性能，针对不同的样本大小：（a）平均ROC-AUC，（b）性别1类别的分类平均误差，（c）性别2类别的分类平均误差。数值是5次运行的平均值；阴影区域表示标准偏差。该网络对性别2不平衡（B=0.7），几乎中性（H=0.6）。因此，分类性能在ROC-AUC=0.5左右是可以预料的。从（a）中我们可以看到，最高度节点（degreeDESC）的小训练样本30％可以达到ROC-AUC=0.66。然而，最佳模型是degreeMIX，它使用最高混合度节点的70％（即35％最高高度节点和35％最高低度节点）实现ROC-AUC=0.76。总的来说，所有抽样方法在较大的样本大小下都可以提高分类性能。从图（b，c）中我们可以看到类别不平衡问题。由于性别2是多数类别，它的分类误差较少于少数类别性别1。0其中仅包括校内链接（即用户FB页面之间的友谊链接）。每个节点代表学校的一个成员，并由几个属性描述：学生/教职员工状态标志、性别、专业、第二专业/辅修、宿舍/住房、年级和高中。为了进行实验，我们选择属性дender∈{1,2}作为分类器的类标签（也是唯一的属性）。删除没有性别信息（即дender=0）和没有边的节点后，我们得到了701个节点和15464条边。最终网络几乎是中性的（H=0.6），并且对性别2不平衡（B=0.7）。该网络的属性显示在表2中。例如，我们可以看到人们之间的连接非常紧密（平均有44.12个友谊）。请注意，与合成网络示例相比，该网络不仅在类别不平衡方面有所不同，而且在链接密度、平均度和聚类系数方面也有所不同。尽管该网络超出了我们的工作范围（即它是一个不平衡的网络），但我们将其包含在本报告中有两个原因：（一）突出强调进一步研究最小化类别不平衡问题的重要性，（二）展示同质性是否对分类具有影响，而不考虑类别不平衡。0结果。图3显示了Caltech网络的分类结果。由于该网络几乎是中性的（H=0.6），我们预计其性能与均匀分类器（即随机猜测）类似。图3a证实了这一预期，因为它显示大多数抽样技术在0.5左右的ROC-AUC值，尤其是对于小样本（5-50％种子节点）。我们得出结论，degreeMIX优于其他抽样方法，尽管它0至少需要70％的节点总数N才能实现ROC-AUC=0.76。ROC-AUC值为我们提供了分类的整体性能，但它们并不能给出类别内的完整情况。在图3b和3c中，分别显示了少数和多数的分类平均误差值。在这里，我们观察到了类别不平衡问题，分类估计倾向于多数类别：性别2（即多数70％）的平均误差值低于性别1（即少数30％）。这些结果显示了在具有不同同质性水平的不平衡网络中进一步研究关系分类的重要性。0表2：Caltech 2005。Caltech大学Facebook网络的属性。0属性 值 属性 值0N 701 �k� 44.12 |E| 15464 �k minority� 51 gender 1 (min.) 228(33%) �k majority� 41 gender 2 (maj.) 473 (67%) 节点连通性 0 B �0.70 度同配性 -0.0617 H 0.6 属性同配性 0.054 链接密度 0.063聚类系数 0.390Track: Mining Attributed Networks WWW 2018, April 23-27, 2018, Lyon, France204060800.00.20.40.60.81.0204060800.00.20.40.60.81.0204060800.00.20.40.60.81.012820degreeASCdegreeDESC0degreeMIX nedges0nodespagerankASC0pagerankDESCpercolationASC0percolationDESC snowball0%种子节点0平均RocAuc0H0.1-B0.50（a）异质网络0%种子节点0平均RocAuc0H0.5-B0.50（b）中性网络0%种子节点0平均RocAuc0H0.9-B0.50（c）同质网络0图4：合成（密集）网络（�k� = 40，d =0.019）的结果。与图2类似，该图显示了10种采样方法在（a）异质网络，（b）中性网络和（c）同质网络上的分类平均ROC-AUC值。区别在于链接密度。这些网络具有更高的密度。样本大小显示在x轴上。值是5次运行的平均值；阴影区域表示标准差。04讨论0本研究对网络采样对关系分类性能的影响进行了描述性研究。接下来我们详细讨论了我们探索的因素。04.1网络结构0链接密度。我们实验中使用的合成网络具有N = 2000个节点，|E| =7984条边，平均度�k� = 8，链接密度d =0.0039。先前的研究发现链接密度会影响关系分类器的性能[12,17]。为了测试这一发现，我们将链接密度增加到d =0.019，结果得到|Edense| = 39600条边，平均度�kdense� =40。我们将这组网络称为密集网络。如图4所示，更高的链接密度并没有改善分类性能。对于中性网络（图4b）和异质网络（图4a），结果与使用较低链接密度的网络类似。然而，同质网络的分类（图4c）在非常小的样本大小（即5-20%的种子节点）下，ROC-AUC值下降。只有基于degreeDESC、pagerankDESC和percolationDESC样本的分类器性能不受链接密度增加的影响，并且在只有少量样本（5%的节点）可用时表现优于其他技术。注意，在链接密度的两个变体中，ROC-AUC值在至少有30%的种子节点时收敛到1.0。从图6中我们可以看到，高链接密度有助于首先排列低度节点的采样技术。类不平衡。现实世界中的网络可能高度不平衡，每种类型的节点比例不同。例如，我们在第3.2节研究的网络具有同质性H = 0.6和类平衡B =0.7。我们证明了类平衡会影响分类结果。由于几乎中性的同质性，集体推断仅略优于随机基线（即随机猜测），不论采样技术如何。然而，由于类不平衡，每个类别（例如少数类别与多数类别）的错误差异很大。例如，使用随机节点采样和30%的种子节点，性别1类别的分类错误率为0.85，而性别2类别仅为0.16。需要进一步研究来理解在不平衡网络中关系分类的动态。0推断仅略优于随机基线（即随机猜测），不论采样技术如何。然而，由于类不平衡，每个类别（例如少数类别与多数类别）的错误差异很大。例如，使用随机节点采样和30%的种子节点，性别1类别的分类错误率为0.85，而性别2类别仅为0.16。需要进一步研究来理解在不平衡网络中关系分类的动态。0同质性。我们的研究表明，同质性明显影响关系分类器的性能（参见图2）。当网络平衡时，ROC-AUC曲线根据同质性水平和样本大小而变化。如预期，在中性网络（同质性 H =0.5）中，所有采样方法的性能都相同，样本大小不影响分类性能。因此，不论样本的大小如何，分类器都无法学习任何模式，因为不存在任何模式。然而，在异质性（ H = 0.1）或同质性（ H =0.9）网络中，分类准确性根据采样策略和训练样本中标记种子的数量而变化。为了理解这一点，让我们关注图5中展示的具有不同同质性水平的网络上三种不同采样方法的性能。每个热图显示了每个11个合成网络（x轴）的分类平均误差（在5次运行中平均），这些网络在第3.1节中描述，并且显示在训练样本中的种子节点的数量（y轴）。较暗的单元格表示较高的误差，即性能较差。总体而言，我们可以看到在异质性区域（H ≤0.2，最左边的列），分类器在只有少量种子节点的情况下工作得非常好。对于同质性网络（H ≥0.8，最右边的列），当节点和边采样的训练样本很小时，分类误差较高。另一方面，按度数降序排列的采样方法在只有5%的种子节点时表现最佳。这似乎与直觉相反，因为人们会期望在两种情况下都能实现完美分类。0Track: Mining Attributed Networks WWW 2018, April 23-27, 2018, Lyon, France0.00.10.20.30.40.50.60.70.80.91.051020304050607080900.000.030.130.330.470.490.500.500.500.500.400.000.020.110.310.460.510.490.490.410.120.000.000.020.100.270.450.500.480.480.100.020.000.000.020.090.260.430.500.470.420.100.020.000.000.020.090.250.420.500.440.310.100.020.000.000.020.090.250.420.500.440.250.090.020.000.000.020.090.240.410.510.410.240.100.020.000.000.020.090.230.400.510.410.240.080.020.000.000.010.080.210.380.500.410.220.090.020.000.000.010.080.210.390.500.400.240.080.010.000.00.20.40.60.81.00.00.10.20.30.40.50.60.70.80.91.051020304050607080900.000.020.110.310.480.500.490.490.420.210.000.000.020.110.290.460.510.490.470.190.020.000.000.020.100.270.450.500.470.380.110.020.000.000.020.100.270.430.500.460.280.110.020.000.000.020.100.280.430.500.420.270.110.020.000.000.020.110.270.430.510.430.270.110.020.000.000.020.100.270.410.500.440.260.110.030.000.000.020.110.270.420.510.440.250.110.020.000.000.020.110.260.410.500.440.270.110.030.000.000.030.120.280.420.470.420.270.130.030.000.00.20.40.60.81.00.00.10.20.30.40.50.60.70.80.91.051020304050607080900.000.020.120.290.470.500.480.440.120.020.000.000.020.120.280.470.500.460.360.110.020.000.000.020.110.280.450.500.440.280.120.020.000.000.030.120.280.440.500.440.270.130.030.000.000.030.120.280.430.500.450.270.130.030.000.000.030.130.280.420.490.440.270.130.030.000.000.030.130.290.430.500.430.280.140.030.000.000.030.130.290.410.490.440.280.140.040.000.000.040.120.300.420.500.440.290.130.040.000.000.040.140.320.410.490.450.270.150.040.000.00.20.40.60.81.012830% 同质性0%种子节点0B0.5 按节点数排列0（a）节点采样0% 同质性0%种子节点0B0.5 按边数排列0（b）边采样0% 同质性0%种子节点0B0.5 按度数降序排列0（c）按度数降序排列采样0图5：稀疏（合成）网络的整体平均误差。这些热图展示了使用（a）随机节点采样，（b）随机边采样和（c）度后代采样的整体分类平均误差。列代表具有不同同质性的网络，从异质性（ H = 0.0）到同质性（ H = 1.0）。每一行显示采样中收集的节点百分比。中性和几乎中性的网络（0.4 ≤ H ≤0.6）使用任何采样技术都表现一致。网络的同质性/异质性越高，所有情况下的分类越准确。然而，与异质性网络相比，同质性网络需要更大的样本，特别是在使用节点和边采样时。总的来说，在两种情况下，随着训练样本的大小增加，分类错误率会降低。数值是5次运行的平均值。0因为强同质性和强异质性应该帮助分类器学习链接和属性之间的关系，所以我们的工作表明同质性明显影响关系分类器的性能（参见图2）。此外，两个网络的全局属性似乎几乎相同，如表1所示。乍一看，似乎异质性网络更容易分类，并且它们的性能在不同的采样技术下不变。此外，高度种子节点有助于分类器不仅学习正确的参数，还在异质性和同质性网络中传播正确的推理。请注意，在两种情况下，随着训练样本的增大，分类错误率降低。04.2 采样网络0如第2.3节所述，我们使用了十种不同的网络采样策略。在图6中，我们根据需要训练分类器以实现两个类别的分类错误率低于20%的样本大小对采样方法进行排名。图6a和6b是指第3.1节中展示的稀疏网络（链接密度 d =0.0039）。图6c和6d是指相应的密集版本（链接密度 d =0.019）。最右边的图显示了在同质性网络上训练的分类器的结果。可以看出，包括在网络中具有中心位置的节点（按度数降序排列、按PageRank降序排列、按渗透降序排列）的采样策略效果最好，只需要5%的种子节点。然而，这些采样策略需要了解完整的网络信息，在难以获取这些信息的情况下可能不合适。在稀疏网络的情况下，第二好的选择（参见图6b）是通过边数采样10%的节点，这会随机选择网络中的边。请注意，这会导致优先选择中心节点（即度数高的节点）。对于密集网络（参见图6d），第二好的选择是随机采样20%的节点。03 虽然这个度量可能是任意的，但目标是展示一个无偏的分类，其中两个类别都能被正确推断出来0其他的采样技术需要更大的训练样本。接下来，我们解释它们性能差的原因。雪球采样是一种随机选择一个节点，然后选择它的邻居和邻居的邻居的技术，类似于广度优先搜索。由于在同质网络中，以红色节点开始的雪球样本将选择其邻居（很可能大部分是红色节点），而没有捕获足够的蓝色节点，因此预计需要更大的种子节点样本。度、pagerank和渗透升序采样方法（degreeASC、pagerankAS