Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userExposing Multi-Relational Networks to Single-Relational Network Analysis Algorithms
91
0
0.0
(
0
)
Added by
Marko A. Rodriguez
Publication date
2009
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Many, if not most network analysis algorithms have been designed specifically for single-relational networks; that is, networks in which all edges are of the same type. For example, edges may either represent friendship, kinship, or collaboration, but not all of them together. In contrast, a multi-relational network is a network with a heterogeneous set of edge labels which can represent relationships of various types in a single data structure. While multi-relational networks are more expressive in terms of the variety of relationships they can capture, there is a need for a general framework for transferring the many single-relational network analysis algorithms to the multi-relational domain. It is not sufficient to execute a single-relational network analysis algorithm on a multi-relational network by simply ignoring edge labels. This article presents an algebra for mapping multi-relational networks to single-relational networks, thereby exposing them to single-relational network analysis algorithms.
rate research
Read More
In this paper, we develop asymptotic theories for a class of latent variable models for large-scale multi-relational networks. In particular, we establish consistency results and asymptotic error bounds for the (penalized) maximum likelihood estimators when the size of the network tends to infinity. The basic technique is to develop a non-asymptotic error bound for the maximum likelihood estimators through large deviations analysis of random fields. We also show that these estimators are nearly optimal in terms of minimax risk.
A multi-relational graph maintains two or more relations over a vertex set. This article defines an algebra for traversing such graphs that is based on an $n$-ary relational algebra, a concatenative single-relational path algebra, and a tensor-based multi-relational algebra. The presented algebra provides a monoid, automata, and formal language theoretic foundation for the construction of a multi-relational graph traversal engine.
Graph Attention Network (GAT) focuses on modelling simple undirected and single relational graph data only. This limits its ability to deal with more general and complex multi-relational graphs that contain entities with directed links of different labels (e.g., knowledge graphs). Therefore, directly applying GAT on multi-relational graphs leads to sub-optimal solutions. To tackle this issue, we propose r-GAT, a relational graph attention network to learn multi-channel entity representations. Specifically, each channel corresponds to a latent semantic aspect of an entity. This enables us to aggregate neighborhood information for the current aspect using relation features. We further propose a query-aware attention mechanism for subsequent tasks to select useful aspects. Extensive experiments on link prediction and entity classification tasks show that our r-GAT can model multi-relational graphs effectively. Also, we show the interpretability of our approach by case study.
A two-state epidemic model in networks with links mimicking two kinds of relationships between connected nodes is introduced. Links of weights w1 and w0 occur with probabilities p and 1-p, respectively. The fraction of infected nodes rho(p) shows a non-monotonic behavior, with rho drops with p for small p and increases for large p. For small to moderate w1/w0 ratios, rho(p) exhibits a minimum that signifies an optimal suppression. For large w1/w0 ratios, the suppression leads to an absorbing phase consisting only of healthy nodes within a range p_L =< p =< p_R, and an active phase with mixed infected and healthy nodes for p < p_L and p>p_R. A mean field theory that ignores spatial correlation is shown to give qualitative agreement and capture all the key features. A physical picture that emphasizes the intricate interplay between infections via w0 links and within clusters formed by nodes carrying the w1 links is presented. The absorbing state at large w1/w0 ratios results when the clusters are big enough to disrupt the spread via w0 links and yet small enough to avoid an epidemic within the clusters. A theory that uses the possible local environments of a node as variables is formulated. The theory gives results in good agreement with simulation results, thereby showing the necessity of including longer spatial correlations.
Multi-relational networks are used extensively to structure knowledge. Perhaps the most popular instance, due to the widespread adoption of the Semantic Web, is the Resource Description Framework (RDF). One of the primary purposes of a knowledge network is to reason; that is, to alter the topology of the network according to an algorithm that uses the existing topological structure as its input. There exist many such reasoning algorithms. With respect to the Semantic Web, the bivalent, monotonic reasoners of the RDF Schema (RDFS) and the Web Ontology Language (OWL) are the most prevalent. However, nothing prevents other forms of reasoning from existing in the Semantic Web. This article presents a non-bivalent, non-monotonic, evidential logic and reasoner that is an algebraic ring over a multi-relational network equipped with two binary operations that can be composed to execute various forms of inference. Given its multi-relational grounding, it is possible to use the presented evidential framework as another method for structuring knowledge and reasoning in the Semantic Web. The benefits of this framework are that it works with arbitrary, partial, and contradictory knowledge while, at the same time, it supports a tractable approximate reasoning process.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
