Management of a large-scale IT project requires establishing and following an elaborate set of rules. They range from code-style checking to project-wide workflows. For instance, we might establish thorough requirements traceability, meaning that every requirement should have both implementation and a set of tests, and vice-versa: every code change and every test should reference a requirement it addresses.

Now to automate traceability checking, all of the code, tests, documentation and requirements need to be parsed and represented as a dependency graph. The rule itself is a small graph depicting required relationships among appropriate types of objects.

After that checking, the rule comes down to finding all the instances where corresponding subgraphs match or fail to do so while they should. The same method can be employed for all kinds of analysis, from finding bugs in the code to the whole organisational network analysis.

Representing rules as graphs and using subgraph matching, in addition to rule validation, also implements knowledge extraction from a knowledge graph. After matching a rule like “a requirement should have a corresponding test”, a developer knows that the first matched thing is a requirement and the second one is a test. Despite the fact that requirements and tests are represented by complex subgraphs and have many other relations.

Unfortunately, subgraph matching is an NP-complete problem meaning it scales poorly to big graphs. Thus all practical algorithms solving NP-complete problems use clever sets of heuristics in order to speed-up the search process. Specifically for the problems of subgraph matching and graph isomorphism, researchers from the University of Salerno proposed the VF3 algorithm [1], which achieves state-of-the-art performance, especially on large and dense graphs. And yet subgraph matching on very big graphs can still take hours. This is perfectly fine for offline analyses in chemistry, pharmacology or genetics but unacceptable for interactive development.

Recently researchers started augmenting graph algorithms with Graph Neural Networks [2], which show impressive results in the tasks of node and edge properties prediction (say, travel time or max flow) but do not naturally generalise to the tasks involving several graphs like subgraph isomorphism problem [3].

One way to overcome this problem is to compute graph similarity using graph embeddings [4] because graphs with unsimilar embeddings cannot possibly be isomorphic. The same idea can be extended to subgraph matching. Dividing big graphs into small patches and computing similarity among them [5] makes it possible to discover parts of graphs that align.

Another line of research combines GNNs with Reinforcement Learning in order to speed up matching small query graphs in large graphs [6]. It is a common task for graph databases and knowledge bases. An even more ambitious approach employs topological and spectral methods in order to tackle a generalised version of subgraph matching, the graph alignment problem [7]. Unfortunately, these methods don’t always reduce computational demand, often provide only an approximate solution that can’t be turned into an exact one, and might have weird false positive corner cases.

Neural Sheaf Diffusion [8] seeks to recover the underlying structure of a graph in order to overcome GNN oversmoothing and improve performance in heterophilic settings, which opens up the possibility of employing this technique to speed up graph algorithms. But efficient application of this method to subgraph matching remains an open research and engineering problem.

Learn how to participate in our Research

05_image_crane.png

What is the fastest way to do subgraph matching for knowledge extraction and meaning grounding?

[1] V. Carletti, P. Foggia, A. Saggese, and M. Vento, “Introducing VF3: A New Algorithm for Subgraph Isomorphism”, in Graph-Based Representations in Pattern Recognition, P. Foggia, C.-L. Liu, and M. Vento, Eds., in Lecture Notes in Computer Science, vol. 10310. Cham: Springer International Publishing, 2017, pp. 128–139.

[2] L. Wu, P. Cui, J. Pei, L. Zhao, and X. Guo, Graph Neural Networks: Foundation, Frontiers and Applications. 2022.

[3] K. Xu, W. Hu, J. Leskovec, and S. Jegelka, “How Powerful are Graph Neural Networks?”, p. 17, 2019

[4] Y. Li, C. Gu, T. Dullien, O. Vinyals, and P. Kohli, Graph Matching Networks for Learning the Similarity of Graph Structured Objects. Cornell University, 2019, pp. 3835–3845.

[5] Z. Ying, A. H. -j. Wang, J. You, W. Chengtao, A. Canedo, and J. Leskovec, “Neural Subgraph Matching”. May 2021.

[6] Y. Bai, D. Xu, Y. Sun, and W. Wang, “Detecting Small Query Graphs in A Large Graph via Neural Subgraph Search”. Sep. 29, 2022.

[7] J. Hermanns, A. Tsitsulin, M. Munkhoeva, A. M. Bronstein, D. Mottin, and P. Karras, “GRASP: Graph Alignment Through Spectral Signatures,” in Lecture Notes in Computer Science, Springer Science+Business Media, 2021, pp. 44–52.

[8] C. Bodnar, F. Di Giovanni, B. P. Chamberlain, P. Liò, and M. M. Bronstein, “Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs”, Feb. 2022.

Machine Learning Assisted Graph Algorithms

When properly prompted, ChatGPT can correctly write a function in Python to sum up a list of numbers. This task is easy. On the other hand, if one asks ChatGPT to implement a Twitter clone, it will fail, producing incomplete and buggy code. Even a simplified Twitter-like system comprises a number of subsystems and non-trivial interactions and data transfers between them due to functional and technical constraints, as the System Design Primer illustrates [1].

It is possible to ask an LLM to come up with a high-level design, and then for each subsystem ask to refine the design into components, and then ask the same about components until it comes up with actual code. This hierarchical goal decomposition process is exactly what Auto-GPT tries to achieve, wrapping GPT-4 API calls in a loop with prompt engineering and long-term memory management [2]. At the same time, while working with goals, Auto-GPT faces many challenges of such a black-box approach: infinite goal decomposition, reasoning loops, inability to actually perform necessary steps, as well as inability to memoise and reuse already developed plans [3].

There is a huge abstraction gap between the low-level source code an agent needs to produce and high-level goals like "implement a Twitter clone". To overcome this problem, Noeon Research is building an IT automation system with rich semantic knowledge representation, the ability to form abstractions and decompose goals into lower-level subgoals.

Non-Axiomatic Reasoning System (NARS) [4] exemplifies one of the very few systems that can explicitly deal with the notion of a goal. Using Non-Axiomatic Logic (NAL), it represents goals as structured symbolic terms and thus can perform reasoning on them and with them, including decomposing goals into subgoals. But NARS is an immature research project, and many aspects of it are far from done. In particular, little headway has been made on the crucial problem of efficient resource allocation – finding facts relevant for logical inference in a huge database of facts. As facts and relations between them form a graph, resource allocation becomes a subgraph matching problem, very computationally demanding on its own.

An alternative to the top-down approach, where a high-level abstraction is recursively decomposed into lower-level abstractions, is the bottom-up approach, where we recursively compose low-level abstractions to create new high-level abstractions. For example, DreamCoder [5] learns to solve programming problems by growing a library of useful functions, using functions it has already invented to write new functions. Unfortunately, learned abstractions may not correspond to any known ones, and even when they do, they need to be recognised and properly named by a user.

Recently DeepMind presented a middle-ground approach [6]. Researchers combined user-supplied “proto-goals” with automatic pruning, which infers a subset of goals useful for solving a particular problem. The goals and proto-goals are represented as binary functions, which provides both its main advantage and major limitation: binary functions are easy to specify and relatively simple to understand and visualise. But they do not form a hierarchy of abstractions which limits applicability to more broad state and action spaces.

Learn more

02_image_crown.png

How to make an AI system that can decompose complex problems on different abstraction levels for efficient reasoning?

[1] System Design Primer. (2022). Twitter.

[3] Han Xiao. (2023) Auto-GPT Unmasked: The Hype and Hard Truths of Its Production Pitfalls.

[4] P. Wang, “Intelligence: From definition to design”. In International Workshop on Self-Supervised Learning (pp. 35-47). PMLR. 2022.

[5] K. Ellis et al., “DreamCoder: bootstrapping inductive program synthesis with wake-sleep library learning”. 2021.

[6] A. Bagaria, R. Jiang, R. Kumar, and T. Schaul, ‘Scaling Goal-based Exploration via Pruning Proto-goals’. arXiv, Feb. 09, 2023.

Goal Decomposition

For Noeon Research system to be applicable, it needs to automate organisational knowledge processing and structuring. It should convert project specifications, documentation, and code into a rich internal knowledge representation capable of handling both highly structured and natural language data. This representation should connect to vast pre-existing common-sense and IT-specific knowledge in order to swiftly and automatically learn project specifics.

Every knowledge-based system needs an initial population of its knowledge base, no matter what form it takes – explicit knowledge graph or non-interpretable LLM weights. Cyc – arguably the most comprehensive and vast knowledge graph and symbolic reasoning system – has been in development for almost 40 years, and much of that time was spent inputting handcrafted facts and rules [1]. LLMs require only a few weeks of training distributed across a fleet of machines. But while ontologies [2] and knowledge graphs are laborious to build, LLMs are opaque, hard to reason about and interpret.

However, it’s possible to automatically extract knowledge from LLMs in the form of a symbolic Knowledge Graph using symbolic knowledge distillation [3] techniques. Application of the same approach to current multi-modal LLMs has the potential to cover also not-so-common-sense knowledge from diverse areas like Physics, Chemistry and IT with highly structured knowledge in the form of formulae, code and diagrams.

This approach, however, is very new, and its applicability to wider contexts remains speculative. Moreover, it needs an extensive restricted natural language dataset expressing relevant knowledge to coax the LLM into generating further bits of knowledge in the same domain.

Another promising direction is to fine-tune pre-trained LLMs on a structured corpus in order to produce interpretable causal explanations [4]. These explanations are shaped into a predetermined structure in a restricted fragment of natural language and can be easily parsed into a symbolic form [5]. This approach also requires a relevant seed dataset for fine-tuning. Moreover, a limited context window demands clever prompt engineering in order to present an LLM with all relevant information and structure and elicit correct generation.

04_image_panda.png

What is the cheap and reliable way to incorporate both common and domain-specific knowledge into the knowledge base?

[1] W. Knight. (2016). An AI that spent 30 years learning some common sense is ready for work. MIT Technology Review.

[2] S. Borgo and P. Hitzler, Some Open Issues After Twenty Years of Formal Ontology. 2018, pp. 1–9.

[3] P. West et al., “Symbolic Knowledge Distillation: from General Language Models to Commonsense Models”. 2021.

[4] N. Mostafazadeh et al., “GLUCOSE: GeneraLized and COntextualized Story Explanations”. 2020.

[5] A. Kalyanpur, T. Breloff, and D. A. Ferrucci, “Braid: Weaving Symbolic and Neural Knowledge into Coherent Logical Explanations,” Proceedings of the AAAI Conference on Artificial Intelligence, vol. 36, no. 10, pp. 10867–10874, Jun. 2022.

Initial Population of Knowledge Base

Efficient completion of an IT project, automated or not, requires good Knowledge Representation. Noeon Research architects its Knowledge Representation to be able to handle different notions at different levels of abstraction. For example, structured entities like code, configuration, and data model are treated at a different level of abstraction compared to facts and negations such as requirements, architectural decisions and constraints; these, in turn, must be treated at a different level compared to causal relations, for instance, how workload affects performance and memory consumption. At a yet higher level, we have the relation of the project objectives to the objectives of adjacent projects, etc.

LLMs represent knowledge in the form of learned weights in vast neural networks approximating some conditional probability distribution function. This representation proves to be very versatile. For instance, ChatGPT natively answers programming questions, producing code in various programming languages. Surprisingly ChatGPT often performs on par or even better than fine-tuned systems like Copilot or CodeWhisperer [[1](#references)], presumably due to a bigger context window size and cross-domain knowledge transfer. However, LLM-based systems struggle with hallucinations and made-up facts [[2](#references)], inventing non-existent functions and APIs.

For an enterprise system to be trustworthy, it is mandatory to get correct answers where there are correct answers and be able to check the correctness. To achieve this, we need much more structured representations.

To overcome the opaqueness of weights and biases of Neural Network layers, researchers apply symbolic distillation [[3](#references)] to recover the structure of LLMs knowledge in the form of a Knowledge Graph. Being symbolic, structured and explicit, Knowledge Graphs support direct reasoning about causal relationships and fact-checking. However, it is unclear if this technique can be effectively transferred from common-sense general knowledge to domain-specific knowledge like programming.

In particular, if the process of compressing a corpus into an internal LLM representation loses information about relationships between domain objects, we will not be able to recover that information in the Knowledge Graph. This is not important in common-sense reasoning, where progress is measured in percent accuracy, but is much more important in software engineering, where using any API incorrectly will crash the program.

It is tempting to think that recovering a symbolic representation of knowledge entirely obviates the need for an LLM. However, instructions are usually given in natural language, which needs to be translated into a graph query language to interact with the symbolic knowledge base. LLMs are the best known tool for this kind of translation.

Ontologies [[4](#references)] are the best-known form of structured Knowledge Representation. However, there’s no universal philosophical and methodological approach to ontology construction which results in a multitude of mutually incompatible domain-specific ontologies [[5](#references)]. Moreover, as long as most ontologies are based on Description Logic [6] they are not adapted to representing procedural (algorithmic) knowledge which severely limits their usefulness for automatic code transformation.

01_image_fox.png

What is the best way to architect knowledge representation that helps to utilise it in downstream tasks?

[1] B. Yetiştiren, I. Özsoy, M. Ayerdem, and E. Tüzün, “Evaluating the Code Quality of AI-Assisted Code Generation Tools: An Empirical Study on GitHub Copilot, Amazon CodeWhisperer, and ChatGPT”, Apr. 21, 2023.

[2] Z. Ji et al., “Survey of Hallucination in Natural Language Generation”, ACM Computing Surveys, vol. 55, no. 12, pp. 1–38, Mar. 2023.

[3] P. West et al., “Symbolic Knowledge Distillation: from General Language Models to Commonsense Models”, Nov. 28, 2022.

[4] S. Staab and R. Studer, “What Is an Ontology?”, in Handbook on Ontologies, Springer Science & Business Media, 2013.

[5] S. Borgo and P. Hitzler, “Some Open Issues After Twenty Years of Formal Ontology”, 2018, pp. 1–9. 

[6] L. F. Sikos, “Description Logics: Formal Foundation for Web Ontology Engineering”, in Description Logics in Multimedia Reasoning, 2017.