On the one hand, nowadays, fake news articles are easily propagated through various online media platforms and have become a grand threat to the trustworthiness of information. On the other hand, our understanding of the language of fake news is still minimal. Incorporating hierarchical discourse-level structure of fake and real news articles is one crucial step toward a better understanding of how these articles are structured. Nevertheless, this has rarely been investigated in the fake news detection domain and faces tremendous challenges. First, existing methods for capturing discourse-level structure rely on annotated corpora which are not available for fake news datasets. Second, how to extract out useful information from such discovered structures is another challenge. To address these challenges, we propose H ierarchical D iscourse-level S tructure for F ake news detection. HDSF learns and constructs a discourse-level structure for fake/real news articles in an automated and data-driven manner. Moreover, we identify insightful structure-related properties, which can explain the discovered structures and boost our understating of fake news. Conducted experiments show the effectiveness of the proposed approach. Further structural analysis suggests that real and fake news present substantial differences in the hierarchical discourse-level structures. In this work, we focus on detecting fake news articles (hereafter referred to as documents ) based on their contents. Many existing linguistic approaches for fake news detection (Feng et al., 2012; Pennebaker et al., 2015; Ott et al., 2011) overlook a crucial linguistic aspect of fake/real news documents i.e., the hierarchical discourse-level structure. Usually, in a document, discourse units (e.g., sentences) are organized in a hierarchical structure e.g., a tree. The importance of considering the hierarchical discourse-level structure for fake news detection is three-fold. First, previous studies (Bachenko et al., 2008; Rubin and Lukoianova, 2015) explored discourse-level structure in fake news detection and discovered that the way two discourse units of a document are connected could be quite revealing and insightful about its truthfulness. For instance, (Rubin and Lukoianova, 2015) applied Rhetorical Structure Theory (RST) (Mann and Thompson, 1988) and noted that fake stories lack evidence as a defined inter-discourse relation. Second, fake news is typically produced by connecting disjoint pieces of news and unlike well-established journalism (e.g., New York Times) fake news production lacks a meticulous editorial board. Therefore, by incorporating the hierarchical discourse-level structure, we can investigate the coherence of fake/real news documents (we will show this later). Third, a substantial number of studies have shown that using hierarchical structures yields a better document representation in various downstream tasks whose predictions depend on the entire text (Bhatia et al., 2015; Morey et al., 2018; Li et al., 2014b). Since typically fake news detection is considered as a classification problem based on the entire text, applying discourse analysis has the potential to advance fake news detection (this will be verified later). On the other hand, incorporating the hierarchical structure at the discourse level for fake news detection faces tremendous challenges. First, many existing methods incorporating structural discourse (Li et al., 2014a; Bhatia et al., 2015) (not for fake news detection though) rely on annotated corpora such as Penn Discourse Treebank ( Prasad et al., 2007). Constructing and annotating such corpora is an arduous and costly process. Incor-where G is a non-linear activation function, W is some weight matrix, b is a bias vector, and  denotes the dot product operator. Further, since we need a root node in a dependency tree, we compute the probability of a sentence s j being the root node, denoted as r j , as follows. where u j [ y ] is the y -th element of vector u j . Similarly, we calculate the root probabilities for all sentences and obtain the array of root probabilities denoted as r = { r 1 , r 2 ,    , r k } where 0  r j  r  1 . Construction We use the learned matrix of inter-sentential parent-child probabilities i.e., A (Eq. 3) as well as the array of root probabilities i.e., r (Eq. 4) and propose a greedy algorithm, illustrated in Algorithm 1, to construct the discourse dependency tree of a document. A sentence with the maximum value in r is considered the root node and is inserted into the tree (line 5). Then, at each iteration, the algorithm finds the maximum entry in a block of the matrix A whose rows correspond to the rows of current nodes added to the tree (i.e., nodes V in line 7) and its columns correspond to columns of the rest of nodes (i.e., nodes N \ V in line 7). Note that the columns of the current nodes are excluded because their parents have already been identified and also each node should have exactly one parent (except the root which has no parent). Assume the search in line 7 results in the entry ( p, c ) of A where 1  p, c  k and p 6 = c . Then, the sentence s c is added as the child node of the sentence s p (line 8). Algorithm 1 continues until all sentences of a document are added to the tree T . To fix the idea of discourse dependency tree construction algorithm, we present a step-by-step execution of this algorithm demonstrated in Figure 3. In Step 0, the sentence s 1 is added as the root of the tree T since it has the maximum value in the array of the root probabilities. Next in Step 1, the algorithm searches for the maximum probability value in the row s 1 while the column s 1 is excluded. The maximum value is this block is 0 . 4 and corresponds to entry ( s 1 , s 2 ). Therefore, the Algorithm 1: The proposed algorithm for discourse dependency tree construction Input: A ; r Output: Discourse dependency tree T 1 T = empty 2 N = { s 1 , s 2 ,    , s k } // All nodes 3 V = {} // Set of current nodes 4 Add N [ argmax ( r )] to V 5 T sentence s 2 is added as the child node of the sentence s 1 . In a similar fashion, the algorithm continues until all 6 sentences are added to the tree. We use a similar method presented in (Liu and Lapata, 2018) to extract a structurally rich representation for the entire document. First, for each sentence (i.e., a discourse unit), we obtain a structurally-aware representation. To achieve this, we take into account the parent-child probabilities as well as the root probabilities as follows. where p j and c j are two context vectors taking into account possible parents and children of a sentence s j , respectively, e root denotes a special root embedding vector, || denotes vector concatenation operator, and g j is a structurally-aware representation for sentence s j . Finally, to extract a structurally rich representation for the entire document. Recall that k is the total number of sentences in a document. The intuition behind defining Property 1 is as follows. According to the description of the dependency tree in Section 3.1, leaf nodes are isolated discourse units and no other discourse units depend on them. Thus, the more the number of leaf nodes is, the less inter-linked the discourse units will be, and vice versa. Therefore, Property 1 is likely to indicate the coherence of a document  the higher P l , the more isolated sentences and the less coherent the document. Also, for a document with k sentences P l  [ 1 log ( k ) , k  1 log ( k ) ] . Property 2 (Preorder Difference) This property, denoted as P t , defines the normalized positional difference between the preorder traversal of a document's discourse dependency tree and its original sentential sequential order: P t = P k j =1 | s position j  j | log ( k ) (9) where s positionj denotes the position of a sentence s j in the preorder traversal 1 of dependency tree of a document e.g., s position 3 = 4 in Figure 1. The position of s j in the original sequential order is simply j 2 . The preorder traversal of the tree in Figure 1 is the sequence { s 1 , s 2 , s 4 , s 3 , s 5 } and the sentential sequential order is { s 1 , s 2 , s 3 , s 4 , s 5 } . Therefore, according to the definition of Property 2: P t = | 1  1 | + | 2  2 | + | 4  3 | + | 3  4 | + | 5  5 | log (5)  2 . 86 . The preorder traversal of a document's discourse dependency tree takes into consideration the organization of a document respect to the dependencies between sentences. Then, the purpose of Property 2 is to measure how much the organization of a document, captured through the preorder traversal, deviates from its sentential sequential order. Sentence order is highly related to the coherence of a document where the displaced order of sentences in a document makes it less coherent (Li and Hovy, 2014). Thus, intuitively, the less the value of Property 2 for a document is, the more coherent that document should be. Also, for a document with k sentences P t  [ k  1 log ( k ) , ( k 2  1) 2 log ( k ) ] if k is odd and P t  [ k  1 log ( k ) , k 2 2 log ( k ) ] if k is even. Property 3 (Parent-Child Distance) This property, denoted as P c , defines the normalized sum of positional distances between child nodes and their parents when they are considered in the original sequential order: P c = P  c,p T | c position  p position | log ( k ) (10) where c position and p position denote the positions of a child node c and a parent node p , respectively, in the original sentential sequential order. For instance, in our running example, the parent node s 3 has p position = 3 (i.e., it is the third sentence) and its child node s 5 has c position = 5 . Therefore, their parent-child distance is | 5  3 | = 2 . Following a similar calculation for other parent-child pairs, we have P c = 1+2+2+2 log (5)  10 . Similar to Property 2, Property 3 pertains to the organization of a document and takes into consideration the deviation from sentential sequential order. Intuitively speaking, usually, we expect that a child node and its parent to be close to each other in the original sequential order. Consequently, the less value of this property is, the more coherent a document is likely to be. The range of Property 3 in a document containing k sentences is P c  [ k  1 log ( k ) , k ( k  1) 2 log ( k ) ] . 1. How does the proposed framework perform on fake news detection? 2. How do the defined structure-related properties describe the fake and real news documents? In this section, we first describe the datasets followed by presenting the experimental settings. Afterward, we evaluate the performance of HDSF compared to several representative baselines. Finally, we present a structural analysis of the fake/real news documents. We utilize five available fake news datasets in this study. The first two datasets are collected by (Shu et al., 2017) and include online articles whose veracities have been identified by experts in Buz-zFeed 1 and PolitiFact 2 . For the next two datasets, we utilize two available online fake news datasets provided by kaggle.com 3 4 . Finally, we include the dataset constructed and shared by McIntire 5 . Since the proposed framework HDSF is a general-purpose framework investigating discourse-level structures of fake/real news documents based on their textual contents, we do not restrict HDSF to a particular source of data and therefore combine all datasets. Similar to the previous work (Shu et al., 2017), we balance the dataset to avoid a trivial solution as well as ensuring a fair performance comparison. In total, we have 3360 fake and 3360 real documents. First, we pre-process the documents by removing numbers, non-English characters, stop-words (e.g., with'), and converting all characters to lower case. We randomly select 134 documents as the development set, ( 67 from each class) and 134 documents ( 67 from each class) as the test set. The remaining 6452 documents are used for training. The development set is used for tuning the hyper-parameters. We initialize the word embeddings from the Google news pre-trained word2vec embeddings (Mikolov et al., 2013) 6 . LeakyReLU (Xu et al., 2015) is used as the nonlinear activation function and the number of hidden units in the BLSTM network is set to 100 . Each simulation is run for 200 steps with a random mini-batch size of 40 documents. The learning rate starts at 0 . 01 with the decay rate of 0 . 9 after every 50 steps. We use the ADAM optimizer (Kingma and Ba, 2014) to optimize the parameters. The PyTorch package 7 is utilized for the implementation and the code and data are publicly available in https://github.com/ hamidkarimi/HDSF . 1 https://www.buzzfeed.com 2 http://www.politifact.com/ 3 https://www.kaggle.com/mrisdal/ fake-news/data 4 https://www.kaggle.com/jruvika/ fake-news-detection 5 https://github.com/GeorgeMcIntire/ fake_real_news_dataset 6 Out-of-vocabulary words are initialized randomly. 7 https://pytorch.org/ 5.3 Comparison Results To answer the research question (1), we compare the performance of HDSF with the following representative baselines. N-grams . In this baseline method, we extract and combine unigrams, bigrams, and trigrams features and use SVM (Support Vector Machines) (Scholkopf and Smola, 2001) for classification. LIWC (Pennebaker et al., 2015). LIWC (Lin-guistic Inquiry and Word Count) offers a set of rich psycholinguistic features for a written document. We extract 94 features for each document and use SVM for classification. RST (Rubin and Lukoianova, 2015). We extract a set of RST relations (Mann and Thompson, 1988) using the implementation of the method proposed by (Ji and Eisenstein, 2014). Then, we vectorize the relations and employ SVM for classification. This baseline takes into account the hierarchical structure of documents via RST. BiGRNN-CNN (Ren and Zhang, 2016). A CNN (Convolutional Neural Network) is applied at the sentence-level on word embeddings and a BiGRNN (Bi-Directional Gated Recurrent Neural Network) extracts features from a sequence of extracted sentential features. This baseline takes into consideration a two-level sequential structure for a document. LSTM[w+s] . In this baseline, we apply an LSTM network on a sequence of word embeddings belonging to a sentence and then apply another LSTM on a sequence of extracted sentential features. LSTM[w+s] also considers a two-level sequential structure for a document. LSTM[s] . This method is similar to LSTM[w+s] except that the mean of word embeddings in a sentence is used instead of applying an LSTM network. LSTM[s] considers a single sequential structure for a document. We use accuracy as the metric of performance evaluation given that the dataset is fully balanced. Table 1 shows the comparison results on the test set and we make the following observations:  N-grams achieve a better performance than LIWC. In line with the previous study (Ott et al., 2011), this shows that for fake news detection, taking into account the context of a document as n-grams do is more effective than employing the existing pre-defined dictionaries as LIWC does. Most of the time, methods wherein a document's structure is somehow taken into account outperform n-grams and LIWC. This observation shows that for fake news detection, the content's structure plays an important role. The poor performance of RST is because of the following reasons: a) using RST without an annotated corpus is not very effective, and b) RST relations are extracted using auxiliary tools optimized for other corpora which cannot be applied effectively to the fake news corpus in hand. Note that annotating RST for our corpus is extremely unscalable and time-consuming. The proposed framework HDSF significantly outperforms all other methods. This observation shows that hierarchical discourse-level representations are effectively rich for fake news prediction. To further verify the working of the HDSF framework, we inspect HDSF in more detail. Figure 4a demonstrates the training error during model optimization. As we can observe from this figure, the error is decreasing as the training process proceeds. Furthermore, Figure 4b demonstrates the accuracy on the development set during the training and it is monotonically increasing as the training goes on. Hence, based on these figures, we can ensure the framework is getting optimized and learns to classify fake news documents correctly. In this section, we compute the average values of structure-related properties, presented in Section 4, for the fake/real news documents belonging to the test set. Figure 5 shows the results. We make the two key observations based on this figure:  There is a significant difference in all three properties for fake news documents vs. real news documents. This observation shows the fact that structures of fake news documents at the discourse-level are substantially different from those of real ones . Noticeably, in all three properties, the real news documents show less value than the fake news documents. As described in Section 4, all three properties are closely connected to the coherence of a document. Therefore, real news documents indicate more degree of coherence . Content-based fake news detection has been the subject of many linguistic research endeavors. (DePaulo et al., 2003) investigated fake stories introduced insightful cues in fake stories and highlighted unusual' language in such stories. N-grams and Part-of-Speech (POS) tags are fundamental features of a text which have been utilized for fake news detection (Ahmed et al., 2017; Ott et al., 2013). Also, LIWC (Pennebaker et al., 2015) has been employed to investigate the role of individual words in a document for deception detection (Ott et al., 2011). Since POS tags, n-grams, and LIWC features are considered as shal-low' and hand-crafted features, deep neural networks have been utilized for fake news detection where features are extracted automatically (Wang, 2017; Ren and Zhang, 2016; Volkova et al., 2017; Karimi et al., 2018). In this study, we also utilized an automated feature extraction instead of relying on hand-craft features. Joan Bachenko, Eileen Fitzpatrick, and Michael Schonwetter. 2008. Verification and implementation of language-based deception indicators in civil and criminal narratives. In Proceedings of the 22nd International Conference on Computational Linguistics-Volume 1 , pages 4148. Association for Computational Linguistics. Regina Barzilay and Mirella Lapata. 2008. Modeling local coherence: An entity-based approach. Computational Linguistics , 34(1):134. Parminder Bhatia, Yangfeng Ji, and Jacob Eisenstein. 2015. Better document-level sentiment analysis from rst discourse parsing. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing , pages 22122218. Leon Bottou. 2010. Large-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT'2010 , pages 177186. Springer. Bella M DePaulo, James J Lindsay, Brian E Malone, Laura Muhlenbruck, Kelly Charlton, and Harris Cooper. 2003. Cues to deception. Psychological bulletin , 129(1):74. Song Feng, Ritwik Banerjee, and Yejin Choi. 2012. Syntactic stylometry for deception detection. In Proceedings of the 50th Annual Meeting of the Association for Computational Linguistics: Short Papers-Volume 2 , pages 171175. Association for Computational Linguistics. Camille Guinaudeau and Michael Strube. 2013. Graph-based local coherence modeling. In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , volume 1, pages 93103. Robert Hecht-Nielsen. 1992. Theory of the backprop-agation neural network. In Neural networks for perception , pages 6593. Elsevier. Sepp Hochreiter and Jurgen Schmidhuber. 1997. Long short-term memory. Neural computation , 9(8):17351780. Yangfeng Ji and Jacob Eisenstein. 2014. Representation learning for text-level discourse parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , volume 1, pages 1324. Hamid Karimi, Proteek Roy, Sari Saba-Sadiya, and Jiliang Tang. 2018. Multi-source multi-class fake news detection. In Proceedings of the 27th International Conference on Computational Linguistics , pages 15461557. Yoon Kim, Carl Denton, Luong Hoang, and Alexander M Rush. 2017. Structured attention networks. arXiv preprint arXiv:1702.00887 . Diederik P Kingma and Jimmy Ba. 2014. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 . Jiwei Li and Eduard Hovy. 2014. A model of coherence based on distributed sentence representation. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 20392048. Jiwei Li, Rumeng Li, and Eduard Hovy. 2014a. Recursive deep models for discourse parsing. In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP) , pages 20612069. Sujian Li, Liang Wang, Ziqiang Cao, and Wenjie Li. 2014b. Text-level discourse dependency parsing. In Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) , volume 1, pages 2535. Yang Liu and Mirella Lapata. 2018. Learning structured text representations. Transactions of the Association of Computational Linguistics , 6:6375. William C Mann and Sandra A Thompson. 1988. Rhetorical structure theory: Toward a functional theory of text organization. Text-Interdisciplinary Journal for the Study of Discourse , 8(3):243281. Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013. Efficient estimation of word representations in vector space. arXiv preprint arXiv:1301.3781 . Mathieu Morey, Philippe Muller, and Nicholas Asher. 2018. A dependency perspective on rst discourse parsing and evaluation. Computational Linguistics , (Just Accepted):154. Myle Ott, Claire Cardie, and Jeffrey T Hancock. 2013. Negative deceptive opinion spam. In Proceedings of the 2013 conference of the north american chapter of the association for computational linguistics: human language technologies , pages 497501. James W Pennebaker, Ryan L Boyd, Kayla Jordan, and Kate Blackburn. 2015. The development and psychometric properties of liwc2015. Ziheng Lin, Hwee Tou Ng, and Min-Yen Kan. 2011. Automatically evaluating text coherence using discourse relations. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1 , pages 9971006. Association for Computational Linguistics. Myle Ott, Yejin Choi, Claire Cardie, and Jeffrey T Hancock. 2011. Finding deceptive opinion spam by any stretch of the imagination. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies-Volume 1 , pages 309319. Association for Computational Linguistics. Technical report. Veronica Perez-Rosas and Rada Mihalcea. 2015. Experiments in open domain deception detection. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing , pages 11201125. Rashmi Prasad, Eleni Miltsakaki, Nikhil Dinesh, Alan Lee, Aravind Joshi, Livio Robaldo, and Bonnie L Webber. 2007. The penn discourse treebank 2.0 annotation manual. Yafeng Ren and Yue Zhang. 2016. Deceptive opinion spam detection using neural network. In Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers , pages 140150. Victoria L Rubin and Tatiana Lukoianova. 2015. Truth and deception at the rhetorical structure level. Journal of the Association for Information Science and Technology , 66(5):905917. Bernhard Scholkopf and Alexander J Smola. 2001. Learning with kernels: support vector machines, regularization, optimization, and beyond . MIT press. Mike Schuster and Kuldip K Paliwal. 1997. Bidirectional recurrent neural networks. IEEE Transactions on Signal Processing , 45(11):26732681. Kai Shu, Suhang Wang, and Huan Liu. 2017. Exploiting tri-relationship for fake news detection. arXiv preprint arXiv:1712.07709 . Angelika Storrer. 2002. Coherence in text and hyper-text. Document Design , 3(2):156168. Alexander Strehl and Joydeep Ghosh. 2000. Impact of similarity measures on web-page clustering. Svitlana Volkova, Kyle Shaffer, Jin Yea Jang, and Nathan Hodas. 2017. Separating facts from fiction: Linguistic models to classify suspicious and trusted news posts on twitter. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers) , volume 2, pages 647653. William Yang Wang. 2017. liar, liar pants on fire: A new benchmark dataset for fake news detection. arXiv preprint arXiv:1705.00648 .
abstain abstain abstain abstain abstain abstain objective abstain method abstain abstain method abstain abstain abstain abstain abstain abstain objective abstain abstain abstain abstain abstain abstain method abstain result objective method abstain abstain abstain abstain abstain abstain abstain abstain objective abstain abstain abstain abstain abstain abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain abstain abstain abstain abstain abstain abstain abstain other abstain abstain method abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain other other other abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain abstain abstain abstain abstain abstain abstain abstain abstain result abstain result abstain abstain abstain abstain abstain result abstain abstain abstain abstain other other other other other method other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other other