Electrical Laws Can Help Break Network Graph Comparison Bottleneck

Yiannis Koutis wants to know if a method inspired by electrical laws could lead to a faster and more insightful way of comparing seemingly disparate networks.

Koutis, an associate professor of computer science in NJIT's Ying Wu College of Computing, will study this question for his $150,000 research grant from the National Science Foundation program known as EAGER — EArly-concept Grants for Exploratory Research — which supports research that is unproven yet potentially transformative.

"Suppose one wants to understand the similarities between two, very large unknown networks from an application domain, such as brains networks, gene expression networks, or protein networks," Koutis stated in his grant summary. "There are two associated problems that are far from trivial: how to mathematically model similarity, and how to detect it in a reasonable amount of time, considering that the networks can have millions or billions of connections."

Existing approaches for quantifying network similarity may not only be inappropriate for many applications of naturally-occurring problems, but also face many barriers due to complexity. However, analogies with electrical networks might be more useful, and Koutis' expertise in spectral graph theory — the study of a network’s properties related to its adjacency matrix – describing the connections between entities in the network — offers the possibility of a more effective modeling that also yields faster and more robust methods.  

Asked for elaboration beyond the grant summary, "This is a generalization of a famous computational problem, known as graph isomorphism," Koutis observed. Graph isomorphism is the study of comparing graphs to each other.

"In the formulation we are exploring, we view both networks as electrical networks and we are looking for a mapping that renders the two networks electrically similar," Koutis said. “For instance, given the mapping, applying the same set of voltages on the two electrical networks will dissipate a similar amount of energy on both." 

He said that makes sense from an application point of view. For example, "when two chemical networks behave the same way electrically given a mapping, maybe that is the correct mapping that you're trying to find... The hope is by following a different definition from a different application domain, you will have better outputs."

Koutis, who joined NJIT in 2017, said he and his team are in the early stages of the research. He hopes to have good results by May 2021. "It's a clearly open question. It just emerged through talks and discussions over the years," he said.

There are no promises being made, as happens in the EAGER program. "This work may be considered especially 'high risk, high payoff'," the NSF notes on its website, "in the sense that it, for example, involves radically different approaches, applies new expertise, or engages novel disciplinary or interdisciplinary perspectives."