The goal of this thesis is to investigate the existing graph embedding methods. We aim to represent the nodes of undirected weighted graphs as low-dimensional vectors, also called embeddings, in order to create a rep- resentation suitable for various analytical tasks such as link prediction and clustering. We first introduce several contemporary approaches allowing to create such network embeddings. We then propose a set of modifications and improvements and assess the performance of the enhanced models. Finally, we present a set of evaluation metrics and use them to experimentally evalu- ate and compare the presented techniques on a series of tasks such as graph visualisation and graph reconstruction. 1

音樂歌單是由一組多首不同元素、風格的音樂所組成的，它包含了編輯者的個人品味以及因應主題、目的性產生而成。我們可以透過樂曲的律動、節奏、歌曲的主題精神，進而編輯一個相應契合的系列歌曲。當今的音樂收聽市場主要是在網路串流平台上進行隨時、隨地的聆聽，主要的平台有Spotify、Apple Music 以及KKBOX。各家業者不單只是提供使用者歌曲的搜索、單曲的聆聽，更提供訂閱專業歌單編輯者的歌單訂閱服務，甚至是讓一般的使用者參與歌單自訂編輯的過程。然而如何在有限的時間內針對使用者的聆聽習慣去介紹平台上豐富的音樂資源是個很大的挑戰。上述的過程我們稱之為推薦，而當前的音樂推薦研究大多是在對使用者進行相關歌曲的推薦，鮮少能進一步在更抽象層次上的歌單上進行推薦。這邊我們就此一推薦應用提供嵌入式向量表示法學習模型，在有著使用者、歌曲、歌單的異質性社交網路上，對使用者進行歌單的推薦。為了能有效的學習出歌單推薦的模型，我們更將使用者、歌單和歌曲的異質性圖形重組成二分圖（bipartite graph）， 並在此圖形的邊上賦予不等的權重，此一權重是基於使用者隱式反饋獲得的。接著再透過隨機漫步（random walk），根據邊上的權值進行路徑的抽樣選取，最後再將路徑上經過的節點進行嵌入式向量表示法的學習。我們使用歐幾里德距離計算各節點表示法的鄰近關係，再將與使用者較為相關的歌單推薦給使用者。實驗驗證的部分，我們蒐集KKBOX 兩年份的資料進行模型訓練並進行推薦，並將推薦的結果與使用者所喜愛的歌單進行準確度（Precision）評估， 結果證實所得到的推薦效果較一般熱門歌單的推薦來的好，且為更具個人化的歌單推薦。 / Music playlist is crafted with a series of songs, in which the playlist creator has controlled over the vibe, tempo, theme, and all the ebbs and flows that come within the playlist. To provide a personalization service to users and discover suitable playlists among lots of data, we need an effective way to achieve this goal. In this paper, we modify a representation learning method for learning the representation of a playlist of songs, and then use the representation for recommending playlists to users. While there have been some well-known methods that can model the preference between users and songs, little has been done in the literature to recommend music playlists. In light of this, we apply DeepWalk, LINE and HPE to a user-song-playlist network. To better encode the network structure, we separate user, song, and playlist nodes into two different sets, which are grouped by the user and playlist set and song as the other one. In the bipartite graph, the user and playlist node are connected to their joint songs. By adopting random walks on the constructed graph, we can embed users and playlists via the common information between each other. Therefore, users can discover their favorite playlists through the learned representations. After the embedding process, we then use the learned representations to perform playlist recommendation task. Experiments conducted on a real-world dataset showed that these embedding methods have a better performance than the popularity baseline. In addition, the embedding method learns the informative representations and brings out the personal recommendation results.

京都大学 / 新制・課程博士 / 博士(工学) / 甲第23153号 / 工博第4797号 / 新制||工||1750(附属図書館) / 京都大学大学院工学研究科建築学専攻 / (主査)教授 大崎 純, 教授 竹脇 出, 准教授 倉田 真宏 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DFAM

Indiana University-Purdue University Indianapolis (IUPUI) / The internet is the home for massive volumes of valuable data constantly being created, making it difficult for users to find information relevant to them. In recent times, online users have been relying on the recommendations made by websites to narrow down the options. Online reviews have also become an increasingly important factor in the final choice of a customer. Unfortunately, attackers have found ways to manipulate both reviews and recommendations to mislead users. A Recommendation System is a special type of information filtering system adapted by online vendors to provide suggestions to their customers based on their requirements. Collaborative filtering is one of the most widely used recommendation systems; unfortunately, it is prone to shilling/profile injection attacks. Such attacks alter the recommendation process to promote or demote a particular product. On the other hand, many spammers write deceptive reviews to change the credibility of a product/service. This work aims to address these issues by treating the review manipulation and shilling attack scenarios independently. For the shilling attacks, we build an efficient Reinforcement Learning-based shilling attack method. This method reduces the uncertainty associated with the item selection process and finds the most optimal items to enhance attack reach while treating the recommender system as a black box. Such practical online attacks open new avenues for research in building more robust recommender systems. When it comes to review manipulations, we introduce a method to use a deep structure embedding approach that preserves highly nonlinear structural information and the dynamic aspects of user reviews to identify and cluster the spam users. It is worth mentioning that, in the experiment with real datasets, our method captures about 92\% of all spam reviewers using an unsupervised learning approach.

During the past few years online misinformation, generally referred to as fake news, has been identified as an increasingly dangerous threat. As the spread of misinformation online has increased, fake news detection has become an active line of research. One approach is to use knowledge graphs for the purpose of automated fake news detection. While large scale knowledge graphs are openly available these are rarely up to date, often missing the relevant information needed for the task of fake news detection. Creating new knowledge graphs from online sources is one way to obtain the missing information. However extracting information from unstructured text is far from straightforward. Using Natural Language Processing techniques we developed a pre-processing pipeline for extracting information from text for the purpose of creating knowledge graphs. In order to classify news as fake or not fake with the use of knowledge graphs, these need to be converted into a machine understandable format, called knowledge graph embeddings. These embeddings also allow new information to be inferred or classified based on the already existing information in the knowledge graph. Only one knowledge graph embedding model has previously been used for the purpose of fake news detection while several new models have recently been developed. We compare the performance of three different embedding models, all relying on different fundamental architectures, in the specific context of fake news detection. The models used were the geometric model TransE, the tensor decomposition model ComplEx and the deep learning model ConvKB. The results of this study shows that out of the three models, ConvKB is the best performing. However other aspects than performance need to be considered and as such these results do not necessarily mean that a deep learning approach is the most suitable for real world fake news detection.

No description available.

The rapidly increasing number of existing drugs with genomic, biomedical, and pharmacological data make computational analyses possible, which reduces the search space for drugs and facilitates drug repositioning (DR). Thus, artificial intelligence, machine learning, and data mining have been used to identify biological interactions such as drug-target interactions (DTI), drug-disease associations, and drug-response. The prediction of these biological interactions is seen as a critical phase needed to make drug development more sustainable. Furthermore, late-stage drug development failures are usually a consequence of ineffective targets. Thus, proper target identification is needed. In this dissertation, we tried to address three crucial problems associated with the DR pipeline and presents several novel computational methods developed for DR. First, we developed three network-based DTI prediction methods using machine learning, graph embedding, and graph mining. These methods significantly improved prediction performance, and the best-performing method reduces the error rate by more than 33% across all datasets compared to the best state-of-the-art method. Second, because it is more insightful to predict continuous values that indicate how tightly the drug binds to a specific target, we conducted a comparison study of current regression-based methods that predict drug-target binding affinities (DTBA). We discussed how to develop more robust DTBA methods and subsequently developed Affinity2Vec, the first regression-based method that formulates the entire task as a graph-based method and combines several computational techniques from feature representation learning, graph mining, and machine learning with no 3D structural data of proteins. Affinity2Vec outperforms the state-of-the-art methods. Finally, since drug development failure is associated with sub-optimal target identification, we developed the first DL-based computational method (OncoRTT) to identify cancer-specific therapeutic targets for the ten most common cancers worldwide. Implementing our approach required creating a suitable dataset that could be used by the computational method to identify oncology-related DTIs. Thus, we created the OncologyTT datasets to build and evaluate our OncoRTT method. Our methods demonstrated their efficiency by achieving high prediction performance and identifying therapeutic targets for several cancer types. Overall, in this dissertation, we developed several computational methods to solve biomedical domain problems, specifically drug repositioning, and demonstrated their efficiencies and capabilities.

Le graphe est un concept puissant pour la représentation des relations entre des paires d'entités. Les données ayant une structure de graphes sous-jacente peuvent être trouvées dans de nombreuses disciplines, décrivant des composés chimiques, des surfaces des modèles tridimensionnels, des interactions sociales ou des bases de connaissance, pour n'en nommer que quelques-unes. L'apprentissage profond (DL) a accompli des avancées significatives dans une variété de tâches d'apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées sur une grille, comme dans la compréhension du texte, de la parole ou des images. Cependant, étonnamment peu de choses ont été faites pour explorer l'applicabilité de DL directement sur des données structurées sous forme des graphes. L'objectif de cette thèse est d'étudier des architectures de DL sur des graphes et de rechercher comment transférer, adapter ou généraliser à ce domaine des concepts qui fonctionnent bien sur des données séquentielles et des images. Nous nous concentrons sur deux primitives importantes : le plongement de graphes ou leurs nœuds dans une représentation de l'espace vectorielle continue (codage) et, inversement, la génération des graphes à partir de ces vecteurs (décodage). Nous faisons les contributions suivantes. Tout d'abord, nous introduisons Edge-Conditioned Convolutions (ECC), une opération de type convolution sur les graphes réalisés dans le domaine spatial où les filtres sont générés dynamiquement en fonction des attributs des arêtes. La méthode est utilisée pour coder des graphes avec une structure arbitraire et variable. Deuxièmement, nous proposons SuperPoint Graph, une représentation intermédiaire de nuages de points avec de riches attributs des arêtes codant la relation contextuelle entre des parties des objets. Sur la base de cette représentation, l'ECC est utilisé pour segmenter les nuages de points à grande échelle sans sacrifier les détails les plus fins. Troisièmement, nous présentons GraphVAE, un générateur de graphes permettant de décoder des graphes avec un nombre de nœuds variable mais limité en haut, en utilisant la correspondance approximative des graphes pour aligner les prédictions d'un auto-encodeur avec ses entrées. La méthode est appliquée à génération de molécules / Graph is a powerful concept for representation of relations between pairs of entities. Data with underlying graph structure can be found across many disciplines, describing chemical compounds, surfaces of three-dimensional models, social interactions, or knowledge bases, to name only a few. There is a natural desire for understanding such data better. Deep learning (DL) has achieved significant breakthroughs in a variety of machine learning tasks in recent years, especially where data is structured on a grid, such as in text, speech, or image understanding. However, surprisingly little has been done to explore the applicability of DL on graph-structured data directly.The goal of this thesis is to investigate architectures for DL on graphs and study how to transfer, adapt or generalize concepts working well on sequential and image data to this domain. We concentrate on two important primitives: embedding graphs or their nodes into a continuous vector space representation (encoding) and, conversely, generating graphs from such vectors back (decoding). To that end, we make the following contributions.First, we introduce Edge-Conditioned Convolutions (ECC), a convolution-like operation on graphs performed in the spatial domain where filters are dynamically generated based on edge attributes. The method is used to encode graphs with arbitrary and varying structure.Second, we propose SuperPoint Graph, an intermediate point cloud representation with rich edge attributes encoding the contextual relationship between object parts. Based on this representation, ECC is employed to segment large-scale point clouds without major sacrifice in fine details.Third, we present GraphVAE, a graph generator allowing to decode graphs with variable but upper-bounded number of nodes making use of approximate graph matching for aligning the predictions of an autoencoder with its inputs. The method is applied to the task of molecule generation

Scalable and accurate analysis of networks is essential to a wide variety of existing and emerging network systems. Specifically, network measurement and analysis helps to understand networks, improve existing services, and enable new data-mining applications. To support various services and applications in large-scale networks, network analytics must address the following challenges: (i) how to conduct scalable analysis in networks with a large number of nodes and links, (ii) how to flexibly accommodate various objectives from different administrative tasks, (iii) and how to cope with the dynamic changes in the networks. This dissertation presents novel path analysis schemes that effectively address the above challenges in analyzing pair-wise relationships among networked entities. In doing so, we make the following three major contributions to large-scale IP networks, social networks, and application service networks. For IP networks, we propose an accurate and flexible framework for path property monitoring. Analyzing the performance side of paths between pairs of nodes, our framework incorporates approaches that perform exact reconstruction of path properties as well as approximate reconstruction. Our framework is highly scalable to design measurement experiments that span thousands of routers and end hosts. It is also flexible to accommodate a variety of design requirements. For social networks, we present scalable and accurate graph embedding schemes. Aimed at analyzing the pair-wise relationships of social network users, we present three dimensionality reduction schemes leveraging matrix factorization, count-min sketch, and graph clustering paired with spectral graph embedding. As concrete applications showing the practical value of our schemes, we apply them to the important social analysis tasks of proximity estimation, missing link inference, and link prediction. The results clearly demonstrate the accuracy, scalability, and flexibility of our schemes for analyzing social networks with millions of nodes and tens of millions of links. For application service networks, we provide a proactive service quality assessment scheme. Analyzing the relationship between the satisfaction level of subscribers of an IPTV service and network performance indicators, our proposed scheme proactively (i.e., detect issues before IPTV subscribers complain) assesses user-perceived service quality using performance metrics collected from the network. From our evaluation using network data collected from a commercial IPTV service provider, we show that our scheme is able to predict 60% of the service problems that are complained by customers with only 0.1% of false positives. / text

We give a strongly polynomial time combinatorial algorithm to minimise the largest eigenvalue of the weighted Laplacian of a bipartite graph. This is accomplished by solving the dual graph embedding problem which arises from a semidefinite programming formulation. In particular, the problem for trees can be solved in time cubic in the number of vertices.