PaperlayerView exact revision on arXiv

Source-linked AI summary

Estimating network edge probabilities by neighborhood smoothing

Yuan Zhang, Elizaveta Levina, Ji Zhu

arXiv:1509.08588v3stat.ML

TL;DR

Estimating edge probabilities from one observed network requires assumptions about the probability matrix’s structure. The paper proposes computationally efficient neighborhood smoothing to estimate that matrix directly, and reports strong performance across varied synthetic-network scenarios compared with the methods tested.

  • Problem

    Edge probabilities cannot be estimated from a single observed adjacency matrix without assuming some structure in the probability matrix.

    Source: §1 · p. 1

  • Method

    Neighborhood smoothing estimates the edge-probability matrix by selecting similar node neighborhoods rather than imposing a priori structural assumptions.

    Source: §1 · p. 3, Neighborhood smoothing for edge… · p. 4

  • Results

    Across the synthetic graphons tested, neighborhood smoothing performs well over a broad range of scenarios, while compared methods fail when their structural assumptions do not hold.

    Source: §3 · p. 9

  • Takeaways & Limitations

    Adaptive neighborhood choice supports performance across different graphon conditions, and the method is computationally efficient, easy to implement, and essentially tuning free.

    Source: §5 · p. 10

    The method’s piecewise Lipschitz condition can lead to over-smoothing, it does not attain the minimax error rate, and relaxing the independent-edges assumption remains a challenge.

    Source: §5 · p. 11

Abstract

from arXiv · show

The estimation of probabilities of network edges from the observed adjacency matrix has important applications to predicting missing links and network denoising. It has usually been addressed by estimating the graphon, a function that determines the matrix of edge probabilities, but this is ill-defined without strong assumptions on the network structure. Here we propose a novel computationally efficient method, based on neighborhood smoothing to estimate the expectation of the adjacency matrix directly, without making the structural assumptions that graphon estimation requires. The neighborhood smoothing method requires little tuning, has a competitive mean-squared error rate, and outperforms many benchmark methods on link prediction in simulated and real networks.

1. INTRODUCTION

Estimating a network’s edge-probability matrix from one observed adjacency matrix requires assumptions about its structure. The paper motivates neighborhood smoothing as a computationally efficient alternative for estimating that matrix across a broad range of network structures.

1. INTRODUCTION

  • A single observed adjacency matrix cannot identify edge probabilities without some structure, while community models make estimation possible through a smaller set of block probabilities.The stochastic block model’s main fitting challenge is estimating the blocks themselves.Source: §1 · p. 1
  • Graphon-based representations describe edge probabilities using latent node positions, but the graphon function is not uniquely identifiable under measure-preserving transformations.A non-decreasing expected-degree condition can make a canonical representation identifiable, but strict monotonicity is strong and excludes the stochastic block model.Source: §1 · p. 2
  • Existing approaches either rely on structural conditions or incur computational or statistical costs: sort-and-smooth assumes monotone degrees, while universal singular value thresholding has a slower error rate.Block-partition methods can achieve minimax error adaptively but require evaluating partitions; the paper also notes their computational infeasibility.Source: §1 · p. 3
  • The proposed computationally efficient neighborhood-smoothing method estimates the edge-probability matrix for piecewise Lipschitz graphons without strong graphon assumptions.Its adaptive neighborhood selection is intended to work across low- and full-rank graphons, with and without monotone degrees.Source: §1 · p. 3

Neighborhood smoothing for edge probability estimation

The method estimates the probability matrix for the observed latent positions rather than estimating the graphon itself. It uses neighborhoods of nodes with similar adjacency-matrix rows to smooth edge observations.

Neighborhood smoothing for edge probability estimation

  • The target is the edge-probability matrix P for the particular latent positions that generated the observed adjacency matrix, not the graphon function f.The matrix entries are Bernoulli edge probabilities.Source: Neighborhood smoothing for edge… · p. 3
  • Neighborhood smoothing estimates a node’s probability row by averaging adjacency rows from nodes whose probability rows are similar.The passage motivates this approach by analogy with nonparametric regression, although the latent positions are unobserved.Source: Neighborhood smoothing for edge… · p. 3
  • For undirected networks, the method uses a symmetric estimator; the stated alternative of averaging over N_i × N_j is avoided to allow vectorization and improve computational efficiency.This description concerns the estimator’s symmetry and computational form.Source: Neighborhood smoothing for edge… · p. 4
  • Unlike step-function approximations, neighborhood smoothing allows flexible neighborhoods that vary from node to node and can be selected without first estimating blocks.In block-based step-function methods, nodes in the same block share similar neighborhoods.Source: Neighborhood smoothing for edge… · p. 4

Neighborhood selection

Neighborhood selection uses similarity between graphon slices to identify nodes whose adjacency rows can be averaged. The method estimates a tractable upper bound on slice distance and selects neighbors by a quantile threshold.

Neighborhood selection

  • The method selects nodes with similar graphon slices, using a tractable upper bound on their distance rather than estimating the distance itself.The distance is based on an ℓ2 comparison of graphon slices; adjacency-row inner products are used to estimate its terms.Source: Neighborhood selection · p. 4
  • Adjacency inner products estimate the distance terms; similar-slice nodes serve as proxies for otherwise difficult self-inner-products, with unknown latent positions handled by rearranging the expression.The third term is estimated by 2⟨Ai·, Ai′·⟩/n; the proxy-node approximation is motivated under a Lipschitz graphon.Source: Neighborhood selection · p. 4
  • Quantile thresholding adapts neighborhood selection to networks with differing degree distributions and is reported to be more stable and effective than an absolute threshold.The quantile is taken over estimated distances, with h as a tuning parameter.Source: Neighborhood selection · p. 5
  • Neighbors may have similar graphon slices without similar latent positions, so the method does not need to estimate latent positions or the graphon itself.In a stochastic block model, nodes in the same block may be equally likely to enter one another’s neighborhoods regardless of their latent positions.Source: Neighborhood selection · p. 5

Consistency of the neighborhood smoothing estimator

For piecewise Lipschitz graphons, the section establishes error bounds for neighborhood smoothing under stated conditions. It also reports near rate-optimality up to a log n factor, while efficient attainment of the minimax rate for general δ remains open.

Consistency of the neighborhood smoothing estimator

  • Under piecewise Lipschitz conditions, Theorem 1 gives an error bound for the estimator with h=C(n^-1 log n)^1/2; the estimator is nearly rate-optimal up to a log n factor.The theorem assumes δ/(n^-1 log n)^1/2→∞; the near-optimality statement concerns the (2,∞) norm.Source: Consistency of the neighborhood… · pp. 5–6
  • Replacing the theorem’s estimator with its alternative preserves bound (12), but not necessarily bound (11).Source: Consistency of the neighborhood… · p. 6
  • The sort-and-smooth method achieves the minimax rate only under the strong assumption of strictly monotone expected node degrees.Source: Consistency of the neighborhood… · p. 6
  • For the studied graphon family when δ/(n^-1 log n)^1/2→∞, neighborhood smoothing and singular value thresholding achieve the same mean squared error rate, n^-2/3.The passage describes singular value thresholding as computationally efficient.Source: Consistency of the neighborhood… · p. 6
  • For general δ, the minimax rate is log n/n, but whether a computationally efficient method can achieve it remains open.The minimax-rate statement applies when δ/(log n/n)^1/2→∞.Source: Consistency of the neighborhood… · p. 6

3. PROBABILITY MATRIX ESTIMATION ON SYNTHETIC NETWORKS

Across four synthetic graphons, the method performs competitively across varied structures, while several benchmarks perform well only under their respective assumptions. The experiments compare estimated probability matrices using RMSE and MAE averaged over 2,000 replications.

3. PROBABILITY MATRIX ESTIMATION ON SYNTHETIC NETWORKS

  • For graphon 1, our method avoids the boundary errors of whole-region smoothing while performing among the best methods.The graphon has seven blocks; the oracle also makes boundary errors because it uses n^1/2 blocks rather than the true block count.Source: §3 · pp. 7–8
  • For graphon 2, our method, Chatterjee’s method, and n^1/3 singular value thresholding obtain the best visual approximations; Chan & Airoldi’s method fails without monotone degrees.The passage attributes spectral clustering’s poor performance likely to noise from using too many eigenvectors.Source: §3 · p. 8, Figure 1 · p. 8
  • For diagonal-dominated graphon 3, our method is the best among computationally efficient methods; n^1/3 singular value thresholding does better than Chatterjee (2015) and provides lower-resolution denoising.Source: §3 · p. 8
  • For graphon 4, all methods struggle, but our method captures global structure and curvature and has significantly lower errors than visually similar n^1/3 singular value thresholding.The graphon is full rank, has structure at different scales, and includes subtle local differences that challenge global methods.Source: §3 · pp. 8–9
  • Across all four graphons, neighborhood smoothing is very competitive with benchmarks and performs well across scenarios where assumption-specific methods can fail.The reported comparison covers RMSE and MAE averaged over 2,000 replications.Source: §3 · p. 9, Table 2 · p. 9

4. APPLICATION TO LINK PREDICTION

The paper evaluates probability-matrix estimators through link prediction, where missing edges are ranked by estimated propensity. Its method performs best overall on both simulated networks and the political blogs network.

4. APPLICATION TO LINK PREDICTION

  • Link prediction treats unobserved edges as potentially true edges or false negatives, and evaluates ranked scores through false-positive and true-positive rates.The missing-edge indicators are unobserved and the missing rate is unknown; methods produce scores or estimated probability matrices for ranking candidate links.Source: §4 · pp. 9–10
  • The benchmark set includes Jaccard, Zhao et al. (2017), and PropFlow scores, alongside probability-matrix estimation methods.PropFlow uses expected random-walk distance; Jaccard scores node pairs by neighbor overlap.Source: §4 · p. 10
  • On simulated graphons, our method outperformed all other methods, with a ROC curve very close to the curve based on the true probability matrix.The experiments used n = 500, p = 10%, and 1000 repetitions; graphon-estimation methods generally outperformed score-based methods.Source: §4 · p. 10
  • On the political blogs network, our method performed best overall among the compared methods; probability-matrix methods outperformed score-based methods.The network has two communities and heterogeneous degrees, including hubs; 10% of edges were removed at random.Source: §4 · p. 10

5. DISCUSSION

The method relies on adaptive neighborhood selection and is computationally efficient, easy to implement, and essentially tuning free. Its limitations include the piecewise Lipschitz condition, failure to attain the minimax rate, and an independent-edges assumption.

5. DISCUSSION

  • Adaptive neighborhood choice is the method’s stated strength, alongside computational efficiency, ease of implementation, and little tuning.The discussion says it works well under many different conditions.Source: §5 · p. 10
  • Figure 2 plots ROC curves for political-blog link prediction with 10% of edges missing at random, including curves for the proposed method and n1/3 singular value thresholding.The legend identifies the proposed method with a red dashed curve and singular value thresholding with a black dotted curve.Source: Figure 2 · p. 11, §5 · p. 11
  • The piecewise Lipschitz condition can occasionally lead to over-smoothing, and the method does not attain the minimax error rate.The authors state that its rate cannot be improved and leave open whether a polynomial-time method can achieve the minimax rate.Source: §5 · p. 11
  • Relaxing the independent-edges assumption is identified as a major future challenge for better fitting real-world networks.Source: §5 · p. 11

6. CHOOSING THE CONSTANT FACTOR FOR THE BANDWIDTH

The section examines how the bandwidth constant affects mean squared error across four graphons. The reported results support using C = 1 in the paper’s numerical experiments.

6. CHOOSING THE CONSTANT FACTOR FOR THE BANDWIDTH

  • Figure 3 plots mean squared error against C for four graphons, marked by a circle, asterisk, plus, and cross, respectively.Source: Figure 3 · p. 12
  • C values from 2^-2 to 2 worked equally well across four very different graphons, motivating the choice C = 1 for all numerical results.The tested networks had n = 2000 nodes, and Figure 3 varies C in h = C(n^-1 log n)^1/2.Source: §6 · pp. 11–12

7. RECEIVER OPERATING CHARACTERISTIC CURVES FOR LINK PREDICTION

For simulated networks, link-prediction results generally agree with the methods’ probability-matrix estimation performance. The method is slightly better than, but comparable to, two alternatives on the reported root mean squared (2,∞) errors.

7. RECEIVER OPERATING CHARACTERISTIC CURVES FOR LINK PREDICTION

  • The method’s link-prediction results on synthetic graphons generally agree with its performance in probability-matrix estimation.The link-prediction results are presented in Figure 4.Source: §7 · p. 12
  • Our method’s normalized root mean squared (2,∞) error is slightly better than, but comparable to, n1/3 singular value thresholding and Chatterjee (2015); all three generally outperform other practical methods.The passage suggests a possible (2,∞) error bound for low-rank methods, but says investigating it is outside the manuscript’s scope.Source: §7 · p. 12

9. PROOFS

The proofs establish bounds and constructions used in the smoothing analysis, including neighborhood-count and similarity bounds, a block-model approximation, and alternatives for Theorem 2. They also select parameters to maximize a displayed bound and specify constraints on probability matrices and block sizes.

Lemma 1

  • Lemma 1’s proof uses concentration and a union bound to control the number of nodes in each shrinking neighborhood, relying on ∆n being smaller than half the shortest partition interval..Source: §9 · pp. 14–15

Lemma 2

  • Under Lemma 2’s stated conditions, thresholding estimated distances at the lower h-th quantile, h=C0((n−1) log n)^1/2, yields neighborhoods Ni with |Ni| ≥ C0(n log n)^1/2.Source: §9 · p. 15

Proof of Theorem 1

  • Theorem 1’s proof handles neighborhood-selection dependence by bounding the summed error components and combining their bounds to complete the argument.The proof notes that individual terms cannot be bounded directly by Bernstein’s inequality because adjacency entries are not independent of neighborhood selection.Source: §9 · pp. 17–19

Proof of Proposition 1

  • For Proposition 1, the least-squares estimator has the same error rate for the paper’s graphon family, while the lower bound follows from Gao et al. (2015).The proof adapts the block partition to the continuity intervals, under a minimum interval-width condition of order greater than (n^-1 log n)^1/2.Source: §9 · p. 19

Proof of Theorem 2

  • Theorem 2’s proof constructs a three-community stochastic block model and uses Gilbert–Varshamov vectors to generate exponentially many alternative membership assignments.Lemma 3 states that at least exp(ℓ/8) binary vectors exist with a pairwise Hamming-distance condition.Source: §9 · p. 20

9. PROOFS

  • Choosing φ ≤ 1/4 puts every edge probability in (1/2, 3/4), enabling Proposition 4.2 of Gao et al. (2015); each pair of matrices differs in at most 2mn entries.Source: §9 · p. 21
  • The right-hand side is maximized by setting φ^2 = ℓ/(257mn), with ℓ ≥ max{n/3, 32}.The proof invokes Lemma 3 of Yu (1997) before this optimization.Source: §9 · p. 21
  • The constructed matrices must correspond to stochastic block models in Fδ,L, with the smallest block growing faster than (n log n)^1/2.Source: §9 · p. 21
Loading 1509.08588v3…