1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
|
#+TITLE: Plan for querying
#+AUTHOR: बुबोधयिषुः
#+DATE: <2024-01-11 Jeu 11:40>
* Basic plan
Basically speaking, we are trying to solve a subgraph isomorphism
problem, but for parse forests only. Moreover, each pattern node
specifies some condition that the target node should satisfy, like the
rule number, the grammar node number et cetera. This simply acts like
the filtering algorithms employed by the general subgraph isomorphism
algorithms.
There is however one difference from the original problem:
#+begin_quote
Edges might be matched by paths.
#+end_quote
This means that some edges in the pattern graph could be matched by
paths in the (directed) target graph. Moreover, some edges require to
be siblings of some previously matched edges. This poses some
traditionally missing contraints.
But anyways, we can consult the backtracing algorithms that were
written for the general problem to have an idea how to solve our
specific variant of the problem.
** Filtering
Our pattern nodes already specify some conditions for the target nodes
to match. So it is worth condidering whether or not we employ some
more powerful filtering techniques, like the iterative strenghthening
of the subgraph-isomorphism-compatible-labels algorithm. This can be
simply adapted to our situation since we have a natural candidate for
the labels: the pattern nodes have the matching conditions as labels,
whereas the target nodes have labels that are either grammar nodes or
rule numbers. We can define a partial order on this set of labels by
requiring that a matching condition is less than or equal to a target
label if and only if that target label satisfies the matching
condition.
Then we simply apply the iterative strenghthening procedure, by
forming, from the label \(L\), the new label \(L\times N(L)\), where
\(N(L)\) is the function that sends each node \(n\) to the /multiset/
\(\{L(m) \mid \text{Adj}(m, n)\}\), where \(\text{Adj}\) means that
the two nodes are adjacent. And we say that a multiset \(m_1\) is less
than or equal to another multiset \(m_2\) if and only if the bipartite
graph formed from these two multisets have a matching covering every
vertex corresponding to elements in \(m_1\). Note that this bipartite
graph has as nodes \(N_x^i\) for every \(x\in m_1\), where \(i = 0, \ldots,
m_1(x)\) and \(m_1(x)\) is the multiplicity of \(x\) in \(m_1\). Also
two nodes \(N_x^i\) and \(N_y^j\), where \(x\in m_1\) and \(y\in m_2\) are
adjacent if and only if \(x\leq y\). We can prove that if \(L\) is
subgraph-isomorphism-compatible, then this new label \(L\times N(L)\) is
also subgraph-isomorphism-compatible.
As a consequence, we can iteratively construct new labels to filter
out wrong candidate pairs of pattern nodes and target nodes, until
this procedure does not yield stronger labels, which are guaranteed to
happen in polynomial time.
** General sketch
Since our starting label is already domain-specific, it might be
anticipated that this procedure can enhance the performance of the
algorithm a lot. This is the general sketch of the algorithm.
* Two difficulties
** When a branch is exhausted, how should we switch to another branch?
To solve this issue, we need a data type with the following methods:
- Follow nodes in the depth-first order
- Enumerate and switch to a specific "world line" in the forest: that
is, a forest is a pack of trees, and we match against each tree
separately; when a tree cannot be matched, we switch to the next
tree.
All of this should be implemented efficiently, that is, within a
constant and "small" amount of operations.
For now, the plan is to preprocess the forest to store the information
about each packed node in advance, and then the world line is defined
by which child of those packed nodes to use. Thus to switch world
line, we just change an array of numbers, which is pretty efficient I
suppose.
** When a query cannot be matched, how should we fallback to a parent query?
To solve this issue, we need a data type with the following methods:
- Follow nodes in the depth-first order
- Jump to the parent and restore the querying context that was stored
earlier.
We can consult the codes for general subgraph isomorphism problems
to implement this, since the general structure is the same.
* Steps [1/4]
** TO-THINK Preprocess the target graph
The target needs to be preprocessed so that we know about the world
lines in advance, and we can generate some supplemental graphs as well
to facilitate the search.
This may not be required anymore.
** SOLVED Backtrack based on domains
We need to keep track of the domains. Can we find better ways to do
this?
Maybe we can keep track of only the differences of the set of domains,
where each domain is a bitset. For the functionality of bit-sets,
[[https://docs.rs/bitset-core/latest/bitset_core/index.html][this crate]] is quite useful.
Since this is an external crate, we may treat this feature as an
optionally enabled feature, and by default we use ordinary arrays of
booleans. The main advantage, in my opinion, provided by the external
crate is its SIMD-awareness, so the default implementation should not
lose exponential performance.
A more serious problem is how to handle the packed nodes, or
equivalently how to treat different trees packed inside a forest.
Previously I was thinking of searching each packed tree separately,
but this is not respecting the shared structures of these trees, so
that we must waste a lot of efforts to search the same portions
multiple times.
A better approach could be to ignore all children of packed nodes, and
treat the grand-chidlren of the packed nodes as their own children.
This way we do not need to waste efforts, and we need no special
treatment of different world-lines when searching.
Here is a more formal description of the approach.
- For each pattern vertex, associate a vector of target vertices,
initialized as a vector of vertices with the same boolean true
label of length the number of nodes of the target graph.
- Repeat the following steps.
- Find a pattern vertex with the smallest domain, tiebreaking by
randomly choosing one with the higher degree, excluding vertices
whose domains are either empty or singleton.
+ If there is a vertex with empty domain, the pattern graph is not a
subgraph of the target graph.
+ If every vertex has a singleton domain, return the found mapping.
- Find a "suitable" target vertex with highest degree within the
domain of the chosen vertex.
+ If none exists, then we go back to the previous association of
some target vertex to some pattern vertex, and exclude that target
vertex from the domain of that pattern vertex, and then repeat the
process again.
* If no previous association exists, this means we happen to
choose one pattern vertex that cannot be mapped to the target
graph at the first step, so we can simply stop the algorithm and
decide that the pattern graph is not a subgraph of the target
graph.
- Record the mapping from the above pattern to the above target in the
list of associations, and filter other domains.
+ We can filter by the degree.
+ We can filter by the sequence of degrees of neighbors.
** TODO Rapid restarts and no-good recording
This is a highly important optional improvement.
** TODO Connect with the rest of the package
Now we want to connect the subgraph isomorphism solver with the rest
of the package. This requires a mechanism to convert from user-input
to a pattern graph, and then run the subgraph (isomorphism) solver to
find a mapping from the pattern graph to the parse-graph.
In addition, there are some other constraints that might be imposed by
the user, such as to require that certain edges be siblings, or that
certain edges be non-repeating (either for nodes or for edges) paths
instead of plain edges.
All these can be implemented at the filtering step as additional
requirements other than the neighbourhood-preserving constraint.
Also the user may expect the neighbour relation to be directed. I am
not sure if this causes any trouble, but I need to deal with this
correctly to avoid potential disasters.
|
