我们提出了一种新方法，即校准的非参数扫描统计量（CNSS），以更准确地检测大型现实世界图中的异常模式。扫描统计数据可以通过最大化似然比统计量来确定有趣或意外的连接子图；特别是，非参数扫描统计（NPSS）识别具有比预期的单独显着节点比例高的子图。但是，我们表明最近提出的NPSS方法被错误地校准了，无法解释统计量超过子图的多样性。这既可以降低微妙信号的检测能力，又导致检测到的子图的精度降低，即使对于更强的信号也是如此。因此，我们开发了一种重新校准NPSS的新统计方法，正确调整了多个假设测试并考虑了基础图结构。虽然基于随机测试的重新校准在计算上是昂贵的，但我们提出了一种有效的（近似）算法和新的，封闭形式的下限（在零假设下，在给定大小的子尺寸的显着节点的预期最大比例上，没有异常模式）。这些进步，加上最近的核心树分解方法的整合，使CNSS能够扩展到大型现实世界图，并在检测到的子学的准确性方面有了很大的提高。与最先进的对应物相比，证明了对半合成和现实数据集的广泛实验，以验证我们提出的方法的有效性。

我们提出了对学度校正随机块模型（DCSBM）的合适性测试。该测试基于调整后的卡方统计量，用于测量$ n $多项式分布的组之间的平等性，该分布具有$ d_1，\ dots，d_n $观测值。在网络模型的背景下，多项式的数量（$ n $）的数量比观测值数量（$ d_i $）快得多，与节点$ i $的度相对应，因此设置偏离了经典的渐近学。我们表明，只要$ \ {d_i \} $的谐波平均值生长到无穷大，就可以使统计量在NULL下分配。顺序应用时，该测试也可以用于确定社区数量。该测试在邻接矩阵的压缩版本上进行操作，因此在学位上有条件，因此对大型稀疏网络具有高度可扩展性。我们结合了一个新颖的想法，即在测试$ K $社区时根据$（k+1）$ - 社区分配来压缩行。这种方法在不牺牲计算效率的情况下增加了顺序应用中的力量，我们证明了它在恢复社区数量方面的一致性。由于测试统计量不依赖于特定的替代方案，因此其效用超出了顺序测试，可用于同时测试DCSBM家族以外的各种替代方案。特别是，我们证明该测试与具有社区结构的潜在可变性网络模型的一般家庭一致。

即使机器学习算法已经在数据科学中发挥了重要作用，但许多当前方法对输入数据提出了不现实的假设。由于不兼容的数据格式，或数据集中的异质，分层或完全缺少的数据片段，因此很难应用此类方法。作为解决方案，我们提出了一个用于样本表示，模型定义和培训的多功能，统一的框架，称为“ Hmill”。我们深入审查框架构建和扩展的机器学习的多个范围范式。从理论上讲，为HMILL的关键组件的设计合理，我们将通用近似定理的扩展显示到框架中实现的模型所实现的所有功能的集合。本文还包含有关我们实施中技术和绩效改进的详细讨论，该讨论将在MIT许可下发布供下载。该框架的主要资产是其灵活性，它可以通过相同的工具对不同的现实世界数据源进行建模。除了单独观察到每个对象的一组属性的标准设置外，我们解释了如何在框架中实现表示整个对象系统的图表中的消息推断。为了支持我们的主张，我们使用框架解决了网络安全域的三个不同问题。第一种用例涉及来自原始网络观察结果的IoT设备识别。在第二个问题中，我们研究了如何使用以有向图表示的操作系统的快照可以对恶意二进制文件进行分类。最后提供的示例是通过网络中实体之间建模域黑名单扩展的任务。在所有三个问题中，基于建议的框架的解决方案可实现与专业方法相当的性能。

社区检测是网络科学中最重要的方法领域之一，在过去的几十年里引起了大量关注的方法之一。该区域处理网络的自动部门到基础构建块中，目的是提供其大规模结构的概要。尽管它的重要性和广泛的采用普及，所谓的最先进和实际在各种领域实际使用的方法之间存在明显的差距。在这里，我们试图通过根据是否具有“描述性”或“推论”目标来划分现有方法来解决这种差异。虽然描述性方法在基于社区结构的直观概念的网络中找到模式的模式，但是推理方法阐述了精确的生成模型，并尝试将其符合数据。通过这种方式，他们能够为网络形成机制提供见解，并以统计证据支持的方式与随机性的单独结构。我们审查如何使用推论目标采用描述性方法被陷入困境和误导性答案，因此应该一般而言。我们认为推理方法更通常与更清晰的科学问题一致，产生更强大的结果，并且应该是一般的首选。我们试图消除一些神话和半真半假在实践中使用社区检测时，努力改善这些方法的使用以及对结果的解释。

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.

We present a new algorithm for Bayesian network structure learning, called Max-Min Hill-Climbing (MMHC). The algorithm combines ideas from local learning, constraint-based, and search-and-score techniques in a principled and effective way. It first reconstructs the skeleton of a Bayesian network and then performs a Bayesian-scoring greedy hill-climbing search to orient the edges. In our extensive empirical evaluation MMHC outperforms on average and in terms of various metrics several prototypical and state-of-the-art algorithms, namely the PC, Sparse Candidate, Three Phase Dependency Analysis, Optimal Reinsertion, Greedy Equivalence Search, and Greedy Search. These are the first empirical results simultaneously comparing most of the major Bayesian network algorithms against each other. MMHC offers certain theoretical advantages, specifically over the Sparse Candidate algorithm, corroborated by our experiments. MMHC and detailed results of our study are publicly available at http://www.dsl-lab.org/supplements/mmhc paper/mmhc index.html.

在线切换点检测的许多现代应用需要能够处理高频观测，有时有时可用的可用计算资源。用于检测平均值的在线算法通常涉及使用移动窗口，或指定预期的变化大小。这种选择影响哪些改变算法具有最大的功率检测。我们介绍了一种算法，功能在线CUSUM（焦点），其等同于同时为所有大小窗口运行这些早期方法，或者所有可能的变化尺寸的可能值。我们的理论结果为每次迭代的预期计算成本提供紧张的界限，这是在观察人数中的对数。我们展示了如何将焦点应用于均匀场景的许多不同变化，并通过其最先进的性能来展示其在计算机服务器数据中的异常行为时的实用实用性。

在2015年和2019年之间，地平线的成员2020年资助的创新培训网络名为“Amva4newphysics”，研究了高能量物理问题的先进多变量分析方法和统计学习工具的定制和应用，并开发了完全新的。其中许多方法已成功地用于提高Cern大型Hadron撞机的地图集和CMS实验所执行的数据分析的敏感性;其他几个人，仍然在测试阶段，承诺进一步提高基本物理参数测量的精确度以及新现象的搜索范围。在本文中，在研究和开发的那些中，最相关的新工具以及对其性能的评估。

Network-based analyses of dynamical systems have become increasingly popular in climate science. Here we address network construction from a statistical perspective and highlight the often ignored fact that the calculated correlation values are only empirical estimates. To measure spurious behaviour as deviation from a ground truth network, we simulate time-dependent isotropic random fields on the sphere and apply common network construction techniques. We find several ways in which the uncertainty stemming from the estimation procedure has major impact on network characteristics. When the data has locally coherent correlation structure, spurious link bundle teleconnections and spurious high-degree clusters have to be expected. Anisotropic estimation variance can also induce severe biases into empirical networks. We validate our findings with ERA5 reanalysis data. Moreover we explain why commonly applied resampling procedures are inappropriate for significance evaluation and propose a statistically more meaningful ensemble construction framework. By communicating which difficulties arise in estimation from scarce data and by presenting which design decisions increase robustness, we hope to contribute to more reliable climate network construction in the future.

随机块模型（SBM）是一个随机图模型，其连接不同的顶点组不同。它被广泛用作研究聚类和社区检测的规范模型，并提供了肥沃的基础来研究组合统计和更普遍的数据科学中出现的信息理论和计算权衡。该专着调查了最近在SBM中建立社区检测的基本限制的最新发展，无论是在信息理论和计算方案方面，以及各种恢复要求，例如精确，部分和弱恢复。讨论的主要结果是在Chernoff-Hellinger阈值中进行精确恢复的相转换，Kesten-Stigum阈值弱恢复的相变，最佳的SNR - 单位信息折衷的部分恢复以及信息理论和信息理论之间的差距计算阈值。该专着给出了在寻求限制时开发的主要算法的原则推导，特别是通过绘制绘制，半定义编程，（线性化）信念传播，经典/非背带频谱和图形供电。还讨论了其他块模型的扩展，例如几何模型和一些开放问题。

贝叶斯网络中的精确推断非常棘手，并且对相应集团树（CT）中最大集团的大小具有指数依赖性，因此需要近似。基于因子的结合物大小的方法比基于结构的方法更准确，但是昂贵，因为它们涉及大量候选结构或区域图中的信念的推断。我们提出了一种基于增量的建筑 - 上方（ibia）范式的近似推断的替代方法，该方法将贝叶斯网络转换为包含一系列链接的集团森林（SLCTF）的数据结构，并由用户包围的集团尺寸 - 指定值。在此方法的增量构建阶段中，只要集团大小在指定的界限内，CTF是通过向CTF添加变量来逐步构建的。一旦达到集团尺寸约束，CTF中的CTS就会在IBIA的推断阶段进行校准。所得的集团信念在近似阶段使用，以获得较小的集团大小的近似CTF。近似CTF构成了序列中下一个CTF的起点。重复这些步骤，直到将所有变量添加到序列中的CTF中。我们证明，我们用于汇总树的增量结构的算法始终会产生有效的CT，并且我们的近似技术保留了一个集团内变量的共同信念。基于此，我们表明SLCTF数据结构可用于有效的分区功能以及先验和后边缘的近似推断。使用了500多个基准测试该方法，与其他近似方法相比，结果显示出具有竞争力的运行时的误差显着降低。

许多复杂网络的结构包括其拓扑顶部的边缘方向性和权重。可以无缝考虑这些属性组合的网络分析是可取的。在本文中，我们研究了两个重要的这样的网络分析技术，即中心和聚类。采用信息流基于集群的模型，该模型本身就是在计算中心的信息定理措施时构建。我们的主要捐款包括马尔可夫熵中心的广义模型，灵活地调整节点度，边缘权重和方向的重要性，具有闭合形式的渐近分析。它导致一种新颖的两级图形聚类算法。中心分析有助于推理我们对给定图形的方法的适用性，并确定探索当地社区结构的“查询”节点，从而导致群集聚类机制。熵中心计算由我们的聚类算法摊销，使其计算得高效：与使用马尔可夫熵中心为聚类的先前方法相比，我们的实验表明了多个速度的速度。我们的聚类算法自然地继承了适应边缘方向性的灵活性，以及​​边缘权重和节点度之间的不同解释和相互作用。总的来说，本文不仅具有显着的理论和概念贡献，还转化为实际相关性的文物，产生新的，有效和可扩展的中心计算和图形聚类算法，其有效通过广泛的基准测试进行了验证。

A common approach to modeling networks assigns each node to a position on a low-dimensional manifold where distance is inversely proportional to connection likelihood. More positive manifold curvature encourages more and tighter communities; negative curvature induces repulsion. We consistently estimate manifold type, dimension, and curvature from simply connected, complete Riemannian manifolds of constant curvature. We represent the graph as a noisy distance matrix based on the ties between cliques, then develop hypothesis tests to determine whether the observed distances could plausibly be embedded isometrically in each of the candidate geometries. We apply our approach to data-sets from economics and neuroscience.

在过去十年中，图形内核引起了很多关注，并在结构化数据上发展成为一种快速发展的学习分支。在过去的20年中，该领域发生的相当大的研究活动导致开发数十个图形内核，每个图形内核都对焦于图形的特定结构性质。图形内核已成功地成功地在广泛的域中，从社交网络到生物信息学。本调查的目标是提供图形内核的文献的统一视图。特别是，我们概述了各种图形内核。此外，我们对公共数据集的几个内核进行了实验评估，并提供了比较研究。最后，我们讨论图形内核的关键应用，并概述了一些仍有待解决的挑战。

通常，使用网络编码在物理，生物，社会和信息科学中应用程序中复杂系统中实体之间的交互体系结构。为了研究复杂系统的大规模行为，研究网络中的中尺度结构是影响这种行为的构件。我们提出了一种新方法来描述网络中的低率中尺度结构，并使用多种合成网络模型和经验友谊，协作和蛋白质 - 蛋白质相互作用（PPI）网络说明了我们的方法。我们发现，这些网络拥有相对较少的“潜在主题”，可以成功地近似固定的中尺度上网络的大多数子图。我们使用一种称为“网络词典学习”（NDL）的算法，该算法结合了网络采样方法和非负矩阵分解，以学习给定网络的潜在主题。使用一组潜在主题对网络进行编码的能力具有多种应用于网络分析任务的应用程序，例如比较，降解和边缘推理。此外，使用我们的新网络去核和重建（NDR）算法，我们演示了如何通过仅使用直接从损坏的网络中学习的潜在主题来贬低损坏的网络。

我们介绍了一个新型的多层加权网络模型，该模型除了本地信号外，还考虑了全局噪声。该模型类似于多层随机块模型（SBM），但关键区别在于，跨层之间的块之间的相互作用在整个系统中是常见的，我们称之为环境噪声。单个块还以这些固定的环境参数为特征，以表示不属于其他任何地方的成员。这种方法允许将块同时聚类和类型化到信号或噪声中，以便更好地理解其在整个系统中的作用，而现有块模型未考虑。我们采用了分层变异推断的新颖应用来共同检测和区分块类型。我们称此模型为多层加权网络称为随机块（具有）环境噪声模型（SBANM），并开发了相关的社区检测算法。我们将此方法应用于费城神经发育队列中的受试者，以发现与精神病有关的具有共同心理病理学的受试者社区。

我们可以使用机器学习来压缩图形数据吗？在图中没有排序对传统压缩算法构成了重大挑战，限制了其可达到的收益以及他们发现相关模式的能力。另一方面，大多数图表压缩方法依赖于域依赖的手工制作表示，并且无法适应不同的底层图分布。这项工作旨在建立必要的原则，无损图形压缩方法应遵循以接近熵储存下限。我们不是对图形分布进行僵化的假设，我们将压缩机作为概率模型制定，可以从数据学习并概括到看不见的实例。我们的“分区和代码”框架需要三个步骤：首先，分区算法将图形分解为子图，然后映射到我们学习概率分布的小词典的元素，最后，熵编码器转换了表示进入比特。所有组件（分区，字典和分发）都是参数化的，可以用梯度下降训练。理论上，从温和条件下理论上比较了几个图形编码的压缩质量，并证明了PNC实现了线性或二次以顶点的数量而产生的压缩增益。经验上，PNC对不同的现实网络产生了显着的压缩改进。

We develop an online kernel Cumulative Sum (CUSUM) procedure, which consists of a parallel set of kernel statistics with different window sizes to account for the unknown change-point location. Compared with many existing sliding window-based kernel change-point detection procedures, which correspond to the Shewhart chart-type procedure, the proposed procedure is more sensitive to small changes. We further present a recursive computation of detection statistics, which is crucial for online procedures to achieve a constant computational and memory complexity, such that we do not need to calculate and remember the entire Gram matrix, which can be a computational bottleneck otherwise. We obtain precise analytic approximations of the two fundamental performance metrics, the Average Run Length (ARL) and Expected Detection Delay (EDD). Furthermore, we establish the optimal window size on the order of $\log ({\rm ARL})$ such that there is nearly no power loss compared with an oracle procedure, which is analogous to the classic result for window-limited Generalized Likelihood Ratio (GLR) procedure. We present extensive numerical experiments to validate our theoretical results and the competitive performance of the proposed method.

近年来，在平衡（超级）图分配算法的设计和评估中取得了重大进展。我们调查了过去十年的实用算法的趋势，用于平衡（超级）图形分区以及未来的研究方向。我们的工作是对先前有关该主题的调查的更新。特别是，该调查还通过涵盖了超图形分区和流算法来扩展先前的调查，并额外关注并行算法。

Pre-publication draft of a book to be published byMorgan & Claypool publishers. Unedited version released with permission. All relevant copyrights held by the author and publisher extend to this pre-publication draft.