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

DOI10.24166/IM.14.2017MaRDI QIDQ3389688zbMATH OpenOpenAlexFDO

Authors Corrado Monti, Paolo Boldi

Publication date 23 March 2022

Published in Internet Mathematics (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(1)

• Latent association graph inference for binary transaction data

Describes a project that uses

Uses Software

• PRMLT
• KronFit
• WEKA

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)