Skip to content

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

1 watching

Forks

Latest commit

 

History

2 Commits

Folders and files

NameName
Last commit message
Last commit date
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Structural Data Analysis for Bigraphs

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.

Features

  • 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.

Installation

Requirements

  • Java 21 or later
  • Maven

Maven Dependency

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>

Gradle Dependency

For a Gradle project, add the dependency to your build.gradle:

dependencies {
    implementation 'org.bigraphs.model.analysis:structural-data-analysis:1.0.0'
}

Quick Start

The following examples assume that bigraphA and bigraphB are valid PureBigraph instances created using the Bigraph Framework.

Compute WL Color Refinement

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 WL Graph Kernel

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.

Check Bigraph Isomorphism

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.

License

This project is licensed under the Apache License, Version 2.0. See the LICENSE file for the full license text.

References

  1. 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.
  2. 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.
  3. Babai, L., and Kucera, L. (1979). Canonical Labelling of Graphs in Linear Average Time.
  4. Rieck, B., Bock, C., and Borgwardt, K. (2019). A Persistent Weisfeiler-Lehman Procedure for Graph Classification.

About

No description, website, or topics provided.

Resources

Stars

0 stars

Watchers

1 watching

Forks

Releases

Packages

Contributors

Languages