To see the other types of publications on this topic, follow the link: Node embeddings.
Journal articles on the topic 'Node embeddings'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 journal articles for your research on the topic 'Node embeddings.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.
1
BOZKURT, ILKER NADI, HAI HUANG, BRUCE MAGGS, ANDRÉA RICHA, and MAVERICK WOO. "Mutual Embeddings." Journal of Interconnection Networks 15, no. 01n02 (March 2015): 1550001. http://dx.doi.org/10.1142/s0219265915500012.
Full textAbstract:
This paper introduces a type of graph embedding called a mutual embedding. A mutual embedding between two n-node graphs [Formula: see text] and [Formula: see text] is an identification of the vertices of V1 and V2, i.e., a bijection [Formula: see text], together with an embedding of G1 into G2 and an embedding of G2 into G1 where in the embedding of G1 into G2, each node u of G1 is mapped to π(u) in G2 and in the embedding of G2 into G1 each node v of G2 is mapped to [Formula: see text] in G1. The identification of vertices in G1 and G2 constrains the two embeddings so that it is not always possible for both to exhibit small congestion and dilation, even if there are traditional one-way embeddings in both directions with small congestion and dilation. Mutual embeddings arise in the context of finding preconditioners for accelerating the convergence of iterative methods for solving systems of linear equations. We present mutual embeddings between several types of graphs such as linear arrays, cycles, trees, and meshes, prove lower bounds on mutual embeddings between several classes of graphs, and present some open problems related to optimal mutual embeddings.
2
Cheng, Pengyu, Yitong Li, Xinyuan Zhang, Liqun Chen, David Carlson, and Lawrence Carin. "Dynamic Embedding on Textual Networks via a Gaussian Process." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 05 (April 3, 2020): 7562–69. http://dx.doi.org/10.1609/aaai.v34i05.6255.
Full textAbstract:
Textual network embedding aims to learn low-dimensional representations of text-annotated nodes in a graph. Prior work in this area has typically focused on fixed graph structures; however, real-world networks are often dynamic. We address this challenge with a novel end-to-end node-embedding model, called Dynamic Embedding for Textual Networks with a Gaussian Process (DetGP). After training, DetGP can be applied efficiently to dynamic graphs without re-training or backpropagation. The learned representation of each node is a combination of textual and structural embeddings. Because the structure is allowed to be dynamic, our method uses the Gaussian process to take advantage of its non-parametric properties. To use both local and global graph structures, diffusion is used to model multiple hops between neighbors. The relative importance of global versus local structure for the embeddings is learned automatically. With the non-parametric nature of the Gaussian process, updating the embeddings for a changed graph structure requires only a forward pass through the learned model. Considering link prediction and node classification, experiments demonstrate the empirical effectiveness of our method compared to baseline approaches. We further show that DetGP can be straightforwardly and efficiently applied to dynamic textual networks.
3
Park, Chanyoung, Donghyun Kim, Jiawei Han, and Hwanjo Yu. "Unsupervised Attributed Multiplex Network Embedding." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5371–78. http://dx.doi.org/10.1609/aaai.v34i04.5985.
Full textAbstract:
Nodes in a multiplex network are connected by multiple types of relations. However, most existing network embedding methods assume that only a single type of relation exists between nodes. Even for those that consider the multiplexity of a network, they overlook node attributes, resort to node labels for training, and fail to model the global properties of a graph. We present a simple yet effective unsupervised network embedding method for attributed multiplex network called DMGI, inspired by Deep Graph Infomax (DGI) that maximizes the mutual information between local patches of a graph, and the global representation of the entire graph. We devise a systematic way to jointly integrate the node embeddings from multiple graphs by introducing 1) the consensus regularization framework that minimizes the disagreements among the relation-type specific node embeddings, and 2) the universal discriminator that discriminates true samples regardless of the relation types. We also show that the attention mechanism infers the importance of each relation type, and thus can be useful for filtering unnecessary relation types as a preprocessing step. Extensive experiments on various downstream tasks demonstrate that DMGI outperforms the state-of-the-art methods, even though DMGI is fully unsupervised.
4
Hou, Yuchen, and Lawrence B. Holder. "On Graph Mining With Deep Learning: Introducing Model R for Link Weight Prediction." Journal of Artificial Intelligence and Soft Computing Research 9, no. 1 (January 1, 2019): 21–40. http://dx.doi.org/10.2478/jaiscr-2018-0022.
Full textAbstract:
Abstract Deep learning has been successful in various domains including image recognition, speech recognition and natural language processing. However, the research on its application in graph mining is still in an early stage. Here we present Model R, a neural network model created to provide a deep learning approach to the link weight prediction problem. This model uses a node embedding technique that extracts node embeddings (knowledge of nodes) from the known links’ weights (relations between nodes) and uses this knowledge to predict the unknown links’ weights. We demonstrate the power of Model R through experiments and compare it with the stochastic block model and its derivatives. Model R shows that deep learning can be successfully applied to link weight prediction and it outperforms stochastic block model and its derivatives by up to 73% in terms of prediction accuracy. We analyze the node embeddings to confirm that closeness in embedding space correlates with stronger relationships as measured by the link weight. We anticipate this new approach will provide effective solutions to more graph mining tasks.
5
Wang, Yueyang, Ziheng Duan, Binbing Liao, Fei Wu, and Yueting Zhuang. "Heterogeneous Attributed Network Embedding with Graph Convolutional Networks." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 10061–62. http://dx.doi.org/10.1609/aaai.v33i01.330110061.
Full textAbstract:
Network embedding which assigns nodes in networks to lowdimensional representations has received increasing attention in recent years. However, most existing approaches, especially the spectral-based methods, only consider the attributes in homogeneous networks. They are weak for heterogeneous attributed networks that involve different node types as well as rich node attributes and are common in real-world scenarios. In this paper, we propose HANE, a novel network embedding method based on Graph Convolutional Networks, that leverages both the heterogeneity and the node attributes to generate high-quality embeddings. The experiments on the real-world dataset show the effectiveness of our method.
6
He, Tao, Lianli Gao, Jingkuan Song, Xin Wang, Kejie Huang, and Yuanfang Li. "SNEQ: Semi-Supervised Attributed Network Embedding with Attention-Based Quantisation." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 4091–98. http://dx.doi.org/10.1609/aaai.v34i04.5832.
Full textAbstract:
Learning accurate low-dimensional embeddings for a network is a crucial task as it facilitates many network analytics tasks. Moreover, the trained embeddings often require a significant amount of space to store, making storage and processing a challenge, especially as large-scale networks become more prevalent. In this paper, we present a novel semi-supervised network embedding and compression method, SNEQ, that is competitive with state-of-art embedding methods while being far more space- and time-efficient. SNEQ incorporates a novel quantisation method based on a self-attention layer that is trained in an end-to-end fashion, which is able to dramatically compress the size of the trained embeddings, thus reduces storage footprint and accelerates retrieval speed. Our evaluation on four real-world networks of diverse characteristics shows that SNEQ outperforms a number of state-of-the-art embedding methods in link prediction, node classification and node recommendation. Moreover, the quantised embedding shows a great advantage in terms of storage and time compared with continuous embeddings as well as hashing methods.
7
Wang, Zheng, Yuexin Wu, Yang Bao, Jing Yu, and Xiaohui Wang. "Fusing Node Embeddings and Incomplete Attributes by Complement-Based Concatenation." Wireless Communications and Mobile Computing 2021 (February 25, 2021): 1–10. http://dx.doi.org/10.1155/2021/6654349.
Full textAbstract:
Network embedding that learns representations of network nodes plays a critical role in network analysis, since it enables many downstream learning tasks. Although various network embedding methods have been proposed, they are mainly designed for a single network scenario. This paper considers a “multiple network” scenario by studying the problem of fusing the node embeddings and incomplete attributes from two different networks. To address this problem, we propose to complement the incomplete attributes, so as to conduct data fusion via concatenation. Specifically, we first propose a simple inductive method, in which attributes are defined as a parametric function of the given node embedding vectors. We then propose its transductive variant by adaptively learning an adjacency graph to approximate the original network structure. Additionally, we also provide a light version of this transductive variant. Experimental results on four datasets demonstrate the superiority of our methods.
8
Zhong, Jianan, Hongjun Qiu, and Benyun Shi. "Dynamics-Preserving Graph Embedding for Community Mining and Network Immunization." Information 11, no. 5 (May 2, 2020): 250. http://dx.doi.org/10.3390/info11050250.
Full textAbstract:
In recent years, the graph embedding approach has drawn a lot of attention in the field of network representation and analytics, the purpose of which is to automatically encode network elements into a low-dimensional vector space by preserving certain structural properties. On this basis, downstream machine learning methods can be implemented to solve static network analytic tasks, for example, node clustering based on community-preserving embeddings. However, by focusing only on structural properties, it would be difficult to characterize and manipulate various dynamics operating on the network. In the field of complex networks, epidemic spreading is one of the most typical dynamics in networks, while network immunization is one of the effective methods to suppress the epidemics. Accordingly, in this paper, we present a dynamics-preserving graph embedding method (EpiEm) to preserve the property of epidemic dynamics on networks, i.e., the infectiousness and vulnerability of network nodes. Specifically, we first generate a set of propagation sequences through simulating the Susceptible-Infectious process on a network. Then, we learn node embeddings from an influence matrix using a singular value decomposition method. Finally, we show that the node embeddings can be used to solve epidemics-related community mining and network immunization problems. The experimental results in real-world networks show that the proposed embedding method outperforms several benchmark methods with respect to both community mining and network immunization. The proposed method offers new insights into the exploration of other collective dynamics in complex networks using the graph embedding approach, such as opinion formation in social networks.
9
Celikkanat, Abdulkadir, and Fragkiskos D. Malliaros. "Exponential Family Graph Embeddings." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3357–64. http://dx.doi.org/10.1609/aaai.v34i04.5737.
Full textAbstract:
Representing networks in a low dimensional latent space is a crucial task with many interesting applications in graph learning problems, such as link prediction and node classification. A widely applied network representation learning paradigm is based on the combination of random walks for sampling context nodes and the traditional Skip-Gram model to capture center-context node relationships. In this paper, we emphasize on exponential family distributions to capture rich interaction patterns between nodes in random walk sequences. We introduce the generic exponential family graph embedding model, that generalizes random walk-based network representation learning techniques to exponential family conditional distributions. We study three particular instances of this model, analyzing their properties and showing their relationship to existing unsupervised learning models. Our experimental evaluation on real-world datasets demonstrates that the proposed techniques outperform well-known baseline methods in two downstream machine learning tasks.
10
Zhou, Sheng, Xin Wang, Jiajun Bu, Martin Ester, Pinggang Yu, Jiawei Chen, Qihao Shi, and Can Wang. "DGE: Deep Generative Network Embedding Based on Commonality and Individuality." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 6949–56. http://dx.doi.org/10.1609/aaai.v34i04.6178.
Full textAbstract:
Network embedding plays a crucial role in network analysis to provide effective representations for a variety of learning tasks. Existing attributed network embedding methods mainly focus on preserving the observed node attributes and network topology in the latent embedding space, with the assumption that nodes connected through edges will share similar attributes. However, our empirical analysis of real-world datasets shows that there exist both commonality and individuality between node attributes and network topology. On the one hand, similar nodes are expected to share similar attributes and have edges connecting them (commonality). On the other hand, each information source may maintain individual differences as well (individuality). Simultaneously capturing commonality and individuality is very challenging due to their exclusive nature and existing work fail to do so. In this paper, we propose a deep generative embedding (DGE) framework which simultaneously captures commonality and individuality between network topology and node attributes in a generative process. Stochastic gradient variational Bayesian (SGVB) optimization is employed to infer model parameters as well as the node embeddings. Extensive experiments on four real-world datasets show the superiority of our proposed DGE framework in various tasks including node classification and link prediction.
11
Shang, Chao, Yun Tang, Jing Huang, Jinbo Bi, Xiaodong He, and Bowen Zhou. "End-to-End Structure-Aware Convolutional Networks for Knowledge Base Completion." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 3060–67. http://dx.doi.org/10.1609/aaai.v33i01.33013060.
Full textAbstract:
Knowledge graph embedding has been an active research topic for knowledge base completion, with progressive improvement from the initial TransE, TransH, DistMult et al to the current state-of-the-art ConvE. ConvE uses 2D convolution over embeddings and multiple layers of nonlinear features to model knowledge graphs. The model can be efficiently trained and scalable to large knowledge graphs. However, there is no structure enforcement in the embedding space of ConvE. The recent graph convolutional network (GCN) provides another way of learning graph node embedding by successfully utilizing graph connectivity structure. In this work, we propose a novel end-to-end StructureAware Convolutional Network (SACN) that takes the benefit of GCN and ConvE together. SACN consists of an encoder of a weighted graph convolutional network (WGCN), and a decoder of a convolutional network called Conv-TransE. WGCN utilizes knowledge graph node structure, node attributes and edge relation types. It has learnable weights that adapt the amount of information from neighbors used in local aggregation, leading to more accurate embeddings of graph nodes. Node attributes in the graph are represented as additional nodes in the WGCN. The decoder Conv-TransE enables the state-of-the-art ConvE to be translational between entities and relations while keeps the same link prediction performance as ConvE. We demonstrate the effectiveness of the proposed SACN on standard FB15k-237 and WN18RR datasets, and it gives about 10% relative improvement over the state-of-theart ConvE in terms of HITS@1, HITS@3 and HITS@10.
12
Makarov, Ilya, Mikhail Makarov, and Dmitrii Kiselev. "Fusion of text and graph information for machine learning problems on networks." PeerJ Computer Science 7 (May 11, 2021): e526. http://dx.doi.org/10.7717/peerj-cs.526.
Full textAbstract:
Today, increased attention is drawn towards network representation learning, a technique that maps nodes of a network into vectors of a low-dimensional embedding space. A network embedding constructed this way aims to preserve nodes similarity and other specific network properties. Embedding vectors can later be used for downstream machine learning problems, such as node classification, link prediction and network visualization. Naturally, some networks have text information associated with them. For instance, in a citation network, each node is a scientific paper associated with its abstract or title; in a social network, all users may be viewed as nodes of a network and posts of each user as textual attributes. In this work, we explore how combining existing methods of text and network embeddings can increase accuracy for downstream tasks and propose modifications to popular architectures to better capture textual information in network embedding and fusion frameworks.
13
Zhan, Junjian, Feng Li, Yang Wang, Daoyu Lin, and Guangluan Xu. "Structural Adversarial Variational Auto-Encoder for Attributed Network Embedding." Applied Sciences 11, no. 5 (March 7, 2021): 2371. http://dx.doi.org/10.3390/app11052371.
Full textAbstract:
As most networks come with some content in each node, attributed network embedding has aroused much research interest. Most existing attributed network embedding methods aim at learning a fixed representation for each node encoding its local proximity. However, those methods usually neglect the global information between nodes distant from each other and distribution of the latent codes. We propose Structural Adversarial Variational Graph Auto-Encoder (SAVGAE), a novel framework which encodes the network structure and node content into low-dimensional embeddings. On one hand, our model captures the local proximity and proximities at any distance of a network by exploiting a high-order proximity indicator named Rooted Pagerank. On the other hand, our method learns the data distribution of each node representation while circumvents the side effect its sampling process causes on learning a robust embedding through adversarial training. On benchmark datasets, we demonstrate that our method performs competitively compared with state-of-the-art models.
14
Bandyopadhyay, Sambaran, N. Lokesh, and M. N. Murty. "Outlier Aware Network Embedding for Attributed Networks." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 12–19. http://dx.doi.org/10.1609/aaai.v33i01.330112.
Full textAbstract:
Attributed network embedding has received much interest from the research community as most of the networks come with some content in each node, which is also known as node attributes. Existing attributed network approaches work well when the network is consistent in structure and attributes, and nodes behave as expected. But real world networks often have anomalous nodes. Typically these outliers, being relatively unexplainable, affect the embeddings of other nodes in the network. Thus all the downstream network mining tasks fail miserably in the presence of such outliers. Hence an integrated approach to detect anomalies and reduce their overall effect on the network embedding is required.Towards this end, we propose an unsupervised outlier aware network embedding algorithm (ONE) for attributed networks, which minimizes the effect of the outlier nodes, and hence generates robust network embeddings. We align and jointly optimize the loss functions coming from structure and attributes of the network. To the best of our knowledge, this is the first generic network embedding approach which incorporates the effect of outliers for an attributed network without any supervision. We experimented on publicly available real networks and manually planted different types of outliers to check the performance of the proposed algorithm. Results demonstrate the superiority of our approach to detect the network outliers compared to the state-of-the-art approaches. We also consider different downstream machine learning applications on networks to show the efficiency of ONE as a generic network embedding technique. The source code is made available at https://github.com/sambaranban/ONE.
15
Fionda, Valeria, and Giuseppe Pirrò. "Learning Triple Embeddings from Knowledge Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3874–81. http://dx.doi.org/10.1609/aaai.v34i04.5800.
Full textAbstract:
Graph embedding techniques allow to learn high-quality feature vectors from graph structures and are useful in a variety of tasks, from node classification to clustering. Existing approaches have only focused on learning feature vectors for the nodes and predicates in a knowledge graph. To the best of our knowledge, none of them has tackled the problem of directly learning triple embeddings. The approaches that are closer to this task have focused on homogeneous graphs involving only one type of edge and obtain edge embeddings by applying some operation (e.g., average) on the embeddings of the endpoint nodes. The goal of this paper is to introduce Triple2Vec, a new technique to directly embed knowledge graph triples. We leverage the idea of line graph of a graph and extend it to the context of knowledge graphs. We introduce an edge weighting mechanism for the line graph based on semantic proximity. Embeddings are finally generated by adopting the SkipGram model, where sentences are replaced with graph walks. We evaluate our approach on different real-world knowledge graphs and compared it with related work. We also show an application of triple embeddings in the context of user-item recommendations.
16
Makarov, Ilya, Dmitrii Kiselev, Nikita Nikitinsky, and Lovro Subelj. "Survey on graph embeddings and their applications to machine learning problems on graphs." PeerJ Computer Science 7 (February 4, 2021): e357. http://dx.doi.org/10.7717/peerj-cs.357.
Full textAbstract:
Dealing with relational data always required significant computational resources, domain expertise and task-dependent feature engineering to incorporate structural information into a predictive model. Nowadays, a family of automated graph feature engineering techniques has been proposed in different streams of literature. So-called graph embeddings provide a powerful tool to construct vectorized feature spaces for graphs and their components, such as nodes, edges and subgraphs under preserving inner graph properties. Using the constructed feature spaces, many machine learning problems on graphs can be solved via standard frameworks suitable for vectorized feature representation. Our survey aims to describe the core concepts of graph embeddings and provide several taxonomies for their description. First, we start with the methodological approach and extract three types of graph embedding models based on matrix factorization, random-walks and deep learning approaches. Next, we describe how different types of networks impact the ability of models to incorporate structural and attributed data into a unified embedding. Going further, we perform a thorough evaluation of graph embedding applications to machine learning problems on graphs, among which are node classification, link prediction, clustering, visualization, compression, and a family of the whole graph embedding algorithms suitable for graph classification, similarity and alignment problems. Finally, we overview the existing applications of graph embeddings to computer science domains, formulate open problems and provide experiment results, explaining how different networks properties result in graph embeddings quality in the four classic machine learning problems on graphs, such as node classification, link prediction, clustering and graph visualization. As a result, our survey covers a new rapidly growing field of network feature engineering, presents an in-depth analysis of models based on network types, and overviews a wide range of applications to machine learning problems on graphs.
17
Zhuo, Wei, Qianyi Zhan, Yuan Liu, Zhenping Xie, and Jing Lu. "Context Attention Heterogeneous Network Embedding." Computational Intelligence and Neuroscience 2019 (August 21, 2019): 1–15. http://dx.doi.org/10.1155/2019/8106073.
Full textAbstract:
Network embedding (NE), which maps nodes into a low-dimensional latent Euclidean space to represent effective features of each node in the network, has obtained considerable attention in recent years. Many popular NE methods, such as DeepWalk, Node2vec, and LINE, are capable of handling homogeneous networks. However, nodes are always fully accompanied by heterogeneous information (e.g., text descriptions, node properties, and hashtags) in the real-world network, which remains a great challenge to jointly project the topological structure and different types of information into the fixed-dimensional embedding space due to heterogeneity. Besides, in the unweighted network, how to quantify the strength of edges (tightness of connections between nodes) accurately is also a difficulty faced by existing methods. To bridge the gap, in this paper, we propose CAHNE (context attention heterogeneous network embedding), a novel network embedding method, to accurately determine the learning result. Specifically, we propose the concept of node importance to measure the strength of edges, which can better preserve the context relations of a node in unweighted networks. Moreover, text information is a widely ubiquitous feature in real-world networks, e.g., online social networks and citation networks. On account of the sophisticated interactions between the network structure and text features of nodes, CAHNE learns context embeddings for nodes by introducing the context node sequence, and the attention mechanism is also integrated into our model to better reflect the impact of context nodes on the current node. To corroborate the efficacy of CAHNE, we apply our method and various baseline methods on several real-world datasets. The experimental results show that CAHNE achieves higher quality compared to a number of state-of-the-art network embedding methods on the tasks of network reconstruction, link prediction, node classification, and visualization.
18
Tsitsulin, Anton, Marina Munkhoeva, Davide Mottin, Panagiotis Karras, Ivan Oseledets, and Emmanuel Müller. "FREDE." Proceedings of the VLDB Endowment 14, no. 6 (February 2021): 1102–10. http://dx.doi.org/10.14778/3447689.3447713.
Full textAbstract:
Low-dimensional representations, or embeddings , of a graph's nodes facilitate several practical data science and data engineering tasks. As such embeddings rely, explicitly or implicitly, on a similarity measure among nodes, they require the computation of a quadratic similarity matrix, inducing a tradeoff between space complexity and embedding quality. To date, no graph embedding work combines (i) linear space complexity, (ii) a nonlinear transform as its basis, and (iii) nontrivial quality guarantees. In this paper we introduce FREDE ( FREquent Directions Embedding ), a graph embedding based on matrix sketching that combines those three desiderata. Starting out from the observation that embedding methods aim to preserve the covariance among the rows of a similarity matrix, FREDE iteratively improves on quality while individually processing rows of a nonlinearly transformed PPR similarity matrix derived from a state-of-the-art graph embedding method and provides, at any iteration , column-covariance approximation guarantees in due course almost indistinguishable from those of the optimal approximation by SVD. Our experimental evaluation on variably sized networks shows that FREDE performs almost as well as SVD and competitively against state-of-the-art embedding methods in diverse data science tasks, even when it is based on as little as 10% of node similarities.
19
Sarkar, Arindam, Nikhil Mehta, and Piyush Rai. "Graph Representation Learning via Ladder Gamma Variational Autoencoders." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5604–11. http://dx.doi.org/10.1609/aaai.v34i04.6013.
Full textAbstract:
We present a probabilistic framework for community discovery and link prediction for graph-structured data, based on a novel, gamma ladder variational autoencoder (VAE) architecture. We model each node in the graph via a deep hierarchy of gamma-distributed embeddings, and define each link probability via a nonlinear function of the bottom-most layer's embeddings of its associated nodes. In addition to leveraging the representational power of multiple layers of stochastic variables via the ladder VAE architecture, our framework offers the following benefits: (1) Unlike existing ladder VAE architectures based on real-valued latent variables, the gamma-distributed latent variables naturally result in non-negativity and sparsity of the learned embeddings, and facilitate their direct interpretation as membership of nodes into (possibly multiple) communities/topics; (2) A novel recognition model for our gamma ladder VAE architecture allows fast inference of node embeddings; and (3) The framework also extends naturally to incorporate node side information (features and/or labels). Our framework is also fairly modular and can leverage a wide variety of graph neural networks as the VAE encoder. We report both quantitative and qualitative results on several benchmark datasets and compare our model with several state-of-the-art methods.
20
Hu, Fang, Liuhuan Li, Xiaoyu Huang, Xingyu Yan, and Panpan Huang. "Symptom Distribution Regularity of Insomnia: Network and Spectral Clustering Analysis." JMIR Medical Informatics 8, no. 4 (April 16, 2020): e16749. http://dx.doi.org/10.2196/16749.
Full textAbstract:
Background Recent research in machine-learning techniques has led to significant progress in various research fields. In particular, knowledge discovery using this method has become a hot topic in traditional Chinese medicine. As the key clinical manifestations of patients, symptoms play a significant role in clinical diagnosis and treatment, which evidently have their underlying traditional Chinese medicine mechanisms. Objective We aimed to explore the core symptoms and potential regularity of symptoms for diagnosing insomnia to reveal the key symptoms, hidden relationships underlying the symptoms, and their corresponding syndromes. Methods An insomnia dataset with 807 samples was extracted from real-world electronic medical records. After cleaning and selecting the theme data referring to the syndromes and symptoms, the symptom network analysis model was constructed using complex network theory. We used four evaluation metrics of node centrality to discover the core symptom nodes from multiple aspects. To explore the hidden relationships among symptoms, we trained each symptom node in the network to obtain the symptom embedding representation using the Skip-Gram model and node embedding theory. After acquiring the symptom vocabulary in a digital vector format, we calculated the similarities between any two symptom embeddings, and clustered these symptom embeddings into five communities using the spectral clustering algorithm. Results The top five core symptoms of insomnia diagnosis, including difficulty falling asleep, easy to wake up at night, dysphoria and irascibility, forgetful, and spiritlessness and weakness, were identified using evaluation metrics of node centrality. The symptom embeddings with hidden relationships were constructed, which can be considered as the basic dataset for future insomnia research. The symptom network was divided into five communities, and these symptoms were accurately categorized into their corresponding syndromes. Conclusions These results highlight that network and clustering analyses can objectively and effectively find the key symptoms and relationships among symptoms. Identification of the symptom distribution and symptom clusters of insomnia further provide valuable guidance for clinical diagnosis and treatment.
21
Das, Sajal K., Sabine Öhring, and Amit K. Banerjee. "Embeddings into Hyper Petersen Networks: Yet Another Hypercube-Like Interconnection Topology." VLSI Design 2, no. 4 (January 1, 1995): 335–51. http://dx.doi.org/10.1155/1995/95759.
Full textAbstract:
A new hypercube-like topology, called the hyper Petersen (HP) network, is proposed and analyzed, which is constructed from the well-known cartesian product of the binary hypercube and the Petersen graph of ten nodes.This topology is an attractive candidate for multiprocessor interconnection having such desirable properties as regularity, high symmetry and connectivity, and logarithmic diameter. For example, an n-dimensional hyper Petersen network, HPn, with N=1.25 * 2n nodes is a regular graph of degree and node-connectivity n and diameter n–1 , whereas an (n–1)-dimensional binary hypercube, Qn−1 , with the same diameter covers only 2n−1 nodes, each of degree (n–1). Thus the HP topology accommodates 2.5 times extra nodes than Qn−1 at the cost of increasing the node-degree by one. With the same degree and connectivity of n, the diameter of the HPn network is one less than that of Qn, yet having 1.25 times larger number of nodes.Efficient routing and broadcasting schemes are presented, and node-disjoint paths in HPn, are computed even under faulty conditions. The versatility of the hyper Petersen networks is emphasized by embedding rings, meshes, hypercubes and several tree-related topologies into it. Contrary to the hypercubes, rings of odd lengths, and a complete binary tree of height n–1 permit subgraph embeddings in HPn.
22
Li, Yu, Yuan Tian, Jiawei Zhang, and Yi Chang. "Learning Signed Network Embedding via Graph Attention." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 4772–79. http://dx.doi.org/10.1609/aaai.v34i04.5911.
Full textAbstract:
Learning the low-dimensional representations of graphs (i.e., network embedding) plays a critical role in network analysis and facilitates many downstream tasks. Recently graph convolutional networks (GCNs) have revolutionized the field of network embedding, and led to state-of-the-art performance in network analysis tasks such as link prediction and node classification. Nevertheless, most of the existing GCN-based network embedding methods are proposed for unsigned networks. However, in the real world, some of the networks are signed, where the links are annotated with different polarities, e.g., positive vs. negative. Since negative links may have different properties from the positive ones and can also significantly affect the quality of network embedding. Thus in this paper, we propose a novel network embedding framework SNEA to learn Signed Network Embedding via graph Attention. In particular, we propose a masked self-attentional layer, which leverages self-attention mechanism to estimate the importance coefficient for pair of nodes connected by different type of links during the embedding aggregation process. Then SNEA utilizes the masked self-attentional layers to aggregate more important information from neighboring nodes to generate the node embeddings based on balance theory. Experimental results demonstrate the effectiveness of the proposed framework through signed link prediction task on several real-world signed network datasets.
23
LI, KEQIN. "A METHOD FOR EVALUATING THE EXPECTED LOAD OF DYNAMIC TREE EMBEDDINGS IN HYPERCUBES." International Journal of Foundations of Computer Science 11, no. 02 (June 2000): 207–30. http://dx.doi.org/10.1142/s0129054100000132.
Full textAbstract:
A key issue in performing tree structured parallel computations is to distribute process components of a parallel program over processors in a parallel computer at run time such that both the maximum load and dilation are minimized. The main contribution of this paper is the application of recurrence relations in studying the performance of a dynamic tree embedding algorithm in hypercubes. We develop recurrence relations that characterize the expected load in randomized tree embeddings where, a tree grows by letting its nodes to take random walks of short distance. By using these recurrence relations, we are able to calculate the expected load on each processor. Therefore, for constant dilation embeddings, we are able to evaluate expected loads numerically and analytically. The applicability of recurrence relations is due to the recursive structure of trees and the fact that embeddings of the subtrees of a process node are independent of each other. Our methodology does not depend on the hypercube topology. Hence, it can be applied to studying dynamic tree growing in other networks.
24
Li, Cheng-Te, and Zi-Yun Zeng. "Learning Effective Feature Representation against User Privacy Protection on Social Networks." Applied Sciences 10, no. 14 (July 14, 2020): 4835. http://dx.doi.org/10.3390/app10144835.
Full textAbstract:
Users pay increasing attention to their data privacy in online social networks, resulting in hiding personal information, such as profile attributes and social connections. While network representation learning (NRL) is widely effective in social network analysis (SNA) tasks, it is essential to learn effective node embeddings from privacy-protected sparse and incomplete network data. In this work, we present a novel NRL model to generate node embeddings that can afford data incompleteness coming from user privacy protection. We propose a structure-attribute enhanced matrix (SAEM) to alleviate data sparsity and develop a community-cluster informed NRL method, c2n2v, to further improve the quality of embedding learning. Experiments conducted across three datasets, three simulations of user privacy protection, and three downstream SNA tasks exhibit the promising performance of our NRL model SAEM+c2n2v.
25
Yu, Liqun, Hongqi Wang, and Haoran Mo. "Estimating Network Flowing over Edges by Recursive Network Embedding." Shock and Vibration 2020 (November 26, 2020): 1–7. http://dx.doi.org/10.1155/2020/8893381.
Full textAbstract:
In this paper, we propose a novel semisupervised learning framework to learn the flows of edges over a graph. Given the flow values of the labeled edges, the task of this paper is to learn the unknown flow values of the remaining unlabeled edges. To this end, we introduce a value amount hold by each node and impose that the amount of values flowing from the conjunctive edges of each node to be consistent with the node’s own value. We propose to embed the nodes to a continuous vector space so that the embedding vector of each node can be reconstructed from its neighbors by a recursive neural network model, linear normalized long short-term memory. Moreover, we argue that the value of each node is also embedded in the embedding vectors of its neighbors, thus propose to approximate the node value from the output of the neighborhood recursive network. We build a unified learning framework by formulating a minimization problem. To construct the learning problem, we build three subproblems of minimization: (1) the embedding error of each node from the recursive network, (2) the loss of the construction for the amount of value of each node, and (3) the difference between the value amount of each node and the estimated value from the edge flows. We develop an iterative algorithm to learn the node embeddings, edge flows, and node values jointly. We perform experiments based on the datasets of some network data, including the transportation network and innovation. The experimental results indicate that our algorithm is more effective than the state-of-the-arts.
26
Li, Cheng-Te, and Hong-Yu Lin. "Structural Hierarchy-Enhanced Network Representation Learning." Applied Sciences 10, no. 20 (October 16, 2020): 7214. http://dx.doi.org/10.3390/app10207214.
Full textAbstract:
Network representation learning (NRL) is crucial in generating effective node features for downstream tasks, such as node classification (NC) and link prediction (LP). However, existing NRL methods neither properly identify neighbor nodes that should be pushed together and away in the embedding space, nor model coarse-grained community knowledge hidden behind the network topology. In this paper, we propose a novel NRL framework, Structural Hierarchy Enhancement (SHE), to deal with such two issues. The main idea is to construct a structural hierarchy from the network based on community detection, and to utilize such a hierarchy to perform level-wise NRL. In addition, lower-level node embeddings are passed to higher-level ones so that community knowledge can be aware of in NRL. Experiments conducted on benchmark network datasets show that SHE can significantly boost the performance of NRL in both tasks of NC and LP, compared to other hierarchical NRL methods.
27
Lu, Ruili, Pengfei Jiao, Yinghui Wang, Huaming Wu, and Xue Chen. "Layer Information Similarity Concerned Network Embedding." Complexity 2021 (August 26, 2021): 1–10. http://dx.doi.org/10.1155/2021/2260488.
Full textAbstract:
Great achievements have been made in network embedding based on single-layer networks. However, there are a variety of scenarios and systems that can be presented as multiplex networks, which can reveal more interesting patterns hidden in the data compared to single-layer networks. In the field of network embedding, in order to project the multiplex network into the latent space, it is necessary to consider richer structural information among network layers. However, current methods for multiplex network embedding mostly focus on the similarity of nodes in each layer of the network, while ignoring the similarity between different layers. In this paper, for multiplex network embedding, we propose a Layer Information Similarity Concerned Network Embedding (LISCNE) model considering the similarities between layers. Firstly, we introduce the common vector for each node shared by all layers and layer vectors for each layer where common vectors obtain the overall structure of the multiplex network and layer vectors learn semantics for each layer. We get the node embeddings in each layer by concatenating the common vectors and layer vectors with the consideration that the node embedding is related not only to the surrounding neighbors but also to the overall semantics. Furthermore, we define an index to formalize the similarity between different layers and the cross-network association. Constrained by layer similarity, the layer vectors with greater similarity are closer to each other and the aligned node embedding in these layers is also closer. To evaluate our proposed model, we conduct node classification and link prediction tasks to verify the effectiveness of our model, and the results show that LISCNE can achieve better or comparable performance compared to existing baseline methods.
28
Bai, Jie, Linjing Li, and Daniel Zeng. "HiWalk: Learning node embeddings from heterogeneous networks." Information Systems 81 (March 2019): 82–91. http://dx.doi.org/10.1016/j.is.2018.11.008.
Full text
29
Razzaq, Adil, Markus Hidell, and Peter Sjödin. "Virtual Network Embedding: A Hybrid Vertex Mapping Solution for Dynamic Resource Allocation." Journal of Electrical and Computer Engineering 2012 (2012): 1–17. http://dx.doi.org/10.1155/2012/358647.
Full textAbstract:
Virtual network embedding (VNE) is a key area in network virtualization, and the overall purpose of VNE is to map virtual networks onto an underlying physical network referred to as a substrate. Typically, the virtual networks have certain demands, such as resource requirements, that need to be satisfied by the mapping process. A virtual network (VN) can be described in terms of vertices (nodes) and edges (links) with certain resource requirements, and, to embed a VN, substrate resources are assigned to these vertices and edges. Substrate networks have finite resources and utilizing them efficiently is an important objective for a VNE method. This paper analyzes two existing vertex mapping approaches—one which only considers if enough node resources are available for the current VN mapping and one which considers to what degree a node already is utilized by existing VN embeddings before doing the vertex mapping. The paper also proposes a new vertex mapping approach which minimizes complete exhaustion of substrate nodes while still providing good overall resource utilization. Experimental results are presented to show under what circumstances the proposed vertex mapping approach can provide superior VN embedding properties compared to the other approaches.
30
Song, Wenzhuo, Shengsheng Wang, Bo Yang, You Lu, Xuehua Zhao, and Xueyan Liu. "Learning node and edge embeddings for signed networks." Neurocomputing 319 (November 2018): 42–54. http://dx.doi.org/10.1016/j.neucom.2018.08.072.
Full text
31
Ribeiro, Leonardo F. R., Yue Zhang, Claire Gardent, and Iryna Gurevych. "Modeling Global and Local Node Contexts for Text Generation from Knowledge Graphs." Transactions of the Association for Computational Linguistics 8 (September 2020): 589–604. http://dx.doi.org/10.1162/tacl_a_00332.
Full textAbstract:
Recent graph-to-text models generate text from graph-based data using either global or local aggregation to learn node representations. Global node encoding allows explicit communication between two distant nodes, thereby neglecting graph topology as all nodes are directly connected. In contrast, local node encoding considers the relations between neighbor nodes capturing the graph structure, but it can fail to capture long-range relations. In this work, we gather both encoding strategies, proposing novel neural models that encode an input graph combining both global and local node contexts, in order to learn better contextualized node embeddings. In our experiments, we demonstrate that our approaches lead to significant improvements on two graph-to-text datasets achieving BLEU scores of 18.01 on the AGENDA dataset, and 63.69 on the WebNLG dataset for seen categories, outperforming state-of-the-art models by 3.7 and 3.1 points, respectively. 1
32
Pareja, Aldo, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao Schardl, and Charles Leiserson. "EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 5363–70. http://dx.doi.org/10.1609/aaai.v34i04.5984.
Full textAbstract:
Graph representation learning resurges as a trending research subject owing to the widespread use of deep learning for Euclidean data, which inspire various creative designs of neural networks in the non-Euclidean domain, particularly graphs. With the success of these graph neural networks (GNN) in the static setting, we approach further practical scenarios where the graph dynamically evolves. Existing approaches typically resort to node embeddings and use a recurrent neural network (RNN, broadly speaking) to regulate the embeddings and learn the temporal dynamics. These methods require the knowledge of a node in the full time span (including both training and testing) and are less applicable to the frequent change of the node set. In some extreme scenarios, the node sets at different time steps may completely differ. To resolve this challenge, we propose EvolveGCN, which adapts the graph convolutional network (GCN) model along the temporal dimension without resorting to node embeddings. The proposed approach captures the dynamism of the graph sequence through using an RNN to evolve the GCN parameters. Two architectures are considered for the parameter evolution. We evaluate the proposed approach on tasks including link prediction, edge classification, and node classification. The experimental results indicate a generally higher performance of EvolveGCN compared with related approaches. The code is available at https://github.com/IBM/EvolveGCN.
33
Baumslag, Marc, and Bojana Obrenić. "Index-Shuffle Graphs." International Journal of Foundations of Computer Science 08, no. 03 (September 1997): 289–304. http://dx.doi.org/10.1142/s0129054197000197.
Full textAbstract:
Index-shuffle graphs are introduced as candidate interconnection networks for parallel computers. The comparative advantages of index-shuffle graphs over the standard bounded-degree "approximations" of the hypercube, namely butterfly-like and shuffle-like graphs, are demonstrated in the theoretical framework of graph embedding and network emulations. An N-node index-shuffle graph emulates: • an N-node shuffle-exchange graph with no slowdown, which the currently best emulations of shuffle-like graphs by hypercubes and butterflies incur a slowdown of Ω( log N). • its like-sized butterfly graph with a slowdown O( log log log N), while the currently best emulations of butterfly-like graphs by shuffle-like graphs incur a slowdown of Ω( log log N). • an N-node hypercube that executes an on-line leveled algorithm with a slowdown O( log log N), while the slowdown of currently best such emulations of the hypercube by its bounded-degree shuffle-like and butterfly-like derivatives remains Ω( log N). Our emulation is based on an embedding of an N-node hypercube into an N-node index-shuffle graph with dilation O( log log N), while the currently best embeddings of the hypercube into its bounded-degree shuffle-like and butterfly-like derivatives incur a dilation of Ω( log N).
34
Zhiyuli, Aakas, Xun Liang, Yanfang Chen, and Xiaoyong Du. "Modeling Large-Scale Dynamic Social Networks via Node Embeddings." IEEE Transactions on Knowledge and Data Engineering 31, no. 10 (October 1, 2019): 1994–2007. http://dx.doi.org/10.1109/tkde.2018.2872602.
Full text
35
Xu, Jin, Yubo Tao, Yuyu Yan, and Hai Lin. "Exploring Evolution of Dynamic Networks via Diachronic Node Embeddings." IEEE Transactions on Visualization and Computer Graphics 26, no. 7 (July 1, 2020): 2387–402. http://dx.doi.org/10.1109/tvcg.2018.2887230.
Full text
36
KAUFFMAN, LOUIS H., and RAMA MISHRA. "NODAL PARITY INVARIANTS OF KNOTTED RIGID VERTEX GRAPHS." Journal of Knot Theory and Its Ramifications 22, no. 04 (April 2013): 1340002. http://dx.doi.org/10.1142/s0218216513400026.
Full text
37
Zhou, Hui, Zhongying Zhao, Chao Li, Yongquan Liang, and Qingtian Zeng. "Rank2vec: Learning node embeddings with local structure and global ranking." Expert Systems with Applications 136 (December 2019): 276–87. http://dx.doi.org/10.1016/j.eswa.2019.06.045.
Full text
38
Peng, Yun, Byron Choi, and Jianliang Xu. "Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art." Data Science and Engineering 6, no. 2 (April 28, 2021): 119–41. http://dx.doi.org/10.1007/s41019-021-00155-3.
Full textAbstract:
AbstractGraphs have been widely used to represent complex data in many applications, such as e-commerce, social networks, and bioinformatics. Efficient and effective analysis of graph data is important for graph-based applications. However, most graph analysis tasks are combinatorial optimization (CO) problems, which are NP-hard. Recent studies have focused a lot on the potential of using machine learning (ML) to solve graph-based CO problems. Most recent methods follow the two-stage framework. The first stage is graph representation learning, which embeds the graphs into low-dimension vectors. The second stage uses machine learning to solve the CO problems using the embeddings of the graphs learned in the first stage. The works for the first stage can be classified into two categories, graph embedding methods and end-to-end learning methods. For graph embedding methods, the learning of the the embeddings of the graphs has its own objective, which may not rely on the CO problems to be solved. The CO problems are solved by independent downstream tasks. For end-to-end learning methods, the learning of the embeddings of the graphs does not have its own objective and is an intermediate step of the learning procedure of solving the CO problems. The works for the second stage can also be classified into two categories, non-autoregressive methods and autoregressive methods. Non-autoregressive methods predict a solution for a CO problem in one shot. A non-autoregressive method predicts a matrix that denotes the probability of each node/edge being a part of a solution of the CO problem. The solution can be computed from the matrix using search heuristics such as beam search. Autoregressive methods iteratively extend a partial solution step by step. At each step, an autoregressive method predicts a node/edge conditioned to current partial solution, which is used to its extension. In this survey, we provide a thorough overview of recent studies of the graph learning-based CO methods. The survey ends with several remarks on future research directions.
39
Škrlj, Blaž, Jan Kralj, and Nada Lavrač. "Embedding-based Silhouette community detection." Machine Learning 109, no. 11 (July 27, 2020): 2161–93. http://dx.doi.org/10.1007/s10994-020-05882-8.
Full textAbstract:
AbstractMining complex data in the form of networks is of increasing interest in many scientific disciplines. Network communities correspond to densely connected subnetworks, and often represent key functional parts of real-world systems. This paper proposes the embedding-based Silhouette community detection (SCD), an approach for detecting communities, based on clustering of network node embeddings, i.e. real valued representations of nodes derived from their neighborhoods. We investigate the performance of the proposed SCD approach on 234 synthetic networks, as well as on a real-life social network. Even though SCD is not based on any form of modularity optimization, it performs comparably or better than state-of-the-art community detection algorithms, such as the InfoMap and Louvain. Further, we demonstrate that SCD’s outputs can be used along with domain ontologies in semantic subgroup discovery, yielding human-understandable explanations of communities detected in a real-life protein interaction network. Being embedding-based, SCD is widely applicable and can be tested out-of-the-box as part of many existing network learning and exploration pipelines.
40
Zhang, Yiding, Xiao Wang, Nian Liu, and Chuan Shi. "Embedding Heterogeneous Information Network in Hyperbolic Spaces." ACM Transactions on Knowledge Discovery from Data 16, no. 2 (April 30, 2022): 1–23. http://dx.doi.org/10.1145/3468674.
Full textAbstract:
Heterogeneous information network (HIN) embedding, aiming to project HIN into a low-dimensional space, has attracted considerable research attention. Most of the existing HIN embedding methods focus on preserving the inherent network structure and semantic correlations in Euclidean spaces. However, one fundamental problem is whether the Euclidean spaces are the intrinsic spaces of HIN? Recent researches find the complex network with hyperbolic geometry can naturally reflect some properties, e.g., hierarchical and power-law structure. In this article, we make an effort toward embedding HIN in hyperbolic spaces. We analyze the structures of three HINs and discover some properties, e.g., the power-law distribution, also exist in HINs. Therefore, we propose a novel HIN embedding model HHNE. Specifically, to capture the structure and semantic relations between nodes, HHNE employs the meta-path guided random walk to sample the sequences for each node. Then HHNE exploits the hyperbolic distance as the proximity measurement. We also derive an effective optimization strategy to update the hyperbolic embeddings iteratively. Since HHNE optimizes different relations in a single space, we further propose the extended model HHNE++. HHNE++ models different relations in different spaces, which enables it to learn complex interactions in HINs. The optimization strategy of HHNE++ is also derived to update the parameters of HHNE++ in a principle manner. The experimental results demonstrate the effectiveness of our proposed models.
41
Wang, Xiao, Yiding Zhang, and Chuan Shi. "Hyperbolic Heterogeneous Information Network Embedding." Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 5337–44. http://dx.doi.org/10.1609/aaai.v33i01.33015337.
Full textAbstract:
Heterogeneous information network (HIN) embedding, aiming to project HIN into a low-dimensional space, has attracted considerable research attention. Most of the exiting HIN embedding methods focus on preserving the inherent network structure and semantic correlations in Euclidean spaces. However, one fundamental problem is that whether the Euclidean spaces are the appropriate or intrinsic isometric spaces of HIN? Recent researches argue that the complex network may have the hyperbolic geometry underneath, because the underlying hyperbolic geometry can naturally reflect some properties of complex network, e.g., hierarchical and power-law structure. In this paper, we make the first effort toward HIN embedding in hyperbolic spaces. We analyze the structures of two real-world HINs and discover some properties, e.g., the power-law distribution, also exist in HIN. Therefore, we propose a novel hyperbolic heterogeneous information network embedding model. Specifically, to capture the structure and semantic relations between nodes, we employ the meta-path guided random walk to sample the sequences for each node. Then we exploit the distance in hyperbolic spaces as the proximity measurement. The hyperbolic distance is able to meet the triangle inequality and well preserve the transitivity in HIN. Our model enables the nodes and their neighborhoods have small hyperbolic distances. We further derive the effective optimization strategy to update the hyperbolic embeddings iteratively. The experimental results, in comparison with the state-of-the-art, demonstrate that our proposed model not only has superior performance on network reconstruction and link prediction tasks but also shows its ability of capture hierarchy structure in HIN via visualization.
42
Shen, Feichen, Suyuan Peng, Yadan Fan, Andrew Wen, Sijia Liu, Yanshan Wang, Liwei Wang, and Hongfang Liu. "HPO2Vec+: Leveraging heterogeneous knowledge resources to enrich node embeddings for the Human Phenotype Ontology." Journal of Biomedical Informatics 96 (August 2019): 103246. http://dx.doi.org/10.1016/j.jbi.2019.103246.
Full text
43
Patra, Sabyasachi, and Anjali Mohapatra. "Motif discovery in biological network using expansion tree." Journal of Bioinformatics and Computational Biology 16, no. 06 (December 2018): 1850024. http://dx.doi.org/10.1142/s0219720018500245.
Full textAbstract:
Networks are powerful representation of topological features in biological systems like protein interaction and gene regulation. In order to understand the design principles of such complex networks, the concept of network motifs emerged. Network motifs are recurrent patterns with statistical significance that can be seen as basic building blocks of complex networks. Identification of network motifs leads to many important applications, such as understanding the modularity and the large-scale structure of biological networks, classification of networks into super-families, protein function annotation, etc. However, identification of network motifs is challenging as it involves graph isomorphism which is computationally hard. Though this problem has been studied extensively in the literature using different computational approaches, we are far from satisfactory results. Motivated by the challenges involved in this field, an efficient and scalable network Motif Discovery algorithm based on Expansion Tree (MODET) is proposed. Pattern growth approach is used in this proposed motif-centric algorithm. Each node of the expansion tree represents a non-isomorphic pattern. The embeddings corresponding to a child node of the expansion tree are obtained from the embeddings of the parent node through vertex addition and edge addition. Further, the proposed algorithm does not involve any graph isomorphism check and the time complexities of these processes are [Formula: see text] and [Formula: see text], respectively. The proposed algorithm has been tested on Protein–Protein Interaction (PPI) network obtained from the MINT database. The computational efficiency of the proposed algorithm outperforms most of the existing network motif discovery algorithms.
44
Long, Yahui, Min Wu, Yong Liu, Chee Keong Kwoh, Jiawei Luo, and Xiaoli Li. "Ensembling graph attention networks for human microbe–drug association prediction." Bioinformatics 36, Supplement_2 (December 2020): i779—i786. http://dx.doi.org/10.1093/bioinformatics/btaa891.
Full textAbstract:
Abstract Motivation Human microbes get closely involved in an extensive variety of complex human diseases and become new drug targets. In silico methods for identifying potential microbe–drug associations provide an effective complement to conventional experimental methods, which can not only benefit screening candidate compounds for drug development but also facilitate novel knowledge discovery for understanding microbe–drug interaction mechanisms. On the other hand, the recent increased availability of accumulated biomedical data for microbes and drugs provides a great opportunity for a machine learning approach to predict microbe–drug associations. We are thus highly motivated to integrate these data sources to improve prediction accuracy. In addition, it is extremely challenging to predict interactions for new drugs or new microbes, which have no existing microbe–drug associations. Results In this work, we leverage various sources of biomedical information and construct multiple networks (graphs) for microbes and drugs. Then, we develop a novel ensemble framework of graph attention networks with a hierarchical attention mechanism for microbe–drug association prediction from the constructed multiple microbe–drug graphs, denoted as EGATMDA. In particular, for each input graph, we design a graph convolutional network with node-level attention to learn embeddings for nodes (i.e. microbes and drugs). To effectively aggregate node embeddings from multiple input graphs, we implement graph-level attention to learn the importance of different input graphs. Experimental results under different cross-validation settings (e.g. the setting for predicting associations for new drugs) showed that our proposed method outperformed seven state-of-the-art methods. Case studies on predicted microbe–drug associations further demonstrated the effectiveness of our proposed EGATMDA method. Availability Source codes and supplementary materials are available at: https://github.com/longyahui/EGATMDA/ Supplementary information Supplementary data are available at Bioinformatics online.
45
Hell, Franz, Yasser Taha, Gereon Hinz, Sabine Heibei, Harald Müller, and Alois Knoll. "Graph Convolutional Neural Network for a Pharmacy Cross-Selling Recommender System." Information 11, no. 11 (November 11, 2020): 525. http://dx.doi.org/10.3390/info11110525.
Full textAbstract:
Recent advancements in deep neural networks for graph-structured data have led to state-of-the-art performance in recommender system benchmarks. Adapting these methods to pharmacy product cross-selling recommendation tasks with a million products and hundreds of millions of sales remains a challenge, due to the intricate medical and legal properties of pharmaceutical data. To tackle this challenge, we developed a graph convolutional network (GCN) algorithm called PharmaSage, which uses graph convolutions to generate embeddings for pharmacy products, which are then used in a downstream recommendation task. In the underlying graph, we incorporate both cross-sales information from the sales transaction within the graph structure, as well as product information as node features. Via modifications to the sampling involved in the network optimization process, we address a common phenomenon in recommender systems, the so-called popularity bias: popular products are frequently recommended, while less popular items are often neglected and recommended seldomly or not at all. We deployed PharmaSage using real-world sales data and trained it on 700,000 articles represented as nodes in a graph with edges between nodes representing approximately 100 million sales transactions. By exploiting the pharmaceutical product properties, such as their indications, ingredients, and adverse effects, and combining these with large sales histories, we achieved better results than with a purely statistics based approach. To our knowledge, this is the first application of deep graph embeddings for pharmacy product cross-selling recommendation at this scale to date.
46
Albert, Michael, Cecilia Holmgren, Tony Johansson, and Fiona Skerman. "Embedding Small Digraphs and Permutations in Binary Trees and Split Trees." Algorithmica 82, no. 3 (January 7, 2020): 589–615. http://dx.doi.org/10.1007/s00453-019-00667-5.
Full textAbstract:
AbstractWe investigate the number of permutations that occur in random labellings of trees. This is a generalisation of the number of subpermutations occurring in a random permutation. It also generalises some recent results on the number of inversions in randomly labelled trees (Cai et al. in Combin Probab Comput 28(3):335–364, 2019). We consider complete binary trees as well as random split trees a large class of random trees of logarithmic height introduced by Devroye (SIAM J Comput 28(2):409–432, 1998. 10.1137/s0097539795283954). Split trees consist of nodes (bags) which can contain balls and are generated by a random trickle down process of balls through the nodes. For complete binary trees we show that asymptotically the cumulants of the number of occurrences of a fixed permutation in the random node labelling have explicit formulas. Our other main theorem is to show that for a random split tree, with probability tending to one as the number of balls increases, the cumulants of the number of occurrences are asymptotically an explicit parameter of the split tree. For the proof of the second theorem we show some results on the number of embeddings of digraphs into split trees which may be of independent interest.
47
Saha, Aadirupa, Rakesh Shivanna, and Chiranjib Bhattacharyya. "How Many Pairwise Preferences Do We Need to Rank a Graph Consistently?" Proceedings of the AAAI Conference on Artificial Intelligence 33 (July 17, 2019): 4830–37. http://dx.doi.org/10.1609/aaai.v33i01.33014830.
Full textAbstract:
We consider the problem of optimal recovery of true ranking of n items from a randomly chosen subset of their pairwise preferences. It is well known that without any further assumption, one requires a sample size of Ω(n2) for the purpose. We analyze the problem with an additional structure of relational graph G([n],E) over the n items added with an assumption of locality: Neighboring items are similar in their rankings. Noting the preferential nature of the data, we choose to embed not the graph, but, its strong product to capture the pairwise node relationships. Furthermore, unlike existing literature that uses Laplacian embedding for graph based learning problems, we use a richer class of graph embeddings—orthonormal representations—that includes (normalized) Laplacian as its special case. Our proposed algorithm, Pref-Rank, predicts the underlying ranking using an SVM based approach using the chosen embedding of the product graph, and is the first to provide statistical consistency on two ranking losses: Kendall’s tau and Spearman’s footrule, with a required sample complexity of O(n2χ(G¯))⅔ pairs, χ(G¯) being the chromatic number of the complement graph G¯. Clearly, our sample complexity is smaller for dense graphs, with χ(G¯) characterizing the degree of node connectivity, which is also intuitive due to the locality assumption e.g. O(n4/3) for union of k-cliques, or O(n5/3) for random and power law graphs etc.—a quantity much smaller than the fundamental limit of Ω(n2) for large n. This, for the first time, relates ranking complexity to structural properties of the graph. We also report experimental evaluations on different synthetic and real-world datasets, where our algorithm is shown to outperform the state of the art methods.
48
Meng, Lingqi, and Naoki Masuda. "Analysis of node2vec random walks on networks." Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 476, no. 2243 (November 2020): 20200447. http://dx.doi.org/10.1098/rspa.2020.0447.
Full textAbstract:
Random walks have been proven to be useful for constructing various algorithms to gain information on networks. Algorithm node2vec employs biased random walks to realize embeddings of nodes into low-dimensional spaces, which can then be used for tasks such as multi-label classification and link prediction. The performance of the node2vec algorithm in these applications is considered to depend on properties of random walks that the algorithm uses. In the present study, we theoretically and numerically analyse random walks used by the node2vec. Those random walks are second-order Markov chains. We exploit the mapping of its transition rule to a transition probability matrix among directed edges to analyse the stationary probability, relaxation times in terms of the spectral gap of the transition probability matrix, and coalescence time. In particular, we show that node2vec random walk accelerates diffusion when walkers are designed to avoid both backtracking and visiting a neighbour of the previously visited node but do not avoid them completely.
49
Bai, Yunsheng, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. "Learning-Based Efficient Graph Similarity Computation via Multi-Scale Convolutional Set Matching." Proceedings of the AAAI Conference on Artificial Intelligence 34, no. 04 (April 3, 2020): 3219–26. http://dx.doi.org/10.1609/aaai.v34i04.5720.
Full textAbstract:
Graph similarity computation is one of the core operations in many graph-based applications, such as graph similarity search, graph database analysis, graph clustering, etc. Since computing the exact distance/similarity between two graphs is typically NP-hard, a series of approximate methods have been proposed with a trade-off between accuracy and speed. Recently, several data-driven approaches based on neural networks have been proposed, most of which model the graph-graph similarity as the inner product of their graph-level representations, with different techniques proposed for generating one embedding per graph. However, using one fixed-dimensional embedding per graph may fail to fully capture graphs in varying sizes and link structures—a limitation that is especially problematic for the task of graph similarity computation, where the goal is to find the fine-grained difference between two graphs. In this paper, we address the problem of graph similarity computation from another perspective, by directly matching two sets of node embeddings without the need to use fixed-dimensional vectors to represent whole graphs for their similarity computation. The model, Graph-Sim, achieves the state-of-the-art performance on four real-world graph datasets under six out of eight settings (here we count a specific dataset and metric combination as one setting), compared to existing popular methods for approximate Graph Edit Distance (GED) and Maximum Common Subgraph (MCS) computation.
50
Shafqat, Wafa, and Yung-Cheol Byun. "Incorporating Similarity Measures to Optimize Graph Convolutional Neural Networks for Product Recommendation." Applied Sciences 11, no. 4 (February 3, 2021): 1366. http://dx.doi.org/10.3390/app11041366.
Full textAbstract:
With the ever-growing amount of online data and information, recommender systems are becoming overwhelmingly popular as an adequate approach for overcoming the challenge of information overload. Artificial Intelligence (AI) and Deep Learning (DL) have accumulated significant interest in many research areas, and recommender systems are one of them. In this paper, a Graph Convolutional Neural Network (GCNN)-based approach was used for online product recommendation. Graph-based methods have undergone substantial consideration for several recommendation tasks, with effective results. However, handling the computational complexities and training large datasets remain a challenge for such a model. Even though they are useful, the excessive measure of the model’s boundaries obstructs their applications in real-world recommender frameworks to a great extent. The recursive way of generating neighbor node embeddings for each node in the graph makes it more challenging to train a deep and large GCNN model. Therefore, we propose a model that incorporates measures of similarity between two different nodes, and these similarity measures help us to sample the neighbors beforehand. We estimate the similarity based on their interaction probability distribution with other nodes. We use KL divergence on different probability distributions to find the distance between them. This way, we set a threshold criterion for neighbor selection and generate other clusters. These clusters are then converted to subgraphs and are used as input for the proposed GCNN model. This approach simplifies the task of neighbor sampling for GCNN, and hence, we can observe a significant improvement in the computational complexity of the GCNN model. Finally, we compared the results with those for the previously proposed OpGCN model, basic GCNN model, and other traditional approaches such as collaborative filtering and probabilistic matrix factorization. The experiments showed that the complexity and computational time were decreased by estimating the similarity among nodes and sampling the nodes before training.