Learning Influence-Receptivity Network Structure with Guarantee

Ming Yu, Varun Gupta, Mladen Kolar

TL;DR

This paper introduces a novel latent model for social and citation networks where connections aren't static but depend on the specific topic of an interaction. By decomposing network structure into node-specific "influence" and "receptivity" vectors, the authors provide an interpretable framework that accurately recovers hidden structures with strong theoretical guarantees on estimation error.

What Problem Does This Paper Address?

Traditional network analysis often assumes a single, static adjacency matrix (who is connected to whom). However, real-world relationships are context-dependent. For example, a researcher might collaborate with one peer on "string theory" but an entirely different peer on "nonparametric statistics."

Existing models like the Stochastic Block Model (SBM) or simple information diffusion models struggle to capture this "topic-aware" connectivity. They either ignore the content of the interaction entirely or require an impractical number of parameters to model every possible topic-specific network. The challenge is to learn these latent structures from noisy observations (like a sequence of cascades or collaborations) while ensuring the math actually converges to the truth.

Methods

The authors propose the Influence-Receptivity Model. Each node $j$ is assigned two $K$-dimensional vectors (where $K$ is the number of topics):

  1. Influence Vector ($B_1$): How authoritative/influential node $j$ is on each topic.
  2. Receptivity Vector ($B_2$): How susceptible/receptive node $j$ is to each topic.

For any specific event $i$ (like a paper or a tweet) with a topic distribution $m_i$, the connection intensity between node $j$ and node $\ell$ is modeled as: $$X^*_i = \sum_{k=1}^K b^1_{jk} \cdot m_{ik} \cdot b^2_{\ell k}$$

To solve this, the authors use Alternating Proximal Gradient Descent. Because the model is non-convex (and thus prone to getting stuck in local optima), they introduce a balancing regularization term to ensure the magnitudes of influence and receptivity stay "in sync." They also include a hard thresholding step to encourage sparsity, reflecting the reality that most people are only interested in a few specific topics.

Datasets

The model was evaluated on two fronts:

  • Synthetic Data: A controlled environment with 200 nodes and 10 topics to test the algorithm's ability to recover ground truth under varying noise levels and sample sizes.
  • ArXiv High Energy Physics Theory (HEP-TH): A real-world dataset covering papers from 1993 to 2003. The authors treated authors as nodes and individual publications as observations, using the paper's abstract to derive topic distributions.

Key Insights and Ideas

  • Asymmetric Roles: Unlike many community detection models, this model explicitly recognizes that being a "leader" (high influence) in a topic is different from being a "follower" (high receptivity). An eminent professor might have high influence but low receptivity, while a young researcher might be the opposite.
  • Parameter Efficiency: A model that learns a full $p \times p$ matrix for every topic $K$ would require $p^2K$ parameters, leading to massive overfitting. This model uses only $2pK$ parameters. Since the number of nodes ($p$) is usually much larger than the number of topics ($K$), this is a huge reduction that makes the model much more robust.
  • Theoretical "Safety Net": The paper provides a rigorous proof that their algorithm converges linearly to the true parameters (up to a statistical error floor), even when the topic distributions of the events are unknown and must be learned alongside the network structure.

Key Results

  • Superior Prediction: In both real-valued and binary synthetic tests, the Influence-Receptivity model significantly outperformed "One matrix" (static) and "K matrices" (topic-specific but unstructured) baselines in predicting unseen links.
  • Interpretability: On the ArXiv data, the model successfully mapped famous physicists to their actual research areas. For instance, Edward Witten was correctly identified with high influence in "string theory" and "algebraic space," matching his real-world contributions.
  • Generalization: The model showed much lower testing error than the "K matrices" approach, which suffered from severe overfitting due to its high parameter count.

Limitations and Future Work

  • Static Latent Vectors: The model assumes that a person's influence and receptivity are fixed over the observation period. In reality, expertise and interests evolve over time.
  • Topic Source: Currently, the model either assumes topics are known or learns them purely from the network structure. The authors suggest that a "joint" model combining the network structure with Natural Language Processing (NLP) on the text of the interactions could be even more powerful.
  • Computational Scaling: While more efficient than some models, the gradient calculations still scale with $O(p^2K)$, which might be challenging for massive social networks with millions of nodes without further optimization.

Summary updated

Abstract

Traditional works on community detection from observations of information cascade assume that a single adjacency matrix parametrizes all the observed cascades. However, in reality the connection structure usually does not stay the same across cascades. For example, different people have different topics of interest, therefore the connection structure depends on the information/topic content of the cascade. In this paper we consider the case where we observe a sequence of noisy adjacency matrices triggered by information/event with different topic distributions. We propose a novel latent model using the intuition that a connection is more likely to exist between two nodes if they are interested in similar topics, which are common with the information/event. Specifically, we endow each node with two node-topic vectors: an influence vector that measures how influential/authoritative they are on each topic; and a receptivity vector that measures how receptive/susceptible they are to each topic. We show how these two node-topic structures can be estimated from observed adjacency matrices with theoretical guarantee on estimation error, in cases where the topic distributions of the information/event are known, as well as when they are unknown. Experiments on synthetic and real data demonstrate the effectiveness of our model and superior performance compared to state-of-the-art methods.
BibTeX
@inproceedings{yu2019learning,
  author = {Ming Yu and Varun Gupta and Mladen Kolar},
  title = {{Learning Influence-Receptivity Network Structure with Guarantee}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=HeW5CR2jInu},
}
Figure