具有可观测边标签和不可观测节点标签的二分图中的图估计

Apr, 2023

具有可观测边标签和不可观测节点标签的二分图中的图估计

Graphon Estimation in bipartite graphs with observable edge labels and unobservable node labels

Etienne Donier-Meroz, Arnak S. Dalalyan, Francis Kramarz, Philippe Choné, Xavier D'Haultfoeuille

TL;DR本文研究了一种估计潜在变量下矩阵条件期望的方法 —— 使用图函数。通过对分段常数和 H"older 连续图函数的研究，提出最小二乘估计量和指数加权聚合的有限样本风险界。另提出使用 Lloyd 的交替最小化算法来近似该估计量。在合成数据集上进行的数值实验表明了该图函数估计器的良好性能。

Abstract

Many real-world data sets can be presented in the form of a matrix whose entries correspond to the interaction between two entities of different natures (number of times a web user visits a web page, a student's grade in a subject, a patient's rating of a doctor, etc.). We assume in this paper that the mentioned interaction is determined by unobservable

latent variables conditional expectation graphon least squares estimator alternating minimization algorithm

发现论文，激发创造

非参数图分析估计

本文提出了一种非参数分析网络的框架，基于一种自然的极限对象 —— 图源。我们证明了在一般条件下，图源估计的一致性，包括稀疏网络等重要的实际情况。我们使用档案似然方法，并将我们的结果与逼近理论、非参数函数估计和图限理论联系起来。

Sep, 2013

稀疏图的私有图汇估计

本文提出了一种基于节点差分隐私的非参数块模型逼近算法，可以保护个体成员隐私信息而又能在保证正确性的前提下对高维稀疏网络的多路径割进行估算，并给出了误差界限。

Jun, 2015

基于和平方的私有图信息估计

首次开发纯节点差分隐私算法，用于学习随机块模型和多项式时间估计图论，其统计效能保证与先前最佳的信息理论（指数时间）节点私有机制相匹配。该算法基于一个指数机制，用于基于二次优化的得分函数，其水平取决于区块数。我们结果的关键要素是：（1）在可双重随机矩阵的多面体上进行的一个二次优化问题，描述了区块图模式之间的距离；（2）多项式优化在任意多面体上的通用二次收敛结果；（3）对得分函数进行利普希茨扩展的通用方法，作为二次优化算法范例的一部分。

Mar, 2024

谱方法用于图浓度估计的收敛速率

本研究分析了一种称为通用奇异值阈值（USVT）算法的谱方法在估计 Graphon 模型中的应用，证明了其误差速率在某些情况下可以达到最小值，但在某些情况下误差较大，与社区检测的计算难度相一致。

Sep, 2017

基于随机块模型的图函数逼近：理论及一致估计

该论文提出了一种计算高效的方法，基于随机分块模型（SBA）对图形进行建模，对观察到的网络数据进行了一致的估计图谱，估计误差随着图形大小的增加而消失.

Nov, 2013

使用离散优化的稀疏高斯图模型：计算和统计视角

我们提出了一种稀疏图的学习方法，应用于一个无向高斯图模型的问题，并通过凸混合整数规划框架得到了新的估计器，该估计器在稀疏性精度矩阵的估计与变量选择方面有着优越的性能。

Jul, 2023

混合图模型的选择和估计

本文考虑了在一种成对图模型中，每个节点的条件分布都属于指数族分布这样一种参数调整问题。该文章证明了参数空间的限制条件以及基于邻域选择方法对于高维数据下的图重建方法的相容性，同时提出了在处理不同参数形式的情况下如何选择节点间边的问题，并举出高斯分布，伯努利分布，泊松分布和指数分布等实例验证了理论发现。

Nov, 2013

基于节点学习的多个高斯图模型

该论文探究了高维高斯图形模型估计问题，提出了两种假设：网络差异源于被扰动的个别节点或在所有网络中共享的公共中心节点，然后使用凸优化问题和多重乘数算法解决，并以合成数据、网页数据和癌症基因表达数据为例进行说明。

Mar, 2013

使用图侧信息的离散值潜在偏好矩阵估计

提出了一种新的模型，该模型可以更好地利用图侧信息对个性化推荐问题进行建模并准确预测用户的评分，且该模型可以容纳任何离散值的潜在偏好矩阵和用户聚类，算法性能优于现有算法。

Mar, 2020

通过结构化 Gromov-Wasserstein 重心学习 Graphons

本研究提出了一种新的方法，学习一种非参数图模型，称为图基，该模型定义于无限维空间中，表示任意大小的图，我们通过基于图基理论的弱规律引理，利用一个阶梯函数来近似图基，然后利用图基的割距可以松弛到其阶梯函数的 Gromov-Wasserstein 距离来学习一组图的对应阶梯函数。该方法不仅有效地克服了先前的方法的缺点，而且在合成和实际数据上表现出更好的性能。

Dec, 2020