Holistic Graph-Processing Systems: Enabling Real-World Scale and Societal Impact

In this talk, Distinguished Professor David A. Bader explores the evolution and impact of large-scale graph analytics, from his pioneering work in Linux supercomputing to today’s democratization of massive data science capabilities. The presentation highlights how the open-source Arachne framework, built on Arkouda, enables researchers and organizations to process and analyze graphs containing terabytes of data through an accessible Python interface, while the heavy computational work occurs on powerful backend systems.

Bader discusses three critical application domains of this technology: national security (detecting malicious network activity through relationship patterns), computational neuroscience (analyzing connectomes containing millions of neurons and synapses), and scientometrics (mapping research collaboration networks). These examples demonstrate how graph analytics can solve complex problems that were previously inaccessible due to computational limitations.

The talk emphasizes the parallel between Bader’s 1998 development of the Linux-based supercomputer – now the architecture for 100% of the world’s top supercomputers with an estimated economic impact of $100 trillion – and his current mission to democratize access to sophisticated graph analytics capabilities. Through open-source tools and frameworks, Bader’s work continues to bridge the gap between cutting-edge computing resources and real-world applications, making powerful data analysis accessible to researchers and practitioners across disciplines.

This talk explores the interplay of graph data models and Large Language Models (LLMs), addressing whether their integration is a current reality or an emerging vision. Graphs, as intuitive and powerful abstractions for modeling interconnected data, underpin a wide array of applications from social networks to scientific data analysis. The presentation dives into property graph transformations, emphasizing the need for expressive, declarative tools to enable robust, composable rule-based transformations and graph creation. The second part examines the role of LLMs in generating transformation rules and consistency constraints for property graphs. It discusses techniques for encoding graphs for LLM processing, compares performance across models (LLaMA-3, Mixtral), and highlights challenges in rule quality, scalability, and semantics. The talk concludes by outlining the promise of retrieval-augmented generation (RAG) for enhancing LLM capabilities with external graph-based knowledge, offering a roadmap for integrating symbolic and neural reasoning in future systems.

Recent advances in machine learning, especially with language models, have transformed many fields, dramatically raising expectations for artificial intelligence systems. Yet, these advances have also exposed a critical weaknesses: a lack of reliability and a need for a ridiculous amount of training data. In contrast, traditional AI methods offer more dependable but less flexible solutions, often limiting their broad applicability.

I am working in the intersection of these approaches which is sometimes called neuro-symbolic AI, particularly with knowledge graphs (KG). I investigate how graph neural networks can bridge the gap between discrete KGs and the statistical world of machine learning, enabling more robust and scalable solutions for tasks like structured and natural language question answering. My work often utilizes data from the medical and biomedical domains. During the seminar, I hope to discuss two sharpen my vision on the future of graph research. Among others, I am interesting in

1. 1.

   Improving ML Trustworthiness: Many popular ML models are not trustworthy. Can the addition of graph data make a difference? Can we get to a point where we can provide formal guarantees (e.g., error bounds) to enhance trust in graph ML models?

2. 2.

   Addressing issues in Multi-source KGs: There are challenges when attempting learning on unbalanced KGs, where a larger, potentially biased graph overshadows smaller, more specific ones. How could we overcome this?

3. 3.

   Get to scalable graph ML models using both smart use of hardware and knowledge on what the content of the graph is.

This talk discusses several co-design approaches to enable accelerated graph analytics across the whole continuum of computing. The talk first identifies the key issues in large scale graph processing, then reviews some algorithm-hardware co-design works to enable parallel graph processing on leadership computing systems with thousands of graphic processing units (GPUs). We then provide a full stack case study, the Graph Engine For Multithreaded Systems, which implements a scalable in-memory graph database for distributed high-performance computing clusters. The talk then briefly discusses the role of C++ distributed data structures libraries to design complex and malleable data models (including property graphs) and parallel (graph) algorithms. Finally, we discuss how to generate specialized accelerators for irregular applications and graph algorithms starting from shared memory parallel code descriptions with the SODA Synthesizer.

I talk about two topics one of which focuses on graph processing algorithms and techniques, and the other on an interesting use of graphs. The first topic is querying streaming graphs which is difficult because it combines two difficult issues, namely the unboundedness and high velocity of arrivals of streaming data and the difficulty of graph querying. In this space we systematically analyzed query models with clear semantics, developed streaming graph algebra primitives that allowed logical plan generation. Transformation rules were developed to manipulate the logical plans as well as a cost-based optimization framework to find the better plans. All of this was implemented as a prototype over Calcite.

The second topic is graph-based vector indexing. In this space, vectors that are generated by an embedding model form a graph dataset over which an approximate nearest neighbour search (ANNS) is performed. To aid search, indexes are built on this dataset. Graph-based indexes are those that treat each vector as a vertex with edges representing relationships between these vectors. The search takes a query point, starts from an entry point vertex in this index and finds the approximate nearest neighbours of the query point. These indexes can be built using either a refinement approach (e.g., NNDescent) or an iterative approach (e.g., HNSW). Refinement-based approaches start with a random graph (of vectors) and iterativey improve the graph. They have fast index construction time, but lower queries-per-second than iterative approaches and they cannot do incremental inserts of new vectors. On the other hand, iterative approaches insert vectors one-at-a-time, performing an ANNS to determine which other vectors it should be connected to. They have high construction cost, but good query performance and can handle incremental inserts. Our work involves an index, called MIRAGE, that combines the good characteristics of both approaches. It has better construction time and higher queries-per-second.

The recent seminar successfully identified and delineated several open problems within the domain of holistic graph-processing systems. Addressing these challenges is critical for enabling systems that can operate at real-world scale and maximize societal impact. From the issues discussed, we have prioritized and selected five problems of scientific and engineering importance, which are briefly described below.

• $\mathrm{■}$

  Application-centric graph usage matrix: the goal is to establish a structured analytical framework to systematically characterize graph utilization across diverse application domains, drawing inspiration from the foundational work of Asanovic et al. [1]. This analysis must extend beyond a mere quantification of how intensely are graph technologies utilized and must rigorously assess usage across four critical dimensions: (i) graph generative approaches and graph analytics, (ii) graph processing algorithms and workflows, (iii) graph operations at scale across the digital continuum, and (iv) adaptivity and optimization to ensure performance, scalability, and sustainability. Furthermore, a quantitative characterization should be developed to map applications across the trade-off space defined by accuracy, performance, and portability. This will facilitate the creation of a workflow model to guide the selection of appropriate algorithms. The matrix will be complemented by a curated, diverse collection of exemplars: documented instances of successful algorithm-implementation pairs focusing on algorithmic building blocks that drive high performance, productivity, and portability within real-world application contexts.

• $\mathrm{■}$

  Workload abstraction and scalable reference architecture: building upon the insights derived from the application-centric graph usage matrix, the objective is to define formal workload abstractions (Basic Graph Operations). These Basic Graph Operations must be composable elements for the construction of complex algorithms, workflows, and scalable, interacting data processing pipelines. Furthermore, we propose the development of a reference architecture for scalable graph processing. This architecture must leverage the defined workload abstractions and directly address the needs identified by the application-centric graph usage matrix. The design must weight distributed computing architectures and single-node architectures, considering their respective strengths and weaknesses and educate how processing demands can be framed to achieve the desired outcomes.

• $\mathrm{■}$

  The Memex Architecture: integrating graphs, metalearning, and causality: we aim to lay the foundation for an architecture that would allow to build a holistic knowledge graph and leverage it for self-improvement. The knowledge graph will semantically link information regarding system execution processes, resource performance metrics, identified system anomalies, underlying infrastructure properties, and crucially, causal relationships among these elements. We envision that this architecture can be leveraged for metalearning, enabling the system to continuously self-optimize and improve its operational efficiency over time.

• $\mathrm{■}$

  Hardware acceleration and graph compression techniques: a systematic analysis is required to determine the short-term and long-term implications of emerging hardware accelerators on the efficiency of holistic graph operations. Concurrently, there is a necessity to catalogue and evaluate graph compression techniques that can be efficiently processed by these accelerators.

• $\mathrm{■}$

  Scientific benchmarking standardization: perceive a significant opportunity to establish a new generation of rigorous, scientifically grounded graph processing benchmarks. These benchmarks could be built upon the foundations laid by the application-centric graph usage matrix, the formal characterization of algorithms, and the capabilities of emerging accelerators. The primary goal is to introduce a transparent methodology for comparing and contrasting algorithms, datasets, processing workloads, and the heterogeneous underlying computing infrastructure used for their execution.

As an academic and professional community focused on advancing holistic graph-processing systems, we consider addressing these open problems is fundamental to realizing the next generation of scalable and sustainable systems capable of generating significant real-world and societal-scale impact.