论文标题
块Approximated指数随机图
Block-Approximated Exponential Random Graphs
论文作者
论文摘要
指数随机图（ERG）领域的一个重要挑战是在大图上拟合非平凡的ERG。 By utilizing fast matrix block-approximation techniques, we propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions, while being able to meaningfully model both local information of the graph (e.g., degrees) as well as global information (e.g., clustering coefficient, assortativity, etc.) if desired.这允许人们有效地生成具有与观察到的网络相似属性的随机网络，并且这些模型可用于多个下游任务，例如链接预测。我们的方法可扩展到由数百万节点组成的稀疏图。经验评估表明，使用最先进的方法在速度和准确性方面表明了竞争力 - 通常基于将图表嵌入到一些低维空间中 - 用于链接预测，展示了该任务的更直接和可解释的概率模型的潜力。
An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. By utilizing fast matrix block-approximation techniques, we propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions, while being able to meaningfully model both local information of the graph (e.g., degrees) as well as global information (e.g., clustering coefficient, assortativity, etc.) if desired. This allows one to efficiently generate random networks with similar properties as an observed network, and the models can be used for several downstream tasks such as link prediction. Our methods are scalable to sparse graphs consisting of millions of nodes. Empirical evaluation demonstrates competitiveness in terms of both speed and accuracy with state-of-the-art methods -- which are typically based on embedding the graph into some low-dimensional space -- for link prediction, showcasing the potential of a more direct and interpretable probabalistic model for this task.
