当节点具有人口统计属性时,概率图形模型中社区结构的推理可能不会与公平约束一致。某些人口统计学可能在某些检测到的社区中过度代表,在其他人中欠代表。本文定义了一个新的$ \ ell_1 $ -regulared伪似然方法,用于公平图形模型选择。特别是,我们假设真正的基础图表​​中存在一些社区或聚类结构,我们寻求从数据中学习稀疏的无向图形及其社区,使得人口统计团体在社区内相当代表。我们的优化方法使用公平的人口统计奇偶校验定义,但框架很容易扩展到其他公平的定义。我们建立了分别,连续和二进制数据的高斯图形模型和Ising模型的提出方法的统计一致性,证明了我们的方法可以以高概率恢复图形及其公平社区。
translated by 谷歌翻译
网络研究中最根本的问题之一是社区检测。随机块模型(SBM)是一种流行的模型,具有不同的估计方法,其社区检测一致性结果揭晓。但是,SBM受到强烈假设的限制:同一社区中的所有节点在随机上都是等效的,这可能不适合实际应用。我们引入了成对协变量调整后的随机块模型(PCABM),这是SBM的概括,该模型包含成对协变量信息。我们研究协变量和社区分配系数的最大似然估计。结果表明,在适当的稀疏条件下,协变量和社区分配的系数估计均一致。引入了带有调节的光谱聚类(SCWA),以有效地求解PCABM。在某些条件下,我们得出了SCWA下社区检测的错误限制,并表明它是社区检测一致的。此外,研究了模型的选择,并研究了成对协变量的特征选择,并提出了两种相应的算法。当可访问协变量信息时,PCABM与SBM或学位校正的随机块模型(DCBM)进行比较。
translated by 谷歌翻译
现代高维方法经常采用“休稀稀物”的原则,而在监督多元学习统计学中可能面临着大量非零系数的“密集”问题。本文提出了一种新的聚类减少秩(CRL)框架,其施加了两个联合矩阵规范化,以自动分组构建预测因素的特征。 CRL比低级别建模更具可解释,并放松变量选择中的严格稀疏假设。在本文中,提出了新的信息 - 理论限制,揭示了寻求集群的内在成本,以及多元学习中的维度的祝福。此外,开发了一种有效的优化算法,其执行子空间学习和具有保证融合的聚类。所获得的定点估计器虽然不一定是全局最佳的,但在某些规则条件下享有超出标准似然设置的所需的统计准确性。此外,提出了一种新的信息标准,以及其无垢形式,用于集群和秩选择,并且具有严格的理论支持,而不假设无限的样本大小。广泛的模拟和实数据实验证明了所提出的方法的统计准确性和可解释性。
translated by 谷歌翻译
光谱聚类在从业者和理论家中都很受欢迎。尽管对光谱聚类的性能保证有充分的了解,但最近的研究集中于在群集中执行``公平'',要求它们在分类敏感的节点属性方面必须``平衡''人口中的种族分布)。在本文中,我们考虑了一个设置,其中敏感属性间接表现在辅助\ textit {表示图}中,而不是直接观察到。该图指定了可以相对于敏感属性互相表示的节点对,除了通常的\ textit {相似性图}外,还可以观察到。我们的目标是在相似性图中找到簇,同时尊重由表示图编码的新个人公平性约束。我们为此任务开发了不均衡和归一化光谱聚类的变体,并在代表图诱导的种植分区模型下分析其性能。该模型同时使用节点的群集成员身份和表示图的结构来生成随机相似性图。据我们所知,这些是在个人级别的公平限制下受约束光谱聚类的第一个一致性结果。数值结果证实了我们的理论发现。
translated by 谷歌翻译
光谱聚类是网络中广泛使用的社区检测方法之一。然而,大型网络为其中的特征值分解带来了计算挑战。在本文中,我们研究了从统计角度使用随机草图算法的光谱聚类,在那里我们通常假设网络数据是从随机块模型生成的,这些模型不一定是完整等级的。为此,我们首先使用最近开发的草图算法来获得两个随机谱聚类算法,即基于随机投影和基于随机采样的光谱聚类。然后,我们在群体邻接矩阵的近似误差,错误分类误差和链路概率矩阵的估计误差方面研究得到的算法的理论界限。事实证明,在温和条件下,随机谱聚类算法导致与原始光谱聚类算法相同的理论界。我们还将结果扩展到校正的程度校正的随机块模型。数值实验支持我们的理论发现并显示随机化方法的效率。一个名为rclusct的新R包是开发的,并提供给公众。
translated by 谷歌翻译
随机奇异值分解(RSVD)是用于计算大型数据矩阵截断的SVD的一类计算算法。给定A $ n \ times n $对称矩阵$ \ mathbf {m} $,原型RSVD算法输出通过计算$ \ mathbf {m mathbf {m} $的$ k $引导singular vectors的近似m}^{g} \ mathbf {g} $;这里$ g \ geq 1 $是一个整数,$ \ mathbf {g} \ in \ mathbb {r}^{n \ times k} $是一个随机的高斯素描矩阵。在本文中,我们研究了一般的“信号加上噪声”框架下的RSVD的统计特性,即,观察到的矩阵$ \ hat {\ mathbf {m}} $被认为是某种真实但未知的加法扰动信号矩阵$ \ mathbf {m} $。我们首先得出$ \ ell_2 $(频谱规范)和$ \ ell_ {2 \ to \ infty} $(最大行行列$ \ ell_2 $ norm)$ \ hat {\ hat {\ Mathbf {M}} $和信号矩阵$ \ Mathbf {M} $的真实单数向量。这些上限取决于信噪比(SNR)和功率迭代$ g $的数量。观察到一个相变现象,其中较小的SNR需要较大的$ g $值以保证$ \ ell_2 $和$ \ ell_ {2 \ to \ fo \ infty} $ distances的收敛。我们还表明,每当噪声矩阵满足一定的痕量生长条件时,这些相变发生的$ g $的阈值都会很清晰。最后,我们得出了近似奇异向量的行波和近似矩阵的进入波动的正常近似。我们通过将RSVD的几乎最佳性能保证在应用于三个统计推断问题的情况下,即社区检测,矩阵完成和主要的组件分析,并使用缺失的数据来说明我们的理论结果。
translated by 谷歌翻译
我们考虑了从节点观测值估算多个网络拓扑的问题,其中假定这些网络是从相同(未知)随机图模型中绘制的。我们采用图形作为我们的随机图模型,这是一个非参数模型,可以从中绘制出潜在不同大小的图形。图形子的多功能性使我们能够解决关节推理问题,即使对于要恢复的图形包含不同数量的节点并且缺乏整个图形的精确比对的情况。我们的解决方案是基于将最大似然惩罚与Graphon估计方案结合在一起,可用于增强现有网络推理方法。通过引入嘈杂图抽样信息的强大方法,进一步增强了所提出的联合网络和图形估计。我们通过将其性能与合成和实际数据集中的竞争方法进行比较来验证我们提出的方法。
translated by 谷歌翻译
网络分析一直是揭示大量对象之间关系和交互的强大工具。然而,它在准确识别重要节点节点相互作用的有效性受到快速增长的网络规模的挑战,数据以空前的粒度和规模收集。克服这种高维度的共同智慧是将节点崩溃成较小的群体,并在小组级别进行连通性分析。将努力分为两个阶段不可避免地打开了一致性的差距,并降低了效率。共识学习是通用知识发现的新常态,并具有多个可用的数据源。为此,本文以组合多个数据源来开发同时分组和连接分析的统一框架。该算法还保证了统计上最佳的估计器。
translated by 谷歌翻译
我们提出了对学度校正随机块模型(DCSBM)的合适性测试。该测试基于调整后的卡方统计量,用于测量$ n $多项式分布的组之间的平等性,该分布具有$ d_1,\ dots,d_n $观测值。在网络模型的背景下,多项式的数量($ n $)的数量比观测值数量($ d_i $)快得多,与节点$ i $的度相对应,因此设置偏离了经典的渐近学。我们表明,只要$ \ {d_i \} $的谐波平均值生长到无穷大,就可以使统计量在NULL下分配。顺序应用时,该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作,因此在学位上有条件,因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法,即在测试$ K $社区时根据$(k+1)$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量,我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案,因此其效用超出了顺序测试,可用于同时测试DCSBM家族以外的各种替代方案。特别是,我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。
translated by 谷歌翻译
There are synergies of research interests and industrial efforts in modeling fairness and correcting algorithmic bias in machine learning. In this paper, we present a scalable algorithm for spectral clustering (SC) with group fairness constraints. Group fairness is also known as statistical parity where in each cluster, each protected group is represented with the same proportion as in the entirety. While FairSC algorithm (Kleindessner et al., 2019) is able to find the fairer clustering, it is compromised by high costs due to the kernels of computing nullspaces and the square roots of dense matrices explicitly. We present a new formulation of underlying spectral computation by incorporating nullspace projection and Hotelling's deflation such that the resulting algorithm, called s-FairSC, only involves the sparse matrix-vector products and is able to fully exploit the sparsity of the fair SC model. The experimental results on the modified stochastic block model demonstrate that s-FairSC is comparable with FairSC in recovering fair clustering. Meanwhile, it is sped up by a factor of 12 for moderate model sizes. s-FairSC is further demonstrated to be scalable in the sense that the computational costs of s-FairSC only increase marginally compared to the SC without fairness constraints.
translated by 谷歌翻译
在分布式机器学习实践中越来越受欢迎,在分布式机器学习实践中越来越受欢迎,在不共享本地数据的情况下,对算法进行了算法培训的联合学习。通常,图形结构$ g $存在于本地设备以进行通信。在这项工作中,我们考虑使用数据分布和通信异质性以及本地设备的计算能力有限的联合学习中的参数估计。我们通过在本地设备上参数化分布来编码分布异质性,并具有一组不同的$ p $维矢量。然后,我们建议在$ m $估算框架下与融合套索正则化的所有设备共同估计所有设备的参数,从而鼓励对$ g $中连接的设备上的参数进行平等估计。根据$ G $,我们可以为估计器提供一般结果,可以进一步校准以获得各种特定问题设置的收敛率。令人惊讶的是,我们的估计器在$ g $上的某些图保真度条件下达到了最佳率,就好像我们可以汇总所有共享相同分布的样本一样。如果未满足图形保真度条件,我们通过多次测试提出一个边缘选择过程,以确保最佳性。为了减轻本地计算的负担,提供了一个分散的随机版本的ADMM,收敛速率$ o(t^{ - 1} \ log t)$,其中$ t $表示迭代的数量。我们强调,我们的算法在每次迭代时仅沿$ g $的边缘传输参数,而无需保留隐私的中央机器。我们将其进一步扩展到在训练过程中随机无法接近设备的情况,并具有类似的算法收敛保证。模拟实验和2020年美国总统选举数据集证明了我们方法的计算和统计效率。
translated by 谷歌翻译
考虑一个面板数据设置,其中可获得对个人的重复观察。通常可以合理地假设存在共享观察特征的类似效果的个体组,但是分组通常提前未知。我们提出了一种新颖的方法来估计普通面板数据模型的这种未观察到的分组。我们的方法明确地估计各个参数估计中的不确定性,并且在每个人上具有大量的个体和/或重复测量的计算可行。即使在单个数据不可用的情况下,也可以应用开发的想法,并且仅向研究人员提供参数估计与某种量化的不确定性。
translated by 谷歌翻译
本文考虑了Pensky和Wang(2021)中引入的各种多重(Dimple)网络模型,该网络的所有层都具有相同的节点集合,并配备了随机块模型。此外,所有层都可以分为具有相同社区结构的组,尽管同一组中的层可能具有不同的块连接概率矩阵。 Dimple模型概括了许多论文,这些论文在所有层中研究具有相同社区结构的多层网络,以及混合物多层随机块模型(MMLSBM),同一组中的层具有相同的块连接概率的矩阵。彭斯基和王(2021)将光谱聚类应用于邻接张量的代理,而本文则使用稀疏的子空间聚类(SSC)来识别具有相同社区结构的层组。在轻度条件下,后者导致层间聚类非常一致。此外,SSC允许比Pensky和Wang(2021)的方法处理更大的网络,并且非常适合应用并行计算。
translated by 谷歌翻译
众所周知,许多网络系统,例如电网,大脑和舆论动态社交网络,都可以遵守保护法。这种现象的例子包括电网中的基尔乔夫法律和社交网络中的意见共识。网络系统中的保护定律可以建模为$ x = b^{*} y $的平衡方程,其中$ b^{*} $的稀疏模式捕获了网络的连接,$ y,x \在\ mathbb {r}^p $中分别是节点上“电势”和“注入流”的向量。节点电位$ y $会导致跨边缘的流量,并且在节点上注入的流量$ x $是网络动力学的无关紧要的。在几个实用的系统中,网络结构通常是未知的,需要从数据估算。为此,可以访问节点电位$ y $的样本,但只有节点注射$ x $的统计信息。在这个重要问题的激励下,我们研究了$ n $ y $ y $ y $ y $ y $ y $ y $ y $ b^{*} $稀疏结构的估计,假设节点注射$ x $遵循高斯分布,并带有已知的发行协方差$ \ sigma_x $。我们建议在高维度中为此问题的新$ \ ell_ {1} $ - 正则最大似然估计器,网络的大小$ p $大于样本量$ n $。我们表明,此优化问题是目标中的凸,并接受了独特的解决方案。在新的相互不一致的条件下,我们在三重$(n,p,d)$上建立了足够的条件,对于$ b^{*} $的精确稀疏恢复是可能的; $ d $是图的程度。我们还建立了在元素最大,Frobenius和运营商规范中回收$ b^{*} $的保证。最后,我们通过对拟议估计量对合成和现实世界数据的性能进行实验验证来补充这些理论结果。
translated by 谷歌翻译
我们在一般随机块模型下研究现实网络中的社区层次结构,其中连接概率在二叉树中构造。在这种模型中,标准递归双分区算法基于非通知图拉普拉斯的Fiedler向量将网络分成两个社区,并重复分割,直到停止规则指示不进一步的社区结构。我们在广泛的模型参数下证明了这种方法的强大一致性,它包括稀疏网络,节点度为$ O(\ log n)$。此外,与大多数现有工作不同,我们的理论涵盖了多尺度网络,其中连接概率可能因数量级而异,这包括一类实际相关但技术上挑战处理的重要阶段。最后,我们展示了我们对综合性数据和实际示例算法的表现。
translated by 谷歌翻译
我们考虑学习底层多变量数据的稀疏无向图的问题。我们专注于稀疏精度矩阵上的图表拉普拉斯相关的约束,它在与图形节点相关联的随机变量之间编码条件依赖性。在这些约束下,精度矩阵的偏差元素是非正(总阳性),并且精度矩阵可能不是全级。我们调查了对广泛使用惩罚的日志似然方法来强制执行总积极性但不是拉普拉斯结构的修改。然后可以从非对角线精密矩阵中提取图拉普拉斯。乘法器(ADMM)算法的交替方向方法被提出和分析了Laplacian相关约束和套索的约束优化以及自适应套索处罚。基于合成数据的数值结果表明,所提出的约束的自适应套索方法显着优于现有的基于拉普拉斯的方法。我们还评估了我们对实际财务数据的方法。
translated by 谷歌翻译
The stochastic block model (SBM) is a random graph model with planted clusters. It is widely employed as a canonical model to study clustering and community detection, and provides generally a fertile ground to study the statistical and computational tradeoffs that arise in network and data sciences.This note surveys the recent developments that establish the fundamental limits for community detection in the SBM, both with respect to information-theoretic and computational thresholds, and for various recovery requirements such as exact, partial and weak recovery (a.k.a., detection). The main results discussed are the phase transitions for exact recovery at the Chernoff-Hellinger threshold, the phase transition for weak recovery at the Kesten-Stigum threshold, the optimal distortion-SNR tradeoff for partial recovery, the learning of the SBM parameters and the gap between information-theoretic and computational thresholds.The note also covers some of the algorithms developed in the quest of achieving the limits, in particular two-round algorithms via graph-splitting, semi-definite programming, linearized belief propagation, classical and nonbacktracking spectral methods. A few open problems are also discussed.
translated by 谷歌翻译
现实世界网络经常具有侧面信息,可以帮助提高网络分析任务等群集的性能。尽管在过去十年中对网络聚类方法进行了大量的实证和理论研究,但侧面信息的附加值和用于在聚类算法中最佳地结合的方法的附加值相对较少理解。我们向群集网络提出了一种新的迭代算法,其中包含节点的侧面信息(以协调因子的形式)提出并表明我们的算法在上下文对称随机块模型下是最佳的。我们的算法可以应用于一般上下文随机块模型,并避免与先前提出的方法相比,避免了HyperParameter调整。我们在综合数据实验中确认我们的理论结果,其中我们的算法显着优于其他方法,并表明它也可以应用于签名的图表。最后,我们展示了我们对实际数据方法的实际兴趣。
translated by 谷歌翻译
我们提出了一种凸锥程序,可推断随机点产品图(RDPG)的潜在概率矩阵。优化问题最大化Bernoulli最大似然函数,增加核规范正则化术语。双重问题具有特别良好的形式,与众所周知的SemideFinite程序放松MaxCut问题有关。使用原始双功率条件,我们绑定了原始和双解决方案的条目和等级。此外,我们在轻微的技术假设下绑定了最佳目标值并证明了略微修改模型的概率估计的渐近一致性。我们对合成RDPG的实验不仅恢复了自然集群,而且还揭示了原始数据的下面的低维几何形状。我们还证明该方法在空手道俱乐部图表和合成美国参议图中恢复潜在结构,并且可以扩展到最多几百个节点的图表。
translated by 谷歌翻译
随机块模型(SBM)是一个随机图模型,其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型,并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展,无论是在信息理论和计算方案方面,以及各种恢复要求,例如精确,部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换,Kesten-Stigum阈值弱恢复的相变,最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导,特别是通过绘制绘制,半定义编程,(线性化)信念传播,经典/非背带频谱和图形供电。还讨论了其他块模型的扩展,例如几何模型和一些开放问题。
translated by 谷歌翻译