Learning Influence-Receptivity Network Structure with Guarantee

Ming Yu, Varun Gupta, Mladen Kolar

Introduction

Traditional network modeling often assumes that the strength of a connection between two nodes is static. However, in real-world scenarios like social media or academic citations, interactions are typically driven by specific topics. For instance, two researchers might frequently cite each other on "machine learning" but never on "gardening." Standard models, such as the Stochastic Block Model, rely on a single adjacency matrix, failing to capture how the underlying connection structure shifts based on the topic of interaction.

This paper introduces a latent model that endows each node with specific "influence" and "receptivity" scores across various topics. By observing a sequence of interactions, the proposed algorithm can recover these hidden structures with provable theoretical guarantees, outperforming state-of-the-art methods in both efficiency and accuracy.

The Influence-Receptivity Model

The authors propose a parameter-efficient approach called the Influence-Receptivity Model. Instead of a massive $p \times p$ matrix to represent the network (where $p$ is the number of nodes), they use two $p \times K$ matrices, where $K$ is the number of topics:

  1. Influence Matrix ($B_1$): Measures how authoritative a node is on each topic.
  2. Receptivity Matrix ($B_2$): Measures how susceptible or interested a node is in each topic.

For any event with a known or unknown topic distribution, the probability of an edge forming between two nodes is determined by the weighted sum of their respective influence and receptivity scores. This separation of roles captures directed dynamics—such as a prominent professor who influences many but is receptive only to a few peers.

Efficiency and Generalization

A major advantage of this model is its parameter efficiency. While traditional "K-matrix" models require $p^2 K$ parameters, this model only requires $2pK$. This reduction prevents the model from overfitting to noise, a common issue in complex network analysis.

Table 1: Comparison of model complexity and error rates on the ArXiv dataset. Our method achieves the lowest test error with a fraction of the parameters used by other models.

As shown in the results above, the proposed method achieves significantly lower test error compared to unconstrained models, despite having a higher training error. This indicates that the influence-receptivity structure captures the true underlying dynamics of the network rather than just memorizing the training data.

Interpretability in Real-World Networks

The model's effectiveness was tested on an ArXiv collaboration and citation dataset containing high-energy physics papers. The algorithm successfully identified the research specialties of prominent physicists based solely on their citation patterns.

Table 2: Learned topic distributions for prominent physicists. The model accurately maps authors to their respective fields, such as Ashoke Sen's focus on string theory and black holes.

For example, the model correctly identified Ashoke Sen’s primary interests in "string theory" and "black holes." This level of interpretability, combined with a "safety net" of theoretical guarantees—proving linear convergence to the true structure—makes the model a robust tool for analyzing complex, topic-driven networks.

Conclusion

By moving beyond static adjacency matrices, the Influence-Receptivity Model provides a more nuanced and accurate representation of real-world interactions. Future work may involve integrating natural language processing to link latent topics directly to text or adding time-varying components to capture how a node's interests evolve over time.

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/events 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/events 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