On the Asymptotic Convergence of Subgraph Generated Models
We study a family of random graph models - termed subgraph generated models (SUGMs) - initially developed by Chandrasekhar and Jackson in which higher-order structures are explicitly included in the network formation process. We use matrix concentration inequalities to show convergence of the adjacency matrix of networks realized from such SUGMs to the expected adjacency matrix as a function of the network size. We apply this result to study concentration of centrality measures (such as degree, eigenvector, and Katz centrality) in sampled networks to the corresponding centralities in the expected network, thus proving that node importance can be predicted from knowledge of the random graph model without the need of exact network data.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods
In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon--Fletcher--Powell (DFP) method and the Broyden--Fletcher--Goldf…
A Convergence Theorem for the Graph Shift-type Algorithms
Graph Shift (GS) algorithms are recently focused as a promising approach for discovering dense subgraphs in noisy data. However, there are no theoretical foundations for proving the convergence of the GS Algorithm. In th…
Vocal Bursts Type PredictionQuantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential
Stochastic gradient descent (SGD) is the main algorithm behind a large body of work in machine learning. In many cases, constraints are enforced via projections, leading to projected stochastic gradient algorithms. In re…
Provably Convergent Subgraph-wise Sampling for Fast GNN Training
Subgraph-wise sampling -- a promising class of mini-batch training techniques for graph neural networks (GNNs -- is critical for real-world applications. During the message passing (MP) in GNNs, subgraph-wise sampling me…
LMC: Fast Training of GNNs via Subgraph Sampling with Provable Convergence
The message passing-based graph neural networks (GNNs) have achieved great success in many real-world applications. However, training GNNs on large-scale graphs suffers from the well-known neighbor explosion problem, i.e…