View Item 
      •   Home
      • 7. Theses and Dissertations
      • Theses and Dissertations (Doctor of Philosophy)
      • View Item
      •   Home
      • 7. Theses and Dissertations
      • Theses and Dissertations (Doctor of Philosophy)
      • View Item
      JavaScript is disabled for your browser. Some features of this site may not work without it.
      Subject Lookup

      Browse

      All of DR-NTUCommunities & CollectionsTitlesAuthorsBy DateSubjectsThis CollectionTitlesAuthorsBy DateSubjects

      My Account

      Login

      Statistics

      Most Popular ItemsStatistics by Country/RegionMost Popular Authors

      About DR-NTU

      From node embedding to community embedding on graphs

      Thumbnail
      added statement declaration (22.86Mb)
      Author
      Cavallari, Sandro
      Date of Issue
      2019-05-17
      School
      School of Computer Science and Engineering
      Abstract
      In the last few years, graphs have become an instinctive representative tool to better study complex structures. For example, in chemistry, it is common to represent and study the interaction between different proteins as a graph, reducing the experimental costs. Similarly, with the consolidation of Web 2.0 and the rise of Web 3.0, social networks have become one of the most popular sources of information, wherein users not only utilize but also provide content. On such platforms, the users’ information is explicitly provided and most of the information is implicitly contained in the links between different users. In robotics, it is possible to achieve more a “human-like” movement of an artificial skeleton if we represent the interaction of each major joint rather than adopting an independent approach. In addition to its representation capabilities, effectively extracting valuable information from graph data remains an open problem. While, in the last few years, machine learning, particularly deep learning, has achieved outstanding results in many complex applications such as image processing or natural language processing, researchers have not yet found a legitimate technique to leverage the structural information contained in the graph data type. Moreover, it is not yet possible to fully unleash the learning capabilities of deep models. Thus, in this thesis, we will introduce the concept of graph embedding, a robust set of techniques able to automatically extract meaningful information from network structures. First, we will provide an understanding of the problem setting by formally defining each component. Subsequently, we provide a review of all the major studies related to this topic. Then, we study an important yet largely under-explored setting of graph embedding, i.e., embedding communities rather than individual nodes. We identify that community embedding is not only useful for community-level applications such as graph visualization but also provides an exciting opportunity to improve community detection and node classification. To learn such embedding, our insight hinges on a closed loop among community embedding, community detection, and node embedding. On the one hand, node embedding can help improve community detection, which outputs good communities for fitting better community embedding. On the other hand, community embedding can be used to optimize the node embedding by introducing a community-aware high-order proximity. Based on this insights, we propose a novel Community Embedding (ComE) model that jointly solves the three tasks together. In practice, the number of communities can be unknown beforehand; therefore, we further proposed ComE+, a new framework that handles both uncertainty of unknown ground truth community assignments and an unknown number of communities. We further developed an efficient inference algorithm for ComE+ by maintaining the complexity as low as O(|V| + |E|). We evaluated the proposed algorithms on multiple real-world data sets and showed that they improve graph visualization and outperform the state-of-the-art baselines in various application tasks, e.g., community detection and node classification. Finally, given the proliferation of dynamic interactive structure in many socio-economic problems, we argue that a new set of embedding techniques are required. Recently, spatio-temporal graphs and interaction networks have proven to be useful in abstracting the underling interactive structure that defines the influence between the various aspects of a problem, but most of the previous studies have developed architecture that is able to only preserve manually crafted interrelation. However, we argue that it is necessary to automatically learn from such interaction structures if we want such models to fit in real-world problems. We also require that the discovered latent structure should be easily interpretable to facilitate the understanding of the modern world. Thus, we propose an efficient neural mixture model able to project a dynamic interaction in a fixed size space, preserving the influence that each node undergoes because of its neighbors. The proposed architecture is able to outperform strong baselines in various data sets ranging from the prediction of the household’s energy load to traffic congestion, and many others.
      Subject
      DRNTU::Engineering::Computer science and engineering
      Type
      Thesis
      Collections
      • Theses and Dissertations (Doctor of Philosophy)
      https://doi.org/10.32657/10220/48265
      Get published version (via Digital Object Identifier)

      Show full item record


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       


      NTU Library, Nanyang Avenue, Singapore 639798 © 2011 Nanyang Technological University. All rights reserved.
      DSpace software copyright © 2002-2015  DuraSpace
      Contact Us | Send Feedback
      Share |    
      Theme by 
      Atmire NV
       

       

      DCSIMG