U-statistics on network-structured data with kernels of degree larger than one

Yuyi Wang, Christos Pelekis, Jan RamonSSDM@ECML/PKDD 2014 · OpenReview

Abstract

Most analysis of U-statistics assumes that data points are independent or stationary. However, when we analyze network data, these two assumptions do not hold any more. We first define the problem and develop a theoretical framework for applying U-statistics to data structured as a network. By using linear and convex programming, we show how to assign optimal weights to data samples to minimize variance and provide "safe" confidence bounds, even when data points are highly correlated.

Introduction

Classical statistical methods frequently rely on the "i.i.d." (Independent and Identically Distributed) assumption. In real-world scenarios such as social networks, recommendation engines, or protein interactions, data points are often "networked." These points share common components and exhibit complex dependencies that violate traditional assumptions. This research, published in the Journal of Machine Learning Research, addresses the fundamental challenge of applying U-statistics—estimators like sample variance or Kendall’s $\tau$—to such networked data.

Problem Formulation

U-statistics involve looking at tuples of data, such as comparing every pair of points. When these points are nodes or edges in a graph, standard calculations for variance and concentration (the likelihood of an estimate deviating from the truth) are no longer valid. The primary goal of this research is to provide a mathematically sound method for using these estimators on relational data without overestimating the certainty of the results.

Methods: Weighted U-statistics

The authors introduce Weighted U-statistics for networked data. Instead of a simple average, a weight $w_{i,j}$ is assigned to each pair of data points. The framework rests on three technical pillars:

  1. Hoeffding’s Decomposition for Networks: This classic technique is adapted to account for "overlap" between networked samples, such as two edges sharing a common vertex.
  2. Linear Programming (LP) for Concentration: An LP is formulated to find weights that maximize the "effective" sample size while ensuring no single vertex has disproportionate influence.
  3. Convex Programming for Minimum Variance: A quadratically constrained program finds weights that minimize "worst-case" variance, ensuring robustness even when the underlying data distribution is unknown.

Illustrative Example: Bipartite Graphs

To demonstrate how dependencies arise, the authors utilize a bipartite graph structure. For instance, in a dataset of movie ratings, multiple users (nodes 1-4) might rate the same set of movies (nodes 5-7).

A bipartite graph representing dependencies between nodes, such as users (1-4) and movies (5-7).

In this structure, the ratings are linked by the movies themselves. The proposed weighting method automatically down-weights pairs that share more connections, leading to more reliable estimates than simple unweighted averages.

Key Insights

  • Vertex-Bounded Constraint: Stable estimates require limiting the contribution of any single node. This prevents "influencer" nodes from biasing the entire U-statistic.
  • The $s'$-value: This value, derived from the linear program, represents the "effective number of independent observations" within the dependent network.
  • Optimal Weighting: The paper proves that unweighted averages are often sub-optimal in networked data. Some pairs are "noisier" because they share more connections; the authors' method automatically down-weights these to produce a more reliable result.

Key Results

  • Theorem 2 (Variance Bound): Establishes a tight upper bound on the variance of a weighted U-statistic based on the network's overlap index.
  • Theorem 4 (Concentration Bound): Provides an exponential bound (similar to Hoeffding’s Inequality) for networked data, showing that error probability decreases exponentially relative to the optimized weight sum $|w|$.
  • Computational Efficiency: Optimal weights can be calculated in polynomial time using standard optimization solvers, making the method practical for real-world engineering applications.

Limitations and Future Work

While the results can be extended to $k$-partite hypergraphs, the current derivations focus primarily on bipartite structures and kernels of degree 2 (comparing pairs). Future research may explore extensions to V-statistics, which include self-comparisons and may offer lower variance in specific settings.

Summary updated

Abstract

Most analysis of U-statistics assumes that data points are independent or stationary. However, when we analyze network data, these two assumptions do not hold any more. We first define the problem ...
BibTeX
@inproceedings{wang2014u,
  author = {Yuyi Wang and Christos Pelekis and Jan Ramon},
  title = {{U-statistics on network-structured data with kernels of degree larger than one}},
  booktitle = {SSDM@ECML/PKDD},
  year = {2014},
  url = {https://openreview.net/forum?id=_IVjd8fKW6YX},
}
Figure