Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model

Myunghwan Kim, Jure Leskovec

Abstract

Traditional network models often separate mechanistic growth processes from statistical parameter estimation, frequently neglecting the role of node attributes in shaping topology. We present the Multiplicative Attribute Graph (MAG) model, which defines edge probabilities as the product of attribute-specific affinity matrices. This framework is both statistically expressive and analytically tractable. We further introduce MagFit, a variational EM algorithm that utilizes a sparse-graph approximation to achieve near-linear scalability. Evaluations on LinkedIn, Yahoo!-Answers, and AddHealth datasets demonstrate that MAG significantly outperforms existing Kronecker-based models in structural accuracy and probabilistic fit while capturing complex social phenomena like homophily and core-periphery structures.

Introduction

In network science, a persistent challenge is bridging the gap between what nodes are (their attributes) and how they connect (the resulting topology). While mechanistic models explain growth and statistical models estimate parameters, node attributes—such as age, location, or interests—are often overlooked or lead to mathematically intractable frameworks. The Multiplicative Attribute Graph (MAG) model addresses this by using node features to explain network shape in a way that remains mathematically studyable.

The Multiplicative Attribute Graph Model

The core of the MAG model is the multiplicative rule for link formation. Each node $i$ is associated with a vector of categorical attributes $F_i$. For each attribute $l$, an affinity matrix $\Theta_l$ defines the probability of a link forming between two nodes based on that specific trait.

The Multiplicative Rule for link probability calculation.

As shown in Figure 1, the total probability $p_{ij}$ of an edge between nodes $i$ and $j$ is the product of the entries selected from the affinity matrices corresponding to their shared or differing attributes. This flexibility allows MAG to simultaneously model homophily (similarity-based linking), heterophily (difference-based linking), and core-periphery structures. Notably, the popular Kronecker Graph model is a special case of MAG where all affinity matrices are identical.

Parameter Estimation and Scalability

Fitting MAG to large-scale networks presents a significant combinatorial challenge. The authors developed MagFit, a parameter estimation method based on Variational Expectation-Maximization. To ensure the model learns independent and meaningful features, a mutual information regularization term is included.

A primary hurdle in fitting such models is the $O(N^2)$ complexity required to calculate probabilities for all node pairs. MagFit overcomes this using a "Sparse Graph" speedup. By calculating the gradient for an "empty" graph and applying corrections only for existing edges, the complexity is reduced to near-linear time, $O(N+E)$, where $N$ is the number of nodes and $E$ is the number of edges.

Execution time comparison between Naive and Fast MagFit implementations.

As illustrated in Figure 5, the "Fast" version of the algorithm exhibits near-linear scaling with the number of nodes, significantly outperforming the naive $O(N^2)$ implementation and allowing the model to scale to large real-world datasets.

Experimental Results

The model was evaluated against synthetic and real-world datasets, including LinkedIn, Yahoo!-Answers, and the AddHealth high-school friendship network.

  • Structural Accuracy: MAG outperformed Kronecker models by 50-70% across metrics such as degree distribution and clustering coefficients.
  • Probabilistic Fit: MAG showed a 50-60% improvement in log-likelihood over baselines. Its True Positive Rate Improvement (TPI) was 23 to 35 times better than the Kronecker model.
  • Real-World Interpretation: In the AddHealth dataset, which includes ground-truth student attributes, MAG correctly identified "School Year" and "AP English" as primary drivers of homophily, where students in the same year were much more likely to connect.

Conclusion

The Multiplicative Attribute Graph model provides a powerful framework for integrating node attributes into network analysis. By combining statistical expressiveness with computational efficiency, MAG enables a deeper understanding of the interplay between individual characteristics and global network topology. Future work may extend this model to continuous attributes and semi-supervised settings where some node attributes are missing or noisy.

Summary updated

BibTeX
@inproceedings{kim2011modeling,
  author = {Myunghwan Kim and Jure Leskovec},
  title = {{Modeling Social Networks with Node Attributes using the Multiplicative Attribute Graph Model}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2011},
}
Figure