TL;DR
This paper introduces the Wasserstein Weisfeiler-Lehman Subtree (WWLS) distance, a novel graph metric that refines the Weisfeiler-Lehman (WL) test's approach to graph similarity. By leveraging WL subtrees and approximating tree edit distance with a Wasserstein distance framework, WWLS can capture finer structural differences than existing WL-based methods, leading to improved performance in metric validation and graph classification tasks.
What Problem Does This Paper Address?
Graph similarity and distance metrics are crucial for various applications, from recommendation systems to drug discovery. Traditional graph edit distance (GED) is computationally expensive. While graph kernels and neural networks have advanced graph analysis, many existing methods, particularly those based on the Weisfeiler-Lehman (WL) test, struggle to capture subtle structural differences. The WL test, while effective for graph isomorphism, aggregates node information into a single hash, losing crucial details about inter-node connections. This coarseness limits the ability of WL-based kernels and distances to precisely measure graph similarity, especially when dealing with graphs that are not drastically different. This paper aims to address this limitation by developing a more sensitive graph metric.
Methods
The core of this paper is the Wasserstein Weisfeiler-Lehman Subtree (WWLS) distance. The authors build upon the Weisfeiler-Lehman (WL) subtree, which represents a node and its neighborhood structure.
Here's a breakdown of their approach:
- WL Subtree as Structural Information: Instead of just using the hash output of the WL test, the paper treats the WL subtree itself as rich structural information for a node's neighborhood.
- L1-Approximated Tree Edit Distance (L1-TED): To measure the difference between two WL subtrees (rooted at nodes in different graphs), they employ an L1-approximated Tree Edit Distance. This is a computationally more tractable alternative to the exact Tree Edit Distance, which is NP-hard. They define a feature vector for each WL subtree based on the counts of different "complete subtrees" within it.
- Wasserstein Distance Framework: The L1-TED is then used as the ground distance within the Wasserstein distance framework. This allows them to compute a graph-level distance by finding the optimal transport plan between the distributions of node-level distances (L1-TED between WL subtrees) in two graphs.
- Efficient Tree Hashing: To efficiently compute the L1-TED, they develop a tree hash function. This function maps complete subtrees to polynomial representations, and then to integer hash values. Theoretical guarantees are provided for the low probability of hash collisions.
Datasets
The paper evaluates their proposed WWLS distance on several datasets:
- Metric Validation Experiments:
- Random graphs
- Cycle graphs
- Grid graphs
- Graph Classification Experiments:
- Bioinformatics Datasets: MUTAG, PTC-MR, COX2, ENZYMES, PROTEINS, NCI1, BZR.
- Social Network Datasets: IMDB-B, IMDB-M, COLLAB.
The paper notes that the GIN (Graph Isomorphism Network) baseline was not evaluated on all datasets due to its original paper's limitations.
Key Insights and Ideas
- WL Subtree is Richer Than its Hash: The WL test's power lies in its ability to capture graph structure, but its aggregation into a single hash discards valuable information. The paper demonstrates that the WL subtree itself, when treated as a structured object, holds more discriminative power.
- L1-TED as a Bridge: Approximating Tree Edit Distance with L1-norm offers a practical way to quantify differences between WL subtrees, making it suitable for integration into broader distance metrics.
- Wasserstein Distance for Graph-Level Sensitivity: Applying the Wasserstein distance at the graph level, using node-level WL subtree distances, allows for a more nuanced comparison of overall graph structures, capturing subtle differences that might be missed by simpler aggregation methods.
- Structural Information Improves Classification: Even with the same underlying expressive power as the WL test, incorporating richer structural information (WL subtrees) leads to improved performance in graph classification. This suggests that how information is represented and compared is as crucial as the information itself.
Key Results
- Metric Validation: WWLS showed a smoother and more gradual increase in distance values with increasing edge noise compared to WWL and Gromov-Wasserstein (GW) distances. This indicates WWLS is less sensitive to minor structural changes and better reflects gradual degradation of graph structure.
- Graph Classification: WWLS achieved competitive or superior accuracy compared to baselines (WL, WL-OA, WWL, GIN) on most datasets. It outperformed other methods on several bioinformatics and social network datasets, demonstrating its effectiveness in distinguishing between graph structures for classification.
- Runtime: While WWLS is slower than the WWL distance, the difference is reported to be within acceptable limits, suggesting a practical trade-off for improved accuracy.
Limitations and Future Work
- Computational Cost: The WWLS distance is computationally more expensive than the WWL distance, especially as the number of iterations (h) increases. The paper notes that the complexity is exponential in h.
- Parameter Sensitivity: The performance of WWLS, like many graph metrics, can be sensitive to parameter choices (e.g., the number of WL iterations 'h' and the SVM parameter 'γ').
- Future Work: The authors suggest exploring the application of this idea to Graph Neural Networks (GNNs), drawing a parallel between the WL test and GNN mechanisms. They believe similar improvements in expressive power and classification accuracy could be achieved for GNNs by incorporating richer structural information.
Summary updated