Scalable Graph Mining and Learning

This talk surveys recent accomplishments in graph machine learning and graph neural network research.

A real-world challenge in data science is to develop interactive methods for quickly analyzing new and novel data sets that are potentially of massive scale. In this talk, Bader will discuss his development of graph algorithms in the context of Arkouda, an open-source NumPy-like replacement for interactive data science on tens of terabytes of data. Massive-scale analytics is an emerging field that integrates the power of high-performance computing and mathematical modeling to extract key insights and information from large-scale data sets. Productivity in massive-scale analytics entails quick interpretation of results through easy-to-use frameworks, while also adhering to design principles that combine high-performance computing and user-friendly simplicity. However, data scientists often encounter challenges, especially with graph analytics, which require the analysis of complex data from various domains, such as the cybersecurity, natural and social sciences. To address this issue, we introduce Arachne, an open-source framework that enhances accessibility and usability in massive-scale graph analytics. Arachne offers novel algorithms and implementations of graph kernels for efficient data analysis, such as connected components, breadth-first search, triangle counting, k-truss, among others. The high-performance algorithms are integrated into a back-end server written in HPE/Cray’s Chapel language and can be accessed through a Python application programming interface (API). Arachne’s back-end server is compatible with Linux supercomputers, is easy to set up, and can be utilized through either Python scripts or Jupyter notebooks, which makes it a desirable tool for data scientists who have access to high performance computers. In this talk, Bader presents an overview of the algorithms his research group has implemented into Arachne and, if applicable, the algorithmic innovations of each. Further, Bader will discuss improvements to our graph data structure to store extra information such as node labels, edge relationships, and node and edge properties. Arachne is built as an extension to the open-source Arkouda framework and allows for graphs to be generated from Arkouda dataframes.

The open-source code for Arachne can be found at https://github.com/Bears-R-Us/arkouda-njit. This is joint work with Oliver Alvarado Rodriguez, Zhihui Du, Joseph Patchett, Naren Khatwani, Fuhuan Li, Bader is supported in part by the National Science Foundation award CCF-2109988.

Combinatorial optimization problems play a pivotal role in various domains, challenging researchers to find optimal solutions within large solution spaces. One key strategy to tackle the complexity of these problems is data reduction, where instances are simplified to facilitate more efficient algorithms. In this talk, we delve into the world of combinatorial optimization, exploring classic data reduction techniques and their impact on problem-solving efficiency.

Additionally, we will explore different strategies of utilizing machine learning to reduce problem instances in the context of combinatorial optimization and ask how machine learning and exact data reductions can be combined more effectively. In particular, in future work we want to explore potential synergies between these approaches, considering the strengths of each and the challenges in their integration.

Identifying a maximum independent set is a fundamental NP-hard problem. This problem has several real-world applications and requires finding the largest possible set of vertices not adjacent to each other in an undirected graph. Over the past few years, branch-and-bound and branch-and-reduce algorithms have emerged as some of the most effective methods for solving the problem exactly. Specifically, the branch-and-reduce approach, which combines branch-and-bound principles with reduction rules, has proven particularly successful in tackling previously unmanageable real-world instances. This progress was largely made possible by the development of more effective reduction rules. Nevertheless, other key components that can impact the efficiency of these algorithms have not received the same level of interest. Among these is the branching strategy, which determines which vertex to branch on next. Until recently, the most widely used strategy was to choose the vertex of the highest degree. In this work, we present a graph neural network approach for selecting the next branching vertex. The intricate nature of current branch-and-bound solvers makes supervised and reinforcement learning difficult. Therefore, we use a population-based genetic algorithm to evolve the model’s parameters instead. Our proposed approach results in a speedup on 73% of the benchmark instances with a median speedup of 24%.

A knowledge graph (KG) represents a unique convergence of graph structures and natural language. On one side the graph structure is well defined by connection among entities. On the other hand, each entity and each relationship has a type and convey semantic meaning. Over time, research has emphasized different facets – while the machine learning community favors semantic and semi-structured information, the Data Mining and Database community views KGs as labeled graphs. Recently, the raise of Language Models and multimodal learning, seem to have found a new space for KGs to enhance the interpretability and improve the accuracy of models. This talk will survey some research on all sides of the coin and challenge the audience in finding a unification framework for KGs.

Social network data breaks a fundamental assumption of existing causal inference techniques, known as the Stable Unit Treatment Value Assumption (SUTVA), which states that the treatment of one unit cannot influence the outcome of other units. In real-world scenarios, it is common for related units to interact with each other which leads to interference (also known as spillover, or peer effects), in which the outcomes of units are interdependent. For example, the opinion of one person can influence the opinion of their friends, and the health status of one individual can impact the health status of others they interact with. In this talk, I will focus on recent work and problems related to discovering causal insights from social network data.

The field of natural language processing has witnessed significant progress in recent years, with a notable focus on improving language models’ performance through innovative prompting techniques. Among these, structure-enhanced prompting has emerged as a promising paradigm, with designs such as Chain-of-Thought (CoT) or Tree of Thoughts (ToT), in which the LLM reasoning is guided by a structure such as a tree. We refer to these structures as reasoning topologies, because their representation becomes to a degree spatial, as they are contained within the LLM context. In the first part of the talk, we overview this recent field, focusing on fundamental classes of harnessed structures, the representations of these structures, algorithms executed with these structures, relationships to other parts of the generative AI pipeline such as knowledge bases or Graph Neural Networks, and others. Second, we introduce Graph of Thoughts (GoT): a framework that advances prompting capabilities in LLMs beyond those offered by CoT or ToT. The key idea and primary advantage of GoT is the ability to model the information generated by an LLM as an arbitrary graph, where units of information (“LLM thoughts”) are vertices, and edges correspond to dependencies between these vertices. This approach enables combining arbitrary LLM thoughts into synergistic outcomes, distilling the essence of whole networks of thoughts, or enhancing thoughts using feedback loops. We illustrate that GoT offers advantages over state of the art on different tasks such as keyword counting while simultaneously reducing costs. We finalize with outlining research challenges in this fast-growing field.

For over a decade, the Graph Mining team in Google Research has been working on the mission to build the world’s most scalable library for graph algorithms and analysis, and use it to improve Google products. Our goal is to make it easy for developers to use graph algorithms in their applications, and to provide them with the tools they need to build scalable and efficient graph processing systems. Our algorithms and systems are used in a wide array of Google products, such as Search, YouTube, AdWords, Play, Maps, and Social. The systems developed by our team have had a significant impact on the way that Google engineers build and deploy graph-based applications.

In this talk I will give an overview of the team, what it works on, and what challenges we view as fundamental for large scale graph systems.

Various disciplines, from computer science to physics to sociology to economics, have each approached “graphs” or “networks” from a different perspective or interest. Each of these fields has established its specific publishing venues, conferences and societies. Overall, the talk aims to present what (future) challenges and opportunities this division over disciplines brings in terms of the exchange of methods and findings. In addition to highlighting how insights from one field have positively influenced the other, the talk also describes several instances of “multiple discoveries” of network phenomena.

Matchings in graphs are classical problems in combinatorial optimization and computer science, significant due to their theoretical importance and relevance to applications. Polynomial time algorithms for several variant matching problems with linear objective functions have been known for fifty years. However, these algorithms fail to compute matchings in big graphs with billions of edges. They are also not concurrent and thus practical parallel algorithms are not known.

This has led to work in the last twenty years on designing approximation algorithms for variant matching problems with near-linear time complexity in the size of the graphs. Approximation has thus become a useful paradigm for designing parallel matching algorithms and also streaming algorithms. In this talk I will report on an approach to fast approximation algorithms and streaming algorithms for the maximization version of edge-weighted matching. It can be extended to edge-weighted b-matching, and the maximum k-disjoint weighted matching problems.

Matching and related problems could be applied to graph mining, where the matching objective is a submodular function.

Graph sparsification is the approximation of dense graphs by sparse ones. Work over the past two decades have exhibited a wide range of objectives that are sparsifiable, such as cut structure, dense subgraphs, and eigenvectors, but also objectives that are not sparsifiable, such as distances and matchings. This talk will overview recent results on sparsification, and also discuss algorithmic ways of blurring the distinctions between sparse and dense problems.

Foundation models in graph learning are hard to design due to the lack of common invariances that transfer across different structures and domains. In this talk, I will give an overview of ULTRA, our new approach for creating foundation models for knowledge graph reasoning that captures relation interactions and does not require any input node or edge features. Experimentally, a single pre-trained ULTRA in the zero-shot inference mode outperforms supervised SOTA models on 50+ diverse graphs and can generalize to any multi-relational graph.

State-of-the-art link prediction models leveraging neighborhood topology for node representation learning underperform in data-scarce regimes involving low-degree nodes and entities with insufficient metadata. To overcome this challenge, we have proposed a non-end-to-end training approach leveraging unsupervised pre-training on a corpus significantly different from and larger than the training graph to enhance the generalizability of link prediction models. Additionally, we have introduced AI-Bind, a model that combines network science-inspired negative sampling and unsupervised pre-training on molecular representation. AI-Bind not only addresses topological shortcuts and the generalization shortcomings of existing models in predicting drug-target interactions but also excels in identifying binding locations on proteins for novel molecular structures. Furthermore, its integration with AutoDock Tools expedites the molecular docking process.

We give a technique for partitioning streaming communication data into static graph snapshots. We use combinatorial statistical models to adaptively find when a snapshot is stable, while watching for significant data shifts – indicating a new snapshot should begin. If snapshots are not found carefully, they poorly represent the underlying data – and downstream graph analytics can fail.

We demonstrate the method on several real-world datasets and show its accuracy against known-answer synthetic datasets. Not surprisingly, snapshot properties change from those created with other methods. For example, our snapshots do not generally “densify” over time, contradicting previous influential results that used simpler partitioning methods.

Detecting, counting, or even enumerating the copies of a specific subgraph pattern contained in a graph is an important tool in the analysis of various kinds of networks, from social sciences to biology and chemistry, with numerous further applications, e.g. in machine learning on graphs, building graph generators, or graph partitioning. In many use case scenarios, the input graphs are almost naturally subject to change, i.e., edges may newly arrive or disappear, vertices may be introduced or abandoned, or weights may change, which makes the input graph dynamic.

In this talk, we will focus on maintaining the number of occurrences of small patterns on three or four vertices in a dynamic graph that undergoes an a priori unknown sequence of edge insertions and deletions. In the first part, we will see how this problem can be solved algorithmically in theory. Afterwards, we will also take a look at the practical side and discuss how the algorithms behave on real-world instances and how they can be further improved experimentally.

The talk concludes with some challenges and open questions in algorithm engineering for dynamic graph problems.

A major recent development in computer hardware was the rise of dedicated accelerator hardware for machine learning applications such as the Graphcore IPUs and Cerebras WSE. These processors have evolved from the experimental state into market-ready products, and they have the potential to constitute the next major architectural shift after GPUs saw widespread adoption a decade ago.

A salient feature of these devices is the use of SRAM for memory, which offers very low latency and high bandwidth, making them attractive for a wide range of graph algorithms. On the other hand, the wide parallelism employed in these devices makes it difficult to use them efficiently for irregular computations.

In this talk we will present the new hardware and discuss the programming techniques that are required to unlock their potential. We present implementations of basic graph algorithms and show early results on the attainable performance, as well as comparisons to other architectures. We follow up by discussing the wider implications of the architecture for algorithm design and programming, along with the wider implications of adopting such hardware, and we discuss some recent graph mining applications.

The ubiquity of massive graph data sets in numerous applications requires fast algorithms for extracting knowledge from these data. We are motivated here by three electrical measures for the analysis of large small-world graphs $G=(V,E)$ – i.e., graphs with diameter in $O(\log |V|)$, which are abundant in complex network analysis. From a computational point of view, the three measures have in common that their crucial component is the diagonal of the graph Laplacian’s Pseudoinverse, $L^{†}$. Computing $diag(L^{†})$ exactly by pseudoinversion, however, is as expensive as dense matrix multiplication – and the standard tools in practice even require cubic time. Moreover, the Pseudoinverse requires quadratic space – hardly feasible for large graphs. Resorting to approximation by, e.g., using the Johnson-Lindenstrauss transform, requires the solution of $O(\log |V|/{ϵ}^2)$ Laplacian linear systems to guarantee a relative error, which is still costly for large inputs.

In the ongoing project, we work on extending a previous approximation algorithm that requires the solution of only one Laplacian linear system and sampling of uniform spanning trees, which then are related to $diag(L^{†})$ via effective resistances. This previous work so far only supports undirected graphs, and the extension is towards directed graphs. For that, we introduce a new sampling scheme, which relies on the sampling of escape random walks. In theory, the converted algorithm obtains an $\pm ϵ$-approximation with high probability in a time that is nearly linear in $|E|$ and quadratic in $1/ϵ$. In addition, the formulation makes the approximation suitable for GPU-based implementation, leading to massive parallelism.

Understanding protein function and developing molecular therapies require deciphering the cell types in which proteins act as well as the interactions between proteins. However, modeling protein interactions across diverse biological contexts, such as tissues and cell types, remains a significant challenge for existing algorithms. We introduce PINNACLE, a flexible geometric deep learning approach that is trained on contextualized protein interaction networks to generate context-aware protein representations. Leveraging a human multi-organ single-cell transcriptomic atlas, PINNACLE provides 394,760 protein representations split across 156 cell type contexts from 24 tissues and organs. PINNACLE’s contextualized representations of proteins reflect cellular and tissue organization and PINNACLE’s tissue representations enable zero-shot retrieval of the tissue hierarchy. Pretrained PINNACLE’s protein representations can be adapted for downstream tasks: to enhance 3D structure-based protein representations for important protein interactions in immuno-oncology (PD-1/PD-L1 and B7-1/CTLA-4) and to study the effects of drugs across cell type contexts. PINNACLE outperforms state-of-the-art, yet context-free, models in nominating therapeutic targets for rheumatoid arthritis and inflammatory bowel diseases, and can pinpoint cell type contexts that predict therapeutic targets better than context-free models. PINNACLE is a graph-based contextual AI model that dynamically adjusts its outputs based on biological contexts in which it operates.

Graph learning algorithms have attained state-of-the-art performance on many graph analysis tasks such as node classification, link prediction, and clustering. It has, however, become hard to track the field’s burgeoning progress. One reason is due to the very small number of datasets used in practice to benchmark the performance of graph learning algorithms. This shockingly small sample size used for standard evaluations allows for only limited scientific insight into how graph learning models perform.

My group has been working on addressing this deficiency through the use of synthetic graph generation for evaluating graph learning models [1]. This approach consists of generating synthetic graphs, and contrasting the behavior of different graph learning algorithms in these controlled scenarios. Our prior work in this area (e.g. GraphWorld [2]) introduced the “GraphWorld paradigm”

1. 1.

   Define graph metrics to quantify the “universe” of graphs generated by the framework

2. 2.

   Define a Task (graph generator, feature generator, and prediction) tuple that fully defines a graph learning problem

3. 3.

   Vary the graphs generated, in order to cover the “universe” as well as possible

4. 4.

   Evaluate a wide range of graph learning models on the Task to characterize the response surface for each model

Naturally, there is much more to do in the space! For example, our initial investigation focused on community-aware generators (like the Stochastic Block Model) for this evaluation. However, this design decision limited the scope of graphs which could be generated. Further analysis [3], has shown that better control of the degree distribution of the generated graph creates situations which further differentiate graph learning models. Aside from obvious improvements to the components of the framework above, this line of research enables new problem formulations. For example, we also have examined how privacy-aware graph generative models can generate anonymized graph datasets on which a model has similar performance to the real datasets [4]. This is a new and interesting regime for both graph generation and synthetic evaluation. Finally, in very recent work [5], we’ve illustrated how this style of synthetic analysis can also be used to quantify the reasoning capabilities of Large Language Models (LLMs), providing an interesting connection to the emerging field of Artificial Intelligence.

Causal representation learning refers to the discovery of high-level causal variables from low-level observational data and is an important problem in machine learning and causal inference. In machine learning, causal representation learning can help with robustness and learning reusable mechanisms [1]. In causal inference, it can help with discovering the causal mechanisms that gave rise to the observed data and with identifying causal effects of interest. While initial work has been done in causal representation learning for IID data (e.g., [1, 2]), little research has been done on causal representation learning for graphs [3, 4].

Many real-world systems can be represented as graphs in which nodes represent entities of interest, which can be of various types, and edges represent interactions between these entities. Some examples include social networks, protein interaction networks, molecular structure networks, and drug-protein-disease networks [4]. Graph representation learning has facilitated discoveries across real-world applications on structured data [4, 6]. However, despite the prevalence of causal relationships in real-world systems, existing graph representation learning algorithms are unable to extrapolate causal mechanisms.