People of ACM - Ken-ichi Kawarabayashi

July 30 , 2026

Broadly speaking, what is graph theory and why is it an especially useful tool in computer programming projects?

Graph theory is the mathematical study of networks. A graph consists of vertices, which represent objects; and edges, which represent relationships or connections between them. This simple abstraction is extraordinarily versatile: transportation systems, communication networks, scheduling constraints, biological interactions, financial transactions, and social relationships can all be modeled as graphs.

That is what makes graph theory so useful in computing. Once a problem is expressed as a graph, we can apply a large body of mathematical results and efficient algorithms. Routing protocols search for good paths through communication networks; search engines analyze links among webpages; scheduling systems reason about dependencies and conflicts; and recommendation systems use relationships among users, products, and preferences.

Graphs are also natural data structures for programmers. They let us separate the structure of a problem from its particular application. PageRank is a famous example—it uses a random-walk model on the web graph to estimate the importance of webpages. A concept developed in graph theory can therefore move directly from mathematics into a practical system used at enormous scale. Furthermore, from a software engineering perspective, graphs provide a remarkably elegant and natural data structure to implement in code.

When you are working on a mathematical problem, do you sometimes have an intuition that your approach is correct even before you have demonstrated the proof?

Yes, very often. Mathematical research usually begins with an intuition that a statement should be true or that a certain route may lead to a proof. I test that intuition on small examples, try to find counterexamples, and ask which part of the structure is really essential. As the evidence accumulates, the intuition becomes more precise and may suggest the right lemma or invariant.

But intuition is only a guide; it is not a proof. Sometimes the proof confirms the original idea, and sometimes it reveals that the intuition was wrong or incomplete. I think of intuition as a rough map; without it, it is difficult to know where to go, but proof tells us whether the route is valid.

In one of your most cited papers, “Representation Learning on Graphs with Jumping Knowledge Networks” you and your co-authors present a new deep learning approach for representation learning. What role can graphs play in improving machine learning models?

Graphs allow machine-learning models to use relationships, not just the features of isolated data points. In a graph neural network, a node repeatedly gathers information from its neighbors. After one layer, it sees nearby nodes. After several layers, it can incorporate information from a larger neighborhood.

The difficulty is that the useful neighborhood size varies across locations. In a sparse part of a graph, information may need to travel farther; in a dense part, a smaller neighborhood may already be sufficient. Our Jumping Knowledge network combines representations from different layers, allowing each node to dynamically select the neighborhood range most appropriate for its local density and the specific task.

The broader lesson is that graph theory can help us understand how information propagates through a model. That understanding can guide the design of more adaptive and reliable machine learning architectures for social, biological, citation, and many other networked data sets.

You've stated that one of the top open questions you'd like to work on is the Four Color Theorem. What is the Four Color Theorem and why is it an important concept in graph theory?

The Four Color Theorem states that every planar map can be colored with at most four colors so that regions sharing a boundary have different colors. Equivalently, every planar graph is 4-colorable. The statement is simple enough for a child to understand, yet it resisted proof for more than a century. Its combination of elementary formulation, enormous difficulty, and influence on the relationship between mathematics and computation makes it one of the central results of graph theory.

The 1976 proof by Kenneth Appel and Wolfgang Haken was historic because it relied on a computer to check many configurations that could not realistically be verified line by line by hand. It therefore raised a fundamental question: how should mathematics establish confidence in a computation that is part of a proof? Later formalizations, including a proof checked in Coq, provided one answer, but the issue remains central to computer-assisted science.

In our recent work, "The Four Color Theorem with Linearly Many Reducible Configurations and Near-Linear Time Coloring,” which will appear at FOCS 2026, we strengthen the structural statement behind the theorem. Earlier proofs guarantee at least one reducible configuration; we show, roughly speaking, that a planar graph contains linearly many places where reductions can be made. This turns an existence proof into a deterministic near-linear time coloring algorithm; instead of reducing the graph by a constant amount at each step, we can reduce it by a constant factor.

Equally important to me is how the algorithm is presented. A computer-assisted proof should not merely publish source code and ask the community to trust it. It should explain why the computation proves the lemma, provide human-readable pseudocode that fully specifies the computation, and connect each routine to its implementation.

Good pseudocode should be both mathematically readable and algorithmically complete. In our project, we describe its computation so precisely and transparently in human-readable pseudocode that an independent researcher (or even independent AI systems) should be able to verify the code. If you wanted, you could reconstruct the actual program without consulting the authors’ source code and reproduce the same mathematical checks. This does not replace formal verification, but it introduces a powerful new standard for implementation checks:

Do not ask science merely to trust a program. Publish the algorithmic specification so precisely
(i.e., detailed pseudocode) that others can check the program and reproduce the result. That principle extends far beyond graph theory to any scientific field that relies on computational results.

Personally, the Four Color Theorem has fascinated me since I was an undergraduate. Although it is proved, I do not think our understanding of the proof is complete. I hope we can find simpler, faster, and more conceptual explanations of why four colors are enough.

The National Institute of Informatics (NII) works closely with Japanese industries. What's an example of an emerging industry where graph theory will play an especially important role?

One important area is next-generation communication and data infrastructure. NII operates SINET, Japan's academic network, which connects about 1,000 universities and research institutions through a nationwide 400-Gbps backbone. Although SINET serves academia, the underlying challenges are the same ones faced by telecommunications companies, cloud providers, and data-center operators.

Mathematically, the network is a graph: routers and sites are vertices, and communication links are edges with capacities, delays, costs, and reliability constraints. When data travels between institutions, the system must select routes that respect these constraints. When several routes are available, it must balance traffic so that no link becomes a bottleneck. It must also remain connected when equipment or links fail.

The 2011 Tohoku earthquake showed how important resilience is. A large-scale failure can remove several vertices or edges at once, so the network must detect vulnerable points and reroute traffic quickly. These are graph problems involving shortest paths, flows, cuts, connectivity, and optimization.

Graph algorithms therefore help make networks faster, more efficient, and more reliable. As 5G and future 6G systems, cloud services, AI data centers, and distributed scientific instruments continue to grow, graph theory will become even more important because the networks are larger, more dynamic, and more interconnected.