FilterEngine Class Reference

Iterative orbit filtering (Algorithm 1 of the paper, IterOrbitFilter). More...

#include <FilterEngine.h>

Collaboration diagram for FilterEngine:

Classes
struct	OwnedCGraph
	A graph in CSR form that owns its arrays; view points into them. More...

Public Member Functions
	FilterEngine (const AppGraph &data, const AppGraph &pattern, int g_size, bool use_full_graph_mode, int max_iters=1, bool print_stats=true, bool enable_orbit_throttle=false, double orbit_throttle_threshold=0.05, bool enable_semi_join=true, bool arc_consistency=true, bool enable_orbit_filter=true, bool post_orbit_induction=true, bool edge_thinning=false)
bool	run ()
	Runs the filter.
const CandidateSets &	getCandidateSets () const
	The candidate sets after run().
const OrbitCounts &	getPatternOrbits () const
	Orbit counts of the pattern, indexed by the pattern's internal index.
const AppGraph &	getCandidateSubgraph () const
	The data graph induced on the final candidates (the whole data graph in full-graph mode).
void	countCandidates (const std::string &filter_step_name) const
	Prints size statistics of the current candidate sets under the given heading (only when statistics are enabled).

Private Member Functions
bool	ldfNlfFilter (size_t &ldf_only_count)
	LDF, and round 1's NLF on the full data graph, in one pass.
bool	nlfFilter (const AppGraph &neighbor_graph)
	NLF against neighbor_graph: keeps v in C(u) only if v's neighbours there cover the label multiset of u's pattern neighbours.
bool	semiJoinFilter (const AppGraph &neighbor_graph)
	Semi-join against neighbor_graph, to arc consistency unless disabled.
bool	arcConsistencyFilter (const AppGraph &neighbor_graph)
bool	orbitFilter ()
	Induces the candidate subgraph, counts its orbits and keeps v in C(u) only if every orbit count of v is at least that of u.
void	induceCandidateSubgraph ()
	Sets candidate_subgraph to the data graph induced on the union of the candidate sets.
void	thinEdges (const AppGraph &g, OwnedCGraph &out) const
	g without the edges no pattern edge can map to (see edge_thinning): same vertices and internal indices, fewer edges.
size_t	getCandidateCount () const
	Total number of candidates over all pattern vertices.

Private Attributes
const AppGraph &	data_graph
const AppGraph &	pattern_graph
int	graphlet_size
bool	use_subgraph
int	max_iterations
bool	print_stats
bool	enable_orbit_throttle
double	orbit_throttle_threshold
bool	enable_semi_join
bool	arc_consistency
bool	enable_orbit_filter
bool	post_orbit_induction
bool	edge_thinning
CandidateSets	candidate_sets
OrbitCounts	pattern_orbits
std::vector< bool >	needed_orbits
	Orbits some pattern vertex has; the data graph's other orbits are not counted.
std::unordered_map< int, std::unordered_map< int, int > >	pattern_nlf
	Per pattern node ID: label -> number of pattern neighbours with that label.
int	max_data_label = 0
AppGraph	candidate_subgraph
size_t	subgraph_candidate_count = SIZE_MAX
	Candidate count when candidate_subgraph was last induced (SIZE_MAX: not yet).

Detailed Description

Iterative orbit filtering (Algorithm 1 of the paper, IterOrbitFilter).

Starting from the label-and-degree filter (LDF), each round applies the neighbourhood label filter (NLF) and the semi-join (to arc consistency), induces the data graph on the surviving candidates, applies the orbit filter on that graph, and induces the data graph again on its survivors for the next round. Candidate sets only ever shrink, and no round removes the image of an embedding.

Constructor & Destructor Documentation

FilterEngine()

FilterEngine::FilterEngine	(	const AppGraph &	data,
		const AppGraph &	pattern,
		int	g_size,
		bool	use_full_graph_mode,
		int	max_iters = 1,
		bool	print_stats = true,
		bool	enable_orbit_throttle = false,
		double	orbit_throttle_threshold = 0.05,
		bool	enable_semi_join = true,
		bool	arc_consistency = true,
		bool	enable_orbit_filter = true,
		bool	post_orbit_induction = true,
		bool	edge_thinning = false
	)

Parameters

data	the data graph G_d
pattern	the pattern graph G_p
g_size	graphlet size for orbit counting: 3, 4 or 5
use_full_graph_mode	count orbits on G_d instead of the candidate-induced subgraph; forces a single round
max_iters	I_max: the maximum number of rounds; 0 iterates until a round removes no candidate
print_stats	print candidate statistics and timings after each stage
enable_orbit_throttle	skip the orbit stage in rounds where the cheaper filters are still removing candidates but the sets have shrunk by less than orbit_throttle_threshold since it last ran; it always runs once more before returning
orbit_throttle_threshold	that fraction
enable_semi_join	run the semi-join stage
arc_consistency	iterate the semi-join until it removes nothing (default); false: one pass per round
enable_orbit_filter	run the orbit stage; false leaves contraction with NLF and the semi-join only (ablation)
post_orbit_induction	induce the data graph again after the orbit stage; false: the next round's NLF and semi-join read the graph the orbit stage counted on
edge_thinning	count orbits on the candidate subgraph without the edges no pattern edge can map to (no pattern edge {u, u'} with one end a candidate of u and the other of u'); an embedding uses none of them, so each of its graphlets is still counted at its image

Member Function Documentation

arcConsistencyFilter()

bool FilterEngine::arcConsistencyFilter ( const AppGraph &  neighbor_graph )

private

countCandidates()

void FilterEngine::countCandidates

(

const std::string &

filter_step_name

)

const

Prints size statistics of the current candidate sets under the given heading (only when statistics are enabled).

getCandidateCount()

size_t FilterEngine::getCandidateCount ( ) const

private

Total number of candidates over all pattern vertices.

getCandidateSets()

const CandidateSets & FilterEngine::getCandidateSets ( ) const

inline

The candidate sets after run().

getCandidateSubgraph()

const AppGraph & FilterEngine::getCandidateSubgraph ( ) const

inline

The data graph induced on the final candidates (the whole data graph in full-graph mode).

It contains the image of every embedding; the search runs on it.

getPatternOrbits()

const OrbitCounts & FilterEngine::getPatternOrbits ( ) const

inline

Orbit counts of the pattern, indexed by the pattern's internal index.

induceCandidateSubgraph()

void FilterEngine::induceCandidateSubgraph ( )

private

Sets candidate_subgraph to the data graph induced on the union of the candidate sets.

ldfNlfFilter()

bool FilterEngine::ldfNlfFilter ( size_t &  ldf_only_count )

private

LDF, and round 1's NLF on the full data graph, in one pass.

Sets ldf_only_count to the number of candidates LDF alone leaves. Returns false if a set is empty.

nlfFilter()

bool FilterEngine::nlfFilter ( const AppGraph &  neighbor_graph )

private

NLF against neighbor_graph: keeps v in C(u) only if v's neighbours there cover the label multiset of u's pattern neighbours.

Returns false if a set becomes empty.

orbitFilter()

bool FilterEngine::orbitFilter ( )

private

Induces the candidate subgraph, counts its orbits and keeps v in C(u) only if every orbit count of v is at least that of u.

Returns false if a set becomes empty.

run()

bool FilterEngine::run

(

)

Runs the filter.

Returns false if some candidate set becomes empty, in which case the pattern has no embedding in the data graph.

semiJoinFilter()

bool FilterEngine::semiJoinFilter ( const AppGraph &  neighbor_graph )

private

Semi-join against neighbor_graph, to arc consistency unless disabled.

thinEdges()

void FilterEngine::thinEdges ( const AppGraph &  g, OwnedCGraph &  out  ) const

private

g without the edges no pattern edge can map to (see edge_thinning): same vertices and internal indices, fewer edges.

Member Data Documentation

arc_consistency

bool FilterEngine::arc_consistency

private

candidate_sets

CandidateSets FilterEngine::candidate_sets

private

candidate_subgraph

AppGraph FilterEngine::candidate_subgraph

private

data_graph

const AppGraph& FilterEngine::data_graph

private

edge_thinning

bool FilterEngine::edge_thinning

private

enable_orbit_filter

bool FilterEngine::enable_orbit_filter

private

enable_orbit_throttle

bool FilterEngine::enable_orbit_throttle

private

enable_semi_join

bool FilterEngine::enable_semi_join

private

graphlet_size

int FilterEngine::graphlet_size

private

max_data_label

int FilterEngine::max_data_label = 0

private

max_iterations

int FilterEngine::max_iterations

private

needed_orbits

std::vector<bool> FilterEngine::needed_orbits

private

Orbits some pattern vertex has; the data graph's other orbits are not counted.

orbit_throttle_threshold

double FilterEngine::orbit_throttle_threshold

private

pattern_graph

const AppGraph& FilterEngine::pattern_graph

private

pattern_nlf

std::unordered_map<int, std::unordered_map<int, int> > FilterEngine::pattern_nlf

private

Per pattern node ID: label -> number of pattern neighbours with that label.

pattern_orbits

OrbitCounts FilterEngine::pattern_orbits

private

post_orbit_induction

bool FilterEngine::post_orbit_induction

private

print_stats

bool FilterEngine::print_stats

private

subgraph_candidate_count

size_t FilterEngine::subgraph_candidate_count = SIZE_MAX

private

Candidate count when candidate_subgraph was last induced (SIZE_MAX: not yet).

Candidate sets only shrink, so an equal count means the same sets and the same graph.

use_subgraph

bool FilterEngine::use_subgraph

private

---

The documentation for this class was generated from the following files:

• include/FilterEngine.h
• src/FilterEngine.cpp