Abstract
We discuss the problem of extending data mining approaches to cases in which data points arise in the form of individual graphs. Being able to find the intrinsic low-dimensionality in ensembles of graphs can be useful in a variety of modeling contexts, especially when coarse-graining the detailed graph information is of interest. One of the main challenges in mining graph data is the definition of a suitable pairwise similarity metric in the space of graphs. We explore two practical solutions to solving this problem: one based on finding subgraph densities, and one using spectral information. The approach is illustrated on three test data sets (ensembles of graphs); two of these are obtained from standard graph generating algorithms, while the graphs in the third example are sampled as dynamic snapshots from an evolving network simulation. We further incorporate these approaches with equation free techniques, demonstrating how such data mining approaches can enhance scientific computation of network evolution dynamics.
Introduction
Traditional data mining tools, such as Principal Component Analysis (PCA) or Diffusion Maps (DMAPs), are typically designed for data points residing in Euclidean space—essentially, vectors of numerical values. However, in many modern scientific applications, data often arrives as a collection of networks or graphs. These objects are inherently difficult to compare because they lack a natural coordinate system; simple subtraction is not defined, and comparing them directly is computationally intensive (the graph isomorphism problem). This research addresses the fundamental challenge: how to define a mathematically sound and computationally efficient similarity metric between graphs to treat them as points in a high-dimensional space.
Methodology
The core of the proposed framework is the use of Diffusion Maps to perform non-linear dimensionality reduction on graph ensembles. The authors propose two distinct metrics to quantify the similarity between any two graphs:
The Subgraph Density Approach
This method characterizes a large graph by the frequency of small patterns, or motifs, contained within it. If two large graphs share similar densities of these fundamental building blocks, they are considered close in the data space.
The Spectral Approach
This novel method utilizes "non-conservative diffusion." By simulating random walkers on a graph where the total number of walkers can change based on edge weights, a unique "spectral signature" is generated. Comparing these signatures provides a fast, motif-independent way to measure similarity.
Equation-Free Integration
The discovered coordinates are further integrated into an Equation-Free (EF) framework. Specifically, Coarse-Projective Integration (CPI) is used to accelerate network evolution simulations. By using the data-mined coordinates as "coarse variables," the system can "jump" forward in time, skipping many fine-grained simulation steps.
Experimental Evaluation
The approach was evaluated on three distinct graph ensembles:
- Erdős-Rényi Graphs: A random graph model defined by a single connection probability parameter $p$.
- Chung-Lu Graphs: A two-parameter family ($p$ and $r$) allowing for controlled skewness in degree distribution.
- Dynamic Evolution Model: Temporal snapshots of a network evolving toward a steady state based on specific edge-addition rules.
Key Results and Insights
The framework successfully identified the intrinsic dimensionality of the test sets. For Erdős-Rényi graphs, the Diffusion Map independently rediscovered the parameter $p$. For Chung-Lu graphs, it recovered both $p$ and $r$. This "independent rediscovery" confirms that the mapping can uncover the hidden parameters governing complex graph ensembles without prior knowledge of the underlying math.
In dynamic simulations, the CPI approach successfully predicted long-term evolution while skipping 50% of the fine-grained steps. Furthermore, the spectral approach was found to be significantly faster than subgraph counting, particularly as graph size or motif complexity increased.
Conclusion
This work demonstrates that non-linear data mining can be effectively extended to graph-based datasets. By defining appropriate similarity metrics, researchers can "unwrap" complex network data into simple, low-dimensional manifolds. While challenges remain in hyperparameter tuning and scaling to varying node counts, this framework provides a powerful tool for discovering the laws governing network evolution and for accelerating large-scale scientific computations.
Summary updated