Dirichlet Meets Horvitz and Thompson: Estimating Homophily in Large Networks via Sampling

Hamed Ajorlou, Gonzalo Mateos, and Luana Ruiz · 2025

Read Dirichlet Meets Horvitz and Thompson: Estimating Homophily in Large Networks via Sampling by Hamed Ajorlou, Gonzalo Mateos, and Luana Ruiz (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-17084.txt.

Introduction

Hamed Ajorlou, Gonzalo Mateos, and Luana Ruiz give a sampling method to estimate homophily in large networks, the trait of linked nodes to resemble each other. Full smoothness scores need the whole network and all node features, which privacy, scale, or churn may block.

Their frame estimates the Dirichlet energy, a Laplacian-based variation score, from sampled subgraphs with a Horvitz-Thompson estimator, which reweights by known edge inclusion odds for unbiased results. They prove the energy can be estimated consistently from samples and test other heterophily measures as well. On benchmark heterophilic data sets, the sampled estimates tracked the true structure reliably, opening network analysis to partial views.

Catalog record

CREATORHamed Ajorlou, Gonzalo Mateos, and Luana Ruiz
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE25 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2512-17084

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Dirichlet Meets Horvitz and Thompson: Estimating Homophily in Large Networks via Sampling Hamed Ajorlou, Gonzalo Mateos, and Luana Ruiz Abstract Assessing homophily in large-scale networks is central to understanding structural regularities in graphs, and thus inform the choice of models (such as graph neural networks) adopted to learn from network data. Evaluation of smoothness metrics requires access to the entire network topology and node features, which may be impractical in several large-scale, dynamic, resource-limited, or privacy-constrained settings. In this work, we propose a sampling-based framework to estimate homophily via the Dirichlet energy (Laplacian-based total variation) of graph signals, leveraging the Horvitz-Thompson (HT) estimator for unbiased inference from partial graph observations. The Dirichlet energy is a so-termed total (of squared nodal feature deviations) over graph edges; hence, estimable under general network sampling designs for which edge-inclusion probabilities can be analytically derived and used as weights in the proposed HT estimator. We establish that the Dirichlet energy can be consistently estimated from sampled graphs, and empirically study other heterophily measures as well. Experiments on several heterophilic benchmark datasets demonstrate the effectiveness of the proposed HT estimators in reliably capturing homophilic structure (or lack thereof) from sampled network measurements. I Introduction Homophily is a cardinal principle at the heart of several graph-based statistical learning tasks, including nearest-neighbor prediction, semi-supervised learning, and topology inference [ 1 , 2 , 3 ] . Accordingly, assessing homophily characteristics (i.e., the extent to which edges preferentially connect nodes with similar attributes or labels) of network datasets is central to understanding structural regularities in graphs, and, e.g., inform the choice of learning architectures such as graph neural networks (GNNs) [ 4 ] . In fact, a recent trend is to develop models for heterophilous data as well [ 2 , 5 , 6 ] . Problem statement. Consider a weighted and undirected graph G=({\mathcal{V}},{\mathcal{E}}) , with n=|{\mathcal{V}}| nodes, adjacency matrix \mathbf{A}=[A_{ij}]\in\mathbb{R}_{+}^{n\times n} , and combinatorial graph Laplacian {\mathbf{L}}=\textrm{diag}({\mathbf{A}}\mathbf{1})-{\mathbf{A}} . Let \mathbf{X}_{n}\in\mathbb{R}^{n\times f} be a graph signal matrix, where row vector {\mathbf{x}}_{i}^{\top} collects the f features at node i\in{\mathcal{V}} . A workhorse homophily (i.e., signal smoothness) metric is the Dirichlet energy or Laplacian-based total variation defined as \textrm{TV}_{G}({\mathbf{X}}_{n}):=\mathrm{trace}({\mathbf{X}}_{n}^{\top}{\mathbf{L}}{\mathbf{X}}_{n})=\sum_{(i,j)\in{\mathcal{E}}}A_{ij}\|{\mathbf{x}}_{i}-{\mathbf{x}}_{j}\|^{2}, (1) where smaller \textrm{TV}_{G}({\mathbf{X}}_{n}) values are indicative of homophilous feature characteristics in the data. The evaluation of \textrm{TV}_{G}({\mathbf{X}}_{n}) relies on the implicit assumption that the graph dataset is observed in its entirety; however, it is often the case that relational information is only acquired from a portion of the complex system of interest. Network sampling is arguably the rule rather than the exception in statistical network analysis [ 1 , Ch. 5] , either due to uncontrollable factors behind the data acquisition process; or, by design in large-scale, dynamic, resource-limited, or privacy-constrained settings. Suppose that instead of fully observing G , we take measurements that effectively produce a sampled graph G^{*}=({\mathcal{V}}^{*},{\mathcal{E}}^{*}) and signals {\mathbf{X}}_{n^{*}} , n^{*}\leq n . Consequently, it will be typically impossible to exactly recover \textrm{TV}_{G}({\mathbf{X}}_{n}) from the partial information in G^{*} . Instead, we study the problem of developing useful homophily estimates of \textrm{TV}_{G}({\mathbf{X}}_{n}) , say \widehat{\textrm{TV}} , from G^{*} and {\mathbf{X}}_{n^{*}} under various sampling designs [ 1 , 7 , 8 ] . Contributions in context. Sampling has been widely studied in graph signal processing, but often with the objective of reconstructing bandlimited graph signals from limited nodal samples (yet G is known in its entirety) [ 9 ] . Recent efforts have explored efficient training of GNNs from intentionally sampled homophilous graphs [ 10 ] . Our distinct goal is to estimate a global structural characteristic of a network (here homophily) in an unbiased fashion, and with quantifiable performance. In Section II , we start by establishing a fundamental property of the estimation problem, namely that the Dirichlet energy is a so-termed testable graph parameter under induced subgraph sampling. As introduced in [ 11 ] , testability of a network summary statistic is tantamount to the existence of an estimator satisfying a weak form of consistency as the sample size increases. The upshot is that, for testable parameters, one would expect that simple (e.g., plug-in \widehat{\textrm{TV}}=\textrm{TV}_{G^{*}}({\mathbf{X}}_{n^{*}}) ) estimators will be accurate under induced subgraph sampling. For our technical arguments, we extend the seminal characterizations of testability based solely on convergence of graph sequences to graph limits (i.e., graphons) [ 11 ] , to also accommodate sequences of convergent graph signals [ 12 ] . Although the testability result has merit to ensure the estimation task is feasible under induced subgraph sampling, other sampling designs could be of interest as well. And it is not uncommon for these to produce unequal probability sampling of nodes or edges, challenging the reliability of biased plug-in estimators [ 13 , Ch. 3] . To bridge this gap, in Section III we propose an homophily estimation framework by leveraging the Horvitz-Thompson (HT) estimator for unbiased inference from incomplete graph measurements. The Dirichlet energy ( 1 ) is a total (of squared nodal feature deviations) over graph edges. Thus, estimable under general network sampling designs for which edge-inclusion probabilities can be analytically derived and used as weights in the proposed HT estimator. Interestingly, the variance of \widehat{\textrm{TV}} can be readily estimated from the sample G^{*} and {\mathbf{X}}_{n^{*}} . We experimentally verify the unbiasedness of the HT estimator and examine how different sampling rates influence its variance (Section IV ). To gain further insight into the behavior of the estimator across a range of practical scenarios, we compare multiple network sampling designs and heterophily measures beyond ( 1 ). All in all, the main contributions of this work can be summarized as follows: • We establish that the Dirichlet energy is a testable graph parameter under induced subgraph sampling. • We develop a novel HT estimator for unbiased estimation of homophily measures under general sampling designs. • We conduct a comprehensive experimental evaluation using several heterophilic benchmark datasets. II Testability of the Dirichlet Energy This section leverages results from the theory of graph limits to establish that the Dirichlet energy is a testable graph (signal) parameter. Following [ 11 , Def. 2.11] , a graph parameter \varphi is said to be testable if for every \varepsilon>0 there exists a sample size n^{*}(\epsilon) such that for any graph G with n\geq n^{*}(\epsilon) , an estimate \widehat{\varphi}(G^{*}) computed from a uniformly sampled induced subgraph G^{*} satisfies \text{P}\left(\,|\varphi(G)-\widehat{\varphi}(G^{*})|>\varepsilon\right)\leq\varepsilon. Accordingly, testability of \varphi implies the existence of an estimator \widehat{\varphi}(G^{*}) that satisfies a weak form of consistency. A key result [ 11 , Prop. 2.12(a)] asserts that \varphi is testable if and only if \varphi(G_{i}) converges for every convergent graph sequence G_{1},G_{2},\ldots , which naturally leads to graphons and the theory of graph limits [ 14 , 11 ] . Thus, a suitable notion of continuity of \varphi suffices. To establish the testability of the Dirichlet energy (a more general parameter than the graph signal-agnostic \varphi(G) studied in [ 11 ] ), we first recall the graph limit framework and explain how it naturally extends to continuous domain representations of graph signals [ 12 ] . A graphon is a symmetric measurable function {\mathbf{W}}:[0,1]^{2}\mapsto{\mathbb{R}} that arises as the limit of a sequence of dense graphs w.r.t. the cut metric. The cut norm, which underlies the notion of

Read the complete text