Estimating latent feature-feature interactions in large feature-rich graphs

DOI10.24166/IM.14.2017zbMATH Open1491.68167arXiv1612.00984OpenAlexW2962678600MaRDI QIDQ3389688FDOQ3389688

Authors: Corrado Monti, Paolo Boldi 

Publication date: 23 March 2022

Published in: Internet Mathematics (Search for Journal in Brave)

Abstract: Real-world complex networks describe connections between objects; in reality, those objects are often endowed with some kind of features. How does the presence or absence of such features interplay with the network link structure? Although the situation here described is truly ubiquitous, there is a limited body of research dealing with large graphs of this kind. Many previous works considered homophily as the only possible transmission mechanism translating node features into links. Other authors, instead, developed more sophisticated models, that are able to handle complex feature interactions, but are unfit to scale to very large networks. We expand on the MGJ model, where interactions between pairs of features can foster or discourage link formation. In this work, we will investigate how to estimate the latent feature-feature interactions in this model. We shall propose two solutions: the first one assumes feature independence and it is essentially based on Naive Bayes; the second one, which relaxes the independence assumption assumption, is based on perceptrons. In fact, we show it is possible to cast the model equation in order to see it as the prediction rule of a perceptron. We analyze how classical results for the perceptrons can be interpreted in this context; then, we define a fast and simple perceptron-like algorithm for this task, which can process $10^8$ links in minutes. We then compare these two techniques, first with synthetic datasets that follows our model, gaining evidence that the Naive independence assumptions are detrimental in practice. Secondly, we consider a real, large-scale citation network where each node (i.e., paper) can be described by different types of characteristics; there, our algorithm can assess how well each set of features can explain the links, and thus finding meaningful latent feature-feature interactions.

Full work available at URL: https://arxiv.org/abs/1612.00984

Recommendations

• A network model characterized by a latent attribute structure with competition
• Large-scale estimation of random graph models with local dependence
• Nonparametric link prediction in large scale dynamic networks
• Modeling networks with a growing feature-structure

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Small world graphs, complex networks (graph-theoretic aspects) (05C82)

Cites Work

• WEKA -- experiences with a Java open-source project
• Kronecker graphs: an approach to modeling networks
• Estimation and Prediction for Stochastic Blockstructures
• Prediction, Learning, and Games
• Pattern recognition and machine learning.
• Estimation and prediction for stochastic blockmodels for graphs with latent block structure
• An introduction to support vector machines and other kernel-based learning methods.
• Mixed membership stochastic blockmodels
• Exploratory latent structure analysis using both identifiable and unidentifiable models
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• 10.1162/15324430260185600
• On the Generalization Ability of On-Line Learning Algorithms
• Title not available (Why is that?)
• Graph-based knowledge representation. Computational foundations of conceptual graphs
• The dichotomy of probabilistic inference for unions of conjunctive queries
• A network model characterized by a latent attribute structure with competition
• Affiliation networks

Cited In (1)

• Latent association graph inference for binary transaction data

Uses Software

• WEKA
• KronFit
• PRMLT

This page was built for publication: Estimating latent feature-feature interactions in large feature-rich graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3389688)