# An Interpretable Fake News Detection Method Based on Commonsense Knowledge Graph
## 4 Fake News Identification Based on Random Walk Graph Matching
### Principle of Random Wandering Graph Matching Algorithm  
Graph matching refers to using the similarity information of the graph structure to find node matching (first-order matching) relationships or edge matching (second-order matching) relationships between graph structures (as shown in Figure 9, nodes of the same color indicate matching nodes. ), which involves graph matching research in different fields such as computer vision and pattern recognition [31]. Figure 8: Knowledge extraction process based on UIE framework. Because edges also contain information in knowledge graphs, this project needs to consider both node matching and edge matching for graph matching. The similarity matrix, W, is used to represent the matching relationship. The similarity matrix, W, contains both first-order node similarity information and second-order edge similarity information, as follows:  
\[\text{W}= \begin{bmatrix}w_{a_{1}b_{1}a_{1}b_{1}}&w_{a_{1}b_{1}a_{1}b_{2}}& \cdots\\ w_{a_{1}b_{2}a_{1}b_{1}}&w_{a_{1}b_{2}a_{1}b_{2}}&\cdots\\ \vdots&\vdots&\ddots\end{bmatrix} \]  
In the problem shown in Figure 8, the scale of the similarity matrix is 16\(\times\)16. The diagonal elements of the similarity matrix contain node-to-node similarity information, such as \(w_{a_{1}b_{1}a_{1}b_{1}}\), represents the similarity between node \(a_{i}\) in graph a and node \(b_{k}\) in graph \((b)\). Non-diagonal elements contain edge-to-edge similarity information, such as \(w_{a_{1}b_{1}a_{1}b_{1}}\), which represents the similarity between the edge composed of nodes \(a_{i}\) and \(a_{j}\) in graph a and the edge composed of nodes \(b_{k}\) and \(b_{l}\) in graph \((b)\). Based on the similarity matrix, \(W\), and match matrix, \(X\),the problem of the graph match can be modeled as:  
\[x^{*}=arg\,max\left(x^{T}Wx\right)\,\text{s.t.}\,\,x\in\left[0,1\right]^{n^{p} n^{Q}} \tag{11}\]  
to calculate the match result that maximizes the similarity. Mathematically, formula (11) is an NP-hard quadratic assignment problem, which cannot find a global optimal solution within polynomial time. Random walk [32; 33] is an efficient approximation algorithm for graph matching. The random walk algorithm constructs several random walkers. The random walker is initialized from a certain node, and then randomly visits an adjacent node of the current node in each random walk step. There are two graphs waiting for matching in a problem of a graph match, but random walk only performs on a single one. Therefore, the graph matching problem has to be transformed into the form of a single graph-accompaniment graph in order to apply the random walk algorithm to the graph matching problem. As shown in Figure 10, consider the case of two nodes (1, 2) matching three nodes (a, b, c). The two graph structures in (a) represent the original graph matching problem. The diagram in (b) is the accompanying diagram. In the graph matching problem, the node-to-node correspondence (orange dashed double arrows) translates to the nodes in the accompanying diagram; for example, the matching relationship between node 1 and node \(a\) is transformed into node \(1a\) in the accompanying graph. The similarity information between sides (blue dashed double arrows) is transformed into edges in the accompanying graph; for example, the similarity between edge 12 and edge ab is transformed into the right edge 1a-2b in the accompanying graph. The concomitant graph is an undirected weight graph, but, in this project, it is designed as a directed graph because the knowledge graph data has the distinction between entities and attributes. With the random walk algorithm, weights can be computed for each node of the accompanying graph. The graph matching problem is then transformed into the problem of finding the number of nodes with the maximum weight in the accompanying graph [9]. Figure 9: Graph matching schematic. To facilitate uniform processing, absorbing nodes are added to the accompanying graph so that the out-degree of all the other nodes is equal.