Source-linked AI summary
On the Convexity of Latent Social Network Inference
Seth A. Myers, Jure Leskovec
TL;DR
The paper asks how to infer an unobserved social network when diffusion data reveals infection times but not infection links. It formulates maximum-likelihood inference as a sparse convex program, achieving near-perfect network and propagation-parameter recovery while scaling to large networks.
Problem
The paper addresses reconstruction of latent social networks from diffusion data when only infected-node identities or infection times are observed, not infection sources or edges.
Method
The method builds a probabilistic contagion model, maximizes the likelihood of observed diffusion data, and converts the problem into a convex program with an l1-like sparsity penalty.
Results
Near-perfect recovery of the underlying network structure and edge-transmission parameters was achieved across synthetic and real-world networks and several propagation models.
Takeaways & Limitations
The approach provides an optimality-guaranteed and scalable solution for inferring sparse latent networks, including networks with thousands of nodes.
Takeaways & Limitations
Future work remains to learn the diffusion-time parameters w(t), extend the method to additional diffusion models, and apply it to other datasets.
Abstract
from arXiv · showhide
In many real-world scenarios, it is nearly impossible to collect explicit social network data. In such cases, whole networks must be inferred from underlying observations. Here, we formulate the problem of inferring latent social networks based on network diffusion or disease propagation data. We consider contagions propagating over the edges of an unobserved social network, where we only observe the times when nodes became infected, but not who infected them. Given such node infection times, we then identify the optimal network that best explains the observed data. We present a maximum likelihood approach based on convex programming with a l1-like penalty term that encourages sparsity. Experiments on real and synthetic data reveal that our method near-perfectly recovers the underlying network structure as well as the parameters of the contagion propagation model. Moreover, our approach scales well as it can infer optimal networks of thousands of nodes in a matter of minutes.
1 Introduction
The paper targets latent-network inference when explicit social ties are unavailable, using contagion infection times to reconstruct the network. It develops a convex, sparse approach that extends beyond prior methods based on observed pairwise interactions or homogeneous edge weights.
- Motivation: Explicit social-network data is expensive to collect and often unavailable for hidden or hard-to-reach populations.Traditional studies typically involved fewer than 100 people, while some populations cannot feasibly provide complete network data.
- Prior Work: Earlier network-inference methods generally assume pairwise interaction data and reduce inference to selecting an edge threshold.Examples include cellphone-call and email records, where an edge is included when interactions exceed τ.
- Problem: The proposed setting observes only node infection times during diffusion, not the edges or sources through which contagion spread.The framework covers contagions such as disease, information, and product adoption.
- Approach: The method formulates latent-network inference through convex programming with an l1-like penalty that encourages sparsity.It begins with a probabilistic diffusion model and the likelihood of observed cascades under candidate networks and propagation parameters.
- Related Work: Graphical Lasso and related graphical-model methods estimate dependency structures, but the paper instead regresses infection times while addressing diffusion-specific network inference.The cited graphical-model formulations can be intractable and may require heuristic solutions.
- Novelty: Unlike NetInf, which assumes homogeneous latent-edge weights and uses approximation, the proposed approach removes that assumption and guarantees optimality.The paper also states that the approach handles networks with thousands of nodes.
2 Problem Formulation and the Proposed Method
The paper infers weighted latent social networks from observed infection times using a maximum-likelihood formulation transformed into convex, sparsity-promoting optimization problems. The method models contagion dynamics, decomposes network inference by destination node, and preserves global optimality while reducing computation.
- Cascade model: The cascade model uses transmission probabilities A_ij, transmission-time distribution w(t), and recovery model r(t) to describe contagion dynamics.The primary analysis focuses on the SI model, where infected nodes remain infected indefinitely, while SIS and SIR models are also supported.
- Problem formulation: The method infers a weighted adjacency matrix from cascade infection times when infection sources and transmission edges are unobserved.Each A_ij represents the conditional probability that node i infects node j.
- Maximum likelihood: The likelihood combines the probability that each observed infection was caused by a previously infected neighbor with the probability that each uninfected node was never infected.Cascades and infections are treated as conditionally independent, and SIS cascades require including multiple infection times.
- Scalable optimization: Inference can be decomposed into N independent subproblems, one for each node’s incoming edges, reducing each optimization to N − 1 variables.Edges from nodes that never co-occur with the destination in a cascade can be excluded because their maximum-likelihood value is zero.
- Convex formulation: A variable transformation and logarithm convert the likelihood problem into a convex optimization problem, guaranteeing convergence to a globally optimal solution.The transformed formulation uses geometric-program structure before logarithmic convexification.
- Network sparsity: The proposed ρ∑(1−A_ji) penalty promotes sparse solutions while preserving global convexity, unlike directly convexifying the original l1 penalty.The implementation first uses the sparsity penalty for edge prediction, whose estimated transmission probabilities can be distorted and therefore require correction.
3 Experiments
ConNIe was evaluated on synthetic and real networks using simulated or real diffusion data, with edge recovery and transmission-probability estimation assessed against NetInf. Across these settings, it achieved high precision-recall performance, low estimation error, and robustness to noisy infection times.
- Datasets and setup: ConNIe was evaluated on synthetic networks, real email and collaboration networks, and a real recommendation network using diffusion data.Synthetic experiments used 512-node scale-free and Erdős-Rényi networks; real experiments included email, collaboration, and recommendation data.
- Evaluation: The evaluation measured edge-prediction precision and recall together with mean-square error for estimated edge transmission probabilities.Precision and recall were varied through the sparsity parameter ρ, while MSE included true and predicted edge positions, assigning zero weight to absent edges.
- Synthetic data: Above 0.85 was ConNIe’s synthetic precision-recall break-even point across power-law, exponential, and Weibull transmission models.The comparison used a scale-free synthetic network, and the Erdős-Rényi results were reported as very similar but omitted from the figure.
- Synthetic data: Less than 0.05 was ConNIe’s synthetic edge-weight estimation error, more than a factor of two smaller than NetInf’s error.The comparison reflects heterogeneous synthetic edge weights, whereas NetInf assumes homogeneous weights.
- Robustness: 0.4 noise-to-signal ratio was sufficient for ConNIe to retain accurate network inference under independent normally distributed perturbations to infection times.Robustness was evaluated using precision-recall break-even point and edge MSE as functions of observed cascades and infection-time noise.
- Real social networks: Around 0.95 break-even points and less than 0.03 transmission-probability estimation error were obtained on both the email and collaboration datasets.The authors characterize this as near-perfect recovery from a relatively small number of contagions.
4 Conclusion
The paper presents a general, optimality-guaranteed convex solution for inferring latent social networks from diffusion data, with sparsity regularization. Experiments show near-perfect recovery and scalability to networks of thousands of nodes, while future work includes learning diffusion-time parameters and extending datasets and models.
- The method provides a general solution for inferring latent social networks from network diffusion data.
- Maximum likelihood optimization is converted into an equivalent convex problem, guaranteeing an optimal solution while l1 regularization enforces sparsity.
- Experiments across synthetic and real-world networks and multiple cascade models find near-perfect recovery of network structure and edge-transmission parameters.
- The approach scales to inferring optimal networks on thousand-node graphs in a matter of minutes.
- Future work includes learning the diffusion-time parameters w(t), applying the method to additional datasets, and extending it to other diffusion models.