On the Properties of Gromov Matrices and Their Applications in Network Inference

Feng Ji, Wenchang Tang, Wee Peng TayIEEE TSP 2019 · DOI · OpenReview

Introduction: The Challenge of Network Inference

In the field of network science, many critical inference problems—such as identifying the origin of a viral rumor, tracing the source of an infection, or optimizing data center placement—are computationally "intractable" on general, dense graphs. However, these same problems often become mathematically "tractable" when the underlying structure is a tree.

To bridge this gap, researchers traditionally rely on the spanning tree heuristic. This approach involves selecting a single random spanning tree (often a Breadth-First Search or BFS tree) from the graph and applying tree-based algorithms to it. While convenient, this method is fundamentally flawed for dense networks. A single spanning tree captures only a fraction of the structural context; it is akin to trying to understand a city's entire traffic flow by observing a single bus route. This paper introduces Gromov matrices as a solution, providing a continuous algebraic space to represent and interpolate between a vast family of trees.

Beyond the Spanning Tree Heuristic

The primary limitation of the spanning tree heuristic is the loss of geometric information. As illustrated in the comparison between a general graph $G$ and various spanning trees, the choice of tree significantly alters the perceived distance and connectivity between nodes.

A comparison of a graph G and its various spanning trees (T, T1, T2), highlighting how different trees represent the same underlying topology.

Instead of treating trees as discrete combinatorial objects, the authors propose representing them as Gromov matrices. For a tree rooted at a base node $s$, the Gromov product of two nodes $u$ and $v$ measures the length of the shared path from $s$ to both nodes. A Gromov matrix $M$ stores these products for all pairs of nodes. By satisfying a specific "three-point condition," these matrices can uniquely represent valid weighted trees.

G-Convex Combinations: Interpolating Tree Structures

The core innovation of this research is the development of G-convex combinations. Standard linear averaging of two Gromov matrices typically results in a matrix that no longer represents a valid tree. The authors developed a "Gromovied" adjustment procedure that takes a weighted average and "nudges" it back into the space of valid trees.

Visual representation of G-convex interpolation between two tree structures (a) and (b), showing how branching points like p shift to accommodate different path lengths.

This geometric interpolation essentially re-scales edge weights and repositions branching points. As shown in the figure above, the transition between tree (a) and tree (b) allows the model to approximate the "true" propagation path more closely than any single static spanning tree could. This allows researchers to "slide" between different tree structures to find an optimal fit for the observed data.

Key Results and Experimental Validation

The authors validated this framework using both synthetic (Erdős-Rényi, Barabási-Albert) and real-world datasets, including the Enron Email Network and Facebook social graphs. The results demonstrate significant performance gains over traditional heuristics:

  • Information Acquisition Order: The Gromov method achieved 91.1% to 95.3% accuracy in estimating whether a node lies on the path between a source and a target, using only a small set of synthesized trees.
  • Source Identification: In complex networks, the method showed a Detection Improvement of up to 73.7% over the standard BFS tree heuristic, consistently placing the true source within the top 20% of candidates.
  • Data Center Placement: When optimizing for service latency, the Gromov-enhanced approach consistently outperformed standard greedy algorithms across all tested network sizes.

Conclusion and Future Directions

Gromov matrices transform tree-based inference from a discrete search problem into a continuous optimization task. While highly effective, the authors note that the synthesized G-convex trees are "virtual"—their edges may not always exist in the original graph $G$, serving instead as a geometric approximation.

Future work remains in refining the initial selection of "base" trees and optimizing the $O(n^3)$ computational complexity required to reconstruct adjacency matrices for million-node networks. Nonetheless, this algebraic framework provides a powerful new lens for understanding the hidden tree-like structures within complex systems.

Summary updated

Abstract

The spanning tree heuristic is a commonly adopted procedure in network inference and estimation. It allows one to generalize an inference method developed for trees, which is usually based on a statistically rigorous approach, to a heuristic procedure for general graphs by (usually randomly) choosing a spanning tree in the graph to apply the approach developed for trees. However, there are an intractable number of spanning trees in a dense graph. In this paper, we represent a weighted tree with a matrix, which we call a Gromov matrix. We propose a method that constructs a family of Gromov matrices using convex combinations, which can be used for inference and estimation instead of a randomly selected spanning tree. This procedure increases the size of the candidate set and hence enhances the performance of the classical spanning tree heuristic. On the other hand, our new scheme is based on simple algebraic constructions using matrices, and hence is still computationally tractable. We discuss some applications on network inference and estimation to demonstrate the usefulness of the proposed method.
BibTeX
@article{ji2019properties,
  author = {Feng Ji and Wenchang Tang and Wee Peng Tay},
  title = {{On the Properties of Gromov Matrices and Their Applications in Network Inference}},
  journal = {IEEE Trans. Signal Process.},
  year = {2019},
  doi = {10.1109/tsp.2019.2908133},
}
Figure