This project provides a Java library for applying graph-based analysis, kernel methods, and topological data analysis (TDA) techniques to bigraphs and bigraphical reactive systems.
The library provides algorithms for analysing the structural properties of bigraphs, comparing their representations, and assessing structural similarity. It currently includes one-dimensional Weisfeiler–Lehman (1-WL) color refinement, WL subtree graph kernels, and refinement-based isomorphism checking for place graphs, link graphs, and bigraphs.
- 1-WL Color Refinement: Compute iterative color refinements and feature vectors for place graphs and link graphs.
- WL Subtree Graph Kernel: Compare bigraphs using feature histograms generated by successive WL refinement iterations.
- Isomorphism Checking: Compare place graphs, link graphs, or complete bigraphs using the 1-WL-based
BWLIsomorphismChecker.
- Java 21 or later
- Maven
Add the library to your project's pom.xml:
<dependency>
<groupId>org.bigraphs.model.analysis</groupId>
<artifactId>structural-data-analysis</artifactId>
<version>1.0.0</version>
</dependency>For a Gradle project, add the dependency to your build.gradle:
dependencies {
implementation 'org.bigraphs.model.analysis:structural-data-analysis:1.0.0'
}The following examples assume that bigraphA and bigraphB are valid PureBigraph instances created using the Bigraph Framework.
Compute the WL refinement of a place graph and retrieve its feature vector at the stabilization iteration:
import org.bigraphs.analysis.tda.wl.AbstractWLColorRefinementProcedure;
import org.bigraphs.analysis.tda.wl.impl.PlaceGraphWLColorRefinementImpl;
import org.bigraphs.framework.core.impl.pure.PureBigraph;
PureBigraph bigraphA = /* construct or obtain a bigraph */;
PlaceGraphWLColorRefinementImpl wl =
new PlaceGraphWLColorRefinementImpl(bigraphA);
AbstractWLColorRefinementProcedure.WLResult result = wl.compute(10);
var stabilizedFeatures = result.featureVectorsByIteration()
.get(result.stabilizationIteration());For link-graph refinement, use LinkGraphWLColorRefinementImpl in the same way.
Compute the graph-kernel result for two bigraphs:
import org.bigraphs.analysis.tda.wl.WeisfeilerLehmanGraphKernel;
import org.bigraphs.framework.core.impl.pure.PureBigraph;
import org.ejml.simple.SimpleMatrix;
PureBigraph bigraphA = /* construct or obtain a bigraph */;
PureBigraph bigraphB = /* construct or obtain a bigraph */;
WeisfeilerLehmanGraphKernel kernel =
new WeisfeilerLehmanGraphKernel(bigraphA, bigraphB);
var result = kernel.computeGraphKernel(4);
SimpleMatrix placeGraphKernel =
result.getKernelMatrix().getLeft();
SimpleMatrix linkGraphKernel =
result.getKernelMatrix().getRight();The result provides separate kernel matrices for the place-graph and link-graph components.
Use BWLIsomorphismChecker to compare two bigraphs:
import org.bigraphs.analysis.tda.wl.BWLIsomorphismChecker;
import org.bigraphs.framework.core.impl.pure.PureBigraph;
PureBigraph bigraphA = /* construct or obtain a bigraph */;
PureBigraph bigraphB = /* construct or obtain a bigraph */;
BWLIsomorphismChecker checker =
new BWLIsomorphismChecker(bigraphA, bigraphB);
boolean placeGraphsAreIsomorphic = checker.isoCheckByPlaceGraph();
boolean linkGraphsAreIsomorphic = checker.isoCheckByLinkGraph();
boolean bigraphsAreIsomorphic = checker.isoCheck();Note: The checker is based on 1-WL color refinement, which is not a complete graph-isomorphism test. In particular, non-isomorphic structures can produce indistinguishable refinement results. Interpret its results accordingly when exact isomorphism guarantees are required.
This project is licensed under the Apache License, Version 2.0. See the LICENSE file for the full license text.
- Shervashidze, N., Schweitzer, P., van Leeuwen, E. J., Mehlhorn, K., and Borgwardt, K. (2011). Weisfeiler-Lehman Graph Kernels. Journal of Machine Learning Research, 12, 2539–2561.
- Kriege, N. M., Johansson, F. D., and Morris, C. (2020). A Survey on Graph Kernels. Applied Network Science, 5, 1–42. DOI: 10.1007/s41109-019-0195-3.
- Babai, L., and Kucera, L. (1979). Canonical Labelling of Graphs in Linear Average Time.
- Rieck, B., Bock, C., and Borgwardt, K. (2019). A Persistent Weisfeiler-Lehman Procedure for Graph Classification.