Davide Mottin

Subgraph matching is a fundamental problem in graph analysis that seeks all instances (or embeddings) of a query subgraph within a larger data graph. Numerous subgraph matching algorithms have been developed for efficient processing. However, the best-performing algorithm differs across query and data graphs. A previous study proposed manually designed rule-based models for selecting the algorithm to use depending on query and data characteristics. However, this rule-based model is often ineffective even on in-distribution data, let alone on graphs having the same distribution. In this paper, we propose SUBLIME, a machine-learning-based framework that selects a subgraph matching algorithm to use for the sake of efficiency, based on the query and the data. SUBLIME learns from observations of the performance of subgraph matching algorithms on different data. It comprises two key components: a labeling strategy, which adds labels to experimental results, and a featurizer, which extracts handcrafted features from datasets and queries. Our experiments in subgraph matching and subgraph coverage problems show that SUBLIME selects high-performing algorithms and improves embeddings per second by up to 36.0% and coverage by up to 46.3% over baselines.

D-core decomposition (DCD) identifies groups of nodes with strong cohesion \dmsat different levels of granularity, supporting e.g. clustering and community detection in directed graphs. Given the inefficiency of computing DCD, the computational power of GPUs is an attractive target. However, existing algorithms are ill-suited due to their restrictive programming model, as well as memory constraints in the widely available consumer-level GPUs. In particular, we show that any trivial adaptation of peeling algorithms, state-of-the-art for DCD, suffers from workload imbalance, redundant operations, and repeated atomic operations. To address these challenges, we propose a novel dynamic strategy to balance the computation on nodes with varying vertex degree and an enumeration-based lightweight memory footprint with greatly reduced thread contention. We conduct extensive experiments on 12 datasets showing that Geld achieves an average speedup of 31× over GPU peeling DCD, 6× over GPU H-Index DCD, 22× over the best existing parallel DCD algorithm with 33% memory efficiency, and 3 orders of magnitude over the best serial DCD algorithm.

Artificial Intelligence has become integral to intelligent drug discovery, with Graph Machine Learning (GML) emerging as a powerful structure-based method for modelling graph-structured biomedical data and investigating their properties. However, GML faces challenges such as limited interpretability and heavy dependency on abundant high-quality training data. On the other hand, knowledge-based methods leverage biomedical knowledge databases, e.g., Knowledge Graphs (KGs), to explore unknown knowledge. Nevertheless, KG construction is resource-intensive and often neglects crucial structural information in biomedical data. In response, recent studies have proposed integrating external biomedical knowledge into the GML pipeline to realise more precise and interpretable drug discovery with scarce training data. Nevertheless, a systematic definition for this burgeoning research direction is yet to be established. This survey formally summarises Knowledge-augmented Graph Machine Learning (KaGML) for drug discovery and organises collected KaGML works into four categories following a novel-defined taxonomy. We also present a comprehensive overview of long-standing drug discovery principles and provide the foundational concepts and cutting-edge techniques for graph-structured data and knowledge databases. To facilitate research in this promptly emerging field, we share collected practical resources that are valuable for intelligent drug discovery and provide an in-depth discussion of the potential avenues for future advancements.

Knowledge graphs form large networks of millions of entities (e.g., Michelle Obama, Barack Obama) and relationships (e.g., married). To obtain an overview of the entity, we need to inspect a potentially large number of relationships to other entities. For this reason, entity summarization aims to extract succinct but expressive descriptions of each entity. Yet, existing methods build their summaries only based on the immediate connections of an entity, disregarding how indirect relationships contain essential information for describing the entity (e.g., understanding Michelle Obama also via her husband's role as former president). We propose IRES, an unsupervised entity summarization method built on graph theoretical principles. We draw a notable connection between the informativeness of a summary and graph partitioning, and devise an effective approach to learn diverse aspects that characterize an entity. In a comprehensive experimental study, IRES shows superior summary quality. In particular, when full neighborhood information is available, IRES outperforms existing methods by 6 percentage points F1 while maintaining competitive computational efficiency.

Angle-resolved photoemission spectroscopy (ARPES) is a powerful experimental technique to determine the electronic structure of solids. Advances in light sources for ARPES experiments are currently leading to a vast increase of data acquisition rates and data quantity. On the other hand, access time to the most advanced ARPES instruments remains strictly limited, calling for fast, effective, and on-the-fly data analysis tools to exploit this time. In response to this need, we introduce ARPESNet, a versatile autoencoder network that efficiently summmarises and compresses ARPES datasets. We train ARPESNet on a large and varied dataset of 2-dimensional ARPES data extracted by cutting standard 3-dimensional ARPES datasets along random directions in k. To test the data representation capacity of ARPESNet, we compare k-means clustering quality between data compressed by ARPESNet, data compressed by discrete cosine transform, and raw data, at different noise levels. ARPESNet data excels in clustering quality despite its high compression ratio.

Large Language Models (LLMs) have shown remarkable capabilities in processing various data structures, including graphs. While previous research has focused on developing textual encoding methods for graph representation, the emergence of multimodal LLMs presents a new frontier for graph comprehension. These advanced models, capable of processing both text and images, offer potential improvements in graph understanding by incorporating visual representations alongside traditional textual data. This study investigates the impact of graph visualisations on LLM performance across a range of benchmark tasks at node, edge, and graph levels. Our experiments compare the effectiveness of multimodal approaches against purely textual graph representations. The results provide valuable insights into both the potential and limitations of leveraging visual graph modalities to enhance LLMs' graph structure comprehension abilities.

Can we assess a priori how well a knowledge graph embedding will perform on a specific downstream task and in a specific part of the knowledge graph? Knowledge graph embeddings (KGEs) represent entities (e.g., ''da Vinci,'' ''Mona Lisa'') and relationships (e.g., ''painted'') of a knowledge graph (KG) as vectors. KGEs are generated by optimizing an embedding score, which assesses whether a triple (e.g., ''da Vinci,'' "painted,'' ''Mona Lisa'') exists in the graph. KGEs have been proven effective in a variety of web-related downstream tasks, including, for instance, predicting relationship(s) among entities. However, the problem of anticipating the performance of a given KGE in a certain downstream task and locally to a specific individual triple, has not been tackled so far. In this paper, we fill this gap withReliK, a Reli ability measure for K GEs. ReliK relies solely on KGE embedding scores, is task- and KGE-agnostic, and requires no further KGE training. As such, it is particularly appealing for semantic web applications which call for testing multiple KGE methods on various parts of the KG and on each individual downstream task. Through extensive experiments, we attest thatReliK correlates well with both common downstream tasks, such as tail/relation prediction and triple classification, as well as advanced downstream tasks, such as rule mining and question answering, while preserving locality.