A graph-theoretic approach to webpage segmentation

ABSTRACT

We consider the problem of segmenting a webpage into visually and semantically cohesive pieces. Our approach is based on formulating an appropriate optimization problem on weighted graphs, where the weights capture if two nodes in the DOM tree should be placed together or apart in the segmentation; we present a learning framework to learn these weights from manually labeled data in a principled manner. Our work is a significant departure from previous heuristic and rule-based solutions to the segmentation problem. The results of our empirical analysis bring out interesting aspects of our framework, including variants of the optimization problem and the role of learning.

REFERENCES

• 1: Nir Ailon , Moses Charikar , Alantha Newman, Aggregating inconsistent information: ranking and clustering, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060692]
• 2: Shumeet Baluja, Browsing on small screens: recasting web-page segmentation into an efficient machine learning framework, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135788]
• 3: Ziv Bar-Yossef , Sridhar Rajagopalan, Template detection via data mining and its applications, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511522]
• 4: Krishna Bharat , Andrei Broder , Jeffrey Dean , Monika R. Henzinger, A comparison of techniques to find mirrored hosts on the WWW, Journal of the American Society for Information Science, v.51 n.12, p.1114-1122, Oct. 2000 [doi>10.1002/1097-4571(2000)9999:9999<::AID-ASI1025>3.0.CO;2-0]
• 5: Yuri Boykov , Olga Veksler , Ramin Zabih, Fast Approximate Energy Minimization via Graph Cuts, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.23 n.11, p.1222-1239, November 2001 [doi>10.1109/34.969114]
• 6: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 7: D. Cai, S. Yu, J.-R. Wen, and W.-Y. Ma. Extracting content structure for web pages based on visual representation. In 5th Asia Pacific Web Conference, pages 406--415, 2003.
• 8: Deepayan Chakrabarti , Ravi Kumar , Kunal Punera, Page-level template detection via isotonic smoothing, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242582]
• 9: Soumen Chakrabarti , Mukul Joshi , Vivek Tawde, Enhanced topic distillation using text, markup tags, and hyperlinks, Proceedings of the 24th annual international ACM SIGIR conference on Research and development in information retrieval, p.208-216, September 2001, New Orleans, Louisiana, United States [doi>10.1145/383952.383990]
• 10: Yu Chen , Xing Xie , Wei-Ying Ma , Hong-Jiang Zhang, Adapting Web Pages for Small-Screen Devices, IEEE Internet Computing, v.9 n.1, p.50-56, January 2005 [doi>10.1109/MIC.2005.5]
• 11: David Gibson , Kunal Punera , Andrew Tomkins, The volume and evolution of web page templates, Special interest tracks and posters of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1062745.1062763]
• 12: L. Hubert and P. Arabie. Comparing partitions. J. Classification, 2:193--218, 1985.
• 13: Hung-Yu Kao , Jan-Ming Ho , Ming-Syan Chen, WISDOM: Web Intrapage Informative Structure Mining Based on Document Object Model, IEEE Transactions on Knowledge and Data Engineering, v.17 n.5, p.614-627, May 2005 [doi>10.1109/TKDE.2005.84]
• 14: Jon Kleinberg , Éva Tardos, Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields, Journal of the ACM (JACM), v.49 n.5, p.616-639, September 2002 [doi>10.1145/585265.585268]
• 15: Vladimir Kolmogorov , Ramin Zabih, What Energy Functions Can Be Minimizedvia Graph Cuts?, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.26 n.2, p.147-159, January 2004 [doi>10.1109/TPAMI.2004.1262177]
• 16: G. Milligan and M. Cooper. A study of the comparability of external criteria for hierarchical cluster analysis. Multivariate Behavioral Research, 21(4):441--458, 1986.
• 17: Thomas M. Mitchell, Machine Learning, McGraw-Hill Higher Education, 1997
• 18: Alexander Strehl , Joydeep Ghosh, Cluster ensembles --- a knowledge reuse framework for combining multiple partitions, The Journal of Machine Learning Research, 3, p.583-617, 3/1/2003 [doi>10.1162/153244303321897735]
• 19: K. Weinberger, J. Blitzer, and L. Saul. Distance metric learning for large margin nearest neighbor classification. In NIPS 2006, pages 1473--1480, 2006.
• 20: Xinyi Yin , Wee Sun Lee, Using link analysis to improve layout on mobile devices, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988718]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.m Miscellaneous

General Terms:
Algorithms, Experimentation

Keywords:
correlation clustering, energy minimization, graph cuts, webpage sectioning, webpage segmentation